# Graph Information Bottleneck for Subgraph Recognition

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

## Key facts

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

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

- [Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism](https://mlsanity.com/paper/2201.12987/) (2022)
- [Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs](https://mlsanity.com/paper/2202.05441/) (2022)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [InfoGCL: Information-Aware Graph Contrastive Learning](https://mlsanity.com/paper/2110.15438/) (2021)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Graph Structure Learning with Variational Information Bottleneck](https://mlsanity.com/paper/2112.08903/) (2021)
- [Graph Data Augmentation for Graph Machine Learning: A Survey](https://mlsanity.com/paper/2202.08871/) (2022)
- [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)
- [Towards Self-Interpretable Graph-Level Anomaly Detection](https://mlsanity.com/paper/2310.16520/) (2023)
- [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)
- [OrphicX: A Causality-Inspired Latent Variable Model for Interpreting Graph Neural Networks](https://mlsanity.com/paper/2203.15209/) (2022)
- [A Survey on Explainability of Graph Neural Networks](https://mlsanity.com/paper/2306.01958/) (2023)
- [Recognizing Predictive Substructures with Subgraph Information Bottleneck](https://mlsanity.com/paper/2103.11155/) (2021)
- [Bringing Your Own View: Graph Contrastive Learning without Prefabricated Data Augmentations](https://mlsanity.com/paper/2201.01702/) (2022)
- [Interpretable Geometric Deep Learning via Learnable Randomness Injection](https://mlsanity.com/paper/2210.16966/) (2022)
- [Pairwise Alignment Improves Graph Domain Adaptation](https://mlsanity.com/paper/2403.01092/) (2024)
- [Equivariant Graph Hierarchy-Based Neural Networks](https://mlsanity.com/paper/2202.10643/) (2022)
- [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)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [Are You Stealing My Model? Sample Correlation for Fingerprinting Deep Neural Networks](https://mlsanity.com/paper/2210.15427/) (2022)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [EXGC: Bridging Efficiency and Explainability in Graph Condensation](https://mlsanity.com/paper/2402.05962/) (2024)
- [The Interpretable and Effective Graph Neural Additive Networks](https://mlsanity.com/paper/2406.01317/) (2024)
- [MixupExplainer: Generalizing Explanations for Graph Neural Networks with Data Augmentation](https://mlsanity.com/paper/2307.07832/) (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)

## 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.