mlsanityData to 7 Oct 2026

Graph-Skeleton: ~1% Nodes are Sufficient to Represent Billion-Scale Graph

arXiv 2402.09565 ↗First posted 14 Feb 2024cs.AIcited by 6

Not on the map. Why?

Abstract (arXiv)

Due to the ubiquity of graph data on the web, web graph mining has become a hot research spot. Nonetheless, the prevalence of large-scale web graphs in real applications poses significant challenges to storage, computational capacity and graph model design. Despite numerous studies to enhance the scalability of graph models, a noticeable gap remains between academic research and practical web graph mining applications. One major cause is that in most industrial scenarios, only a small part of nodes in a web graph are actually required to be analyzed, where we term these nodes as target nodes, while others as background nodes. In this paper, we argue that properly fetching and condensing the background nodes from massive web graph data might be a more economical shortcut to tackle the obstacles fundamentally. To this end, we make the first attempt to study the problem of massive background nodes compression for target nodes classification. Through extensive experiments, we reveal two critical roles played by the background nodes in target node classification: enhancing structural connectivity between target nodes, and feature correlation with target nodes. Followingthis, we propose a novel Graph-Skeleton1 model, which properly fetches the background nodes, and further condenses the semantic and topological information of background nodes within similar target-background local structures. Extensive experiments on various web graph datasets demonstrate the effectiveness and efficiency of the proposed method. In particular, for MAG240M dataset with 0.24 billion nodes, our generated skeleton graph achieves highly comparable performance while only containing 1.8% nodes of the original graph.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 27 of its 53 references that are in the map. First posted on arXiv 14 Feb 2024.

Builds on

27 of 53 references.

References · 27

  1. 2017Graph Attention Networkscited by 8,854
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  5. 2019Simplifying Graph Convolutional Networkscited by 1,470
  6. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  7. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  8. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  9. 2018Deep Learning on Graphs: A Surveycited by 393
  10. 2021OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphscited by 328
  11. 2020MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embeddingcited by 304
  12. 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
15 more
  1. 2019Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networkscited by 177
  2. 2021Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillationcited by 151
  3. 2022NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphscited by 137
  4. 2022Condensing Graphs via One-Step Gradient Matchingcited by 100
  5. 2021Scaling Up Graph Neural Networks Via Graph Coarseningcited by 80
  6. 2022DGraph: A Large-Scale Financial Dataset for Graph Anomaly Detectioncited by 63
  7. 2017Active Learning for Graph Embeddingcited by 53
  8. 2020Graph Policy Network for Transferable Active Learning on Graphscited by 49
  9. 2020On Graph Neural Networks versus Graph-Augmented MLPscited by 30
  10. 2023Semi-decentralized Federated Ego Graph Learning for Recommendationcited by 22
  11. 2022Collaboration-Aware Graph Convolutional Network for Recommender Systemscited by 12
  12. 2020Perigee: Efficient Peer-to-Peer Network Design for Blockchainscited by 5
  13. 2023Bipartite Graph Convolutional Hashing for Effective and Efficient Top-N Search in Hamming Spacecited by 4
  14. 2018Spectral Subspace Sparsificationcited by 3
  15. 2023Topiary: Fast, Scalable Publish/Subscribe for Peer-to-Peer (D)Appscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 1; 2026: 3.

6 papers.

  1. 2024GraphFM: A generalist graph transformer that learns transferable representations across diverse domainscited by 14
  2. 2024GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insightscited by 7
  3. 2026Rethinking Efficient Graph Coarsening via a Non-Selfishness Principlecited by 1
  4. 2025Inference-friendly Graph Compression for Graph Neural Networkscited by 0
  5. 2026Improving LLM Reasoning with Homophily-aware Structural and Semantic Text-Attributed Graph Compressioncited by 0
  6. 2026Heterogeneous Graph Condensation via Role-Aware Clusteringcited by 0