Collaborative Causal Discovery with Atomic Interventions

• URL: http://arxiv.org/abs/2106.03028v1
• Date: Sun, 6 Jun 2021 04:30:29 GMT
• Title: Collaborative Causal Discovery with Atomic Interventions
• Authors: Raghavendra Addanki, Shiva Prasad Kasiviswanathan
• Abstract summary: We model a common scenario in which we have multiple independent entities each with their own causal graph. The goal is to simultaneously learn all these causal graphs. We study this problem without the causal sufficiency assumption.
• Score: 12.18848217289866
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a new Collaborative Causal Discovery problem, through which we model a common scenario in which we have multiple independent entities each with their own causal graph, and the goal is to simultaneously learn all these causal graphs. We study this problem without the causal sufficiency assumption, using Maximal Ancestral Graphs (MAG) to model the causal graphs, and assuming that we have the ability to actively perform independent single vertex (or atomic) interventions on the entities. If the $M$ underlying (unknown) causal graphs of the entities satisfy a natural notion of clustering, we give algorithms that leverage this property and recovers all the causal graphs using roughly logarithmic in $M$ number of atomic interventions per entity. These are significantly fewer than $n$ atomic interventions per entity required to learn each causal graph separately, where $n$ is the number of observable nodes in the causal graph. We complement our results with a lower bound and discuss various extensions of our collaborative setting.

Related papers

• Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents [27.4884498301785]
  We introduce GraphAgent-Reasoner, a fine-tuning-free framework for explicit and precise graph reasoning. Inspired by distributed graph computation theory, our framework decomposes graph problems into smaller, node-centric tasks that are distributed among multiple agents. Our framework demonstrates the capability to handle real-world graph reasoning applications such as webpage importance analysis.
  arXiv  Detail & Related papers  (2024-10-07T15:34:14Z)
• Generalization of Graph Neural Networks is Robust to Model Mismatch [84.01980526069075]
  Graph neural networks (GNNs) have demonstrated their effectiveness in various tasks supported by their generalization capabilities. In this paper, we examine GNNs that operate on geometric graphs generated from manifold models. Our analysis reveals the robustness of the GNN generalization in the presence of such model mismatch.
  arXiv  Detail & Related papers  (2024-08-25T16:00:44Z)
• Causal Discovery with Fewer Conditional Independence Tests [15.876392307650248]
  Our work focuses on characterizing what can be learned about the underlying causal graph with a reduced number of conditional independence tests. We show that it is possible to learn a coarser representation of the hidden causal graph with a number of tests. As a consequence, our results offer the first efficient algorithm for recovering the true causal graph with a number of tests.
  arXiv  Detail & Related papers  (2024-06-03T22:27:09Z)
• Towards Self-Interpretable Graph-Level Anomaly Detection [73.1152604947837]
  Graph-level anomaly detection (GLAD) aims to identify graphs that exhibit notable dissimilarity compared to the majority in a collection. We propose a Self-Interpretable Graph aNomaly dETection model ( SIGNET) that detects anomalous graphs as well as generates informative explanations simultaneously.
  arXiv  Detail & Related papers  (2023-10-25T10:10:07Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  Graph neural networks (GNNs) rely on the message passing paradigm to propagate node features and build interactions. Recent works point out that different graph learning tasks require different ranges of interactions between nodes. We study two common graph construction methods in scientific domains, i.e., emphK-nearest neighbor (KNN) graphs and emphfully-connected (FC) graphs.
  arXiv  Detail & Related papers  (2022-05-15T11:38:14Z)
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification [59.06717774425588]
  We propose the Explicit Pairwise Factorized Graph Neural Network (EPFGNN), which models the whole graph as a partially observed Markov Random Field. It contains explicit pairwise factors to model output-output relations and uses a GNN backbone to model input-output relations. We conduct experiments on various datasets, which shows that our model can effectively improve the performance for semi-supervised node classification on graphs.
  arXiv  Detail & Related papers  (2021-07-27T19:47:53Z)
• Causal Bandits on General Graphs [1.4502611532302039]
  We study the problem of determining the best intervention in a Causal Bayesian Network (CBN) specified only by its causal graph. We propose a simple regret minimization algorithm that takes as input a semi-Markovian causal graph with atomic interventions and possibly unobservable variables. Our results indicate that the simple regret guarantee of our proposed algorithm can only be improved by considering more nuanced structural restrictions on the causal graph.
  arXiv  Detail & Related papers  (2021-07-06T17:29:45Z)
• Non-isomorphic Inter-modality Graph Alignment and Synthesis for Holistic Brain Mapping [1.433758865948252]
  We propose an inter-modality aligner of non-isomorphic graphs (IMANGraphNet) framework to infer a target graph modality based on a given modality. Our three core contributions lie in (i) predicting a target graph (e.g., functional) from a source graph (e.g., morphological) based on a novel graph generative adversarial network (gGAN) Our comprehensive experiments on predicting functional from morphological graphs demonstrate the outperformance of IMANGraphNet in comparison with its variants.
  arXiv  Detail & Related papers  (2021-06-30T08:59:55Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  We introduce a novel graph convolutional network (GCN) that explicitly disentangles intertwined relations encoded in a graph. FactorGCN takes a simple graph as input, and disentangles it into several factorized graphs. We evaluate the proposed FactorGCN both qualitatively and quantitatively on the synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2020-10-12T03:01:40Z)
• 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.