Source-linked AI summary
Hierarchical Graph Pooling with Structure Learning
Zhen Zhang, Jiajun Bu, Martin Ester, Jianfeng Zhang, Chengwei Yao, Zhi Yu, Can Wang
TL;DR
Graph pooling is underdeveloped in GNNs despite its importance for hierarchical graph representations. HGP-SL combines adaptive node selection with structure learning, and experiments on six benchmarks report superiority over state-of-the-art methods, while the full operator includes an attention parameter.
Problem
Graph pooling operations are usually overlooked in GNNs even though they are important for learning hierarchical graph representations.
Method
HGP-SL adaptively selects informative nodes and learns a refined structure for the pooled graph within a GNN-compatible, end-to-end module.
Results
Experiments on six widely used benchmarks demonstrate HGP-SL’s superiority to a range of state-of-the-art methods.
Takeaways & Limitations
HGP-SL provides a graph pooling operator that can be integrated into various GNN architectures for hierarchical graph representation learning.
Takeaways & Limitations
The full HGP-SL operator is not non-parametric because its structure learning mechanism contains an attention parameter.
Abstract
from arXiv · showhide
Graph Neural Networks (GNNs), which generalize deep neural networks to graph-structured data, have drawn considerable attention and achieved state-of-the-art performance in numerous graph related tasks. However, existing GNN models mainly focus on designing graph convolution operations. The graph pooling (or downsampling) operations, that play an important role in learning hierarchical representations, are usually overlooked. In this paper, we propose a novel graph pooling operator, called Hierarchical Graph Pooling with Structure Learning (HGP-SL), which can be integrated into various graph neural network architectures. HGP-SL incorporates graph pooling and structure learning into a unified module to generate hierarchical representations of graphs. More specifically, the graph pooling operation adaptively selects a subset of nodes to form an induced subgraph for the subsequent layers. To preserve the integrity of graph's topological information, we further introduce a structure learning mechanism to learn a refined graph structure for the pooled graph at each layer. By combining HGP-SL operator with graph neural networks, we perform graph level representation learning with focus on graph classification task. Experimental results on six widely used benchmarks demonstrate the effectiveness of our proposed model.
Introduction
The paper addresses the limited study of graph pooling for hierarchical graph representations by proposing HGP-SL, which combines adaptive node pooling with structure learning. The operator preserves informative nodes and refines pooled graph structures, and experiments on six public datasets evaluate its effectiveness.
- Motivation: Graph pooling is underexplored despite its pivotal role in learning hierarchical representations for graph classification.Global aggregation can miss meaningful local substructures, motivating hierarchical pooling to capture both local and global structure.
- Proposed approach: HGP-SL adaptively selects informative nodes using node features and graph topology, then learns a refined structure for the pooled graph.The pooling step is non-parametric, while structure learning uses sparse attention to preserve key substructures.
- Proposed approach: HGP-SL can be integrated into various GNN architectures and supports end-to-end graph classification.The proposed operator is described as easy to implement and non-parametric for its pooling component.
- Contribution: The method introduces structure learning for pooled graphs to preserve essential graph structure information after node selection.This mechanism addresses distortions that can hinder subsequent message passing.
- Evaluation: Experiments on six public datasets report HGP-SL’s effectiveness and superiority over a range of state-of-the-art methods.The paper presents this evaluation as evidence for the proposed model’s effectiveness.
- Caveat: The overall HGP-SL operator is not non-parametric because its structure learning mechanism contains an attention parameter.The pooling process itself is non-parametric, but the complete operator is not.
Related Work
Prior GNN research developed spectral and spatial convolution methods, while graph pooling approaches reduce graph size and enlarge receptive fields. Existing pooling methods trade computational efficiency against preservation of complete graph structure, and other approaches use global or topology-based pooling.
- GNN convolutions: GNN convolution methods are commonly divided into spectral approaches and spatial approaches.Spectral methods define convolutions through graph Fourier representations, whereas spatial methods aggregate neighborhood representations directly.
- Graph pooling: Pooling in GNNs can reduce input size and enlarge receptive fields, supporting generalization and graph-level representation learning.The related work describes pooling as a mechanism for scaling down graph inputs.
- Graph pooling: DiffPool softly assigns nodes to clusters but forms a dense assignment matrix and is computationally expensive.This contrasts with top-K node-selection methods that form induced subgraphs more efficiently.
- Graph pooling: gPool and SAGPool use top-K node selection to form induced subgraphs, but may lose graph structure completeness and create isolated nodes.These methods improve efficiency while introducing a structural preservation concern.
- Alternative pooling: Other approaches perform global pooling or use graph-topology-based modules such as Graclus.Examples include Set2Set, DGCNN, and topology-based pooling methods.
The Proposed Model
HGP-SL builds hierarchical graph representations by repeatedly applying graph convolution and pooling, then refining each pooled graph’s structure. It selects nodes using neighborhood-based information scores and performs end-to-end graph classification.
- Problem formulation: Graphs are represented with node sets, edge sets, feature matrices, adjacency matrices, and graph labels that may vary in size across examples.The formulation tracks changing graph structure and node counts across layers.
- Problem formulation: The model receives labeled graphs, the number of GNN layers, a pooling ratio, and layer representation dimension, and predicts unknown graph labels end to end.These quantities define the stated input and output of the problem formulation.
- Overall architecture: HGP-SL combines graph convolution with graph pooling and structure learning, and can also be integrated with GraphSAGE and GAT.GCN is used as the model building block in the described implementation.
- Overall architecture: The architecture repeats convolution and pooling, aggregates representations from multiple levels with readout functions, and classifies graphs using an MLP with softmax.The final graph representation is formed by adding summaries from different hierarchy levels.
- HGP-SL operator: Graph pooling preserves informative nodes to form a smaller induced subgraph, while structure learning refines its graph structure.The two components are designed together to preserve essential topological information and facilitate message passing.
- Graph pooling operation: The node information score measures the Manhattan distance between a node representation and one reconstructed from its neighbors.A larger score indicates that the node is less well represented by its neighborhood.
- Graph pooling operation: Nodes with relatively larger information scores are retained, and top-ranked indices define the pooled graph’s extracted representations and adjacency matrix.The pooling ratio determines how many nodes are selected.
Structure Learning Mechanism
The structure learning mechanism refines pooled graph connectivity by combining induced-subgraph structure with attention-based pairwise similarity, using sparsemax to produce a sparse graph.
- Motivation: The structure learning mechanism addresses disconnected highly related nodes that can arise after pooling and hinder message passing.It is designed to preserve more complete graph structure information in the pooled graph.
- Structure learning: The layer learns a refined pooled-graph structure encoding underlying pairwise relationships between nodes.It takes pooled-subgraph structure information and hidden node representations as inputs.
- Attention scores: The attention similarity score is computed from the hidden representations of node pairs using a single-layer neural network with an activation function and concatenation.The hidden representations’ rows correspond to the respective node representations.
- Structure learning: The induced adjacency biases attention toward directly connected nodes while allowing relationships between disconnected nodes to be learned.λ controls the trade-off between these two sources of information.
- Sparse attention: Sparsemax replaces dense softmax connectivity by retaining values above a threshold and truncating the rest to zero.The resulting scores remain non-negative and sum to one.
Improving Structure Learning Efficiency
For large graphs, HGP-SL reduces structure-learning cost by restricting pairwise similarity calculations to local h-hop neighborhoods.
- Efficiency motivation: Similarity computation is expensive when performed between every pair of nodes in large graphs.The method therefore uses graph localization and smoothness to motivate a local constraint.
- Local computation: Restricting calculations to each node’s h-hop neighborhood, with h = 2 or 3, greatly reduces the computation cost of the learned structure.The neighborhood constraint limits the scope of pairwise similarity calculations.
GCN and Graph Pooling Revisiting
After learning a refined graph structure, the model uses it for subsequent graph convolution and pooling operations, with simplifications that ease implementation.
- Layer operations: Subsequent graph convolution and pooling operations are based on the learned refined graph structure.The refined structure is used in the following layers.
- Implementation: These simplifications make the model easy to implement.The simplified expressions apply to the graph convolution and node-information-score computations.
- Computational simplification: Because sparse attention scores sum to one, the degree matrix becomes an identity matrix in the simplified computation.The node-information-score calculation can also be simplified.
The Readout Function and Output Layer
The network produces graph-level representations by aggregating node representations from multiple subgraph levels, then classifies graphs with an MLP and softmax output.
- Hierarchical representations: Repeated graph convolution and pooling operations produce subgraphs of different sizes across multiple levels.The hierarchy contains representations from successive subgraph levels.
- Readout function: The readout function concatenates mean-pooling and max-pooling within each subgraph to generate a fixed-size representation.This combines two aggregation summaries for every level.
- Readout function: Readout outputs from different levels are added to form the final graph-level representation summarizing multiple levels.The resulting representation combines information across the hierarchy.
- Experimental setup: The dataset-statistics table summarizes the six benchmark datasets used for empirical studies.The table is identified by its caption as reporting dataset statistics.
- Output layer: The final graph-level representation is fed to an MLP with a softmax classifier, trained using cross-entropy over labeled graphs.The predicted class probabilities are compared with the ground-truth labels.
Experiments and Analysis
Experiments on six public benchmarks compare HGP-SL with graph kernels, GNNs, global pooling, and hierarchical pooling baselines. HGP-SL consistently performs strongly, while ablations, architecture tests, and sensitivity analyses examine its structure learning, generality, and settings.
- Experimental Setup: HGP-SL is evaluated against graph kernels, GNNs, global pooling methods, and five hierarchical pooling baselines on six public benchmarks.The benchmarks include ENZYMES, PROTEINS, and D&D among the listed datasets.
- Experimental Setup: The experiments use repeated 80%/10%/10% train-validation-test splits, report average performance with standard deviation, and match neural architectures across pooling baselines.The random splitting process is repeated 10 times, with hyperparameters tuned on validation data.
- Graph Classification Results: HGP-SL consistently outperforms state-of-the-art baselines across all datasets, including a 3.08% improvement over the best PROTEINS baseline and 12.97% over GCN without hierarchical pooling.The paper uses these comparisons to support adding graph pooling to GNNs.
- Graph Classification Results: Most hierarchical pooling methods outperform global Set2Set and DGCNN, while HGP-SL surpasses EdgePool with different gains across all settings.The paper attributes the global methods’ weaker performance to flat representations that ignore hierarchical structure or functional units.
- Ablation Analysis: HGP-SL and its dense-structure variant outperform no-structure-learning and h-hop variants, while HGP-SL exceeds the dense variant, suggesting sparse learned structures avoid additional noise.The h-hop variant can leave disconnected nodes unreachable, whereas dense structures may introduce noisy information.
- Architecture and Sensitivity Analysis: Structure learning improves gPool-SL and SAGPool-SL over their original versions, and HGP-SL performs best across varied settings near K = 3, d = 128, and r = 0.8.The pooling ratio should not be too small because pooling can lose much of the graph structure information.
Conclusion
HGP-SL is a graph pooling operator that combines non-parametric node down-sampling with structure learning and integrates into various GNN architectures. Combined with GNNs, it supports graph classification, with experiments on six benchmarks demonstrating superiority to state-of-the-art methods.
- HGP-SL performs non-parametric down-sampling using node features and graph structure information.
- HGP-SL can be integrated into various GNN architectures for graph-level representation learning and graph classification.
- A structure learning layer refines the pooled graph structure to preserve essential topological information.
- Comprehensive experiments on six widely used benchmarks demonstrate superiority to a range of state-of-the-art methods.
Proof for Algorithm 1
The proof characterizes sparsemax as the Euclidean projection of an input vector onto the probability simplex and derives its solution through optimization conditions. The resulting support set and threshold yield the procedure used in Algorithm 1.
- Sparsemax is formulated as the Euclidean projection of input vector z onto the probability simplex.
- The proof introduces the Lagrangian and requires the optimal variables to satisfy the Karush-Kuhn-Tucker conditions.
- The positive-support set S(z) identifies indices whose projected values are positive.
- Summing supported coordinates gives β*=τ(z), while non-supported coordinates satisfy z_i≤β*, yielding Algorithm 1.