Recognizing Predictive Substructures With Subgraph Information Bottleneck.

Area of Science:

• Graph Machine Learning
• Artificial Intelligence

Background:

• Graph Convolutional Networks (GCNs) have advanced graph learning but are hindered by noisy data and lack of interpretability.
• Identifying compressed, predictive subgraphs is crucial for overcoming these limitations.

Purpose of the Study:

• To propose a novel Subgraph Information Bottleneck (SIB) framework, termed IB-subgraph, for recognizing interpretable and compressed subgraphs.
• To address the optimization challenges of mutual information and discrete graph data within the SIB framework.

Main Methods:

• Introduced a bilevel optimization scheme with a mutual information estimator for irregular graphs.
• Developed a continuous relaxation for subgraph selection, incorporating a connectivity loss for stability.
• Provided theoretical guarantees on the error bound of mutual information estimation and noise-invariant properties.

Main Results:

• The proposed IB-subgraph framework effectively identifies predictive and compressed subgraphs.
• Demonstrated superior performance in graph learning tasks.
• Showcased effectiveness on large-scale point cloud datasets.

Conclusions:

• The SIB framework offers a promising approach to enhance GCN interpretability and robustness.
• IB-subgraph successfully mitigates noise and redundancy in graph data.
• The method provides a theoretically sound and empirically validated solution for graph learning challenges.