Adjustment Identification Distance: A gadjid for Causal Structure Learning

• URL: http://arxiv.org/abs/2402.08616v2
• Date: Thu, 11 Jul 2024 13:45:33 GMT
• Title: Adjustment Identification Distance: A gadjid for Causal Structure Learning
• Authors: Leonard Henckel, Theo Würtzen, Sebastian Weichwald,
• Abstract summary: 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.
• Score: 2.72836834536003
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evaluating graphs learned by causal discovery algorithms is difficult: The number of edges that differ between two graphs does not reflect how the graphs differ with respect to the identifying formulas they suggest for causal effects. We introduce a framework for developing causal distances between graphs which includes the structural intervention distance for directed acyclic graphs as a special case. We use this framework to develop improved adjustment-based distances as well as extensions to completed partially directed acyclic graphs and causal orders. We develop new reachability algorithms to compute the distances efficiently and to prove their low polynomial time complexity. In our package gadjid (open source at https://github.com/CausalDisco/gadjid), we provide implementations of our distances; they are orders of magnitude faster with proven lower time complexity than the structural intervention distance and thereby provide a success metric for causal discovery that scales to graph sizes that were previously prohibitive.

Related papers

• Separation-based distance measures for causal graphs [15.37737222790121]
  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.
  arXiv  Detail & Related papers  (2024-02-07T15:36:53Z)
• Exploiting Edge Features in Graphs with Fused Network Gromov-Wasserstein Distance [18.522233517515975]
  We introduce an extension of Gromov-Wasserstein distance for comparing graphs whose both nodes and edges have features. We empirically show the effectiveness of the novel distance in learning tasks where graphs occur in either input space or output space.
  arXiv  Detail & Related papers  (2023-09-28T17:05:03Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
  We show that graph embedding in non-Euclidean metric space can outperform that in Euclidean space with much smaller training data than the existing bound has suggested. Our new upper bound is significantly tighter and faster than the existing one, which can be exponential to $R$ and $O(frac1S)$ at the fastest.
  arXiv  Detail & Related papers  (2023-05-13T17:29:18Z)
• E-Graph: Minimal Solution for Rigid Rotation with Extensibility Graphs [61.552125054227595]
  A new minimal solution is proposed to solve relative rotation estimation between two images without overlapping areas. Based on E-Graph, the rotation estimation problem becomes simpler and more elegant. We embed our rotation estimation strategy into a complete camera tracking and mapping system which obtains 6-DoF camera poses and a dense 3D mesh model.
  arXiv  Detail & Related papers  (2022-07-20T16:11:48Z)
• 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)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching. The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k) It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
  arXiv  Detail & Related papers  (2021-09-01T08:24:02Z)
• A step towards neural genome assembly [0.0]
  We train the MPNN model with max-aggregator to execute several algorithms for graph simplification. We show that the algorithms were learned successfully and can be scaled to graphs of sizes up to 20 times larger than the ones used in training.
  arXiv  Detail & Related papers  (2020-11-10T10:12:19Z)
• Wasserstein Embedding for Graph Learning [33.90471037116372]
  Wasserstein Embedding for Graph Learning (WEGL) is a framework for embedding entire graphs in a vector space. We leverage new insights on defining similarity between graphs as a function of the similarity between their node embedding distributions. We evaluate our new graph embedding approach on various benchmark graph-property prediction tasks.
  arXiv  Detail & Related papers  (2020-06-16T18:23:00Z)
• 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)

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.