Graph Information Bottleneck for Subgraph Recognition

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

In the messy world of real-world data, graphs are often cluttered with redundant or noisy information. Whether it's a social network with "bot" connections or a molecule where only a small functional group determines its toxicity, finding the "core" subgraph is a major challenge. At ICLR 2021, researchers presented a powerful new framework to solve this: the Graph Information Bottleneck (GIB).

The Challenge of Subgraph Recognition

Deep learning on graphs typically involves aggregating information from all nodes and edges using Graph Neural Networks (GNNs). However, real-world graphs are often "noisy"—they contain structures that don't contribute to the task at hand or actively mislead the model.

The goal is subgraph recognition: identifying a subgraph that is as informative as possible for a specific label (like a molecule's property) while being as small and simple as possible. This is a classic Information Bottleneck (IB) problem: "squeezing" the input graph through a bottleneck to extract only the vital bits. The challenge is that graphs are irregular and discrete, making standard IB techniques—which usually rely on smooth, continuous data—notoriously difficult to apply.

The GIB Framework

The authors propose the Graph Information Bottleneck (GIB) framework, which seeks to maximize the mutual information between a subgraph and the target label, while minimizing the mutual information between the original graph and the subgraph.

To make this work, they introduced three key innovations:

  1. MI Estimator for Irregular Data: Since calculating mutual information on graphs is mathematically intractable, they use the Donsker-Varadhan representation to create a tractable estimator. This allows the model to "measure" how much information is being passed through the bottleneck.
  2. Bi-level Optimization: Optimizing the GIB objective is unstable. The authors use a bi-level approach: an inner loop optimizes the statistics network to get a good estimate of the mutual information, while an outer loop optimizes the GNN to select the best subgraph.
  3. Connectivity Loss: To prevent the model from picking a collection of isolated, "important" nodes, they added a connectivity loss. This encourages the model to select nodes that are actually connected in the original topology, leading to more physically meaningful and compact subgraphs.
The Graph Information Bottleneck (GIB) framework featuring bi-level optimization and connectivity constraints.

Key Insights and Performance

Treating subgraph selection as an information-theoretic compression problem provides a formal way to define what an "interpretable" subgraph actually is. Furthermore, GIB is model-agnostic; it can be plugged into existing backbones like GCN, GAT, or GIN, acting as a sophisticated feature selector.

The researchers evaluated GIB across graph classification, interpretation, and denoising scenarios, yielding impressive results:

  • Superior Accuracy: GIB-enhanced models consistently outperformed standard GNNs and popular pooling methods on classification tasks. For example, on the DD dataset, GraphSAGE+GIB achieved 78.1% accuracy compared to 72.9% for standard GraphSAGE.
  • Precise Interpretation: In molecule tasks, GIB found subgraphs that were much closer to the "ground truth" functional groups identified by chemists, achieving a significantly lower "property bias" compared to standard attention mechanisms.
  • Robust Denoising: In denoising experiments, GIB achieved a 0.692 precision in identifying real edges versus noisy ones, outperforming attention-based baselines and leading to better classification on corrupted data.
Performance table on graph denoising and visualizations of interpreted subgraphs on molecular datasets.

Limitations and Future Work

While GIB is powerful, it comes with a computational trade-off. The bi-level optimization requires an inner loop of steps for every outer training step, which increases training time.

Additionally, the current approach uses a continuous relaxation to handle the discrete nature of selecting nodes and edges. Exploring more direct discrete optimization methods (like reinforcement learning or Gumbel-Softmax variations) could be a promising future direction. Finally, for some properties, the "informative subgraph" is almost the entire molecule, suggesting that the bottleneck size needs to be highly adaptive to the specific task.

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