PaperlayerView exact revision on arXiv

Source-linked AI summary

Oracle inequalities for network models and sparse graphon estimation

Olga Klopp, Alexandre B. Tsybakov, Nicolas Verzelen

arXiv:1507.04118v4math.ST

TL;DR

The paper studies estimation of network connection probabilities and graphons in inhomogeneous, including sparse, random graphs. It uses ordinary and restricted block-constant least-squares estimators to obtain oracle inequalities and estimation rates, while accounting for latent-design variability in graphon estimation. The results distinguish empirical probability-matrix loss from integrated graphon loss and identify an additional agnostic-error component.

  • Problem

    The paper asks how to estimate connection-probability matrices and graphons when networks may be sparse and graphon latent variables are unobserved.

  • Method

    The paper uses ordinary and restricted block-constant least-squares estimators and analyzes them through oracle inequalities relative to block-constant approximations.

  • Results

    The estimators yield optimal probability-matrix rates in sparse settings, while graphon estimation obtains L2 rates with an additional agnostic error from latent-variable variability.

  • Takeaways & Limitations

    Probability-matrix estimation follows an empirical-loss perspective, whereas graphon estimation follows an integrated-loss perspective and can be slower because of latent-design variability.

  • Takeaways & Limitations

    The restricted estimator requires an upper bound on ||Θ0||∞, and graphons are identifiable only up to weak isomorphism.

Abstract

from arXiv · show

Inhomogeneous random graph models encompass many network models such as stochastic block models and latent position models. We consider the problem of statistical estimation of the matrix of connection probabilities based on the observations of the adjacency matrix of the network. Taking the stochastic block model as an approximation, we construct estimators of network connection probabilities -- the ordinary block constant least squares estimator, and its restricted version. We show that they satisfy oracle inequalities with respect to the block constant oracle. As a consequence, we derive optimal rates of estimation of the probability matrix. Our results cover the important setting of sparse networks. Another consequence consists in establishing upper bounds on the minimax risks for graphon estimation in the $L\_2$ norm when the probability matrix is sampled according to a graphon model. These bounds include an additional term accounting for the "agnostic" error induced by the variability of the latent unobserved variables of the graphon model. In this setting, the optimal rates are influenced not only by the bias and variance components as in usual nonparametric problems but also include the third component, which is the agnostic error. The results shed light on the differences between estimation under the empirical loss (the probability matrix estimation) and under the integrated loss (the graphon estimation).

1 Introduction

The paper studies network probability-matrix and graphon estimation, focusing on sparse inhomogeneous networks and the challenges caused by latent graphon designs. It develops block-constant least-squares estimators and derives oracle-based estimation results for both targets.

  • 1.1 Graphons and sparse graphon models: Graphons are symmetric measurable functions that represent limiting objects for networks and generate random graphs through latent uniformly distributed variables.Conditionally on the latent variables, edge observations are independent Bernoulli variables with probabilities determined by the graphon.
  • 1.1 Graphons and sparse graphon models: Sparse graphon models introduce a scale parameter ρn, yielding networks with O(ρnn2) edges and extending the dense graphon setting.The sparse model can also be viewed as independently removing edges from a graphon-generated network.
  • 1.2 Our results: The paper estimates the connection-probability matrix Θ0 from adjacency observations using block-constant least-squares estimators and oracle inequalities.The ordinary and restricted estimators approximate stochastic block models, with the restricted version controlling partition balance or parameter magnitude.
  • 1.2 Our results: Graphon estimation differs from probability-matrix estimation because latent design points are unobserved and graphons are identifiable only up to weak isomorphism.The paper frames matrix estimation as an empirical-loss problem and graphon estimation as an integrated-loss problem.
  • 1.2 Our results: The paper derives non-asymptotic L2 graphon-estimation rates for step-function and smooth graphon classes, including regimes where graphon rates are slower than probability-matrix rates.For step-function graphons, it also provides a matching minimax lower bound.

