Metrics on Markov Equivalence Classes for Evaluating Causal Discovery Algorithms

• URL: http://arxiv.org/abs/2402.04952v2
• Date: Fri, 15 Mar 2024 17:21:56 GMT
• Title: Metrics on Markov Equivalence Classes for Evaluating Causal Discovery Algorithms
• Authors: Jonas Wahl, Jakob Runge,
• Abstract summary: We argue that an evaluation of a causal discovery method against synthetic data should include an analysis of how well this explicit goal is achieved. We show that established evaluation measures do not accurately capture the difference in separations/connections of two causal graphs. We introduce three new measures of distance called s/c-distance, Markov distance and Faithfulness distance that address this shortcoming.
• Score: 15.37737222790121
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many state-of-the-art causal discovery methods aim to generate an output graph that encodes the graphical separation and connection statements of the causal graph that underlies the data-generating process. In this work, we argue that an evaluation of a causal discovery method against synthetic data should include an analysis of how well this explicit goal is achieved by measuring how closely the separations/connections of the method's output align with those of the ground truth. We show that established evaluation measures do not accurately capture the difference in separations/connections of two causal graphs, and we introduce three new measures of distance called s/c-distance, Markov distance and Faithfulness distance that address this shortcoming. We complement our theoretical analysis with toy examples, empirical experiments and pseudocode.

Related papers

• Measuring Similarity in Causal Graphs: A Framework for Semantic and Structural Analysis [0.7373617024876725]
  Causal graphs are commonly used to understand and model complex systems. Researchers often construct these graphs from different perspectives, leading to significant variations for the same problem. Despite its importance, research on causal graph comparison remains scarce.
  arXiv  Detail & Related papers  (2025-03-14T03:29:26Z)
• Adjustment Identification Distance: A gadjid for Causal Structure Learning [2.72836834536003]
  We develop a framework for developing causal distances between graphs. We use this framework to develop improved adjustment-based distances as well as extensions to completed partially directed acyclic graphs and causal orders.
  arXiv  Detail & Related papers  (2024-02-13T17:32:59Z)
• A continuous Structural Intervention Distance to compare Causal Graphs [5.477914707166288]
  The distance is based on embedding intervention distributions over each pair of nodes. We show theoretical results which we validate with numerical experiments on synthetic data.
  arXiv  Detail & Related papers  (2023-07-31T07:20:26Z)
• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  We propose a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation. We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
  arXiv  Detail & Related papers  (2023-06-05T00:01:17Z)
• Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality [3.1219977244201056]
  This technical report studies the problem of ranking from pairwise comparisons in the classical Bradley-Terry-Luce (BTL) model. We show that, with sufficiently many samples, maximum likelihood estimation (MLE) achieves an entrywise estimation error matching the Cram'er-Rao lower bound. We explore divide-and-conquer algorithms that can provably achieve similar guarantees even in the regime with the sparsest samples.
  arXiv  Detail & Related papers  (2023-04-13T21:14:30Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Kernel distance measures for time series, random fields and other structured data [71.61147615789537]
  kdiff is a novel kernel-based measure for estimating distances between instances of structured data. It accounts for both self and cross similarities across the instances and is defined using a lower quantile of the distance distribution. Some theoretical results are provided for separability conditions using kdiff as a distance measure for clustering and classification problems.
  arXiv  Detail & Related papers  (2021-09-29T22:54:17Z)
• FGOT: Graph Distances based on Filters and Optimal Transport [62.779521543654134]
  Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph distance approximation.
  arXiv  Detail & Related papers  (2021-09-09T17:43:07Z)
• Graph topology inference benchmarks for machine learning [16.857405938139525]
  We introduce several benchmarks specifically designed to reveal the relative merits and limitations of graph inference methods. We also contrast some of the most prominent techniques in the literature.
  arXiv  Detail & Related papers  (2020-07-16T09:40:32Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs [6.72542623686684]
  We propose SLaQ, an efficient and effective approximation technique for computing spectral distances between graphs with billions of nodes and edges. We show that SLaQ outperforms existing methods, oftentimes by several orders of magnitude in approximation accuracy.
  arXiv  Detail & Related papers  (2020-03-03T01:25:07Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.