Low-Rank Graphon Learning for Networks
Authors: Xinyuan Fan
Feiyan Ma
Chenlei Leng
Weichi Wu
Venue: NeurIPS 2025 poster ()
Keywords: low-rank graphon
subgraph counts
connection probability matrix
nonparametric statistics
network analysis
Primary area: probabilistic_methods

Abstract: Graphons offer a powerful framework for modeling large-scale networks, yet estimation remains challenging. We propose a novel approach that leverages a low-rank additive representation, yielding both a low-rank connection probability matrix and a low-rank graphon--two goals rarely achieved jointly. Our method resolves identification issues and enables an efficient sequential algorithm based on subgraph counts and interpolation. We establish consistency and demonstrate strong empirical performance in terms of computational efficiency and estimation accuracy through simulations and data analysis.

Low-Rank Graphon Learning for Networks
Xinyuan Fan" Department of Statistics and Data Science
Feiyan Ma' Weiyang College Tsinghua University
Tsinghua University
Beijing. China
Beijing, China
fxy22@mails tsinghua. edu.
Emails. tsinghua, edu.
Chenlei Leng"
Weichi Wu
Department of Applied Mathematics
Department of Statistics and Data Science
Hong Kong Polytechnic University Hong Kong, China
Tsinghua University Beijing, China
chenlei.. 1el.@poolyy@@py edu.hk
wuweichi@maii wtw.ll.ssinnaaaa.aa edu. en
Abstract
Graphons offer powerful framework for modeling large-scale networks, yet es- timation remains challenging. We propose a novel approach that leverages a low-rank additive representation, yielding both a low-rank connection probabil- ity matrix and low-rank graphon-two goals rarely achieved jointly. Our method resolves identification issues and enables an efficient sequential algorithm based on subgraph counts and interpolation. We establish consistency and demonstrate strong empirical performance in terms of computational efficiency and estimation accuracy through simulations and data analysis.
Introduction
With advances in data collection, modeling network data has become increasingly important across domains such as brain networks [Maugis al, 2022),, co-authorship networks [[standyari Moghaddam et all, 20233), and biological systems |Kamimoto et all, 2023). A key challenge is under- standing the generative mechanisms underlying these networks, which informs tasks like studying dynamics [Pensky 2019)) link prediction [Gao et all 2016), and community detection [Uin et all 2021]..
A powerful framework for modeling networks is based on exchangeable graphs. where node per- mutations leave the edge distribution invariant. By the Aldous-Hoowe theorem [Kallenberg all 2003], such graphs are characterized by a graphon, a symmetric measurable function. Graphons offer a unified perspective, supporting tasks such as asymptotic analysis of subgraph counts [Bickell at 201] and graph equivalence testing [Maugis et all 2020]. They also underpin widely used models, including the stochastic block model (SBM) [Hollndd et all [183]) random dot product graphs (RDPG) [Young and Schennermar, ((07)) and latent space models (Hoffetal 2002]
graphon is symmetric, measurable bivariate function and serves the limit object for sequences of dense graphs [Lovasz. and Szegedy, 2006). Without further assumptions, it cannot be directly estimated from a single network. However, its cigenvalue-cigenfunntio decomposition offers practical solution: by truncating to the leading components- -anaenooot--aaoouuus to principal component analysis-we obtain a low-rank approximation. The resulting connection probability matrix P. con- structed by evaluating the graphon at observed nodes, inherits this low-rank structure.
"qqual contribution.
Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Contributions. We propose novel low-rank approach to graphon modeling that simultaneously captures the low-rank structure of both the graphon and the connection probability matrix. While prior work has focused primarily on estimating the connection matrix, our method uniquely recovers both the graphon function and the matrix with the same rank, offering a unified framework that fills a gap in existing literature.
The method builds on the key observation that rank-r matrix can be decomposed into sum of r rank-l components. By counting (rr) carefully selected subgraphs, we efficiently extract these components and solve the resulting system to estimate the connection matrix P. The graphon is subsequently recovered by sorting and interpolation. Crucially, while sorting is a powerful tool for recovering one-dimensional latent structures as in our approach, is generally ineffective when applied directly to P estimated by other methods, which lack the rank-1 I aligned structure necessary for accurate graphon recovery. This sequential design ensures that the estimated graphon inherits the correct rank of P, leading to tuning- free, scalable method that performs robustly across a range of settings, including sparse networks, as validated in our experiments.
In addition to our methodological advances, we deliver several key theoretical contributions that deepen the understanding of low-rank graphon models. First, we establish sharp perturbation bounds for solutions to stochastic systems of equations (Lemmas L and L.G), shedding light on how esti- mation errors propagate through the model. Second, we prove a novel result (Lemma M. showing that, in low-rank graphon settings, the appropriately scaled number of fixed-length paths from a node uniformly approximates its conditional expectation given the latent variable. This insight forms the backbone of our eigenfunction estimation strategy and provides fresh analytical tool for studying low-rank network models. Finally, all our convergence results (Theorems B.I. G and B.G) are de- rived under the sup-norm, delivering stronger uniform guarantees than those based on average-error metries commonly used the literature. Collectively, these contributions offer a robust theoretical foundation and significantly enhance the practical impact of our approach.
Literature review. Existing graphon estimation methods generally fall into two categories: those that directly estimate the graphon and those that estimate the connection probability matrix P. A central challenge in both is reconciling the low-rank structure of P with that of the underlying graphon, often resulting in inconsistencies.
Graphon-based approaches include Qlhede and Wolfe [204), who approximate the graphon with a step function by partitioning it into blocks. Their method requires permutation maximization via a greedy algorithm, which computationally intensive (see Section 9 Chan and Aurolan [ refine this by reordering nodes by degree and applying total variation minimization. assuming strictly monotonic marginals, an assumption that excludes models like the SBM. Moreover, the resulting P is not guaranteed to be low-rank.
In contrast, P-based methods include Chatteree [201]] who assume low rank and use Universal Singular- Valuue Thresholding (USVT), treating the adjacency matrix as a noisy version of P. Zhang et all [20|]] propose neighborhood smoothing to estimate P, achieving near-minimax optimality. Gão et all [2016] introduce a combinatorial least-squares estimator, later extended by Wu et all [2025]] to non-exchangeable networks. However, these methods do not directly recover the graphon. The latent variables are unknown and unordered, preventing P from being viewed as a lattice sample of the graphon, which complicates alignment. Moreover, further analysis of the estimated P, such as through eigenvalue decomposition, is challenging, especially to achieve sup-norm consistency. Most prior work focuses on mean squared error bounds. These limitations underscore the need for methods bridging graphon and P estimation. Our approach offers a unified framework enabling sup-norm consistency both.
Finally, we note that extensive research has been devoted to graphon models, therefore, we provide broader literature review in Section B of the appendix.
Structure, The paper is organized as follows: Section P introduces the low-rank graphon framework. Section & presents the estimation procedures and algorithms for both r = and > 2. Section H reports simulation studies illustrating the method's efficiency and accuracy. Section concludes with a discussion and future research directions. Additional details, including the significance of graphon estimation, time complexity, simulation settings, rank selection, sensitivity analysis, real data examples, proofs, and technical lemmas, are provided in the appendix.
2

---

Notations. For real number [æ| denotes the greatest integer less than or equal to I. For positive real numbers and b, we define a V b max(o, b) and b min(a. b). Let ||A|| be the Frobenius norm of matrix A, and Asj denote its element at the i-th row and j-th column. For two sequences of positive real numbers On and bn. we write dn O(b,) or an S b, if there exist constants N and C' such that On I Cb2 for all > N. For random variable sequences Xn and Y, we write Xn = Op(Yn) if for any & > O, there exists a constant Cg > such that sup, P[[[n]] 2 |n) <.
2 Low-rank Approaches
We consider a random graph G = EV within the graphon model framework. For i L.... where is the network size, each node i is associated with an ii.. random variable U Uniform( (0, 1). The edges Eij are independently drawn as Eij ~ Bernouli(f
for i < j. where ((---) -) is a symmetric, measurable function f : [0, 1J + [o, IJ. the graphon. We impose E; 0 and Eij Eji for i > j. While focus on undirected graphs without self-loops, our methods extend to graphs with self-loops or directed graphs. Many large-scale real-world networks exhibit low-rank features, such as group memberships or communities, which popular models like SBM and RDPG capture. For further discussions and real-data examples, see Athreya et al. [ Thibeault et all [2024]], and Fortunatd [2010]]
To incorporate low-rank structure into graphon models, we introduce the following parsimonious model:
S(U; = A.G(UU))A(UU))
where |vg 2 A2
2 Arl O, G3 is a measurable function with for () 1 for k 1,....,, T, and f (u( du cigen-decomposition of the graphon, as suggested by the Hilbert-Schmide theorem [Szegedy, 2011] Model (II) includes both the SBM and RDPG as special cases. If the G₃ functions step functions, reduces to an SBM with r blocks. When all 2 values are positive, the model simplifies to a rank-r RDPG.
for i
This model represents truncated
Introducing low-rank structures graphon models enhances their ability to capture real-world net- work features, such as community structures and latent memberships. while also offering com- putational advantages through the models additive separability. We propose a novel, computa- tionally efficient, and theoretically grounded method for estimating the connection probabilities (f(U,, U,),", and the full graphon function f. Notably, practical methods for estimating general graphon functions in polynomial time are scarce [GGa and Ma. 202T]]
3 Methodology and Theory
Let Pty f(U,. U,) represent the connection probability between the i-th and j-th nodes, with P P= (Pij)a,j as the connection probability matrix. To provide an intuitive understanding, we first focus on the estimation of P and f for r = 1 in Section B.1l We then extend the discussion to the general case where
in Section B.2
3.1 == Low-rank Modeling with Rank-1
To provide clarity, we begin by considering the case where r 1, i... f(U,,U)) = GU, Without loss of generality, assume that inf G1(u) 2 O: otherwise, we replace (u) with IG, (w)). A key observation is that the degree of the i-th node, denoted d, = E, Eij. satisfies the following equation:
E(d U.)
[ I(U., =x,(()( /. Gr(u) du, $41
Σ
(2)
22
n
3

---

which is proportional to G1 (U,), Furthermore, by Lemma we have the following bound:
d B(d4 U.) Op (V (log(n)
sup 7
Thus, (U,) can be learned by , and as a result, Pij can be estimated by (x-17² to a multiplicative constant. To account for the sparsity of the graph G, we apply a moment estimation to determine this multiplicative factor. Note that the method of moments (MoM) widely used in network analysis, for example, Bickel all [20T]] employed MoM to estimate parameters based on subgraph counts, while Zhang and Xia [2022] analyzed the finite-sample distribution of MoM estimators for network motifs using Edgeworth expansions. The estimation procedure for Pij is
d.d.
summarized in Algorithm
Algorithm Estimation for (Pig) Rank-1 Model.
Require: The graph G EV,
I: For I,..., n, let d, Eyzzz Esy.
2: Let c1 = -Eijiies Eiz/ E Ensri dedy.
3: any (i,3) pair, i o j. let the estimator of Psy byg (crd.dz).
4: Let p.: 0 for
n.
5: Output (pi Nij=1-
Algorithm M is straightforward and leverages the low-rank assumption with r 1. Its time com- plexity Onn²), which is efficient given that there are ( values of Pij learn. In contrast, SVD-based methods (c.g., Xu [2018]) typically require Onn") time complexity, making them less efficient. We remark that when the connection probability matrix is known a priori to be rank-1, a truncated version of Xu [2018] can, in principle, be accelerated O(n²) time by computing only the leading singular value and its corresponding singular vectors through efficient procedures such the power iteration method (see also Section (I). It should be noted, however, that although the power iteration method is often effective in practice, it generally lacks rigorous convergence guaran- tees and theoretical justification. The times for these methods shown in Table II for various ranks r.
We now present the theoretical results for the estimates Pij.
Theorem 3.1. For r = 1, assume that So Gi(u) du > 0. Applying Algorithm B to obtain the estimates Pij. we have
sup pi Pijl =Op (V (V log(n) i.j
(Vog(()) n
The assumption in Theorem 6 is mild and does not require the continuity of the function G1- This flexibility allows our model accommodate various block structures, including the SBM with rank-1 connection probability matrix. Additionally, the estimated connection probability matrix p = -Pig)ss retains the rank-1 structure, consistent with the rank of P. The result sup.,; [P:j-Pi)
Op
log(n]
also implies convergence in the Frobenius norm, specifically:
P - PI Op (lo(())
n
standard metric used in the literature, such as in Zhang et all 2017] and Gao all [2015].
Estimating the graphon function (u,, u) is generally more challenging due identification issues arising from measure- measure-preservinn preserving transformations [Borgs et al,, 2015. Dracomi and lanson. 200
Olhede and Wolfe. X As a result, many prominent methods, including those Gioo all [2016] and Zhang et all [2017], focus on estimating the connection probability matrix, as we do in Theorem B.I. In the case with r we can mitigate the non-identifiability issue by defining canonical, monotonically non-decreasing graphon through rearrangement. Specifically, let Gf (m) = inf (t: J(G,, S () 2 u}, where p(-) denotes the Lebesgue measure. As shown in Barbarino ef al

---

[022|, the function G (u) is the monotone rearrangement of (1(),, making it monotonically non- decreasing, left-continuous, and peassreepreseevine Moreover, (1) is continuous if Gi(u) is continuous. Consequently, we can focus on the canonical graphon (u, v) (n)((()
To estimate (u, v), we propose degree sorting and interpolation method. Let (k) denote the index corresponding to the k-th smallest value in the sequence [d.],,,i.... do(1) I do(2) S ....
do(n)- Then, for any (u, v) E [0, 1J3. we define
(u, = 1A (((ch(W))(()))
where ((()) is defined follows. Let 8 o(n + 1) and k = |s]. Then, h(v) do( +1 (8 k), for k E [0, ni,, with the convention that do(u) - do(1) and do(n+1) do(n)) We remark that the degrees with ties can be ordered in any sequence, and the resulting h(v) will remain unchanged. This further ensures the uniqueness of f f+,,, (),
Theorem 3.2. For = 1, assume that Gi (u) is Lipschitz continuous on the interval [0, 11. i.e., there exists a constant M > O such that for any U1 U2 E [0,1], 11, [G1(zn) G)(u2) S M U1 U2). Then,
(f( -) (u, a O, and Op (V log(n) u,eE(o,1]
sup
7
The estimation rate of our method matches that of Chan and Airoldi [2014], with convergence the sup-norm, which is stronger than the mean squared error (MSE)- based approaches of Xu [20]]] Olhedee and Wolfe [20]]], and Chan and Airoldi [2014]. While MSE focuses on average error, the sup-norm ensures uniform convergence, controlling the error every point. This distinction underscores the robustness and precision of our approach.
3.2 1: Low-rank Modeling with Rank-r
For r 2 2, the connection probability Pty f(U,, U2) in (II) is additive. To estimate Ptj. it is neces- sary to recover each A and G₁ for = 1,
A central difficulty lies in the fact that estimating As requires climinating the dependence on the unknown components GI...., G,. A key concep- tual insight is that this disentanglement can be achieved by leveraging subgraph count statistics. Subgraphs, or "motifs". are crucial both theoretically [Maugis all 20200,
all 2023, Ribeiro et all [02I]] and practically [Miio atll, 2002 Dey et all 2019, et 2019). Their expectations are expressed via the graphon function. Consider cycle of length a passing through node i, whose count in the sample can be written
c.O0
Σ
Eig Ei,
II Esg 18, for 2 3,
(4)
tir... L)EL
where Ta =01,"" la distinct ie * 1, S sksa) a).
expectation given by
a-1
B(C,"))
II (n
Σ
(5)
which is independent of all Gt. Moreover, under an appropriate normalization, c.a) concentrates around (E(!.))) as established in Lemmal L.4 Consequently, by counting cycles of different lengths, we can recover all λt-
Similarly, consider a simple path of length a that has node an endpoint, whose count in the sample is
T (1)
Σ Fai 1
Σ
Exc. II Ex,-ii for 2. j=2
(6)
5

---

Its expectations are given by
Σ X/G)(U.) [: Gx(u)du,
B (U))
j)
|=1
Σ X Caluu
B(L!o)
nn 5)
B(I,0)) Moreover, by Lemma L4 and Lemma M 1, (i), are close under suitable normalizations. Therefore, after estimating Ag. we can first use L. to obtain an estimate of Ig' Ga (u(u)du, and then proceed to estimate GE(U;). Substituting these estimates into equation (I) yields estimator for Pij- To illustrate the above calculations, provide a toy example in Sec- tion D while the rigorous proofs are given in our theoretical derivations in the appendix.
We summarize the procedure in Algorithm M Note that in Algorithm D add standardization step in Line It typically enhances performance in finite samples, benefiting both dense and sparse graphon settings.
Algorithm Estimation for (pt))i,j=1 Rank-r Model.
Require: The graph 9 (V,
I: = I...., n. compute _l")
S a S and c. S defined (6) (E).
2: Solve the system of equations
yk 20 for I >... |Årl,
E
dr
Di= c(a) for 3 S S +
(n-))
(8)
Ei= divi Im E (n) for 1 aag
obtain (A1,-.. An, ...... v.).
3: For = 1,2.... compute the estimators (i.U.,, ,,.(U:) from
I 1.00 Σ (a for Sasr.
(9)
4: Compute the standardized estimators (U.
G..) from
(c(u:)=(x(() Σ (HU.)/n
(10)
5: For each pair (i,j), where * j. estimate Pij Pij = (ov (. Set
Die for = n, Output (p.g K.5-1-
Remark 3.3. The primary computational complexity of Algorithm D arises from counting lines and cycles within the graph. Notably, counting paths that allow repeated nodes is considerably simpler than counting simple paths, as the former can be achieved via matrix multiplication with complex- ity of Onn)). where w = 2.373 [Williams, 2012 Motivated by this observation, we propose an algorithm (Algorithm in Section with matrix multiplication time complexity, while preserving all theoretical guarantees from Theorems B.G and [Ty
Remark 3.4 (Comparison with the spectral method for estimating the connection probability matrix). Spectral methods, such USVT [Chatterjed, 2015], estimate the connection probability matrix through eigenvalues and eigenvectors. However, our approach differs in several ways. First, our goal is estimate the graphon function, not just the connection probability matrix, which leads to distinct methodology based on subgraph counts and moment-based techniques. Additionally, our method achieves the minimax rate for mean squared error up to a logarithmic factor, without re- quiring smoothness assumptions, unlike spectral methods that assume piecewise constant or Hölder- class smoothness [[ 2018]. Finally, for sparse graphons, our method outperforms USVT, as shown in Table D

---

We impose the following mild conditions for the consistency of Pis.
|1il > ... |r > So ( = 1, for 1 S k: S and Jo (((w),(()dda = for S ビi S n, (ii) fo Gu(u)du 0, for < k S r, (iii) there exists a constant > 0 such that maxigkgr [0. (G(( K.
Assumption 3.5. Assume that: (i
Assumption 3 (i) ensures the identifiability of the functions Gk. similar to the eigengap condition in the RDPG model [ PLyzinski et all 2013]. Condition (ii) guarantees a unique solution for the system of equations (,) akin to the requirement in Bickel et all [2 Condition (iii) is mild and typically holds for most graphon functions. Notably, we do not require G2 be piecewise smooth, which broadens the applicability of our model for estimating the connection probability matrix. The theoretical result for Pij is presented next.
Theorem 3.6. For 2 2, under Assumption FA when n is sufficiently large, there exists an open set U C 2 containing the point (A1.-.., Ar: So (1( du,.... -. G, (u) du) such that, with probability 1, the system of equations in (S) has unique solution within this region. Moreover,
1/2), for dR, 1 S S v, P.pe we have maxigkgr Dde ARl OOpn (n(n))/2), and sups, Iiis - Pişl = (p(Vlo((n)/n)
Theorem B shows that | Pli = (log(()) /n))), achieving a rate matching the minimax rate (up logarithmic factor) in Gao et all [201]] The rate does not involve r since we treat it as fixed. We leave the case where grows with n for future work.
Estimating graphon functions is more challenging for 2 due to the model's additive structure. To address this, we introduce the following assumptions for learning the graphon function in the
2 2 case:
Assumption 3.7. Assume that: (i) At least one G3 is strictly monotonically increasing: and (ii) All G3 's are Lipschitz continuous with constant M.
Assumption 7 aligns with the "canonical form" for graphon functions, where the monotone func- tion serves as the reference marginal function. This is similar to the identification criterion in Chan and Auroldi [0])]) which requires the graphon to be monotone after integrating out one argument. Note that Assumption (3. not needed if the goal is to estimate only the connection probability matrix. We remark that Assumptions 3 and B together imply that the graphon function belongs to the 1-Hölder class. In contrast, Klleee and Wolfe [|]]]]] assumed only a-Hölder smoothness with 0 < a < 1 when estimating the graphon via histogram methods. However, their approach requires the selection of a bandwidth parameter.
Under Assumption 3.7 we proceed without loss of generality by assuming G1 is the reference marginal graphon. The recovery of G2 relies the following insight: for i.i.d. samples U,,... Un- the j-th order statistic UG) is close to j/ (n++1) with high probability. Consequently, G1 (U)) serves as an approximation to G1 (i/(n++))) Moreover, G1 is itself the j-th smallest element among (G1 (U:)) and each & (U,) provides good approximation to Gi (U;). Hence, G1 Gi 1)) can be effectively estimated. Since n is large and G₁ Lipschitz continuous, piecewise linear interpolation yields consistent approximation of G1. The estimation strategy for the other functions GR, k = 2, ... r follows an analogous approach.
Formally, we first sort the estimated pairs (U,), G2(U.), ... (U.)) according to the first co- ordinate. Let y be one-to-one permutation such that
(U,))))) & (I S (.. (UU)
After sorting, we denote the reordered pairs as (G)(U,))) (. define the function
(U,()))) We then
(u) = G1 +1) < 1) +(
(k [k+1-ua 19) (u(n +0) (U) + 1)J k)
k=

---

as an estimate of the function G1. For GR. 2 2, recognizing that G₁ is a function of G1, we define:
he (u) GA(U) Gi(U, + CR(U hi Ii(w) - ((()(())) n-1 G((GG(+t)) - h1(1) GL(UT(N) + "I(Us((+1) Gi(Us())
G1(Un()))
Σ -G(Un(er1)-GG(CC - (((()()))
GK (u((T(ot))
T(Gi(U,()) s h2(u) < (1(UU(K+1))
Finally, we define
f(u, = ov Σ (cche(u)he(())) ]
(11)
as an estimate of the graphon fu, v).
Remark 3.8. In practice, we can relax the previous approach by considering each G; (i = ...... n) a potential reference function. For each G; we estimate the graphon as described above ref- erencing G₁, then compare the expected motif (e.g.. triangles, stars) densities from the estimated with the observed motif densities in the sample. By evaluating this criterion for all we select the f that best matches the empirical motif distributions.
Theorem 3. presents the theoretical result for this estimation. Since its proof follows directly from the proof of Theorem 3.2, we omit the details.
Theorem 3.9. For r 2 under Assumptions and the estimated graphon given by satisfies
sup [f(u, v) f(u, v) 0, and = Op( (p(Vlog(()) [lo(()/n)) a.vE(o,1]
Our result is based on the sup-norm, providing stronger uniform convergence guarantee compared to pointwise or average error metrics. The achieved rate matches Chan and Airoldi [2]E)] demon- strating the optimality and robustness of our method.
Remark 3.10. When is unknown, provided in Appendix F
estimate it using ratio-based method. Details
Numerics
In this section, we evaluate our method's effectiveness through extensive simulations. We assess the accuracy of the learned connection probability matrix P using three metrics: Mean Squared Error (MSE) as | Pll///n2, n²² maximum error maxişj |P: Psyl. and time cost. The code is available httpss:/ggituu..om//CCC wwwwroooo/hhooooooooooooo Mee--Rank--ahhhoo Learning-for------ for-Netorss....
Networks are generated using seven graphons listed in Table B (Appendix) with = 2000. We also consider sparse counterparts, where edge probabilities follow E.j Bernoulli( (p..f ff (U,,, U2)). with Pn n 1/2 controlling sparsity. We conduct 100 independent trials per configuration and report the average metrics.
For comparison, include the following methods: Universal Singular Value Thresholding (USVT):: [Chatterjee, 2015), Sort-and-Smooth (SAS): [Chan and Airoldi, 2014), Network His- togram (Nethist): [QQlhede_.r and Wolfe. 2014 Neighborhood Smoothing (N.S.): Zhang all
2017] and Power Iteration (P.L.): [Stoer et [880].
All methods are implemented using the R functions provided by the respective authors with de- fault parameters. Experiments were conducted on an Apple MI machine with 16GB RAM, macOS Sonoma, and R 4.2.1. For efficiency, modified Algorithm E slightly, described in Section E in the appendix.
We summarize the results in Table I (dense graphons) and Table Ø (sparse graphons). In the dense graphon cases, our method consistently matches or outperforms others both MSE and maximum error, achieving the best results in the first and fourth settings. It also matches the computational

---

Table 1: Results for dense graphons across 100 independent trials.
ID
Method
MSE (x 100
(x10-*)
MSE
(x10--)
error
(x10->)
Std.
(S)
(x10-
MSE
(x10-*)
MSE
(x19
enor
(x10-")
Std.
(5)
Ours
1,275
3,871
5.817
4,953
0.121
2,452
7,806
8.114
5,819
0.339
N.S.
5.175
115.076
12.033
17.617
115.757
Nethist
4.237
8,330
5,980
11.474
16,705
9.867
24.220
16,962
44.037
16,744
USVT
1.282
3,863
5.837
4,994
13.587
2.403
7,593
7.977
5,740
14.629
SAS
19.120
16.865
85,000
0,000
1.273
39,888
29.339
78.134
37.486
1.250
PI.
1,280
3,860
5,837
4,994
0.304
2,400
7,590
7.977
5,740
0.274
Ours
1,973
0.259
1.826
6.172
0.627
N.S.
8.337
14.186
17.329
8,566
114.694
4,388
8.413
17.902
11,686
108. 108.569 .69
Nethist
7.942
27.962
17.094
10.368
20.288
3.928
16.982
18.649
15.296
22.829
USVT
1.919
6.530
9.395
7.146
13.758
7.617
17.079
13.637
13.036
10,064
SAS
26.987
77.248
94.849
20.701
1.241
18.641
90.264
97.064
24.053
1.422
FL.
1,920
6,530
9.395
7,146
0.328
1,890
6,420
13,400
13.927
0, 0.654
Ours
1.774
6,204
9.676
7.804
1,507
2.582
7,017
9.319
7,808
0.682
N.S.
7.101
14,996
17,473
122.995
7.527
6,960
11.119
115.813
Nethist
7.729
31,838
18.559
15.486
23,804
9.548
244.015
22.573
107.570
19.441
USVT
1.769
6.078
9.661
7,871
13.684
2,383
6.082
10.052
8.343
11.169
SAS
28.703
115.215
89.861
49.
1.104
18.456
16.344
95,000
1,500
P.I
4,680
7.730
29.196
56.981
0.736
2.380
6,080
10.052
8,344
0.682
Ours
3.768
9,091
12.721
12.235
1,316
N.S.
6.596
6.372
17.611
9.760
126.270
Nethist
41.224
1574.245
59.567
96.247
20.238
USVT
3.644
12.613
11.640
SAS
20.552
22.529
90.000
0,000
1.701
P..
7,580
Table 2: Results for sparse graphons characterized by Pn. 1/Vn.
MSE
Std. MSE
Max.
Std. Max
MSE
Std. MSE
Max.
Std. Max
ID
Method
ID
(x10-X
(x10-9)
(x10-3)
(x10-3)
(x10
(x10-8)
(x10-3)
(x10
Ours
0.036
0.127
1.784
2.548
0.115
0.401
2.560
3.367
N.S.
19.224
45.848
99.665
0.000
61.897
249.576
99.161
0.002
Nethist
0.116
0.460
1.115
1.594
0.391
1.536
2.112
2.926
USVT
0.051
0.077
0.335
0.000
0.352
2.524
1.790
0.017
SAS
0.153
1.990
99.665
0.000
0,946
5.704
99.160
0.013
P.I.
0.249
0.735
1.500
0.000
0.132
0.490
2.951
4.110
Ours
0.075
0.284
3.079
4,494
0.043
0.398
3.840
8,423
N.S.
40.084
119.792
99.968
0.093
14.573
43.039
99.973
0.047
3 Nethist
0.249
1.056
2,840
14.842
0.111
0.642
2.485
12.126
USVT
0.314
0.952
2.093
0,039
0.102
0.648
2.202
0.075
SAS
0.200
2.163
99.956
0.426
0.078
0.945
89.227
253.955
P.I.
0.099
0.445
4.255
6.704
0.115
2.704
33.130
158,566
Ours
0.071
0,330
2.910
4.576
0.105
0,536
2.571
0.909
N.S.
34,490
115.091
99.993
0,039
42.530
69.027
99.984
0.099
5 Nethist
0.229
0.948
3,001
20.765
0.408
1.372
4.326
3,571
USVT
0.294
0.971
1,906
0.023
0.224
1.160
4.734
3.877
SAS
0.118
0.907
75.367
325.895
0,390
1.396
89.351
3,252
P.I.
0.170
4,392
21.174
101.657
0.415
2.055
2.821
4.047
Ours
0.091
0.585
2.139
1,440
N.S.
29.434
103.240
99,858
1,310
7
Nethist
0.359
1.688
3.123
1.715
USVT
0.410
1.306
4,808
1,855
SAS
0.915
3.112
99.604
0.113
P.I. 0.259
0.924
2.813
3.071
speed of SAS and P.I., while significantly outperforming other methods efficiency. Notably, our method achieves accuracy similar USVT, which is nearly minimax optimal for MSE under certain conditions [X. 2018), but with much lower computational complexity. Our method requires no tuning parameters, enhancing robustness across settings. In contrast, the power iteration method, though effective in some cases, lacks convergence guarantees and theoretical support.
In sparse graphon cases, method excels, consistently outperforming all other approaches in MSE. This is expected, as directly incorporates the sparsity parameter Pu, (see equation (E)). Additionally, conducted additional simulations to investigate the performance of all methods sparsity varies from n 1/2 -12 to 1, taking graphon 4 and 5 illustrative examples. The results shown in Table

---

(Appendix). As sparsity increases, the estimation error for all methods increases. However, our method consistently outperforms others the sparse regime.
For estimation of functions Gk, Figure II shows the fitted G1 and G2 using our method, with esti- mates closely matching the true values. Notably, G2 is continuous but not monotonic. The parison between the estimated graphon and the true graphon, measured by the maximum entrywise error (i.e., the sup-norm), reported Table G. The results demonstrate that the sup-norm errors of the graphon estimates remain well controlled, which is in line with the theoretical guarantees established in Theorems and 3
Table 3: Sup- sup-norms for graphon estimation across 100 independent trials.
ID Sup-norm (x10-3 3) Std. Dev. (x10->)
12.053
10.738
15.539
12.037
We provide additional simulation studies in Appendix and Appendix HL examining rank selection when the true rank is unknown, the impact of rank mis-specification, and the scalability of our method. Moreover, Appendix demonstrates the practical utility our approach through two real- world applications: the Primary School dataset and the U.S. Political Blogs dataset.
Graphon 3: Gu(u)
Graphon 4: Gr Gu(u)
Graphon 4: Gę(u)
1.004
1.0-
0.75
0.5
1.5
0.50
1.0
-0.5
0.25
0.5-
0.76
0.00
0.75
0.25
1.00
Legend
Esdimatdd
True
Figure Estimation of G 's for the third and fourth settings.
5
Discussion
This work presents the first unified framework for simultaneously estimating both a low-rank con- nection probability matrix and its corresponding graphon. Traditional approaches treat these com- ponents separately, leading to inconsistencies and inefficiencies. By aligning their estimation, our method offers a more robust, consistent, and efficient solution for modeling network structures, par- ticularly low-rank graphon models. We propose a computationally efficient method based on subgraph counts, supported by rigorous theoretical guarantees for low-rank graphon models of fixed rank r. The method's 's effectiveness validated through extensive simulations and real-data exam- ples.
Future research directions include exploring convergence rates and optimality in sparse graphon models, optimizing subgraph selection for better efficiency and accuracy, and extending the method cases where the rank increases with n, which could have significant implications for large-scale network analysis in high-dimensional or rapidly evolving networks.
6 Funding Disclosure
This work was supported by the High Performance Computing Center, Tsinghua University. Weichi Wu is supported by the NSFC No. 12271287.
10

---

References
Lada A. Adamic and Natalie Glance. The political blogosphere and the 2004 u.s. election: divided they blog. In Proceedings of the 3rd International Workshop Link Discovery, LinkKDD '05 page 3643, Association for Computing Machinery, 2005.
Seung C Ahn and Alex R Horenstein. Eigenvalue ratio test for the number of factors. Econometrica, 113)::103-1122,, 2013
Ernesto Araya Valdivia and De Castro Yohann. Latent distance estimation for random geometric graphs. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, , Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Avanti Athreya, Donniell E Fishkind, Minh Tang, Carey E Priebe, Youngser Park. Joshua T Vo- gelstein, Keith Levin, Vince Lyzinski, Yichen Qin, and Daniel L Sussman. Statistical inference on random dot product graphs: survey. Journal of Machine Learning Research, 18(226):1 2018.
Giovanni Barbarino, Davide Bianchi, and Carlo Garoni. Constructive approach to the monotone rearrangement of functions. Expositiones Mathemalicue, 40(1):155-173) 2022.
Peter Bickel, Aiyou Chen, and Elizaveta Levina. The method of moments and degree distributions for network models. The Annals of Statistics, 39(5):2280, 2011.
Christian Borgs, Jennifer Chayes, and Adam Smith. Private graphon estimation for sparse graphs.
Advances in Neural Information Processing Systems, 28, 2015.
Gecia
Lee M Gunderson, Pidrre-André Maugis, and Carey E Priebe. Quantifying network similarity using graph cumulants. Journal of Machine Learning Research, 24 14(1 2023.
T Tony Cai, Dong Xia, and Mengyue Zha. Optimal differentially private pea and estimation for spiked covariance matrices. arXiv preprint arXiv:2401.0353 2024.
Emmanuel Candès and Benjamin Recht. Exact matrix completion via convex optimization. Com- mun. ACM, 55(6): 11119, June 2012. ISSN 0001-0782. doi: 14.1145/1883199.11443
Stanley Chan and Edoardo Airoldi. A consistent histogram estimator for exchangeable graph models. In International Conference on Machine Learning, pages 208-216. PMLR, 2014.
Sourav Chatterjee. Matrix estimation by universal singular value thresholding. The Annals of Statis- fies, 43(1):177-214, 2015.
Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, and Rachel Ward. Completing any low-rank matrix, provably, 2014.
Asim K Dey, Yulia R Gel, and H Vincent Poor. What network motifs tell us about resilience and reliability of complex networks. Proceedings of the National Academy of Sciences, 116(39): 19368-1999 19373, 2019.
Persi Diaconis and Svante Janson. Graph limits and exchangeable random graphs. arXiv preprint urXiv:0712.27749 2007.
Etienne Donier-Meroz, Arnak S. Dalalyan, Francis Kramarz, Philippe Choné, and Xavier D' D'Haultfoeuille. Graphon estimation in bipartite graphs with observable edge labels and unob- servable node labels, 2023.
Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):55-17,, 2010.
Chao Gao and Zongming Ma. Minimax Rates in Network Analysis: Graphon Estimation, Commu- nity Detection and Hypothesis Testing. Statistical Science, 36(1):16 33, 2021.
Chao Gao, Yu Lu, and Harrison H. Zhou, Rate-optimal graphon estimation. The Annals of Statistics, 43(6):2624-266) 26522, 2015.

---

Chao Gao, Yu Lu, Zongming Ma, and Harrison H Zhou. Optimal estimation and completion of ma- trices with biclustering structures. Journal of Machine Learning Research. 17(161):1-29, 2016.
Solenne Gaucher and Olga Klopp. Optimality of variational inference for stochasticblock model with missing links. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 19947- 19959. Curran Associates, Inc., 2021.
Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches social network analysis. Journal of the American Statistical Association, 97(460):1090- 1098, 2002.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First Steps. Social Networks, 5(2):109-137, 1983.
Alireza TraandyrriMoggaddee
Mohammad Karim Saberi, Safieh Rahmasebi-Limone Sajjad Mo- hammadian, and Farahnaz Naderbeigi. Global scientific collaboration: A social network analysis and data mining of the co-authorship networks. Journal of Information Science, 2023.
Akhil Jalan, Arya Mazumdar, Soumendu Sundar Mukherjee, and Purnamrita Sarkar. Transfer learn- ing for latent variable network models, 2024.
Di Jin, Zhizhi Yu, Pengfei Jiao, Shirui Pan, Dongxiao He, Jia Wu, S Yu Philip, and Weixiong Zhang. A survey of community detection approaches: From statistical modeling to deep learning. IEEE Transactions Knowledge and Data Engineering. 35(2):1149-1177) 2021.
Jiashun Jin, Tracy Ke, Bingcheng Sui, and Zhenggang Wang. Counting cycles with deepseck. arXiv preprint arXiv:2505.1796 2025.
Olav Kallenberg et al. Probabilistic symmetries and invariance principles, volume 9. Springer, 2005.
Kenji Kamimoto, Blerta Stringa, Christy Hoffmann, Kunal Jindal, Lilianna Solnica- Kreiee, and Samantha Morris. Dissecting cell identity via network inference and in silico gene perturbation. Nature, 614:1-10, 02 2023.
Bernhard Kawohl. Rearrangements and convexity of level sets in PDE, volume 1150. Springer, 2006.
Olga Klopp and Nicolas Verzelen. Optimal graphon estimation in cut distance. Probability Theory and Related Fields, 174, 08 2019. doi: 02.10077/00444--1---077777
Olga Klopp, A. Tsybakov, Nicolas Verzelen MODAL'X, Crest, and Mistea. Oracle inequalities for network models and sparse graphon estimation. arXiv: Statistics Theory, 2015.
Vladimir S Korolyuk. Theory of U-statistics, volume 273. Springer Science & Business Media, 2013.
Clifford Lam and Qiwei Yao. Factor modeling for high-dimensional time series: inference for the number of factors. The Annals of Statistics, pages 694-726, 2012.
Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1), 2015. ISSN 0090-5364. doi: 10.1214/14 4os
Mengchu Li, Tom Berrett, and Yi Yu. Network change point localisation under local differential privacy. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages Associates, Inc., 2022a.
Curran
Yanying Li, Xiuling Wang, Yue Ning, and Hui Wang. Fairip: Towards fair link prediction on social network graphs. In International Conference on Web and Social Media, 2022b.
I László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 9666)9333557 2006.
12

---

Vince Lyzinski, Daniel L. Sussman, Minh Tang, Avanti Athreya, and Carey E. Priebe. Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding. Electronic Journal of Statistics, 8(2):2905 2922, 2014.
P-AG Maugis, Sofia C Olhede, Carey E Priebe, and Patrick Wolfe. Testing for equivalence of network distribution using subgraph counts. Journal of Computational and Graphical Statistics, 29(3):455 (663):45-4665, 2020.
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Net- work motifs: simple building blocks of complex networks. Science, 298(5594) 2002.
Maximilian Nickel, Kevin P. Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104:11-33) 2015.
Sofia C Olhede and Patrick Wolfe. Network histograms and universality of blockmodel approxi- mation. Proceedings of the National Academy of Sciences, 111441):1722-11727, 2014.
Marianna Pensky. Dynamic network models and graphon estimation. The Annals of Statistics, 47 (4):2378 2403, 2019.
Pedro Ribeiro, Pedro Paredes, Miguel EP Silva, David Aparicio, and Fernando Silva. A survey on subgraph counting: concepts, algorithms, and applications network motifs and graphlets. ACM Computing Surveys (CSUR), 54(2):1-36, 2021.
Josef Stoer, Roland Bulirsch, R Bartels, Walter Gautschi, and Christoph Witzgall. Introduction to numerical analysis, volume 1993. Springer, 1980.
Balázs Szegedy. Limits of kernel operators and the spectral regularity lemma. European Journal of Combinatorics, 32(7):1156-1117) 2011.
Vincent Thibeault, Antoine Allard, and Patrick Desrosiers. The low-rank hypothesis of complex systems. Nature Physics, 20(2):294-305 -022 2024.
Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Sci- ence. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Virginia Vassilevska Williams. Multiplying matrices faster than goppesmitthwinnorradd In Proceed- ings of the forty-fourth annual ACM symposium on Theory of computing, pages 887-898, 2012.
Weichi Wu, Sofia Olhede, and Patrick Wolfe. Tractably modelling dependence in networks beyond exchangeability. Bernoulli, 31(1):584-608, 2025.
Jiaming Xu. Rates of convergence of spectral methods for graphon estimation. In International Conference on Machine Learning, pages 5433-5442. PMLR, 2018
Stephen Young and Edward R Scheinerman. Random dot product graph models for social net- works. In International Workshop Algorithms and Models for the Web-Graph, pages 138-149. Springer, 2007.
Shuo Yu, Jin Xu, Chen Zhang, Feng Xia. Zafer Almakhadmeh, and Amr Tolba. Motifs in big networks: Methods and applications. JEEE Access, 7:183322-1833 183338, 2019.
Yuan Zhang and Dong Xia. Edgeworth expansions for network moments. The Annals of Statistics, 50(2):726-753, 2022.
Yuan Zhang, Elizaveta Levina, and Ji Zhu. Estimating network edge probabilities by neighbourhood smoothing. Biometrika, 104(4):771-78,, 2017.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the development of a novel low- rank approach to graphon estimation, highlighting its advantages in terms of parsimony, identifiability, and computational efficiency. These claims are substantiated by theoretical analyses and empirical evaluations presented in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings. is fine to include aspirational goals motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses several limitations, including the reliance on low-rank assumptions for the underlying graphon structure. Further discussion is given regarding the trade-off between model complexity and interpretability.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The paper clearly states the assumptions required for its theoretical results, such as those Assumption 14. All theorems and lemmas are formally stated and proofs are provided in full in the supplementary material. The main text also contains intuitive explanations and sketches the results to guide the readers.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should he numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The experimental setup, including data generation processes, parameter set- tings, algorithms used, and evaluation metrics, is described in detail in Section 4. The paper also provides the source of the analyzed real-world datasets to enable reproducibility.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or the contribution it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate the research performed.
specific model and empirical evaluation.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
15

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Sthhyyrr/LoowRank Rann--Rkk-aaa Baan-Graphon- Learning-for- for-Networks. The datasets used are publicly available and cited appropriately.
Justification: Code is available at
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.co cc/
for more details.
While we encourage the release of code and data, understand that this might not be possible, so No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips hraips.cc/public//uuddees htapli/c/guidee/Coeeeieeeee http:///eeSSSSemieeeeeeee agionPoliccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Section 4 provides complete details of the experimental setup, including data generation schemes, model parameters (such as rank r, thresholds, and projection steps), and justifications for their selection.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In Section 4, the paper reports mean squared errors and maximum errors over 100 repetitions, and provides standard deviations to show the variability due to random initialization and sampling.
16

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of eπrогs is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
The paper specifies in Section that experiments were conducted on a stan- dard personal computer. The computational requirements minimal, and all experiments can be run efficiently on CPUs without specialized hardware. This makes the setup easily reproducible without access to perfforerfe computing resources.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics atttps://neurr: http///rrrrp..cpppppll/l////ttaa
Answer: [Yes]
Justification: The research adheres to the NeurIPS Code of Ethics. The datasets used are publicly available and non-sensitive, and the algorithms proposed do not pose known ethi- cal or societal risks.
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
17

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The paper does not release any high-risk models or datasets and poses no identifiable risk of misuse. uses only publicly available, well-documented data (e.g., the US Political Blog dataset).
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The paper cites the original creators of the datasets used (e.g., the US Political Blog dataset by Adamic and Glance). The data used is publicly available for academic use, and appropriate attribution is given.
18

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the pack- age should be provided. For popular datasets, paperswi thcode com conddataseta has curated licenses for some datasets. Their licensing guide can help determine the cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: The paper does not introduce any new datasets or models. It proposes new methodology but applies to existing, publicly available datasets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve any human subjects or crowdsourced data collec- tion.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
19

---

Answer: [NA]
Justification:
This study does not involve human subjects and does not require IRB ap- proval.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: No large language models (LLMs) were used as part of the method develop- ment, experimentation, or analysis.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM for what should or should not be described.
20

---

A Graphon Estimation Beyond the Connection Matrix
Graphon estimation provides richer and more general description of network structure than the connection probability matrix. While the connection probability matrix captures marginal probabil- ities for edges in a specific network instance, it lacks information about how edges jointly interact. In contrast, the graphon f defines a generative model over a family of networks and encodes global structural properties, including the distribution motifs and other higher-order patterns.
For example, the expected density of a fixed motif (e.g., a triangle or star) in a large random graph generated from / is given by its homomorphism density
J [o.
[(r; By) doi dr(v(F))- ((5)EE(F)
II
For triangles, this quantity captures the limiting probability that three nodes form triangle, a fumda- mentally joint property that the connection probability matrix alone cannot characterize. Similarly, the expected transitivity can be expressed as
J f(x, (fr.))(y. (y,(()))((()C)) 2)f(2, x) dr dy dz/ I f(x, (), dr dydz. 10.11s
Graphon estimation thus enables direct prediction of such higher-order features. also facilitates comparison between networks of different sizes by analyzing their underlying generative mecha- nisms, independently of the specific realizations captured in the connection probability matrix.
To substantiate the discussion, we conducted an experiment using graphons with IDs 4-6. We gener- ated networks with 2000 nodes, randomly removed 10% of the nodes, estimated the graphon from the subgraph, and regenerated networks from the estimate. The mean absolute errors in triangle counts and transitivity (normalized appropriately) over 100 trials are shown below in Table !!
Table 4: Triangle and transitivity errors across 100 repetitions.
Graphon ID
Triangle Error (x (x10==)
Transitivity Error (x10-3)
Mean
Std. Dev.
Mean
Std. Dev.
4
2.942
5.309
0.696
6.240
5
1.863
2.107
1.506
1.749
6
0.914
1.192
1.346
0.453
These consistently low errors demonstrate that key higher-order features are well preserved, even with subsampling, highlighting the structural fidelity and generalizability of graphon estimation.
B A Broader Literature Review
More recently, advances have been made in understanding the minimax rates and adaptivity of graphon estimation methods. Notably, [Klopp and Verzelen, 2019 rigorously analyzed optimal rates under the challenging cut distance, providing sharp risk bounds for several estimator classes. Oracle inequalities for network models, which allow for adaptivity in the presence of sparsity, were established by [Klopp et al,, 2015), while [Doneer-Meooz et all R02K') extended the graphon frame- work to bipartite graphs with partial observability, further broadening the applicable scope of sta- tistical models in network analysis. These works, along with related efforts by [Gaoo et all 201S] and [[ei and Rinaldo 2015S) situate the current work within a rich landscape of research focused on both theoretical properties and practical algorithms for graphon estimation, highlighting the ongoing evolution of this field.
Matrix completion and matrix sensing are intimately related to graphon estimation, especially when considering networks with latent structure expressible through low-rank matrix representations. [Chen et all [0 addressed the general case of completing low-rank matrices, offering provable guarantees under mild assumptions, while the survey by [Candes and Rechi, 2012| provides foun- dational understanding of matrix completion via convex optimization techniques. These techniques inform approaches to graphon estimation, where the adjacency matrix of network can often be approximated by low-rank structure.
21

---

The study of smoothness assumptions further refines graphon estimation, particularly through the establishment of rates under Hölder or Sobolev smoothness conditions. For example, [[iao all 2015] analyzed community detection and graphon estimation under smoothness constraints, pro- viding minimax rates and adaptive procedures. [Wu all 2025] introduced a flexible framework for network modeling beyond exchangeability, leveraging composite and Hölder-smooth graphon structures.
Finally, emerging works have sought to bridge graphon estimation with transfer learning and latent variable modeling. [Dalan et all, 2022:] explored leveraging knowledge across related network mod- els for improved inference, illustrating the potential for cross-network generalization. Collectively, these contributions provide comprehensive landscape for graphon estimation, matrix completion, and smoothness-adaptive procedures, informing both the theoretical boundaries and practical ap- proaches to latent structure recovery in large-scale networks.
The significance of statistical network analysis and graphon estimation continues to grow within the Al and machine learning communities, as evidenced by prominent work presented leading conferences [Laetal 2022 Gaucher and Klopp, R[224, Araya Valdivia and Yohann, 20D)] Our methodology advances efficient and accurate network model estimation, with broad impact in do- mains such as social network analysis eL 2022D and knowledge graphs [[Nicke] el 2015..
C A Toy Example for Equations 5 and 7
Consider rank-2 graphon v( G G2G We illustrate the above result for (2 using a = 3. Note that nc!3)) /6 corresponds to the number of triangles in the graph. Hence,
nC nC(3)/0 /6
E
f(u, u)f(e, f) u) dudvdw = x + x
n(n 1)(n 2)/6
(0113
where the last equality follows from the orthonormality of {Gz)j=1,2. Moreover, we verify the conditional expectation of (3) Since 1.50 Ein da $1 i2 Eig Eigig we have
E(T (U,) E
Σ in
B(Ea, Fiiis UG U1, U.,)
(n -n 2) B[f(U,, Ui)
(n (n - (AROi(U.) L. Gz(u) du x3Ga(U:) L Calw)
The derivation for more general cases proceeds analogously.
D A Variant Algorithm and Time Complexity
In this section, we present modified version of Algorithm D that preserves all theoretical guar- antees from Theorems 3. and B.g while achieving the time complexity of matrix multiplication, O(n"), 2.373. This variant algorithm motivated by defining paths that permit node repeti- tion. For i = 1,..., n, define the lines and cycles allowing repeated nodes as:
100 = Σ
EEy 1,00
Σ in
Eag II
Ei 14, for 2 2, j=2
b
Sn
c(o) Σ
E Ei
Eij-nin for a 2 3.
$1.0 Ra-1
These quantities can be computed efficiently. adjacency matrix E. Then, have:
Specifically, let E denote the a-th power of the
I (0)
Σ
(E
c(0) (E
22

---

The variant algorithm (Algorithm M uses (,(0) and ( instead of L and c(a)
Algorithm 3 Fast Estimation Procedure for (ptg Fig-1 -1 in Rank-r Model.
Require: The graph 9 = E),
I: For i = ,,........................ compute _ = E (E")s (Ez))")) for Sas and C = ) f
2: Set _ [ and c =
Follow from Line of Algorithm to learn {po)ij=1.
4: Output (fs (o
Remark D.1 (Time Complexity of Algorithm B). Since all _ and c for S S and 1 S a S r can be computed using matrix multiplication, which has a time complexity of ((n2.37))
the overall time complexity of Algorithm & is also (13237))
To analyze the theoretical properties, we present a key lemma showing that _ and L (a) (as well as c(aa) and ) are sufficiently close, such that their differences do not impact the results of Theorem B.6 and Theorem Big
Lemma D.2. For a rank-r model, under the assumptions of Theorem B.G. we have:
1 (() 1 (n Op
C c( [1 (n
max max 1S Se
max max 1SSSnSaaSH2
Op
VT
Vn
With Lemma established, follows straightforwarddy that the following theorem holds.
Theorem D.3. Theorem Bd and Theorem B remain valid when the fast estimation procedure described in Algorithm applied.
E
Graphons in Simulation Studies
We list the graphons in Table E.
Table 5: List of graphons. We learn three rank-1 graphons using Algorithm D and four rank-r 2 graphons using Algorithm R
Graphon f(u, v)
Rank flu, v)
0.15
[-expl texpi -2
(tan (
+ 4) (tan (5 +
4
0.95 exp( exp(333eepp3333) exp(-3u) + 0.04(3n - 5u - 5c +
2
5
(sin sininssnne-e
0.05 0..15 0.4,v 0.4) + 0.4)
7
0.1 0.1 0.75 + < kuvu +0.5 3)
F A Remark on Computaiton
In Algorithm we employ i,(0) and 0(a)) as approximations for L(a)) and c.a) enabling efficient
computation. Though their equivalence has been proven in Theorem D.3. applying certain correc- tions in practice can improve Enite-sample performance. Specifically, we define:
F F(3) f.(3) T.(2) (1,51)3,
6(4) c(4) i.(2) (I
σ( 59(5] 2
(1) 2 (3)
1 Σ
i())
((3) - Σ
E. (3)
k
k=
km
23

---

and use _ CiO and (,²) to replace L Ch and C, respectively, in Algorithm BL These corrections ensure L = L, c(() = c and (+) is closer to c,¹) compared to c
G More Simulations
G.1 Additional Simulation Results on Scalability
To show the scalability of our method, we vary n from 1000 to 2000 for the rank-2 2 settings and report the results and time costs Table Our method consistently shows decrease in both metrics as increases, which is consistent with our theoretical results.
Table 6: Results for rank-2 settings with varying node sizes between 1000 and 2000.
ID
MSE (x10 *)
MSE S.D.
(x10
Max. Error (x10 =)
Max. Error S.D.
(x10 2)
Node Size 71
4
3.677
0.143
16.618
1.745
1000
3.067
0.126
15.772
1.419
1200
2.457
0.091
14.507
1,490
1500
2,043
0.064
13.564
1.269
1800
1.826
0.062
12.898
1.256
2000
5
3,552
0.159
13.003
1.083
1000
2.995
0.396
12.252
1,819
1200
2.365
0.086
10.732
0.878
1500
2.001
0,311
10.444
2.244
1800
1.774
0.062
9.676
0.780
2000
6
5.576
0.185
12.119
1.160
1000
4.533
0.155
11.665
1.177
1200
3.535
0.108
10.378
0.938
1500
2,890
0.073
9.772
0.964
1800
2.582
0.070
9.319
0.781
2000
For time costs, we plot the logarithm of runtime against the logarithm of in Figure Ø with varying from 200 to 1000. The observed asymptotic trend exhibits linear growth, aligning with the theoretical computational complexity.
Logastren (00.cccaal
Locarthen
Figure 2: Average runtime of our algorithm function of node size, computed over 100 repetitions. The blue line indicates the best least-squares fit.
G.2 Additional Simulation Results when Assumption 3.7 is Violated
Theoretically, Assumption serves as regularization condition graphon estimation, and sim- ilar conditions are necessary and can be commonly found in the literature (e.g.. Chan ai P014). this assumption violated, no theoretical guarantees for graphon estimation (Theo- rem M can be made; however, the estimation of the probability matrix (Theorem B.)) still works
24

---

as expected. Practically, even if Assumption B is slightly violated, the estimated graphon function 6 can still be reasonably close. We illustrate this with an example. Let G1(u) V 17 (vū + 1),
G2(u) - 300 (vz 1 which non-Lipschitz orthogonal functions. We apply method to estimate the graphon function, and the estimated G1 and 22 are plotted below. It evident that the estimates exhibit the correct trend, and will be more accurate as the sample size increases.
Graphon Gy(u)
Graphon Gy(u)
122
0.3
8.00
Legend
The
Figure 3: Estimation of the components of the graphon function for the proposed setting.
G.3 Additional Simulation Results when the Sparsity Varies
Taking graphon 4 and 5 as illustrative examples, we conducted additional simulations to investigate performance all methods as sparsity varies from n 112 to 1, The results are shown in Table
H Selecting r when it is unknown
In this section, we propose a method for selecting when its value is unknown. Since Ås approx- imates A by Theorem BTG we can estimate incrementally, starting from = 1. When [ågl is
significantly larger than O, but [Åg] for > k + are close to 0, we select = k. The detailed procedure for selecting summarized in Algorithm
Algorithm 4 Procedure for selecting
Require: Graph 9 = (V, E), threshold т.
I: = 1,..., n, compute ((3) Set
= 1,..., n, compute C (1++)))
Solve system of equations (8) with S a S and obtain (a....,A444))
4: if A 5 T, then
5: Choose
and return
6: end
7: Set k + and go back to Line
8: Output
We remark that Line 4 in Algorithm applies the eigenratio method, which is well-established approach in the statistics literature (c.g.. Lam and Yag A Abn and Horenstem (2013). It offers
25

---

Table 7: Results for sparse graphons across 100 independent trials.
Std. dev of MSE
Std. dev of Max. Error
MSE (x10-+
Max. Error
Graphon ID
Sparsity Parameter Pr:
Method
(x10 3)
(x10
(x10-9)
Ours
0.178
0.663
5.722
9,922
N.S.
31.285
140.98
99.907
0,15
USVT
0.389
1.964
6.163
24.638
Nethist
1.193
7.809
7.815
0.278
SAS
0.597
3.787
99.72
0,985
Ours
0.752
3,501
10.022
12.693
N.S.
8.833
86.337
98.761
0,416
n-1/6
USVT
1.348
6.356
12.44
11.336
Nethist
13.66
89.165
27.699
1.149
SAS
5.356
32.228
99.597
2.321
Ours
1.116
4.874
12.412
14.103
N.S.
3,264
10.317
38.125
129.087
Tt 11/10
USVT
2.161
10.221
15.706
14.102
Nethist
34.658
221.149
45.841
2.907
SAS
14.681
59.42
93.407
72.598
Ours
0.258
1.205
4.93
7.207
N.S.
29.992
170.322
99.969
0.167
n n//
USVT
0.9
3.584
6.231
5.969
Nethist
3.316
10.137
6.766
0,074
SAS
0.821
4,783
97.805
101.723
Ours
1.145
34.613
11.757
40.912
N.S.
3.624
6.686
20.814
98,466
n 1/6
USVT
3.039
11.992
12.511
9.675
Nethist
30.673
72.197
23.993
0,395
SAS
9.165
18.182
74.31
132.569
Ours
1.338
33.349
10.409
30.081
N.S.
4.852
10,989
16.784
9.73
n -1/10
USVT
4.626
18.243
15,865
13.431
Nethist
58.583
185.89
39.152
5,418
SAS
9.281
21.39
93.009
68.993
robustness to scaling and noise, especially in settings where the eigenvalues decay gradually or have non-uniform magnitudes (see also Cateral [2024]). In our context, the use of the ratio helps highlight significant drops in the eigenvalue sequence while mitigating the influence of slow decay or scale variability. Algorithm selects the correct rank with high probability as the threshold asymptotically approaches zero at certain rate.
We apply Algorithm B to select for the 3rd, 6th and 7th settings in Table E. with 0.2. Theoret- ically, the threshold 7 should asymptotically tend to 0. For finite sample simulations, we choose 0.2 as heuristic value. The results are presented in Table & These results demonstrate that Algorithm is effective in most cases.
In simulations in the main paper, we applying our method leads to minimal differences because r can be chosen correctly with high probability by method (see Table K) in scenarios. For example, algorithm to the 6th setting, and there is only an 8% probability of making an incorrect selection. The MSE when selecting r first and then running our method 2.4 10-4 (with standard error of 0.9 x 10 5), which close to the values reported in the main article.
the rank is known. Estimating first and then
apply rank selection
Table 8: Selection of r for the 3rd, 6th and 7th settings across 100 independent trials.
Estimated r
ID
True
2
3
2
3
1
100
0
0
0
6
0
92
0
8
7
3
0
0
89
11
26

---

Moreover, we assess the impact of an incorrect rank selection by testing cases where r is mis- specified as 2. The results, presented in Table show that the differences in performance are minimal compared to the original settings in Table III highlighting that our method is robust to over-estimation of the rank r.
Table 9: Results for rank- settings when their rank is mis-selected as
ID
MSE (10-1)
Std. MSE (10-1)
Max error (10-²)
Std. Max (10-2)
1
1.45
0.475
6.274
1.226
2
6.11
6.650
18.186
18.17
3
1.92
0.067
9.399
0.693
mis-specified as r 1, the corresponding results are summarized in Table Im As shown in the table, the estimation error increases significantly when rank graphons are incorrectly selected as rank 1, since an essential component is omitted during estimation. How- our rank selection experiments (see also Table N) indicate that while the selected rank may sometimes be higher than the true rank, we seldom select a rank lower than the actual one, which would otherwise lead to large errors.
For the case where r
Table 10: Results summary with runtime statistics.
ID
MSE (x10
Std. MSE (x10
Max. error (x 10
Std. Max (x10
4
15,559
5.939
30.818
17.708
1.810
0.620
10.320
8.962
71.987
29.280
15.086
2.447
I Real-world Data Analysis
We applied our method to two real-world datasets evaluate its performance and robustness in
practical scenarios.
L.1 Primary School Student Contact Data
Firstly, applied our method to real contact data from a primary school, collected by the SocioPat- terns project using active RFID devices that recorded data every 20 seconds. On October 1st, 2009, from 8:40 17:18, contact data were gathered for 236 individuals, resulting in 60,623 records. We constructed an undirected graph where nodes are connected if individuals had at least one contact. Using Algorithm with threshold quently learned the connection probability matrix with Algorithm E. The resulting heatmap, shown on the left of Figure M aligns with expectations for real-world interactions.
0.25, selected
4 based Table III We subse-
Table 11: Learned eigenvalues for the contact data.
Rank
A
0.264
0.159
3
0.266
0.146
0.0593
4
0.271
0.118
0.118
-0,0992
5
0.272
0.117
0.0813
-0.0423
-0.00721
Assuming Assumption [w/ we learn the graphon function, using G₁ as the reference marginal graphon. The learned functions ht.... hy are shown the right of Figure Al The learned graphon function f(u, v) for any (u,r) [0, 1]2 is computed using equation [
1.2
U.S. Political Blogs Data
We evaluate our method on a larger real-world dataset. We consider the U.S. Political Blog Dataset Adamic and Glance, 2CDS), which consists of 1490 nodes. This dataset captures the hyperlink net-
http::/www.sccippatteeee.
27

---

Estimated Graphons
You Wnthormming Hft in in Iwm you Wm My
Type
Estimated G1
Estimated G2
Estimatted
Essimated G4
Figure 4: Learned P (Left) and learned graphon (Right).
work among political blogs during the 2004 U.S. presidential election, where each node represents blog labeled as either liberal or conservative, and approximately 19000 edges between these blogs.
Using Algorithm A with a threshold T = 0.25, we selected rank r = 2 based on Table D2. We mention that our choice of rank consistent with the known structure of the network, in which blogs affiliated with the same political orientation tend to form two distinct communities, characterized by dense intra-community and sparse inter-community connections.
Table 12: Learned eigenvalues for the political blog data.
Rank r
Ag
A
0.0668
0.0326
0.0692
0.0304
0.00649
We subsequently estimated the connection probability matrix using Algorithm B. The resulting heatmap, shown in Figure EL reveals relatively sparse structure, reflecting the nature of the observed political blog network.
02
64
Figure 5: Learned connection probability matrix P for U.S. political blog data.
Assuming Assumption holds, we learn the graphon function using G1 the reference marginal graphon. The leamed functions hy and h2 are presented in Figure G. The estimated graphon func- tion f(, v) for any (u,e) v) E [o, 1]2 can be computed according to equation (II) The learning procedure demonstrates promising performance when applied to large-scale real-world networks, and effecttiveyy detects the latent structure of low-rank networks.
28

---

Extmated graphora the walloote
Figure 6: Estimated components of the graphon for U.S. political blog data.
1.3 Validating the Quality of the Real-data Estimates
Using the U.S. political blog dataset illustrative example, demonstrate the advantages of our method through extensive comparisons with existing approaches.
Specifically, estimated the underlying graphon from the observed network and computed the expected densities various motifs, such as triangles, squares, and 5-cycles. For competing meth- ods, we generated synthetic networks from their estimated connection probability matrices and per- formed motif counting on these networks. We then compared the absolute differences in motif counts normalized by the total possible in complete graph of the same size-between the original and generated networks. The results, summarized in Table I show that our method consistently achieves smaller errors in motif prediction than competing approaches.
Table 13: Motif counting errors and runtime for each method.
Triangle counting error (x (x10-4)
Runtime
Square counting
Runtime
5-cycle counting error (x10 (x10-6)
Runtime
Method
error (x 5)
(s)
(s)
Ours
0.252
0.167
0.761
0.198
3.848
0.175
N.S.
1.709
119.812
3.758
120.837
9.039
123.863
Nethist
8.087
19.082
1.809
20.523
4.383
22.427
USVT
4.449
15.971
1.712
17.098
5.149
19.439
SAS
1.327
3.018
2.256
4.730
4.960
5.237
Moreover, as shown Table IR our approach significantly improves computational efficiency, Af- ter estimating the graphon, the expected density of any motif in networks of any size can be quickly approximated using the plug-in method, with only a constant number of matrix operations per sam- plc. In contrast, existing methods require explicit motif counting in generated networks, which is computationally expensive (see In cLa [2025] for details). This blend of efficiency and accuracy is particularly beneficial for downstream tasks where motif statistics are crucial (e.g., Milo et al [202)).
Details of the power iteration method
To estimate the leading r (r 2 1) eigenpairs of a matrix A, we use the power iteration method itera- tively, combined with matrix deflation. Beginning with A A. each step (from to r) estimates the dominant eigenpair (Ax; (x) of A using the power iteration method. After normalization of
fg the matrix is deflated as Aş = Ar-1- 1- ARtxOT Once all eigenpairs are computed, an approx- imation P is reconstructed as P Er=1 d+ Finally, the probability connection matrix 1 is

---

obtained via element-wise thresholding:
Pij min (1, (nxx(0,P:)))
ensuring all entries lie within the probability range [0, 1]. The complete algorithm is summarized in Algorithm
Algorithm 5 Iterative Power Iteration.
Require: Adjacency matrix A, rank r, maximum iterations N, tolerance c.
Ensure: Estimated probability connection matrix P.
1: Initialize Ag A.
2: for =1 to do Initialize vector xg of length n with all ones and normalize: xo x0/1|xol12.
4: for == 1 to N do
5: Update X; t 1 and normalize: x; f- x;/||x;ll
6: if x - -121 then
7:
break
8:
end if end for
9:
10: Compute eigenvalue da +- x, Ak-1 and eigenvector iR
Deflate the matrix: An Ak-1 Antx
12:
end for
Compute P P P ÂnōRoy and threshold element-wise: P.j min (1, max pt))).
14:
Return P.
For the experiments, set the maximum number of iterations to 500 and the convergence threshold to 10 6, Tables and IS summarize the actual number of iterations for all scenarios discussed in this paper. In some cases, the power iteration does not converge within 500 iterations.
Table 14: Number of iterations for dense settings across 100 independent trials.
ID
o Iterations
Std. Dev.
À2 Iterations
Std. Dev.
Å Iterations Std. Dev.
1
6
0
2
0
3
5.01
0.0995
4
9
17.99
0.5744
5
500
6
15.34
0.6200 1.8871
0
7
27.83
15.1
0.7416
8
Table 15: Number of iterations for sparse settings across 100 independent trials.
ID
A Iterations
Std. Dev. Std. Dev. Å Iterations
2
13
3
17.15
0.3571
4
31.91
1.8713
500
5
17.98
0.3995
500
K
Proofs
Proof of Theorem 1.1 By (2)) and (E)), we have
sup GT c(n 1) dl =Op (Vlos()))
(12)
where c= dı So Gi(u) du.
30

---

Using the property of U-statistics (see, for example, Theorem 4.2.1 in Korolyuk (201)
we have
Σ
( 0p(n
(13)
n(n - 1.11
Moreover, note that
Σ (U0.Us)
(U.....UG Un
E
Eas
(14)
n(n
1)
n(n - 1)
(Briji -f(;,, U))))((sss) - f(U U1) Un.)
Σ
E
(15)
1
(Bin - f(U,, ((,),, U1,... Un )n)=0 -0 n2
<
E
(16)
n
$1,42
where the second inequality follows from the fact that the terms nonzero only when i2, J1 j2, and the last equality is due to the boundedness of each term.
Combining (115) and
4
we obtain
1
Σ i.jot}
Egg => d diaad + +0p(n
(17)
n(n
Similarly,
Σ d.d, Xi (f((())) + On (1/2).
(18)
n(n - 1)3 (.j:igj
Combining 71 and (18), we have
(n-1) 1)² E Enjstt Eij Eisats dedg
1
+ 10pnn-1/2)
A1 (Io G1(1) du)
Thus,
Eisues Eij di
sup (U,)
(19)
Eiscoes didl Vxi
1
Σ Eij Esj dj i did, Vhi cln - di
sup
GU,).)
c(n - 1) di
+ sup
(20)
(n 1)2 Eijre Eij
I sup (U))
c(n - 1) de
+ |V
(21)
Σ Enpridey didj vxi
An So Gi
Op (V log(n)
(22)
n
By the definition the graphon function, sups, I.u A1 (u < 1. and thus suPae[o.]] VT)G((u) < 1.
31

---

Eisiny By Eigugy ddd
For c
we have
sup Pig - pisl (
S sup
(id,d - -
< sup Vold VVd--ViG VTGGI(U)) yold
Vadd VAC(UU) (anGG(Uj)VVAGGIii (UGG((U))
+ sup is
Log(n)
Op
Proof of Theorem A It suffices to show that
1
sup
(u)
h(u)
5 0,
(23)
(n 1) fo Gi Gu(dde
sup (u) (n 1) So G1 h(u)
1
=Op O,
(ogg(m)
(24)
m [0.1]
and the subsequent steps can then be obtained by following the similar proof of Theorem B.I. transi-
Ligne Ey tioning from (l2) to (T9) by replacing (n 1)A1 for G1 (u(vdd with V Eigsee d:dy' and modifying
the argument from taking the maximum over all Ug to taking the supremum over all E [0, 1].
show (LK) and (24), we consider the following two steps.
(Step 1.) In this step, we prove that
n+1
w Gf
+ 1)
8.g. 0,
sup wE (1,2,, nn
(n 1)A1 So Gi(v)dv
and
Gi n (1(11)
(Vogg(n)
(og(()
" Op
sup (1,22 m) (n - 1) fo Gi(U)do
Let Um).... (()) denote the rearrangement of UI, Un iid.
Uniform(0,) 1) such that U(1) S
S (n). By Lemma Li2, we have
1U10 - in + 1) 4 0. i=1... i
sup
(Chapter I1.2), the rearrangement function G is Lipschitz continuous with con- stant M as long as G2 is Lipschitz continuous with constant M. As a consequence,
By Kawoh
sup IG Gi 1)) M sup (0()) i/(n = 0.
(25)
i=,,... .n
il..... n
Moreover, using the proof of Lemma in Chan and Airoldi [014] we have
sup U1) - 1/(n + 1) 1 00 (V [lg(m)
$=
which also shows that
- 1))1 Op (v log log(())
sup
(26)
32

---

By definition, for i = 1,...,,..... h(2/(n+1)) = dr(i)- By (22 (more precisely, the similar argument
of (TL2) applied to G1), (25), and Lemma DR we have
h
G!
i
sup 2,,
(n 1)^1 So Gi())d
n+
Similarly, via (I22), (26), and Lemma L.S. have
h
= =Op (V
(log(n)
n+I
Gf
sup (1,22 _))
n n+1
(n 1) So Gi(v)du
n
(Step 2.) In this step, prove (23).
We note that
1
sup me we(0.1/(n+1)
(i)
(n- 1)21 So G1 (u()do h(uu)
h(1/(n+ +1)
G
11
(n 1)A1 So (i
Gl ( (1)
sup wE(0,I/(x+1)]
h(1/(n+ +
M
G n n+1
+ + 1
(n-1)) 1n So Gi())du
a 0, and Op (Vlog(n)
n
Similarly, we have
Op (llg(()
sup NE(n/(a+1).i]
Gu( (n- 1) fo G (v)du
1
h(u)
= o, and
n2
For u (1/(n + 1), n/(n + 1)), let (n + 1)]. then
h(u)
G((w) (n- 1)A1 Jo (v)ddo
$ (k: + 1 u(n + 1))
G((()) -cl
n (m=1)
+ +k - 1il1-unn-- 1))
G7
b
n+1
(
(n - 1)A1 So Gi (v)do
k [++1
h
k+1 n+I
+uu(n + 1) - k) G]
n n+11
(n (n- 1n> fo Gi
k (++1)
(u(n + 1) - k) G[(u) - Gf
n++1
M
a+1
G
sup 1E(1,2.--..)
n n+1
mm
(n 1)d1 So Gi(v)de
n
n
Therefore, by the result from (Step 1).
1
00p log(n)
(11o((n))
sup (e[1/(n+
(((")
h(u)
(n 1) So (i))do
Finally, combining the results of the steps yiclds the proof of Theorem
33

---

Proof of Theorem 3. Without loss of generality, we assume that So Gx(u) du 2 0 for < sr Jo Gx(u) du 2 0, we can replace Gj with -Gk-
For i = ,,.... n, recall that
Σ
A
11
T.(a)=
Σ
Past II
for a 2 2, P f=2
Sindd distinet, iskka
0l
Σ
Eig E
for 2 3. Eig 185
Mundd distinct,
Note that PBg = U,))) = Ex= (AG(U))()))) and Sü (u 1 for si We then have
1
B(L( (1) |U,) = Σ (UG /. Gk(w)du du for 1
T (n - j)
k=l
E(C((a) U.) = Σ (U))( for3sasr+2.
(27)
k=1
We prove the theorem in two steps. (Step 1.) We first show that
yk - L Gx(u) On
ARl Op(n-113)
max
max ISKST
By (2Z)), we have
Xa ((aa)))di)) for sasa
E(( (0)
T (n j)
B(C x 5 (n j)
(28)
Moreover, by the implicit function theorem, the system of equations (Io Ga(n) (u) for < A S has unique solution if
28
terms of 0 and
X
X2
A1
A2
X :
O
# 0.
(29)
xx+1
X1
X
X
X
This condition is satisfied under Assumption 5.5 which assumes Aς for 1 < k S r and A # X for i # j.
By Lemma 4 have
n
Σ (I,00) B(II(O)) Op-00nnn12/ for 1 S a <asr.
1n (n - j)
1
(c(0) - B(C(o)) (p(1/1 for f
a-1 (n- 5)
1==0
By Lemma 5 we have
Ad - Aul = Op(nn1/3)
max 1Skšr
34

---

By Lemma L. we have
L." Gx(w)du
Op(n (12).
max
yk
ISASr
Note that there is no ambiguity in the square root since we assume So Gi(u) du 2 0 for = 1, (Step 2.) In this step, prove that
logn n
sup jyg Ptll =0, Op i.
Recall that (U. is estimated by solving the system of equations with respect to (TUU),...,,,((U.)
- (n (a)
Gu..) for 1 salsa
where ig and yn are defined in (8). For this linear system, we have
log
max max max (GL(U.) - Gx(U,)) =0 Op
(30)
n
provided that
I (1)0) B(L
(a) U.)
log n
max max
Op
j== (n -j)
which is guaranteed by Lemma M By (IIO, for every 1 S k have
GR(U))
-1) (31)
-G(U))
(u, G+(U.)
VI C)(U.)
/ Cg(U,)
Since U,'s are i.i.d., we have
CL(U,) - 1 -10
==1
Thus,
Σ 1=1
Σ (UU - --
(). + 1 -
- -1 Op
(V
log n
i=1
==1
which implies
log
11=0p
(32)
En_ (U.)))
n
By Assumption we have
G is bounded by K. Combining (32)), (BI)), (EO), and noting that O(1),
log
max (G,(U,) Gx(() =
n
Therefore,
log n n
max (axxxx((G(()) - = Op
35

---

As result, for the estimation of connection probabilities, we have
IA ov Σ (.G.
)) Σ EaCwOaaa
sup bg
Pij
Pişl
sup 6,
log T2
Op
71
Proof of Lemma
We show that
(1 r.("))
max max IsiSn SsaSr
1 (n
Op vin
as the result for C(a) follows similarly. By definition, we have
[
(0)
Σ
E.i, II B
where
M = {At least two of the values i, i....., d are identical).
Therefore,
O(n-11)
II -n [100 - 1 < T (n (n=
Σ
11 (n -j)
As result, we have
O(na-1)
Op (
i(a) I <
max max IsiSn Isa5r
II (n - -j)
11 (n -
71
L Technical Lemmas
Lemma L.1. For the rank-2 model with [(u,, v) = ()) where G1, G2 are bounded by a constant M >> O, we have
dd E(d,
U.) = Op
(V log(m)
(Vlox((n)
sup 11....77
T2
n
where de is the degree of the i-th node. Note that the model reduces to rank-1 model when X2 0.
Proof. We first that
Σ (U) + (ZG2(U)))((U)))
sup 1l
n
-AGG(( I' Gi(u)du Ci(w)dn-X22(1))) >22((1)) L' Cal
< M Σ Ci( L'' Gr(u)
1
n M
G2(U,) //' G2(u) du +
1
M
On -1/2),
n
36

---

where the last result follows from Slutsky's 's theorem. It now suffices show that
sup I.....
(1 (UGgSAAAUU)/G)))))ACCCD)
(33)
((((UU)))) (GG((U)))()))) =0p (log() (v
(34)
where UNi í J are i.d.d uniformly distributed random variables on [0, 1], and Uya = Uni for >
Let
a 7
1
(T +
n
By Hoeffding's inequality (Theorem 2.6.2 of Vershynin (2018]) for any t 0, we have
P [v L U......U. Un) S 2exp(-cl"),
where 0 is absolute constant. Taking expectations, get
Z Z > t) E (VnlZ, > UI,...,Un)) s eexp(-ct)
As result, VnZi are nab-Gaussian random variables. Then, using standard bounds for maxima of Lub-Gaussian variables, we have
((V log(n)
E max 1B.....
12,1 =0
n
which implies that
(1og(nn) n
max
1z Op
Lemma L.2. Suppose that U. Lid. Uniform(0., 1). for 1,.i;:,..,,,, 1,..., Let UG) denote the i-th smallest value among UI,... Un. i.e,, U(1) S U(2) S .... S U(n)) Then
sup U(a + 2 O.
Proof. It is well-known that U() Beta(i, + 1), with probability density function
1 - x)n-
p(x)
So x (1 - x)n- dr
We now proceed to bound the tail probability for any 0 using Markov's inequality. First, have
PP
U
2
<
1
E
U (1)
i
n +
5i(n 1i(n-it1 1)
6 (n + 1)8(n + 2) + 4)(n + ()(n+)
1
5n²A
(n
+ 1)1I!
where
= =
37

---

- - - - - 4(n 1 12) + (24 26(n - +3 - i 1)3).
We note that _ 12m 6 +3n + +44 - 72n Hence, we have
20
i
Σ
sup
U
28 E
28
n ++1
n
360m 8
1)
360
00.
g
n
n=1
Therefore, by the Borel-Cantelli lemma, the result follows.
Lemma L.3. Let G(u), for u [0, 11, be monotonically non-decreasing, Lipschitz continuous function with Lipschitz constant L > Let a, = G(i/(n + 1]), = 1,...,7e n. Suppose that there exists a sequence of random variables b1....,by such that sup;=1..... 1b, - a,l 4 O. Let a be one-to-one permutation such that ba(1)= I ba(2) S S ba(n)- Let a = ba(s)- Then we have
sup aa ail 4 O.
Moreover, if 16, a,l Op(gn). then sup, às - -ail Op(gn) for some 9n o(1), with ngn + D0.
Proof. Let Mn = supi=1,..., |b; asl. then Mn S 0. Assume without loss of generality that 1/n = on.s. (Mn). Let Kn be a non-negative random variable such that Kn = 0, 3M, I Kn S 4M,, and 1/n Oa.s. (K,). For any i 1,..., n1 we have
a. a:l = [ba()) asl S (aa(s)) a; Mn.
First, consider the case where (x) 2 i. Assume, for the sake of contradiction, that da(s) 0i Kn- Then for j = 1,2,, .1,,...,, 1, we derive that
L
(a()) 2 (o) M, a, n K M, b, n+1 + K, - 2Mn.
where for the second inequality, we use the monotonicity of G(u). By the construction of Kn, with probability 1, when sufficiently large, we have ba(i) > by for j = 1,2,....f 1. This implies that there are at least i+1 values smaller than ba()). which contradicts the definition of a. Therefore, aa(i) a, S Kn. Similarly, for the case where a(i) S i, we have dn(i) ai -Kn.
thus conclude that
sup jå; a:l = Oa.s. (Kn) + Mn 53 0.
The statement for Op follows from the same argument.
Lemma L.4. Under the assumptions of Theorem 3.6 we have
n
1, (a)
(B(T Op(2) for 1 Sasn.
T (n - j)
1
Σ (c(o) -B(())) (1/2) for35a5r+2,
M (n 5)
where (a) c( are defined in Section
Proof. We only show that
n1
(a) - E(L( O, 1/2) for a Sr,
n f)
0
1=1
38

---

as the results for 0 follow similarly. Note that E(E,, U4, U3) f(U,, Ug), and that Bi is conditionally independent of Es (i.j) # (11.J1). Then we derive that
when
1
BB
Σ
4
(0)
E i=1
B(4
(U.....Us)
|
IT (n 1)
S 12a+2
Σ
E
Bin
Bi, 18 U.) II S(U
(,51 (,51 do
f=2
Esk
Ekg-iks 5=2
S(Uk, Uk,)
[(UK)-1
| |U..... Un
j=2
20
n2a+2
n²
Since Σ
1,
oo (n j). we have
[1(0) - -E(
Op Un)) Us,.,,
=0p (1)
(35)
o (n j) 1=1
Moreover, by the property of U-statistics (see, for example, Theorem 4.2.1 in Korolyuk (2013), we
have
E f(U,, Uz, f( B da J(U,, U,, 22 ((Ui)-,) + Op(n 1/2). (13))
on j)
on -)
(36)
Note that
Σ B [U UI,.... U.) Σ S(U,, U, I
j=2
Then the result follows by combining (66) with (65))
Lemma L.S. Suppose that , are real numbers satisfying |z|| > [z2 > > |z,|| > 0.
Let ..n....,.r+2..... be random variables such that max; |ei,al = Op(n (m 1/2)). Then the solution
(ă1,..., ...,,,,, ;,) to the following system of equations
2 ca. for f
(37)
satisfies
max [ - xzl = Op(n 11/2).
Proof. Let A; ã. - 24 for < By the implicit function theorem, the system of equations (BZ)) has a unique solution with probability tending to 1. Moreover, by the continuous mapping theorem, we have A (1). By the definition of ei for any E there exist finite constants M and N such that
P maax | M)
for all N.
Therefore, it suffices to show that
max A S C Cmax (c,ml) -
(38)
for some constant C > 0.
39

---

Note that
k
2k + A&)
I
Am
k=
km
km
ar A + Op(mxxxxxx A2)
a-
1=1
We then calculate that
Σ ax 1u--1A -ss = Fa. fa
where Ea,n. da + can and 8, = Op00pppmmpp (m(ax A2).
For the above linear system of equations, by assumption æ; (similar the arguments in (29)), it has a unique solution of the form
+
A Σ ai. j=3
(39)
where oi are constants depending only on Ti...., Tr. By combining
(G9) and the fact that max, 8al Op(max; A3) and A; = (1), conclude that (6 follows.
Lemma L.6. Suppose that ,, are real numbers satisfying |21| 02 and that T1...., _, random variables satisfying max; [ī; zu1 = (n 1/2). Let .1..... Vr be r non-zero real numbers, and let E1,us..., Cr, be r random variables satisfying max; |<,,l = Op(n 1/2). (p(n-1/2) Then the solution (in,..., -rr) to the following system of equations with respect to (y1 (y))...)ur):
|z, > O,
V/ 0,
can for 1 Sasr.
(40)
1=1
k=1
satisfies
max l0s Vil (122).
Proof.
Note that
32 u ( - u -: + [ 122)
Since max; | zz (HI) reduces to
(1(2)1 we have max; [ 211 Op(n" (n-2). Therefore, equation
Va 0.
Σ
CHC v2) Ja,n for 1 - Sr
where max, | (p (n 1/2). Moreover, since max b = (1),, and noting that the above system equations is linear in 02 v for s < r, and that r = 0(1), we have
max D v On 1/2).
Finally, recalling that .i..... ye are non-zero, we conclude that
max U Vill = On(nnnnn/) 1/2).
Lemma L.7. Under the assumptions of Theorem B. we have
L (a) B(L Ut))
(V log(n)
max 1
11= (n
Opp
40

---

where
1/
Σ E
(0)
Σ
Bag
Big-1t 18, for 2 2.
fr An distinct Hi1kkoa
/=2
Proof. We divide the proof into two steps. In Step 1, we show that
(v log(n)
max (1(") Ss,ol Op
- (n -
where
S
Σ
f(U, U. II
$1.0 de distinct. S
In Step 2, we show that
max Si, - Ti,1 = Op(n~1/4
[n 1
where
T3 = E
Σ
s( U, II S = EELL") (U:).
fr Sa dy #1, gkgaa
j=2
Then the proof is complete by combining the above two equations and noticing that is bounded.
Step 1. Let
S f1 do distinct,
Σ
E
II Ei f(U
Then
T (n j) (1!-) Ss
1
IT -j)
Σ
Ea, II j=2
Big iss (Ei, i' f(U,, 1s U..))
41 Sa distinct, Hi
(41)
Notice that Eg, 1s. I(U,, S(U 1, U,)) binary, with U., 1.2 Uniform(O, 1) inde- pendently, and that U.J is independent of Up for any i.j, k. By Hoeffding's inequality in Theorem 2.6.2 of Vershynin [2018], we have for any t > O.
P
Σ
(Fr (( 2 t Ui ... Un s 22exp(-of
ta da-1
where e >> is an absolute constant. Then
P
Σ
(Eiaiii (-Ul-,1,Th)) 2t
11
de-1
(Erarit Utal) 2 2t ,Un 1) < 2exp(_cdt)
E
P
1
Σ
do-1
41

---

As result, vn-a and we have
Eietidh da-1
(Era-ite - f(Vio-11 Uta)) are sub-Gaussian random variables.
=0 Eia-iia f(Vio-11 Una) ((n an= 001 (V)og())
Σ
E max
f Ra-1
By recalling
(1 and the fact that Eiy are binary, have
(a) Sia-11= =0 (0()oe(rn)
E max
Similarly, let
S S f1 da distinct, Ht,gkkaa
Σ
Ein Il
Bay ui [(U Uk, (V
J=2
Then
j=1 (n - j) (Si,-1 Sia-2) = 1 - -J) by da distinct, de $sk
Σ
Exa
x II Exj-rty (Eia-zia-1 f(Uma-2: Ulm-1))
f(Uta-1 Usa)
a-2
E (n - j) kn. da-1 distinct, 24, sk
Eis Eig 1é (Bi, 2ba 1(Ube 21 Un, .))
II j=2
(42)
The same reasoning holds by Hoeffding's inequality to show that
( (n j) max [1 (a) S.a-2l = =Op (v log(n)
n
Continuing this process iteratively and combining with the fact that is bounded, we obtain
(n (n 1- max (1,00 Scol =O, (V /logm))
(43)
Step Let
aia-1= S1 distinct, #4,1
Σ
S(U,, U. II U.,), (f(U).-1: Una-1).
j=2
Then, we have
max
1Sin -Ti,a-1
1 (n - -j)
S(U U,) a-1 SU, U.U))
Σ
maxx
11 (n-
i ve B(f(U Un.) UnD))))
j=2
x (ff(U).-1 Uta)
a-1
max
Σ
U(U,,U))
II SU j=2
(n 5)
Ka- distinct, in S
Xa GuUU, .) (cnlUN) S/' Galu)
(G(U - S. Galu) 01122112),
M Σ
11
in
42

---

where we use the facts that fz, y) are bounded by 1, Gj. are bounded by M, and U2 are i..d. random variables.
Similarly, let
a-2
Tia-2
Σ
I(U,, U.,)
II ==2
D.V. Una) (i Uia-2).
Aa distinct, i Hil
Then, we have
1
max
Tiaa11 -2
j==1 - j]
a-2
Σ
f(U;, U II 1=2
((U)))))))))))))
max
[1 (n-
is distinet, #i
x (J(U,, 2: Usa )B(SUU, 11 ..U).) Un, 1) - E (S(Ur, Ur Ml ;,U)s) Us 2))
Aka Akz Gk. (U 1G (Uk /' (u)
fa-1 by =1=1 kg=1
f du
Σ (RR(U,, -)
Σ #22
Σ fa-1
(Ua ,) +0
1 72
+ n kn
1
On 1/2),
where we use the facts that f(z, y) are bounded by 1, Gy are bounded by M, r is bounded, So' du 1, fo G,(w)G,(u) du = 0 for i * j. and that U; are i.i.d. random variables.
Similar arguments can be performed for -,, 3,. ... Tr,1 Since is bounded, by combining all the results, we obtain
II (n ÿ) max |S Tı,1l Op(n
(44)
where
T3 E
Σ
1U, U. II I(U Uc)
fininca distinct, de f #LiSA
j=2
Finally, the proof is complete by combining the results from equations bounded.
and noting that
43


Reviews:
[{"review_id": "lAqLff3uYz", "reviewer": "Reviewer_1DRW", "summary": "The author(s) propose a low-rank graphon modelling for networks. The estimation approach reconcile the estimation of the graphon function and the corresponding connection probability matrix. The author(s) propose a sequential efficient algorithm baed on subgraph counts and interpolation. They also prove theoretical consistency results in sup-norm for the connection matrix and the graphon function estimation. The proposed approach is validated on simulated data examples and on real world network data.", "questions": "I think the low-rank modelling approach using graphon models for networks is a novel formulation indeed. Especially, the contribution in the direction of joint estimation of connection matrix and the graphon function itself is a long-standing problem in the literature of networks. So indeed this is valuable.\n\nI have a couple of minor queries for the author(s)\n\n-I may have missed this point but how does one ensure the uniqueness of the estimated graphon function $\\hat{f}^{+}(u,v)$ ?\n-What happens if there are ties in the degree sequence $\\lbrace d_i\\rbrace_{i=1}^n$? How do you do the sorting then i.e. how breaking of ties is implemented?\n-Does the additional assumption 3.7 means in certain cases one can only estimate $P$ and not the graphon function $f$?\n-Why ratio is being used in (A.5) to select unknown rank $r$ instead of the difference $|\\lambda_{k+1}-\\lambda_k|$? \n-Theorem 3.8 says the sup-norm rate is independent of $r$ but practically speaking, not all networks can have same rate of estimation since the rank may vary. Am I missing something here?", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "strengths:\n\n1. A novel modelling approach of network data via low-rank graphon modelling\n2. Estimating jointly the graphon function and the connection matrix via an efficient algorithm based on subgraph counts and interpolation\n3. Strong theoretical results on sup-norm consistency of graphon function estimation and connection matrix.\n4. Scalable algorithm that has favourable time complexity over its neighbours.\n5. The assumptions in the theoretical framework often matches with those in SBM or RDPG network models.\n\nweakness\n\n1. For clarity and understanding, the section on low-rank modelling with rank $r > 2$ should be rewritten especially the graphon function estimation. The subgraph count based idea along with sorting may facilitate reader's understanding with a toy example.\n2. Some motivation/discussion was lacking why graphon function estimation would be useful beyond estimation the connection matrix.\n3. As it seems, the motivational example of $r=1$ uses the method of moments approach in estimating the $p_{ij}$. Some discussion on that would have been good as method of moments has been used in network parameter estimation earlier in the literature as well.", "was_revised": true, "final_justification": "The author(s) put in a sincere and detailed effort in answering queries posed by myself and other reviwers. I am happy with the author(s)'s response and would like to maintain my score \"Accept\".", "rebuttal": "Thank you for your positive feedback on our paper. We appreciate your recognition of the novelty of our approach, theory, and the effectiveness of the algorithms. In the following, we will address each concern that you raised one by one.\n\n**1. Regarding the clarity of the section on low-rank modeling with rank $r > 2$.**\n\nThank you for this helpful suggestion. We agree that the discussion of low-rank modeling for $r > 2$, particularly in the context of graphon estimation, could benefit from additional clarity. In the revised version, we will rewrite this section, as suggested, to better convey the key ideas and provide more intuitive explanations. To aid understanding, we will include a toy example based on the graphon $f(u,v) = \\cos(u - v)$. While omitted here due to space constraints, we will incorporate it in the revision to make the presentation more accessible.\n\n**2. Regarding why graphon function estimation is useful beyond estimating the connection matrix.**\n\nThank you for this insightful question. We clarify that graphon estimation provides a richer and more general description of network structure than the connection probability matrix $P$. While $P$ captures marginal probabilities for edges in a specific network instance, it lacks information about how edges jointly interact. In contrast, the graphon $f$ defines a generative model over a family of networks and encodes global structural properties, including the distribution of motifs and other higher-order patterns.\n\nFor example, the expected density of a fixed motif $F$ (e.g., a triangle or star) in a large random graph generated from $f$ is given by its homomorphism density: $t(F,f) = \\\\int_{[0,1]^k} \\\\prod_{(i,j) \\\\in E(F)} f(x_i, x_j) \\, dx_1 \\\\cdots dx_k,$ where $k = |V(F)|$. For triangles, this quantity captures the limiting probability that three nodes form a triangle, a fundamentally joint property that $P$ alone cannot characterize. Similarly, the expected transitivity can be expressed as $C = \\\\frac{\\\\int_{[0,1]^3} f(x,y) f(y,z)f(z,x) dxdydz}{\\\\int_{[0,1]^3} f(x,y) f(y,z)  dxdydz}.$\n\nGraphon estimation thus enables direct prediction of such higher-order features. It also facilitates comparison between networks of different sizes by analyzing their underlying generative mechanisms, independently of the specific realizations captured in $P$.\n\nTo support this, we conducted an experiment using graphons with IDs 4-6. We generated networks with 2000 nodes, randomly removed 10\\% of the nodes, estimated the graphon from the subgraph, and regenerated networks from the estimate. The mean absolute errors in triangle counts and transitivity (normalized appropriately) over 100 trials are shown below in Table R1. \n\n*Table R1: Triangle and transitivity errors across 100 repetitions.*\n\n| Graphon ID | Triangle Error $(\\times 10^{-4})$ Mean | Triangle Error $(\\times 10^{-4})$ Std. Dev. | Transitivity Error $(\\times 10^{-3})$ Mean | Transitivity Error $(\\times 10^{-3})$ Std. Dev. |\n|------------|---------------------------------------|--------------------------------------------|--------------------------------------------|------------------------------------------------|\n| 4          | 2.942                                 | 5.309                                      | 0.696                                      | 6.240                                          |\n| 5          | 1.863                                 | 2.107                                      | 1.506                                      | 1.749                                          |\n| 6          | 0.914                                 | 1.192                                      | 1.346                                      | 0.453                                          |\n\nThese consistently low errors demonstrate that key higher-order features are well preserved, even with subsampling, highlighting the structural fidelity and generalizability of graphon estimation. We will incorporate this discussion and table in the revised paper.\n\n**3. Regarding discussion of the method of moments (MoM) used in network parameter estimation.**\n\nThank you for your question. The method of moments (MoM) has been employed in the network literature, including [3], where MoM was used to estimate parameters based on subgraph counts, and [4], where the authors analyzed the finite-sample distribution of MoM estimators for network motifs via Edgeworth expansions. \n\nIn our work, we align network sparsity using MoM when $r = 1$, which is inspired by [3]. We will include explicit citations and discussion of these relevant works in the revised version.\n\n**4. Regarding the uniqueness of the estimated graphon function $\\\\hat{f}^{+}(u,v)$ and the ties in the degree sequence $\\\\{d_i\\\\}$**\n\nThank you for your question. If there are ties in the degree sequence - for example, if $d_1 = d_2$ and they represent the smallest degrees - then for $\\\\frac{1}{n+1} \\\\le v < \\\\frac{2}{n+1}$, $h(v)$ will always be equal to $d_1$ (which is also equal to $d_2$). In fact, ties do not affect the function $h(v)$: the degrees with ties can be ordered in any sequence, and the resulting $h(v)$ will remain unchanged. This further ensures the uniqueness of $\\\\hat{f}^{+}(u,v)$.\n\n**5. Regarding Assumption 3.7.**\n\nThank you for your question. The short answer is yes. Assumption 3.7 provides an additional condition for estimating the underlying graphon function $f$ (beyond the connection probability matrix $P$). Without such conditions, the graphon is non-identifiable--it is only defined up to measure-preserving transformations. It is well-known that in this case, we can typically only estimate the probability matrix $P$ (see, for example, Section 10.2 in [2] for discussions on identifiability). Therefore, when estimating the graphon itself, the literature generally requires additional conditions (such as [9]). Assumption 3.7 plays a similar role, enabling the recovery of both the connection probability matrix $P$ and the graphon $f$. \n\n**6. Regarding why a ratio is used in selecting the unknown rank $r$.**\n\nThank you for your question. The eigenratio method is a well-established approach in the statistics literature (e.g., [5], [6]). It offers robustness to scaling and noise, especially in settings where the eigenvalues decay gradually or have non-uniform magnitudes (see also [7]). \n\nIn our context, the use of the ratio helps highlight significant drops in the eigenvalue sequence while mitigating the influence of slow decay or scale variability. Algorithm 4 selects the correct rank $r$ with high probability as the threshold $\\\\tau$ asymptotically approaches zero at a certain rate. We will clarify this connection and cite the relevant literature in the revision.\n\n**7. Regarding the relation between the sup-norm rate and the rank $r$.**\n\nThank you for your question. In this paper, we treat $r$ as fixed, which is why it does not explicitly appear in the stated error rate--it is absorbed into the constant factor. In practice, $r$ is typically unknown and may vary, which motivates the inclusion of Algorithm 4 to estimate it.\n\nWe agree that the error rate should reflect the dependence on $r$ more explicitly. Since the rate deteriorates as $r$ increases, we will include this dependence in the revised statement of the error rate. The case where $r$ grows with $n$ is an interesting and important direction, which we leave for future work.\n\n[1] Borgs, Christian, Jennifer Chayes, László Lovász, Vera T. Sós, Balázs Szegedy, and Katalin Vesztergombi. \"Graph limits and parameter testing.\" In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 261-270. 2006.\n\n[2] Lovász, László. Large networks and graph limits. Vol. 60. American Mathematical Soc., 2012.\n\n[3] Bickel, Peter J., Aiyou Chen, and Elizaveta Levina. \"The method of moments and degree distributions for network models.\" (2011): 2280-2301.\n\n[4] Zhang, Yuan, and Dong Xia. \"Edgeworth expansions for network moments.\" The Annals of Statistics 50, no. 2 (2022): 726-753.\n\n[5] Lam, C., \\& Yao, Q. (2012). Factor modeling for high-dimensional time series: inference for the number of factors. The Annals of Statistics, 694-726.\n\n[6] Ahn, S. C., \\& Horenstein, A. R. (2013). Eigenvalue ratio test for the number of factors. Econometrica, 81(3), 1203-1227.\n\n[7] Cai, T. Tony, Dong Xia, and Mengyue Zha. \"Optimal differentially private PCA and estimation for spiked covariance matrices.\" arXiv preprint arXiv:2401.03820 (2024).\n\n[8] Von Luxburg, Ulrike. \"A tutorial on spectral clustering.\" Statistics and computing 17, no. 4 (2007): 395-416.\n\n[9] Chan, Stanley, and Edoardo Airoldi. \"A consistent histogram estimator for exchangeable graph models.\" In International Conference on Machine Learning, pp. 208-216. PMLR, 2014."}, {"review_id": "DdEPRGvh5P", "reviewer": "Reviewer_n6Ak", "summary": "The authors proposed a methodology that estimates both the connection probability matrix and its underlying graphon at low computational cost. The approach leveraged the rank-r eigen-decomposition of a graphon into r eigenvalues and eigenfunctions. These quantities were recovered by counting cycles and paths of prescribed length, which leads to an estimate of the connection probability matrix. Identification issue was handled via sorting, and linear interpolation was used to extend the discrete estimates of the eigenfunctions to a continuous graphon.", "questions": "1. How can this work tangibly benefit the AI research community or How can this work be related to the scope of the conference?\n\n2. Can you provide the missing results for IDs 1, 6, 7 and the runtime column in Table 2?\n\n3. What happens if the target graphon is high-rank? Is the method scalable or accurate in that regime?\n\n4. Is low-rank (less than or equal to 3) approximation applicable to real-world data?\n\n5. Could you compare computational cost as a function of rank?\n\n6. Could you report quantitative graphon-estimation errors (e.g., norm)?\n\n7. How do you validate the quality of the real-data estimates?", "limitations": "- Unclear practical impact\n- Limited experimental verification", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "<Strengths>\n\n1. Mathematically well-founded:\nThe methodology was supported by rigorous proofs; e.g., Theorems 3.2, 3.6, and 3.8 establish convergence rates.\n\n2. Solid methodology:\nTo my knowledge, the authors introduced a new methodology to estimate both a connection probability matrix and graphon of a graph while remaining computationally efficient.\n\n<Weaknesses>\n\n1. Writing is hard to follow\n- The word “learning” in the title is potentially misleading; the work concerns “estimation”, not machine learning.\n- Key background concepts such as graphon, identification issue, connection probability matrix were introduced too briefly.\n- No visual aids were provided to help readers grasp the pipeline.\n- Several derivations, particularly those involving interpolation, omitted explanatory text between equations.\n- Practical relevance was under-explained: concrete downstream tasks or benchmarks would help. \n\n2. Insufficient experimental verification\n- Table 1 and Table 2 were inconsistent: Table 2 omitted runtime results and the entries for IDs 1, 6, and 7.\n- Experiments appeared limited to rank less than or equal to 3.\n- Graphon estimation was assessed only qualitatively (Fig. 1); no quantitative error metric on graphon (not connection probability matrix) is reported.\n- Real-data experiments were presented, but there is no evaluation of how accurate the estimated graphons or matrices are.\n\n3. The source code is not available.\nThus, there is limitation in reproducing the proposal.", "was_revised": true, "final_justification": "My concerns about a relevance to this venue and a lack of experimental verification have now been resolved through rebuttals. However, a concern regarding readability, presentation, and reproducibility still remains. I hope that the authors can significantly improve the readability while surely providing a source code upon acceptance.", "rebuttal": "Thank you for reviewing our paper. We appreciate your recognition of our proof, method novelty, and algorithm effectiveness. Below, we address your questions one by one.\n\n**1. Concerns about clarity, use of “learning” in the title, and lack of context or motivation.**\n  \nThank you for the feedback. We acknowledge that several aspects of the presentation can be improved to enhance clarity and accessibility.\n\n*(1) On \"learning\" usage:* Our use of \"learning\" follows its statistical meaning in latent structure estimation (e.g., [14], [15]). We understand it could imply a focus on predictive machine learning and are open to changing the title to \"estimation\" to avoid confusion.\n\n*(2) On key concepts:* We agree the introduction of graphons, identifiability, and the connection probability matrix was too brief. In the revision, we’ll expand this section, cite standard references [1], [2], [3], and include a toy example with $f(u,v) = \\\\cos(u-v)$ (see our first response to Reviewer 1DRW) for better intuition.\n\n*(3) On the lack of visual aids:* We will include a schematic figure to illustrate the overall modeling and estimation pipeline, which will help readers understand the structure and flow of our method.\n\n*(4) On missing exposition between equations:* We agree that several derivations, particularly in Section 3.2, can be made more accessible. We will revise this section to add explanatory text and clarify the interpolation-based estimation procedure (see also our first response to Reviewer 1DRW).\n\n*(5) On practical relevance and downstream tasks:* We appreciate this point. In the revision, we’ll add a subsection discussing the utility of estimating the graphon $f$ beyond recovering $P$, focusing on predicting motifs and higher-order structures (see our second response to Reviewer 1DRW). We’ll also clarify its role in network comparison and structure generalization.\n\n**2. Regarding insufficient experimental verification and evaluation.**\n\nThank you for raising these important points. We address each concern as follows:\n  \n*(1) Inconsistency between Tables 1 and 2:* We acknowledge that Table 2 omits runtime results and entries for graphon IDs 1, 6, and 7 to focus on key illustrative cases. We will clarify this in the revision to avoid confusion and include a more comprehensive summary of runtimes and results across all graphons.\n\n*(2) Experiments limited to rank $r\\\\leq 3$:* While our main experiments focus on low ranks for clarity and interpretability, our method extends naturally to higher ranks. Due to space constraints, we prioritized detailed analysis for $r\\\\leq 3$ but will include additional experiments for larger ranks in the supplementary material.\n\n*(3) Quantitative error metrics on graphon estimation:* We agree that quantitative evaluation of graphon estimates is crucial. In the revision, we will add such metrics, including integrated squared error and sup-norm errors, to complement the qualitative assessments in Figure 1.\n\n*(4) Real-data experiments and accuracy evaluation:* While real-data experiments primarily demonstrate practical applicability, we acknowledge the importance of assessing the accuracy of estimated graphons or connection probability matrices. In our response to Q7 below, we provide an illustration by evaluating the estimation quality through motif counting.\n\n**3. Regarding source code.**\n  \nWe fixed the random seed and ran 100 repetitions to ensure reproducibility. The code will be publicly available on GitHub, and the link will be included in the revision. All datasets used are publicly available and cited in the manuscript. \n\n**Q1: Relevance to AI.**\n  \nOverall, statistical network analysis and graphon estimation are increasingly important in machine learning and AI, as reflected by recent work at NeurIPS and related conferences (e.g., [8], [9], [10]). Our methodology advances efficient and accurate network model estimation, with broad impact in domains such as social network analysis [4] and knowledge graphs [5].\n\n**Q2. Regarding the results for IDs 1, 6, 7 and the runtime column in Table 2.**\n  \nDue to page limits, we omitted the results for graphon IDs 1, 6, and 7 under the sparse setting in Table 2, but our method still outperforms others in these cases. The runtime results in Table 2 are similar to those in Table 1, as the network size remains the same. Due to space constraints, we were unable to present these results, but we will include all of them in the revised manuscript.\n\n**Q3. Regarding the scalability of our method to high ranks.**\n\nOur theoretical results hold for any fixed rank $r$, including large values. However, in this paper, we treat $r$ as fixed and do not consider the regime where $r$ grows with the sample size $n$, which poses fundamentally different and more challenging problems. We leave this important direction for future work. Empirically, as $r$ increases, a larger sample size is required to maintain comparable performance (e.g., in terms of MSE), which is consistent with our simulation results. To further demonstrate scalability, we will include additional experiments with $r=5$ in the revised version.\n  \n  **Q4. Regarding application of low-rank methods to real-world data.**\n    \nWhile our low-rank setting assumes $r\\ll n$, the rank $r$ can certainly be larger than $3$. Low-rank approximations are widely used in real-world data analysis. For example, the stochastic block model (SBM) has been extensively applied for community detection in social [11], biological [12], and geological networks [13] due to its interpretability and ability to capture community structures. As noted in lines 101–104 of our manuscript, our framework generalizes low-rank models like the random dot product graph (RDPG) and SBM.\n  \n**Q5. Regarding the relationship between computational cost and rank.**\n    \nWhen the rank $r = O(1)$ is fixed, the computational complexity of our method is $O(r n^\\\\omega)$, where $n^\\omega$ denotes the complexity of matrix multiplication. Since $r$ is a constant, this simplifies to $O(n^\\\\omega)$, indicating that the cost is dominated by matrix operations.\n    \n**Q6. Regarding quantitative graphon-estimation errors.**\n      \nTo provide further illustration, we conducted additional experiments on graphon IDs 3 and 4, comparing the estimated graphon with the true graphon using the maximum entrywise error (i.e., the sup-norm). Due to space constraints, results for other graphons are omitted here but will be included in the revised manuscript.\n\nThe results, summarized in the table below, show that the sup-norm errors of the graphon estimates closely match those of the estimated connection probability matrices, as expected. This demonstrates that the estimation error is well controlled in practice, consistent with our theoretical guarantees in Theorems 3.2 and 3.8.\n    \n*Table R2. Simulated sup norms for graphons across 100 independent trials.*\n      \n| Graphon ID | Sup-norm ($\\times 10^{-2}$) | Std. Dev. ($\\times 10^{-3}$) |\n|-|-|-|\n|3|12.053|10.738|\n|4|15.539|12.037|\n      \n**Q7. Regarding validating the quality of the real-data estimates.**\n      \nUsing the U.S. political blog dataset as an illustrative example, we demonstrate the advantages of our method through extensive comparisons with existing approaches.\n    \nSpecifically, we estimated the underlying graphon from the observed network and computed the expected densities of various motifs, such as triangles, squares, and 5-cycles (see also our response to Reviewer 1DRW for technical details). For competing methods, we generated synthetic networks from their estimated connection probability matrices and performed motif counting on these networks. We then compared the absolute differences in motif counts - normalized by the total possible in a complete graph of the same size - between the original and generated networks. The results, summarized in Table R3, show that our method consistently achieves smaller errors in motif prediction than competing approaches.\n    \n*Table R3. Motif count errors and runtime for each method.*\n      \n|Method|Triangle counting error$(\\times 10^{-4})$|Run time(s)|Square counting error$(\\times 10^{-5})$|Run time(s)|5-cycle counting error$(\\times 10^{-6})$|Run time(s)|\n|-|-|-|-|-|-|-|\n|Ours|0.252|0.167|0.761|0.198|3.848|0.175|\n|N.S.|1.709|119.812|3.758|120.837|9.039|123.863|\n|Nethist|8.087|19.082|1.809|20.523|4.383|22.427|\n|USVT|4.449|15.97|1.712|17.098|5.149|19.439|\n|SAS|1.327|3.018|2.256|4.730|4.960|5.237|\n\nMoreover, as shown in Table R3, our approach significantly improves computational efficiency. After estimating the graphon, the expected density of any motif in networks of any size can be quickly approximated using the plug-in method, with only a constant number of matrix operations per sample. In contrast, existing methods require explicit motif counting in generated networks, which is computationally expensive (see [7] for details). This blend of efficiency and accuracy is particularly beneficial for downstream tasks where motif statistics are crucial (e.g., [6]).\n    \n[1] Chan, S., & Airoldi, E. \"Consistent histogram estimator...\"\n    \n[2] Zhou, Z., & Amini, A. A. \"Spectral clustering for...\"\n    \n[3] Abbe, E., & Sandon, C. \"Community detection in...\"\n    \n[4] Li, Y., et al. \"FairLP: Fair link...\"\n    \n[5] Nickel, M., et al. \"Review of relational...\"\n    \n[6] Milo, R., et al. \"Network motifs: Building...\"\n    \n[7] Jin, J., et al. \"Counting Cycles with...\"\n    \n[8] Li, M., et al. \"Network change point...\" NeurIPS, 2022.\n\n[9] Gaucher, S., & Klopp, O. \"Optimality of variational...\" NeurIPS, 2021.\n\n[10] Valdivia, E. A., & De Castro, Y. \"Latent distance estimation...\" NeurIPS, 2019.\n\n[11] Al-Anzi, B., et al. \"Modeling modular structure...\"\n\n[12] Holland, P. W., et al. \"Stochastic blockmodels: First...\"\n\n[13] Davari, A., et al. \"Enhancing reservoir production...\"\n\n[14] Aicher, C., et al. \"Learning latent block...\"\n\n[15] Kitson, N. K., et al. \"Survey of Bayesian...\""}, {"review_id": "uZyzZwvZ1o", "reviewer": "Reviewer_BVhG", "summary": "This paper offers a framework for estimating the connectivity matrix and the underlying function of a low-rank graphon through subgraph counts (AKA motifs). The authors' main theorem is an error guarantee in the sup-norm for both the connectivity matrix $P$ (Theorem 3.6) and the graphon function $f$ (Theorem 3.8). The former is noted to match pre-existing minimax error rates for smooth graphon estimation. Additionally, the authors perform simulation studies to compare their method with various prior algorithms, in terms of mean-squared errors and runtimes.", "questions": "- Literature review seems sparse: can you cite more papers on matrix sensing / matrix completion, as well as Holder-smooth graphon estimation? Putting in an appendix would be okay. \n\nChen, Yudong, et al. \"Completing any low-rank matrix, provably.\" The Journal of Machine Learning Research 16.1 (2015): 2999-3034.\n\nKLOPP, OLGA, ALEXANDRE B. TSYBAKOV, and NICOLAS VERZELEN. \"ORACLE INEQUALITIES FOR NETWORK MODELS AND SPARSE GRAPHON ESTIMATION.\" The Annals of Statistics 45.1 (2017): 316-354.\n\nJalan, Akhil, et al. \"Transfer Learning for Latent Variable Network Models.\" The Thirty-eighth Annual Conference on Neural Information Processing Systems.\n\n- Eq. 1 seems to imply that the graphon is “almost” Lipschitz, since each G_k is L^2, so it must be bounded outside a set of measure zero in [0,1]. So, I understand the main difference between your model and smooth graphons to be this measure zero set. \n\nHow critical is this set of measure zero for \n(a) real-world modeling applications such as the biological networks you cite, and \n\n(b) theoretical work such as your estimation algorithms, as compared to USVT or Gao’s averaging technique? \n\nSome discussion on both points would be helpful.\n\n- The discussion of theoretical contributions on line 42 begins with Lemmas A8-A10. Could these be consolidated into a single statement and put in the main body? If they are a core contribution of the work, I feel they should be at least discussed in the main text, even if space constraints prevent the proof from being included therein. \n\n- Line 126: Can Xu 2018 not also take advantage of the rank-1 structure to do better than O(n^3) time? If I recall, Xu’s algorithm is bottlenecked by computing the SVD itself. \n\n- Theorem 3.1: You are citing previous minimax lower bounds later for smooth graphon estimation, so I understand these are a special case of your model. What is an example of a graphon that falls into your model but does not meet the piecewise Holder assumption? \n\n- Theorem 3.2: The use of a canonical G_1 seems similar to the idea of estimating graphons up to equivalence relations as defined in e.g. Klopp 2017, among others. Can you explain the differences?  \n\n- Line 187: What is the citation is needed for the complexity of matrix multiplication? I think would be more readable if you just wrote $O(n^\\omega)$. \n\n- Line 193-194: You emphasize that your method does not require smoothness assumptions, but Theorem 3.2 requires a Lipschitz G_1, which would imply a Lipschitz f in the rank-1 case. Lipschitz smoothness is in fact stronger than Holder smoothness as in Xu 2018. Can you clarify how your method does not require smoothness? \n\n- Assumption 3.5(iii): Similarly, the assumption of bounded G_k functions, along with them being in L^2, seems to imply a lot of regularity, since the G_k must be Lipschitz. How precisely does your model differ? I apologize for being repetitive. \n\n- Table 1 would benefit from bolds / italics to emphasize the best performing methods in each scenario \n\n- Table 1: Is the runtime an average across all 100 runs? Reporting stdev or quantile interval of runtimes would be helpful. \n\n- Table 1: It seems USVT is comparable in MSE across all scenarios except #4; however, even here it is comparable in terms of max error. Why is USVT so effective in all of these examples? Are there any motivating examples of graphons where USVT is clearly worse? \n\n- Table 2: Why does sparsity make your method so much better than others? Discussion would be helpful. \n\n- Table 2: It would be helpful to see how methods’ performance scales with sparsity, ranging from $\\rho = 1/\\sqrt{n}$ up to $\\rho = 1$. \n\n- Appendix A6: Can you report the MSE numbers and comparisons to your baseline methods (USVT, neighborhood smoothing, etc) for these experiments? With the figures as they are now, it is very unclear why your method should be preferable for these real-world graphs.", "limitations": "There is not much discussion of the limitations of their work, aside from a suggestion on future work in the conclusion. I would suggest a deeper discussion of: \n\n- The unique aspects of their model as opposed to smooth graphon models. \n\n- The real-world applicability of their model, perhaps to the graphons they study in Appendix A.6 or others. \n\n- A more extensive discussion of why their method only seems to outperform baselines in a sparse graphon regime.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 2, "strengths_and_weaknesses": "The paper's main strength is presenting and addressing graphon estimation in a new framework: namely, estimating both the graphon connectivity matrix and the underlying function, through efficient algorithms that leverage motifs. Additionally, the numerical experiments are extensive, and demonstrate their method is advantageous (at least in a very low sparsity regime of $\\rho = 1/\\sqrt{n}$). The algorithm is clean, scalable, and intuitive. \n\nThe main weaknesses are:\n\n1. Unclear scope for their model of low-rank graphons, which seem quite similar to the well-studied case of piecewise Holder-smooth graphons. Experiments show that prior methods are mostly competitive even for the authors' chosen simulated graphons (see my questions below), so it is not clear what sort of graphon problems really fit their specific theoretical assumptions and algorithm.  \n\n2. Lack of real-world experiments, which appear in Appendix A.6 but in very limited form (see my questions) below.", "was_revised": true, "final_justification": "In light of the additional discussion in the review period, especially the new experiments which examine a range of sparsity parameters for $\\rho$, and the responses to Q6 and Q7 for reviewer n6Ak, I will update my score to a 4.", "rebuttal": "Thank you for taking the time and effort to review our work, and for your positive feedback on our algorithm and theory. We will now address each of your questions one by one.\n\n**1. Regarding additional literature review.**\n\nThank you for your helpful suggestions and for recommending these excellent papers. We agree that a more comprehensive literature review will strengthen the manuscript. We will cite these works and provide an expanded discussion on matrix sensing, matrix completion, and Hölder-smooth graphon estimation in the revised version, including additional details in the appendix as suggested.\n\n**2. Regarding Eq. (1) and the \"almost\" Lipschitz property of the graphon.**\n\nEquation (1) states that our graphon $f$ is low-rank, with each component $G_k$ in $L_2$. We address your concerns from two angles: the low-rank property and the measure-zero set.\n\nFrom the low-rank perspective, this is a key distinction from approaches like USVT. The low-rank assumption provides two main benefits: (i) it enables consistent estimation of both the connection probability matrix $P$ and the graphon $f$ (see our response to Reviewer 1DRW for more on estimating $f$); and (ii) it improves computational efficiency, with complexity comparable to matrix multiplication. In contrast, methods like those in [4], [8] incur much higher computational costs.\n\nRegarding the measure-zero set and continuity assumptions, unlike Gao [5] and USVT [2], we do not require the graphon $f$ to be continuous or in stochastic block model (SBM) form for estimating $P$. This flexibility is practical, as real-world networks, such as biological networks, can exhibit sharp structural heterogeneity or abrupt changes that violate smoothness assumptions. Allowing for discontinuities on measure-zero sets makes our model more flexible and realistic.\n\nSuch irregularities challenge classical methods like the Network Histogram [4] and SAS [6], which may fail or yield biased estimates. Moreover, Gao’s averaging technique has a relatively high computational complexity.\n\nWhile our approach offers these theoretical and practical advantages, further investigation is needed to fully assess the impact of these assumptions on real-world datasets. We see this as an important avenue for future research.\n\n**3. Regarding Lemmas A8-A10.**\n\nThank you for your suggestion. Lemmas A8–A10 are technical lemmas that primarily serve as auxiliary results for the main theoretical proofs. We will consolidate them into a single statement and incorporate the content into the main article.\n\n**4. Regarding Xu's method in rank 1 conditions.**\n\t \nIf it is known a priori that the connection probability matrix is rank-1, a truncated version of Xu’s USVT method could, in principle, be accelerated to $O(n^2)$ time by computing only the top singular value and its corresponding singular vectors using efficient algorithms such as the power iteration method.   For the case of $r>1$, since they use SVD, their method appears to be slower than ours based on the simulations.\n\n**5. Regarding Theorem 3.1.**\n\nThank you for your question. Theorem 3.1 concerns the estimation of the connection probability matrix $P$ in the rank $r=1$ setting. In this case, no additional smoothness or continuity conditions are required on $G_1$. It suffices that $G_1$ belongs to $L_2$ and is non-zero on a set of positive measure. Notably, $G_1$ may contain many discontinuities and does not need to be piecewise Lipschitz.\n\n**6. Regarding the use of a canonical $G_1$.**\n\nThank you for your question. In Klopp et al. (2017), the identifiability issue is addressed by defining a distance between functions that accounts for measure-preserving transformations (see their Eq. (14) for details). In contrast, our approach resolves identifiability by defining a canonical graphon function.\n\n**7. Regarding the complexity of matrix multiplication.**\n\t\nThank you for your suggestion. We will use the notation $O(n^\\\\omega)$ to clarify the expression. The relevant citation is [7], which we have now added to Appendix A.1 and will include in the main text.\n\n**8. Regarding the smoothness assumptions.**\n\nThank you for your question. We would like to clarify that lines 193–194 refer to Remark 3.4, where we state that no smoothness assumptions are needed for estimating the connection probability matrix $P$. In contrast, Xu (2018) requires smoothness assumptions to estimate $P$.\n\nAdditionally, our analysis focuses on the sup-norm error, whereas Xu (2018) primarily considers the $L_2$ norm. Their approach does not estimate the graphon function $f$ itself. The Lipschitz condition arises only when estimating $f$, which is a fundamentally more challenging and ill-posed problem due to identifiability issues.\n\nAssumption 3.5(iii) pertains to graphon estimation, which Xu (2018) cannot handle. The condition that $G_k$ is bounded can be relaxed, and we leave this for future work.\n\n**9. Regarding results in Table 1.**\n\nWe will use boldface  to highlight the best-performing methods in the revised version. As for runtime values, they are averaged over 100 runs, and we will add the standard deviation (which is relatively small) in the revised manuscript.\n\nThe rate of USVT is indeed nearly minimax optimal in terms of MSE under certain conditions [2], so it is not surprising that it performs so well. However, we emphasize that USVT cannot estimate the graphon function itself, which is the key distinction between our approach and theirs.\n\n**10. Regarding results in Table 2.**\n\nWhile our simulations show that our method works for sparse graphs, the theoretical guarantees for this regime are left for future work, as mentioned in the discussion. Intuitively, Equation (5) is homogeneous with respect to sparsity, suggesting that our theoretical results may extend to the sparse regime. A rigorous proof, however, would require extending the theoretical arguments in our paper.\n\nRegarding the performance of all methods as sparsity varies from $n^{-1/2}$ to $1$, we conducted additional simulations, and the results are shown in Table R1. As sparsity increases, the estimation error for all methods also increases. However, our method consistently outperforms others in the sparse regime and remains competitive as sparsity increases, highlighting its particular strength for estimating sparse networks.\n\n**Table R1. Results for estimating the connection probability matrix $P$ generated by sparse graphons across 100 independent trials.**\n\n|Graphon ID|Sparsity Parameter $\\rho_n$|Method|MSE $(\\times 10^{-4})$|Std. dev of MSE $(\\times 10^{-6})$|Max. Error $(\\\\times 10^{-2})$|Std. dev of Max. Error $(\\times 10^{-3})$|\n|----------|---------------------------|------|----------------------|----------------------------------|----------------------------|-----------------------------------------|\n|4|$n^{-1/3}$|Ours|0.178|0.663|5.722|9.922|\n| | |N.S.|31.285|140.98|99.907|0.15|\n| | |USVT|0.389|1.964|6.163|24.638|\n| | |Nethist|1.193|7.809|7.815|0.278|\n| | |SAS|0.597|3.787|99.72|0.985|\n| |$n^{-1/6}$|Ours|0.752|3.501|10.022|12.695|\n| | |N.S.|8.833|86.337|98.761|0.416|\n| | |USVT|1.348|6.356|12.44|11.336|\n| | |Nethist|13.66|89.165|27.699|1.149|\n| | |SAS|5.356|32.228|99.597|2.321|\n| |$n^{-1/10}$|Ours|1.116|4.874|12.412|14.103|\n| | |N.S.|3.264|10.317|38.125|129.087|\n| | |USVT|2.161|10.221|15.706|14.102|\n| | |Nethist|34.658|221.149|45.841|2.907|\n| | |SAS|14.681|59.42|93.407|72.598|\n|5|$n^{-1/3}$|Ours|0.258|1.205|4.93|7.207|\n| | |N.S.|29.992|170.322|99.969|0.167|\n| | |USVT|0.9|3.584|6.231|5.969|\n| | |Nethist|3.316|10.137|6.766|0.074|\n| | |SAS|0.821|4.783|97.805|101.723|\n| |$n^{-1/6}$|Ours|1.145|34.613|11.757|40.912|\n| | |N.S.|3.624|6.686|20.814|98.466|\n| | |USVT|3.039|11.992|12.511|9.675|\n| | |Nethist|30.673|72.197|23.993|0.395|\n| | |SAS|9.165|18.182|74.31|132.569|\n| |$n^{-1/10}$|Ours|1.338|33.349|10.409|30.081|\n| | |N.S.|4.852|10.989|16.784|9.73|\n| | |USVT|4.626|18.243|15.865|13.431|\n| | |Nethist|58.583|185.89|39.152|5.418|\n| | |SAS|9.281|21.39|93.009|68.993|\n\n**11.  Regarding quantitative graphon-estimation errors, and validating the quality of the real-data estimates**\n\nThank you for your question. We kindly refer you to our response Q6 and Q7 to Reviewer n6Ak.\n\n**W1. Regarding the low-rank graphon setting, performance of the experiments, and the theoretical assumptions.**\n\nWe kindly refer you to our responses 2, 5, 6, 8, 9, 10.\n\n**W2. Regarding the real-world experiments.**\n\nWe kindly refer you to our response Q7 to Reviewer n6Ak, where we conducted experiments to validate the quality of the real-data estimations.\n\n[1] Klopp et al., \"Oracle inequalities for network models...\" (2017): 316-354.\n\n[2] Xu, \"Rates of convergence of spectral methods...\" (2018): 5433-5442.\n\n[3] Borgs et al., \"Graph limits and parameter testing...\" (2006): 261-270.\n\n[4] Olhede & Wolfe, \"Network histograms and universality...\" (2014): 14722-14727.\n\n[5] Gao et al., \"Rate-optimal graphon estimation...\" (2015): 2624-2652.\n\n[6] Chan & Airoldi, \"A consistent histogram estimator...\" (2014): 208-216.\n\n[7] Vassilevska Williams, \"Multiplying matrices faster...\" (2012): 887-898.\n\n[8] Bickel et al., \"The method of moments and degree distributions...\" (2011): 2280-2301."}, {"review_id": "Nc3kDGf7hP", "reviewer": "Reviewer_SWT9", "summary": "The paper addresses the problem of estimating the graphon function  $f: [0,1]^2 \\to [0,1]$ that governs the edge probabilities in an undirected random graph. Each of the $n$ nodes in the graph is associated with an unobserved latent variable $U_i$, drawn independently from the uniform distribution on $[0,1]$. Conditional on these latent variables, the presence of an edge between nodes $i$ and $j$ is determined by a Bernoulli trial with success probability $f(U_i, U_j)$.\n\nThe authors propose new algorithms for estimating the graphon $f$, and establish that, under certain structural assumptions, the estimator $\\hat{f}$ achieves a convergence rate of  $\\sqrt{\\frac{\\log(n)}{n}}$ in the supremum norm. A key assumption is that the true graphon $f$ admits a decomposition as a finite sum of $r$ orthogonal, rank-one symmetric functions, i.e., functions of the form $ G(u)G(v)$, where each $G$ is a univariate function. Furthermore, it is assumed that the functions $G$ are Lipschitz continuous and that one of them is known to be monotone increasing. These structural constraints play a central role in enabling consistent and computationally efficient estimation.", "questions": "1. Could you provide some hints on why the conditions required in Section 3 could be acceptable in practice?  \n\n2. How should the equations (5) be solved?  \n\n3. You claim that your proposal based on counting subgraphs is computationally efficient. I did not find the justification of this claim in the main body. Did I miss something? If not, and if it is a crucial property of your method as compared to past work, it might be beneficial to move it to the main body of the paper.\n\n4. Is it easy to extend the results of Section 3.2 to the case where $r$ might depend on $n$ and tend to infinity when $n$ tends to infinity? If yes, how then does $r$ enter into the rate?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. I enjoyed reading this paper. It is well polished and pleasant to read.  \n2. All the math details that I checked appear to be correct.  \n3. The obtained rates of estimation match the best known rates in the problem of graphon estimation.\n\n**Weaknesses**\n1. The conditions imposed on the true graphon appear to be quite strong, especially when it comes to considering the case $r > 1$. Indeed, both the condition that the $G_i$s are orthogonal and that they are orthogonal to the constant function is a strong assumption that has no reason to be satisfied.  \n2. The condition 3.7 that essentially requires that $G_1$ is an increasing function is overly restrictive. I cannot think of a relevant example of application in which such a condition could be acceptable.  \n3. The paper would be much better if more intuitions were given about the construction of the estimators. Here are some examples of intuitive explanations that can be added, but of course this is just a sample:  \n   a. The estimator provided at line 150 is based on the fact that the $i$th order statistic of the sample of uniform in $[0,1]$ random variables is close to $i/(n+1)$.  \n   b. The rate of convergence $n^{-1/2}$ corresponds to the standard nonparametric rate $N^{-\\beta/(2\\beta + d)}$, where $\\beta$ is the smoothness, $d$ is the dimension and $N$ is the sample size. Since in the problem under consideration the observations are the edges, the sample size $N$ is $n^2$. The Lipschitz assumption implies that $\\beta = 1$, and the dimension is obviously $d = 2$.\n\n4. Many relevant references on graphon estimation are missing. I am not claiming that these references have a direct connection to the obtained results, but they have to be discussed in order to situate the current work in the landscape of already existing results. The papers I have in mind are:\n- E. Donier-Meroz, A. Dalalyan, F. Kramarz, P. Choné, X. D'Haultfoeuille (2023). *Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels*. arXiv:2304.03590  \n- O. Klopp and N. Verzelen. *Optimal graphon estimation in cut distance*. *Probability Theory and Related Fields*, 174(3), pp. 1033–1090 (2019)  \n- O. Klopp, A. Tsybakov and N. Verzelen. *Oracle inequalities for network models and sparse graphon estimation*. *Annals of Statistics*, 45(1), pp. 316–354 (2017)", "was_revised": true, "final_justification": "I agree with the authors’ responses to my concerns regarding the orthogonality assumption and the condition that \\( G_1 \\) is monotone. However, I encourage the authors to consider these conditions jointly, together with the Lipschitz condition.  \n\nI am fully satisfied with items 3-5 of their response. As for item 6, I find the answer less convincing. Indeed, Algorithm 3 specifies that line 2 of Algorithm 2 should be used, which implies that the nonlinear system (5) must be solved. The computational complexity of this step (and therefore of Algorithm 3) remains unclear.  \n\nFinally, the fact that only the case of fixed \\( r \\) is considered remains a weakness of the paper.  \n\nOverall, I believe the paper merits publication. However, given the weaknesses noted in the reviews (some of which were not fully addressed in the rebuttal), I consider “weak accept” to be the appropriate score.", "rebuttal": "Thank you for your review and the positive feedback. We truly appreciate your recognition of our writing, your checking of our mathematics, and your affirmation of our rate. We will address each of your comments one by one in the following response.\n\n**1. Regarding the conditions imposed on the graphon.**\n\nThank you for your comment. We would like to clarify that the orthogonality assumptions are standard in the literature for functional decompositions and low-rank models. Formally, the assumption is a natural consequence of the Hilbert-Schmidt theorem, which guarantees that any symmetric, square-integrable kernel admits an eigen-decomposition with orthogonal eigenfunctions (see e.g., Chapter 10 in [4]). For the relationship between graphons and the Hilbert-Schmidt norm, we refer to Section 2.3 of [5]. Therefore, these conditions do not limit the generality of our approach, but rather allow us to present the results and the estimation procedure in a more interpretable and mathematically tractable way.\n\n**2. Regarding condition 3.7.**\n\nThank you for your insightful question. In graphon estimation, it is well-known that the graphon is geneally non-identifiable - it is only defined up to measure-preserving transformations (see, for example, [1] for discussions on identifiability). Therefore, when estimating the graphon itself, the literature generally requires additional conditions. One example is [3], where the authors assume that the true graphon satisfies certain Lipschitz conditions and has sparse gradients. Our condition 3.7 serves a similar purpose, enabling the estimation of the graphon $f$.\n\nRegarding estimating graphons with reference to $G_1$, we can relax our approach by considering each $G_i$ ($i = 1, \\\\ldots, n$) as a potential reference function. For each $G_i$, we estimate the graphon $f$ as described in our method referencing $G_1$, then compare the expected motif (e.g. triangles, stars, and so on) densities from the estimated $\\hat{f}$ with the observed motif densities in the data. By evaluating this criterion for all $i$, we select the $\\\\hat{f}$ that best matches the empirical motif distributions. This relaxation yields a more flexible approach, and we will include a remark in the paper to clarify this improvement. We leave the exploration of weaker conditions as future work.\n\n**3. Regarding intuitions about the construction of the estimators.**\n\nThank you for your detailed and helpful suggestions. We especially appreciate your examples clarifying the intuition behind the estimator based on order statistics and the convergence rate in terms of smoothness, dimension, and sample size. We will incorporate these explanations into the revised manuscript to improve clarity and help readers better understand our methods. Thank you again for your valuable feedback.\n\n**4. Regarding the literature review.**\n\nThank you for pointing out these important references. Discussing a broader range of related work helps position our contributions more clearly. In the revised version, we will cite and discuss relevant works on graphon estimation, to provide a more complete literature review.\n\n**5. Regarding the solution of equations (5).**\n\nThanks for your question. In our implementation, we solve it numerically using the nleqslv package in R, which is designed for finding roots of nonlinear systems. This package applies standard numerical methods (such as Broyden’s or Newton-type algorithms) to obtain solutions efficiently. The speed of solving the equation is fast in practice, and we have not observed any anomalies. We will mention this in the revision.\n\n**6. Regarding computational efficiency of our algorithm.**\n\nThank you for your comment. We believe Appendix A.1 addresses your concern. In Appendix A.1, Algorithm 3 shows how lines and cycles allowing repeated nodes can be efficiently computed via matrix multiplication, serving as a surrogate for counting lines and cycles without repeated nodes. This approach is further justified by Lemma A.2 and Theorem A.3, which demonstrate that the approximation error introduced is small and does not affect the error rate in our main theorem. Due to space constraints, these details were omitted from the main text but will be incorporated in the revised version.\n\n**7. Regarding the case where $r$ diverges $n$.**\n\nThank you for your question. We treat $r$ as fixed in this paper, and we believe that the theory for the regime where $r$ grows with $n$ is fundamentally different. If $r$ grows with $n$, the model complexity increases alongside network size, making inference significantly more challenging - similar to high-dimensional or nonparametric settings. Consequently, theoretical guarantees and methods for fixed-rank cases generally do not apply, and larger sample sizes are needed for comparable estimation accuracy. Addressing this growing-rank regime requires new theoretical tools and remains an open research problem. Therefore, we leave it for future work. \n\nEmpirically speaking, when $r$ increases, a larger sample size is required to achieve the similar performance (e.g., in MSE and sup-norm), which aligns with our simulation experiments.\n\n[1] Lovász, László. Large networks and graph limits. Vol. 60. American Mathematical Soc., 2012.\n\n[2] Olhede, Sofia C., and Patrick J. Wolfe. \"Network histograms and universality of blockmodel approximation.\" Proceedings of the National Academy of Sciences 111, no. 41 (2014): 14722-14727.\n\n[3] Chan, Stanley, and Edoardo Airoldi. \"A consistent histogram estimator for exchangeable graph models.\" In International Conference on Machine Learning, pp. 208-216. PMLR, 2014.\n\n[4] Ash, Robert B. Real analysis and probability: probability and mathematical statistics: a series of monographs and textbooks. Academic press, 2014.\n\n[5] Xu, Jiaming. \"Rates of convergence of spectral methods for graphon estimation.\" International Conference on Machine Learning. PMLR, 2018."}]

Author rebuttal:

Meta-review: This paper proposes a novel and computationally efficient method for
estimating low-rank graphons, a significant problem in network analysis.
The core contribution is an approach that jointly estimates the connection
probability matrix and the underlying graphon function using subgraph
counts, supported by strong theoretical guarantees on the estimation error.

Initially, this was a classic borderline paper. Reviewers unanimously
praised the technical novelty and theoretical rigor but raised significant
and valid concerns about the empirical validation and presentation clarity.
The original submission lacked quantitative evaluation on real-world data,
provided limited simulation results, and did not sufficiently motivate the
practical utility of graphon estimation beyond recovering the connection
matrix.

However, the authors provided an exceptionally thorough and convincing
rebuttal that fundamentally strengthened the submission. They conducted
numerous new experiments, including a quantitative evaluation of motif
prediction on real-world data, additional metrics for graphon estimation
error, and new analyses under varying sparsity and rank-mismatch
conditions. This extensive new evidence successfully addressed the primary
concerns of the reviewers, leading two of them to raise their scores in
favor of acceptance. It needs to be emphasised that the current state of
this submission (specifically, the section of numerical experiments) has
not met the standard of NeurIPS publication, and these experiment
supplements in the rebuttal must be included to the final preparation.

While some minor concerns remain regarding the presentation and certain
theoretical assumptions, the consensus is that the paper's novel
methodology, strong theoretical guarantees, and now substantially improved
empirical support make it a valuable contribution. The paper is recommended
for acceptance.
Decision: Accept (poster)