pith. sign in

arxiv: 1907.01605 · v1 · pith:ZIFZAVGInew · submitted 2019-07-02 · 🧮 math.PR

Limits of Sparse Configuration Models and Beyond: Graphexes and Multi-Graphexes

Christian Borgs , Jennifer T. Chayes , Souvik Dhara , Subhabrata Sen This is my paper

Pith reviewed 2026-05-25 10:22 UTC · model grok-4.3

classification 🧮 math.PR
keywords sparse random graphsconfiguration modelpreferential attachmentgraphexsampling convergencemultigraphsexchangeable graphsbipartite graphs
0
0 comments X

The pith

Sparse random graphs from the configuration model and preferential attachment converge to graphexes under sampling convergence when degree conditions hold.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the configuration model, preferential attachment model, generalized random graph, and bipartite configuration model admit limits described by graphexes when their sequences are viewed through sampling convergence. Sampling convergence tracks the behavior of randomly sampled induced subgraphs and extends the usual notion of convergence to the sparse setting where average degree stays bounded. For the configuration model, preferential attachment model, and bipartite variant, the authors supply necessary and sufficient conditions on the input parameters that guarantee this convergence occurs. The resulting limit objects for the configuration and preferential attachment cases take the form of augmented exchangeable random graph models. This supplies a compact description of the large-scale structure that these random graphs approach as size grows.

Core claim

We establish the graphex limit for the configuration model, a preferential attachment model, the generalized random graph, and a bipartite variant of the configuration model. The results for the configuration model, preferential attachment model and bipartite configuration model provide necessary and sufficient conditions for these random graph models to converge. The limit for the configuration model and the preferential attachment model is an augmented version of an exchangeable random graph model.

What carries the argument

Graphex, the object that records the limiting sampling distribution of sparse graph sequences.

If this is right

  • The configuration model converges in sampling precisely when its degree sequence meets the given moment conditions.
  • The preferential attachment model converges under matching conditions on its attachment parameters.
  • The generalized random graph admits a graphex limit without additional restrictions beyond the model definition.
  • Bipartite configuration models converge to multi-graphex limits under analogous degree conditions.
  • Multigraph versions of these models are handled by the same sampling-convergence framework.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same sampling-convergence approach could be applied to other sparse models such as those with community structure.
  • Graphex limits may yield asymptotic formulas for quantities like the number of short cycles or the spectrum of the adjacency matrix.
  • The framework opens a route to define continuum limits for processes that build networks sequentially.
  • Numerical sampling from the limiting graphex could serve as a fast proxy for simulating very large instances of the original models.

Load-bearing premise

Sampling convergence is the correct way to capture the structural features of interest in these sparse graphs.

What would settle it

A sequence of configuration-model graphs whose degrees satisfy the stated conditions yet whose induced subgraphs on random samples fail to converge to the predicted graphex.

read the original abstract

We investigate structural properties of large, sparse random graphs through the lens of "sampling convergence" (Borgs et. al. (2017)). Sampling convergence generalizes left convergence to sparse graphs, and describes the limit in terms of a "graphex". We introduce a notion of sampling convergence for sequences of multigraphs, and establish the graphex limit for the configuration model, a preferential attachment model, the generalized random graph, and a bipartite variant of the configuration model. The results for the configuration model, preferential attachment model and bipartite configuration model provide necessary and sufficient conditions for these random graph models to converge. The limit for the configuration model and the preferential attachment model is an augmented version of an exchangeable random graph model introduced by Caron and Fox (2017).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The paper establishes sampling convergence (in the sense of Borgs et al. 2017) to graphexes and multi-graphexes for four sparse random graph models: the configuration model, a preferential attachment model, the generalized random graph, and a bipartite configuration model. For the configuration model, preferential attachment model, and bipartite variant it supplies necessary and sufficient conditions on the degree sequences (or attachment parameters) for convergence to hold; the limiting objects are augmented versions of the exchangeable random graph models introduced by Caron and Fox (2017).

