PaperlayerView exact revision on arXiv

Source-linked AI summary

Edge Contraction Pooling for Graph Neural Networks

Frederik Diehl

arXiv:1905.10990v1cs.LGstat.ML

TL;DR

Graph neural network research has developed relatively few pooling layers, although pooling could support reasoning over clusters and hierarchical node groups. The paper introduces EdgePool, a localized and sparse hard pooling method based on edge contraction. EdgePool generally outperforms prior pooling approaches, integrates into many GNN architectures, and usually improves node- and graph-classification performance.

  • Problem

    Graph neural network research has proposed many convolutional layers but relatively few pooling layers, despite pooling’s potential to support hierarchical groups of nodes.

  • Method

    EdgePool performs hard pooling by selecting edges for contraction, producing a localized and sparse transform based on graph structure.

  • Results

    Except for one pooling procedure on one dataset, EdgePool outperforms previously proposed pooling approaches and usually improves node- and graph-classification performance across many GNN architectures.

  • Takeaways & Limitations

    EdgePool can be integrated into a large number of GNN architectures without adaptations to training or architecture and may support future methods that modify graph structures.

  • Takeaways & Limitations

    Performance increases are not consistent across datasets and models, making specific recommendations about when to include EdgePool impossible.

Abstract

from arXiv · show

Graph Neural Network (GNN) research has concentrated on improving convolutional layers, with little attention paid to developing graph pooling layers. Yet pooling layers can enable GNNs to reason over abstracted groups of nodes instead of single nodes. To close this gap, we propose a graph pooling layer relying on the notion of edge contraction: EdgePool learns a localized and sparse hard pooling transform. We show that EdgePool outperforms alternative pooling methods, can be easily integrated into most GNN models, and improves performance on both node and graph classification.

1 Introduction

Graph pooling remains less developed than graph convolution, despite its potential to identify clusters, reduce node counts, and support hierarchical graph representations. EdgePool addresses this gap by selecting edges for contraction, and the paper reports better performance, architectural integration, and node-classification improvements.

  • Graph neural network research has proposed many convolutional layers but relatively few pooling layers.
  • Graph pooling can identify feature- or structure-based clusters, reduce computational requirements, and abstract nodes into hierarchical groups.
  • EdgePool learns which edges to contract, pooling their connected nodes while incorporating graph structure and avoiding complete node removal.
  • The paper reports that EdgePool performs better than other pooling methods and improves performance on node classification.
  • EdgePool is presented as a hard pooling layer that can be integrated into existing graph classification architectures.

2 Related work

Prior learned pooling methods trade off flexibility, sparsity, locality, or computational practicality. DiffPool uses dense feature-based cluster assignments, while TopKPool and SAGPool select nodes globally, leaving structural and scalability concerns.

  • Learned pooling methods are emphasized because they appear to outperform fixed topology-based pooling methods.
  • DiffPool: DiffPool soft-assigns nodes to a fixed number of feature-based clusters, requiring auxiliary objectives and a dense assignment matrix that scales quadratically with node count.
  • DiffPool: DiffPool’s feature-only assignments ignore distances, while its dense representation complicates integration into sparse GNNs.
  • TopKPool: TopKPool is sparse and supports variable graph sizes but uses globally dependent node selection, so adding nodes can change the whole pooling result.
  • SAGPool: SAGPool incorporates neighboring node features through graph convolutions, but retains TopKPool’s disadvantages.

3 EdgePool

EdgePool pools graphs by learning edge scores and iteratively contracting compatible high-scoring edges. It produces sparse, localized transformations, supports node-classification unpooling, and has a fixed pooling ratio of roughly 50%.

  • 3.1 Edge contraction: EdgePool contracts selected edges by merging their endpoint nodes and reconnecting the merged node to their former neighbors.Multiple contractions are applied only when no two selected edges share a node or newly merged node.
  • 3.2 Choosing edges: The highest-scoring eligible edges are contracted iteratively, while edges incident to newly merged nodes are ignored.This greedy compatibility rule determines the sparse hard pooling transform.
  • 3.2 Choosing edges: Raw edge scores are learned from concatenated endpoint features, then locally normalized over edges incident to each node.The normalization shifts the score range to have mean 1, supporting numerically stable unpooling.
  • 3.2 Choosing edges: EdgePool always pools roughly 50% of the total nodes, unlike DiffPool and TopKPool, whose pooling ratios can be changed.The fixed ratio constrains control over the amount of pooling.
  • 3.3 Computing new node features: Merged node features use the sum of endpoint features and edge-score gating to preserve gradient flow into the scores.The authors report that softmax normalization performed better than a simple tanh gate.
  • 3.5 Integrating edge features: EdgePool operates on sparse representations with runtime and memory scaling linearly in the number of edges, and its local decisions need not be recomputed globally.For graphs with edge features, the method can concatenate them into score computation, but edge-feature merging was not experimentally evaluated.
  • 3.6 Unpooling EdgePool: The layer emits node mappings for unpooling, allowing mappings to chain across layers and enabling pooled representations in node classification.Unpooled features are divided by their corresponding edge scores.

