PaperlayerView exact revision on arXiv

Source-linked AI summary

Detecting Random Geometric Graphs with General Kernel

Dong Huang, Shuangping Li

arXiv:2610.12765v1math.STcs.ITmath.ITmath.PRstat.TH

TL;DR

The paper asks how kernel behavior near zero determines when a spherical random geometric graph can be distinguished from an Erdős–Rényi graph of the same edge density. It characterizes thresholds for cusp and finitely flat smooth kernels using signed cycle counts, finding triangles or quadrilaterals optimal across these classes.

  • Problem

    For dense graphs, how does the detection threshold change between hard kernels and smooth kernels, and what happens when the kernel is nondifferentiable at zero or has a vanishing first derivative?

    Source: §1.1 · p. 3

  • Method

    The paper relates local kernel behavior to detection thresholds and analyzes signed cycle counts, including triangles and quadrilaterals.

    Source: §2.1 · p. 11, §6 · p. 39

  • Results

    Pure odd cusps have d⋆ = n^(3/(3β+1)), finitely flat smooth kernels have d⋆ = n^(3/(3m+qm)), and quadrilaterals are optimal for certain mixed cusps with triangle-signal cancellation.

    Source: §6 · p. 39

  • Takeaways & Limitations

    Across the studied fixed-kernel classes, local behavior at zero determines the threshold, with signed triangles or quadrilaterals attaining it.

    Source: §6 · p. 39

    The results concern fixed dense kernels; the optimal threshold for sparse graphs or dimension-dependent kernels remains open.

    Source: §6 · p. 39

Abstract

from arXiv · show

We study testing a random geometric graph with a fixed kernel against an Erd\H{o}s-R\'enyi graph with the same edge density. Under the null hypothesis, the graph has $n$ vertices and independent edges with probability $p$. Under the alternative hypothesis, latent points $X_1,\ldots,X_n$ are independent and uniform on $\mathbb{S}^{d-1}$, and edges are conditionally independent with probabilities $K(\langle X_i,X_j\rangle)$, where $p=\mathbb{E}[K(\langle X_1,X_2\rangle)]$. The goal is to determine a critical dimension $d_\star = d_\star(n,K)$: the total variation distance between the two graph laws tends to one for $d\ll d_\star$ and to zero for $d\gg d_\star$. For dense graphs, [BDER16] established $d_\star\asymp n^3$ for hard threshold kernels, whereas [MWX26] proved $d_\star\asymp n^{3/4}$ for smooth kernels with $K'(0)\ne0$. We connect these results by characterizing the detection thresholds for kernels that need not be differentiable at zero. We also determine the thresholds for smooth kernels whose first nonzero derivative at zero has finite order greater than one. Throughout these classes, signed triangle or quadrilateral counts attain the optimal detection threshold. For certain nondifferentiable kernels, quadrilateral counts are optimal while triangle counts are suboptimal.

1 Introduction

The introduction frames testing spherical random geometric graphs against density-matched Erdős–Rényi graphs, situating detection thresholds in relation to local kernel behavior and prior subgraph tests. It introduces spherical-kernel notation and the paper’s proof roadmap, including the role of signed triangle and quadrilateral counts across the kernel classes considered.

1.1 Model and testing problem

  • The test compares spherical latent-position graphs with density-matched Erdős–Rényi graphs; their edge and forest laws agree, making triangles the smallest revealing pattern.Earlier dense thresholds are d*≍n^3 for hard threshold kernels and d*≍n^{3/4} for smooth kernels with K′(0)≠0 [MWX26].Source: §1.1 · p. 3

1.2 Main results

  • The signed triangle and quadrilateral counts together attain the optimal detection threshold throughout the cusp class; models are indistinguishable when Λn,d→0 and distinguishable when Λn,d→∞.Their signals are comparable to the squared signal-to-noise ratios of the signed triangle and quadrilateral counts, respectively; noise is measured under Qn,d.Source: §1.2 · p. 5
  • When mixed-cusp contributions cancel at β=α+1/3, the triangle signal weakens, and signed quadrilateral counts can be necessary for the optimal threshold.Signed quadrilaterals avoid this cancellation because their mean is expressible as an integral of a square.Source: §1.1 · p. 4, §1.2 · p. 5
  • For smooth kernels whose first nonzero derivative has finite order m≥2, d*=n^{3/(3m+q_m)}, and signed triangle counts attain this threshold.Here q_m=1 for odd m and q_m=2 for even m.Source: §1.2 · p. 6

