Research map / Learning theory and algorithms / Matrix and tensor methods
Low-Rank Graphon Learning for Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a low-rank additive graphon model estimated via subgraph counts (paths and cycles) and a moment system, with sorting-and-interpolation to recover the graphon and a rank-r connection probability matrix, with sup-norm consistency.
Problem
Estimating both the low-rank connection probability matrix and the graphon function from a single observed network, where existing methods estimate only P or are computationally expensive and lack sup-norm guarantees.
Approach
Assume a truncated eigen-decomposition graphon f(u,v)=sum_k lambda_k G_k(u)G_k(v); estimate lambda_k and G_k(U_i) from moment equations built from counts of paths and cycles (with a fast matrix-power variant), then recover the graphon by sorting nodes by the reference G_1 and piecewise-linear interpolation.
Key results
- In dense simulations, the method's MSE (1.275e-4 for graphon 1) matches USVT and beats neighborhood smoothing and SAS, with runtime around 0.1-1.5 s versus about 115 s for N.S.
- In sparse simulations (rho_n = n^{-1/2}), the method attains the lowest MSE in most settings, e.g., 0.036e-4 for graphon 1 versus 0.051e-4 for USVT.
- Sup-norm graphon error is about 0.12 (x10^-1) for graphon 3 and 0.16 for graphon 4 over 100 trials at n=2000.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed estimator instead of the strongest listed baseline for MSE | Low-rank graphon estimation · Dense graphons 1–7 | MSE: 1.275 vs 1.282; 2.452 vs 2.400; 1.973 vs 1.919; 1.826 vs 1.890; 1.774 vs 1.769; 2.582 vs 2.380; 3.768 vs 3.640 | Mixed |
| Use the proposed estimator instead of the strongest listed baseline for MSE | Low-rank graphon estimation · Sparse graphons 1–7 (ρₙ = 1/√n) | MSE: 0.036 vs 0.051; 0.115 vs 0.132; 0.075 vs 0.099; 0.043 vs 0.111; 0.071 vs 0.118; 0.105 vs 0.224; 0.091 vs 0.259 | Helped |
| Add the standardization step for estimated components (ablation) | Rank-r estimator · Dense and sparse graphons | estimation performance | Helped |
| Replace repeated-node path and cycle counts with corrected counts (ablation) | Fast rank-r estimator · Rank-r graphons | finite-sample estimation accuracy | Helped |
| Overestimate rank-1 graphons as rank 2 (ablation) | Proposed estimator · Rank-1 graphons 1–3 | MSE (×10⁻⁴): ID 1: 1.45; ID 2: 6.11; ID 3: 1.92 | No clear effect |
| Underestimate rank-2 graphons as rank 1 (ablation) | Proposed estimator · Rank-2 graphons 4–6 | MSE (× 10⁻⁴): 15.559; 1.810; 71.987 | Hurt |
Surprising findings
- Mis-specifying rank 2 as rank 1 causes large errors, while over-estimating rank barely hurts performance.
- Power iteration performs competitively on several dense settings despite lacking convergence guarantees.
Limitations
- Rank r is assumed fixed; theory does not cover growing rank.
- Graphon identification for r>=2 requires a monotone reference function and Lipschitz conditions; a non-Lipschitz example shows degraded guarantees.
- Sparse-graphon convergence rates are not established.
Experimental setup
Datasets: Primary School contact data (SocioPatterns) U.S. Political Blogs
Benchmarks: simulated graphons 1-7 (dense and sparse) Primary School contact data U.S. Political Blogs
Metrics: MSE of P maximum entrywise error sup-norm graphon error run time triangle and transitivity error
Baselines: USVT Sort-and-Smooth (SAS) Network Histogram (Nethist) Neighborhood Smoothing (N.S.) Power Iteration (P.I.)
Builds on: USVT Sort-and-Smooth neighborhood smoothing network histogram
Closest papers by meaning
- A Few Moments Please: Scalable Graphon Learning via Moment Matching (NeurIPS 2025 · similarity 0.90)
- Transfer Learning on Edge Connecting Probability Estimation Under Graphon Model (NeurIPS 2025 · similarity 0.88)
- Graphon based Clustering and Testing of Networks: Algorithms and Theory (ICLR 2022 · similarity 0.87)
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.87)
- A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs (ICLR 2024 · similarity 0.86)
- Learning Changes in Graphon Attachment Network Models (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.