PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking pooling in graph neural networks

Diego Mesquita, Amauri H. Souza, Samuel Kaski

arXiv:2010.11418v1cs.LGcs.AIcs.CV

TL;DR

Whether graph pooling needs locality-preserving clusters had not been rigorously evaluated. The paper compares representative GNNs with randomized and non-local pooling variants and studies how convolution interacts with pooling. The variants retain comparable or better performance, while early convolutions help make the specific pooling assignments less relevant.

  • Problem

    Although clustering-based local pooling is widespread, the importance of cluster-assignment quality had not been rigorously evaluated.

    Source: §1 · p. 1

  • Method

    The authors modify representative GNNs to use randomized assignments or non-local pooling, then study convolution-pooling interplay and learned embeddings.

    Source: §1 · p. 2, §2.1 · p. 2

  • Results

    Non-local GNN variants perform comparably to, or better than, the original methods across the experiments.

    Source: §1 · p. 2

  • Takeaways & Limitations

    On the accredited benchmarks studied, extracting local information is not necessary for efficient pooling, and pooling proposals warrant more ablation studies.

    Source: §1 · p. 2, §5 · p. 9

    Randomized variants break DIFFPOOL's permutation invariance, though a simple feature-based fix is described.

    Source: Case 2: Differential pooling · p. 4

Abstract

from arXiv · show

Graph pooling is a central component of a myriad of graph neural network (GNN) architectures. As an inheritance from traditional CNNs, most approaches formulate graph pooling as a cluster assignment problem, extending the idea of local patches in regular grids to graphs. Despite the wide adherence to this design choice, no work has rigorously evaluated its influence on the success of GNNs. In this paper, we build upon representative GNNs and introduce variants that challenge the need for locality-preserving representations, either using randomization or clustering on the complement graph. Strikingly, our experiments demonstrate that using these variants does not result in any decrease in performance. To understand this phenomenon, we study the interplay between convolutional layers and the subsequent pooling ones. We show that the convolutions play a leading role in the learned representations. In contrast to the common belief, local pooling is not responsible for the success of GNNs on relevant and widely-used benchmarks.

1 Introduction

The paper questions whether graph pooling must preserve local clusters, a widely used but insufficiently tested design choice. It finds that randomized or non-local pooling performs comparably to original methods, and links this robustness to convolution-driven smoothing of node representations.

1 Introduction

  • Most GNNs use local pooling, combining graph-cluster regions into a coarser graph as an analogue of CNN neighborhoods.GNN layers typically interleave local filtering and pooling, with pooling reducing the graph representation while aiming to preserve important structure.Source: §1 · p. 1
  • Despite the influence of clustering-based pooling, the importance of cluster-assignment quality had not been rigorously evaluated.The paper notes that misconceptions can encourage unnecessary complexity and obscure interpretability.Source: §1 · p. 1
  • Non-local GNN variants using randomized assignments or complement graphs perform comparably to, or better than, the original methods in all experiments.Source: §1 · p. 2
  • Early low-pass convolutions produce homogeneous embeddings, making the specific way nodes are combined during pooling less relevant.Source: §1 · p. 2
  • The authors use benchmarks where GNNs outperform structure-agnostic baselines and argue that pooling schemes need more ablation studies.Source: §1 · p. 2

2 Exposing local pooling

The experiments test whether graph pooling needs locality-preserving assignments by replacing clustering with complement-graph or random assignments in representative GNNs. Across the tested tasks, these variants perform comparably to the original models.

2.1 Experimental setup

  • The study tests GRACLUS, DIFFPOOL, and GMN on four graph-level tasks, reporting 20-run performance statistics with an 80/10/10 train-validation-test split.The authors modify pooling while keeping the rest of each model structure untouched, aiming to isolate local-pooling effects rather than benchmark the models.Source: §2.1 · p. 2

Case 1: Pooling with off-the-shelf graph clustering

  • Complement-graph clustering computes assignments on the complement but pools using the original graph; GRACLUS and COMPLEMENT perform almost on par across tasks.Figure 1 shows similar performance distributions over 20 runs.Source: Case 1: Pooling with off-the-shelf… · p. 3, Figure 1 · p. 3
  • NCI1 accuracy was 80.0±1.4 for GIN versus 80.1 ± 1.6 for COMPLEMENT; on IMDB-B, GraphSAGE scored 69.9 ± 4.6 versus COMPLEMENT’s 70.6 ± 5.1.The comparisons are reported against previously reported models; Table 1 covers GRACLUS and COMPLEMENT alongside GIN and GraphSAGE.Source: Table 1 · p. 3, Case 1: Pooling with off-the-shelf… · p. 3

