Redefining the Shortest Path Problem Formulation of the Linear
  Non-Gaussian Acyclic Model: Pairwise Likelihood Ratios, Prior Knowledge, and
  Path Enumeration
Hans Jarett J. Ong Brian Godwin S. Lim
Effective causal discovery is essential for learning the causal graph from
observational data. The linear non-Gaussian acyclic model (LiNGAM) operates
under the assumption of a linear data generating process with non-Gaussian
noise in determining the causal graph. Its assumption of unmeasured confounders
being absent, however, poses practical limitations. In response, empirical
research has shown that the reformulation of LiNGAM as a shortest path problem
(LiNGAM-SPP) addresses this limitation. Within LiNGAM-SPP, mutual information
is chosen to serve as the measure of independence. A challenge is introduced -
parameter tuning is now needed due to its reliance on kNN mutual information
estimators. The paper proposes a threefold enhancement to the LiNGAM-SPP
framework.
  First, the need for parameter tuning is eliminated by using the pairwise
likelihood ratio in lieu of kNN-based mutual information. This substitution is
validated on a general data generating process and benchmark real-world data
sets, outperforming existing methods especially when given a larger set of
features. The incorporation of prior knowledge is then enabled by a
node-skipping strategy implemented on the graph representation of all causal
orderings to eliminate violations based on the provided input of relative
orderings. Flexibility relative to existing approaches is achieved. Last among
the three enhancements is the utilization of the distribution of paths in the
graph representation of all causal orderings. From this, crucial properties of
the true causal graph such as the presence of unmeasured confounders and
sparsity may be inferred. To some extent, the expected performance of the
causal discovery algorithm may be predicted. The refinements above advance the
practicality and performance of LiNGAM-SPP, showcasing the potential of
graph-search-based methodologies in advancing causal discovery.