Low-Rank Graphon Learning for Networks

1. Problem Statement

The paper addresses the challenge of estimating graphons (symmetric measurable functions that serve as limit objects for dense graph sequences) and their corresponding connection probability matrices ($P$) in large-scale networks.

• The Core Difficulty: While many existing methods estimate the connection probability matrix $P$ (e.g., via spectral methods or neighborhood smoothing), they often fail to simultaneously recover the underlying graphon function $f$ with the same structural consistency.
• Identification Issues: Graphon estimation suffers from non-identifiability due to measure-preserving transformations (node permutations).
• Low-Rank Gap: Many real-world networks (e.g., social, biological) exhibit low-rank structures (communities, latent memberships). Existing methods often treat the low-rank structure of $P$ and the graphon $f$ separately, leading to inconsistencies. There is a lack of unified frameworks that achieve sup-norm consistency (uniform error control) for both $P$ and $f$ in low-rank settings, particularly for sparse networks.

2. Methodology

The authors propose a novel Low-Rank Graphon Learning framework based on a truncated eigen-decomposition of the graphon.

Model Assumption

The graphon $f(u, v)$ is modeled as a rank-$r$ additive decomposition:
$$f(U_i, U_j) = \sum_{k=1}^r \lambda_k G_k(U_i)G_k(U_j)$$
where $U_i \sim \text{Uniform}(0,1)$ are latent variables, $\lambda_k$ are eigenvalues, and $G_k$ are orthogonal eigenfunctions. This model encompasses Stochastic Block Models (SBM) and Random Dot Product Graphs (RDPG) as special cases.

Estimation Strategy

The method employs a sequential algorithm based on subgraph counts (motifs) and interpolation, avoiding the need for iterative optimization or heavy spectral decomposition.

Step 1: Estimating Eigenvalues ($\lambda_k$) and Integrals

• Cycles: The authors utilize the counts of cycles of length $a$ ($C_i^{(a)}$) passing through node $i$. The expectation of these counts depends only on the eigenvalues $\lambda_k$, independent of the eigenfunctions $G_k$.
  $$E[C_i^{(a)}] \propto \sum_{k=1}^r \lambda_k^a$$
• By counting cycles of lengths $3$ to $r+2$, they solve a system of equations to recover $\hat{\lambda}_k$.

Step 2: Estimating Eigenfunctions ($G_k$)

• Paths: They utilize counts of simple paths of length $a$ starting at node $i$ ($L_i^{(a)}$). The conditional expectation of path counts depends on both $\lambda_k$ and $G_k(U_i)$.
  $$E[L_i^{(a)} | U_i] \propto \sum_{k=1}^r \lambda_k^a G_k(U_i) \int G_k(u) du$$
• Using the estimated $\hat{\lambda}_k$ from Step 1, they solve a linear system to estimate the values of $G_k(U_i)$ for each node.

Step 3: Graphon Recovery (Sorting and Interpolation)

• Rank-1 Case ($r=1$): The estimated values $\hat{G}_1(U_i)$ are sorted to align with the latent variable order (degree sorting). A piecewise linear interpolation is applied to reconstruct the monotonic canonical graphon function $\hat{f}^\dagger(u, v)$.
• Rank-$r$ Case ($r \ge 2$): The estimated vectors $(\hat{G}_1(U_i), \dots, \hat{G}_r(U_i))$ are sorted based on the first component $\hat{G}_1$. The other components are interpolated relative to the sorted first component to reconstruct the full graphon.

Step 4: Connection Matrix Estimation

• The connection probability matrix is estimated by plugging the reconstructed functions back into the model: $\hat{p}_{ij} = \sum \hat{\lambda}_k \hat{G}_k(U_i)\hat{G}_k(U_j)$.
• Complexity: A variant algorithm (Algorithm 3) uses matrix multiplication to count paths/cycles with repeated nodes, achieving a time complexity of $O(n^\omega)$ (where $\omega \approx 2.373$), significantly faster than the $O(n^3)$ required by standard SVD-based methods.

3. Key Contributions

1. Unified Framework: The first method to simultaneously estimate the low-rank connection probability matrix $P$ and the graphon function $f$ with the same rank, resolving the inconsistency found in prior separate estimation approaches.
2. Theoretical Guarantees (Sup-Norm):
   • Establishes sup-norm consistency (uniform convergence) for both $\hat{P}$ and $\hat{f}$, which is a stronger guarantee than the mean squared error (MSE) bounds common in literature.
   • Proves convergence rates of $O_p(\sqrt{\log(n)/n})$ for the connection matrix and graphon, matching minimax rates up to logarithmic factors.
3. Novel Theoretical Lemmas:
   • Derives sharp perturbation bounds for solutions to stochastic systems of equations.
   • Proves that scaled path counts from a node uniformly approximate its conditional expectation given the latent variable, forming the backbone of the eigenfunction estimation.
4. Computational Efficiency:
   • The method is tuning-free and scalable.
   • It outperforms spectral methods (like USVT) in sparse network regimes and avoids the convergence issues of power iteration methods.
5. Robustness: Demonstrates robustness to rank mis-specification (over-estimation) and performs well across dense and sparse network settings.

4. Experimental Results

• Simulation Studies:
  • Tested on 7 different graphon models (ranks 1, 2, and 3) with $n=2000$.
  • Accuracy: The proposed method consistently achieved the lowest Mean Squared Error (MSE) and maximum entrywise error compared to benchmarks like USVT, Sort-and-Smooth (SAS), Neighborhood Smoothing (N.S.), and Network Histogram (Nethist).
  • Sparse Networks: In sparse regimes ($\rho_n = n^{-1/2}$), the method significantly outperformed all competitors, whereas others (especially SAS and N.S.) failed or produced high errors.
  • Speed: The method was significantly faster than N.S. and Nethist, matching the speed of Power Iteration but with better theoretical guarantees.
• Real-World Applications:
  • Primary School Contact Data: Successfully identified a rank-4 structure, producing a connection matrix heatmap that aligned with known social interactions.
  • U.S. Political Blogs: Identified a rank-2 structure corresponding to the Liberal/Conservative divide, accurately capturing the community structure and predicting motif densities (triangles, squares) with lower error than competing methods.

5. Significance

This work bridges a critical gap in network analysis by providing a computationally efficient, theoretically rigorous method to recover both the generative mechanism (graphon) and the specific network realization (connection matrix) simultaneously.

• Practical Impact: The ability to estimate graphons in sup-norm allows for reliable prediction of higher-order network features (like motif densities and transitivity) and generalization to networks of different sizes, which is crucial for tasks like link prediction and community detection.
• Theoretical Advancement: By moving beyond average-error metrics to uniform convergence, the paper sets a new standard for the robustness of graphon estimators, particularly in sparse and low-rank settings where previous methods struggled.
• Scalability: The $O(n^\omega)$ complexity makes the approach viable for large-scale networks where traditional spectral methods are computationally prohibitive.