Injective Aggregation for Expressive Graph Neural Networks

This direction is merged into another direction: 1-WL expressivity limit, injective neighborhood aggregation. Its last version stays readable and citable here.

Version 1 of 126 papers35 conceptsfrozen 2026-10-04

Graph Neural Networks (GNNs) are often described as "message-passing" systems where nodes update their features by looking at their neighbors. While this intuition is helpful for implementation, it masks a fundamental mathematical limitation: if the function used to combine those messages is not "injective," the network becomes blind to the actual structure of the graph.

Recent theoretical work has shifted the focus from merely passing messages to ensuring that the aggregation process is mathematically powerful enough to distinguish between different local neighborhoods.

The Failure of Mean and Max Pooling

To understand the problem, consider a node's neighborhood as a multiset—a collection of features where the number of times a feature appears (its cardinality) matters. Standard GNNs typically use one of three aggregators: Mean, Max, or Sum.

As Keyulu Xu, Jure Leskovec, and colleagues demonstrated in How Powerful are Graph Neural Networks?, mean and max pooling are inherently "lossy." Mean pooling captures the distribution of neighbor features but loses track of the exact count. Max pooling identifies the most prominent features but ignores everything else.

If an aggregation function is not injective—meaning it doesn't map distinct multisets to unique outputs—the GNN will collapse different graph structures into the same representation. For example, a mean-pooling GNN might see a neighborhood of two "Type A" nodes as identical to a neighborhood of four "Type A" nodes. This "structural blindness" prevents the model from solving tasks that require counting or identifying specific configurations.

The Weisfeiler-Lehman Benchmark

The gold standard for measuring this discriminative power is the Weisfeiler-Lehman (WL) graph isomorphism test. The WL test is a classical algorithm that iteratively colors nodes based on their neighborhood structures to determine if two graphs are identical.

The breakthrough in How Powerful are Graph Neural Networks? was proving that a GNN is at most as powerful as the 1-WL test. To reach this maximum theoretical limit, the GNN's aggregation and update functions must be injective. This led to the creation of the Graph Isomorphism Network (GIN), which uses sum-pooling followed by a Multi-Layer Perceptron (MLP). Because an MLP can approximate any continuous function, it can learn to map the sum of neighbor features into a unique space, preserving the multiset's identity.

Building Injective Architectures

Following the GIN framework, researchers have developed various ways to ensure injectivity across different domains:

  • Degree-Awareness: Jun Wu and Jingrui He proposed DEMO-Net, which explicitly incorporates node degrees into the convolution. By making the aggregation degree-specific, the model ensures that nodes with different numbers of neighbors are never confused, even if their neighbor features are similar.
  • Path-Based Aggregation: Standard message passing only looks at immediate neighbors. Caterina Graziani and Franco Scarselli extended the injectivity requirement to paths in The Expressive Power of Path-Based Graph Neural Networks. By using injective sequence encoders for paths and injective aggregators for sets of paths, these models can distinguish complex structures (like cycles) that standard 1-WL GNNs cannot.
  • Multi-Level Structures: In Robust Embedding with Multi-Level Structures for Link Prediction, Zihan Wang and Zhaochun Ren use injective MLP-based aggregation combined with graph coarsening. This ensures that structural information is preserved not just at the node level, but as the graph is simplified into hierarchical clusters.

Beyond Graph Classification

The need for injective mapping extends beyond simple graph classification. It is a prerequisite for any task where the "uniqueness" of an input must be preserved:

  • Neural Architecture Search (NAS): In arch2vec, Shen Yan and Mi Zhang use injective GNNs to encode neural architectures. Without injectivity, two different computational graphs might be mapped to the same point in latent space, making it impossible for the search algorithm to distinguish between a high-performing and a low-performing model.
  • Multi-Agent Reinforcement Learning: When multiple agents communicate, their messages form a multiset. Diyi Hu and Bhaskar Krishnamachari show in LAUREL that using sum-based MLP encoders allows agents to distinguish between different combinations of incoming signals, which is critical for coordination in noisy environments.

Summary of Intuition

The core lesson of this research direction is that aggregation is a bottleneck. If you use a non-injective function like mean or max, you are throwing away structural information that can never be recovered by later layers. By using injective functions—typically through the combination of summation and MLPs—GNNs can theoretically match the power of the Weisfeiler-Lehman test, allowing them to "see" the graph's topology with perfect clarity.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_injective_aggregation_for_expressive_gra_88d1f2f8,
  title = {Injective Aggregation for Expressive Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/injective-aggregation-for-expressive-graph-neural-networks/rdr_88d1f2f80e524ecc88f86b54715ed535},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_injective_aggregation_for_expressive_gra_88d1f2f8_v1,
  title = {Injective Aggregation for Expressive Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/injective-aggregation-for-expressive-graph-neural-networks/rdr_88d1f2f80e524ecc88f86b54715ed535/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}