Accurate Learning of Graph Representations with Graph Multiset Pooling

Jinheon Baek, Minki Kang, Sung Ju Hwang

The Bottleneck in Graph Neural Networks

While Graph Neural Networks (GNNs) have proven exceptionally capable of learning node-level features, they often stumble at the "pooling" stage. Pooling is the critical process of condensing a whole set of node embeddings into a single, compact vector that represents the entire graph.

Historically, existing pooling methods have fallen into three main categories, each carrying significant flaws:

  1. Simple Aggregation (Sum/Mean): These methods treat all nodes as equally important. By ignoring structural dependencies, they lose the "shape" and topology of the graph.
  2. Node Drop (Top-K): These approaches discard nodes with low scores. While efficient, this aggressive pruning can lead to severe information loss.
  3. Node Clustering (DiffPool): These group nodes into clusters but typically rely on dense assignment matrices. This results in $O(n^2)$ memory complexity, rendering them unusable for large-scale graphs.
Comparison of existing graph pooling methods versus the proposed Graph Multiset Encoding approach.

To capture a graph's true representation, a pooling function must be both injective (mapping different graphs to distinctly different embeddings) and permutation invariant. The ideal pooling method should be as theoretically powerful as the Weisfeiler-Lehman (WL) graph isomorphism test, yet computationally efficient enough for real-world applications.

Introducing the Graph Multiset Transformer (GMT)

To address these limitations, researchers have introduced the Graph Multiset Transformer (GMT). The core innovation of GMT is reframing graph pooling as a multiset encoding problem, where the graph's structural information acts as crucial auxiliary data.

Graphs frequently contain nodes with identical features. Treating pooling as a multiset problem—which mathematically allows for repeating elements—is a more rigorous and accurate way to handle graph data than simple set encoding.

How GMT Works

The GMT architecture relies on a few key components to compress graph data without losing structural integrity:

  • Graph Multi-head Attention (GMH): In standard attention mechanisms, keys and values are simple linear projections of the input. GMH, however, uses GNNs to generate these keys and values. This effectively "bakes" the local graph topology directly into the attention mechanism, ensuring the model looks at how nodes are positioned within the graph, not just their feature similarity.
  • Graph Multiset Pooling (GMPool): This layer introduces a set of learnable Seed Vectors that act as queries. These queries attend to the node features, condensing $n$ original nodes into $k$ representative "cluster" nodes. The attention weights act as a soft assignment of nodes to these structural prototypes.
  • Self-Attention (SelfAtt): After the graph is condensed, a self-attention layer allows the $k$ representative nodes to interact with one another, capturing long-range dependencies across the graph.
The GMPool architecture, showing how learnable Seed Vectors attend to the graph structure to compress node space.

The standard pipeline follows a logical sequence: Encoder (GNN) -> GMPool (compresses to k nodes) -> SelfAtt -> GMPool (compresses to 1 node).

Theoretically, GMT is proven to be as powerful as the WL test. Crucially, it maintains a space complexity of $O(n)$, making it vastly more scalable than dense clustering methods.

Key Results and Performance

The authors evaluated GMT across a rigorous suite of tasks, including graph classification, reconstruction, and generation.

  • State-of-the-Art Classification: Across 10 benchmark datasets—spanning biochemical networks (like PROTEINS and MUTAG) and social networks (like IMDB-B)—GMT matched or outperformed state-of-the-art pooling methods like DiffPool and StructPool, achieving a perfect 10/10 significance score in these domains.
  • High Efficiency: GMT proved vastly more efficient than clustering-based baselines. In memory stress tests, GMT successfully handled graphs with over 10,000 nodes, whereas methods like DiffPool crashed due to their quadratic memory requirements.
  • Superior Reconstruction: Because GMT compresses nodes via attention rather than dropping them entirely, it retains significantly more information. In synthetic tests (Ring/Grid), GMT achieved near-perfect reconstruction (MSE $\approx 0.0001$), while node-drop methods failed to capture the basic shape of the graphs.
  • Stable Generation: When GMT was swapped into MolGAN for molecule generation, it led to much more stable training dynamics and a higher percentage of valid molecules generated in the early stages of training.

Limitations and Future Directions

While GMT represents a major step forward, it is not without limitations.

First, while GMT excels at reconstructing node features, reconstructing the exact adjacency matrix after pooling remains a challenge, yielding higher error rates than feature reconstruction. Second, the authors note that developing more sophisticated ways to adjust adjacency information after compression (rather than relying on an identity matrix for coarsened adjacency) is a promising area for future research. Finally, the model exhibits some hyperparameter sensitivity; the optimal number of representative nodes ($k$) and attention heads often requires task-specific tuning.

Overall, the Graph Multiset Transformer offers a highly scalable, theoretically grounded, and performant solution to the graph pooling bottleneck, paving the way for more accurate graph representation learning.

Summary updated

Abstract

Graph neural networks have been widely used on modeling graph data, achieving impressive results on node classification and link prediction tasks. Yet, obtaining an accurate representation for a graph further requires a pooling function that maps a set of node representations into a compact form. A simple sum or average over all node representations considers all node features equally without consideration of their task relevance, and any structural dependencies among them. Recently proposed hierarchical graph pooling methods, on the other hand, may yield the same representation for two different graphs that are distinguished by the Weisfeiler-Lehman test, as they suboptimally preserve information from the node features. To tackle these limitations of existing graph pooling methods, we first formulate the graph pooling problem as a multiset encoding problem with auxiliary information about the graph structure, and propose a Graph Multiset Transformer (GMT) which is a multi-head attention based global pooling layer that captures the interaction between nodes according to their structural dependencies. We show that GMT satisfies both injectiveness and permutation invariance, such that it is at most as powerful as the Weisfeiler-Lehman graph isomorphism test. Moreover, our methods can be easily extended to the previous node clustering approaches for hierarchical graph pooling. Our experimental results show that GMT significantly outperforms state-of-the-art graph pooling methods on graph classification benchmarks with high memory and time efficiency, and obtains even larger performance gain on graph reconstruction and generation tasks.
BibTeX
@inproceedings{baek2021accurate,
  author = {Jinheon Baek and Minki Kang and Sung Ju Hwang},
  title = {{Accurate Learning of Graph Representations with Graph Multiset Pooling}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=yWlY_kAkwnb},
}
Figure