mlsanityData to 7 Oct 2026

Graph Information Bottleneck for Subgraph Recognition

arXiv 2010.05563 ↗First posted 12 Oct 2020cs.LG stat.MLcited by 119

Not on the map. Why?

Abstract (arXiv)

Given the input graph and its label/property, several key problems of graph learning, such as finding interpretable subgraphs, graph denoising and graph compression, can be attributed to the fundamental problem of recognizing a subgraph of the original one. This subgraph shall be as informative as possible, yet contains less redundant and noisy structure. This problem setting is closely related to the well-known information bottleneck (IB) principle, which, however, has less been studied for the irregular graph data and graph neural networks (GNNs). In this paper, we propose a framework of Graph Information Bottleneck (GIB) for the subgraph recognition problem in deep graph learning. Under this framework, one can recognize the maximally informative yet compressive subgraph, named IB-subgraph. However, the GIB objective is notoriously hard to optimize, mostly due to the intractability of the mutual information of irregular graph data and the unstable optimization process. In order to tackle these challenges, we propose: i) a GIB objective based-on a mutual information estimator for the irregular graph data; ii) a bi-level optimization scheme to maximize the GIB objective; iii) a connectivity loss to stabilize the optimization process. We evaluate the properties of the IB-subgraph in three application scenarios: improvement of graph classification, graph interpretation and graph denoising. Extensive experiments demonstrate that the information-theoretic IB-subgraph enjoys superior graph properties.

Key facts. Cited by 119 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 26; 2023: 30; 2024: 30; 2025: 16; 2026: 9.

119 papers.

Sort:

By area:

  1. 2022Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanismcited by 171
  2. 2022Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphscited by 144
  3. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 132
  4. 2021InfoGCL: Information-Aware Graph Contrastive Learningcited by 105
  5. 2022Trustworthy Graph Neural Networks: Aspects, Methods and Trendscited by 88
  6. 2021Graph Structure Learning with Variational Information Bottleneckcited by 81
  7. 2022Graph Data Augmentation for Graph Machine Learning: A Surveycited by 61
  8. 2021Improving Subgraph Recognition with Variational Graph Information Bottleneckcited by 45
  9. 2023Does Invariant Graph Learning via Environment Augmentation Learn Invariance?cited by 42
  10. 2023Towards Self-Interpretable Graph-Level Anomaly Detectioncited by 41
  11. 2021Few-shot Backdoor Defense Using Shapley Estimationcited by 40
  12. 2023Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Modelscited by 37
38 more
  1. 2023Mind the Label Shift of Augmentation-based Graph OOD Generalizationcited by 34
  2. 2022OrphicX: A Causality-Inspired Latent Variable Model for Interpreting Graph Neural Networkscited by 33
  3. 2021Recognizing Predictive Substructures with Subgraph Information Bottleneckcited by 28
  4. 2022Bringing Your Own View: Graph Contrastive Learning without Prefabricated Data Augmentationscited by 28
  5. 2023A Survey on Explainability of Graph Neural Networkscited by 28
  6. 2022Interpretable Geometric Deep Learning via Learnable Randomness Injectioncited by 27
  7. 2024Pairwise Alignment Improves Graph Domain Adaptationcited by 25
  8. 2022Equivariant Graph Hierarchy-Based Neural Networkscited by 24
  9. 2023Conditional Graph Information Bottleneck for Molecular Relational Learningcited by 24
  10. 2023Interpretable Prototype-based Graph Information Bottleneckcited by 23
  11. 2023Data-centric Graph Learning: A Surveycited by 22
  12. 2022Are You Stealing My Model? Sample Correlation for Fingerprinting Deep Neural Networkscited by 21
  13. 2022A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protectioncited by 20
  14. 2024EXGC: Bridging Efficiency and Explainability in Graph Condensationcited by 20
  15. 2024The Interpretable and Effective Graph Neural Additive Networkscited by 19
  16. 2023MixupExplainer: Generalizing Explanations for Graph Neural Networks with Data Augmentationcited by 18
  17. 2025A Comprehensive Survey on Self-Interpretable Neural Networkscited by 18
  18. 2022BrainIB: Interpretable Brain Network-based Psychiatric Diagnosis with Graph Information Bottleneckcited by 17
  19. 2024GOODAT: Towards Test-time Graph Out-of-Distribution Detectioncited by 17
  20. 2024HIGHT: Hierarchical Graph Tokenization for Molecule-Language Alignmentcited by 17
  21. 2021Quantitative Evaluation of Explainable Graph Neural Networks for Molecular Property Predictioncited by 15
  22. 2022Self-Supervised Information Bottleneck for Deep Multi-View Subspace Clusteringcited by 15
  23. 2022Semi-Supervised Hierarchical Graph Classificationcited by 15
  24. 2022Exploring Faithful Rationale for Multi-hop Fact Verification via Salience-Aware Graph Learningcited by 15
  25. 2023Individual and Structural Graph Information Bottlenecks for Out-of-Distribution Generalizationcited by 15
  26. 2023A Unified Framework of Graph Information Bottleneck for Robustness and Membership Privacycited by 14
  27. 2024Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNscited by 14
  28. 2024Empowering Graph Invariance Learning with Deep Spurious Infomaxcited by 14
  29. 2023Explainable Spatio-Temporal Graph Neural Networkscited by 13
  30. 2024How Interpretable Are Interpretable Graph Neural Networks?cited by 13
  31. 2024Pre-training Graph Neural Networks on Molecules by Using Subgraph-Conditioned Graph Information Bottleneckcited by 11
  32. 2023Identifying Semantic Component for Robust Molecular Property Predictioncited by 10
  33. 2023Learning High-Order Relationships of Brain Regionscited by 10
  34. 2025Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspectivecited by 10
  35. 2022Principle of Relevant Information for Graph Sparsificationcited by 9
  36. 2022Finding Diverse and Predictable Subgraphs for Graph Domain Generalizationcited by 9
  37. 2023RegExplainer: Generating Explanations for Graph Neural Networks in Regression Taskscited by 9
  38. 2023Combating Bilateral Edge Noise for Robust Link Predictioncited by 9

50 most cited of 119 All 119 (JSON)