# Concentration and regularization of random graphs

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2015.

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

- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [Quantifying Structure in CLIP Embeddings: A Statistical Framework for Concept Interpretation](https://mlsanity.com/paper/2506.13831/) (2025)
- [Majority Opinion Diffusion in Social Networks: An Adversarial Approach](https://mlsanity.com/paper/2012.03143/) (2020)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Network Estimation by Mixing: Adaptivity and More](https://mlsanity.com/paper/2106.02803/) (2021)
- [Learning Laplacian Positional Encodings for Heterophilous Graphs](https://mlsanity.com/paper/2504.20430/) (2025)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [A class of network models recoverable by spectral clustering](https://mlsanity.com/paper/2104.10347/) (2021)
- [Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2304.13139/) (2023)
- [On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models](https://mlsanity.com/paper/2412.14315/) (2024)
- [On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models](https://mlsanity.com/paper/2505.05816/) (2025)
- [Modularity maximisation for graphons](https://mlsanity.com/paper/2101.00503/) (2021)
- [Implications of sparsity and high triangle density for graph representation learning](https://mlsanity.com/paper/2210.15277/) (2022)
- [Spectral embedding and the latent geometry of multipartite networks](https://mlsanity.com/paper/2202.03945/) (2022)
- [Adversarial contamination of networks in the setting of vertex nomination: a new trimming method](https://mlsanity.com/paper/2208.09710/) (2022)
- [Variational Inference: Posterior Threshold Improves Network Clustering Accuracy in Sparse Regimes](https://mlsanity.com/paper/2301.04771/) (2023)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (2023)
- [Node Regression on Latent Position Random Graphs via Local Averaging](https://mlsanity.com/paper/2410.21987/) (2024)
- [Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency](https://mlsanity.com/paper/2510.07136/) (2025)
- [Optimal Graph Clustering without Edge Density Signals](https://mlsanity.com/paper/2510.21669/) (2025)
- [Global Optimization on Graph-Structured Data via Gaussian Processes with Spectral Representations](https://mlsanity.com/paper/2511.07734/) (2025)
- [Spectral graph clustering with inhomogeneous latent geometry](https://mlsanity.com/paper/2608.11321/) (2026)
- [Sharp spectral norm concentration of sparse random tensors](https://mlsanity.com/paper/2609.20520/) (2026)
- [The Limits of Query Monitoring against Distributed Model Extraction](https://mlsanity.com/paper/2610.13083/) (2026)

## Abstract (arXiv)

This paper studies how close random graphs are typically to their expectations. We interpret this question through the concentration of the adjacency and Laplacian matrices in the spectral norm. We study inhomogeneous Erd"os-R'enyi random graphs on n vertices, where edges form independently and possibly with different probabilities pij. Sparse random graphs whose expected degrees are o(log n) fail to concentrate; the obstruction is caused by vertices with abnormally high and low degrees. We show that concentration can be restored if we regularize the degrees of such vertices, and one can do this in various ways. As an example, let us reweight or remove enough edges to make all degrees bounded above by O(d) where d=max npij. Then we show that the resulting adjacency matrix A' concentrates with the optimal rate: |A' - mathbbE A| = O(√d). Similarly, if we make all degrees bounded below by d by adding weight d/n to all edges, then the resulting Laplacian concentrates with the optimal rate: |L(A') - L(mathbbE A')| = O(1/√d). Our approach is based on Grothendieck-Pietsch factorization, using which we construct a new decomposition of random graphs. We illustrate the concentration results with an application to the community detection problem in the analysis of networks.