Source-linked AI summary
Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
Edoardo M Airoldi, Thiago B Costa, Stanley H Chan
TL;DR
The paper addresses how to infer an underlying graphon from observed networks. It proposes a computationally efficient stochastic blockmodel approximation, proving consistency and reporting effective estimation of block-structured graphons. The method requires at least two independently observed graphs and specific conditions on observations and precision.
Problem
The paper asks whether a graphon can be consistently estimated from a sequence of observed directed graphs as the number of vertices grows.
Method
The SBA algorithm clusters unknown vertex labels using estimated graphon-slice distances and then estimates block values with an empirical histogram.
Results
The estimated graphon is consistent, with expected MAE and MSE both converging to zero as n approaches infinity.
Takeaways & Limitations
SBA provides a computational tool that effectively estimates block-structured graphons while retaining consistency despite greedy, non-global clustering.
Takeaways & Limitations
The analysis requires at least two independently observed graphs, assumes piecewise Lipschitz graphons, and requires S to grow proportionally with n.
Abstract
from arXiv · showhide
Non-parametric approaches for analyzing network data based on exchangeable graph models (ExGM) have recently gained interest. The key object that defines an ExGM is often referred to as a graphon. This non-parametric perspective on network modeling poses challenging questions on how to make inference on the graphon underlying observed network data. In this paper, we propose a computationally efficient procedure to estimate a graphon from a set of observed networks generated from it. This procedure is based on a stochastic blockmodel approximation (SBA) of the graphon. We show that, by approximating the graphon with a stochastic block model, the graphon can be consistently estimated, that is, the estimation error vanishes as the size of the graph approaches infinity.
1 Introduction
The paper develops a computational tool for estimating graphons, motivated by the need to reveal hidden graph structure and make inference from observed networks. It uses a stochastic blockmodel approximation and targets consistency as graph size grows.
- Graphons are measurable limit objects that preserve many local and global properties of convergent graph sequences.
- A graphon generates a random graph by assigning each vertex a Uniform[0,1] label and connecting vertices with probability w(u_i, u_j).
- The central problem is whether a graphon can be estimated consistently from 2T observed directed graphs as n approaches infinity.
- The proposed SBA procedure approximates the graphon with a two-dimensional step function, equivalent to a stochastic block model.
- The SBA estimate is defined only up to node permutations, which does not affect consistency relative to the generating graphon.
2 Stochastic blockmodel approximation: Procedure
The procedure approximates a piecewise-Lipschitz graphon with a stochastic blockmodel by clustering vertices whose graphon slices are similar, then estimating blockwise edge frequencies. A greedy, locally computed clustering remains consistent as the graph size grows while offering numerical efficiency.
- Assumptions: The method assumes a piecewise-Lipschitz graphon and permits asymmetric graphons, corresponding to directed random graphs.Symmetric graphons are included as a special case.
- Similarity measure: The distance d_ij measures similarity of both row and column graphon slices, which should be close when labels u_i and u_j are close.This supplies the basis for grouping vertices with similar connectivity profiles.
- Similarity estimation: The estimator b̂d_ij uses observed graphs to estimate d_ij and can replace all vertices outside i and j with a random subset while retaining the same asymptotic behavior.The resulting distance estimation can be performed locally in a neighborhood of the two vertices.
- Blockmodel approximation: The graphon is approximated by clustering labels into blocks and estimating each block pair’s value from the empirical frequency of edges between those blocks.Summed adjacency entries across block pairs estimate the expected number of linking edges.
- Greedy clustering: The greedy algorithm selects random pivots, assigns vertices with b̂d below Δ^2 to the pivot’s block, and iterates until all vertices are assigned.Its complexity is O(TSKn), where T is half the number of observations, S the neighborhood size, K the block count, and n the vertex count.
- Consistency: Although the greedy clustering is not globally optimal, the resulting estimated graphon is guaranteed to be consistent as n →∞.The paper presents the algorithm as a numerically efficient practical tool for estimating the true graphon.
3 Stochastic blockmodel approximation: Theory of estimation
The section establishes concentration and consistency of the stochastic blockmodel graphon estimator, while characterizing block-size trade-offs and parameter selection.
- 3.1 Concentration analysis of bdij: Theorem 1 shows that the pairwise estimator bdij is unbiased and concentrated around its expected value dij.The proof uses conditional independence across two independently observed graphs and Bernstein’s inequality.
- 3.1 Concentration analysis of bdij: The analysis requires at least 2 independently observed graphs because conditional independence is needed to separate the relevant probabilities.The estimator uses observations indexed by 2T graphs, with S denoting the neighborhood size.
- 3.2 Choosing the number of blocks: The accuracy parameter ∆ controls a trade-off between finer graphon approximation and sufficient vertices per block for reliable block-value estimation.Large ∆ yields fewer larger clusters, whereas small ∆ yields more smaller clusters; cross-validation selects ∆ by minimizing estimated risk.
- 3.3 Consistency of bw: The expected mean absolute error and mean squared error both converge to zero as n approaches infinity.Specifically, lim n→∞E[MAE(bw)] = 0 and lim n→∞E[MSE(bw)] = 0.
- 3.3 Consistency of bw: Theorem 3 establishes consistency by combining bounds from Lemmas 1 and 2 to show convergence of |bw(ui, uj) − w(ui, uj)|.The conditions S ∈ Θ(n) and the stated restriction on ∆ are needed for the exponential bounds to vanish or remain well behaved.
4 Experiments
Experiments compare SBA with USVT, LG, and OptSpace across graph size, block count, missing edges, and continuous graphons. SBA’s performance improves with more data, remains competitive as complexity and missingness increase, and depends on graphon structure.
- Experimental setup: SBA is evaluated against USVT, LG, and OptSpace across several graphon-estimation settings.The experiments cover graph size, number of blocks, missing edges, and continuous graphons.
- Accuracy with graph size and observations: MAE decreases as graph size grows, while additional observations T further reduce SBA’s estimation error.The graph-size comparison uses 200-vertex graphs for the observation-count analysis, averaged over 100 independent trials.
- Accuracy with block count: As the number of blocks K increases, estimation error rises, but SBA retains the lowest MAE among the compared algorithms.Each K setting uses n = 200 and T = 1, with results averaged over 100 trials.
- Missing edges: With more missing links, estimation error increases, while SBA outperforms its counterparts at a lower missing-link rate.The missing-edge experiment averages results over 100 independent trials.
- Continuous graphons: For continuous graphons, SBA performs better for high-rank w1, whereas USVT performs better for low-rank w2.Both algorithms improve as n grows, but the preferred method depends on the graphon’s structure.
5 Concluding remarks
The paper concludes that SBA is a computational tool for graphon estimation with a complete consistency analysis and empirical effectiveness on block-structured graphons.
- Method: SBA approximates a continuous graphon with a stochastic block model through label clustering followed by empirical histogram estimation.The algorithm first clusters unknown vertex labels using estimated graphon-slice distances, then constructs an empirical histogram.
- Theory: The paper derives a complete consistency analysis for the proposed algorithm.
- Empirical conclusion: Experiments find SBA effective for estimating block-structured graphons.
- Availability: An implementation of SBA is available online.
A Proofs for Section 3.1
These proofs establish unbiasedness and concentration properties for the distance estimator used in SBA, including separate treatment of directed and undirected graphs. The argument decomposes covariance terms into cases and applies concentration bounds.
- Estimator unbiasedness: The estimator bdij is unbiased for dij.Unbiasedness follows from unbiased component estimators and linearity of expectation.
- Graph types: The proof handles directed and undirected graphs separately when establishing the estimator’s probabilistic bound.
- Estimator construction: The quantities used in the distance estimator are defined through averages over a sampling neighborhood excluding the target vertices.The proof expresses dij and bdij in matching forms using the neighborhood S.
- Covariance decomposition: The covariance analysis separates three cases according to whether sampled indices match the target indices.Combining the three cases yields the stated covariance bound.
- Concentration: For directed graphs, independence of product variables supports concentration through Bernstein’s inequality and a union bound.The proof uses independence across the relevant products before applying the concentration argument.
B Proofs for Section 3.2
The proof bounds the probability that SBA estimates too many blocks by relating block separation to the Lipschitz structure of the ground-truth graphon. It uses interval partitioning, the pigeonhole principle, and a union bound.
- Theorem statement: Theorem 2 bounds the estimation event using accuracy parameter Δ and the algorithm’s estimated block count K.
- Lipschitz partition: A graphon with Lipschitz constant L and Q Lipschitz blocks is partitioned into Q R equal subintervals.Each ground-truth Lipschitz interval is divided into R subintervals, giving Q R total subintervals.
- Block-count bound: If K exceeds Q R, two pivots must lie in the same subinterval by the pigeonhole principle.Their true distance is then constrained by the subinterval width, while the algorithm enforces a larger estimated separation.
- Probability bound: The proof defines a bad event involving an excessively separated pivot pair and bounds its probability through event inclusion and a union bound.
C Proofs for Section 3.3
The proofs establish that blockwise graphon estimates concentrate around true block values and that the resulting estimator is consistent under stated parameter scaling. They also control approximation error for piecewise Lipschitz graphons and show both MAE and MSE vanish asymptotically.
- Concentration bounds: The analysis separates cases according to whether estimated blockwise values remain close to the corresponding ground-truth graphon values.The proof uses an event and its complement to control uniform blockwise deviations.
- Graphon approximation: The proof combines pivot proximity and Lipschitz regularity to bound differences between vertex-pair graphon values within estimated clusters.For piecewise Lipschitz graphons, separability and interval-wise arguments yield a uniform approximation bound.
- Concentration bounds: Hoeffding bounds control deviations of empirical block estimates from their Bernoulli means, with probability at most 2e^-2(2T|bBi||bBj|ε^2).The argument relies on independent Bernoulli observations across the 2T graphs for each vertex pair.
- Graphon approximation: The piecewise Lipschitz approximation satisfies sup_(x,y)∈[0,1]^2 h_ij(x,y) ≤ ε under the stated interval and smoothness construction.The proof reduces the separable bound to one-dimensional functions and controls each interval interior.
- Consistency: lim n→∞ E[MAE(bw)] = 0 and lim n→∞ E[MSE(bw)] = 0.The conclusion uses Δ_n→0 and Pr[E_n]→1, together with boundedness of the estimator in [0,1].
- Consistency: The asymptotic proof shows that the error terms vanish when S∈Θ(n) and the clustering parameter sequence satisfies the required scaling conditions.Small clusters are treated as asymptotically irrelevant, while sufficiently large clusters provide exponentially decreasing concentration terms.