Significance. If the derivations are correct, the work supplies the first explicit necessary-and-sufficient conditions for sampling convergence of several canonical sparse models, together with a concrete link to the Caron-Fox framework. The introduction of multi-graphexes for multigraph sequences is a natural and potentially reusable extension. These results strengthen the applicability of graphex theory to network models that are already widely used in statistics and computer science.

minor comments (4)
  1. §2.2: the definition of the augmented Caron-Fox graphex is given only by reference to the earlier work; a self-contained one-paragraph recap of the augmentation (especially the role of the extra vertex marks) would improve readability.
  2. Theorem 3.4 (configuration model): the statement of the necessary-and-sufficient condition on the empirical degree distribution is clear, but the proof sketch does not explicitly address the case when the second-moment condition fails exactly at the boundary; a short remark on the limiting behavior in that case would be useful.
  3. Notation: the symbols W, S, and I for the graphex components are introduced in §2 but reused with different subscripts in §4 without a consolidated table; this makes cross-referencing the four models cumbersome.
  4. References: the citation to Borgs et al. (2017) on sampling convergence appears only in the introduction; adding it to the statement of each main theorem would help readers locate the precise convergence notion being used.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the paper, the recognition of its contributions to sampling convergence for sparse models, and the recommendation of minor revision. The report does not enumerate any specific major comments.

Circularity Check

0 steps flagged

Minor self-citation to sampling-convergence framework; central limits independently derived

full rationale

The paper applies the sampling-convergence definition from Borgs et al. (2017) (self-citation) to prove graphex limits and necessary/sufficient conditions for the configuration model, preferential attachment, generalized random graph, and bipartite variant. These conditions are stated in terms of model parameters (e.g., degree sequences) and the proofs derive the specific limit objects (augmented Caron-Fox exchangeable graphs) from the random-graph constructions. No equation or claim reduces the stated convergence result to a tautology, fitted input, or self-citation chain; the 2017 framework supplies the metric but the new results are falsifiable against the models themselves. Caron-Fox (2017) is external. This yields a low circularity score consistent with normal use of prior definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The central claims rest on the prior definition of sampling convergence and the Caron-Fox exchangeable graph model; the paper introduces graphex and multi-graphex as new limit objects without independent empirical validation.

axioms (2)
  • standard math Standard axioms and measure-theoretic foundations of probability theory
    Invoked throughout to define random graph sequences and convergence in distribution.
  • domain assumption The sampling convergence framework from Borgs et al. (2017) correctly generalizes left convergence to the sparse regime
    This is the lens through which all structural properties are analyzed.
invented entities (2)
  • graphex no independent evidence
    purpose: Limit object describing the sampling convergence of sparse graphs
    Defined as the object to which the random graph sequences converge.
  • multi-graphex no independent evidence
    purpose: Extension of graphex to allow multiple edges for multigraph sampling convergence
    New notion introduced to handle multigraph sequences.

