# K-Core Decomposition on Super Large Graphs with Limited Resources

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 53 references that are in the map.
- First posted on arXiv 26 Dec 2021.

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

- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [OpenBox: A Generalized Black-box Optimization Service](https://mlsanity.com/paper/2106.00421/) (2021)
- [Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximization](https://mlsanity.com/paper/2108.00219/) (2021)
- [RIM: Reliable Influence-based Active Learning on Graphs](https://mlsanity.com/paper/2110.14854/) (2021)
- [ROD: Reception-aware Online Distillation for Sparse Graphs](https://mlsanity.com/paper/2107.11789/) (2021)
- [I/O Efficient Core Graph Decomposition at Web Scale](https://mlsanity.com/paper/1511.00367/) (2015)
- [Parallel and Streaming Algorithms for K-Core Decomposition](https://mlsanity.com/paper/1808.02546/) (2018)

## Abstract (arXiv)

K-core decomposition is a commonly used metric to analyze graph structure or study the relative importance of nodes in complex graphs. Recent years have seen rapid growth in the scale of the graph, especially in industrial settings. For example, our industrial partner runs popular social applications with billions of users and is able to gather a rich set of user data. As a result, applying K-core decomposition on large graphs has attracted more and more attention from academics and the industry. A simple but effective method to deal with large graphs is to train them in the distributed settings, and some distributed K-core decomposition algorithms are also proposed. Despite their effectiveness, we experimentally and theoretically observe that these algorithms consume too many resources and become unstable on super-large-scale graphs, especially when the given resources are limited. In this paper, we deal with those super-large-scale graphs and propose a divide-and-conquer strategy on top of the distributed K-core decomposition algorithm. We evaluate our approach on three large graphs. The experimental results show that the consumption of resources can be significantly reduced, and the calculation on large-scale graphs becomes more stable than the existing methods. For example, the distributed K-core decomposition algorithm can scale to a large graph with 136 billion edges without losing correctness with our divide-and-conquer technique.