Fixed Aggregation Features Can Rival GNNs

AI summary

Overview

Research area: Machine learning / graph representation learning — specifically node classification with graph neural networks and their simplification.

Technical level: Intermediate. The paper mixes an accessible methodological idea (replacing learned aggregation with fixed, precomputed aggregation) with more advanced theory (Kolmogorov–Arnold representation theorems, injectivity of multiset functions, Cantor-set constructions).

One-sentence scope: The paper proposes Fixed Aggregation Features (FAFs), a training-free preprocessing that turns graph learning into tabular learning, and shows empirically that a well-tuned MLP on FAFs rivals or beats state-of-the-art GNNs and graph transformers on 12 of 14 node-classification benchmarks.

What This Paper Is About

Graph neural networks are the default tool for node classification, and most of their complexity comes from learning how to aggregate information from a node's neighbors. This paper asks whether that learned aggregation is actually necessary. The authors propose replacing it with fixed, non-trainable reducers (mean, sum, max, min, std) applied over multiple hops, concatenating the results into a tabular feature matrix, and training only a standard downstream classifier on top.

Key Contributions

1. Theory of fixed aggregations: The authors give an explicit, lossless construction of neighborhood aggregations based on Kolmogorov–Arnold representations (specifically Theorem 2 of Schmidt-Hieber, 2021), showing that a fixed, univariate, information-preserving aggregation exists but must be discontinuous for general continuous features. They also analyze which information common reducers (sum, mean, max, min) actually preserve.

2. Method — Fixed Aggregation Features (FAFs): A training-free pipeline that recursively applies fixed reducers over neighborhoods up to K hops and concatenates the results with the original node features into a tabular feature matrix, which then feeds a standard classifier.

3. Empirical evidence: FAFs with well-tuned MLPs match or exceed classic GNNs on 12 of 14 standard node-classification benchmarks, and the results are made directly comparable to Graph Transformers and heterophily-aware models by using the hyperparameter grid of Luo et al. (2024).

4. Implications for the field: The results question the necessity of learned neighborhood aggregation on current benchmarks, motivate strong tabular baselines as standard practice, and argue for harder benchmarks that genuinely benefit from learning diverse aggregations.

Main Findings

• Competitive on 12/14 benchmarks: Across 14 benchmarks, MLPs trained on FAFs rival or outperform state-of-the-art GNNs and graph transformers on 12 tasks, often using only mean aggregation. The only exceptions are Roman Empire and Minesweeper.

• Dataset-level comparison to classic GNNs: Relative to GCN, GAT, and GraphSAGE, FAFs improve on 5 datasets, match within error or 1% on another 5, and trail on 4. The 4 trailing datasets split into two homophilic (Citeseer, Cora) and two heterophilic (Minesweeper, Roman-Empire) tasks; the homophilic tasks are close to parity.

• Where FAFs trail: On Minesweeper, FAF reaches 90.00 ± 0.39 versus GraphSAGE's 97.72 ± 0.70 and GCN's 97.48 ± 0.06. On Roman-Empire, FAF reaches 78.11 ± 0.38 versus GCN's 91.05 ± 0.15. This gap mirrors the decrease Luo et al. (2024) report when residual connections are removed, suggesting these datasets need hop-specific aggregations or combinations of consecutive hops.

• Depth mismatch: The best-performing FAFs on Minesweeper and Roman-Empire use far fewer hops (4 and 2) than the GNN baselines (15 and 10), indicating that key signal lies at longer ranges that shallower FAFs under-aggregate.

• Low hops carry the signal: Many datasets peak at k = 2 hops and then plateau or decrease. Concatenating later hops can provoke overfitting, which the authors offer as an alternative explanation for deep-GNN degradation that is not attributable to over-smoothing (since FAFs have no such variability by construction). An MLP with k = 0 performs worse than the other models.

• Single reducers often suffice: Ablations with one aggregation at a time show a single reducer often suffices, though the preferred choice varies by dataset. Mean is most frequently strongest and sometimes surpasses FAF 4 and FAF mean+std (on Amazon-Computer and Amazon-Photo). Citeseer favors sum; Amazon-Ratings favors max.

• Concatenation and nonlinearity matter: MLPs consistently outperform a single linear layer applied to the same concatenated features, and using only the last hop is worse than concatenating hops — both choices are necessary for matching GNN performance.

• Hyperparameters: All FAF variants benefit from normalization components, since aggregated features vary widely in scale across reducers and hops. FAFs typically favor larger learning rates than GNNs, while dropout levels are broadly similar.

• Interpretability via SHAP: SHAP analysis on Minesweeper with mean aggregation identifies the hop-1 mean of feature 1 (the fraction of neighbors whose local bomb count is null) as the top signal, alongside the hop-0 masked-neighbor count. Importances for Pubmed (homophilic) and Amazon-Ratings (heterophilic) are also reported.

• Theoretical limits of standard reducers: Theorem 4.1 shows that for orthogonal features, sum aggregation over multisets of bounded size is injective and any multiset function can be decomposed as a function of the sum; mean carries the same information if node degree is available. The orthogonality assumption fails for aggregated neighbor features at k ≥ 1, so from k ≥ 2 not all distributional information is preserved. Max and min only indicate whether at least one node within k hops has (or lacks) a feature, and this saturates as k grows.

• Augmentations help when concatenated: Concatenating features aggregated on a rewired graph, or splitting edges into positive/negative sets, generally yields larger gains than substituting the originals.