Case 2: Differential pooling

  • Replacing DIFFPOOL’s learned assignments with random matrices gave the highest average accuracy on every task, without consistently higher variance.The tested assignments use Uniform U(0, 1), Normal N(0, 1), and Bernoulli B(0.3) distributions; DIFFPOOL’s link-prediction loss encourages nearby nodes to be pooled together.Source: Case 2: Differential pooling · p. 4, Figure 2 · p. 4
  • Random DIFFPOOL assignments break permutation invariance; an embedding-based random assignment variant was approximately invariant on artificially permuted ZINC graphs.The fix sets the random assignment matrix to the product of the previous-layer embeddings and a random matrix.Source: Case 2: Differential pooling · p. 4, Figure 3 · p. 4

Case 3: Graph memory networks

  • Uniform cluster assignments, which the GMN loss is intended to avoid, are a perfect minimizer of that loss.The loss is described as intended to improve cluster purity.Source: Case 3: Graph memory networks · p. 5
  • DISTANCE groups nodes farthest from fixed uniform keys, while RANDOM uses fixed random assignments; both matched GMN across datasets and had slightly better ZINC MAE.Figure 4 reports that neither dissimilarity-based nor random pooling harms performance, and both variants have lower MAE on ZINC.Source: Case 3: Graph memory networks · p. 5, Figure 4 · p. 5
  • On SMNIST, DISTANCE took up to half GMN’s per-epoch time, while RANDOM was up to ten times faster.The simplified models have significantly fewer learned parameters; RANDOM also bypasses pairwise-distance computation.Source: Case 3: Graph memory networks · p. 5

3 Analysis

The analysis finds that early convolutions produce homogeneous node representations, making pooling assignments less consequential; removing those convolutions hurts performance. Across tested datasets and pooling variants, non-local or global pooling performs comparably to local pooling.

3 Analysis

  • Early convolutions produce relatively homogeneous node features within graphs, and subsequent pooling layers accentuate that homogeneity.The plotted embeddings include randomized DIFFPOOL and GMN variants and COMPLEMENT on ZINC; similar patterns are reported for other datasets in Appendix E.Source: §3 · p. 6
  • DIFFPOOL and GMN also learn homogeneous representations, helping explain why randomized pooling matches their local-pooling counterparts.The local-clustering loss terms are either not beneficial to the task or are obfuscated by supervised loss; this observation does not apply to deterministic GRACLUS.Source: §3 · p. 6, Figure 6 · p. 6
  • Increasing DIFFPOOL’s unsupervised loss has no positive performance impact on ZINC and SMNIST validation results.Source: Figure 7 · p. 7
  • Using a single convolution before pooling lowers performance: NCI1 accuracies fall by about 4% on average, and GRACLUS and GMN drop 4% on SMNIST.With a single initial GraphSAGE convolution, DIFFPOOL and its uniform variant reach 66.4% on SMNIST; the drop is not observed on IMDB-B, whose node features are constant.Source: §3 · p. 7, Table 2 · p. 7
  • Local pooling offers no accuracy benefit in the evaluated models, and global mean pooling performs on par with GRACLUS, DIFFPOOL, and GMN.The reported global mean pooling results are 79.65 ± 2.07 (NCI), 71.05 ± 4.58 (IMDB-B), 95.20 ± 0.18 (SMNIST), and 0.443 ± 0.03 (ZINC).Source: §3 · pp. 6–7

3.1 Additional results

  • On additional datasets, random pooling achieves results comparable to local MINCUTPOOL.The additional-dataset results likewise report non-local pooling as good as local pooling.Source: §3.1 · p. 8, Table 3 · p. 8
  • Across tested hyperparameter settings, GRACLUS and COMPLEMENT remain similar; the largest reported gap favors COMPLEMENT by no more than 0.05 MAE on ZINC.The comparison varies pooling-layer count and embedding dimensionality over a single run; the authors note that hyperparameters were not exhaustively optimized.Source: §3.1 · p. 8, Figure 8 · p. 8

4 Related works

Related work covers global and hierarchical pooling, simplified GNNs, benchmark evaluation, and pooling or attention in regular domains. These studies provide context for assessing assumptions about pooling and model design.

  • Graph pooling includes global aggregation of node representations and hierarchical methods that sequentially coarsen graphs.Knyazev et al. [24] unify local pooling and node attention, study generalization to larger and noisy graphs, and find attention can be negligible or harmful except in certain circumstances.Source: §4 · p. 9
  • Simplified GNN studies report competitive performance from removing nonlinearities, using linear convolutional filters with nonlinear set functions, or using local node statistics.Wu et al. [43] characterize the resulting GCN feature extractor as a low-pass-type filter; Chen et al. [6] report competitive graph-classification performance.Source: §4 · p. 9
  • Prior benchmarking work finds evaluation protocols and small datasets can affect reproducibility and comparisons between GNNs and structure-agnostic baselines.Errica et al. [11] report that structure-agnostic baselines outperform popular GNNs on at least three chemical datasets; Dwivedi et al. [10] introduce a framework with larger datasets.Source: §4 · p. 9
  • CNN studies report pooling is not necessary for deformation stability, while random pooling has been proposed as a faster alternative to conventional CNNs.In attention-based models, Wiegreffe and Pinter [42] find attention weights usually do not provide meaningful explanations for predictions.Source: §4 · p. 9

