PaperlayerView exact revision on arXiv

Source-linked AI summary

A Consistent Histogram Estimator for Exchangeable Graph Models

Stanley H. Chan, Edoardo M. Airoldi

arXiv:1402.1888v2stat.ME

TL;DR

As networks grow more complex, fitting them with particular parametric models becomes increasingly challenging. SAS estimates graphons by sorting empirical degrees and smoothing a histogram with total variation minimization. The paper reports favorable simulation comparisons and consistent estimates on large real networks.

  • Problem

    As network complexity increases, fitting data with a particular parametric model becomes more challenging.

    Source: §1 · p. 1

  • Method

    SAS sorts nodes by empirical degree, forms a histogram of the sorted graph, and smooths it using total variation minimization.

    Source: §3 · p. 6, §3.2 · p. 9

  • Results

    SAS outperforms USVT and SBA in simulations, and returns consistent graphon estimates on large-scale real networks.

    Source: §6 · pp. 17–18

  • Takeaways & Limitations

    The paper presents SAS as a consistent and efficient graphon estimation algorithm evaluated on simulations and real networks.

    Source: §6 · p. 17

    The consistency analysis assumes sparse gradients; the paper notes that a graphon’s discretized gradient need not be sparse in general.

    Source: Total Variation Minimization · p. 9, §4.3 · p. 13

Abstract

from arXiv · show

Exchangeable graph models (ExGM) subsume a number of popular network models. The mathematical object that characterizes an ExGM is termed a graphon. Finding scalable estimators of graphons, provably consistent, remains an open issue. In this paper, we propose a histogram estimator of a graphon that is provably consistent and numerically efficient. The proposed estimator is based on a sorting-and-smoothing (SAS) algorithm, which first sorts the empirical degree of a graph, then smooths the sorted graph using total variation minimization. The consistency of the SAS algorithm is proved by leveraging sparsity concepts from compressed sensing.

1. Introduction.

Increasing network complexity makes fitting a particular parametric model more challenging. The paper proposes a histogram-based SAS graphon estimator and reports consistency under stated conditions alongside favorable simulation results.

1. Introduction.

  • As network complexity increases, fitting data with a particular parametric model becomes more challenging.The paper names exponential random graph, stochastic block, mixed membership, latent space, and graphlet models as examples.Source: §1 · p. 1

1.1. Non-parametric representation of a graph.

  • A graphon characterizes an exchangeable graph model and provides a basis for comparing networks generated from the same model across sample sizes.The paper describes a graphon as a continuous function that generates random graphs.Source: §1.1 · p. 2

1.2. Related work.

  • Earlier approaches either condition on node arrangement and yield noncanonical estimates, or face computational or consistency limitations.The paper presents SAS as sorting empirical degrees, computing a sorted-graph histogram, and smoothing it by total variation minimization.Source: §1.2 · pp. 2–3, §1.3 · p. 3

1.3. Contributions.

  • SAS is reported consistent with MSE O((log n)/n) when the true graphon is Lipschitz and has sparse gradients.The paper also evaluates the estimator on simulation and real-network data.Source: §1.3 · p. 3

2. Graphons and identifiability.

The section introduces graphons as the functions underlying exchangeable graph models, then explains why equivalent models need not have uniquely identified graphon representations. Strict monotonicity of degrees provides the stated unique-representation condition.

2.1. Definition of a graphon.

  • A graphon w is a symmetric measurable function from [0,1]^2 to [0,1], with edges conditionally sampled as Bernoulli(w(U_i,U_j)) for iid Uniform[0,1] latent variables.Source: §2.1 · p. 4

2.2. Identifiability of a graphon.

  • Measure-preserving transformations can yield equivalent exchangeable graph models, so graphons may not be uniquely identified from the model they define.The section gives w(u, v) = uv and w′(u, v) = (2u mod 1)(2v mod 1) as an example defining the same model without such a transformation relating them.Source: §2.2 · p. 5
  • A graphon has a unique representation if and only if its canonical degree function is strictly increasing or decreasing; the paper assumes this condition thereafter.Twin-free alone is necessary but not sufficient for identification.Source: §2.2 · pp. 5–6