2 Probability matrix estimation

The paper estimates network probability matrices with block-constant least squares methods and establishes oracle inequalities and optimal rates, including sparse-network regimes. It also derives graphon-model rates whose behavior depends on smoothness, sparsity, and latent-variable variability.

  • Least squares estimators: The block-constant least squares estimator approximates the probability matrix by fitting connection probabilities and node partitions, while the restricted version additionally controls the maximum fitted probability.The ordinary estimator restricts community sizes through n0; the restricted estimator allows unbalanced partitions but imposes an l∞ radius.
  • Oracle inequalities: The estimators satisfy oracle inequalities comparing their Frobenius risk with the best block-constant approximation of the true probability matrix.The restricted estimator’s bound applies to unbalanced partitions and arbitrarily small maximum connection probabilities, under a known upper bound r.
  • Oracle inequalities: A data-driven upper bound for the restricted estimator can exceed the true maximum probability, but estimating it from edge density multiplies the risk rate by an unbounded sequence.The choice uses an inflated edge-density-based radius rn, with the price of a factor un such as log log n.
  • Stochastic block models: For stochastic block models, the paper extends minimax-rate results to arbitrary sparsity levels ρn, with the restricted estimator achieving the rate when r is proportional to ρn.The lower bound applies for all k and 0 < ρn ≤ 1; the ordinary estimator achieves the rate under balanced-partition and sparsity conditions.
  • Stochastic block models: In very sparse graphs, the minimax estimation rate is of order ρn/n^2, and simple estimators such as the zero estimator become competitive.The paper characterizes this regime as nearly trivial because both the null and constant least squares estimators attain the sparse-scale behavior.
  • Smooth graphons: For smooth graphons, the resulting probability-matrix rates depend on smoothness only for α in (0,1) and sufficiently non-sparse networks, and are minimax optimal when ρn is at least of order n^-1.The graphon results use α-Hölder smoothness and cover 4/n < ρn ≤ 1, with the rate’s smoothness dependence disappearing in sufficiently sparse settings.

3 Graphon estimation problem

The paper transfers probability-matrix estimation results to graphon estimation, where latent design variability creates an additional agnostic error. For step and smooth graphons, the resulting rates depend on sparsity, approximation, estimation, and agnostic-error regimes.

  • 3.1 From probability matrix estimation to graphon estimation: Graphon estimation uses empirical graphons built from probability-matrix estimators, evaluated modulo measure-preserving transformations.The construction converts an estimator of Θ0 into an estimator of f0 = ρnW0, while the quotient-space distance handles graphon non-identifiability.
  • 3.1 From probability matrix estimation to graphon estimation: The integrated-risk bound separates probability-matrix estimation error from agnostic error caused by unobserved latent design points.The agnostic term measures the distance between the true graphon and its discretized version sampled at latent variables.
  • 3.2 Step function graphons: For step graphons, minimax bounds are optimal up to a logarithmic factor in k in one regime, and the rates split into three sparsity regimes.The regimes identify whether agnostic error, probability-matrix estimation error, or a null-estimator rate dominates.
  • 3.2 Step function graphons: The step-graphon bounds match probability-matrix rates in some regimes but can be slower when latent-design uncertainty drives the risk.The lower bound establishes optimality with respect to the graphon distance up to a log(k) factor; the k = 1 case requires separate treatment.
  • 3.3 Smooth graphons: For smooth graphons, the rates depend on smoothness α and sparsity, matching probability-matrix rates in sufficiently sparse settings.When ρn ≤ n^(α−1) log(ρnn), the convergence rate is of order ρn log(ρnn)/n; for denser settings, agnostic effects can produce slower rates.

4 Proofs

