PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Information Bottleneck for Subgraph Recognition

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

arXiv:2010.05563v1cs.LGstat.ML

TL;DR

Graph learning needs compressed subgraphs that preserve label-relevant information despite redundant and noisy graph structure, a setting where conventional information bottleneck methods are limited for irregular graphs. The paper proposes GIB, combining mutual-information estimation, bi-level optimization, and connectivity regularization to discover IB-subgraphs. Across graph classification, interpretation, and denoising, experiments report superior IB-subgraph properties compared with baselines.

  • Problem

    Graph learning lacks an information-bottleneck approach that recognizes compressed subgraphs while preserving predictive information in irregular graph data.

  • Method

    GIB uses a mutual-information estimator, bi-level optimization, and connectivity loss to discover maximally informative yet compressed IB-subgraphs.

  • Results

    Experiments across graph classification, graph interpretation, and graph denoising demonstrate superior properties of information-theoretic IB-subgraphs.

  • Takeaways & Limitations

    IB-subgraphs provide a unified graph-level structure for improving classification, interpreting molecular properties, and denoising graphs.

  • Takeaways & Limitations

    The GIB objective is notoriously hard to optimize because mutual information is intractable and irregular graph subgraph selection is discrete.

Abstract

from arXiv · show

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.

1 Introduction

Graph learning needs subgraphs that preserve predictive information while removing redundant or noisy structure. GIB adapts the information bottleneck principle to recognize such IB-subgraphs and evaluates them across classification, interpretation, and denoising.

  • Subgraph recognition seeks compressed subgraphs that retain information needed to predict graph labels or properties.
  • The information bottleneck principle motivates extracting compressed data that preserves predictive information, but existing methods remain difficult to apply to irregular graph data.
  • GIB extends information bottleneck to irregular graphs and directly reveals vital substructures at the subgraph level.
  • The framework combines a mutual-information estimator, bi-level optimization, and connectivity loss to discover informative, compact IB-subgraphs without explicit annotations.
  • Experiments evaluate IB-subgraphs for graph classification, graph interpretation, and graph denoising, finding superior graph properties relative to state-of-the-art baselines.

2 Related Work

Related work covers graph classification, information bottleneck methods, and subgraph discovery. It highlights limitations of aggregating redundant or noisy graph information and of applying existing IB methods to irregular graphs.

  • Graph Classification: Graph classification commonly uses mean/sum or pooling aggregation, but redundant and noisy graphs can yield sub-optimal representations.
  • Information Bottleneck: Information bottleneck methods seek compact representations that preserve information, with VIB extending the principle to deep learning across several domains.
  • Subgraph Discovery: Subgraph discovery includes dense subgraph discovery, frequent subgraph mining, and attention-based identification of important nodes.

3 Notations and Preliminaries

The paper defines graph and GNN notation, reviews aggregation and pooling, and introduces the information bottleneck objective. Estimating mutual information remains difficult when distributions are inaccessible, especially for irregular graph data.

  • Graph Notation: Each graph is represented by nodes V, edges E, adjacency matrix A, and node-feature matrix X, with neighborhoods defined by incident edges.
  • Graph Convolutional Network: GCN produces node embeddings from node features and graph connectivity using degree normalization and learnable parameters.
  • Graph Representation: Graph embeddings can be obtained by summing node embeddings or using hierarchical pooling with self-attention-weighted node representations.
  • Information Bottleneck: The information bottleneck objective maximizes I(Z, Y) − βI(X, Z), balancing predictive information against compression.
  • Information Bottleneck: Mutual information is hard to estimate in high-dimensional spaces with inaccessible distribution forms, particularly for irregular graph data.

4 Optimizing the Graph Information Bottleneck Objective for Subgraph Recognition

The paper formulates GIB to identify an informative yet compressed IB-subgraph, then makes its objective tractable through mutual-information estimation and bi-level optimization. A continuous subgraph generator and connectivity loss stabilize node selection while encouraging compact topology.

  • 4.1 graph information bottleneck: GIB generalizes information bottleneck to irregular graphs and directly identifies an informative subgraph-level structure.Unlike prior IB methods that learn hidden representations, GIB reveals vital substructures at the subgraph level.
  • 4.1 graph information bottleneck: The IB-subgraph is the maximally informative yet compressed subgraph, preserving graph-property information with minimum information loss.Its objective balances relevance between the subgraph and graph labels or properties against information shared with the original graph.
  • 4.2 Bi-level optimization for the GIB objective: The GIB objective is optimized with a bi-level scheme because mutual information is intractable and graph subgraph selection is discrete.The inner loop optimizes the estimator, while the outer loop updates the subgraph and predictor parameters.
  • 4.2 Bi-level optimization for the GIB objective: Maximizing label relevance is implemented by minimizing a classification loss, using cross entropy for categorical labels and mean squared loss for continuous properties.This makes the selected subgraph predictive of the graph label.
  • 4.2 Bi-level optimization for the GIB objective: A GNN-based statistics network estimates mutual information between the original graph and subgraph by embedding both, concatenating their embeddings, and applying an MLP.This avoids requiring a tractable prior distribution for graph substructures.
  • 4.3 The Subgraph Generator and connectivity loss: The subgraph generator outputs node-assignment probabilities, and connectivity loss drives distinctive assignments, compact topology, and more stable training.The assignment matrix is produced from GNN node embeddings through an MLP and is intended to saturate toward 0/1.

