Source-linked AI summary
Explicit Bounds on the Entropy of Piecewise Hölder Graphon Models
Connor Loehde-Woolard, François G. Meyer
TL;DR
The paper addresses the limited availability of explicit entropy formulae for random graph models generated by graphons. It proves convergence bounds under piecewise Hölder regularity and applies them to obtain explicit SBM and RGG entropy bounds. These bounds complement prior asymptotic characterizations, although their growth order can be higher and the convergence rate may not be optimal.
Problem
Prior entropy results for the SBM and hard RGG provided asymptotic characterizations rather than explicit quantitative formulae.
Method
The paper analyzes normalized entropy for W-random graphs whose graphons are piecewise Hölder, using discretization and block-constant approximation.
Results
The paper obtains a convergence rate for normalized entropy and explicit entropy bounds for the SBM and hard RGG.
Takeaways & Limitations
The bounds provide explicit entropy estimates for two standard random graph models where previous results were asymptotic.
Takeaways & Limitations
The bounds may have higher growth order than previous results, and the convergence rate may not be best possible.
Abstract
from arXiv · showhide
We study the entropy of random graphs generated by piecewise Hölder continuous graphons. We first present a result on the rate of convergence of the normalized entropy as the size of the graph grows. The core ideas of the proof are described, with the detailed proof provided in the appendix. From this result, we then derive quantitative bounds on the entropy for the stochastic block model and random geometric graph model. These bounds provide explicit formulae rather than asymptotic statements which have been found previously.
1 Introduction
The paper addresses the lack of explicit entropy formulae for several random graph models by extending convergence bounds from soft random geometric graph models to piecewise Hölder graphons.
- Entropy quantifies information content and provides limits on lossless compression of graph-valued data.
- Existing entropy results for the stochastic block model and hard random geometric graph model describe only asymptotic behavior.
- The paper extends prior soft random geometric graph work that bounds convergence of entropy as graph size grows.
- The paper derives explicit entropy bounds for the stochastic block model and random geometric graph model.
- The paper presents its main piecewise Hölder graphon result in Section 3 and supplies the detailed proof in Appendix A.
2 Background
The background defines the graph, random graph models, graphons, entropy, and piecewise Hölder regularity used to obtain explicit bounds beyond prior asymptotic characterizations.
- Random Graphs and Graphons: A graph is a simple, undirected, unweighted graph G = (V, E) with n labeled vertices and unordered edges.
- Random Graphs and Graphons: The stochastic block model samples latent block labels independently and connects each node pair using the corresponding matrix probability.
- Random Graphs and Graphons: A geometric graph samples points in a bounded Euclidean domain and determines edge probabilities from a distance-based function.
- Random Graphs and Graphons: A graphon is a symmetric measurable function W: Ω^2 → [0,1], and its random graph samples latent points before independently adding edges with probabilities W(X_i, X_j).
- Random Graphs and Graphons: The SBM can be represented as a graphon by partitioning the unit interval into blocks with lengths given by v.
- Random Graphs and Graphons: Piecewise Hölder graphons are needed because SBM and RGG graphons may be discontinuous rather than globally continuous.
- Random Graphs and Graphons: A relative polytope is a bounded finite-half-space intersection with nonempty interior, whose closure is a conventional convex polytope.
- Entropy and Graphs: Entropy is defined using base-2 logarithms, and for Bernoulli variables it is represented by the binary entropy function h(p).
3 Convergence of Entropy for Piecewise H¨older Graphons
The paper extends entropy-convergence analysis from globally Hölder graphons to piecewise Hölder graphons with polytope domains, then derives explicit entropy bounds for SBM and hard RGG models.
- Piecewise Hölder graphons: Piecewise Hölder graphons with polytope domains have sufficiently regular boundaries that discontinuities do not significantly alter the bound.The model-specific partition sets are intersections of the domain with relative polytopes having non-empty interiors.
- Convergence proof: The proof handles unknown latent node positions by conditioning on a discretization rather than exact positions.The discretization entropy is bounded separately, while conditional graph entropy uses a block-constant approximation of the graphon.
- Convergence rate: The resulting convergence gap Δ_n tends to zero at rate O(log nThe supplied passage truncates the displayed rate after O(log n, so no additional exponent is stated.
- Finite-n entropy bounds: Proposition 5 provides both a convergence rate and an explicit upper bound on entropy for a W-random graph with a fixed number of nodes.This makes the result directly applicable to finite graph sizes, rather than only to limiting entropy behavior.
- Stochastic block model: For the SBM, the earlier asymptotic result has lower leading order than Proposition 5, whereas Proposition 5 supplies an explicit finite-size formula.The paper relates the SBM to an equivalent graphon before applying the general bound.
- Random geometric graph: For hard RGG(n, 1, τ), the graphon is 0-1 valued, yielding a bound with the same leading order as the model’s asymptotic statement, irrespective of τ.The integral term vanishes because h(0)=h(1)=0.
4 Concluding Discussion
The paper provides explicit entropy bounds for piecewise Hölder graphon models, while acknowledging that its convergence rate may not be optimal. It identifies stronger rates, lossy compression, and real-world graphon modeling as directions for future work.
- Contributions and trade-offs: The paper’s explicit entropy bounds may grow at a higher order in n than previous results, but they provide finite-size estimation formulae.This trades potentially sharper asymptotic order for explicit quantitative bounds.
- Limitations: Abbe’s previous result gives a better convergence rate than the paper’s result, suggesting the proposed rate may not be optimal.The authors suspect that improving it may require a different proof technique.
- Future directions: Future work includes lossy compression in the broader graphon setting and modeling real-world networks with the considered graphon class.The paper notes that Baker et al.’s lossy-compression results extend immediately to this framework.
A Proof of Proposition 5
The proof bounds the entropy difference Δn by discretizing the latent domain and separating cells where the graphon is Hölder continuous from those crossing discontinuities or boundaries. Geometric bounds control the number of exceptional cells, while entropy inequalities bound each cell’s contribution.
- Discretization: The proof conditions on a discretization of the latent space and bounds each discretization element’s contribution to Δn.The Hölder assumption controls cells across which the graphon is continuous; discontinuous cells receive a trivial bound.
- Discretization: The discretization uses m^d cells in the domain and m^2d product cells in the squared domain.Latent variables record their containing cells, producing a vector M with alphabet size m^dn.
- Cell classification: Product cells are divided into C1, contained within one continuity region, and C2, not contained within any single region.Their total number is at most m^2d, and cells in C2 are controlled through boundary-overlap estimates.