1.3 Proof overview

  • The proofs establish detection using signed cycle counts and bound indistinguishability through a KL-divergence chain rule, with sharper posterior estimates needed for lower-order terms.In the jump case, a Gram-matrix comparison gives KL(P∥Q)≲n^3/d.Source: §1.3 · pp. 7–8

1.4 Related work

  • The spherical model supports growing latent dimension with valid inner-product probabilities, complementing random dot-product graph theory, which often studies fixed dimension [AFT+18].Related spherical-graph work studies recovery of an unknown connection function and latent distances.Source: §1.4 · p. 9
  • For p=a/n, showed indistinguishability at d≫(log n)^36, leaving a gap from (nh(p))^3≍(log n)^3; [DMS+26a] resolved the threshold for p≳n^-2/3/log n.[DMS+26a] proved indistinguishability when d≫(nh(p))^3 and d≥(1+ϵ)n over its stated density range.Source: §1.4 · p. 10
  • For spherical graphs, found d⋆≍n^3 for hard thresholds, while [MWX26] found d⋆≍n^3/4 for smooth K′(0)≠0; [Luo26] shows quadrilaterals can detect when triangles cancel.[Luo26] also identifies an additional detection scale for dense polynomial kernels of bounded degree.Source: §1.4 · pp. 9–10
  • Other variants study anisotropic Gaussian geometry, soft or Gaussian connection functions, spherical edge noise, and hidden or masked geometry [SOLH26] [BLY26] [GPS26].[HMS26] established the same threshold for n^-1/5 polylog(n)≤p≤1/3; [DMS+26b] established the sharp threshold for p→0 and p≥n^-1+δ.Source: §1.4 · p. 10
  • Signed subgraph moments are Fourier coefficients of the graph likelihood ratio; [BB24b] characterizes low-degree testing, while finds quadrilaterals optimal and triangles suboptimal for toroidal L∞ geometry.Related Fourier methods treat random algebraic graphs; signed stars and quadrilaterals suffice for constant-degree polynomial tests in several block models [BB25a]. Subgraph statistics also support network estimation [BCL11], community tests [GL17], and contiguity or testing with degree heterogeneity and mixed memberships; quadrilaterals connect to graph quasirandomness.Source: §1.4 · p. 10

1.5 Notation and paper organization

  • Notation assumes independent latent points with uniform law σd, defines kernel energy vd=E[κd(Td)^2], and introduces the integral operator for zonal profiles.The conventions also define TV and KL distances, function and operator norms, falling factorials, positive parts, and asymptotic comparison symbols.Source: §1.5 · pp. 10–11
  • Section 2 proves detection results with signed triangles and quadrilaterals; Section 3 develops the KL and posterior formulation; Sections 4–5 prove matching impossibility results for cusp and finitely flat smooth kernels.Section 6 discusses implications and connections to prior work, with some technical proofs deferred to appendices.Source: §1.5 · p. 11

2 Detection by cycle counts

Signed triangle and quadrilateral counts provide detection guarantees, and together their signals determine whether the graph laws are distinguishable. The paper applies this framework to cusp kernels and finitely flat smooth kernels, where triangle signals can weaken or remain optimal depending on the kernel.

2.1 Detection guarantees for triangle and quadrilateral counts

  • Centered triangle and quadrilateral counts detect latent dependence that is absent from single edges and pairs of edges.Under the Erdős–Rényi model, centered cycle counts have mean zero; the triangle and quadrilateral alternatives have means proportional to their respective cycle traces.Source: §2.1 · pp. 11–13
  • If n^3τ3,d^2 + n^4τ4,d^2 diverges, selecting the stronger cycle-count test yields total variation tending to one.The criterion combines the squared signal-to-noise contributions of signed triangles and quadrilaterals.Source: §2.1 · pp. 14–15

2.2 Possibility results for cusp kernels

  • Pure even cusps have τ3,d^2 ≍ d^−3α−2 and τ4,d ≍ d^−2α−2; pure odd cusps have τ3,d^2 ≍ d^−3β−1 and τ4,d ≍ d^−2β−1; jumps have all three scales ≍ d^−1.The third scale in each case is the squared operator norm of Tκd.Source: §2.2 · pp. 15–16
  • For cusp kernels, triangles detect away from the critical relation, while quadrilaterals can detect when cancellation weakens the triangle signal.For jumps, signed triangles alone achieve detection for d ≪ n^3; on the critical relation, both traces remain in the criterion.Source: §2.2 · p. 16

