mlsanityData to 7 Oct 2026

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

arXiv 2202.13538 ↗First posted 28 Feb 2022cs.LG cs.DB cs.DCcited by 28

Not on the map. Why?

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.

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

Builds on

40 of 68 references.

References · 40

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  8. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  9. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  10. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  11. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  12. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
28 more
  1. 2018Link Prediction Based on Graph Neural Networkscited by 829
  2. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  3. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  4. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  5. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  6. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  7. 2019Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networkscited by 241
  8. 2019Inductive Relation Prediction by Subgraph Reasoningcited by 237
  9. 2020Can Graph Neural Networks Count Substructures?cited by 235
  10. 2021Inductive Representation Learning in Temporal Networks via Causal Anonymous Walkscited by 188
  11. 2018Adaptive Sampling Towards Fast Graph Representation Learningcited by 180
  12. 2019AliGraph: A Comprehensive Graph Neural Network Platformcited by 152
  13. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 148
  14. 2022Decoupling the Depth and Scope of Graph Neural Networkscited by 94
  15. 2020Graph Meta Learning via Local Subgraphscited by 89
  16. 2019Inductive Matrix Completion Based on Graph Neural Networkscited by 85
  17. 2021Dorylus: Affordable, Scalable, and Accurate GNN Training with Distributed CPU Servers and Serverless Threadscited by 51
  18. 2020Neural Subgraph Matchingcited by 47
  19. 2021Accelerating Large Scale Real-Time GNN Inference using Channel Pruningcited by 41
  20. 2021Heterogeneous Graph Representation Learning with Relation Awarenesscited by 31
  21. 2021Marius: Learning Massive Graph Embeddings on a Single Machinecited by 29
  22. 2021Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximizationcited by 28
  23. 2019Neural Subgraph Isomorphism Countingcited by 27
  24. 2019Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contextscited by 19
  25. 2021Neural Predicting Higher-order Patterns in Temporal Networkscited by 13
  26. 2020AGL: a Scalable System for Industrial-purpose Graph Machine Learningcited by 9
  27. 2019On the Equivalence between Positional Node Embeddings and Structural Graph Representationscited by 7
  28. 2021Whole Brain Vessel Graphs: A Dataset and Benchmark for Graph Learning and Neuroscience (VesselGraph)cited by 7

Built on by

Cited by year

Citing papers per year: 2022: 7; 2023: 10; 2024: 8; 2025: 3.

28 papers.

Sort:

By area:

  1. 2023Temporal Graph Benchmark for Machine Learning on Temporal Graphscited by 137
  2. 2024Position: Graph Foundation Models are Already Herecited by 84
  3. 2022Graph Neural Networks for Link Prediction with Subgraph Sketchingcited by 81
  4. 2022Neighborhood-aware Scalable Temporal Network Representation Learningcited by 54
  5. 2022Linkless Link Prediction via Relational Distillationcited by 39
  6. 2023Revisiting Link Prediction: A Data Perspectivecited by 29
  7. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  8. 2023Pure Message Passing Can Estimate Common Neighbor for Link Predictioncited by 18
  9. 2024Learning Long Range Dependencies on Graphs via Random Walkscited by 18
  10. 2025Flatten Graphs as Sequences: Transformers are Scalable Graph Generatorscited by 12
  11. 2022Link Prediction with Non-Contrastive Learningcited by 11
  12. 2022Sampling Enclosing Subgraphs for Link Predictioncited by 9
16 more
  1. 2023SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learningcited by 8
  2. 2022Flashlight: Scalable Link Prediction with Effective Decoderscited by 7
  3. 2023Simplifying Subgraph Representation Learning for Scalable Link Predictioncited by 7
  4. 2023Efficient Link Prediction via GNN Layers Induced by Negative Samplingcited by 6
  5. 2024A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectivenesscited by 6
  6. 2025SoREX: Towards Self-Explainable Social Recommendation with Relevant Ego-Path Extractioncited by 5
  7. 2023Learning Scalable Structural Representations for Link Prediction with Bloom Signaturescited by 4
  8. 2023Stochastic Subgraph Neighborhood Pooling for Subgraph Classificationcited by 3
  9. 2024NetInfoF Framework: Measuring and Exploiting Network Usable Informationcited by 3
  10. 2024Can GNNs Learn Link Heuristics? A Concise Review and Evaluation of Link Prediction Methodscited by 3
  11. 2024Towards Ideal Temporal Graph Neural Networks: Evaluations and Conclusions after 10,000 GPU Hourscited by 2
  12. 2023Asymmetric Learning for Graph Neural Network based Link Predictioncited by 0
  13. 2023Circle Feature Graphormer: Can Circle Features Stimulate Graph Transformer?cited by 0
  14. 2024Sub-graph Based Diffusion Model for Link Predictioncited by 0
  15. 2024Exact Acceleration of Subgraph Graph Neural Networks by Eliminating Computation Redundancycited by 0
  16. 2025A Community-Enhanced Graph Representation Model for Link Predictioncited by 0