TL;DR
Graph pooling operations often fail to outperform simple "no-pool" baselines because a graph's node features are frequently misaligned with its topological structure. This paper introduces a novel graph-coloring framework to quantify this feature-topology alignment and demonstrates that incorporating structural Positional Encodings (PEs) can significantly restore the effectiveness of deep graph pooling.
What Problem Does This Paper Address?
In graph classification tasks, graph pooling is designed to step-wise reduce the size of a graph into a compact vector representation, mimicking the successful downsampling hierarchical architecture of Convolutional Neural Networks (CNNs) in computer vision. However, in practice, graph pooling often yields inconsistent or marginal performance gains. Frequently, a simple "no-pool" baseline—which just passes messages across the full graph and performs a global aggregation at the very end—performs just as well, if not better.
The authors identify a fundamental conflict causing this issue: pooling operators typically cluster nodes based on their features or embeddings, but the unsupervised loss functions evaluating these clusters rely strictly on the graph's topology. If a graph's features do not inherently correlate with its structure, pooling fails.
Methods
The authors formalize the mathematical requirements for when node features allow a deterministic neural network to find an optimal topological partition. To evaluate real-world datasets, they introduce a graph-colouring-based framework that treats node features as discrete colors and measures two key properties:
- Colouring Validity ($\Gamma$): The probability that nodes sharing the same color belong to the same topological cluster.
- Colouring Transferability ($\Lambda$): The ability of a learned feature-to-cluster mapping to generalize from seen training graphs to unseen testing graphs (essential for inductive learning).
They combine these into a single quality metric: $Q = \min(\Gamma, \Lambda)$.
To fix the misalignment problem, the authors propose a modified pooling setup. They inject Positional Encodings (PEs)—such as Laplacian eigenvectors or Node2Vec embeddings—directly into the selection (SEL) stage of pooling operators (like DiffPool or MinCut). Crucially, they bypass message-passing on these PEs to prevent "over-smoothing," ensuring the pooling layer retains sharp structural coordinates.
Datasets
The framework and modified pooling architectures were evaluated on a wide array of standard graph classification benchmarks from the TUDataset collection:
- Bioinformatics/Molecules: MUTAG, PROTEINS, ENZYMES, Mutagenicity, NCI1, DD.
- Social/Interaction Networks: COLLAB, IMDB-BINARY, REDDIT-BINARY, COLORS-3.
- Synthetic: A controlled synthetic dataset.
Key Insights and Ideas
- The Deterministic Trap: Because GNNs and MLPs act as deterministic functions, they are forced to assign nodes with identical features and identical local neighborhoods to the same cluster, even if those nodes are on opposite sides of a large graph.
- Empirical Misalignment: In many popular benchmark datasets, the natural alignment between raw node features and topological communities is incredibly poor (as measured by Normalized Mutual Information).
- The Refinement Trade-off: Running Weisfeiler-Leman (WL) color refinement steps initially creates more unique, topology-aware colors. While this can alter validity, it generally causes transferability to suffer because the exact structural color combinations become too specific to the training graphs.
- Pooling Suitability is an Inherent Dataset Property: Poor pooling performance isn't just a flaw of the pooling algorithms themselves. Some datasets are fundamentally unsuited for community-based pooling because their target labels do not correlate with topological clusters.
Key Results
The authors tested five major pooling methods (DiffPool, DMoN, JBPool, MDL-Pool, and MinCut) across the datasets.
- PEs Boost Feature Quality: Structural positional encodings (especially Laplacian PEs and node2vec) consistently achieved drastically higher feature-topology quality scores ($Q$) compared to raw empirical features or random baselines.
- Downstream Performance Gains: When PEs were added to pooling architectures, downstream graph classification accuracy improved significantly on datasets where pooling is inherently appropriate. For instance, on MUTAG and REDDIT-BINARY, pooling with PEs comfortably outperformed the strong "no-pool" baseline.
- No Silver Bullet: On certain datasets like PROTEINS, the "no-pool" baseline remained superior even after adding PEs, confirming that pooling is not universally beneficial for every graph architecture.
Limitations and Future Work
A primary limitation is that the proposed feature-quality measure assumes a community-detection or spectral-clustering definition of node groups. It is not directly compatible with ranking-based pooling methods (which drop "unimportant" nodes rather than clustering them).
Additionally, the authors assume that a graph's topological communities are inherently informative for predicting its class label, which may not always be true due to low-quality dataset labeling. Future work includes developing GNN clustering layers that integrate topology more directly without relying heavily on high-quality features, and extending the coloring framework to tasks beyond graph classification.
Summary updated