Extremely Greedy Equivalence Search

• URL: http://arxiv.org/abs/2502.19551v1
• Date: Wed, 26 Feb 2025 20:45:04 GMT
• Title: Extremely Greedy Equivalence Search
• Authors: Achille Nazaret, David Blei,
• Abstract summary: We propose eXtremely Greedy Equivalent Search (XGES) to improve the search strategy of Greedy Equivalence Search (GES)<n>XGES favors deleting edges early in the search over inserting edges, which reduces the possibility of the search ending in local optima.<n>XGES consistently outperforms GES in recovering the correct graphs, and it is 10 times faster.
• Score: 2.486161976966064
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The goal of causal discovery is to learn a directed acyclic graph from data. One of the most well-known methods for this problem is Greedy Equivalence Search (GES). GES searches for the graph by incrementally and greedily adding or removing edges to maximize a model selection criterion. It has strong theoretical guarantees on infinite data but can fail in practice on finite data. In this paper, we first identify some of the causes of GES's failure, finding that it can get blocked in local optima, especially in denser graphs. We then propose eXtremely Greedy Equivalent Search (XGES), which involves a new heuristic to improve the search strategy of GES while retaining its theoretical guarantees. In particular, XGES favors deleting edges early in the search over inserting edges, which reduces the possibility of the search ending in local optima. A further contribution of this work is an efficient algorithmic formulation of XGES (and GES). We benchmark XGES on simulated datasets with known ground truth. We find that XGES consistently outperforms GES in recovering the correct graphs, and it is 10 times faster. XGES implementations in Python and C++ are available at https://github.com/ANazaret/XGES.

Related papers

• Competition is the key: A Game Theoretic Causal Discovery Approach [2.248800010440909]
  We introduce a game-theoretic reinforcement learning framework for causal discovery.<n>A DDQN agent directly competes against a strong baseline (GES or GraN-DAG), always warm-starting from the opponent's solution.<n>This design yields three provable guarantees: the learned graph is never worse than the opponent, warm-starting strictly accelerates convergence, and most importantly, with high probability the algorithm selects the true best candidate graph.
  arXiv  Detail & Related papers  (2025-10-23T01:19:21Z)
• Less Greedy Equivalence Search [52.30805873759552]
  Greedy Equivalence Search (GES) is a score-based algorithm for causal discovery from observational data.<n>We develop Less Greedy Equivalence Search (LGES), a variant of GES that retains its theoretical guarantees while partially addressing these limitations.<n>We prove that LGES recovers the true equivalence class in the sample limit from observational and interventional data, even with misspecified prior assumptions.
  arXiv  Detail & Related papers  (2025-06-27T15:39:48Z)
• Why Does Dropping Edges Usually Outperform Adding Edges in Graph Contrastive Learning? [54.44813218411879]
  We introduce a new metric, namely Error Passing Rate (EPR), to quantify how a graph fits the network.<n>Inspired by the theoretical conclusions and the idea of positive-incentive noise, we propose a novel GCL algorithm, Error-PAssing-based Graph Contrastive Learning (EPAGCL)<n>We generate views by adding and dropping edges based on the weights derived from EPR.
  arXiv  Detail & Related papers  (2024-12-11T06:31:06Z)
• Efficient Graph Encoder Embedding for Large Sparse Graphs in Python [3.5374094795720854]
  Graph Embedding (GEE) has been shown as the fastest graph embedding technique and is suitable for a variety of network data applications. We propose an improved version of GEE, sparse GEE, which optimize the calculation and storage of zero entries in sparse matrices to enhance the running time further. Our experiments demonstrate that the sparse version achieves significant speedup compared to the original GEE with Python implementation for large sparse graphs, and sparse GEE is capable of processing millions of edges within minutes on a standard laptop.
  arXiv  Detail & Related papers  (2024-06-06T03:49:34Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection [44.501646702560635]
  GADBench is a benchmark tool dedicated to supervised anomalous node detection in static graphs. Our main finding is that tree ensembles with simple neighborhood aggregation can outperform the latest GNNs tailored for the GAD task.
  arXiv  Detail & Related papers  (2023-06-21T13:16:10Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• Limited Query Graph Connectivity Test [14.108454811023465]
  We consider a graph whose edges have two possible states (On/Off) We aim to test s-t connectivity by identifying either a path (consisting of only On edges) or a cut (consisting of only Off edges) Our model is mainly motivated by a cyber security use case where we need to establish whether an attack path exists in a network.
  arXiv  Detail & Related papers  (2023-02-25T09:27:02Z)
• Source Free Unsupervised Graph Domain Adaptation [60.901775859601685]
  Unsupervised Graph Domain Adaptation (UGDA) shows its practical value of reducing the labeling cost for node classification. Most existing UGDA methods heavily rely on the labeled graph in the source domain. In some real-world scenarios, the source graph is inaccessible because of privacy issues. We propose a novel scenario named Source Free Unsupervised Graph Domain Adaptation (SFUGDA)
  arXiv  Detail & Related papers  (2021-12-02T03:18:18Z)
• Graph Traversal with Tensor Functionals: A Meta-Algorithm for Scalable Learning [29.06880988563846]
  Graph Traversal via Functionals(GTTF) is a unifying meta-algorithm framework for embedding graph algorithms. We show for a wide class of methods, our learns in an unbiased fashion and, in expectation, approximates the learning as if the specialized implementations were run directly.
  arXiv  Detail & Related papers  (2021-02-08T16:52:52Z)
• Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
  We introduce an efficient algorithm for finding sparse permutations of a directed acyclic graph. We show that our method with depth $w$ runs in $O(pw+3)$ time. We also compare our algorithm to provably consistent causal structure learning algorithms, such as the PC algorithm, GES, and GSP, and show that our method achieves comparable performance with a shorter runtime.
  arXiv  Detail & Related papers  (2020-11-06T21:56:41Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Heuristic Semi-Supervised Learning for Graph Generation Inspired by Electoral College [80.67842220664231]
  We propose a novel pre-processing technique, namely ELectoral COllege (ELCO), which automatically expands new nodes and edges to refine the label similarity within a dense subgraph. In all setups tested, our method boosts the average score of base models by a large margin of 4.7 points, as well as consistently outperforms the state-of-the-art.
  arXiv  Detail & Related papers  (2020-06-10T14:48:48Z)

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.