Graph Information Bottleneck for Subgraph Recognition

Junchi Yu, Tingyang Xu, Yu Rong, Yatao Bian, Junzhou Huang, Ran He

Abstract

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.

Introduction

Graph Neural Networks (GNNs) are powerful tools for molecular property prediction and social network analysis. However, real-world graphs are often noisy and contain redundant structural information—such as irrelevant edges or nodes—that can degrade model performance.

Ideally, we want to extract a compressed "IB-subgraph" that retains all predictive power for a target label while discarding noise. This is the core of the Information Bottleneck (IB) principle. While IB has been successful in computer vision and NLP, applying it to irregular graph data is difficult because calculating mutual information (MI) between irregular graphs is mathematically intractable, and subgraph selection is a discrete, non-differentiable operation.

The GIB Framework

To bring the IB principle to graphs, the authors propose the GIB framework, which introduces three technical innovations:

  1. Graph Mutual Information Estimator: Traditional Variational IB requires a known prior distribution, which is impossible to define for arbitrary graph substructures. GIB uses a statistics network based on the DONSKER-VARADHAN representation to estimate MI without a predefined prior.
  2. Bi-level Optimization: The GIB objective is optimized in two phases. An inner loop trains the statistics network to accurately estimate MI, while an outer loop updates the subgraph generator to maximize predictive power and minimize structural redundancy.
  3. Connectivity Loss: To bypass the non-differentiable nature of discrete selection, the model outputs node assignment probabilities. A novel connectivity loss encourages the model to select compact, contiguous subgraphs rather than scattered nodes, stabilizing the training process.
The GIB framework architecture featuring bi-level optimization and MI estimation.

Experimental Results

The authors evaluated GIB across three distinct scenarios: graph classification, interpretation, and denoising.

Graph Classification

GIB is model-agnostic and can be attached to standard GNN backbones (GCN, GAT, GIN, GraphSAGE). As shown in the performance table below, plugging GIB into standard GNNs yielded consistent performance boosts across benchmarks like MUTAG, PROTEINS, and DD.

Graph classification performance of various GNN backbones with and without the GIB framework.

Graph Interpretation and Denoising

On the DRD2 molecular property task, GIB achieved an absolute property bias of just 0.06, vastly outperforming attention-based methods (0.16). It also produced highly contiguous subgraphs, averaging only 1.08 disconnected components per graph vs. 1.76 for attention methods. In denoising tasks on the MUTAG dataset, GIB recovered true edges with significantly higher precision and recall than baselines, proving its ability to filter structural noise.

Conclusion

The GIB framework successfully adapts the Information Bottleneck principle for irregular graph data. By leveraging a novel MI estimator and bi-level optimization, it enables the recognition of maximally informative yet compressed subgraphs. While the optimization scheme adds computational overhead, the resulting IB-subgraphs offer improved robustness, superior interpretability, and effective denoising across diverse graph learning tasks.

Summary updated

Abstract

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.
BibTeX
@inproceedings{yu2021graph,
  author = {Junchi Yu and Tingyang Xu and Yu Rong and Yatao Bian and Junzhou Huang and Ran He},
  title = {{Graph Information Bottleneck for Subgraph Recognition}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=hP90uw1jh2Q},
}
Figure