5 Conclusion

The paper examines local pooling amid limited rigorous assessment of GNN design choices. It reports that early convolutions smooth node representations, making pooling assignments approximately invariant, and that local information is not necessary for efficient pooling on the evaluated benchmarks.

  • The paper finds that most GNN architectures use convolutions that can quickly produce smooth node representations, making pooling layers approximately invariant to cluster assignments.Source: §5 · p. 9
  • Across accredited benchmarks, extracting local information is not necessary for efficient pooling, and clustering-enforcing regularization is usually innocuous.Source: §5 · p. 9
  • The authors propose these findings as a sanity-check for novel pooling strategies and as a way to challenge misconceptions about graph pooling.Source: §5 · p. 9

Broader impact

The paper addresses local pooling as a core GNN design choice whose role in GNN success is only partially understood. It anticipates helping researchers and practitioners choose where to direct effort when building more accurate GNNs.

  • The work focuses on local pooling, a core design choice in many GNN architectures whose underlying design principles remain only partially understood.Source: Broader impact · p. 10
  • The authors expect the work to help researchers and practitioners choose where to direct time and resources when building more accurate GNNs.Source: Broader impact · p. 10
  • The stated motivation spans GNN use in social network analysis, drug discovery, recommender systems, and natural language processing.Source: Broader impact · p. 10

A.1 Datasets

The appendix describes dataset choices and implementation settings for the evaluated pooling models, including selected preprocessing, model configurations, and training procedures.

A.1 Datasets

  • NCI1 is the only chemical TU dataset cited here where GNNs beat baselines, while IMDB-B has an ≈20% baseline–DiffPool gap.Statistics are also reported for PROTEINS, NCI109, DD, and MOLHIV.Source: §A.1 · p. 13
  • SMNIST and ZINC use the preprocessing and data splits from [10], while IMDB-B assigns every node an all-ones feature vector.The authors also report dataset statistics for PROTEINS, NCI109, DD, and MOLHIV.Source: §A.1 · p. 13

A.2 Models

  • Training uses Adam with a learning rate decaying from 10^-3 to 10^-5, halved after 10 epochs without validation improvement, and early stopping with patience 50.The implementation uses PyTorch Geometric.Source: §A.2 · p. 13
  • GRACLUS and COMPLEMENT interleave convolution and pooling, then use global mean readout and a one-hidden-layer MLP.COMPLEMENT follows the same setup as GRACLUS.Source: §A.2 · p. 13
  • DIFFPOOL follows [10] with GraphSAGE convolutions before and after pooling, while GMN is reimplemented with a two-convolution query network and a 50-node hidden layer.For MOLHIV, edge embeddings are added to node features before the first convolution.Source: §A.2 · pp. 13–14

B Additional experiments

Additional experiments compare more pooling variants and examine permutation invariance and the GMN unsupervised loss. The appendix also explains how uniform cluster assignments minimize that loss.

B Additional experiments

  • MINCUTPOOL learns assignments using node features and graph topology; its randomized variant replaces the learned matrix with a standard-normal random matrix and uses only supervised loss.The appendix also evaluates a second DIFFPOOL architecture and its randomized N-DIFFPOOL V2 variant.Source: B Additional experiments · p. 15
  • 89.3% vs 82.0%: MINCUTPOOL outperforms its randomized variant on SMNIST, although original and randomized pooling methods otherwise perform similarly.The authors attribute the exception to using only one convolution before the first pooling layer; two initial convolutions suffice to close the gap.Source: Table S5 · p. 15, B Additional experiments · p. 15

C Permutation Invariance

  • Permutation invariance means predictions do not change with graph representation, whereas equivariance makes nodewise outputs change correspondingly under node relabeling.The appendix states these properties for simplified GNNs.Source: C Permutation Invariance · pp. 15–16

B Additional experiments

  • Updating GMN keys more frequently does not improve performance, and the validation-loss curves show a worse minimum for IMDB-BINARY.The comparison uses key-update intervals p = 2 and p = 5 on ZINC and IMDB-BINARY.Source: B Additional experiments · p. 15, Figure S1 · p. 16

C.1 GRACLUS

  • COMPLEMENT is invariant when its clustering algorithm is invariant; GRACLUS may not be, because its initialization-dependent heuristic can return different cuts.Source: §C.1 · p. 16

C.2 DIFFPOOL

  • The randomized DIFFPOOL variant is invariant, with its modified assignment matrix transforming consistently when node features are permuted.Source: §C.2 · p. 16

C.3 GMN

  • The simplified GMN is invariant if its initial query network is equivariant, because each modified memory layer is invariant.This variant uses distances rather than the Student’s t-kernel.Source: §C.3 · p. 17

D Further details on Remark 2

E Additional embeddings

The supplementary activation figures reinforce the finding that GNNs learn smooth signals in early layers, making pooling strategies less relevant. Their visualizations normalize each embedding’s color scale separately.

E Additional embeddings

Loading 2010.11418v1…