Methodology in Plain English

Instead of letting a GNN learn how to combine neighbor features layer by layer, the authors first compute, for every node and every hop from 1 to K, simple fixed statistics over its neighbors: the mean, sum, max, min, or standard deviation of neighbor features. These are applied recursively, so hop-2 features are aggregates of hop-1 features. All of these hop-wise statistics are then concatenated with the node's original features into one long tabular vector per node, with input dimensionality |x_v| · (1 + |R| · K) where R is the set of reducers.

Because this step has no trainable parameters, the graph problem becomes a standard tabular classification problem, and any tabular classifier can be used. In the experiments, the downstream model is a multilayer perceptron tuned with the hyperparameter grid from Luo et al. (2024), which makes the comparison against published GNN, Graph Transformer, and heterophily-aware results fair. The main configuration, FAF 4, uses the reducers {mean, sum, max, min}; other variants use mean+std, mean only, max+std, max only, sum only, and std only. Baselines are GCN, GAT, and GraphSAGE, and the best FAF variant is selected using validation results.

For the theory, the authors treat neighborhoods as multisets of feature vectors and ask what information different reducers preserve. They prove a decomposition result for one-hop sum aggregation under orthogonal features, then show the assumption breaks down at higher hops. To establish that a lossless fixed aggregation can exist at all, they invoke a Kolmogorov–Arnold construction based on ternary expansions and the Cantor set, which separates all required discontinuity into a fixed encoder while leaving the learnable readout continuous. They also use SHAP feature importances and hop/reducer ablations as interpretability tools.

Why This Matters

Impact on research: The paper argues that a large portion of GNN performance on standard benchmarks can be matched by powerful tabular predictors fed with fixed, transparent features. It therefore makes two methodological demands: include strong tabular baselines routinely, and design benchmarks that actually require learning aggregation. It also frames FAFs as a diagnostic tool — new methods' gains can be dissected by building their FAF counterpart — and reorients the expressiveness conversation from injectivity alone toward learnability and numerical stability.

Real-world applications (as grounded in the paper's datasets and framing):

• Citation and coauthor networks (Cora, Citeseer, Pubmed, Coauthor-CS, Coauthor-Physics): a lightweight, interpretable pipeline could replace heavier GNNs where deployment cost matters.
• Co-purchase graphs (Amazon-Computer, Amazon-Photo, Amazon-Ratings): product nodes with rich features, where mean aggregation is often the strongest single reducer.
• Web and wiki graphs (Wikics, Questions): reduced training compute via precomputed aggregation.
• Scientific and biological domains, which the paper cites as a driver of message-passing adoption, could benefit from decoupling representation from optimization.

Industry relevance: Precomputing aggregation and then training an MLP is more scalable than repeatedly running and backpropagating through message-passing layers. The paper reports average training runtimes in Table 3 (Appendix B) and finds FAFs are generally more efficient, particularly with a single reducer. The approach is also compatible with existing toolkits for tabular data, which handle noise, class imbalance, and feature selection, and it supports the concurrent trend of adapting tabular foundation models to graph data.

Future Directions

1. Feature and reducer engineering: Design node features that encode graph structure, require less learning, and preserve more — but ideally only relevant — information, potentially combined with partial feature learning as a new class of architectures.

2. Moving with and beyond injectivity: Since non-injective aggregation already solves most current benchmarks competitively, the authors call for a shift in focus from mere injectivity to other learning properties, a gap that applies to GNNs generally, not just FAFs.

3. New, harder benchmarks: If the goal is to showcase GNNs' ability to learn meaningful features, the field needs benchmarks that require it. The authors note recent evidence that graph models struggle to capture interactions beyond 13 hops.

4. Optimization and learnability of aggregations: An ideal aggregation would be both injective like the Cantor-set construction and statistically useful like the mean. Whether GNNs can learn such representations end-to-end without overfitting — and whether their failure to outcompete FAFs is partly a trainability problem — remains open.

Target Audience

Graph learning researchers and practitioners who benchmark GNN architectures, dataset designers interested in what makes a graph benchmark meaningful, and applied machine-learning engineers who need interpretable, compute-efficient node classification. It is also relevant to researchers working on tabular foundation models for graph data, and to anyone tracking the debate over how much of GNN performance comes from learned message passing versus strong downstream classifiers.

Authors’ abstract

Graph neural networks (GNNs) are widely believed to excel at node representation learning through trainable neighborhood aggregations. We challenge this view by introducing Fixed Aggregation Features (FAFs), a training-free approach that transforms graph learning tasks into tabular problems. This simple shift enables the use of well-established tabular methods, offering strong interpretability and the flexibility to deploy diverse classifiers. Across 14 benchmarks, well-tuned multilayer perceptrons trained on FAFs rival or outperform state-of-the-art GNNs and graph transformers on 12 tasks -- often using only mean aggregation. The only exceptions are the Roman Empire and Minesweeper datasets, which typically require unusually deep GNNs. To explain the theoretical possibility of non-trainable aggregations, we connect our findings to Kolmogorov-Arnold representations and discuss when mean aggregation can be sufficient. In conclusion, our results call for (i) richer benchmarks benefiting from learning diverse neighborhood aggregations, (ii) strong tabular baselines as standard, and (iii) employing and advancing tabular models for graph data to gain new insights into related tasks.