Pruning Spurious Subgraphs for Graph Out-of-Distribtuion Generalization

• URL: http://arxiv.org/abs/2506.05957v3
• Date: Wed, 11 Jun 2025 12:14:41 GMT
• Title: Pruning Spurious Subgraphs for Graph Out-of-Distribtuion Generalization
• Authors: Tianjun Yao, Haoxuan Li, Yongqiang Chen, Tongliang Liu, Le Song, Eric Xing, Zhiqiang Shen,
• Abstract summary: We propose PrunE, the first pruning-based graph OOD method that eliminates spurious edges to improve OOD generalizability.<n>PrunE employs two regularization terms to prune spurious edges: 1) graph size constraint to exclude uninformative spurious edges, and 2) $epsilon$-probability alignment to further suppress the occurrence of spurious edges.
• Score: 90.32406785945223
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) often encounter significant performance degradation under distribution shifts between training and test data, hindering their applicability in real-world scenarios. Recent studies have proposed various methods to address the out-of-distribution generalization challenge, with many methods in the graph domain focusing on directly identifying an invariant subgraph that is predictive of the target label. However, we argue that identifying the edges from the invariant subgraph directly is challenging and error-prone, especially when some spurious edges exhibit strong correlations with the targets. In this paper, we propose PrunE, the first pruning-based graph OOD method that eliminates spurious edges to improve OOD generalizability. By pruning spurious edges, PrunE retains the invariant subgraph more comprehensively, which is critical for OOD generalization. Specifically, PrunE employs two regularization terms to prune spurious edges: 1) graph size constraint to exclude uninformative spurious edges, and 2) $\epsilon$-probability alignment to further suppress the occurrence of spurious edges. Through theoretical analysis and extensive experiments, we show that PrunE achieves superior OOD performance and outperforms previous state-of-the-art methods significantly. Codes are available at: \href{https://github.com/tianyao-aka/PrunE-GraphOOD}{https://github.com/tianyao-aka/PrunE-GraphOOD}.

Related papers

• 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)
• Dissecting the Failure of Invariant Learning on Graphs [36.11431280689549]
  We develop a Structural Causal Model (SCM) to theoretically dissect the performance of two prominent invariant learning methods.<n>We propose Cross-environment Intra-class Alignment (CIA), which explicitly eliminates spurious features by aligning cross-environment representations conditioned on the same class.<n>We further propose CIA-LRA (Localized Reweighting Alignment) that leverages the distribution of neighboring labels to selectively align node representations.
  arXiv  Detail & Related papers  (2024-11-05T06:36:48Z)
• Subgraph Aggregation for Out-of-Distribution Generalization on Graphs [29.884717215947745]
  SubGraph Aggregation (SuGAr) is designed to learn a diverse set of subgraphs that are crucial for OOD generalization on graphs.<n>Experiments on both synthetic and real-world datasets demonstrate that SuGAr outperforms state-of-the-art methods, achieving up to a 24% improvement in OOD generalization on graphs.
  arXiv  Detail & Related papers  (2024-10-29T16:54:37Z)
• Graph Anomaly Detection with Noisy Labels by Reinforcement Learning [13.135788402192215]
  We propose a novel framework REGAD, i.e., REinforced Graph Anomaly Detector. Specifically, we aim to maximize the performance improvement (AUC) of a base detector by cutting noisy edges approximated through the nodes with high-confidence labels.
  arXiv  Detail & Related papers  (2024-07-08T13:41:21Z)
• ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks [53.41164429486268]
  Graph Neural Networks (GNNs) have exhibited the powerful ability to gather graph-structured information from neighborhood nodes. The performance of GNNs is limited by poor generalization and fragile robustness caused by noisy and redundant graph data. We propose a novel adversarial edge-dropping method (ADEdgeDrop) that leverages an adversarial edge predictor guiding the removal of edges.
  arXiv  Detail & Related papers  (2024-03-14T08:31:39Z)
• Graph Out-of-Distribution Generalization via Causal Intervention [69.70137479660113]
  We introduce a conceptually simple yet principled approach for training robust graph neural networks (GNNs) under node-level distribution shifts. Our method resorts to a new learning objective derived from causal inference that coordinates an environment estimator and a mixture-of-expert GNN predictor. Our model can effectively enhance generalization with various types of distribution shifts and yield up to 27.4% accuracy improvement over state-of-the-arts on graph OOD generalization benchmarks.
  arXiv  Detail & Related papers  (2024-02-18T07:49:22Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. Due to the selection bias of training and testing data, distribution deviation is widespread. We propose OOD calibration to measure the distribution deviation of virtual samples.
  arXiv  Detail & Related papers  (2023-08-16T13:10:27Z)
• Refined Edge Usage of Graph Neural Networks for Edge Prediction [51.06557652109059]
  We propose a novel edge prediction paradigm named Edge-aware Message PassIng neuRal nEtworks (EMPIRE) We first introduce an edge splitting technique to specify use of each edge where each edge is solely used as either the topology or the supervision. In order to emphasize the differences between pairs connected by supervision edges and pairs unconnected, we further weight the messages to highlight the relative ones that can reflect the differences.
  arXiv  Detail & Related papers  (2022-12-25T23:19:56Z)

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.