4 Experiments

The experiments evaluate EdgePool on graph and semi-supervised node classification, comparing pooling strategies and testing integration across several GNN architectures. They use shared training procedures and randomized 10-fold cross-validation for the datasets.

  • 4 Experiments: The study asks whether EdgePool outperforms alternative pooling, integrates as a plug-and-play GNN addition, and supports node classification.These questions organize three experiments across graph and node classification settings.
  • 4.1 Experimental setup: All datasets use randomized 10-fold cross-validation with reported means and standard deviations, rather than the default planetoid split.Training uses shared procedures including Adam, 200 epochs, and a learning rate of 10^-3 halved every 50 epochs.
  • 4.1.1 Datasets: Graph classification uses PROTEINS, REDDIT-BINARY, REDDIT-MULTI-12K, and COLLAB, covering enzyme, subreddit, and researcher-field prediction tasks.COLLAB and both reddit-based datasets have no node features.
  • 4.1.1 Datasets: Node classification uses citation and Amazon co-purchasing graphs to predict document subfields or product categories from bag-of-word features.The setup uses 20 labeled training nodes and 30 test nodes per class, with remaining nodes unlabeled.
  • 4.2 Q1: The pooling comparison uses a shared SAGEConv-based graph classifier, with pooling after each block for EdgePool, DiffPool, and TopKPool.DiffPool is restricted to 750 nodes per graph and TopKPool uses a pool ratio of 0.5 for comparability.
  • 4.3.2 Q2: The architecture-integration experiment tests GCN, GIN, GIN0, GraphSAGE variants, and MLPs with pooling inserted after every second convolutional layer.The models use seven convolutional layers followed by global pooling and two fully connected layers.
  • 4.2 Q1: Accuracy comparisons are reported in percent with standard deviations, and DiffPool results omit its additional auxiliary losses and computed features.The table marks best results in bold.
  • 4.4 Q3: Node classification evaluates GCN, GIN, GIN0, GAT, and MLP layers using seven convolutional layers, intermediate pooling, unpooling, shortcuts, and a two-layer prediction MLP.Pooling occurs after the second and fourth layers, with unpooling after the fifth and seventh.

5 Results and discussion

EdgePool generally improves graph and node classification when integrated into existing architectures, although gains vary across datasets and models. Its edge-based pooling produces competitive results while preserving a sparse, architecture-compatible workflow.

  • 5.1 EdgePool vs. alternative pooling approaches: EdgePool consistently improves performance over non-pooling models and TopKPool, outperforming other pooling approaches on two tasks and trailing DiffPool on one.PROTEINS is excluded from this comparison because performance is close.
  • 5.2 EdgePool in existing architectures: On most GNN/dataset combinations, EdgePool increases accuracy by an average of almost 2 p.p.GraphSAGE gains the most at 5.5 p.p., while GIN and GIN0 gain 0.3 p.p. on average.
  • 5.2 EdgePool in existing architectures: EdgePool allows an MLP to perform competitively on PROTEINS and COLLAB by using pooling to obtain neighborhood information.The MLP cannot otherwise rely on graph convolutions for neighborhood information.
  • 5.2 EdgePool in existing architectures: Performance gains are not consistent across datasets and models, preventing a specific recommendation about when to include EdgePool.The authors therefore caution that some model and dataset combinations may not benefit.
  • 5.3 EdgePool for node classification: EdgePool improves node-classification performance for 21 of 25 dataset/model combinations, with an average GNN improvement of 3.5 p.p.It performs worst on PUBMED and with GCNs, while improving GIN and GIN0 by 5.8 p.p. and 6.6 p.p., respectively.
  • 5.3 EdgePool for node classification: Visualizations show that EdgePool preserves protein linearity and unconnected paths after pooling, although some resulting node merges are counter-intuitive to humans.The figures illustrate both structural preservation and cases where the learned pooling differs from human intuition.

6 Conclusion

The paper presents EdgePool as a hard graph pooling method based on edge contraction. It is localized and sparse, generally improves node and graph classification, and can be integrated into many GNN architectures without training or architectural changes.

  • 6 Conclusion: EdgePool is a hard pooling method for Graph Neural Networks based on edge contraction.The method pools connected nodes by contracting selected edges.
  • 6 Conclusion: Because EdgePool is localized, it is independent of non-local graph changes; because it is sparse, it remains computationally efficient on large graphs.Only pooling local to changed areas needs updating when the graph changes.
  • 6 Conclusion: Except for one pooling procedure on one dataset, EdgePool outperforms previously proposed pooling approaches.The conclusion reports this as the paper's broad comparative result.
  • 6 Conclusion: EdgePool can be integrated into many GNN architectures and usually improves both node and graph classification without training or architectural adaptations.The authors also frame EdgePool as a step toward methods operating on abstracted groups of nodes.
Loading 1905.10990v1…