Graph Neural Networks (GNNs) operate primarily through message passing, where nodes update their states by aggregating features from their immediate neighbors. Because graphs are unordered structures, a node's neighborhood is mathematically defined as a multiset—a set that allows for duplicate elements.
The fundamental limitation of standard message passing lies in how these multisets are compressed into a single vector. If the aggregation function maps two different multisets to the same output vector, the network becomes structurally blind. To prevent this loss of information, the aggregation function must be injective, ensuring that every unique neighborhood configuration maps to a completely unique representation.
The Information Bottleneck of Standard Aggregators
To understand why injectivity matters, consider how standard reduction operators handle a simple neighborhood. Imagine a target node trying to distinguish between two different local environments: one where it has two neighbors both possessing feature $A$ (the multiset $\{A, A\}$), and another where it has only a single neighbor with feature $A$ (the multiset $\{A\}$).
If the GNN uses max-pooling, it simply identifies the presence of features. For both multisets, the maximum value is $A$, meaning max-pooling collapses $\{A, A\}$ and $\{A\}$ into the exact same representation. It completely loses track of count and structural density.
If the GNN uses mean-pooling, it captures the proportion or distribution of features. The average of $\{A, A\}$ is $A$, and the average of $\{A\}$ is also $A$. Mean-pooling fails to distinguish between graphs of different sizes or node counts if their feature proportions are identical.
This architectural bottleneck severely limits a model's expressive power. In a foundational paper, Keyulu Xu et al. proved in How Powerful are Graph Neural Networks? that standard message-passing GNNs are at most as powerful as the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test. Crucially, they demonstrated that a GNN can only match the discriminative capacity of the 1-WL test if its neighborhood aggregation functions are strictly injective over multisets. As surveyed by Bingxu Zhang et al. in The Expressive Power of Graph Neural Networks: A Survey, injectivity is the core mathematical prerequisite for preserving topological fingerprints during the message-passing process.
Designing Injective Operators: Summation and MLPs
How do we construct an aggregation function that is provably injective over multisets? The simplest standard operator capable of this is summation. Unlike mean or max, a sum-based aggregator naturally scales with both the multiplicity and the cardinality of the elements. The sum of $\{A, A\}$ is $2A$, while the sum of $\{A\}$ is $A$, successfully keeping the two structures distinct.
This property makes sum-pooling highly effective for preserving structural signals. For instance, Yeping Hu et al. leverage sum-based aggregators in Scenario-Transferable Semantic Graph Reasoning for Interaction-Aware Probabilistic Prediction to prevent distinct multi-agent configurations from collapsing into identical representations, enabling zero-shot transfer across driving environments. Similarly, Siddhant Doshi et al. demonstrate in Graph Neural Networks With Parallel Neighborhood Aggregations for Graph Classification that summation and concatenation operators preserve structural fingerprints during graph readout where mean and max functions fail, especially when distinguishing between regular graphs of different sizes.
To handle complex, parameterized transformations of node features, researchers combine multi-layer perceptrons (MLPs) with summation. According to the universal approximation theorem for multisets, any injective function over a countable multiset can be modeled by passing the features through an MLP, summing the results, and then applying another post-aggregation MLP.
Zihan Wang et al. utilize this framework in Robust Embedding with Multi-Level Structures for Link Prediction, showing that MLP-based aggregation preserves cardinality and distribution details, making the network robust against noise and data sparsity. This theoretical requirement is also central to the work of Meng Liu et al. in Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm, where MLP-and-sum architectures are deployed to maintain strict injectivity while incorporating the communication between neighboring edges.
The Continuous Feature Challenge: Multi-Aggregator Expressiveness
While summation guarantees injectivity when dealing with countable or discrete feature spaces, real-world graphs often contain continuous node attributes. In a continuous domain, a single sum aggregator is no longer mathematically sufficient to ensure injectivity across varying neighborhood sizes.
To solve this problem, Gabriele Corso et al. introduced Principal Neighbourhood Aggregation (PNA) in Principal Neighbourhood Aggregation for Graph Nets. They proved that to fully characterize a neighborhood multiset of size $n$ containing continuous features, a model requires at least $n$ independent, parallel aggregators. By combining multiple statistical aggregators (such as mean, sum, variance, and skewness) scaled by neighborhood degree, the network can uniquely identify continuous distributions without losing structural information.
This multi-aggregator strategy is highly effective for scaling to massive industrial applications. For example, Sheng Tian et al. develop a parallel framework in GraphRPM: Risk Pattern Mining on Industrial Large Attributed Graphs that combines sum, max, min, and squeeze aggregators. This combination creates an injective mapping for subgraphs, preventing complex fraud and risk patterns from being erroneously grouped into identical representations.
Incorporating Structural Context
Injectivity can also be explicitly guided by incorporating graph topology directly into the aggregation mechanism. Rather than treating all neighbors uniformly, models can condition their functions on structural properties like node degrees or higher-order subgraphs.
In DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification, Jun Wu et al. propose a degree-specific hashing and bucketing mechanism. By grouping node representations into distinct buckets based on their degrees before concatenation, the architecture ensures that unique neighborhood configurations map to unique vectors, aligning its representational power directly with the WL isomorphism test.
When moving beyond immediate neighbors to higher-order structures, Xuexin Chen et al. introduce the Motif Graph Neural Network. This approach explicitly models small subgraphs (motifs) and uses injective combinations to merge their features, ensuring that complex topological signals do not collide or vanish during the learning process.
The Role of Dimensions and Activation Functions
A common assumption was that maintaining injectivity across growing graph sizes required the dimensionality of hidden feature vectors to scale continuously. However, recent theoretical insights show that the choice of activation function can bypass this requirement.
César Bravo et al. prove in On dimensionality of feature vectors in MPNNs that a single feature dimension ($d=1$) is theoretically sufficient for any graph size, provided the network uses a non-polynomial analytic activation function (such as sigmoid or tanh). Because graph aggregations involve integer-based multisets, these specific activation functions can maintain linear independence over the rational numbers, ensuring uniqueness across different structural configurations without expanding vector sizes.
The deeper role of activations is further explored by Sammy Khalife et al. in On the power of graph neural networks and the role of the activation function, demonstrating that the activation function dictates the model's underlying representational logic rather than just its optimization behavior. This is mathematically formalized by Timon Barlag et al. in Graph Neural Networks and Arithmetic Circuits, who establish an exact correspondence between GNNs and arithmetic circuits, proving that standard activations like ReLU and Sigmoid are countably injective and preserve the theoretical limits of the architecture in practical applications.
To explicitly combat the rank collapse problem where node representations become uniform, Andreas Roth et al. introduce Localized MIMO Graph Convolutions in What Can We Learn From MIMO Graph Convolutions?. Their framework provides theoretical guarantees for multiset injectivity and linear independence, ensuring that distinct node and graph features remain separable throughout deep architectures.
Extending Injectivity to Global Graph Readout
The necessity of injective mapping extends from local neighborhood aggregation to the global pooling layers that summarize an entire graph into a single vector for graph-level classification. If the global readout layer is non-injective, two entirely different graphs with identical isolated node pools could be mapped to the same graph embedding.
Jinheon Baek et al. address this in Accurate Learning of Graph Representations with Graph Multiset Pooling by framing global graph pooling as a multiset encoding problem. By utilizing a multi-head attention mechanism that explicitly accounts for the frequency of identical node feature sets, their Graph Multiset Transformer maintains permutation invariance while ensuring an injective mapping that preserves global structural complexity.
Ultimately, this line of work culminates in a broader understanding of graph expressiveness. As shown by Rickard Brüel Gabrielsson in Universal Function Approximation on Graphs, universal function approximation on graphs is fundamentally tied to using functions that are injective with respect to graph isomorphism classes. By ensuring injectivity at both the local neighborhood level and the global readout level, GNNs can bypass the discriminative limitations of traditional message-passing schemes and map distinct graph structures to entirely unique vector spaces.
Key Foundational Work
How Powerful are Graph Neural Networks? (2019) — contributed 3 concept elements to this direction.
Robust Embedding with Multi-Level Structures for Link Prediction (2019) — contributed 2 concept elements to this direction.
DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification (2019) — contributed 2 concept elements to this direction.