pith-pipeline@v0.9.0 · 5670 in / 1561 out tokens · 41744 ms · 2026-05-25T10:22:39.420435+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages · 4 internal anchors

  1. [1]

    Our proofs rely on one lemma and three propositions

    Proof for configuration model results. Our proofs rely on one lemma and three propositions. For any (multi)-graph G, let e(G) denote the number of non-loop edges in G. Lemma 2.1 (Non-loop edges in CM n(d)). As n→∞ , e(CMn(d)) ℓn → 1/2 a.s. P CM. Further, as n→∞ , for all ε > 0 2E [e(ECMn(d))] ℓn − ∫ ∞ 0 ∫ ∞ 0 (1− e−xy)ρn(dx)ρn(dy)→ 0.(2.1) P ECM(|e(ECMn(d)...

    work page

  2. [2]

    In this section, we prove Theorem 1.6

    Proof of results on preferential attachment model. In this section, we prove Theorem 1.6. To avoid notational overhead, we re-cycle some notation, and denote the random point process Lbl √2mn(PAn(δ, mn)) for the graph PAn(δ, mn) by ξn. For a subset A∈ B(R +), let Vn(A) denote the set of vertices obtained by labeling the vertices uniformly from [0,√2mn] 34...

    work page

  3. [3]

    We first es- tablish that the number of edges in GRG n(w) is concentrated around a deterministic value

    Proof of results on generalized random graph. We first es- tablish that the number of edges in GRG n(w) is concentrated around a deterministic value. Recall that for any graph G, we use e(G) to denote the number of non-loop edges in G, and that Ln denotes the ℓ1 norm of the weight vector, Ln = ∑ i∈[n] wi. GRAPHEX LIMITS OF RANDOM GRAPHS 41 Lemma 4.1. For 0...

    work page

  4. [4]

    44 BORGS, CHAYES, DHARA, SEN Fix ε > 0 and let V>ε ={i∈ [n] : wi > ε√Ln} and V c ≤ε = V>ε

    Similarly, lim ε→0 lim sup K→∞ lim sup n→∞ Err(ε, K, n) = 0 and lim K→∞ lim sup ε→0 lim sup M→∞ lim sup n→∞ Err(K, ε, M, n) = 0. 44 BORGS, CHAYES, DHARA, SEN Fix ε > 0 and let V>ε ={i∈ [n] : wi > ε√Ln} and V c ≤ε = V>ε. Recalling that we assigned a random label in [0 ,√Ln] to each vertex in [ n], let Vi be the set of vertices with labels in Bi. We set V >...

    work page

  5. [5]

    Next, again by Markov’s inequality, P (Ac 2)≤ 1 K E [ ∑ i∈Vt ¯wi] = 1 K t Ln ∑ i∈[n] wi = t K = Err(1/K, n)

    = Err(ε, n). Next, again by Markov’s inequality, P (Ac 2)≤ 1 K E [ ∑ i∈Vt ¯wi] = 1 K t Ln ∑ i∈[n] wi = t K = Err(1/K, n). Finally,|V > t |∼ Bin(|V>ε|, t/√Ln). Thus, another application of Markov’s inequality yields P (Ac 3)≤ t|V>ε|√LnM = tρn([ε,∞)) M = Err(ε, M, n). 48 BORGS, CHAYES, DHARA, SEN Proof of Lemma 4.5. First, observe that, on the event A define...

    work page

  6. [6]

    Proofs of results on Bipartite Configuration Model. The proof of Theorem 1.10 is very similar to that of Theorem 1.2 for the configura- tion model and again relies on three key propositions, whose proofs are also similar to those of the corresponding key propositions from the proof of The- orem 1.2. We will outline this proof strategy by stating the key pro...

    work page

  7. [7]

    Aldous, D. J. (1981). Representations for partially exchangeable arrays of random variables. J. Multivar. Anal. , 11(4):581–598

    work page 1981

  8. [8]

    Austin, T. (2008). On exchangeable random variables and the statistics of large graphs and hypergraphs. Probab. Surveys, 5:80–145

    work page 2008

  9. [9]

    Barab´ asi, A. L. (2016). Network Science. Cambridge University Press, 1 edition

    work page 2016

  10. [10]

    Barbour, A. D. (1988). Stein’s method and poisson process convergence. J. Appl. Probab., 25:175–184

    work page 1988

  11. [11]

    Bollob´ as, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin., 1(4):311–316

    work page 1980

  12. [12]

    and Riordan, O

    Bollob´ as, B. and Riordan, O. (2009).Metrics for sparse graphs, pages 211–288. London Mathematical Society Lecture Note Series. Cambridge University Press

    work page 2009

  13. [13]

    T., and Vesztergombi, K

    Borgs, C., Chayes, J., Lov´ asz, L., S´ os, V. T., and Vesztergombi, K. (2006).Counting graph homomorphisms, pages 315–371. Springer Berlin Heidelberg, Berlin, Heidelberg

    work page 2006

  14. [14]

    T., Cohn, H., and Holden, N

    Borgs, C., Chayes, J. T., Cohn, H., and Holden, N. (2018a). Sparse exchangeable graphs and their limits via graphon processes. J. Mach. Learn. Res. , 18(210):1–71

    work page

  15. [15]

    Identifiability for graphexes and the weak kernel metric

    Borgs, C., Chayes, J. T., Cohn, H., and Lov´ asz, L. M. (2018b). Identifiability for graphexes and the weak kernel metric. arXiv:1804.03277

    work page internal anchor Pith review Pith/arXiv arXiv

  16. [16]

    T., Cohn, H., and Veitch, V

    Borgs, C., Chayes, J. T., Cohn, H., and Veitch, V. (2017). Sampling perspectives on sparse exchangeable graphs. arxiv:1708.03237

    work page arXiv 2017

  17. [17]

    T., Cohn, H., and Zhao, Y

    Borgs, C., Chayes, J. T., Cohn, H., and Zhao, Y. (2014). An Lp theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions. To appear in Trans. Amer. Math. Soc

    work page 2014

  18. [18]

    T., Cohn, H., and Zhao, Y

    Borgs, C., Chayes, J. T., Cohn, H., and Zhao, Y. (2018c). An Lp theory of sparse graph convergence II: LD convergence, quotients, and right convergence. Ann. Probab., 46:337–396

    work page

  19. [19]

    T., Dhara, S., and Sen, S

    Borgs, C., Chayes, J. T., Dhara, S., and Sen, S. (2019). A correction to Kallenberg’s theorem for jointly exchangeable random measures. GRAPHEX LIMITS OF RANDOM GRAPHS 59

    work page 2019

  20. [20]

    T., Lov´ asz, L., S´ os, V

    Borgs, C., Chayes, J. T., Lov´ asz, L., S´ os, V. T., and Vesztergombi, K. (2008). Conver- gent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Adv. Math., 219(6):1801–1851

    work page 2008

  21. [21]

    T., Lov´ asz, L., S´ os, V

    Borgs, C., Chayes, J. T., Lov´ asz, L., S´ os, V. T., and Vesztergombi, K. (2011). Limits of randomly grown graph sequences. European J. Combin., 32(7):985–999

    work page 2011

  22. [22]

    T., Lov´ asz, L., S´ os, V

    Borgs, C., Chayes, J. T., Lov´ asz, L., S´ os, V. T., and Vesztergombi, K. (2012). Con- vergent sequences of dense graphs II. Multiway cuts and statistical physics.Ann. Math., 176(1):151–219

    work page 2012

  23. [23]

    Britton, T., Deijfen, M., and Martin-L¨ of, A. (2006). Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. , 124(6):1377–1397

    work page 2006

  24. [24]

    and Fox, E

    Caron, F. and Fox, E. B. (2017). Sparse graphs using exchangeable random measures. J. R. Stat .Soc. Series B Stat. Methodol. , 79(5):1–44

    work page 2017

  25. [25]

    Chatterjee, S., Diaconis, P., and Sly, A. (2011). Random graphs with a given degree sequence. Ann. Appl. Probab., 21(4):1400–1435

    work page 2011

  26. [26]

    and Lu, L

    Chung, F. and Lu, L. (2006). Concentration inequalities and martingale inequalities: a survey. Internet Math., 3(1):79–127

    work page 2006

  27. [27]

    Daley, D. J. and Vere-Jones, D. J. D. D. (2008). An Introduction to the Theory of Point Process, volume II. Springer-Verlag, New York

    work page 2008

  28. [28]

    Graph limits and exchangeable random graphs

    Diaconis, P. and Janson, S. (2007). Graph limits and exchangeable random graphs. arXiv:0712.2749

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  29. [29]

    van der Hofstad, R. (2017). Random Graphs and Complex Networks , volume I. Cam- bridge University Press, Cambridge

    work page 2017

  30. [30]

    van der Hofstad, R., Hooghiemstra, G., and Van Mieghem, P. (2005). Distances in random graphs with finite variance degrees. Random Struct. Algor., 27(1):76–123

    work page 2005

  31. [31]

    Hoover, D. N. (1979). Relations on probability spaces and arrays of random variables. Preprint, Institute for Advanced Study, Princeton

    work page 1979

  32. [32]

    and Shiryaev, A

    Jacod, J. and Shiryaev, A. N. (2003). Limit Theorems for Stochastic Processes . Grundlehren der mathematischen Wissenschaften. Springer-Verlag Berlin Heidelberg

    work page 2003

  33. [33]

    Janson, S. (2017). On convergence for graphexes. arXiv:1702.06389

    work page arXiv 2017

  34. [34]

    Janson, S., Luczak, T., and Rucinski, A. (2000). Random Graphs. Wiley, New York

    work page 2000

  35. [35]

    Kallenberg, O. (1990). Exchangeable random measures in the plane. J. Theor. Probab., 3(1):81–136

    work page 1990

  36. [36]

    Kallenberg, O. (2005). Probabilistic Symmetries and Invariance Principles. Springer- Verlag New York

    work page 2005

  37. [37]

    Kingman, J. F. C. (1967). Completely random measures. Pacific J. Math. , 21(1):59– 78

    work page 1967

  38. [38]

    R., Lindgren, G., and Rootzen, H

    Leadbetter, M. R., Lindgren, G., and Rootzen, H. (1983). Extremes and Related Properties of Random Sequences and Processes. Springer, New York, NY

    work page 1983

  39. [39]

    Lipster, R. S. and Shiryayev, A. N. (1989). Theory of Martingales . Springer, Dor- drecht

    work page 1989

  40. [40]

    (2012).Large Networks and Graph Limits

    Lov´ asz, L. (2012).Large Networks and Graph Limits . American Mathematical Soci- ety

    work page 2012

  41. [41]

    and Szegedy, B

    Lov´ asz, L. and Szegedy, B. (2006). Limits of dense graph sequences. J. Combin. Theory Ser. B , 96(6):933–957

    work page 2006

  42. [42]

    and Szegedy, B

    Lov´ asz, L. and Szegedy, B. (2007). Szemer´ edi’s lemma for the analyst.Geom. Funct. Anal. (GAFA), 17(1):252–270

    work page 2007

  43. [43]

    and Reed, B

    Molloy, M. and Reed, B. (1995). A critical-point for random graphs with a given degree sequence. Random Struct. Algor., 6(2-3):161–179

    work page 1995

  44. [44]

    Newman, M. (2010). Networks: An Introduction. Oxford University Press, 1 edition

    work page 2010

  45. [45]

    Pittel, B. (2010). On a random graph evolving by degrees. Adv. Math., 223(2):619– 60 BORGS, CHAYES, DHARA, SEN 671

    work page 2010

  46. [46]

    and Szak´ acs, L

    R´ ath, B. and Szak´ acs, L. (2012). Multigraph limit of the dense configuration model and the preferential attachment graph. Acta Math. Hung. , 136(3):196–221

    work page 2012

  47. [47]

    The Class of Random Graphs Arising from Exchangeable Random Measures

    Veitch, V. and Roy, D. M. (2015). The class of random graphs arising from exchange- able random measures. arXiv:1512.03099

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  48. [48]

    Sampling and Estimation for (Sparse) Exchangeable Graphs

    Veitch, V. and Roy, D. M. (2016). Sampling and Estimation for (sparse) exchangeable graphs. arXiv:1611.00843

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  49. [49]

    Wormald, N. C. (1999). Models of random regular graphs. In Lamb, J. D. and Preece, D. A., editor, Surveys in Combinatorics, 1999 , pages 239–298. Cambridge University Press. Microsoft Research, One Memorial Drive, Cambridge MA 02142. E-mail: Christian.Borgs@microsoft.com jchayes@microsoft.com Department of Mathematics Massachusetts Institute of Technology...

    work page 1999