3. Proposed SAS Algorithm.

SAS estimates a graphon by ordering nodes using empirical degrees and smoothing a histogram of the reordered graph. Its smoothing stage produces a blockwise estimate with reduced effective degrees of freedom.

3. Proposed SAS Algorithm.

  • SAS first sorts the graph by empirical degree, then computes a histogram and applies total variation minimization to estimate a smooth surface.The algorithm is motivated by convergence of sorted empirical degrees toward the canonical degree distribution as graph size grows.Source: §3 · pp. 6–7

3.1. Stage 1: Sorting.

  • The sorting permutation orders empirical degrees monotonically, but it can differ from the oracle permutation that orders the latent node labels.The oracle permutation is defined by increasing latent variables U_i.Source: §3.1 · pp. 7–8

3.2. Stage 2: Smoothing.

  • The histogram approximates the sorted adjacency matrix with a piecewise-constant block model whose effective degrees of freedom are k × k, where k = ⌊n/h⌋.Here h is the size of each block.Source: §3.2 · pp. 8–9

Total Variation Minimization

Total variation minimization refines the histogram estimate by imposing a sparse-gradient assumption on the graphon. The resulting k × k estimate is expanded to the graphon estimate’s n × n size.

Total Variation Minimization

  • The refinement assumes the graphon discretized on a k × k grid has small total variation, analogous to sparse gradients in natural images.The text identifies horizontal and vertical finite differences as the gradient components.Source: Total Variation Minimization · p. 9
  • The refinement minimizes total variation while controlling fidelity to the histogram through the parameter ε.The paper solves this minimization problem using ADMM.Source: Total Variation Minimization · p. 9
  • The k × k smoothed estimate is expanded to n × n using the Kronecker product with an h × h all-ones matrix.This produces the final estimate at the same size as the true graphon.Source: Total Variation Minimization · p. 9
  • The stated overall complexity is O(n log n + k^2 log k^2) multiplications plus O(n^2) additions.The analysis combines degree computation, sorting, histogram computation, and the ADMM step.Source: §3.3 · p. 10

4. Theoretical Properties of the SAS Algorithm.

The analysis bounds the errors contributed by empirical-degree sorting, histogram approximation, and total-variation smoothing. Together, these bounds establish consistency under stated regularity and gradient-sparsity conditions.

4.1. Consistency of empirical degree sorting.

  • A two-sided Lipschitz condition links differences in oracle positions to empirical-degree differences, and conversely bounds position differences from degree differences.This is the basis for controlling errors from empirical-degree sorting.Source: §4.1 · pp. 11–12, §4 · p. 11

4.2. Consistency of the histogram estimator.

  • The analysis bounds the discrepancy between the empirical histogram and ideal histogram, and between the ideal histogram and the graphon’s step approximation.These are separate contributions to the histogram-estimation error.Source: §4.2 · p. 12

4.3. Consistency of total variation smoothing.

  • Total-variation smoothing controls estimation error through the observation perturbation and the sparse-approximation error of the step function’s gradient.The sparse-approximation term is zero when Hw is s-sparse in gradient, an assumption the paper says is often reasonable for practical consideration.Source: §4.3 · p. 13

4.4. Overall consistency.

  • Under Lipschitz conditions on the graphon and degree function, and gradient sparsity of Hw, SAS MSE tends to zero as n grows when k/n tends to zero.Here k is the number of histogram blocks.Source: §4.4 · p. 14

5. Experimental results.

In simulations, SAS achieves the lowest MSE among the three methods; on two real networks, its graphon estimates reveal network structure and are computed in seconds.

