# Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 68 references that are in the map.
- First posted on arXiv 28 Feb 2022.

## Builds on (most cited first, 30 of 40)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [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)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks](https://mlsanity.com/paper/1909.01315/) (2019)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [AliGraph: A Comprehensive Graph Neural Network Platform](https://mlsanity.com/paper/1902.08730/) (2019)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [Graph Meta Learning via Local Subgraphs](https://mlsanity.com/paper/2006.07889/) (2020)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [Dorylus: Affordable, Scalable, and Accurate GNN Training with Distributed CPU Servers and Serverless Threads](https://mlsanity.com/paper/2105.11118/) (2021)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)

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

- [Temporal Graph Benchmark for Machine Learning on Temporal Graphs](https://mlsanity.com/paper/2307.01026/) (2023)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [Neighborhood-aware Scalable Temporal Network Representation Learning](https://mlsanity.com/paper/2209.01084/) (2022)
- [Linkless Link Prediction via Relational Distillation](https://mlsanity.com/paper/2210.05801/) (2022)
- [Revisiting Link Prediction: A Data Perspective](https://mlsanity.com/paper/2310.00793/) (2023)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Pure Message Passing Can Estimate Common Neighbor for Link Prediction](https://mlsanity.com/paper/2309.00976/) (2023)
- [Learning Long Range Dependencies on Graphs via Random Walks](https://mlsanity.com/paper/2406.03386/) (2024)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [Link Prediction with Non-Contrastive Learning](https://mlsanity.com/paper/2211.14394/) (2022)
- [Sampling Enclosing Subgraphs for Link Prediction](https://mlsanity.com/paper/2206.12004/) (2022)
- [SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2303.03379/) (2023)
- [Flashlight: Scalable Link Prediction with Effective Decoders](https://mlsanity.com/paper/2209.10100/) (2022)
- [Simplifying Subgraph Representation Learning for Scalable Link Prediction](https://mlsanity.com/paper/2301.12562/) (2023)
- [Efficient Link Prediction via GNN Layers Induced by Negative Sampling](https://mlsanity.com/paper/2310.09516/) (2023)
- [A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness](https://mlsanity.com/paper/2406.09675/) (2024)
- [SoREX: Towards Self-Explainable Social Recommendation with Relevant Ego-Path Extraction](https://mlsanity.com/paper/2510.00080/) (2025)
- [Learning Scalable Structural Representations for Link Prediction with Bloom Signatures](https://mlsanity.com/paper/2312.16784/) (2023)
- [NetInfoF Framework: Measuring and Exploiting Network Usable Information](https://mlsanity.com/paper/2402.07999/) (2024)
- [Stochastic Subgraph Neighborhood Pooling for Subgraph Classification](https://mlsanity.com/paper/2304.08556/) (2023)
- [Can GNNs Learn Link Heuristics? A Concise Review and Evaluation of Link Prediction Methods](https://mlsanity.com/paper/2411.14711/) (2024)
- [Towards Ideal Temporal Graph Neural Networks: Evaluations and Conclusions after 10,000 GPU Hours](https://mlsanity.com/paper/2412.20256/) (2024)
- [Asymmetric Learning for Graph Neural Network based Link Prediction](https://mlsanity.com/paper/2303.00170/) (2023)
- [Circle Feature Graphormer: Can Circle Features Stimulate Graph Transformer?](https://mlsanity.com/paper/2309.06574/) (2023)
- [Sub-graph Based Diffusion Model for Link Prediction](https://mlsanity.com/paper/2409.08487/) (2024)
- [Exact Acceleration of Subgraph Graph Neural Networks by Eliminating Computation Redundancy](https://mlsanity.com/paper/2412.18125/) (2024)
- [A Community-Enhanced Graph Representation Model for Link Prediction](https://mlsanity.com/paper/2512.21166/) (2025)

## Abstract (arXiv)

Subgraph-based graph representation learning (SGRL) has been recently proposed to deal with some fundamental challenges encountered by canonical graph neural networks (GNNs), and has demonstrated advantages in many important data science applications such as link, relation and motif prediction. However, current SGRL approaches suffer from scalability issues since they require extracting subgraphs for each training or test query. Recent solutions that scale up canonical GNNs may not apply to SGRL. Here, we propose a novel framework SUREL for scalable SGRL by co-designing the learning algorithm and its system support. SUREL adopts walk-based decomposition of subgraphs and reuses the walks to form subgraphs, which substantially reduces the redundancy of subgraph extraction and supports parallel computation. Experiments over six homogeneous, heterogeneous and higher-order graphs with millions of nodes and edges demonstrate the effectiveness and scalability of SUREL. In particular, compared to SGRL baselines, SUREL achieves 10× speed-up with comparable or even better prediction performance; while compared to canonical GNNs, SUREL achieves 50% prediction accuracy improvement.