2.3 Possibility results for smooth kernels

  • For even m, |τ3,d| ≍ d^−(3m+2)/2; for odd m, |τ3,d| ≍ d^−(3m+1)/2.In mixed cusps, the leading triangle contributions cancel when β = α + 1/3 and their leading coefficients sum to zero, but the fourth trace has nonnegative terms and does not cancel.Source: §2.3 · pp. 16–17
  • For finitely flat smooth kernels, the first nonconstant Taylor term has parity m, and signed triangles attain the optimal detection threshold.The leading cubic contribution cannot cancel; degree one dominates for odd m and degree two for even m.Source: §2.3 · p. 17

3 Posterior cavity reduction

The section bounds impossibility by expanding KL divergence through sequential vertex exposure, then estimating the resulting conditional prediction costs. Prior moment bounds control higher orders, while posterior-replica estimates sharpen lower-order terms.

3 Posterior cavity reduction

  • Sequential exposure reduces the impossibility bound to conditional divergences for each new vertex’s edges to the already exposed graph.Pinsker’s inequality makes KL divergence tending to zero sufficient for total variation to tend to zero.Source: §3 · p. 18
  • The cavity inequality bounds each order-k prediction cost by the prior moment E[H_d(T_d)^k], enabling moment estimates to control the KL expansion.The conditional prediction cost is bounded by E[h_k,d(X_1, …, X_k)^2] before comparison with the prior moment.Source: §3 · p. 19
  • For d ≥ 3, Lemma 3.2 gives a uniform contracted-kernel bound; for fixed cusp kernels it also bounds E[H_d(T_d)^4] by C_Kτ_4,d^2 for sufficiently large d.The supplied lemma statement omits the displayed uniform bound’s formula.Source: §3 · p. 20
  • Prior estimates control sufficiently high orders, but lower orders need sharper posterior bounds; the growing-order controls differ between cusp and smooth kernels.For cusps, the prior estimate controls orders above C_K log d on the critical relation; for smooth kernels, the cited bound controls orders above a fixed k⋆ > 6m/q_m + 2.Source: §3 · p. 21
  • Posterior replicas represent squared conditional means, and their averaged marginal law for either replica equals the prior latent-point law.The section uses likelihood-overlap comparisons and posterior tail bounds to estimate replica statistics.Source: §3 · pp. 21–22

4 Impossibility results for cusp kernels

This section establishes impossibility results for cusp kernels by bounding relative entropy through triangle and quadrilateral signals, localizing continuous cusps and controlling contributions of different orders. Across four cusp cases, it proves indistinguishability when the divergence control parameter tends to zero; in a mixed-cusp example, triangle cancellation leaves signed quadrilateral counts to attain the sharp detection threshold.

4 Impossibility results for cusp kernels

  • The proof reduces the total-variation bound to controlling the posterior-expansion terms G_k, with the triangle and quadrilateral signals combined in Λ_n,d.Pinsker’s inequality relates total variation to KL divergence, and Proposition 4.1 gives the required KL bound in terms of Λ_n,d.Source: §4 · p. 22

4.1 Preliminary: localization of the kernel

  • For continuous cusps and n ≤ C0d^2, localization changes the centered kernel, cycle traces, and KL divergence by at most C exp(−c2d^1/12).The localized kernel agrees with the original near zero; the exponentially small error makes the replacement valid for the ensuing estimates.Source: §4.1 · pp. 23–24

4.2 Order two

  • At order two, the path profile yields triangle and quadrilateral moments τ3,d and τ4,d; on the critical mixed-cusp relation, the posterior-retaining estimate gives G2 ≲ Λ_n,d.Retaining the posterior of the unqueried latent points sharpens the bound when cancellation weakens the triangle signal.Source: §4.2 · pp. 24–26

4.3 Order three

  • For a mixed cusp on β = α + 1/3, the order-three contribution satisfies G3 ≲ n^4τ4,d^2 by retaining internal edges and controlling their parity and graph structure.The internal-edge cases reduce to centered terms or to K4 with one edge removed or the complete K4.Source: §4.3 · p. 27

