This paper, "Lost in Aggregation," provides a rigorous theoretical reality check for the Graph Neural Network (GNN) community. It reveals a fundamental bottleneck in how standard Message-Passing GNNs (MP-GNNs) process information, proving they are significantly less expressive than previously thought when applied to graphs of varying sizes.
TL;DR
The paper proves that MP-GNNs using standard aggregation functions (like sum, mean, or max) can only distinguish a polynomial number of graph structures, even though the number of possible graphs grows doubly-exponentially. This makes these models "infinitely weaker" than even two iterations of the classic Color Refinement (Weisfeiler-Lehman) algorithm in a practical, size-independent setting.
What Problem Does This Paper Address?
In the world of Graph Machine Learning, we often measure a model's power by its ability to distinguish non-isomorphic graphs—essentially, can the model tell two different graphs apart? Previous research suggested that MP-GNNs are as powerful as the 1-dimensional Weisfeiler-Lehman (1-WL) test, also known as Color Refinement (CR).
However, those "equivalence" results often relied on a non-uniform assumption: that you can pick a different GNN for every possible graph size. In the real world, we want a single, uniform model that works on graphs of any size. This paper tackles the "uniform" expressivity of MP-GNNs, specifically looking at how the choice of aggregation function (the part that merges neighbor information) limits the model's ability to distinguish complex structures as the number of vertices ($n$) grows.
Methods
The author introduces a framework based on Information Complexity. The core idea is to track the "bit-length" of the values produced by a GNN's layers.
- Aggregation Classes: The paper defines two broad classes of aggregation functions:
- Logarithmic: The output bit-length grows logarithmically with the number of input nodes (e.g.,
sum,mean,max). - Sublinear: A more general class where bit-length grows slower than the number of nodes.
- Complexity Analysis: By bounding the bit-length of intermediate computations (MLP outputs and aggregations), the author calculates the maximum number of distinct "equivalence classes" (unique output values) a GNN can produce for a given graph size $n$.
- Comparison to CR: The paper compares these bounds to the number of equivalence classes induced by just two iterations of the Color Refinement algorithm ($CR^{(2)}$).
Datasets
Not discussed in the paper. This is a purely theoretical work focused on mathematical proofs and complexity analysis.
Key Insights and Ideas
- The "Uniform" Bottleneck: While a GNN could theoretically distinguish many graphs if allowed to have infinite precision or size-specific parameters, a fixed, computable GNN with standard aggregators acts as a massive information bottleneck.
- Logarithmic Aggregators are Weak: Most aggregators used in practice (like
sum) are "logarithmic." The paper proves that any MP-GNN using only these can only distinguish a polynomial number of vertices or graphs. - The Doubly-Exponential Gap: There are $2^{2^{O(n)}}$ non-isomorphic graphs of size $n$. Distinguishing only a polynomial number of them ($n^k$) means the model is missing almost everything as $n$ increases.
- Infinitely Weaker than $CR^{(2)}$: Perhaps the most striking insight is that even though MP-GNNs are often compared to "full" CR, they are actually "infinitely weaker" than just two rounds of CR. As the graph size $n$ goes to infinity, the fraction of $CR^{(2)}$-distinguishable structures that a standard GNN can catch drops to zero.
Key Results
- Theorem 3.7: For any MP-GNN with logarithmic aggregations, the number of induced equivalence classes $N_{dp}(n)$ is $poly(n)$. For sublinear aggregations, it is sub-exponential ($2^{o(n)}$).
- Corollary 3.9: Formally establishes the "infinitely weaker" claim. Specifically: $$\lim_{n\to\infty} \frac{N_{dp}(n)}{CR^{(2)}_{dp}(n)} = 0$$ This means that as graphs get larger, the gap between what a simple local algorithm (CR) can see and what a GNN can see becomes an unbridgeable chasm.
Limitations and Future Work
- Softmax and Attention: The paper does not fully analyze "softmax" aggregation (common in GATs and Graph Transformers). Because softmax involves exponentiation, it might have higher output-size complexity (potentially linear or exponential), which could bypass some of these limits.
- Non-ReLU Activations: The proofs focus on ReLU-activated, rationally-weighted MLPs. Functions like
sigmoidortanhinvolve exponentiation and require further study to see if they offer more "distinguishing bits." - High-Precision Aggregators: The author notes that one could design an aggregator that packs all CR information into a single rational number, but this would likely lead to astronomical runtime complexities or require infinite precision, making it impractical for real-world hardware.
- Expressivity vs. Distinguishing Power: While the paper focuses on distinguishing graphs, the author notes that if a model can't even distinguish two inputs, it certainly can't approximate a function that treats them differently. This sets a hard upper bound on what GNNs can learn to compute.
Summary updated