Technical Summary: Fixed Aggregation Features Can Rival GNNs

Problem Statement

Graph Neural Networks (GNNs) have become the standard for learning from graph-structured data, particularly for node classification. These models typically rely on the message-passing paradigm, where node representations are updated through multiple layers of trainable neighborhood aggregations (e.g., learned linear combinations, attention mechanisms). While effective, this approach introduces high model complexity, challenges in interpretability, and significant computational costs.

Recent evidence suggests that classic GNNs (GCN, GAT, GraphSAGE) remain competitive with state-of-the-art Graph Transformers and heterophily-aware models when equipped with rigorous hyperparameter tuning. This raises a fundamental question: Is the high complexity of learning aggregation functions truly necessary? Specifically, how relevant is the learning of aggregation itself compared to the downstream classification task?

Methodology: Fixed Aggregation Features (FAFs)

The authors introduce Fixed Aggregation Features (FAFs), a training-free approach that transforms graph learning tasks into standard tabular problems. The core idea is to decouple representation learning from optimization by using fixed, non-trainable aggregation operators.

The FAF Pipeline

1. Fixed Aggregation: For a given node $v$, the method recursively computes features from its $k$-hop neighborhoods using a set of fixed reducers $\mathcal{R}$ (e.g., mean, sum, max, min, std).
   • $h^{(0,r)}_v = x_v$ (original features)
   • $h^{(k,r)}_v = r(\{h^{(k-1,r)}_u : u \in \mathcal{N}(v)\})$
2. Feature Concatenation: The features from all hops ($k \in \{1, \dots, K\}$) and all reducers ($r \in \mathcal{R}$) are concatenated with the original node features to form a high-dimensional tabular vector $z_v$.
   • $z_v = x_v \oplus \bigoplus_{r \in \mathcal{R}} \bigoplus_{k=1}^K h^{(k,r)}_v$
3. Downstream Classification: A standard, well-tuned Multi-Layer Perceptron (MLP) is trained on these fixed features $z_v$. No gradients are backpropagated through the aggregation steps; the aggregation is a pre-processing step.

Theoretical Foundation

The paper connects FAFs to the Kolmogorov–Arnold representation theorem, which states that any multivariate continuous function can be represented as a composition of univariate functions.

• Theoretical Possibility: The authors construct a specific, fixed, injective aggregation function $\Phi$ (based on ternary expansions and the Cantor set) that theoretically allows for lossless encoding of neighborhood multisets. This implies that, in theory, no information needs to be learned during aggregation to preserve expressivity.
• Practical Reality: While $\Phi$ is theoretically lossless, it is numerically brittle and produces "rough" embeddings unsuitable for standard classifiers. In contrast, simple, non-injective reducers (like mean and sum) are empirically more amenable to optimization. The authors argue that for most benchmarks, the relevant signal is concentrated in low-hop neighborhoods (1–2 hops), where simple aggregations preserve sufficient information.

Key Contributions

1. Theoretical Insight: The paper establishes that lossless neighborhood aggregation is theoretically possible via fixed, injective functions derived from Kolmogorov–Arnold representations. However, it highlights a crucial gap between expressiveness and learnability: simple, non-injective reducers often yield better practical performance because they produce smoother embeddings that downstream classifiers can optimize more effectively.
2. Methodological Proposal: The introduction of FAFs, which converts graph data into a tabular format by stacking fixed multi-hop aggregations. This provides an interpretable framework to study the interplay between graph structure, features, and the task without architectural bias.
3. Empirical Evidence: Extensive experiments on 14 standard node-classification benchmarks show that FAFs combined with well-tuned MLPs rival or outperform state-of-the-art GNNs and Graph Transformers on 12 out of 14 tasks.
   • Performance: FAFs match or exceed classic GNNs (GCN, GAT, SAGE) and complex architectures on citation networks (Cora, Citeseer, PubMed), co-authorship graphs, and Amazon product graphs.
   • Exceptions: FAFs underperform only on the Roman Empire and Minesweeper datasets. The authors attribute this to these datasets requiring long-range dependencies or specific linear residual connections that standard FAFs (using 2–4 hops) do not capture, aligning with findings that these tasks benefit from deep GNNs with parameterized residuals.
4. Implications for Benchmarking: The results challenge the necessity of learned aggregation on current standard benchmarks. The authors argue that many datasets can be solved by powerful tabular predictors fed with fixed, transparent features, suggesting that current benchmarks may not adequately test the ability of models to learn complex aggregation dynamics.

Results and Analysis

• Ablation Studies:
  • Classifier Complexity: A well-tuned MLP significantly outperforms a single linear layer when applied to FAF features, indicating that nonlinearity and capacity are crucial for leveraging multi-hop information.
  • Hop Concatenation: Concatenating features from all hops yields better performance than using only the last hop, confirming that information is lost during repeated aggregations and that early hops (0–2) contain the most predictive signal.
  • Reducer Choice: While concatenating multiple reducers (e.g., mean, sum, max, min) is generally beneficial, a single reducer (often mean) frequently suffices and sometimes outperforms complex combinations, likely due to reduced overfitting in high-dimensional spaces.
• Interpretability: By treating the problem as tabular, the authors utilize SHAP values to analyze feature importance. For instance, on the Minesweeper dataset, they identify that the hop-1 mean of specific features is the primary signal, clarifying exactly where the model succeeds or fails.
• Efficiency: Precomputing aggregations and training an MLP is generally more scalable and efficient than training deep GNNs, although input dimensionality increases with the number of hops and reducers.

Significance and Claims

The paper posits that the field of graph learning may be over-reliant on complex, trainable aggregation mechanisms for tasks where simple, fixed statistics suffice. The authors claim:

1. Strong Baselines: FAFs should serve as a mandatory, strong baseline for future graph learning research. If a new GNN cannot outperform a well-tuned FAF, its added complexity may not be justified.
2. Re-evaluation of Benchmarks: Current standard benchmarks (e.g., Cora, Citeseer) may not genuinely require learned aggregation, as the predictive signal is often concentrated in low-order neighborhoods. The authors call for "richer benchmarks" that specifically test long-range dependencies and complex inter-hop dynamics.
3. Optimization vs. Expressivity: The success of FAFs suggests that optimizability and trainability are as critical as theoretical expressivity. Complex GNNs may struggle to learn useful aggregations due to optimization difficulties (e.g., vanishing gradients, over-smoothing) rather than a lack of theoretical capacity.
4. Tabular Perspective: Converting graph problems to tabular ones allows researchers to leverage the mature toolbox of tabular learning (feature selection, interpretability, handling class imbalance) and isolate the contribution of graph structure from optimization artifacts.

In conclusion, the authors advocate for a shift in focus: rather than assuming that extra parameters or higher expressivity automatically extract more relevant signal, the community should prioritize simpler, more interpretable models and design benchmarks that genuinely necessitate the learning of complex aggregation functions.