Nonparametric estimation and testing of exchangeable graph models

Justin Yang, Christina Han, Edoardo M. AiroldiAISTATS 2014 · OpenReview

Abstract

Exchangeable graph models (ExGM) are a nonparametric approach to modeling network data that subsumes a number of popular models. The key object that defines an ExGM is often referred to as a graphon, or graph kernel. Here, we make three contributions to advance the theory of estimation of graphons. We determine conditions under which a unique canonical representation for a graphon exists and it is identifiable. We propose a 3-step procedure to estimate the canonical graphon of any ExGM that satisfies these conditions. We then focus on a specific estimator, built using the proposed 3-step procedure, which combines probability matrix estimation by Universal Singular Value Thresholding (USVT) and empirical degree sorting of the observed adjacency matrix. We prove that this estimator is consistent. We illustrate how the proposed theory and methods can be used to develop hypothesis testing procedures for models of network data.

Introduction

In network science, researchers often seek to infer the underlying generative rules from a single observed snapshot of a graph. Exchangeable Graph Models (ExGMs) offer a powerful nonparametric framework for this task. At the core of an ExGM is the graphon ($W$), a symmetric, measurable function $W: [0, 1]^2 \to [0, 1]$ that defines the probability of an edge between two nodes based on their latent characteristics.

Despite their theoretical appeal, ExGMs face two significant challenges:

  1. Identifiability: Multiple graphon functions can generate statistically identical graph structures, complicating the estimation of a "true" underlying function.
  2. Global Estimation: Most existing methodologies focus on estimating the probability matrix (local edge probabilities) rather than the global functional form of the graphon, which is essential for cross-network comparison and growth prediction.

The 3-Step Estimation Framework

The authors introduce a modular 3-step procedure designed to estimate the canonical representation of a graphon:

  1. Probability Matrix Estimation: The first step involves estimating the edge probabilities ($\hat{P}$) from the observed adjacency matrix. The authors advocate for Universal Singular Value Thresholding (USVT), a technique that denoises the graph by retaining only the most significant singular values.
  2. Latent Variable Estimation: Since latent node positions are unobserved, the authors utilize empirical degree sorting. They demonstrate that the relative rank of a node’s degree serves as a robust proxy for its latent position.
  3. Smoothing (Optional): To further refine the estimate, a smoothing algorithm, such as Total Variation Minimization (TVM), can be applied to the resulting function.

The core of this research focuses on the USVT-A procedure, which combines the first two steps to provide a computationally efficient and theoretically grounded estimator.

Theoretical Contributions and Identifiability

A primary contribution of this work is the formalization of a "degree-identifiability condition." The authors prove that if a graphon possesses an absolutely continuous degree distribution, it has a unique canonical representation. This provides the necessary mathematical foundation for functional estimation.

Furthermore, the paper highlights that simple degree sorting—even when derived from a noisy adjacency matrix—is a remarkably consistent method for recovering the latent ordering of nodes. This insight simplifies the estimation process significantly compared to more complex latent variable models.

Empirical Performance and Consistency

The proposed USVT-A estimator is mathematically proven to be consistent: as the network size ($N$) increases, the Mean Square Error (MSE) of the estimate converges to zero. This theoretical result is supported by extensive simulations using quadratic and logistic graphons.

Table 1: Mean Square Error (MSE) comparison of various estimators across different network sizes (N) for a quadratic graphon.

As shown in the simulation results (see Table 1), the USVT-A estimator significantly outperforms "vanilla" sorting methods (A-A). While the addition of a third smoothing step (e.g., USVT-A-TVM) provides marginal improvements, the 2-step USVT-A process captures the vast majority of the structural information.

Practical Hypothesis Testing

The computational efficiency of the USVT-A estimator enables principled hypothesis testing for large-scale networks. By leveraging Monte Carlo simulations, researchers can determine if an observed network aligns with a specific theoretical model.

Figure 1: Distribution of a test statistic T used in hypothesis testing, illustrating the density of values obtained through simulation.

This approach allows for the development of goodness-of-fit tests that were previously computationally prohibitive for nonparametric graph models.

Conclusion

This work advances the field of network modeling by providing a consistent, efficient, and identifiable framework for graphon estimation. While the current proofs assume graphon continuity and focus on dense graphs, the modularity of the 3-step procedure offers a clear path for future extensions into sparse regimes and discrete network structures.

Summary updated

Abstract

Exchangeable graph models (ExGM) are a nonparametric approach to modeling network data that subsumes a number of popular models. The key object that defines an ExGM is often referred to as a graphon, or graph kernel. Here, we make three contributions to advance the theory of estimation of graphons. We determine conditions under which a unique canonical representation for a graphon exists and it is identifiable. We propose a 3-step procedure to estimate the canonical graphon of any ExGM that satisfies these conditions. We then focus on a specific estimator, built using the proposed 3-step procedure, which combines probability matrix estimation by Universal Singular Value Thresholding (USVT) and empirical degree sorting of the observed adjacency matrix. We prove that this estimator is consistent. We illustrate how the proposed theory and methods can be used to develop hypothesis testing procedures for models of network data.
BibTeX
@inproceedings{yang2014nonparametric,
  author = {Justin Yang and Christina Han and Edoardo M. Airoldi},
  title = {{Nonparametric estimation and testing of exchangeable graph models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2014},
  url = {https://openreview.net/forum?id=u9hUr2v7iY},
}
Figure