ION-C: Integration of Overlapping Networks via Constraints

• URL: http://arxiv.org/abs/2411.04243v1
• Date: Wed, 06 Nov 2024 20:12:47 GMT
• Title: ION-C: Integration of Overlapping Networks via Constraints
• Authors: Praveen Nair, Payal Bhandari, Mohammadsajad Abavisani, Sergey Plis, David Danks,
• Abstract summary: We present the first algorithm for enumerating the minimal equivalence class of ground-truth DAGs consistent with all input graphs by exploiting local independence relations, called ION. The ION-C algorithm was run on random synthetic graphs with varying sizes, densities, and degrees of overlap between subgraphs. To validate ION-C on real-world data, we ran the algorithm on overlapping graphs learned from data from two successive iterations of the European Social Survey (ESS)
• Score: 2.6068919473964893
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In many causal learning problems, variables of interest are often not all measured over the same observations, but are instead distributed across multiple datasets with overlapping variables. Tillman et al. (2008) presented the first algorithm for enumerating the minimal equivalence class of ground-truth DAGs consistent with all input graphs by exploiting local independence relations, called ION. In this paper, this problem is formulated as a more computationally efficient answer set programming (ASP) problem, which we call ION-C, and solved with the ASP system clingo. The ION-C algorithm was run on random synthetic graphs with varying sizes, densities, and degrees of overlap between subgraphs, with overlap having the largest impact on runtime, number of solution graphs, and agreement within the output set. To validate ION-C on real-world data, we ran the algorithm on overlapping graphs learned from data from two successive iterations of the European Social Survey (ESS), using a procedure for conducting joint independence tests to prevent inconsistencies in the input.

Related papers

• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC. It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters. GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies [49.99600569996907]
  Testing a hypothesized causal model against observational data is a key prerequisite for many causal inference tasks. While a model can assume exponentially many conditional independence relations (CIs), testing all of them is both impractical and unnecessary. We introduce c-LMP for causal graphs with hidden variables and develop a delay algorithm to list these CIs in poly-time intervals.
  arXiv  Detail & Related papers  (2024-09-22T21:05:56Z)
• DCILP: A Distributed Approach for Large-Scale Causal Structure Learning [4.551283926017506]
  Causal learning tackles the computationally demanding task of estimating causal graphs. This paper introduces a new divide-and-conquer approach for causal graph learning, called DCILP.
  arXiv  Detail & Related papers  (2024-06-15T03:17:48Z)
• DPGAN: A Dual-Path Generative Adversarial Network for Missing Data Imputation in Graphs [17.847551850315895]
  This paper proposes a novel framework, called Dual-Pathrative Adversarial Network (DPGAN) DPGAN can deal simultaneously with missing data and avoid over-smoothing problems. Comprehensive experiments across various benchmark datasets substantiate that DPGAN consistently rivals, if not outperforms, existing state-of-the-art imputation algorithms.
  arXiv  Detail & Related papers  (2024-04-26T05:26:10Z)
• Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalization [60.4169201192582]
  We propose to incorporate label and environment causal independence (LECI) to fully make use of label and environment information. LECI significantly outperforms prior methods on both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-01T19:33:30Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Personalized Decentralized Multi-Task Learning Over Dynamic Communication Graphs [59.96266198512243]
  We propose a decentralized and federated learning algorithm for tasks that are positively and negatively correlated. Our algorithm uses gradients to calculate the correlations among tasks automatically, and dynamically adjusts the communication graph to connect mutually beneficial tasks and isolate those that may negatively impact each other. We conduct experiments on a synthetic Gaussian dataset and a large-scale celebrity attributes (CelebA) dataset.
  arXiv  Detail & Related papers  (2022-12-21T18:58:24Z)
• NetRCA: An Effective Network Fault Cause Localization Algorithm [22.88986905436378]
  Localizing root cause of network faults is crucial to network operation and maintenance. We propose a novel algorithm named NetRCA to deal with this problem. Experiments and analysis are conducted on the real-world dataset from ICASSP 2022 AIOps Challenge.
  arXiv  Detail & Related papers  (2022-02-23T02:03:35Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. An $varepsilon$-solution is achieved in $tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$ number of communications steps. This rate matches (up to poly-log factors) for the first time lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest.
  arXiv  Detail & Related papers  (2021-10-24T04:03:00Z)
• A Single Iterative Step for Anytime Causal Discovery [7.570246812206772]
  We present a sound and complete algorithm for recovering causal graphs from observed, non-interventional data. We rely on the causal Markov and faithfulness assumptions and recover the equivalence class of the underlying causal graph. We demonstrate that our algorithm requires significantly fewer CI tests and smaller condition sets compared to the FCI algorithm.
  arXiv  Detail & Related papers  (2020-12-14T13:46:01Z)
• Exploiting non-i.i.d. data towards more robust machine learning algorithms [0.0]
  Machine learning algorithms have increasingly been shown to excel in finding patterns and correlations from data. In this paper a regularization scheme is introduced that prefers universal causal correlations. A better performance is obtained on an out-of-distribution test set with respect to a more conventional l-regularization.
  arXiv  Detail & Related papers  (2020-10-07T14:15:37Z)

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.