The proofs control least-squares estimation error by decomposing it into clustering and Bernoulli-noise components. Concentration inequalities, unions over partitions, and covering arguments yield the required bounds.

  • 4 Proofs: The proof decomposes the estimation error into misclustering error and Bernoulli-noise error, which are bounded separately.The decomposition writes the inner product with the noise matrix as terms (I) and (II).
  • 4 Proofs: Bernstein’s inequality and union bounds control deviations over all admissible node assignments.The number of assignments is bounded by |Z_n,k,n0| ≤ k^n, enabling simultaneous control.
  • 4 Proofs: Finite Frobenius nets and covering-number bounds control the noise supremum over block-constant matrix classes.The construction uses a 1/4-net and obtains logarithmic covering complexity of order k^2.
  • 4 Proofs: The resulting bounds combine approximation control, concentration, and norm comparisons to complete the proposition.The proof relates the fitted estimator to its best Frobenius approximation and integrates the tail bounds.

4.2 Proof of Proposition 2.3

The proof of Proposition 2.3 handles restricted least-squares estimation by controlling a supremum over matrices with bounded entrywise and Frobenius norms. Multiscale nets and Bernstein bounds produce the stated noise estimate.

  • 4.2 Proof of Proposition 2.3: The restricted proof bounds the noise term over a class constrained by both sup norm 2r and a Frobenius-radius condition.This converts the estimator’s optimization error into a supremum of ⟨Θ,E⟩ over a controlled matrix set.
  • 4.2 Proof of Proposition 2.3: A multiscale finite approximation uses Frobenius nets, dyadic radii, and sign matrices to approximate the constrained class.The construction defines εq = 2^q r and discretizes block-level corrections with entries in {−1,0,1}.
  • 4.2 Proof of Proposition 2.3: Bernstein’s inequality and union bounds control all net elements and admissible assignments simultaneously.The complexity combines k^2 terms from block parameters with n log(k) terms from assignments.
  • 4.2 Proof of Proposition 2.3: The proof obtains a noise contribution bounded by Cr(n log(k) + k^2).This bound is combined with the preceding approximation and concentration inequalities to finish the proposition.

4.3 Proof of Proposition 2.4

The proof of Proposition 2.4 establishes minimax lower bounds by constructing separated probability matrices and controlling their Kullback–Leibler divergences. The constructions are adapted to the sparsity parameter ρn.

  • 4.3 Proof of Proposition 2.4: For the block-complexity term, matrices are constructed with squared Frobenius separation of order n^2(ρn(k/n)^2 ∧ ρn^2).The associated Kullback–Leibler divergences remain bounded by a quantity of order n^2ρn.
  • 4.3 Proof of Proposition 2.4: The logarithmic lower bound uses an analogous construction with modified connection probabilities.The proof adapts the corresponding dense-case construction to sparse probabilities.

4.4 Proof of Proposition 2.5

The proof constructs a balanced partition by ordering latent variables, then uses block averages and approximation bounds to establish Proposition 2.5.

  • Balanced partition: A balanced partition assigns n0 elements to each of the first k−1 classes and n0+r elements to the last class.Here n=n0k+r with 0≤r<n0.
  • Block averaging: The estimator is formed by taking block averages over the blocks induced by this partition.
  • Approximation control: Ordering the latent variables ensures that indices within the same block lie within 2n0 positions of one another.This enables application of the stated regularity lemma.
  • Conclusion: The resulting bound, combined with the preceding inequality and k=⌊n/n0⌋, proves the proposition.

4.5 Proof of Proposition 3.2

The proof compares ordered graphon representations with empirical graphons, controlling discrepancies from latent-group frequency fluctuations and diagonal entries.

  • Ordered representations: The construction replaces an arbitrary graphon by an ordered isomorphic version and compares it with an ordered empirical graphon.
  • Diagonal correction: The diagonal correction contributes at most ρ_n^2/n to the expected squared distance.
  • Mass matching: A measurable relabeling function aligns population and empirical group masses, with unmatched intervals quantified by m+ and m−.The construction uses equality m+=m− to reassign the unmatched mass.
  • Graphon discrepancy: The aligned graphons differ only on intervals associated with group-frequency mismatches, whose discrepancy is bounded by 2m+.
  • Frequency fluctuations: Binomial frequency fluctuations provide the expectation bound needed to control the graphon distance.