5.1. Simulations.

  • Testing spans low- and high-rank graphons, including eigenmodel, logistic-model variant, and latent-distance examples.Ranks were measured numerically using a 1000 × 1000 discretization.Source: §5.1 · p. 14, Table 1 · p. 14
  • Across 10 testing graphons, SAS achieves the lowest MSE among SAS, USVT, and SBA, averaged over 50 trials at n=200 and n=1000.Table 2 reports mean squared error comparisons.Source: Table 2 · p. 15, §5.1 · p. 16
  • SAS uses h = log n, while SBA receives an oracle MSE-minimizing h; USVT and SBA are run after SAS's sorting step.Source: §5.1 · p. 15
  • Figure 4's runtime comparison indicates that SAS has significantly lower complexity than USVT.The comparison was run on an Intel 3.5GHz machine with 16GB RAM using Windows 7 and MATLAB R7.12.0.Source: §5.1 · p. 16

5.2. Real data analysis.

  • For ca-AstroPh, the estimate shows concentrated close collaborations and small diagonal communities; soc-Epinions-1 shows influential nodes interacting repeatedly.Source: §5.2 · p. 16

5.1. Simulations.

  • For Graphons 5 and 10, SAS retains true-graphon features with lower MSE; USVT fares worse on high-rank Graphon 10, while SBA favors few communities.The SBA comparison uses an oracle binwidth that minimizes MSE.Source: §5.1 · p. 16, Figure 3 · p. 17

5.2. Real data analysis.

  • 20 seconds for ca-AstroPh and 170 seconds for soc-Epinions-1 completed the real-network estimates using unoptimized MATLAB code.The authors describe these runtimes as evidence of scalability to larger networks.Source: §5.2 · p. 17

6. Conclusion.

The conclusion presents SAS as a consistent, efficient graphon estimator that outperforms two methods in simulations and returns consistent estimates on large real networks. The appendix describes its total-variation optimization and gives the ADMM complexity bound.

6. Conclusion.

  • In simulations, SAS outperforms universal singular value thresholding and stochastic blockmodel approximation.The conclusion reports these comparisons without giving numerical values.Source: §6 · p. 17
  • SAS sorts nodes by empirical degree, then estimates a smooth graphon with a histogram and total variation minimization.The conclusion describes SAS as a consistent and efficient graphon estimation algorithm.Source: §6 · p. 17
  • On large-scale real networks, SAS returns consistent graphon estimates.Source: §6 · p. 18

APPENDIX A: TOTAL VARIATION MINIMIZATION

  • The ADMM algorithm has complexity O(k^2 log k^2), with the bound set by its 2D fast Fourier transform subproblem.The inverse in the br-subproblem can be executed efficiently using fast Fourier transform operations.Source: Appendix A · p. 21

B.1. Proof of Lemma 1.

The proof proceeds in forward and converse directions, invoking concentration and Lipschitz arguments. The supplied proof passages identify these tools but do not state the full lemma or its conclusion.

  • The forward direction uses a Dvoretzky argument and then a Lipschitz bound.Source: §B.1 · pp. 21–22
  • A Hoeffding inequality gives an event with probability at least 1 − 4 exp{−2nδ^2}.Source: §B.1 · p. 22
  • The converse direction begins with an inverse-Lipschitz argument and also invokes Dvoretzky and Hoeffding bounds.Source: §B.1 · pp. 22–23

B.2. Proof of Lemma 2.

The proof defines a continuous step-function version of the histogram graphon on an equal partition of the unit square and proceeds to bound its approximation error.

  • The proof defines wstep as a continuous version of the histogram graphon on an equal partition of [0, 1].Source: §B.2 · p. 24
  • Within each partition cell, wstep takes the corresponding histogram value.Source: §B.2 · p. 24
  • The proof next bounds the approximation error between the step-function construction and its target.Source: §B.2 · p. 24

B.3. Proof of Lemma 3.

These appendix proofs bound discrepancies involving the ordered empirical graphon, then use intermediate lemmas in an MSE decomposition to complete the theorem proof.

B.3. Proof of Lemma 3.

  • The Lemma 3 proof bounds the discrepancy between the true graphon and the empirical graphon ordered by the estimated permutation, using the graphon's Lipschitz condition.Source: §B.3 · p. 25

B.5. Proof of Theorem 3.

  • Theorem 3's proof decomposes the MSE and bounds its terms using Lemmas 5, 3, 4, and 2.Source: §B.5 · p. 27
Loading 1402.1888v2…