5 Experiments

The experiments assess GIB across graph classification, interpretation, and denoising, finding that IB-subgraphs improve prediction, preserve molecular properties, and better recover real graph structure.

  • Experimental scenarios: GIB is evaluated for graph classification, graph interpretation, and graph denoising across synthetic and real-world datasets.The classification experiments use MUTAG, PROTEINS, IMDB-BINARY, and DD; interpretation uses molecule properties from ZINC; denoising adds redundant edges to MUTAG graphs.
  • Graph interpretation: Figure 2 shows that subgraphs discovered by different methods exhibit chemical properties similar to their corresponding molecules.The figure provides a qualitative comparison of interpretable molecular subgraphs.
  • Improvement of graph classification: GIB improves graph classification by aggregating representations from subgraphs and reducing redundancies in graph structure.The comparison includes mean/sum aggregation and pooling aggregation across multiple GNN backbones.
  • Graph interpretation: GIB produces precise, compact molecular interpretations whose substructures have properties most similar to the input molecules.Removing either the connectivity loss or mutual-information loss worsens performance, while removing the connectivity loss causes unstable training.
  • Graph denoising: GIB outperforms baselines on noisy graph classification and better reveals real edges in permuted graphs using precision and recall.The denoising evaluation reports classification accuracy, recall of real edges, and precision of selected subgraph edges.

6 Conclusion

The conclusion frames GIB as a framework for discovering maximally informative yet compressed subgraphs and reports superior IB-subgraph properties across three graph-learning applications.

  • 6 Conclusion: GIB defines an IB-subgraph as a maximally informative yet compressed subgraph and discovers it for graph learning tasks.The framework is evaluated for graph classification improvement, graph interpretation, and graph denoising.
  • 6 Conclusion: The framework combines a mutual-information estimator, bi-level optimization, and connectivity loss to discover IB-subgraphs.The connectivity loss stabilizes learning, while the bi-level scheme optimizes the GIB objective.
  • 6 Conclusion: Experiments verify the superior properties of IB-subgraphs across graph classification, interpretation, and denoising.

A.1 More details about Eq. 7 and Eq. 8

This appendix derives the mutual-information terms used in the GIB objective and connects prediction loss on the subgraph to retained label information.

  • A.1 More details about Eq. 7 and Eq. 8: The appendix provides additional derivations for Eq. 7 and Eq. 8 using mutual-information expressions involving p(y, Gsub).

A.2 case study

The case study demonstrates bi-level mutual-information minimization by optimizing a distribution parameter and comparing the learned estimator with a traditional calculation.

  • A.2 case study: The case study models X with a sign-transformed standard normal distribution and Y conditionally as a Gaussian centered on X.The parameter σ^2 is optimized to reduce mutual information between X and Y.
  • A.2 case study: For each epoch, the inner step uses 20,000 samples from each distribution and 150 optimization iterations to fit a mutual-information approximator.The outer optimization then minimizes LMI with respect to σ^2.
  • A.2 case study: Mutual information decreases as LMI descends, while the bi-level objective requires samples rather than distribution forms or a tractable variational prior.The trade-off is additional computation in the inner loop.

A.4 More results on graph interpretation

Additional results examine graph interpretation and related evaluation settings, including property bias distributions and qualitative subgraph examples. The paper also reports denoising results and describes the bi-level optimization procedure.

  • Graph interpretation: GIB generates subgraphs with properties more similar to the original graphs, as shown by the absolute-bias distribution in Fig. 4.The comparison concerns the absolute difference between graph and subgraph properties.
  • Graph interpretation: Fig. 5 presents qualitative interpretation results for four graph properties.These results provide additional examples of the subgraphs identified for interpretation.
  • Noisy graph classification: The study provides qualitative results on noisy graph classification in Fig. 6.This evaluation concerns classification on noisy graphs.
  • Optimization: Figure 3 tracks mutual information and the mutual-information loss during bi-level optimization.The caption states that mutual information decreases consistently with LMI.
  • Optimization: Algorithm 1 optimizes GIB with inner and outer steps before returning the learned subgraph Gsub.The procedure initializes parameters, performs optimization updates, and outputs Gsub.
Loading 2010.05563v1…