Source-linked AI summary
SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information Mechanism
Qingyun Sun, Jianxin Li, Hao Peng, Jia Wu, Yuanxing Ning, Phillip S. Yu, Lifang He
TL;DR
Existing graph representation methods often miss semantically important local substructures and face interpretability challenges. SUGAR addresses this with hierarchical subgraph selection and embedding, adaptive reinforcement pooling, and mutual-information-based alignment, achieving consistent gains across graph-classification datasets while providing interpretable subgraph selections.
Problem
Existing methods often emphasize node-level or global graph representations, leaving important motif and subgraph semantics insufficiently captured for graph-level analysis.
Method
SUGAR reconstructs a hierarchical sketched graph, adaptively selects striking subgraphs through reinforcement pooling, and maximizes mutual information between local subgraph and global graph representations.
Results
SUGAR consistently outperforms all baselines across the evaluated datasets, including 96.74% average accuracy on MUTAG and improvements over competing methods on PTC.
Takeaways & Limitations
Selected subgraphs and learned weights provide interpretability and insight into structural bioinformatics analysis, while the model captures both local and global graph properties.
Abstract
from arXiv · showhide
Graph representation learning has attracted increasing research attention. However, most existing studies fuse all structural features and node attributes to provide an overarching view of graphs, neglecting finer substructures' semantics, and suffering from interpretation enigmas. This paper presents a novel hierarchical subgraph-level selection and embedding based graph neural network for graph classification, namely SUGAR, to learn more discriminative subgraph representations and respond in an explanatory way. SUGAR reconstructs a sketched graph by extracting striking subgraphs as the representative part of the original graph to reveal subgraph-level patterns. To adaptively select striking subgraphs without prior knowledge, we develop a reinforcement pooling mechanism, which improves the generalization ability of the model. To differentiate subgraph representations among graphs, we present a self-supervised mutual information mechanism to encourage subgraph embedding to be mindful of the global graph structural properties by maximizing their mutual information. Extensive experiments on six typical bioinformatics datasets demonstrate a significant and consistent improvement in model quality with competitive performance and interpretability.
1 INTRODUCTION
Graph representation learning must capture meaningful substructures rather than relying only on node-level embeddings or global summaries. SUGAR addresses this by adaptively selecting discriminative subgraphs while preserving interpretability and local–global structural information.
- Graph-level embedding supports applications such as molecule-property prediction, but node-level embedding is insufficient for subgraph analysis.
- Global node summarization in flat GNNs can overlook vital motifs and subgraph patterns that characterize graph structure.
- Existing subgraph methods often require manually designed motif rules or other domain-specific procedures to preserve higher-order structure.
- SUGAR reconstructs a sketched graph to preserve node, intra-subgraph, and inter-subgraph information hierarchically.
- Reinforcement pooling adaptively selects striking subgraphs without prior knowledge, while mutual-information learning makes their embeddings aware of global graph properties.
- SUGAR explicitly identifies subgraphs dominating the learned result, providing interpretive insight for downstream applications.
2 RELATED WORK
Related graph-learning methods operate at multiple granularities, but existing approaches face limitations in adaptivity, interpretability, computational cost, or reliance on handcrafted structural rules. SUGAR combines subgraph-level processing with reinforcement pooling and self-supervised mutual information to address these issues.
- Graph Representation Learning: Graph neural networks commonly use recursive message passing to embed graphs at node, motif, or subgraph granularities.
- Graph Representation Learning: Global node-feature fusion methods can produce representations that are implicit and unaware of exact graph structures.
- Subgraph and Motif Methods: Motif-based methods capture local structure explicitly but depend on manually designed extraction rules and exact small-structure enumeration.
- Subgraph and Motif Methods: Prior approaches are limited in discrimination, prior-knowledge requirements, and interpretability; SUGAR represents graphs using adaptively selected striking subgraphs.
- Graph Pooling: Cluster pooling groups nodes through assignment matrices, but can lack interpretability, require heuristic or tuned cluster counts, and incur high computational cost.
- SUGAR Architecture: SUGAR’s architecture samples and encodes subgraphs, selects striking ones into a sketched graph, applies inter-subgraph attention, and classifies subgraphs by voting.
- Graph Pooling: SUGAR uses reinforcement learning to optimize the pooling ratio end-to-end instead of tuning it as a hyper-parameter.
- Self-Supervised Learning: Unlike approaches that maximize information in overarching graph embeddings, SUGAR maximizes mutual information between local subgraph and global graph representations.
3 OUR APPROACH
SUGAR builds graph representations hierarchically by sampling, selecting, and relating subgraphs, then uses reinforcement learning and mutual information to make selection adaptive and embeddings globally informed.
- Subgraph Neural Network: SUGAR samples and encodes subgraphs, selects striking ones with reinforcement pooling, then builds a sketched graph for attention-based subgraph embedding.The pipeline preserves node, intra-subgraph, and inter-subgraph structure.
- Subgraph Neural Network: Subgraphs are sampled around high-degree central nodes with BFS, while a GNN encoder produces node representations within each sampled subgraph.The number of sampled subgraphs and the subgraph size limit coverage under a fixed budget.
- Subgraph Neural Network: An intra-subgraph attention mechanism weights nodes to produce unified subgraph embeddings, and inter-subgraph attention learns mutual influence among selected subgraphs.The intra-subgraph attention parameters are shared across nodes of all subgraphs.
- Subgraph Neural Network: Subgraph-level class probabilities are interpreted as subgraph impacts, and their summed predictions determine the final graph classification distribution.This voting procedure provides an explanatory view of how selected subgraphs contribute to graph-level predictions.
- Reinforcement Pooling Module: The reinforcement pooling module updates k adaptively through a finite-horizon Markov decision process instead of tuning it as a hyper-parameter.Actions add or subtract a fixed Δk, rewards compare classification accuracy across epochs, and training stops when k stabilizes over ten consecutive epochs.
- Self-Supervised Mutual Information Module: The self-supervised mutual information mechanism aligns local subgraph representations with the global graph representation while retaining local and global structural properties.The loss combines classification, mutual-information enhancement weighted by β, and L2 regularization weighted by λ.
4 EXPERIMENTS
Experiments on six bioinformatics datasets evaluate SUGAR’s classification accuracy, architectural robustness, adaptive pooling, mutual-information mechanism, and interpretability. SUGAR consistently outperforms baselines, while larger subgraphs, adaptive pooling, and mutual-information supervision support its performance and selected-subgraph explanations.
- Overall Evaluation (Q1): SUGAR consistently outperforms all baselines across the six bioinformatics datasets.Evaluation uses 10-fold cross-validation, with average accuracy, standard deviation, and rank reported.
- Overall Evaluation (Q1): 96.74% average accuracy on MUTAG improves 3.04% over the second-best MA-GCNN, while PTC gains 14.99% over NEST and 8.04% over MA-GCNN.The authors attribute the PTC gains to SUGAR capturing more complex structural information through random sampling rather than predefined motif rules.
- Subgraph Encoder and Size Analysis (Q2): Performance differences among GCN, GAT, GraphSAGE, and GIN encoders are marginal, indicating robustness to the exact subgraph encoder architecture.The authors suggest these GNNs are all expressive enough to capture subgraph properties.
- Subgraph Encoder and Size Analysis (Q2): Subgraphs larger than three or four nodes improve performance, while increasing size beyond five does not significantly improve SUGAR.The study examines subgraph sizes from 3 to 7 on MUTAG and PTC; competitive performance occurs when sampled subgraphs cover most basic functional building blocks.
- RL Process Analysis (Q3): The adaptive-pooling SUGAR improves mean accuracy by 5.79% over fixed-ratio SUGAR-FixedK, and reinforcement learning converges to mean reward 0.545 with a stable learning curve.SUGAR-FixedK uses a fixed pooling ratio k=1 without subgraph selection.
- Self-Supervised MI Analysis (Q4): Self-supervised mutual information improves performance over SUGAR-NoMI, while sampling from another graph instance outperforms corruption-based negative sampling.The authors suggest corrupted graphs lose important structural information and therefore provide weaker supervision.
- Visualization (Q5): Visualizations identify class-associated molecular subgraphs, including nitro groups for MUTAG mutagenic compounds and nitrogen-linked aromatic bonds for PTC active compounds.Chlorine connected to carbons is selected for MUTAG non-mutagenic molecules; the findings support discriminative subgraph patterns and interpretability.
5 CONCLUSION AND FUTURE WORKS
SUGAR is an end-to-end graph classification framework that selects and represents subgraphs to address discrimination, prior-knowledge, and interpretability challenges. It hierarchically preserves local and global properties, adaptively selects striking subgraphs, and uses mutual-information maximization to discriminate their representations.
- SUGAR reconstructs a sketched graph to preserve local and global properties hierarchically.
- Its reinforcement pooling mechanism adaptively selects striking subgraphs without requiring prior knowledge.
- A self-supervised mutual information maximization mechanism discriminates subgraph representations across graphs.
- Experiments on graph classification show the effectiveness of SUGAR.
- Selected subgraphs and learned weights provide interpretability and insight into structural bioinformatics analysis.
- Future work includes improved reinforcement learning, multi-label subgraphs, and applications to other complex datasets and subgraph classification.