4.6 Proof of Proposition 3.5

The proof bounds graphon distance by restricting the relabeling search to interval permutations and ordering observations by their latent variables.

  • Relabeling: The proof upper-bounds the infimum over measure-preserving bijections using bijections induced by permutations of the empirical intervals.
  • Latent ordering: The selected permutation orders the latent variables increasingly, matching empirical interval positions to latent-variable ranks.
  • Error decomposition: Regularity of the graphon controls the first discrepancy term after this ordering, while the second term is handled separately.
  • Conclusion: Squaring, integrating, and taking expectations combines the two contributions into the desired bound.

4.7 Proof of Corollary 2.7

The corollary applies earlier propositions under balanced partitions and a sparsity condition, yielding the restricted least-squares bound.

  • Assumptions: Balanced-partition assumptions and ρ_n≥Ck log(k)/n allow Proposition 2.1 to be applied as in Corollary 2.2.
  • Error control: Proposition 2.5 bounds the expectation of the first term in the resulting error decomposition.
  • Final bound: The restricted least-squares bound follows by combining Propositions 2.3 and 2.6 under ρ_n<n^(α∧1)−1.

4.8 Proof of Corollary 3.3

The proof controls random block sizes in the balanced graphon model and combines this concentration with earlier propositions to establish the corollary.

  • Proof of Corollary 3.3: Balanced graphon block sizes are binomial, enabling Bernstein bounds for controlling every block simultaneously.For each block a, N_a has parameters (n, 1/k).
  • Proof of Corollary 3.3: All block sizes exceed n0 with probability greater than 1 − k exp(−Cn/k).
  • Proof of Corollary 3.3: Combining the block-size event with Propositions 2.1 and 3.2 yields the stated corollary, while the remaining term is negligible.
  • Proof of Corollary 3.3: The second part follows directly from Propositions 2.1 and 2.3.

4.9 Proof of Proposition 3.4

The proof constructs separated graphon hypotheses using perturbed step functions, then controls their statistical indistinguishability through latent-design randomness and divergence bounds.

  • Proof of Proposition 3.4: The lower bound is reduced to three separate minimax lower bounds, with cases handled for k = 2 and sufficiently large multiples of 16.
  • Hypothesis construction: A symmetric Rademacher matrix generates connection probabilities Q = (J + B)/2 for the step-function graphon hypotheses.The matrix construction is probabilistic because the required second property is difficult to verify for Hadamard matrices.
  • Indistinguishability: The difficulty in distinguishing hypotheses is driven by randomness in the latent design points rather than conditional edge randomness.
  • Hypothesis construction: A Varshamov–Gilbert-style subset provides many well-separated perturbation vectors, whose graphons are separated in the δ distance.The construction uses vectors with balanced ±ε coordinates and slightly unbalanced class weights.
  • Lower-bound conclusion: The resulting construction yields graphon pairs that remain statistically difficult to distinguish while being separated in δ, supporting the minimax lower bound.
  • Two-step case: For the two-step case, χ2(PW2, PW1) ≤ 1/4 when nρnε2 ≤ c0, while the likelihood conditions on pairs sharing the same latent position.

4.10 Technical lemmas

The technical lemmas establish concentration and approximation steps used to control block-constant matrix constructions and related estimator quantities.

  • Technical lemmas: Order-statistic spacings are analyzed through Beta distributions, yielding the stated spacing bound.
  • Technical lemmas: The approximation error is bounded by separating the scale discrepancy from the normalized matrix approximation error.
  • Technical lemmas: The proof discretizes a normalized matrix using a net and selects block-constant approximations under the estimated partition.
Loading 1507.04118v4…