Source-linked AI summary
Towards Sparse Hierarchical Graph Classifiers
Cătălina Cangea, Petar Veličković, Nikola Jovanović, Thomas Kipf, Pietro Liò
TL;DR
Graph classification needs adaptive hierarchical pooling, but DiffPool’s soft assignment matrices require quadratic memory during training. This paper combines graph neural network design advances to retain sparse storage while achieving competitive benchmark performance comparable to DiffPool variants.
Problem
Graph classification remains less developed than node classification and link prediction, and differentiable hierarchical pooling is constrained by DiffPool’s quadratic O(kV 2) storage during training.
Method
The paper builds an end-to-end graph convolutional architecture with inductive graph convolutions, learnable pooling, and multi-layer graph-summary aggregation while retaining sparse operations.
Results
The method achieves performance comparable to DiffPool variants on four standard graph classification benchmarks while using O(V + E) storage.
Takeaways & Limitations
Competitive hierarchical graph classification need not sacrifice sparsity, enabling a path toward scalable deployment on larger real-world datasets.
Takeaways & Limitations
The experiments restrict attention to undirected, unweighted graphs with binary symmetric adjacency matrices.
Abstract
from arXiv · showhide
Recent advances in representation learning on graphs, mainly leveraging graph convolutional networks, have brought a substantial improvement on many graph-based benchmark tasks. While novel approaches to learning node embeddings are highly suitable for node classification and link prediction, their application to graph classification (predicting a single label for the entire graph) remains mostly rudimentary, typically using a single global pooling step to aggregate node features or a hand-designed, fixed heuristic for hierarchical coarsening of the graph structure. An important step towards ameliorating this is differentiable graph coarsening---the ability to reduce the size of the graph in an adaptive, data-dependent manner within a graph neural network pipeline, analogous to image downsampling within CNNs. However, the previous prominent approach to pooling has quadratic memory requirements during training and is therefore not scalable to large graphs. Here we combine several recent advances in graph neural network design to demonstrate that competitive hierarchical graph classification results are possible without sacrificing sparsity. Our results are verified on several established graph classification benchmarks, and highlight an important direction for future research in graph-based neural networks.
1 Introduction and Related Work
Graph classification extends graph representation learning from node-level and link-level tasks to assigning labels to entire graphs. Existing pooling approaches either aggregate globally or coarsen hierarchically, while differentiable pooling improves adaptivity but DiffPool incurs quadratic memory; this work targets competitive hierarchical classification while retaining sparsity.
- Background: Graph classification assigns a class label to an entire graph and generalizes image classification by viewing images as grid graphs.The grid graph connects each pixel to its eight immediate neighbours.
- Related work: Graph convolution research has advanced node classification and link prediction substantially, whereas graph pooling has received less attention.The passage contrasts active development of graph convolutional layers with comparatively limited work on pooling layers.
- Related work: Existing pooling strategies either globally aggregate node representations or cluster nodes to hierarchically coarsen the graph.Earlier hierarchical methods generally use fixed, pre-defined cluster assignments obtained through graph-node clustering algorithms.
- Related work: DiffPool introduced an end-to-end trainable graph CNN with learnable soft node-to-cluster assignments that can converge toward interpretable hard clusterings.Its assignments respect graph adjacency and use an entropy regularizer to induce sparsity.
- Limitations of prior work: DiffPool requires storing an all-pairs assignment matrix during early training, producing quadratic O(kV 2) storage and limiting scalability to large graphs.The limitation applies to pooling schemes with a fixed pooling ratio k.
- Contribution: The proposed approach combines recent graph neural network advances to achieve performance comparable to DiffPool variants on four standard benchmarks using O(V + E) storage.Its storage requirement is comparable to that of the input graph, preserving sparsity.
2 Model
The model combines inductive graph convolutions, adaptive node-dropping pooling, and multiscale readout to classify graphs while preserving sparse computation.
- Model setup: The input graph uses node features X and adjacency matrix A, with undirected, unweighted graphs assumed.Featureless graphs can use node degree information as artificial node features.
- Convolutional layer: The convolutional layer is inductive, enabling classification of unseen graph structures without depending on a fixed graph.It uses a mean-pooling propagation rule with self-loops, learnable transformations, ReLU activation, and a skip connection.
- Pooling layer: Each pooling layer retains ⌈kN⌉ nodes from an N-node graph by dropping the remaining nodes, rather than clustering them into pooled nodes.This contrasts with DiffPool’s soft clustering and avoids its quadratic assignment-storage penalty.
- Pooling layer: Nodes are selected using projection scores against a learnable vector, which also gate feature retention so gradients reach the scoring vector.The pooled feature and adjacency matrices are formed by selecting indexed slices after pointwise gating.
- Readout layer: The readout combines global average and max pooling summaries from every convolution-pooling block, sums them, and sends the result to an MLP.Aggregating across layers preserves information at different processing scales and helps when small graphs are rapidly reduced.
3 Experiments
The experiments evaluate the sparse graph neural network on four graph-classification benchmarks and compare accuracy and memory usage with GraphSAGE and DiffPool. The method remains competitive with DiffPool while avoiding quadratic memory requirements.
- Datasets and evaluation: Evaluation uses 10-fold cross-validation on Enzymes, Proteins, D&D, and Collab graph-classification benchmarks.The comparison relates results to those reported for DiffPool by Ying et al.
- Model parameters: The architecture uses three graph convolution–pooling blocks, with 128 or 64 features depending on the dataset.Each block contains a graph convolutional layer followed by pooling.
- Classification results: Across all datasets, the model outperforms GraphSAGE and remains within at most 1 percentage point of DiffPool variants in accuracy.The reported comparison covers the benchmark results in Table 1.
- Memory usage: The method compares favorably with DiffPool on larger random graphs even without dropping nodes, whereas DiffPool retains 0.25 of the nodes.The memory experiment uses Erdős-Rényi graphs with |E| = 2|V| and three Conv-Pool layers.
A Qualitative analysis
The qualitative analysis examines graph summaries produced for 499 Collab test graphs across three classes. The resulting summaries show evident class clustering after the model's convolution and pooling sequence.
- Figure 3: The t-SNE plot represents graph summaries as points and distinguishes the three classes by color.This visualization is intended to illustrate the model's classification capabilities.
- Qualitative analysis: The analysis uses a pre-trained model to generate summaries for 499 Collab test graphs spanning three classes.The summaries are visualized with t-SNE, with each class represented by a different color.
- Qualitative analysis: An evident clustering of the three classes is achieved after the sequence of convolution and pooling layers.The finding is qualitative and concerns the distribution of learned graph summaries.