# Provable and practical approximations for the degree distribution using sublinear graph samples

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

## Key facts

- Cited by 12 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 24 Oct 2017.

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

- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Spectral Graph Pruning Against Over-Squashing and Over-Smoothing](https://mlsanity.com/paper/2404.04612/) (2024)
- [EXGC: Bridging Efficiency and Explainability in Graph Condensation](https://mlsanity.com/paper/2402.05962/) (2024)
- [Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks](https://mlsanity.com/paper/2302.02922/) (2023)
- [Interpretable Sparsification of Brain Graphs: Better Practices and Effective Designs for Graph Neural Networks](https://mlsanity.com/paper/2306.14375/) (2023)
- [The Snowflake Hypothesis: Training Deep GNN with One Node One Receptive field](https://mlsanity.com/paper/2308.10051/) (2023)
- [Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness](https://mlsanity.com/paper/2402.01242/) (2024)
- [DynST: Dynamic Sparse Training for Resource-Constrained Spatio-Temporal Forecasting](https://mlsanity.com/paper/2403.02914/) (2024)
- [The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs](https://mlsanity.com/paper/2406.12539/) (2024)
- [Learnt Sparsification for Interpretable Graph Neural Networks](https://mlsanity.com/paper/2106.12920/) (2021)
- [Diving into Unified Data-Model Sparsity for Class-Imbalanced Graph Representation Learning](https://mlsanity.com/paper/2210.00162/) (2022)
- [Fast Track to Winning Tickets: Repowering One-Shot Pruning for Graph Neural Networks](https://mlsanity.com/paper/2412.07605/) (2024)

## Abstract (arXiv)

The degree distribution is one of the most fundamental properties used in the analysis of massive graphs. There is a large literature on graph sampling, where the goal is to estimate properties (especially the degree distribution) of a large graph through a small, random sample. The degree distribution estimation poses a significant challenge, due to its heavy-tailed nature and the large variance in degrees. We design a new algorithm, SADDLES, for this problem, using recent mathematical techniques from the field of sublinear algorithms. The SADDLES algorithm gives provably accurate outputs for all values of the degree distribution. For the analysis, we define two fatness measures of the degree distribution, called the h-index and the z-index. We prove that SADDLES is sublinear in the graph size when these indices are large. A corollary of this result is a provably sublinear algorithm for any degree distribution bounded below by a power law. We deploy our new algorithm on a variety of real datasets and demonstrate its excellent empirical behavior. In all instances, we get extremely accurate approximations for all values in the degree distribution by observing at most 1% of the vertices. This is a major improvement over the state-of-the-art sampling algorithms, which typically sample more than 10% of the vertices to give comparable results. We also observe that the h and z-indices of real graphs are large, validating our theoretical analysis.