Abstract
Graph neural networks (GNNs) have achieved state-of-the-art accuracy for graph node classification. However, GNNs are difficult to scale to large graphs, frequently encountering out-of-memory (OOM) errors on even moderate-sized datasets. Recent works have sought to address this problem using a two-stage approach, which first aggregates data along graph edges and then trains a classifier without using additional graph information. While these methods are orders of magnitude faster than GNNs, they often achieve lower classification accuracy. We propose a novel two-stage algorithm, SAS, based on a simple but effective observation: we should first train a classifier and then aggregate, rather than the other way around. We demonstrate that SAS is faster and handles larger graphs than existing two-stage algorithms while achieving comparable or higher accuracy than popular GNNs. We also provide a theoretical basis for this improved accuracy using a synthetic nonlinear dataset where pre-classification aggregation actually decreases performance.
Introduction
Node classification—predicting labels for nodes based on their features and local graph structure—is a cornerstone of graph machine learning. While Graph Neural Networks (GNNs) excel at this task, they face a notorious "memory wall." As graphs grow to millions of nodes and edges, standard GNNs often crash due to the exponential computational growth required to compute a single node's representation from its neighborhood.
To circumvent this, researchers have developed "simplified" GNNs, such as Simple Graph Convolution (SGC). These models typically aggregate features across the graph in a preprocessing step and then train a linear model. While efficient, this "aggregate-then-classify" pipeline often sacrifices accuracy. In this paper, we introduce SAS (Simple, Accurate, and Scalable), an algorithm that flips this script to achieve superior performance and scalability.
The Problem with Pre-Aggregation
The fundamental flaw in existing simplified GNNs lies in the order of operations. Aggregating raw features before classification can "smear" the data. In scenarios where the underlying patterns are non-linear, averaging the features of neighbors from different classes can create a "gray mush" of data points that no classifier can effectively untangle. This is particularly evident in synthetic datasets representing XOR functions, where spatial mixing makes feature-level smoothing counterproductive.
The SAS Methodology
SAS decouples feature transformation and graph aggregation into two distinct, sequential stages:
- Stage 1: Classify First. We train a standard Multi-Layer Perceptron (MLP) using only the node features, completely ignoring the graph structure. This stage is highly efficient and can be trained using standard mini-batch gradient descent, avoiding the memory overhead of graph-based training.
- Stage 2: Aggregate Later. Once the MLP is trained, we use it to generate "base" probability predictions for every node. We then perform $K$ rounds of label aggregation (smoothing), where each node updates its prediction by averaging the predictions of its neighbors.
This "classify-then-aggregate" approach ensures that the non-linear power of the MLP is applied to the raw signal before the graph structure is used to refine the results. By propagating labels (which are low-dimensional) rather than features (which are high-dimensional), SAS significantly reduces the computational and memory footprint.
Experimental Evaluation
We evaluated SAS across a diverse range of benchmarks, from small citation networks to massive industrial-scale graphs:
- Small/Medium Networks: Cora, Citeseer, PubMed, Flickr, and
ogbn-arxiv. - Large-Scale Graphs: Reddit and
ogbn-products. The latter features over 2.4 million nodes and 61 million edges.
Key Results
- Accuracy: SAS consistently outperformed other simplified models. On the
ogbn-productsdataset, SAS achieved 75.9% accuracy, a substantial improvement over SGC’s 65.3%. - Scalability: While complex models like Graph Attention Networks (GAT) and APPNP frequently hit OOM errors on large datasets like Reddit, SAS handled them with ease.
- Speed: SAS is approximately 10x faster than sampling-based methods like GraphSAGE and GraphSAINT. Because the aggregation step does not require retraining the model, hyperparameter tuning for the number of hops ($K$) is nearly instantaneous.
Discussion and Insights
The success of SAS stems from its ability to map points into a "label space" before smoothing. In this space, smoothing acts as a correction mechanism rather than a blurring mechanism. Furthermore, the decoupling of learning (MLP) from the graph structure (Aggregation) removes the need for complex neighbor sampling techniques, making the algorithm easier to implement and tune.
Limitations and Future Work
SAS relies heavily on the quality of the initial MLP. If node features are extremely noisy, the base predictions may be too poor for aggregation to recover. Future research will explore how specific graph topologies and spectral properties relate to the optimal architecture of the initial classifier, as well as the impact of various mini-batching strategies on final smoothed accuracy.
Conclusion
SAS provides a simple yet powerful alternative to traditional GNNs for large-scale node classification. By reversing the standard pipeline to classify before aggregating, SAS overcomes the accuracy limitations of simplified GNNs while maintaining—and often exceeding—their scalability and speed advantages.
Summary updated