# Recognizing Predictive Substructures with Subgraph Information Bottleneck

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 68 references that are in the map.
- First posted on arXiv 20 Mar 2021.

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

- [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)
- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [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)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Deep Variational Information Bottleneck](https://mlsanity.com/paper/1612.00410/) (2016)
- [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)
- [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)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization](https://mlsanity.com/paper/1908.01000/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloud](https://mlsanity.com/paper/2003.01251/) (2020)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Emergence of Invariance and Disentanglement in Deep Representations](https://mlsanity.com/paper/1706.01350/) (2017)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [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)
- [Graph Information Bottleneck for Subgraph Recognition](https://mlsanity.com/paper/2010.05563/) (2020)
- [Variational Discriminator Bottleneck: Improving Imitation Learning, Inverse RL, and GANs by Constraining Information Flow](https://mlsanity.com/paper/1810.00821/) (2018)
- [Grid-GCN for Fast and Scalable Point Cloud Learning](https://mlsanity.com/paper/1912.02984/) (2019)

## Built on by (most cited first, 28 of 28)

- [Graph Structure Learning with Variational Information Bottleneck](https://mlsanity.com/paper/2112.08903/) (2021)
- [Improving Subgraph Recognition with Variational Graph Information Bottleneck](https://mlsanity.com/paper/2112.09899/) (2021)
- [Does Invariant Graph Learning via Environment Augmentation Learn Invariance?](https://mlsanity.com/paper/2310.19035/) (2023)
- [Few-shot Backdoor Defense Using Shapley Estimation](https://mlsanity.com/paper/2112.14889/) (2021)
- [Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models](https://mlsanity.com/paper/2310.03965/) (2023)
- [Mind the Label Shift of Augmentation-based Graph OOD Generalization](https://mlsanity.com/paper/2303.14859/) (2023)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [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)
- [Finding Diverse and Predictable Subgraphs for Graph Domain Generalization](https://mlsanity.com/paper/2206.09345/) (2022)
- [Adaptive Hierarchical Graph Cut for Multi-granularity Out-of-distribution Detection](https://mlsanity.com/paper/2412.15668/) (2024)
- [MvHo-IB: Multi-View Higher-Order Information Bottleneck for Brain Disorder Diagnosis](https://mlsanity.com/paper/2507.02847/) (2025)
- [BatchSampler: Sampling Mini-Batches for Contrastive Learning in Vision, Language, and Graphs](https://mlsanity.com/paper/2306.03355/) (2023)
- [A Graph is Worth 1-bit Spikes: When Graph Contrastive Learning Meets Spiking Neural Networks](https://mlsanity.com/paper/2305.19306/) (2023)
- [Dynamic Graph Information Bottleneck](https://mlsanity.com/paper/2402.06716/) (2024)
- [Towards the Explanation of Graph Neural Networks in Digital Pathology with Information Flows](https://mlsanity.com/paper/2112.09895/) (2021)
- [Rumor Detection with Diverse Counterfactual Evidence](https://mlsanity.com/paper/2307.09296/) (2023)
- [IBCircuit: Towards Holistic Circuit Discovery with Information Bottleneck](https://mlsanity.com/paper/2602.22581/) (2026)
- [Modeling Higher-Order Brain Interactions via a Multi-View Information Bottleneck Framework for fMRI-based Psychiatric Diagnosis](https://mlsanity.com/paper/2604.17713/) (2026)
- [Information Bottleneck-Guided Heterogeneous Graph Learning for Interpretable Neurodevelopmental Disorder Diagnosis](https://mlsanity.com/paper/2502.20769/) (2025)
- [BrainIB++: Leveraging Graph Neural Networks and Information Bottleneck for Functional Brain Biomarkers in Schizophrenia](https://mlsanity.com/paper/2510.03004/) (2025)
- [PIME: Prototype-based Interpretable MCTS-Enhanced Brain Network Analysis for Disorder Diagnosis](https://mlsanity.com/paper/2602.21046/) (2026)
- [Towards Explanation for Unsupervised Graph-Level Representation Learning](https://mlsanity.com/paper/2205.09934/) (2022)
- [Discovering robust biomarkers of psychiatric disorders from resting-state functional MRI via graph neural networks: A systematic review](https://mlsanity.com/paper/2405.00577/) (2024)
- [BlindU: Blind Machine Unlearning without Revealing Erasing Data](https://mlsanity.com/paper/2601.07214/) (2026)
- [Structure Matters: Brain Graph Augmentation via Learnable Edge Masking for Data-efficient Psychiatric Diagnosis](https://mlsanity.com/paper/2509.09744/) (2025)
- [Subgraph Concept Networks: Concept Levels in Graph Classification](https://mlsanity.com/paper/2604.18868/) (2026)

## Abstract (arXiv)

The emergence of Graph Convolutional Network (GCN) has greatly boosted the progress of graph learning. However, two disturbing factors, noise and redundancy in graph data, and lack of interpretation for prediction results, impede further development of GCN. One solution is to recognize a predictive yet compressed subgraph to get rid of the noise and redundancy and obtain the interpretable part of the graph. This setting of subgraph is similar to the information bottleneck (IB) principle, which is less studied on graph-structured data and GCN. Inspired by the IB principle, we propose a novel subgraph information bottleneck (SIB) framework to recognize such subgraphs, named IB-subgraph. However, the intractability of mutual information and the discrete nature of graph data makes the objective of SIB notoriously hard to optimize. To this end, we introduce a bilevel optimization scheme coupled with a mutual information estimator for irregular graphs. Moreover, we propose a continuous relaxation for subgraph selection with a connectivity loss for stabilization. We further theoretically prove the error bound of our estimation scheme for mutual information and the noise-invariant nature of IB-subgraph. Extensive experiments on graph learning and large-scale point cloud tasks demonstrate the superior property of IB-subgraph.