# About Graph Degeneracy, Representation Learning and Scalability

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2020.

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

- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Recent Advances in Malware Detection: Graph Learning and Explainability](https://mlsanity.com/paper/2502.10556/) (2025)
- [Graph Sparsification for Enhanced Conformal Prediction in Graph Neural Networks](https://mlsanity.com/paper/2410.21618/) (2024)

## Abstract (arXiv)

Graphs or networks are a very convenient way to represent data with lots of interaction. Recently, Machine Learning on Graph data has gained a lot of traction. In particular, vertex classification and missing edge detection have very interesting applications, ranging from drug discovery to recommender systems. To achieve such tasks, tremendous work has been accomplished to learn embedding of nodes and edges into finite-dimension vector spaces. This task is called Graph Representation Learning. However, Graph Representation Learning techniques often display prohibitive time and memory complexities, preventing their use in real-time with business size graphs. In this paper, we address this issue by leveraging a degeneracy property of Graphs - the K-Core Decomposition. We present two techniques taking advantage of this decomposition to reduce the time and memory consumption of walk-based Graph Representation Learning algorithms. We evaluate the performances, expressed in terms of quality of embedding and computational resources, of the proposed techniques on several academic datasets. Our code is available at https://github.com/SBrandeis/kcore-embedding