4.4 Higher orders and completion

  • On the critical mixed-cusp relation, internal matchings contribute n^(1−j)(n^3τ3,d^2)^j, larger connected components are controlled by the fourth trace, and fixed ranges of higher orders sum to at most a constant times Λ_n,d.A general query estimate controls the remaining higher orders in Proposition 4.7.Source: §4.4 · pp. 28–29
  • For jump kernels, KL(P∥Q) ≲ n^3/d ≲ Λ_n,d, and across all four cusp cases Λ_n,d → 0 implies TV(P, Q) → 0.Combined with the cycle tests, these bounds complete the proof of Theorem 1.2.Source: §4.4 · pp. 30–31
  • For a mixed cusp with β = α + 1/3 and the stated coefficient choice, the leading triangle contributions cancel.The remaining triangle signal depends on smaller-order terms in the local expansions.Source: §4.4 · p. 31
  • For a fixed dense mixed-cusp kernel, τ_3,d = O(d^(-3α/2-2)) and τ_4,d ≍ d^(-2α-5/3), giving the sharp threshold d⋆ = n^(6/(6α+5)) attained by signed quadrilateral counts.When n ≍ d^(α+1), the triangle signal tends to zero, contradicting [MWX26, Conjecture 1].Source: §4.4 · p. 31

5 Impossibility results for finite flat kernels

This section proves impossibility results for finite flat kernels, showing that in sufficiently large dimension the graph laws are indistinguishable. It controls posterior moments across orders and transfers fixed-order bounds to the original graph law using finite Taylor approximations and a tail estimate.

5.1 Order two

  • Order-two estimates control diagonal overlaps using exponential moments of harmonic overlaps and truncation of the latent-sample Gram matrix.The truncation addresses a deterministic Gram-matrix bound of order n that is too large for the needed exponential estimate.Source: §5.1 · pp. 32–33

5.2 Order three

  • For finite harmonic expansions, order-three control reduces to proving Epost[|T3|] = o(n^-1), using concentration for a canonical U-statistic and transferring its tail to the posterior.The concentration argument conditions on one latent sample, then uses posterior replica bounds to transfer the prior tail.Source: §5.2 · p. 34

5.3 Higher fixed orders

  • Newton’s identities yield bounds for every fixed order k >= 4, while a separate tail bound controls the sum of orders above any fixed k⋆ > 6m/qm + 2.The fixed-order estimates apply to the auxiliary model; the higher-order tail estimate applies to the original kernel.Source: §5.3 · pp. 35–36

5.4 Return to the original graph law

  • Returning to the original graph law, the proof approximates its centered kernel by a finite Taylor polynomial and controls the likelihood and interaction-kernel replacement errors.Six additional derivatives bound the Taylor remainder, and a likelihood comparison is established when n <= C d^(m+qm/3).Source: §5.4 · pp. 37–38
  • Fixed-order arguments apply under the original graph law using Π in the observables and P in the posterior.Proposition 5.8 supplies the same bound with the original likelihood.Source: §5.4 · pp. 38–39
  • The proof combines fixed-order bounds with a tail estimate, using the d−3 gain to control the prior tail in the likelihood comparison.The residual terms are expanded and the slice norms for the canonical statistic bound are checked.Source: §5.4 · pp. 38–39
  • If K ∈ Ksmooth(m) and d ≫ n^3/(3m+q_m), then KL(P∥Q) and TV(P, Q) both tend to zero.This is the indistinguishability threshold for finitely flat kernels.Source: §5.4 · p. 39

6 Discussions

The discussion shows how local kernel behavior determines detection thresholds, while signed quadrilaterals can remain optimal when triangle signals cancel. The analysis is limited to fixed dense kernels; sparse graphs and dimension-dependent kernels remain open settings.

The conjecture in [MWX26]

  • For a mixed cusp, triangle-signal cancellation can leave n^3τ_3,d^2→0 while n^4τ_4,d^2→∞; signed quadrilaterals are then optimal, contradicting [MWX26, Conjecture 1].The quadrilateral signal avoids cancellation, and a matching impossibility result establishes its optimality for this example.Source: §6 · p. 39

Connecting the hard and smooth thresholds

  • For each fixed 0 < β ≤ 1, the pure odd cusp threshold is d⋆=n^(3/(3β+1)), ranging from exponent 3 as β↓0 to 3/4 at β=1, connecting the hard and smooth benchmarks [MWX26].The local power β determines the threshold exponent within this fixed dense kernel family.Source: §6 · p. 39

