Separation-based distance measures for causal graphs

• URL: http://arxiv.org/abs/2402.04952v3
• Date: Thu, 31 Oct 2024 16:55:51 GMT
• Title: Separation-based distance measures for causal graphs
• Authors: Jonas Wahl, Jakob Runge,
• Abstract summary: State-of-the-art causal discovery methods do not output single causal graphs, but rather their equivalence classes (MECs) We propose additional measures of distance that capture the difference in separations distances are not fit to assess. We complement our theoretical analysis with toy examples and empirical experiments that highlight the differences to existing comparison metrics.
• Score: 15.37737222790121
• License:
• Abstract: Assessing the accuracy of the output of causal discovery algorithms is crucial in developing and comparing novel methods. Common evaluation metrics such as the structural Hamming distance are useful for assessing individual links of causal graphs. However, many state-of-the-art causal discovery methods do not output single causal graphs, but rather their Markov equivalence classes (MECs) which encode all of the graph's separation and connection statements. In this work, we propose additional measures of distance that capture the difference in separations of two causal graphs which link-based distances are not fit to assess. The proposed distances have low polynomial time complexity and are applicable to directed acyclic graphs (DAGs) as well as to maximal ancestral graph (MAGs) that may contain bidirected edges. We complement our theoretical analysis with toy examples and empirical experiments that highlight the differences to existing comparison metrics.

Related papers

• 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.