# SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization

arXiv: https://arxiv.org/abs/2207.09179 · HTML: https://mlsanity.com/paper/2207.09179/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 42 references that are in the map.
- First posted on arXiv 19 Jul 2022.

## Builds on (most cited first, 27 of 27)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Graph-Bert: Only Attention is Needed for Learning Graph Representations](https://mlsanity.com/paper/2001.05140/) (2020)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Attention-based Graph Neural Network for Semi-supervised Learning](https://mlsanity.com/paper/1803.03735/) (2018)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization](https://mlsanity.com/paper/2110.14363/) (2021)
- [Spiking Graph Convolutional Networks](https://mlsanity.com/paper/2205.02767/) (2022)
- [Approximate Graph Propagation](https://mlsanity.com/paper/2106.03058/) (2021)
- [DDGK: Learning Graph Representations for Deep Divergence Graph Kernels](https://mlsanity.com/paper/1904.09671/) (2019)
- [Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push](https://mlsanity.com/paper/2101.03652/) (2021)
- [Efficient Algorithms for Approximate Single-Source Personalized PageRank Queries](https://mlsanity.com/paper/1908.10583/) (2019)

## Built on by (most cited first, 19 of 19)

- [FedGTA: Topology-aware Averaging for Federated Graph Learning](https://mlsanity.com/paper/2401.11755/) (2024)
- [Graph-based Approaches and Functionalities in Retrieval-Augmented Generation: A Comprehensive Survey](https://mlsanity.com/paper/2504.10499/) (2025)
- [Rethinking Node-wise Propagation for Large-scale Graph Learning](https://mlsanity.com/paper/2402.06128/) (2024)
- [SIGMA: An Efficient Heterophilous Graph Neural Network with Fast Global Aggregation](https://mlsanity.com/paper/2305.09958/) (2023)
- [A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness](https://mlsanity.com/paper/2406.09675/) (2024)
- [Learning Graph Neural Networks using Exact Compression](https://mlsanity.com/paper/2304.14793/) (2023)
- [MoSE: Unveiling Structural Patterns in Graphs via Mixture of Subgraph Experts](https://mlsanity.com/paper/2509.09337/) (2025)
- [Unifews: You Need Fewer Operations for Efficient Graph Neural Networks](https://mlsanity.com/paper/2403.13268/) (2024)
- [ScaDyG:A New Paradigm for Large-scale Dynamic Graph Learning](https://mlsanity.com/paper/2501.16002/) (2025)
- [Graph Learning at Scale: Characterizing and Optimizing Pre-Propagation GNNs](https://mlsanity.com/paper/2504.13266/) (2025)
- [ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion](https://mlsanity.com/paper/2504.15920/) (2025)
- [Can Large Language Models Act as Ensembler for Multi-GNNs?](https://mlsanity.com/paper/2410.16822/) (2024)
- [When Deepfake Detection Meets Graph Neural Network:a Unified and Lightweight Learning Framework](https://mlsanity.com/paper/2508.05526/) (2025)
- [OpenGLT: A Comprehensive Benchmark of Graph Neural Networks for Graph-Level Tasks](https://mlsanity.com/paper/2501.00773/) (2025)
- [Self-Supervised Graph Learning via Spectral Bootstrapping and Laplacian-Based Augmentations](https://mlsanity.com/paper/2506.20362/) (2025)
- [ATLAS: Adaptive Topology-based Learning at Scale for Homophilic and Heterophilic Graphs](https://mlsanity.com/paper/2512.14908/) (2025)
- [Coden: Efficient Temporal Graph Neural Networks for Continuous Prediction](https://mlsanity.com/paper/2602.12613/) (2026)
- [Revisiting Pre-Propagation GNNs: Robust Diffusion Operators and Hidden-State Re-Propagation](https://mlsanity.com/paper/2605.25111/) (2026)
- [FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism](https://mlsanity.com/paper/2606.22180/) (2026)

## Abstract (arXiv)

Recent advances in data processing have stimulated the demand for learning graphs of very large scales. Graph Neural Networks (GNNs), being an emerging and powerful approach in solving graph learning tasks, are known to be difficult to scale up. Most scalable models apply node-based techniques in simplifying the expensive graph message-passing propagation procedure of GNN. However, we find such acceleration insufficient when applied to million- or even billion-scale graphs. In this work, we propose SCARA, a scalable GNN with feature-oriented optimization for graph computation. SCARA efficiently computes graph embedding from node features, and further selects and reuses feature computation results to reduce overhead. Theoretical analysis indicates that our model achieves sub-linear time complexity with a guaranteed precision in propagation process as well as GNN training and inference. We conduct extensive experiments on various datasets to evaluate the efficacy and efficiency of SCARA. Performance comparison with baselines shows that SCARA can reach up to 100x graph propagation acceleration than current state-of-the-art methods with fast convergence and comparable accuracy. Most notably, it is efficient to process precomputation on the largest available billion-scale GNN dataset Papers100M (111M nodes, 1.6B edges) in 100 seconds.