Smooth kernels with K′(0) = 0

  • For smooth kernels with first nonzero derivative of order m, d⋆=n^(3/(3m+q_m)), where q_m=1 for odd m and q_m=2 for even m; signed triangles attain the threshold.The parity of the leading Taylor term determines q_m.Source: §6 · p. 39

Sparse graphs and kernels depending on the dimension

  • The results concern fixed dense kernels; sparse graphs require tracking p-dependent bounds, while dimension-dependent kernels also require control of their changes on the d^(-1/2) scale.A general optimal-threshold characterization for these settings remains open.Source: §6 · p. 39

Statement on AI use

The authors describe AI assistance at two stages of the investigation: proof development for finitely flat smooth kernels and cusp kernels, including triangle-cancellation cases. They also report assistance with figures, formatting, and language editing.

Statement on AI use

  • GPT-5.6 Sol assisted in developing proofs for smooth kernels with K′(0)=0 and a first nonzero derivative of finite order; the results retain signed-triangle optimality in this class.The authors say Yihong Wu suggested expanding a general kernel to order m and computing the resulting contributions.Source: Statement on AI use · p. 40
  • GPT-6 Astra assisted with proofs for nondifferentiable cusp kernels, including cases where triangle-signal cancellation makes signed quadrilaterals optimal.The authors used local power expansions, including terms such as |x|^α for 0<α<1, to formulate the cusp class.Source: Statement on AI use · p. 40
  • GPT-5.6 Sol and GPT-6 Astra also assisted with figures, LaTeX formatting, and language editing; the authors take responsibility for the mathematical claims and final presentation.Source: Statement on AI use · p. 40

A.1 Spectral estimates for cusp kernels

The estimates separate the kernel into even and odd components to bound their harmonic coefficients and centered moments. They also describe how the component orders determine the fourth-trace and operator-norm scales.

A.1 Spectral estimates for cusp kernels

  • The even and odd parts of the kernel contribute only even and odd harmonic degrees, respectively, and their squared norms sum to v_d.The parts are defined by symmetrizing and antisymmetrizing κ_d.Source: §A.1 · p. 44
  • For pure odd or mixed cases, ∥o_d(T_d)∥_p ≲ d^-β/2 for fixed p ≥ 1.A component that vanishes near zero has exponentially small centered fixed moments and harmonic coefficients.Source: §A.1 · p. 44
  • |p_d − p_0| ≲ d^-α/2 in pure even and mixed cases, while |p_d − p_0| ≲ e^-cd in the pure odd case.When the corresponding local component vanishes, its contribution, including the centering correction, is exponentially small.Source: §A.1 · p. 45
  • In mixed cases with β ≠ α + 1/3, the leading cubic terms have different orders; when β = α + 1/3, they have the same order and their leading constants may cancel.The proof establishes the stated fourth-trace and operator-norm scales for pure even, pure odd, and mixed cases.Source: §A.1 · p. 46

A.2 Finitely flat spectral asymptotics

This section develops finite-flat spectral asymptotics and supporting Gram-matrix and concentration tools, including bounds for harmonic features, polynomials, U-statistics, and harmonic-overlap exponential moments. It also gives a proof step controlling both signs of a quantity via concentration under an operator-norm condition.

A.2 Finitely flat spectral asymptotics

  • For finitely flat kernels, |γq,d| ≍ d^-m/2 at degrees q = m, m − 2, …, qm, yielding the stated τ3,d and τ4,d estimates.The proof controls the remaining spectral degrees to establish Proposition 2.5.Source: §A.2 · p. 47

B Cavity identities and concentration tools

B.1 Uniform Gram operators for harmonic features

  • A uniform Gram event for fixed harmonic degrees is obtained by applying a Gram-matrix bound and a union bound, with failure probability at most (n + Nmax)^-D.The bound applies to harmonic feature vectors whose degree-specific dimensions satisfy Nq,d ≍ d^q.Source: §B.1 · p. 49

