Maximum entropy based testing in network models: ERGMs and constrained optimization

1. Problem Statement

The paper addresses the fundamental problem of statistical inference in random network models, specifically focusing on Goodness-of-Fit (GoF) and Two-Sample testing.

• Goodness-of-Fit: Determining whether an observed network (or a collection of networks) originates from a specific random graph model with predefined parameters (e.g., testing if a network follows an Erdős-Rényi model with edge probability $p_0$ or a specific Exponential Random Graph Model (ERGM)).
• Two-Sample Testing: Determining whether two independent samples of networks are generated from the same underlying distribution.

Existing methods often rely on raw subgraph counts, adjacency matrices, or spectral properties. This paper proposes a novel approach grounded in the Maximum Entropy (MaxEnt) principle, where the test statistics are derived from the Lagrange multipliers associated with a constrained entropy maximization problem.

2. Methodology

The core methodology involves framing hypothesis testing as a constrained optimization problem on the space of probability distributions over graphs.

A. The Optimization Framework

Given $n$ i.i.d. samples of graphs $G_1, \dots, G_n$, the authors define a centered motif count statistic $h(G) = T(H, G) - h_0$, where $T(H, G)$ is the number of copies of a subgraph (motif) $H$ in $G$, and $h_0$ is a target value (usually the expected count under the null hypothesis).

The authors seek the probability distribution $w = (w_1, \dots, w_n)$ over the samples that maximizes the empirical entropy subject to the constraint that the expected value of the statistic is zero:
$$\max_{w} -\sum_{i=1}^n w_i \log w_i \quad \text{subject to} \quad \sum_{i=1}^n w_i h(G_i) = 0, \quad \sum w_i = 1, \quad w_i \ge 0.$$

Using Lagrange multipliers, the optimal weights are found to be:
$$\hat{w}_i = \frac{e^{-\hat{\lambda}_n h(G_i)}}{\sum_{j=1}^n e^{-\hat{\lambda}_n h(G_j)}}$$
where $\hat{\lambda}_n$ is the optimal Lagrange multiplier, determined as the root of the estimating equation:
$$\sum_{i=1}^n h(G_i) e^{-\hat{\lambda}_n h(G_i)} = 0.$$

B. The Test Statistic

The central insight of the paper is that the optimal Lagrange multiplier $\hat{\lambda}_n$ itself serves as the test statistic.

• Under the null hypothesis ($H_0$), the true expected value of the statistic is zero, implying the true Lagrange multiplier $\lambda^\circ = 0$.
• Under the alternative hypothesis ($H_1$), $\lambda^\circ \neq 0$.
• The authors establish the asymptotic distribution of $\hat{\lambda}_n$ (specifically, its consistency and asymptotic normality) to construct valid statistical tests.

C. Analytical Tools

The analysis relies heavily on advanced tools from statistical physics and probability theory:

1. Graph Limit Theory (Graphons): Used to analyze the dense regime where the number of vertices $N \to \infty$.
2. Nonlinear Large Deviation Theory: Specifically the log-sum-exp approximation framework (Chatterjee & Dembo, 2016) to handle the concentration of measure in dense networks.
3. Poisson Approximation: Used for the sparse regime where subgraph counts converge to Poisson distributions.
4. Z-Estimator Theory: Used to derive the asymptotic normality of the root $\hat{\lambda}_n$.

3. Key Contributions

1. Novel Test Statistic: The paper introduces the use of the Lagrange multiplier from a constrained entropy maximization as a test statistic for network data. This connects network inference to classical econometric Lagrange Multiplier (Score) tests, but extends them to the non-Euclidean, high-dimensional setting of random graphs.
2. Unified Framework: It provides a unified entropy-based framework applicable across different network growth regimes:
   • Fixed Size: Graphs with a fixed number of vertices.
   • Sparse Regime: Graphs where edge probability $p \to 0$ (e.g., sparse Erdős-Rényi).
   • Dense Regime: Graphs where $p = \Theta(1)$ (e.g., dense Erdős-Rényi and subcritical ferromagnetic ERGMs).
3. Technical Breakthroughs:
   • Proves the existence and uniqueness of the Lagrange multiplier root in all regimes.
   • Establishes consistency and asymptotic normality of $\hat{\lambda}_n$ in the sparse and fixed-size regimes.
   • Derives sharp convergence rates ($O(m^{-2})$) for the dense regime, where standard Central Limit Theorems for subgraph counts do not directly apply due to phase transition complexities in ERGMs.

4. Main Results

A. Fixed Number of Vertices

• Result: $\hat{\lambda}_n$ is consistent and asymptotically normal.
• Test: A GoF test is constructed where the rejection region is based on $\sqrt{n}\hat{\lambda}_n$. The test is shown to be level $\alpha$ and consistent.

B. Sparse Regime ($N \to \infty, p \to 0$)

• Context: Applied to Erdős-Rényi graphs $G(N, p)$ where subgraph counts follow a Poisson distribution.
• Result: The centered and scaled Lagrange multiplier satisfies a Central Limit Theorem.
  $$\sqrt{n}(\hat{\lambda}_n - \lambda^\circ) \xrightarrow{d} N(0, \sigma^2)$$
• Application: This yields a consistent GoF test for the edge probability $p$ and a Two-Sample test for comparing two sparse networks.

C. Dense Regime ($N \to \infty, p = \Theta(1)$)

• Context: Applied to ERGMs in the subcritical (ferromagnetic) regime and dense Erdős-Rényi graphs.
• Challenge: The standard CLT fails; the behavior is governed by variational problems over graphons (free energy).
• Result: The authors prove that $m^2 (\hat{\lambda}_n - \lambda^\circ)$ converges to a deterministic constant (or zero) depending on the hypothesis.
  • If $H_0$ holds ($\lambda^\circ = 0$), the convergence rate is $o(m^{-2})$.
  • If $H_1$ holds ($\lambda^\circ < 0$), the difference scales as $m^{-2}$.
• Test: A Two-Sample test is constructed by comparing the Lagrange multipliers from two samples. The test statistic $m^2 |\hat{\lambda}_n - \tilde{\lambda}_n|$ diverges to infinity if the parameters differ, allowing for consistent testing.

5. Significance and Implications

• Theoretical Unification: The paper bridges the gap between statistical mechanics (MaxEnt, ERGMs, free energy) and statistical inference (hypothesis testing). It demonstrates that the "dual" variable in entropy maximization (the Lagrange multiplier) carries the necessary statistical information for testing.
• Connection to Econometrics: It revitalizes the classical Lagrange Multiplier (Score) test for network data, showing that despite the complexity of graph limits, the asymptotic behavior of the multiplier remains a powerful inferential tool.
• Robustness: The methodology is robust across different sparsity levels, offering a single conceptual strategy (constrained optimization) for diverse network asymptotics.
• Future Directions: The authors suggest that this framework can be extended to vector-valued Lagrange multipliers for testing multiple parameters simultaneously in general ERGMs and potentially to the supercritical regime of ERGMs, which remains a challenging open problem.

In summary, this paper establishes a rigorous theoretical foundation for using constrained entropy maximization as a primary tool for hypothesis testing in random networks, leveraging the asymptotic properties of the associated Lagrange multipliers to derive consistent and powerful tests for both sparse and dense graph regimes.