# Improving Subgraph Recognition with Variational Graph Information Bottleneck

arXiv: https://arxiv.org/abs/2112.09899 · HTML: https://mlsanity.com/paper/2112.09899/

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 60 references that are in the map.
- First posted on arXiv 18 Dec 2021.

## Builds on (most cited first, 30 of 39)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Deep Variational Information Bottleneck](https://mlsanity.com/paper/1612.00410/) (2016)
- [What Makes for Good Views for Contrastive Learning?](https://mlsanity.com/paper/2005.10243/) (2020)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [MINE: Mutual Information Neural Estimation](https://mlsanity.com/paper/1801.04062/) (2018)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization](https://mlsanity.com/paper/1908.01000/) (2019)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Concrete Dropout](https://mlsanity.com/paper/1705.07832/) (2017)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [Information Dropout: Learning Optimal Representations Through Noisy Computation](https://mlsanity.com/paper/1611.01353/) (2016)
- [Graph Information Bottleneck for Subgraph Recognition](https://mlsanity.com/paper/2010.05563/) (2020)
- [Restricting the Flow: Information Bottlenecks for Attribution](https://mlsanity.com/paper/2001.00396/) (2020)
- [Variational Discriminator Bottleneck: Improving Imitation Learning, Inverse RL, and GANs by Constraining Information Flow](https://mlsanity.com/paper/1810.00821/) (2018)
- [Generalization in Reinforcement Learning with Selective Noise Injection and Information Bottleneck](https://mlsanity.com/paper/1910.12911/) (2019)
- [Unsupervised Speech Decomposition via Triple Information Bottleneck](https://mlsanity.com/paper/2004.11284/) (2020)

## Built on by (most cited first, 30 of 45)

- [Towards Self-Interpretable Graph-Level Anomaly Detection](https://mlsanity.com/paper/2310.16520/) (2023)
- [Mind the Label Shift of Augmentation-based Graph OOD Generalization](https://mlsanity.com/paper/2303.14859/) (2023)
- [A Survey on Explainability of Graph Neural Networks](https://mlsanity.com/paper/2306.01958/) (2023)
- [Conditional Graph Information Bottleneck for Molecular Relational Learning](https://mlsanity.com/paper/2305.01520/) (2023)
- [Interpretable Prototype-based Graph Information Bottleneck](https://mlsanity.com/paper/2310.19906/) (2023)
- [FlowX: Towards Explainable Graph Neural Networks via Message Flows](https://mlsanity.com/paper/2206.12987/) (2022)
- [Contrastive Graph Representation Learning with Adversarial Cross-view Reconstruction and Information Bottleneck](https://mlsanity.com/paper/2408.00295/) (2024)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [Drug Discovery with Dynamic Goal-aware Fragments](https://mlsanity.com/paper/2310.00841/) (2023)
- [A Comprehensive Survey on Self-Interpretable Neural Networks](https://mlsanity.com/paper/2501.15638/) (2025)
- [BrainIB: Interpretable Brain Network-based Psychiatric Diagnosis with Graph Information Bottleneck](https://mlsanity.com/paper/2205.03612/) (2022)
- [CI-GNN: A Granger Causality-Inspired Graph Neural Network for Interpretable Brain Network-Based Psychiatric Diagnosis](https://mlsanity.com/paper/2301.01642/) (2023)
- [Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs](https://mlsanity.com/paper/2406.15156/) (2024)
- [Individual and Structural Graph Information Bottlenecks for Out-of-Distribution Generalization](https://mlsanity.com/paper/2306.15902/) (2023)
- [How Interpretable Are Interpretable Graph Neural Networks?](https://mlsanity.com/paper/2406.07955/) (2024)
- [Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective](https://mlsanity.com/paper/2502.02719/) (2025)
- [Identifying Semantic Component for Robust Molecular Property Prediction](https://mlsanity.com/paper/2311.04837/) (2023)
- [Learning High-Order Relationships of Brain Regions](https://mlsanity.com/paper/2312.02203/) (2023)
- [Finding Diverse and Predictable Subgraphs for Graph Domain Generalization](https://mlsanity.com/paper/2206.09345/) (2022)
- [Self-Explainable Temporal Graph Networks based on Graph Information Bottleneck](https://mlsanity.com/paper/2406.13214/) (2024)
- [Can Knowledge-Graph-based Retrieval Augmented Generation Really Retrieve What You Need?](https://mlsanity.com/paper/2510.16582/) (2025)
- [Deep Hypergraph Structure Learning](https://mlsanity.com/paper/2208.12547/) (2022)
- [Adversarially Robust Neural Architecture Search for Graph Neural Networks](https://mlsanity.com/paper/2304.04168/) (2023)
- [Recent Advances in Malware Detection: Graph Learning and Explainability](https://mlsanity.com/paper/2502.10556/) (2025)
- [How Faithful are Self-Explainable GNNs?](https://mlsanity.com/paper/2308.15096/) (2023)
- [GNN Explanations that do not Explain and How to find Them](https://mlsanity.com/paper/2601.20815/) (2026)
- [Label Information Bottleneck for Label Enhancement](https://mlsanity.com/paper/2303.06836/) (2023)
- [Rumor Detection with Diverse Counterfactual Evidence](https://mlsanity.com/paper/2307.09296/) (2023)
- [Graph Augmentation for Recommendation](https://mlsanity.com/paper/2403.16656/) (2024)
- [B-XAIC Dataset: Benchmarking Explainable AI for Graph Neural Networks Using Chemical Data](https://mlsanity.com/paper/2505.22252/) (2025)

## Abstract (arXiv)

Subgraph recognition aims at discovering a compressed substructure of a graph that is most informative to the graph property. It can be formulated by optimizing Graph Information Bottleneck (GIB) with a mutual information estimator. However, GIB suffers from training instability and degenerated results due to its intrinsic optimization process. To tackle these issues, we reformulate the subgraph recognition problem into two steps: graph perturbation and subgraph selection, leading to a novel Variational Graph Information Bottleneck (VGIB) framework. VGIB first employs the noise injection to modulate the information flow from the input graph to the perturbed graph. Then, the perturbed graph is encouraged to be informative to the graph property. VGIB further obtains the desired subgraph by filtering out the noise in the perturbed graph. With the customized noise prior for each input, the VGIB objective is endowed with a tractable variational upper bound, leading to a superior empirical performance as well as theoretical properties. Extensive experiments on graph interpretation, explainability of Graph Neural Networks, and graph classification show that VGIB finds better subgraphs than existing methods. Code is avaliable at https://github.com/Samyu0304/VGIB