B.2 Concentration inequalities for posterior overlaps

  • For degree at most L in each of s sphere variables, the hypercontractive bound is ∥F∥p ≤ (p − 1)^(sL/2)∥F∥2 for p ≥ 2.Source: §B.2 · p. 49
  • For fixed harmonic degree, signed replica sums and overlaps have controlled exponential moments, including conditional bounds given one latent sample.The Gaussian covariance inequality used in the argument also covers singular covariance matrices.Source: §B.2 · pp. 50, 53
  • The concentration toolkit includes canonical U-statistic bounds based on integrated L2 norms and coefficient size, including a separate order-two bound retaining four kernel norms.The general bound also applies conditionally when the coefficients are random and independent of the sample.Source: §B.2 · pp. 51–52
  • Applying Lemma B.3 to |ϕ−|, expanding |ϕ−|^Q, and integrating the Gaussian variable leads to a logarithmic bound Ct^2Q^2/Nq,d; raising it to n/Q and using Q ≤ 3∥Uℓ(X′)∥op proves both signs.The argument chooses Q/2 signs equal to 1 and Q/2 equal to −1.Source: §B.2 · p. 54

C Proofs for cusp kernels

The cusp-kernel proofs establish common estimates before treating bounds of increasing order. They cover three continuous cases, with the jump case handled separately in Section 4.4.

C Proofs for cusp kernels

  • The proof proceeds from common moment and prediction estimates to bounds for order two, order three, and fixed ranges of higher orders.Section 4.4 combines these estimates with the prior bound and treats the jump case using (43).Source: C Proofs for cusp kernels · p. 54
  • The common estimates apply to the three continuous cases in Definition 1.1.Source: C Proofs for cusp kernels · p. 54
  • Section 4.4 combines the estimates with the prior bound and treats the jump case using (43).Source: C Proofs for cusp kernels · p. 54

C.1 Moment and conditional expectation bounds

This section develops root-moment and conditional-expectation bounds used in the cusp-kernel proofs. The estimates include operator control and distinguish the even and odd components of the link.

C.1 Moment and conditional expectation bounds

  • The scale estimates include τ3,d ≍ d−3/s and √τ4,d ≲ d−1/s−1/6, under the stated parameter conditions.The passage also gives 1/s ≤ 5/3 and bounds vd between d1/3−1/s and d2/3−1/s.Source: §C.1 · p. 55
  • For four deterministic roots, the integrated profile moments are bounded by S2, S3 + S/d, and S4 + S2/d + d−2 for four, two, and zero odd profiles, respectively.Source: §C.1 · pp. 55–56
  • For a localized pure odd link, h3,d = 0.Source: §C.1 · p. 57
  • The conditional-expectation operator is bounded by Cn on constants, Cnτ4,d/d on centered functions, and Cn√τ4,d/d on centered even functions.The lemma assumes n√τ4,d ≤ c and sufficiently large d.Source: §C.1 · p. 58
  • The harmonic-eigenspace Hilbert–Schmidt bounds yield the asserted operator bounds after summing the degree contributions.Source: §C.1 · p. 61

C.2 Order two

The order-two analysis bounds prediction for a queried pair, including when the other vertices' graph is retained. It uses conditioning on that graph to improve a bound and does not require a lower bound on the signed triangle moment.

C.2 Order two

  • Conditioning on the graph among the other vertices and then applying the two-root bound for H4,d improves a prediction-bound term.Source: §C.2 · p. 61
  • The critical-link argument assumes Λn,d = n3τ3,d^2 + n4τ4,d^2 ≤ c4.1(K).Source: §C.2 · p. 61
  • The prediction bounds hold without a lower bound on |τ3,d|.For r = 2, the identity E[Hd(T12) | A12] = τ3,dY12 gives the same bound directly.Source: §C.2 · p. 65

C.3 Order three

The order-three argument bounds contributions to the query estimate using graph integrals and conditional second moments. Its graph structure rules out zero-cost supports containing a biconnected block on at least four vertices.

C.3 Order three

  • A support containing a biconnected block on at least four vertices forces s*>0, excluding zero-cost supports made only of bridges and triangle blocks.The argument uses s*≥1/6 to bound each surviving monomial.Source: §C.3 · p. 68
  • Parity improves the moment bound for h3,d, and no absolute value is taken inside a triangle integral.On the critical relation, the proof retains the three possible internal edges and expands their eight configurations.Source: §C.3 · p. 70
  • Squaring conditional means joins two cone copies along shared roots; with at least two shared roots, the graph contains K2,k and a block on at least four vertices.Deleting internal edges preserves the vertices, center edges, and K2,k subgraph used in the graph-integral bound.Source: §C.3 · pp. 70–71
  • For m=3, all four terms are bounded by Cn^4τ4,d^2; for m≥4, the mean may additionally contribute Cn^3τ3,d^2.Summing these bounds in (115) proves both assertions of Lemma C.6.Source: §C.3 · p. 71

D Proof for smooth kernels

The smooth-kernel appendix proves a prior exponential bound by estimating harmonic pairs and controlling their coefficients. Conditioning on the sample with the larger degree gives the smaller Gram bound.

D.1 The prior exponential bound

  • Lemma 5.1 bounds harmonic pairs by conditioning on the sample with the larger degree, switching samples when ℓ<q.The proof establishes estimates for the finite harmonic model under its coefficient conditions and the Gram event.Source: §D.1 · p. 71, D Proof for smooth kernels · p. 71
  • Condition (49) makes |c0bqbℓ|∥Uℓ(X′)∥op=o(d), allowing Lemma B.8 to bound the conditioned pair.Source: §D.1 · p. 71
  • The same calculation covers a(Sκ+F): its pair coefficients remain bounded by a(1+t0)|bqbℓ|, and Lemma B.8 allows either sign.Source: §D.1 · p. 72

D.2 Order three

The appendix establishes a cubic envelope bound, controls posterior moments of quadratic overlaps for higher orders, and transfers estimates to the original graph law. The order-three argument uses parity, while the transfer section controls the residual kernel.

D.2 Order three

  • For t≥C max_{0≤r≤3} Dr, the cubic envelope estimate gives the bound stated in (55).The proof then transfers the prior estimate to the posterior using the cited moment and marginal bounds.Source: §D.2 · p. 73

D.3 Quadratic overlaps for higher orders

  • For higher orders, the addition formula represents Uq(x,y) as an inner product of unit vectors, a starting point for bounding posterior moments of YH.Source: §D.3 · p. 74

E Transfer to the original graph law

  • The transfer to the original graph law controls the residual R in the likelihood bound and interaction kernels before proving the uniform moment estimate used in Proposition 5.5.Source: E Transfer to the original graph law · p. 75

E.1 Likelihood comparison

The likelihood comparison truncates the kernel residual on a high-probability event and establishes the exponential moment needed for Proposition 5.8. The truncation error is controlled uniformly on the central events.

E.1 Likelihood comparison

  • Truncated kernels are centered and canonical, so Lemma B.5 applies to U in the likelihood comparison.Source: §E.1 · pp. 75–76
  • For every fixed D>0, a sufficiently large C0 gives P[Eτ(X)c]≤(n+d)^−D, and the likelihood residual is uniformly controlled on Eτ(X)∩Eτ(X′).Source: §E.1 · p. 75
  • The proof establishes the exponential moment used in Proposition 5.8 by estimating four parameters and integrating the tail up to the deterministic bound on U.The resulting estimate supplies the exponential moment and proves Proposition 5.8.Source: §E.1 · pp. 75–76

E.2 Conditional moments and completion

The appendix completes Proposition 5.9 by controlling polynomial observables, their residual terms, and posterior tail events. These estimates combine to establish (69).

E.2 Conditional moments and completion

  • For k = 2 the proof uses overlap-tail and diagonal-summation bounds; for k = 3 it integrates a tail event whose retained-event posterior probability is exp(-dζ+o(1)).Excluded-event posterior probabilities are O((n + d)^-D), with D chosen after k so their contribution is o(1).Source: §E.2 · p. 77
  • For nonempty J, the slice bound is at most Cd^-mk/2-3-(|I|-1)+qm/4, using qm/4 < 3.Source: §E.2 · p. 78
  • The symmetric sum Dk is canonical in each Zi, with slice norms a0 ≲ d^-mk-3 and ar ≲ d^-mk-3-(2r-1)qm/4 for 1 ≤ r ≤ k.Canonicity follows from centering of Π and R and independence of the two prior replicas.Source: §E.2 · p. 78
  • The powers in (144) exceed 2qm/3, so suitable δ makes the required ratios diverge and yields some ζ > 2qm/3.Source: §E.2 · p. 78
  • The proof bounds Epost[|Wk|] by o(n^-1); together with the estimate for the difference, this proves (69).Source: §E.2 · p. 79
  • For 2 ≤ p ≤ cA.2(m + 5)d, ∥HΠ(Td)∥p ≲ d^-m(p/d)^(qm/2), and the residual error is at most the same order when qm ≤ 2.The moment bound uses p/d ≤ 1 and the active-degree bounds; the residual estimate also assumes p ≥ 2.Source: §E.2 · p. 79
Loading 2610.12765v1…