A Few Moments Please: Scalable Graphon Learning via Moment Matching
Authors: Reza Ramezanpour
Victor M. Tenorio
Antonio G. Marques
Ashutosh Sabharwal
Santiago Segarra
Venue: NeurIPS 2025 poster ()
Keywords: Graphon estimation
Moment matching
implicit neural representations
MomentMixup
Primary area: general_machine_learning

Abstract: Graphons, as limit objects of dense graph sequences, play a central role in the statistical analysis of network data. 
However, existing graphon estimation methods often struggle with scalability to large networks and resolution-independent approximation, due to their reliance on estimating latent variables or costly metrics such as the Gromov-Wasserstein distance. 
In this work, we propose a novel, scalable graphon estimator that directly recovers the graphon via moment matching, leveraging implicit neural representations (INRs). Our approach avoids latent variable modeling by training an INR--mapping coordinates to graphon values--to match empirical subgraph counts (i.e., moments) from observed graphs.
This direct estimation mechanism yields a polynomial-time solution and crucially sidesteps the combinatorial complexity of Gromov-Wasserstein optimization. 
Building on foundational results, we establish a theoretical guarantee: when the observed subgraph motifs sufficiently represent those of the true graphon (a condition met with sufficiently large or numerous graph samples), the estimated graphon achieves a provable upper bound in cut distance from the ground truth. Additionally, we introduce MomentMixup, a data augmentation technique that performs mixup in the moment space to enhance graphon-based learning. 
Our graphon estimation method achieves strong empirical performance--demonstrating high accuracy on small graphs and superior computational efficiency on large graphs--outperforming state-of-the-art scalable estimators in 75\% of benchmark settings and matching them in the remaining cases. Furthermore, MomentMixup demonstrated improved graph classification accuracy on the majority of our benchmarks.

A Few Moments Please: Scalable Graphon Learning via Moment Matching
Reza Ramezanpour
Victor M. Tenorio
Rice University
King Juan Carlos University victor. tenoriouurjc.ccooomoooo.........
rr68@rice.edi
Antonio G. Marques King Juan Carlos University antonio. garcia marquesuurjc.ess
Ashutosh Sabharwal Rice University ashu@rice. edu
Santiago Segarra
Rice University
segarraGrice.eo edu
Abstract
Graphons, as limit objects of dense graph sequences, play central role in the statistical analysis of network data. However, existing graphon estimation meth- ods often struggle with scalability large networks and resolution-indeeendee approximation, due to their reliance on estimating latent variables or costly metrics distance. In this work, we propose a novel, scal-
such as the Kromov-Wasserstee able graphon estimator that directly recovers the graphon via moment matching, leveraging implicit neural representations (INRs). Our approach avoids latent variable modeling by training an INR- -aammpn coordinates to graphon values-tu to match empirical subgraph counts (i.e., moments) from observed graphs. This direct estimation mechanism yields polynomial-time -imee solution and crucially sidesteps the combinatorial complexity foundational results, we establish theoretical guarantee: when the observed sub- graph motifs sufficiently represent those of the true graphon (a condition met with sufficiently large numerous graph samples), the estimated graphon achieves a provable upper bound cut distance from the ground truth. Additionally, we introduce MomentMixup, data augmentation technique that performs mixup in the moment space to enhance graphon- based learning. Our graphon estimation method achieves strong empirical performance demaonstredmmotttitiinng high accuracy small graphs and superior computational efficiency on large graphs graphs-outperfon outperforming state-of-tte ofae--of-the-ar ff-thhh-rt scalable estimators in 75% of benchmark settings and matching them in the remaining cases. Furthermore, MomentMixup demonstrated improved graph classification accuracy the majority of our benchmarks.
Wasserr-tsse optimization. Building on
Introduction
Networks are fundamental structures for representing complex relational data across diverse domains, from social interactions and biological systems to technological infrastructures 3T. Understand- ing the underlying principles governing these networks is crucial for tasks such as link prediction (26],
community detection [30], and, more broadly, node or graph classification (25). Graphons, or graph limits, have emerged as powerful mathematical framework for capturing the asymptotic structure of sequences of dense graphs [8] 2]. They provide continuous, generative model for graphs, enabling principled statistical analysis and offering canonical representation for large networks. Graphons have been successfully applicd to derive controllers for large networks [1], to understand
network games with many actors [23]. to perform data augmentation in graph settings 21 [3], and
"Source Code: http://///sttaaccccc////rr/rr/rp htt.///rrrerr/pppppoooooooaaaaaa
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

to aid in the topology inference of partially observed graphs 28 20 As such, developing accurate and efficient methods for estimating graphons from observed network data is a central problem in network science and machine learning.
Estimating graphons from finite, potentially noisy graph observations presents significant challenges. Many existing approaches suffer from computational scalability issues when applied to large net- works 35). Furthermore, their resolution is limited by the size of the sample graphs, and obtaining resolution-free approximation of the underlying continuous graphon can be difficult [7]. For instance, implicit neural representations (INRs) have been explored for graphon estimation due their ability to model continuous functions (34). However, estimating the latent variables of the nodes to train the INRs remains challenge, and oftentimes the literature resorts to computationally demanding optimal cunsport-inspiree losses, like the Fromov-Wassersterr (GW) distance for optimization. While recent scalable methods have made progress [3), there remains need for estimators that combine high accuracy, computational efficiency, and direct graphon recovery without complex intermediate steps.
In this paper, we introduce a novel and scalable approach for graphon estimation via moment matching, designed to overcome these prevalent limitations. Our method directly recovers the graphon by leveraging subgraph counts (graph moments) from observed data, thereby bypassing the need for latent variables and their associated complexities. We represent the graphon using an INR, continuous function parameterized by neural network that maps coordinates in [0, 1] to the corresponding graphon value. The parameters of this INR are learned by minimizing the discrepancy between the moments derived from the INR and the empirical moments computed from the input graph(s). This direct recovery strategy, crucially, leads to polynomial-time estimation algorithm and does not rely on combinatorial GW distances, distinguishing it from approaches like IGNR 34. Our approach is underpinned by a theoretical result, building upon foundational work on convergent graph sequences [5), which establishes that the motifs (subgraph patterns) in the observed graph data sufficiently represent the motifs present in the true underlying graphon-a condition met with sufficiently large or numerous graph samples-then the cut distance between the estimated and true graphons is provably upper bounded. Additionally, we propose MomentMixup, novel data augmentation technique that operates by interpolating graph moments between classes and then learning the corresponding mixed graphons, offering improvement over existing mixup strategies in the graphon domain [3].
Our contributions are threefold:
1. We propose MomentNet, a scalable graphon estimator based on moment matching with INR, offering a resolution-free and estimation recovery mechanism.
2. We provide theoretical guarantee linking the fidelity of motif representation observed data to the estimation accuracy in terms of cut distance.
3. We introduce MomentMixup, an effective data augmentation method in the moment space for graphon-based learning tasks.
The remainder of this paper is structured as follows: Section 2 presents the necessary background concepts and related works. Section 3 details our momentt-atchingg INR approach for graphon esti- mation, including its theoretical characterization. Section inttroduces MomentMixup, our approach for data augmentation in graph classification tasks. Section S evaluations in both synthetic graphon estimation and data augmentation for graph classification. Finally, Section 6 concludes the paper and discusses future directions.
presents our comprehensive empirical
2 Background, Related Works and Problem Formulation
In this section, we introduce the foundational concepts of graphons, motif densities, INRs for graphon estimation, and mixup for data augmentation. We also formally state the graphon estimation problem addressed in this paper. In all these topics, we provide a summary of the literature, although a detailed discussion of related works can be found in Appendix A
Graphons A graphon, short for "graph function,"" " is a fundamental concept in the theory of graph limits, serving as limit object for sequences of dense graphs [8 5 Formally, graphon W is a symmetric measurable function W [0, 1]2 - [0. 1]. Intuitively, the unit interval [0, 1] can be thought of as latent space for the graph nodes. For any two points x, y [0, (representing latent

---

positions), the value W (2 y) represents the probability of an edge forming between nodes associated with these latent positions.
random graph G., (W) with n nodes can be generated from a graphon W by sampling n i.i.d. latent positions 7,, "2,,.-- 7m ~ [0 1] and, for each pair of distinct nodes (i, with S < n, an edge j) is included in G,2 (W) independently with probability W (m), πy). Graphons are inherently invariant to permutations of node labels in the generated graphs, meaning that different orderings of the latent positions 7) that preserve their relative positions in [O, 1] (or more formally, measure- preserving bijections of [0. 1)) lead equivalent graphon representations. The natural distance metric capturing this invariance is the cut distance [S].
Motif Densities from Graphons A key property of graphons is their ability to characterize the expected density of small subgraphs, often called motifs [5] [8]. For simple graph F (the motif), whose node and edge set are represented by VF and &p, respectively, with k [VF], its homomorphism density in a graphon W,, denoted t(F, W), is defined as
t(F, () (LF,W)/
f
II 10.11" (KJ)EE
(Tis n7))
II dnp. LEVF
(1)
This integral represents the probability that & randomly chosen latent positions from [0. 1] induce a subgraph homomorphic to according to the edge probabilities defined by W. For a sufficiently large graph G' sampled from W, the empirical count of motif F in G. normalized appropriately, converges to I( W). Thus, empirical motif densities from observed graphs can serve as estimators for the true motif densities of the underlying graphon. The set of all such motif densities {1(F, W (for some collection of motifs F) is often referred to as the moment vector of the graphon We also introduce the induced motif densities follows
(FFF, (FF,W) = [
W(n.)) II
II (1- (L,, m))) II dmp- (1.))
10.11 (F.))EEF
LEVE
This formulation for induced motif density, ('F,, W), specifically counts instances where the motif F appears in W with an exact structural match. This means it accounts for both the required presence of edges specified in F and the required absence of edges between the motif's vertices that not in F. In contrast, a non-induced (or homomorphism) density t(F, W) only requires the presence of edges from F in W, without any assumption of the value of the graphon associated with pairs of nodes not linked by an edge.
Implicit Neural Representations for Graphon Estimation An INR can effectively model graphon by learning it as a continuous function 34 3. In this setup, the INR, typically a neural network fo [0, 1] - [0, 1], is trained to take pairs of latent node coordinates (7/, n1y) from continuous space as input, where 77: and 77 represent the latent positions associated with entities and
j. Its output is the predicted value of the graphon [o(n; mi)) = W (m), ny)). representing the probability of an edge existing between these two latent positions. The network fo learns this mapping from observed samples, which could be ((Th. ), W (T), 3),)) pairs derived from large graph or target graphon function, for a set of sample indices I. Crucially, because fo learns a continuous function over the entire input coordinate space defined by 77., the resulting graphon representation is inherently resolution- free. This means it can determine the edge probability for any arbitrary pair of latent coordinates (1/, nT),, allowing for the generation analysis of graph structures at any desired level of detail or scale without being tied to a fixed number of nodes or a specific discretization.
Mixup for Data Augmentation The core idea of Mixup 40 is to generate synthetic training examples by taking convex combinations of pairs of existing samples and their corresponding labels. Given two input samples z; and z, with their respective labels yi and yj. new synthetic sample (z. 7) is created as ă = Ar; + (1 - A)æ ÿ = Aÿ; + (1 - A)y where X E [0, 1] is a mixing coefficient. This encourages the model to behave linearly in-between training examples, leading to smoother decision boundaries and improved generalization.
Applying Mixup directly to graph-structured data presents challenges because graphs are not inher- ently Fuclidean objects. To perform Mixup for graphs, one typically first maps the graphs into a suitable Euclidean representation 21 [3]. For example, GraphMAD 21 maps the graphs to a latent
3

---

aa) Observed graphs
(b) Density of Motifs
(c) Moment network training
G
Jo > {so(hh ,n
:-1
INR
( A
True graphon
8 + Moment estimator
mina WMSE
S2 mi
Sampled graphs
Figure 1: Graphon estimation pipeline: observed graphs lead to motif frequency extraction and INR-based recovery.
space and performs nonlinear mixup, while G-Mixup 13 performs mixup in the graphon domain. Once graphs G; and Gj are available as Euclidean representations 2; and 2, respectively, mixed representation ž = λz; + (1 - A)zy can be computed. The subsequent step, which can non-trivial, to generate a new graph G from this mixed representation 2 that can be used for training graph classification model.
The primary problem addressed in the graphon estimation literature, and in this work, is recover the underlying graphon W* given one or more observed graphs.
Problem Formulation.
Problem 1 (Graphon Estimation). Given set of observed graphs G (G1, G2...., Gp), where each Gp has n, vertices and is assumed to be sampled (conditionally fadepenndelly))row an unknown true graphon W i.e. Gp Gn (W"), the goal is estimate W*
In the literature, early methods aimed at solving Problem by means of histogram estimators and stochastic block models (5] [8 6
Other non-parametric approaches, like Universal Singular Value Thresholding (USVT) 7 aimed to recover underlying network structures but often faced computational resolution limitations. More recent scalable techniques include those using INRs.
For instance, IGNR (34) often leverages GW distances 24 37 35 for alignment, while methods like SIGL further advance INR-based estimation.
Our work proposes a novel method for solving Problem by directly learning an INR to match empirical moments (subgraph counts) from the observed graph(s). thereby bypassing latent variables and computationally expensive metric optimizations. Moreover, we leverage our proposed solution to Problem to design MomentMixup, novel mixup strategy for graph data augmentation. Mo- mentMixup performs mixup in the space of empirical moments, offering a novel way to generate augmented graph data informed by the underlying generative structure.
3 Moment Matching Neural Network (MomentNet)
In the following subsections, we introduce our proposed method, MomentNet, for learning the graphon. We also provide the fundamental theorem upon which our model is built.
3.1 Methodology
We explain the two steps in our method to estimate the graphon W given the set of sampled graphs denoted by g = (Gp)p=r A schematic view of our method is presented in Figure 1
Step 1: Computing density of motifs. For each graph in our dataset G. we count the occurrences of specific motifs. The density of identified motif then calculated as the ratio of its observed count to the total number of possible ways that particular motif could appear in graph of the same size.

---

We use the ORCA method [15] to count the number of graphlets in the graph, and then we convert the graphlet count into motif counts. This aggregation needed because our analysis cares only about how often each subgraph pattern appears in total, not about the exact placement of individual nodes within those patterns; see Fig. in [15] for an illustration. We parallelize the use of the ORCA method for computing motif counts across the graphs in our dataset, thereby gaining a significant speed-up in processing time. ORCA can count motifs with up to five nodes, and its method can be extended to handle larger motif's Once these motif-based statistics are calculated from the graphs, we no longer use the graphs themselves for subsequent steps. This approach significantly reduces computational overhead. Mathematically, we consider set F of [F] distinct motif types. For each graph Gp in our dataset, its empirical motif density vector is m(2) R! The overall motif density vector m for the dataset is currently computed as the simple average:
(P)
While Eq. (3) treats each graph equally, a more general approach could involve a weighted average, ma p= (P) (where upp 2 0 and Ep=1 wp 1). Such weights wp could, for example, depend on graph properties like size (np), potentially giving more influence to larger graphs, which might yield more stable density estimates. Our present work employs the simple average, with the exploration of weighted schemes as a potential future refinement.
Step 2: Training the Moment network
The moment network is defined combination of INR with a moment-based loss function. This step consists of three components described as follows:
1. INR: Our methodology employs an INR fe to model the graphon, that receives the latent coordinates (1ı, nΙ} and outputs the estimated graphon value Wom,, nj), as explained in Section 2
2. Moment estimator: With the graphon estimated by the INR function for we can compute the induced motif density for any given motif F. This is achieved by substituting Wa in place of W in ( Since we can not compute the integral directly, we approximate it using Monte Carlo integration techniques. By generating sufficient number of random samples from the distribution induced by the graphon, we can estimate the integral. More precisely,
we sample samples of k latent coordinates ( , , where 17 [[0 1]. Then we estimate (F(F, Wo) as
(!)
8(F, L
Wo(n"" ( ,n (L,EEE
II
II (1 Wo(nh 1 ()))) (1.))E
(4)
The Monte Carlo estimator (F,, Wo) is differentiable with respect to the INR parameters 0. Since the INR fo is neural network parameterized by (and thus differentiable with respect 0) the estimator 8 (F, Wo). which is constructed an average of terms derived from fo outputs at fixed sample points (0)), is consequently also differentiable with respect to 0. This characteristic is vital as it allows the use of gradient-based optimization algorithms to train the INR parameters 0 when this estimator incorporated into loss function. A proof of unbiasedness for this approach, i.e., showing that BIf (F. W ) t'(F, Wo), is provided in Appendix D The vector of estimated moments (e.g., motif densities) derived
from the INR outputs denoted as m (0) [F Wo), (F2, Wo). ... (F), We)
3. WMSE: We use weighted mean squared error loss function train our INR. Given the empirical moment vector m, based on sampled graphs and computed using Eq. 3 and the estimated moments based on the INR m()), the loss function is
[F
T((0)
Σ wi (m: m,))
In our experiments, we adjust the importance of different factors by assigning weights (wx) We calculate these weights as the inverse of how strong each factor (mz) appears in our data
5

---

(w) ). This weighting method balances the impact of each moment, preventing the most frequent ones (larger m,) from having a large effect on the learning process.
The training process described above, optimizing the parameters 0 of the INR So to minimize the weighted mean squared error between empirical and estimated motif densities, yields our final graphon estimate W fo- This estimated graphon inherently scale-free due to the continuous nature of the INR. Furthermore, the entire estimation procedure operates in polynomial time with respect to the number of nodes and motifs considered. A detailed complexity analysis is provided in Appendix B
3.2 Theoretical characterization
We present our main theorem bounding the cut distance between the true graphon W and the graphon We estimated by our proposed INR. This result combines insights from the concentration empirical motif densities in the G., (W) model [5] with the inverse counting lemma relating motif distances to cut distance, and an assumption about the neural network's ability to approximate empirical motif densities. Supporting lemmas and the proof of this theorem are provided in Appendix [
Let GI...., GG be P graphs, each with n vertices, sampled independently from the graphon model G.(W") according to the graphon W The empirical motif density of F based on these samples is
- Σp=1 t(F, Gp). where in slight abuse of notation we denote by t(F, Gp) the motifs densities computed from the motif counts of graph Gp.
We consider an INR fe with parameters 8, whose estimated graphon is denoted by We. The motif densities corresponding this estimated graphon are denoted by fo (F, Wo). The INR is trained to directly output fo F, Wo) values that approximate the empirical densities E(F, W*). Also, let FR denote the set of all non-isomorphic simple graphs with exactly i vertices and let N = [F& be the number of such graphs. As a preliminary step, we formalize the performance requirement we use to characterize our neural network next (see Appendix B.2 for justification).
Assumption 1 (Neural Network Approximation Capability). The parameters I of the INR Wa are obtained such that for fixed approximation error > O, the estimated motif densities (F, Wo) satisfy
(F, (F, We) - T(F,, W*) < car for all F P F
With the previous definitions, and those of Lemma 2 in Appendix B we are in a position to present our main result, stated in Theorem !
Theorem (Cut Distance Bound for INR Estimated Graphons). error achieved by the network as stated in Assumption and 8m = 3 3 be the motif deviation threshold. Assume n. > k(k-1) and
Let ca > 0 be the approximation
831
Pn
88s
k:k - 1) 2)
No 2cxp
<S
4k2
2
2n
where {> is a desired confidence level. Then, with probability at least C, the cut distance between the neural network estimated graphon Wa and the true graphon W* is bounded by 1j =
22C with C = m1x ||llloo [| }. / Von, xe'
dew (W, o, W*) <-
A detailed proof of Theorem I along with necessary definitions and supporting lemmas, can be found in Appendix B This result demonstrates that if the INR can accurately approximate the empirical motif' densities (Assumption[]. D and if enough data (characterized by P and n)) is available to ensure the empirical motif densities are close to the true graphon motifs (Lemma [ then the estimated graphon is likely to be close to the true graphon in cut distance.
Although condition
may seem restrictive, note that (i) it decays exponentially with the number of graphs P and their size n considered, so it can be made arbitrarily small by considering larger datasets and (ii) although increases with (and therefore with N₂), the size of the subgraphs considered is usually small (up to nodes most).

---

4
Moment Mixup
Data augmentation a crucial technique in machine learning, particularly in domains like graph learning, where labeled data can be scarce or expensive to obtain [9]. By synthetically expanding the training dataset with new, plausible examples, data augmentation helps improve model gener- alization, reduce overfitting, and enhance robustness. In the context of graph learning, developing effective augmentation strategies is challenging due to the complex, non-Euclidean nature of graph data, where direct analogies to image text augmentation methods are not always feasible.
In this section, introduce MomentMixup, a novel approach for data augmentation in graph learning. The process begins by generating novel moment profiles through convex combinations of moment vectors, where each vector m& derived from sampled graphs belonging to distinct graph class (c.g., Dew = Σ agm.g with ag 2 0, E. ay = 1). This interpolated moment vector, new then used as the input to MomentNet, which subsequently defines a new graphon distribution, (ye 17)), consistent with these synthesized moments. Finally, new graphs are sampled from Wnew (7). 77)) and integrated into the training set. The pseudocode of MomentMixup provided in Algorithm Din in Appendix G
Proposition 1. A convex combination of graphons is not equivalent to the corresponding convex combination of their vectors of moments, with the exception of the edge density moment.
Proof of Proposition]] D using a counterexample is provided in Appendix F. MomuntMixup is devel- oped based on the key insight from Proposition | This foundational understanding distinguishes MomentMixup and offers it as an alternative to existing methods like G-Mixup [13. The core intuition underpinning MomentMixup that newly generated graph samples should exhibit clear structural proximity to specific class (i.e., similar motif counts), thereby ensuring the augmented data reinforces class-specific structural characteristics. We contend that this particular intuition, that a generated sample is structurally close to target class, may not always be reliably achieved Furthermore, a detailed
through G-Mixup's 's graphon interpolation strategy because of Proposition [ reproducibility analysis was unable to substantiate the original paper's 's claims regarding G-Mixup's superiority over other data augmentation methods [22].
Numerical Experiments
In this section, we evaluate the performance of MomentNet and MomentMixup using various synthetic and real-world datasets widely used in the literature. The primary deep learning components of our experiments were executed on an Nvidia A 100 GPU. Separately, empirical graph moments were computed using the ORCA toolkit [15] 7742 64-Core Processor.
with its execution parallelized across an AMD EPYC
5.1 MomentNet Evaluation
To comprehensively evaluate our proposed MomentNet, we focus on two critical dimensions. First, we examine its effectiveness in the primary task of graphon estimation, determining how accurately it can capture the underlying distribution of graphs. Second, we address the practical applicability of model by testing its scalability. This involves assessing its performance and runtime when applied to both large graphs (high number of nodes) and collections of smaller graphs, which are crucial considerations for real- wolldwrld applications. We use 20000, which is the number of samples to compute the density of moments of MomentNet using Eq. in both experiments.
5.1.1 Graphon Estimation
We use the 13 graphon distributions used in the literature their plot is provided in Appendix G. To build our experimental dataset, we adopt the graph generation approach utilized in 33. From each graphon, we then generate 10 distinct graphs of varying sizes, specifically containing [75. 100.... 275, 300} nodes respectively. We treated the INR architecture as a hyperparameter to account for function complexity, noting that a simple one-layer MLP (17) with 64 neurons sufficed for non-complex graphons, while more complex cases (like Stochastic Block Models) required architectures such as SIREN [29] to accurately represent figh-frequency details. This reflects the known limitations of modeling complex functions with small networks;
The list of graphon distributions with
7

---

GW error
SAS
IGNR
10-3
SIGL
Graphon idx
(a) Performance comparison of MomentNet compared to other graphon estimation approaches.
Nomantiee
100
Nediaal
SGGL
Average Runtime (Seconas)
0.20
80
Lo6s
60
0.10
120
200
300
400
202
100
200
350
Number of Noces
Number of Nodes
(b) Comparison of performance scalability of Moment- Net with SIGL.
(c) Comparison of runtime scalability MomentNet with SIGL.
Figure Overall comparison of MomentNet performance and scalability.
the specific best-performing architecture for each graphon is provided in the supplementary code repository. For comparison, following INR training, we generate the graphon using 1000 uniformly sampled equidistant latent variables over the interval [o, 1]. The GW distance (36] then computed between this estimate and the ground truth graphon. For our method, we implemented the same steps described in section 3] considering the motifs provided Fig. 5 evaluate the performance of our graphon estimation, we benchmark it against several established baseline methods. These include universal singular value thresholding (USVT) (7]. wurting-and-smoote
(SAS) (6) implicit
graph neural representation (IGNR) (34), Graph- Wassersesnr barycenters (GWB) [35), and scalable implicit graphon learning (SIGL). For a consistent comparison, graphons estimated by the IGNR and SIGL baselines sampled at resolution of 1000, mirroring our own evaluation protocol. Furthermore, for SAS and USVT, we zero-pad the adjacency matrices of the observed graphs to this target resolution of 1000 before their respective graphon estimation procedures applied; this input processing strategy is similar to those employed in [3]34].
The results are provided in Fig. 2a Based on the GW loss, our method outperforms the scalable state-of-the-art approach in out 13 graphons. Notably, our approach achieved superior results baseline (SIGI.) struggled more. This difficulty
for graphons 10 and 11, where the state-of-the- might stem from the specific structures of graphons 10 and 11, which can challenge SIGL's reliance on accurately learning latent variables for its GNN-based node ordering and subsequent graphon estimation. Alongside the GW loss comparison, we assessed our graphon estimation via centrality measures, and the findings, detailed in Appendix[] [] affirmed our method's performance.
5.1.2 Scalability Evaluation
For experimental evaluations, we use the graphon W (1k n)} 0.5 + 0.1 cos(TV)) cos(TT))) (Fig- ure T] for generating graph instances across multiple independent realizations for each node size n E 100.... 510). each realization, graphs of size n are generated; MomentNet's target motif counts are averaged from these, while SIGL processes them according to its methodology.

---

Reported performance metrics are averaged over these realizations, allowing methods to leverage comprehensive set of samples.
The estimation error results (Figure 2b) show that MomentNet achieves strong performance, with error decreasing n increases. By leveraging multiple graph instances, MomentNet demonstrates near-optimal performance even on relatively small graphs, attributed to more accurate motif den- sity estimation, aligning with theory. In contrast, SIGL's error, while node-dependent, does not substantially improve from multiple graph instances, offering only slight gains for small graphs, potential explanation SIGL's reliance on accurate
resulting in inferior overall performance. latent variable estimation. The specific graphon W W(n, 17₁) 0.5 + 0.1 cos((T)) (Tn))) (Figure makes this challenging, as its construction ensures edge probabilities near 0.5, leading to high vari- ance (W (1 - W) near maximum). This high variance can obscure latent structure. MomentNet's averaging directly reduces density estimate variance. However, for SIGI., if each of the 10 graphs individually fails to resolve latent positions due to high variance, more such graphs may not overcome this limitation as effectively as methods that directly average structural features.
Regarding runtime (Figure 2c MomentNet's average runtime, despite variance, scales more favorably with increasing nodes compared SIGL, showing a clear advantage for 300. The variance in MomentNer's runtime is due to its early stopping criteria (see Appendix for detailed complexity analysis). Further experimental results are provided in Appendix K
5.1.3 Ablation Study: Choice of Moments
The robustness of MomentNet is demonstrated by its strong performance using a relatively small, fixed set of motifs. We conducted an ablation study to investigate the impact of moment selection, with results for Graphons 2 and 4 (from Table 7) presented in Table I A key finding is that while performance generally improves as more motifs are added (indicated by lower GW distance), this trend is not strictly monotonic. We observed minor performance dips, for instance, after incorporating the seventh and eighth motifs for Graphon 2, a behavior also seen with Graphon 4.
This non-monotonicity suggests that not all motifs contribute equally; some higher-order motifs may introduce statistical noise, as they are often rare and thus typically require more samples for accurate approximation. Critically, these fluctuations are minor within strong overall trend, and adding motifs beyond the first six provides no significant advantage. Our experiments affirm that a practical and powerful graphon estimation can be achieved using a fixed set containing all motifs up to a small node count k. While an adaptive motif selection strategy remains a valuable avenue for future exploration, the current approach is robust and highly effective.
Table 1: Ablation of motif count vs. GW distance (Avg + Std). Motif count indicates the cumulative number of motifs used (up to 15, which is all motifs of size < 5).
Motif Count
1
2
3
7
8
10
11
12
13
14
GW Graphon
.089
.100
.036
_031
.029
.021
.024
.027
.026
.022
.023
.020
.020
.018
.020
Std Graphon 2
.012
.015
.008
.008
.008
.003
.003
.006
.002
.003
.005
.003
.002
_001
.002
GW Graphon
.151
.060
.037
.018
.017
.014
.018
.018
.013
.011
.012
.010
.010
.010
.010
Std Graphon 4
.009 .017
_012
.005
.005
.002
.004
.006
.003
.001
.002
.002
.001
.002
.001
5.2
MomentMixup Evaluation
To evaluate the performance of our MomentMixup framework, we conducted graph classification experiments several real-world datasets: AIDS (27). MMDD-Binary (39], IMDB-Multi [39], and Reddit-Binary [39]. Detailed descriptions of these datasets are provided in Appendix K. To ensure fair comparison with prior work, we adopted the same data splitting methodology as reported in previous literature 3 [3] For data augmentation, we treated amiiz Nusdess Nyruph- and N Nsample as hyperparameters in Algorithm 1 and the best parameters provided in Appendix K. We employ the GIN architecture 38 as the graph classification model.
Table 2 presents the model's accuracy on the test set. The results demonstrate that our method achieves a better performance gain over the standard G-Mixup approach on three datasets. As highlighted in the previous section, method demonstrates distinct advantage datasets composed of smaller

---

graphs, such as AIDS, where it notably ouiperforms techniques like SIGL. While our results on the ReddrttBinary dataset, which features very large graphs and where SIGL performs strongly, were influenced by the experimental choice of using a limited set of nine motifs, this contrast further illuminates key insight: the optimal choice mixup method can highly dependent on graph characteristics, particularly size. Our approach appears particularly well-suited for capturing structural nuances in smaller graphs where fewer motifs can still provide rich representative information.
Table 2: Classification accuracy of G-Mixup, MomentMixup, and baselines different datasets.
Dataset
IMDB-B
IMDB-M
REDD-B
AIDS
#graphs
1000
1500
2000
2000
#classes
2
3
2
2
#avg.nodes
19.77
13.00
429.63
15.69
#avg.edges
96.53
65.94
497.75
16.2
GIN
No Augmentation 71.55=3.53
48 2..8
91.78=1.009
98
G-Mixup w/ USVT
71.94=3.00
10,46=1.49
91.32+1..51
97.8+1.9
G-Mixup SIGL
73.95-2.64
50.70
92.25=1.41
97.3#1
MomentMixup
74.30-2.70
50.95
91.8 = 1.2
98.5++0.6
Conclusions
In this paper, we introduced novel, scalable graphon estimator leveraging INRs via direct moment matching, called MomentNet. This approach bypasses latent variables and costly GW optimizations, offering theoretically grounded, polynomial
solution for estimating graphons from empirical subgraph counts, with provable guarantees on its accuracy. We further proposed MomentMixup, a new data augmentation technique that performs mixup in the moment space, then obtains the estimated graphon using MomentNet, and finally samples new graphs from this graphon. Our empirical results validate the effectiveness of our estimator, demonstrating superior or comparable performance against slate-of-the-al methods in graphon estimation benchmarks, and show that MomentMixup improves graph classification accuracy by generating structurally meaningful augmented data.
Despite its strengths, our method's 's reliance on a pre-selected set of moments for graphon estimation limitation; performance can degrade if these moments are insufficient or noisy. Additionally, modeling single graphon (per class for MomentMixup) may not capture highly heterogeneous graph data. Future work could address these by developing adaptive moment selection techniques and exploring extensions to learn mixtures of graphons. Further enhancements include adapting our moment--bsee approach for attributed or dynamic networks and integrating feature learning into the estimation process, broadening the applicability of our framework.
Acknowledgments
This work was partially supported by the U.S. NSF under award CCF-234048L, the Spanish AEI (AEI/10. 13039/501 10001 1033) grant 1400223-49457BBBB and the Community of Madrid via grants IDEA-CM (TEC-2024/CŌM-S)) and URIC/CAM FI 180 and the ELLIS Madrid Unit.
References
[1] Airoldi, E. M.. Blei, D. M., Fienberg E.,., and Xing, E. P. (2008). Mixed membership stochastic blockmodels. In Journal of Machine Learning Research, volume 9, pages 1981-2014.
[2] Avella-Medina, M., Parise, F., Schaub, M. T., and Segarra, S. (2020). Centrality measures for graphons: Accounting for uncertainty in networks. IEEE Trunsactions Network Science and Engineering, 711):220-537.
[3] Azizpour, A., Zilberstein, N., and Segarra, S. (2025). Scalable implicit graphon learning. The 28th International Conference Artificial Intelligence and Statistics.
10

---

[4] Borgs, C., Chayes, J., and Lovász, L. (2010). Moments of two-variable functions and the uniqueness of graph limits. Geometric and Functional Analysis, 19(6):197-1119.
[5] Borgs, C., Chayes, J., Lovász, L., Sós, V., and Vesztergombi, K. (2008), Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing. Advances Mathematics, 21 (19(6):101-1851)
[6] Chan, S. and Airoldi, E. (2014). A consistent histogram estimator for exchangeable graph models. In Xing, E. P. and Jebara, T., editors, Proceedings of the s1 International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 208-216, Bejing, China. PMLR.
[7] Chatterjee, S. (2015). Matrix estimation by universal singular value thresholding, The Annals of Statistics, 43(1).
[8] Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function. Mathematics of control, signals, and systems, 2(4):303-314.
[9] Ding, K., Xu, Z., Tong. H., and Liu, H. (2022). Data augmentation for deep graph learning: A survey.
[10] Dong, X., Thanou, D., Toni, L., Bronstein, M., and Frossard, P. (2020). Graph signal processing for machine learning: review and new perspectives. IEEE Signal Processing Magazine, 37(6):117-122
[11] Gao, C., Lu, Y., and Zhou, H. H. (2015). Rate-optimal graphon estimation. The Annals of Statistics, 2366):2624-262..
[12] Gao, S. and Caines, P. E. (2020). Graphon control of sarge-scale networks of linear systems. IEEE Transactions on Automatic Control, 65(10)449904444 4105.
[13] Han, X., Jiang, Z., Liu, N., and Hu, X. (2022). G-Mixup: Graph Data Augmentation for Graph Classification. Proceedings of the 39th International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 8450-8465. PMLR.
[14] Hornik, K., Stinchcombe, M., and White, (1989). Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366
[15] Hočevar, T. and Demšar, J. (2014). A combinatorial approach to graphlet counting. Bioinfor- matics, 30(4)5559-565
[16] Leshno, M., Lin, V. Y., Pinkus, A., and Schocken, S. (1993). Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural networks, 6(6):661- 867.
[17] Liu, H.-T. D., Williams, F., Jacobson, A., Fidler, S., and Litany, O. (2022). Learning smooth neural functions via lipschitz regularization. In ACM SIGGRAPH 2022 Conference Proceedings, pages 1-13.
[18] Lovász, L. (2012). Large networks and graph limits, volume 60. American Mathematical Soc.
[19] Lovász, L. and Szegedy, B. (2006). Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933-957.
[20] Navarro, M. and Segarra, S. (2022). Joint network topology inference via shared graphon model. IEEE Transactions on Signal Processing, 70:5549-5563
[21] Navarro, M. and Segarra. S. (2023). Graphmad: Graph mixup for data augmentation using data- driven convex clustering. In ICASSP 2023 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5.
[22] Omeragic, F. and Duranovié, V. (2023). [re] Simathcal (G)ahhcal(G)Smmmineeee (G)S-mixup: Graph data augmentation for graph classification. In ML Reproducibiliity Challenge 2022.

---

[23] Parise, F. and Ozdaglar, A. (2023). Graphon games: A statistical framework for network games and interventions. Econometrica, 91(1):111-225.
[24] Peyré, G., Cuturi, M., and Solomon, J. (2016). Gromov-wasserstein averaging of kernel and distance matrices. In International conference on machine learning, pages 2664-2672. PMLR.
[25] Rey, S., Navarro, M., Tenorio, V. M., Segarra, S., and Marques, A. G. (2025). Redesigning graph filter-based gnns to relax the homophily assumption. In 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5.
[26] Rey, S., Tenorio, M., and Marqués, A. G. (2023), Robust graph filter identification and graph denoising from signal observations. IEEE Transactions on Signal Processing, 71:3651-3666.
[27] Riesen, K. and Bunke, H. (2008). Iam graph database repository for graph based pattern recognition and machine learning. da Vitoria Lobo, N., Kasparis. T., Roli, F., Kwok, J. T., Georgiopoulos, M., Anagnostopoulos, G. C., and Loog, M., editors, Structural, Syntactic, and Statistical Pattern Recognition, pages 287-297, Berlin, Heidelberg. Springer Berlin Heidelberg.
[28] Roddenherry, T. M., Navarro, M., and Segarra, S. (2021). Network topology inference with graphon spectral penalties, In 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5390-5394.
[29] Sitzmann, V. Martel, J. N., Bergman, A. W., Lindell, D. B., and Wetzstein, G. (2020). Implicit neural representations with periodic activation functions. In Proc. NeurIPS.
[30] Su, X., Xue, S., Liu, F., Wu, J., Yang. J., Zhou, C., Hu, W., Paris, C., Nepal, S., Jin, D., Sheng, Q. Z., and Yu, P. S. (2024). A comprehensive survey on community detection with deep learning. IEEE Transactions on Neural Networks and Learning Systems, 3584):4682-4702.
[31] Tenorio, V. M., Isufi, E., Leus, G., and Marques, A. G. (2025). Tracking network dynamics using probabilistic state-space models. In 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5.
[32] Van Handel, R. (2014). Probability in high dimension. Lecture Notes (Princeton University), 2(3):2-3.
[33] Wang, Y., Wang, W., Liang. Y., Cai, Y., and Hooi, B. (2021). Mixup for node and graph classification. In Proceedings of the Web Conference 2021, WWW '21, page 3663-3674, New York, NY, USA. Association for Computing Machinery.
[34] Xia, X., Mishne, G., and Wang, Y. (2023). Implicit graphon neural representation. In Proceed- ings The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 10619-10634. PMLR.
[35] Xu, H., Luo, D.,. Carin, L., and Zha, H. (2021a). Learning graphons via structured gromov wnnser-wasserttenn barycenters. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12)10005-10513
[36] Xu, H., Luo, D., Carin, L., and Zha, H. (2021b). Learning graphons via structured gromov- wasserstein barycenters. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 10505-10513.
[37] Xu, H., Luo, D., Zha, H., and Duke, L. C. (2019a). matching and node embedding. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6932-6941. PMLR.
learning for graph
[38] Xu, K., Hu, W., Leskovee, J., and Jegelka, S. (2019h). How powerful are graph neural networks?
[39] Yanardag, P. and Vishwanathan, S. (2015). Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15, page 1365-1374, New York, NY, USA. Association for Computing Machinery.
[40] Zhang, H., Cisse, M., Dauphin, Y. N., and Lopez-Paz, D. (2018). mixup: Beyond empirical risk minimization. In International Conference on Learning Representations (ICLR).
12

---

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:
Our main claim both written in the abstract and the end of the introduction section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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 can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long 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]
The primary constraints of this study, along with potential future research directions to tackle these, are detailed the conclusion section.
Justification:
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 a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with 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 approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: Proofs, assumptions and lemmas are either explicitly mentioned in the result provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We address this part in the appendix by explaining full details of neural net models and hyperparameters of method.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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 dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, 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 accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to 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 be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
14

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The supplementary material includes code used in the experiments, and we will also upload it to GitHub after the review process if the paper gets accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might 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
/ httpppscccppullccguuudoueo Coaee//ddeeSSbbmmmma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments 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 is permitted.
6. Experimental setting/details
Question: 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?
Answer: [Yes]
Justification: The full details of the experiments written in the appendix.
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 a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All experiments were conducted over multiple trials, and the resulting error metrics reported as their mean and standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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]
Justification: At the beginning of the experiments section, we detail the hardware used to run each part of the model and also present a plot of our method's runtime.
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 as 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 or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httts:://neurpps.cc.. http://pp....ppooocccccccccccdd.
Answer: [Yes]
Justification: We confirm that we have read, understood, and adhered to the applicable code ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the societal impact in Appendix
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that 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 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 mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how 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 or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We don't 't use those data in our experiments.
Guidelines:
The answer NA means that the paper poses no 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 requiring that users adhere to usage guidelines or restrictions to 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 is 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
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Methods adopted from the literature were either re- re-implemented by us based on their published descriptions, with due credit given to the original sources via citation, or, where publicly available code from the original authors was utilized, its use is acknowledged in our GitHub repository.
Guidelines:
The answer NA means that the paper does 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 a 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.
17

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Our code will be published GitHub, with the URL provided in this paper. Additionally, all datasets will be made available on GitHub.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of 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. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or 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?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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 an 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: Our method does involve LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neune http//rripsscccbmmfeeeeeee/////p Cc/Connferences/2225//II. for what should or should be described.
19

---

A Detailed Related Work
Graphon Estimation Graphon estimation aims to recover the underlying generative structure of ob- served networks. Classical approaches include methods based histogram estimators by partitioning nodes according to degree or other structural properties [5] 18 6 and fitting stochastic block models (SBMs) or their variants, which can be viewed as piecewise constant graphon estimators [I [T) Universal singular value thresholding (USVT) (7] offers a non-parametric approach for estimating graphons from single adjacency matrix, particularly effective for low-rank structures. However, many of these methods face challenges in terms of computational cost for large graphs, achieving resolution-free approximation, or may rely on specific structural assumptions (e.g., piecewise constant for SBMs).
More recently, scalable graphon estimation techniques have gained prominence. For example, some works aim at minimizing distances between graph representations but often involve computationally expensive metrics like the GW distance [24 37 35 which can be bottleneck for large networks. The advent of INRs has opened new avenues for continuous, resolution-free graphon estimation. For instance, IGNR (Implicit Graphon Neural Representation) R4 proposed directly model graphons using neural networks, enabling the representation of graphons up to arbitrary resolutions and efficient generation of arbitrary-sized graphs. IGNR also addresses unaligned input graphs of different sizes by incorporating the Gromov-Wasserster distance in its learning framework, often within an auto- encoder setup for graphon learning. Subsequently, SIGL (Scalable Implicit Graphon Learning) [] further advanced INR- baaed graphon estimation by combining INRs with Graph Neural Networks (GNNs). In SIGL, GNNs are utilized improve graph aligmment by determining appropriate node orderings, aiming to enhance scalability and learn a continuous graphon at arbitrary resolutions, with theoretical results supporting the consistency of its estimator. While these INR-based techniques offer significant advantages in terms of resolution-fres representation and handling unaligned data, they still implicitly involve latent variable modeling or rely on GW-like objectives for alignment. Our proposed method builds upon the representational power of INRs but distinguishes itself by directly recovering the graphon via moment matching. This avoids the need for latent variables, complex metric computations like GW, and provides theoretically grounded estimation framework that naturally handles multiple observed graphs by matching aggregated empirical moments.
Data Augmentation for Graph Classification Data augmentation is crucial for improving the generalization of GNNs and other graph learning models, especially when labeled data is scarce. Mixup 440, which creates synthetic examples by linearly interpolating pairs of samples and their labels, has shown remarkable success in various domains. Its adaptation to graph data has been ex- plored through several avenues, addressing challenges such as varying node counts, lack of alignment, and the non-Euclidean nature of graphs. For instance, Wang al. (33 proposed interpolating hidden states of GNNs. Particularly relevant to our work are G-Mixup 13 and GraphMAD Navarro and Segarra (21), which recognize the difficulties of direct graph interpolation and propose to augment graphs for graph classification by operating in the space of graphons. GraphMAD Navarro and Segarra (1] projects graphs into the latent space of graphons and implements nonlinear mixup strategies like convex clustering. G-Mixup [13] first estimates a graphon for each class of graphs from the training data. Then, instead of directly manipulating discrete graph structures, G-Mixup interpolates these estimated graphons of different classes in their continuous, Euclidean representation to obtain mixed graphons. Synthetic graphs for augmentation are subsequently generated by sampling from these mixed graphons. This technique has also been adopted as an augmentation strategy in the evaluation pipelines of some graphon estimation studies for downstream tasks 3
B Proof of Theorem I
B.1 Supporting Lemmas
We rely on the following established and derived results. Lemma I is an original contribution of this work, while Lemma is Theorem 3.7 (b) in Borgs et al. [5] and it is included here for completeness. Lemma 1 (Concentration of Empirical Motifs). Let F be simple graph with k |Vrl vertices. For P2 1 graphs G....., Gp, each sampled independently from G,, (W*), and for any error tolerance 6, > 0, the probability that the empirical motif density i(F, W*) $ Ep= t(F, Gp) deviates from
20

---

the true motif density t(F, w*) ) is bounded as
Pn 41.2
k(k 1)
2
PI](LE, ((F W > e. 2exp
6.
(9)
2n
for Eg kik-1)
1,....; P. The graphs Gp are independent samples from G,, (W"", so the random variables Xp are independent and identically distributed.
Proof. Let X ((F, Gp) po
We leverage concentration properties of t(F,, (n()) in Borgs et al. [5] Lemma 4.4], stating that t(P, G., (W*)) is concentrated around t(F,, W*) with probability
P[] G, (W*)) - (FF, W*) 6] & (oap((n82/(Ak))))
(10)
This implies that the variable Z I(F, (((")) ((F, W*) behaves like Sub-Gaussian random variable [32 Comparing the exponent
from (10) with the sub- Gaussian tail exponent 11:2
n6
8²
202
see that t(F,, G.(())) t(F, W is sub-Gaussian with parameter oz
2
The variables we are averaging are Xp t(F, Gp) with G2 G, (W*). Let Prx = E Ejt(F, (W")) The centered variables fulfill X,p - Ur = (t(F, -p)-t((F)))) - ))). Subtracting a constant (the bias [[, Gp)l - ((F, W*)) from a sub-Gaussian variable preserves its sub-Gaussian property with the same parameter. Thus, Xp Nr. are independent,
zero-mean, and sub-Gaussian with 0² = 02
The average of independent g2-sub-Gaussise Gaussian random variables is (d2/P)-sub-Gaud Gaussian Let
Y Ep pa)) i(F, W*) Un. Then Y is
2k
Lub-Gaussian, The tail bound for Y nP
is
8²
8'P
P 2 8 < 2 exx
= 2 exp
(11)
2
2k nP
4k2
Substituting Y [(F, W*) Pnn get the concentration bound for the empirical mean around the
expected mean:
1_8mPP
PIE(E, - uml 2 8] S 2 exp
(12)
4k22
We are interested in the deviation of E(F, W*) from the true motif density t(F, W"). We use the triangle inequality to relate this deviation the deviation from the mean H4,
[[(F, W*) - (F,, W*] S [ W*) Pa + 1mn - [[F, W*)
(13)
Let B, 14,, (FF, W*) be the bias of the empirical estimate. It is known from the theory of k(k
graph limits (c.g., related to Borgs et al. [5] Lemma 4.3]) that this bias is bounded by B, <
2n
the deviation from the true density is at least c, i.e., [E[ W*) - t(F, W)l 2 C.s then must be
that [8(F, W*) unl 2 C. B, This implication requires C, > B, for the bound to be meaningful.
Thus, for G, > B
PIE(EE W*) - t(F, W*) 2 e,1 < FIE((F, W*) - pml 2 - B.
(14)
Using the inequality with 8 c Bn
(- (E. (c.- (c,-Ba)2 PnP nP
PIT(F,W') (F, W 2 ta] S 2exp
(15)
4k2
Introducing the upper bound for the bias, Bn S 2n
k(k-1)
k(k-1)
n.P
- ca] 2exp
2n
(16)
4k2
Pn
k(k
1)
2
2exp
6,
(17)
412
2n
AA random variable Y is o--sub-Gausiian if 11 < 2220//2 for all À E R, which implies the tail bound
p|||| 2 6] < 2e - 1(20))
21

---

This bound is valid when 6,
k(k-1), 2m
as required by the lemma statement.
Lemma 2 (Motif Proximity Implics Cut Distance Proximity (Borgs et al. [51. Theorem 3.7 (b))). For any integer k 2 1, if the motif distance between two graphons W1 and W2 fulfills [t(F, W1) t(F, W2)l 8M 3 for every simple graph F Fk. then the cut distance between W1 and W2 is upper bounded by
22C
dont (o1, w2) 1 Vlog2k k
(18)
where C' max [[i ||2]lbo3]
B.2 A comment on Assumption |
This assumption is fundamentally supported by the Universal Approximation Theorem (UAT) g 14 [6]. The UAT posits that neural network with sufficient capacity (e.g., an adequate number of neurons in one or more hidden layers and appropriate non-linear activation functions) can approximate arbitrary degree of accuracy
any continuous function
compact domain. In our context, the INR fa models the graphon W : [o, 1J + [o, 1]. The motif density t(F,, W) (as defined in Equation] T is continuous functional of W, meaning small changes in W lead to small changes in t(F, W J. Consequently, if the INR fe can approximate any continuous graphon function, it can learn specific fo such that the motif densities of the graphon estimated by the INR ((F,fo) are arbitrarily close some target values. Given that our estimated motif densities &o We) are Monte Carlo approximations of t(F, fe). they too can approach these target values (the empirical densities {(F. W*) )) as the approximation of the underlying function by fo improves as the number of Monte Carlo samples L increases. The assumption thus relies on the INR's ss capacity to learn suitable graphon function fo and the optimization process's 's ability to find the parameters 0 that make the resulting motif estimates io F, Wo) match the empirical observations [(F, W*).
B.3 Proof of Theorem 1
Proof of Theorem 7 Our goal is to bound the cut distance deu(We, W*) by y, which is achieved
we can show that [FF, We) t(F, W*] < 6b for all simple graphs F with [Vll = k and where the values of both 7) and 8 are provided in Lemma 2
Consider any graph F E Fx- Using the triangle inequality, we can bound the difference between the neural network's 's motif estimate and the true graphon motif
(F, Wo) (F) S fo Wo) F(F,, w (Ā(F, W*) +(F, W
(19)
By Assumption D on the neural network's 's training performance, we guarantee
6M
(F, W.) E(F, W < c, 2
(20)
for every F Fk-
Now we need to bound the second term in the right-hand side of 19 the deviation of the empirical motif density from the true motif density |E(F, W*) - -F,, J. We use Lemma with the sampling
error tolerance set to 6g
5as For this lemma to apply, we require e, >
R(K-1) which is equivalent 2n
2
k(k-1) or A(K-1) This condition is enforced in the theorem statement.
2
2n
dar
For specific graph F E Fi., the probability that the sampling error is large is bounded by Lemma ]
8M 2
Pn
kik
1)
2
[[(FW'' - ((F,
2exx
(21)
4k2
2
2n
Let Prai.F F denote this upper bound for a single graph F FR. However, we require the sampling error [F, W*) t(F, W to be less than éxc for all graphs F E Fs simultaneously. By the union bound, the probability that there exists at least one graph F E FR for which the sampling error is éu or more is at most the sum of the probabilities for each individual graph
2
5m
P/F E F& s.t. ((F, t(F.
1
Σ FEFe
P
(22)
2
22

---

Since MPl= k for all F E Fk. the bound F F is identical for all these graphs. The sum is thus NA Frai.F. F. where we recall that N₂ = |F The condition ( in the theorem precisely set to ensure that this total probability of failure is less than the desired confidence level Ç
Pn
k(k
No. exx
<C
(23)
4k2
2n
Therefore, with probability least < (over the random graph samples Gy). the event that [[(F, (((F,W") < far holds for all F E Fk occurs.
Conditioned on this high-probability event, and using the neural network approximation in Assump- tion 1 have for every F FR
[F,(F, Wo) (FF, W To Wo) - ((F, (((,)) -(E)) dM
6m.
(24)
Since (F, Wo) t(F, W < dM holds for all F E FR, Lemma implies that the cut distance between the estimated graphon We and the true graphon W is less than
(Wo, W) 7
(25)
with probability at least
S, concluding the proof.
C Equation 7 BBound's Applicability in Realistic Regimes
Assuming a small motif error δM is achievable, we now show that the overall probabilistic bound from 7 is non-vacuous for realistic dataset sizes. Table shows the minimum value of Ç (left-hand side of equation (7) for & = 4, a conservatively large motif error of 8as = 0.07 (which is orders of magnitude larger than empirical results) and various numbers of graphs P and nodes
Table 3: Minimum value of in equation for varying values of P and
400
600
800
1000
1200
1400
1600
1800
2000
n
200
11.63
11.45
11.27
11.10
10.93
10.76
10.59
10.43
10.26
250
9.93
9.04
8.22
7.48
6.81
6.19
5.63
5.13
4.66
300
7.87
6.37
5.16
4.18
3.39
2.74
2.22
1.80
1.46
350
5.97
4.22
2.97
2.10
1.48
1.04
0.74
0.52
0.37
400
4.42
2.68
1.62
0.99
0.60
0.36
0.22
0.13
0.08
450
3.21
1.66
0.86
0.44
0.23
0.12
0.06
0.03
0.016
Although values are uninformative as probabilities, the table clearly shows the bound's exponential decay. Crucially, the guarantee becomes meaningful for realistic data regimes. For example, the REDDIT-B dataset has P = 2000 graphs with an average n As 497. Our analysis shows that in a comparable setting (n 450. P 2000), the failure probability Ç is practically useful 0.016. This confirms that the theoretical conditions for our guarantee to hold are met within realistic data regimes.
D Unbiasedness of Monte Carlo Estimator for an INR-Based Graphon Moment Estimator
Let F (V=; EP) be graph, where VF a set of & = |/] vertices and & is the set of edges. Let fo [0, 1| [0, 1] be INR parameterized by 0, which models the probability of an edge existing between two nodes based on their latent variables 77. n5 E [0, 1]. and its estimated graphon denoted by We.
The likelihood of observing the graph structure F given specific set of latent variable assignments = [To and the INR model fo is given by
Po(n; F, (.) = II
Wo(n.
II (1 Wo(n. ny))-
(26)
(KJ)EEP
(KJ)
23

---

The quantity (F, Wo) is defined as this likelihood integrated over all possible configurations of the latent variables in the k-dimensional unit hypereube
(F, Wo) JoNr Po(m: F, Wo)dn.
(27)
where drj ILEV dup-
The L-smplle Monte Carlo estimator for (F, Wo) is given by
1 T
(F, Wo)
"( F, Wo).
(28)
For this estimation, each sample r7 = [ner..... Mox is a vector where each component n) (for
E Vp) is drawn independently from the uniform distribution 4/00, 1].
D.1
Unbiasedness of the Estimator
Theorem 2. The Monte Carlo estimator (F, Wo) an unbiased estimator of to (
(F, Wo).
Proof. To show that the Monte Carlo estimation (F, Wo) an unbiased estimator 1/ (F, Wo). we need to prove that Ei2 (F, We)l = ty (F, Wo). The expectation of the estimator is:
(F (o)F = E
L 1=1
L Σ
(n) F F,W,)) Wo) (by linearity of the expectation).
(29)
Since each sample 17 is drawn independently from the same uniform distribution, therefore its pdf is p(n) = on [0. 11 the expectation (n)); F, Wo)] is the same for all Let this common expectation be E( (m F, Wo)], whose value is
F,
Po(n: Wo)p(n)dn po.11
Pa(n: F, Wo)) - idn
(since p(n) = 1 on [0, 1
po.11
(F, Wo).
according to 27 Substituting this back into 29
1
EI& [o)]
Σ (F,WW)
L
i=1
1 [ (6(F,W))
L
(F, Wo).
Thus, EF = (F, Wo). which shows that the Monte Carlo estimator (F, Wo) is an unbiased estimator of (F, Wo). This means that, average, the estimator will yield the true value of the integral defined by fo and the graph structure
E Time Complexity of MOMENTNET
Stage 1: parallel detif-density extraction. For each graph Gp = (Vp, Ep) let ny D2pl. 6p = Epl and dp = max,ev, deg(v) be the number of nodes, number of edges, and maximum degree of the graph Gp. ORCA [15] counts all 2 244nnode graphlets in
ToRCA(G,) Oepdp + n.d.).

---

Because every graph can be processed independently, we dispatch the P graphs to M workers (M < P). Hence the wall-clock preprocessing time
o( M max(cpdp + ng
Stage =
With one worker per graph (M P) this shrinks to the single-graph cost that dominates (max,).
Stage 2: training the Moment network. Define:
L: number of Monte-Catt samples per epoch;
Ng: number of training epochs;
CINR: cost of one forward/back ppopp prop through the INR for single edge probability;
0 total number of trainable parameters.
Each motif instance F of size [V S invokes the INR most six times, a constant. One epoch therefore costs
T epoch O( CINR + 10))
T singe = ONN. (L CNNR + 181))
Overall wall-clock complexity.
Momenttet O1 M
max(epdp + nod Ne CINR 101)
D
Comparison with SIGL in Sparse vs. Dense Regimes
SIGL 3 requires message- -aagggggpsiinggggg GNN training, histogram building and INR fitting: with Ne epochs its wall-clock cost TSIGI. O(PN.n)) where nr maxp np-
Sparse regime (dmax ((1) + Ep = (np)))
-OMENTTET: T (
P M7
nT No (L CINR + 101)):
-SIGL: = O(PNN.
Here MomentNet grows linearly in (plus the network-training term), whereas SIGL is quadratic. In practice we repeatedly observe MomentNet to be faster when graphs have Cp =(pp) even for very large np.
Dense regime (Erdōs-Rényi Rényi with Peonn 0.5 implies dmax = and ep = (nn.)))
MOMENTNET: T ( P. ni N. (L 101))
SIGL: T OPPN.
Asymptotically, SIGL's nī term is smaller than MomentNet's nf. Yet empirical runs on dense ER graphs with Poonn = 0.5 still show MomentNet to be faster once (i) Stage is fully parallelised and (ii) the constants behind GNN message passing and histogramming dominate SIGL's quadratic term. Thus, the theoretical advantage of SIGL in dense graphs does not necessarily translate into shorter wall-clock times. Furthermore, MomentNet utilizes a two-stage process. The initial stage involves computing motif counts from the input graphs. Following this, the graphs are discarded. The second stage, which our experiments show to be the dominant phase of our method, then trains an INR using vector of average moments derived from these counts. This design provides a significant reason for our method's 's improved speed, particularly in dense scenarios. By isolating the computationally expensive motif counting to a preliminary step, this cost is bypassed during the subsequent, dominant INR learning phase.
With graph-level parallelism, MOMENTNET is provably linear in the number of edges for sparse networks and remains competitive on dense networks because its constant factors are smaller and its training cost is independent of the graph size.
25

---

E.1 Justification for Practical Scalability Over SIGL
The theoretical complexity analysis highlights that in the dense regime, MOMENTNET's Stage cost P is bounded by O M n which is asymptotically worse than SIGL's OP).. However, as demonstrated in our empirical results (Figure Fe), MOMENT is practically faster on large, dense graphs. This is due to two critical factors:
Loose Theoretical Bound and Small Empirical Constant for ORCA: The worst-case (n2)) bound for ORCA's 4-node motif counting is known to be non-tight. We conducted an empirical analysis by measuring the wall-clock execution time for counting 4-node graphlets sequence of dense graphs with node counts ranging from 30 to 400.
Empirical Analysis of ORCA Runtime We modeled the relationship between runtime T[n) and node count n using a linear regression log- log-transformed data, T(n) s c-n'". Our results determined the practical growth rate to be nearly cubic, with an exponent of (IT2 x 0.97). Crucially, the fitted constant factor was extremely small, c R 2.97 10- This empirical finding confirms that the algorithm is highly efficient on dense graphs, ensuring that MOMENTNET'S theoretical worst-case cost practically masked by SIGL's larger constant factors and overheads until ny becomes very large.
2. Strategic Subsampling Capability: Our method's performance relies the moment vector m, which is robustly estimated by averaging moments from multiple, smaller graphs (P' graphs of size ny)). MOMENTNET's theoretical guarantee (Theorem [ and Figure 2b allows us to strategically subsample a single large input graph into a collection of smaller graphs, effectively reducing the dominant max, np in Stage 1. This capability lets trade off np for P to minimize runtime while preserving near near-optimal performance, a flexibility SIGL lacks. SIGL must process the full-size graph to properly learn latent representations, directly locking its runtime to the high cost of a single, large ny.
Therefore, MOMENTNET's practical speed advantage stems from combination of a lower-than- worst-case empirical complexity in Stage and a flexible sampling strategy that SIGL cannot utilize.
E.2 Subsampling Effect on Scalability
The scalability evaluation in Figure 2 demonstrates the conditions under which MomentNet achieves computational advantage over SIGL. A key insight from our analysis is that SIGL's performance deteriorates significantly on smaller graphs due its dependence on stable latent variable estimation. This limitation benefits our approach: by subsampling a very large graph into a smaller, more managcable collection of subgraphs, we can maintain near-optimal estimation quality while drastically reducing the computational cost. In contrast, running SIGL directly on these smaller subgraphs is ineffective, as its accuracy drops off steeply.
To further validate the benefit of subsampling in the large-graph regime, we constructed dataset consisting of ten large graphs, each containing 2,000 nodes, sampled from the dense- gaase--rrphhha graphon class used in our scalability analysis (Section 5.1.2). We then extracted ten 50-node subgraphs from each 2,000-node graph and used these smaller subgraphs as inputs for both methods. The results, summarized in Table[] confirm that MomentNet outperforms SIGL in both accuracy (lower GW Loss) and runtime under this efficient subsampling strategy. Crucially, while SIGL.'s 's runtime increases sharply with full graph size, our method maintains comparable performance even when utilizing these smaller subgraphs.
Table 4: Performance comparison large graphs (2,000 nodes) using a subsampling strategy (10
extracted 50-node subgraphs per large graph).
Method
Training Runtime (s)
GW Loss
Motif Counting Runtime (s)
MomentNet
54.83 + 18.69
0.0548 + 0.0016
1.59 + 0.24
SIGL
207.89 + 18.4
0.1085 + 0.0156
26

---

Proof of Proposition 1
Let W1, W2: [0, 10, - [0, 1] be two graphons and fix (0, 1). Denote their convex combination
by
Wa a aaWi (1 - W2-
Edge density (a linear functional), EF. {(1,))) 2)}, the induced density
For the single-edge motif F, on vertices VF. = {1, 2] and
f ( 72) dm duz = ([((n,7))
(Fee W)
1o.11
Because the integrand is linear in W, immediately have
(F,,,, w.) a l' (Fe, Wi) + (P., W2).
so the edge density behaves affinely under convex combinations.
The V-shape motif. Let F be the V-shape (three-vertex path) vertex set Vp (1, and edge set EE = {(1,2) (1, Its induced density is
I 1o11
()F,W)
W(n, W ((n.7a) W (12, na)] dmdd22da..
(30)
Plugging Wa into (30
f(F, = E (aW1 (1 (1-01)1111) a)W2) (aWi (1 a)) 13 (1 aW1 a))
23
3 (WW)) (Wi)))(((()))))))) (1 a) (e((()))2 (W2)23)
mixed terms,
(31)
where, to simplify notation, we used (-)y to denote that the graphon inside the parenthesis is evaluated on (1): 175)) and "mixed terms" contain products which at least one factor comes from W, and another from W,. Because these mixed terms generally do not cancel, the right-hand side of 31
does not reduce to the affine combination
t' (F, Wi) + (1-)))()))
(32)
except in degenerate cases (e.g. W1 W₂ a 10,1)).
Concrete counter-example. Take constant graphons Wi(n,, 7T) = Pı and W2(Th, n1)) P2 with and pa being constants satisfying 0 < P1 P2 < 1. Then (T 715) = apı + (1 a) and
(FF,W,) = 21 pr),
f(F, W.) =p:(1 (p)-
for E 21. However,
p2 - p.) # a1 (1) (1 p1 - p2)
whenever Pı # P2 and a E (0, 1), confirming that the V-shape moment is not affine in W.
Conclusion. Edge moments are linear in the graphon, but higher-orde induced moments involve non-linear (polynomial) combinations of W. Consequently, a convex combination of graphons preserves edge moments but fails to preserve the remaining components of the motif-moment vector.
G Methods Details
G.1
Latent Variable Invariance of MomentNet
The graphon model and our proposed model to learn it exhibit invariance to the specific ordering or labeling of latent variables. This means that the estimated graphon is unchanged under measure
27

---

preserving transformations [S]. In other words, if the underlying structure of a graphon is rearranged or relabeled, MomentNet can still accurately capture the essential underlying comnectivity patterns, To illustrate this crucial property, we conduct experiment using SBM graphon, more precisely the one indexed by 12 in Table 7 For this experiment, we utilize the same dataset that was generated for the performance comparison of MomentNet discussed in Section 5 The learned graphons for three different realizations of this experiment are presented in Figure
is evident that all three estimated graphons closely resemble the ground truth graphon, which is depicted in Figure 4 Also, the three estimated graphons reflect the same underlying structure, and all of them share a similar GW loss, which is loss function invariant to measure preserving transformations. This essentially means that, no matter which of the three depicted graphons we sample graphs from, the underlying structure of all these graphs will be the same. This outcome strongly verifies that MomentNet's primary mechanism involves matching the moments of the graph, without caring about the ordering of the latent variables. Consequently, and in contrast other methodologies, its estimated graphon accurately reflects the ground truth structure, allowing for differences only up to permutation the latent variable locations.
(a) Estimated SBM graphon (Sample 1).
(b) Estimated SBM graphon (Sample 2).
Estimated SBM graphon (Sample 3).
Figure 3: Three samples of estimated graphons derived from SBM.
28

---

G.2 MomentNet Generalization
To test the generalization capabilities MomentNet beyond standard metrics like the GW loss and centrality measures, conducted additional experiment focusing on moment extrapolation. Following the experimental setup described in the paper, we trained model exclusively on the nine motifs corresponding to 2- to 4-node subgraphs (Fo to Fg). We then evaluated its ability accurately predict the densities of a different, unobserved set of subgraphs: the 5-node motif's (motif indices 10 through 30 in the ORCA paper [15]. The relative error for each extrapolated moment is presented in S The highly accurate estimations, with a median relative error of less than 2%, demonstrate that MomentNet successfully learned the true underlying continuous data distribution (the graphon) from the low-order moments, allowing it to accurately extrapolate high-order structural properties.
Table 5: Extrapolation Error: Relative enror (%) of MomentNet's estimated moments for unobserved 5-node motifs (Indices 10-30), after training only on to 4-node motifs (Indices 1 1-9).
Mosif
Rel. Eer. (%)
Motif
Rel. Erc. (9)
Motif
Rel. Err. (%)
Motif
Rel. Err. (5)
Motif
Rel. Eir. (%)
Motif Rel. Brr. (%)
10
2,224
14
0.201
18
0.154
22
1.102
26
3,087
30
11,086
11 1.536
15
1.4331
19
0.371
23
2.463
27
1.753
12
1.744
2,062
21
1,502
4,010
G.3 Monte Carlo Sampling Variance
Based on the relatively high quality of the results achieved by MomentNet, we hypothesize that stable convergence during training contingent upon sufficiently low variance the Monte Carlo estimation of the motif densities (as described in the moment estimator paragraph of Section 3.1 Equation 4 To investigate this hypothesis directly, we designed an experiment to measure the gradient variance as a function of the number of Monte Carlo samples, L. For this test, the parameters (0) of the INR model were held constant while we estimated the gradient's standard deviation over 1,000 runs for varying numbers of samples, T.. The results, summarized in Table 6 show clear inverse relationship: the standard deviation consistently decays as L increases. This finding supports hypothesis and underscores the importance of using sufficient number of samples, L, to ensure stable and efficient optimization.
Table 6: Gradient Stability vs. Monte Carlo Samples (L). The standard deviation of the gradient decreases consistently with the number of Monte Carlo samples, supporting the need for sufficiently large L for stable optimization.
Monte Carlo Samples (L)
Mean Gradient
Std Dev Gradient
100
0.01
0.004484
500
0.013107
0.002033
1000
0,013030
0.001387
5000
0.013019
0.000647
10000
0.013052
0.000439
20000
0.013009
0.000325
50000
0.013013
0.000193
100000
0.013019
0.000134
29

---

G.4
MomentMixup Pseudocode
Algorithm 1 MomentMixup Augmentation
Input:
Omix- float, mixing coefficient (0 Omix Σ 1).
Gi, Gy: list of graphs, graph datasets for classes and j.
Vi, Dy: integer, label for classes and
N sample: integer, number of graphs to sample from each class dataset to compute average moments.
N nodes integer, number of nodes for each new graph.
grapts integer, number of augmented graphs to generate.
Output: Gmug list of graphs and labels, newly generated augmented graphs.
Compute average moment vector for class
2: S + Randomly select N ample graphs from G;
3: m: Nauuke EGEs, ComputeGrrahMommnns(C Compute average moment vector for class
4:
5: S < Randomly select Nample graphs from G
6: m, -- Nample EGes; ComputeGraphMomentt//
7: marget Ommix m, (1 O m
Compute target mixed moments
8: Sharget E
8/s + (1 amix) 3/
Compute the label for the new samples
9: W aangg MomentNet (marrg)))
Trains MomentNet for Marget
10: 9mng +[
> Initialize list for augmented samples
for < to N Ngraphs do
12: Gnew t- SampleGraph W aug. Noodes)
> Sample new graph
Add (Gnews Marrget) to Goug
14: end for
return Gaug
H List of Graphons
Table 7: Table of Graphons
W W(r, v)
e--(a" (2 ())
2
3
1 (x² +y² + v v
[x + y)
5
(1 ( 222 +20+)))))--
(1 el 1--maa(22)) -mn_=()=))(
el - ma 0.76
el (
log(1 max y))
10
V
11
1- x
yl
12
0.8I, @ [o.
13
0.8(1
I2)
2 oz
The graphons also visualized in Figure
30

---

1.0
10
1.3
1.0
0.5
0.0
0.5
0.5
0.5
0.5
0.11
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.0
0.5
1.0
19]
(6)
(7)
18]
1.0
1.0
1.0
1.0
0.0
0.0
(112
0.5
0.0
0.5
10 Figure 5: Motifs up to four nodes.
(13)
Figure 4: Representation of the graphons defined in Table
I Selected Motifs
P%
Fs
Centrality Measures
real-world graph statistical analysis, centrality measures are of significant interest to researchers.
Building upon the work of Avella-Medina et al. (2) who demonstrated the computability of these measures on graphons, we use several centrality metrics to further evaluate the quality of the estimated graphons. Specifically, employ:
31

---

Degree Centrality: This measure quantifies the number of direct connections a node possesses.
High Value: Indicates a node with many direct connections, often acting as local hub with numerous immediate interactions. Such node is highly active in its local neighborhood.
Low Value: Suggests a node with few direct connections, implying less immediate activity or influence within its local vicinity.
Eigenvector Centrality: This identifies influential nodes by considering that connections to other highly-connected (and thus influential) nodes contribute more significantly to node's 's score. It measures how well-connected node is other well-connected nodes.
High Value: A node with high eigenvector centrality is connected to other nodes that themselves influential. This node is likely key player within an influential cluster or a leader among leaders.
Low Value: A node with low eigenvector centrality is typically connected to less influential nodes or has relatively few connections overall. Its influence is not strongly amplified by the influence of its neighbors.
This measure considers all paths in the graph, assigning exponentially more weight to shorter paths while still accounting for longer ones. It uses an attenuation factor a, which determines the weight given to longer paths: smaller values of a emphasize shorter paths, while larger values give more importance to longer paths, up theoretical limit ensure convergence.
Katz Centrality:
Indicates node that is reachable by many other nodes through numerous paths, with shorter paths contributing more. This node is generally well-connected throughout the network, both directly and indirectly, and can efficiently disseminate or receive information.
High Value:
Low Value: Suggests a node that is not easily reachable by many other nodes or is primarily connected via very long paths. Its overall influence accessibility within the network is limited.
PageRank Centrality: Originally developed for web pages, PageRank assesses a node's importance based on the number and quality of its incoming links. A link from an important node carries more weight than link from less important one. It uses damping factor B, representing the probability that a random walker will follow a link to an adjacent node, while (1 (9) is the probability they will jump to random node in the graph, ensuring that all nodes receive some rank and preventing rank-sinking in disconnected components.
High Value: A node with high PageRank centrality receives many "votes" (incoming connections) from other important nodes. This indicates that significant entities within the network consider this node to be important or authoritative.
LLww Value: A node with low PageRank centrality receives few incoming connections or is primarily linked by less important nodes. is not widely recognized as important by other influential nodes in the network.
The mathematical formulations for these graphon- based centrality measures adopted directly from Avella-Medina et al. [2), corresponding to equations (7), (8), (9), and (10) in their paper, respectively. For detailed analysis, we focus graphons 1 and 2, as specified in Table 7 We compute both analytical and sample-based centrality measures, establishing these as baselines for comparison with our results. The analytical computations directly apply the aforementioned formulas from Avella-Medina et al. [2]. For the sample-based approach, we generate discrete graph instances by drawing samples from the ground truth graphon and subsequently compute the centrality measures within this discrete domain. Further details regarding each graphon are presented in the subsequent subsections.
J.1 Graphon 1: The (zy) Model
The analytical centrality measures formulas for this graphon are as follows:
Degree Centrality:
(d(x) =
2
Eigenvector Centrality:
(*(2) V3x
32

---

Katz Centrality:
(x) = (6-2a) + 3ox
PageRank Centrality:
(x) (1 3) + 28x
These measures are for the given latent variable æ E [0, 1], after computing its centrality vector, we normalize it before comparison with discrete graph centralities (2). Since the ordering for these experiments is important, we create a new dataset 20 graphs with 100 nodes each, preserving the latent variables for all the nodes. The experiment results are illustrated in Figure Our results show that centrality measures from the MomentNet predicted graphon (blue lines in the figure) are close to the analytical computations (ground truth, black dashed lines). Furthermore, these graphon- basedd centralities by MomentNet also provide a good approximation for centrality measures computed over discrete graph samples (red dots).
Degane
Egenrector
Missaubiot
C20
Mecaa Dii Egearete
Eingen legen
Gophilggeent Asilyx Eigeneace
Analytii Degan
C12
C350
0.00
0.77
0.90
0.
0.00
09
04
06
10
82
03
04
10
Katr Camtrality to (05500)
Pagelann Centrality (i (V))
1.550
Menecfle Fap
7 140
1.56
1.44
Catteda Tide
3400
0994
Laton Naraat
Leber Vortale
Figure 6: Centrality measures: MomentNet vs. analytic computation for the xy graphon.
J.2 Graphon 2: The (e(-(a"++ya7)) Model
To test the generalizability and consistent performance of our method across varying complexities, we replicated the experiment on more complex graphon. The analytical centrality measures formulas for this graphon are as follows:
Degree Centrality:
(²(x) 0
Eigenvector Centrality:
(²(x) e -=7
VO.473
Katz Centrality:
C (x) 1+ 0.7492 e 0.7
1-0.473
33

---

PageRank Centrality:
O% B)
= ()
3) + 0.7492
B
~ 07
The experiment results are illustrated in Figure 7 Similar the previous experiment, after computing the centrality measures on the graphon and analytically, we normalize them to compare them with the discrete graph measurement. As the plots show, similar to the previous graphon, our estimation is very close to the ground truth results obtained by analytical calculation.
Degnee Centriitty
Ripenoector Centrsity
Coyph Depare Legge
Greti Andel Hggerechr
0116
Cost- May Midee
02
00
Latend
Latez
Kate Centrality la (8500)
PageBank Contralty (6=
0.300
Monoertio Kirz
Manena Ragk
Gogin Pagttink
03300
0.35
0:34
Contealyy Vilee
00000
0:12
00300
0098
0.06
0.99
Lavee Vasaae
Laven Variaee
Figure 7: Centrality measures: MomentNet vs. analytic computation for the el (00776"77 graphon.
K Extra Scalability Evaluations
We conducted an additional experiment to evaluate the scalability of SIGL and MomentNet. For this assessment, rather than focusing on SIGL's known weaknesses in latent variable estimation, we selected graphon number from Table model that both methods accurately estimate. We generate 10 graphs for each node size E {10. . 810}.
Figure 8 iillustrates the scalability of MomentNet and SIGL in terms of both performance, measured by GW loss, and average runtime, as a function of the number of nodes. Subfigure (a) of Figure S reveals that MomentNet (blue line) maintains a consistently low GW loss across the tested range of node sizes, indicating stable performance. In contrast, SIGL's (red line) GW loss starts notably higher for smaller networks but decreases substantially as the number of nodes increases, eventually matching or even slightly outperforming MomentNet's 's loss for larger networks.
However, subfigure (b) of Figure 8 highlights a significant difference in computational efficiency: MomentNet's 's average runtime exhibits only a modest and gradual increase with the number of nodes. Conversely, SIGL's runtime escalates sharply, demonstrating significantly poorer scalability.
Consequently, while SIGL might offer a marginal advantage in GW Loss for very large graphs, MomentNet's 's vastly superior runtime scalability makes it more practical and favorable approach, partieularly for applications involving large-scale networks where computational resources and time are critical factors.
34

---

Metoct
0.70
MomaTtlee
Average Buntimn (Seconz2)
250
1:0
0.10
1:0
0.00
-00
200
300
400
520
600
700
600
100
200
100
400
500
6cn
700
TBC
Number of Noces
Number of Nodes
(a) Comparison of performance scalability of Moment- Net with SIGL.
Comparison of runtime scalability of MomentNet with SIGL.
Figure 8: Scalability Comparison of MomentNet and SIGL
L MomentMixup Evaluation Details
Our experimental evaluation is conducted four diverse benchmark datasets widely used in graph classification research. Table provides a detailed overview of these datasets, outlining their specific characteristics and the nature of their respective classification tasks.
Table 8: Description of the benchmark datasets used for evaluation. Each dataset represents a different type of graph structure and classification task.
Dataset
Description
Classification Task
Citation
IMDB-B
Movie collaboration graphs; nodes represent ac- tors/actresses, and an edge connects two ac- tors/actresses if they appear in the same movie.
Binary genre classi- fication.
39
IMDB-M
A multi-class version of IMDB-B, representing movie collaborations with similar graph construc- tion.
Multi-class classification.
genre
39
REDD-B
Social network graphs from Reddit; nodes repre- sent users, and an edge indicates interaction (e.g., one user commented on another's post).
Binary community (subreddit) classifi- cation.
39
AIDS
Bioinformatics graphs representing molecules; nodes atoms, and edges covalent bonds between them.
Binary classifi- cation based anti-HIV activity (active vs. inactive).
M
Social impacts
The methods presented for graphon estimation via moment-matching INRs and data augmentation through MomentMixup, while offering powerful tools for understanding network structures and enhancing graph-based machine learning, are not without potential societal risks if deployed without careful consideration. For instance, in social network analysis, if the empirical moments used for graphon estimation are derived from graphs reflecting existing societal biases (c.g., in representation or connectivity), both the estimated graphons and synthetic graphs generated via MomentMixup could inadvertently perpetuate or even amplify these biases. This could lead inequitable outcomes when models trained on such data are used for applications like resource allocation, recommendation systems, or public policy modeling. Similarly, in critical domains such as epidemiology or finan- cial systems, inaccuracies in graphon estimation or the generation of unrepresentative augmented data could lead flawed predictions, potentially resulting in misguided interventions or financial instability. While graphon estimation offers level of abstraction, careful attention must also be paid to ensure that the process does not inadvertently leak sensitive information from the original graph data, especially when dealing with networks containing personal confidential details. Therefore,
35

---

it is crucial for practitioners to be acutely aware of these potential pitfalls. This includes critically examining input data and chosen moments for biases, rigorously validating the fidelity and repre- sentativeness of estimated graphons and generated graphs, and thoughtfully considering the ethical implications of their application, particularly in domains with direct and significant societal impact.
36


Reviews:
[{"review_id": "gqmBMjFZeS", "reviewer": "Reviewer_ogzT", "summary": "This paper proposes MomentNet, a novel, scalable graphon estimation method using moment matching and implicit neural representations (INRs). Instead of inferring latent positions or minimizing costly distances like Gromov-Wasserstein (GW), it uses motif count statistics (graphon moments) as supervisory signal. The key idea is to optimize an INR to match empirical subgraph densities from observed graphs. The authors further propose MomentMixup, a mixup-based data augmentation strategy in moment space, which enables structural interpolation of graphs via synthetic moment vectors decoded through MomentNet.\n\nThe paper offers a new path in graphon estimation by combining solid theoretical foundations (e.g., cut-distance guarantees via inverse counting lemma) with practical scalability. It demonstrates strong empirical results on synthetic graphons and several real-world graph classification datasets.", "questions": "1. *On Moment Selection*: Can you elaborate on how robust your method is to the choice or number of motifs? Would adaptive motif selection (e.g., using entropy or redundancy) improve performance?\n\n2. *On MomentMixup Semantics*: When combining moment vectors from two classes, how is the label assigned to the generated graph? Is it a soft label, or do you assign based on dominant α weight?\n\n3. *On INR Generalization*: Have you evaluated whether the trained MomentNet generalizes well to moment vectors outside the training distribution (e.g., interpolations or extrapolations)? How stable is the mapping from moments to graphons?\n\n4. *On Heterogeneous Graph Classes*: How would your method adapt to datasets with significant intra-class structural variability? Could a mixture-of-graphons model address this?\n\n5. *On Motif Sampling Efficiency*: The runtime and sampling complexity of computing motif densities (especially with ORCA) might still be high. Could you consider approximating them via graphlet sampling or neural surrogates?", "limitations": "The authors acknowledge key limitations in Section 6, including:\n\n  - Sensitivity to the choice of moments.\n\n  - Assumption of a single graphon per class in MomentMixup.\n\n  - Lack of adaptation to dynamic or attributed graphs.\n\nThese are valid and well-stated. I would also add:\n\n  - Lack of interpretability in the learned INR.\n\n  - Training instability when motif estimates are noisy (especially for small motifs or sparse graphs).", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n1. *Novelty*: The idea of matching motif densities via an INR is new and elegant. It sidesteps latent position estimation—a common bottleneck in graphon estimation.\n\n2. *Scalability*: The method is inherently scalable. It reduces both memory and computational overhead by discarding raw graphs after extracting moments and works in polynomial time.\n\n3. *Theory-backed*: The paper offers a clear theorem bounding the cut distance between the estimated and true graphon under realistic assumptions (with number of motifs, sample size, etc.).\n\n4. *Empirical Performance*: Strong results on synthetic graphon estimation (13 benchmark graphons) and real-world graph classification via MomentMixup. It outperforms or matches SOTA in most cases.\n\n5. *MomentMixup is principled*: The paper identifies a limitation in G-Mixup (moment vectors of interpolated graphons ≠ interpolated moment vectors) and proposes a better method grounded in structure.\n\n6. *Clear Writing and Presentation*: The exposition is mostly accessible and well-structured for a technical audience. Figure 2 and the breakdown of training steps help clarify the process.\n\n\n**Weaknesses**:\n1. *Choice of Moments is Fixed*: As admitted by the authors, the set of motifs is predefined (up to 5-node motifs via ORCA). There’s no adaptive selection or theoretical guidance on which motifs best characterize a given graphon. Poor motif choice can hurt performance.\n\n2. *Single-Graphon Assumption for Each Class*: MomentMixup assumes each class corresponds to a single graphon. This is limiting for datasets with high intra-class variation (e.g., Reddit-Binary), where performance lags.\n\n3. *No Comparison with Recent Diffusion-Based or Equivariant Methods*: SIGL is a strong baseline, but there are recent graph representation models (e.g., equivariant GNNs, diffusion-based models) that could offer complementary perspectives.\n\n4. *No Ablation on INR Architecture*: The INR used is a shallow 1-layer MLP. It's unclear whether deeper architectures improve estimation quality or overfit due to noise in empirical moments. An ablation would be informative.\n\n5. *MomentMixup’s Label Assignment*: The paper does not detail how the class labels for generated graphs via MomentMixup are assigned. Are they soft labels or nearest neighbor class labels? This has implications for supervised training.", "was_revised": true, "final_justification": "I was initially concerned about the practicality of the proposed approach. However, the authors have addressed these concerns convincingly:\n\n*Motif Count*: The use of five motifs in the experiments is justified by an ablation study, which demonstrates that incorporating more than six motifs does not yield further performance improvements.\n\n*Generalization*: The model’s ability to generalize has been validated by training on 9 motifs and extrapolating to 20 unseen motifs, with strong performance—relative errors are consistently low (typically <4%).\n\n*Heterogeneous Graph Classes*: For these cases, the authors propose partitioning graphs into structurally homogeneous clusters using moment vectors. Their claim—that graphs from the same generative mode have similar moments and are easily separable—provides a sound theoretical basis. While experimental validation is pending, the authors have committed to conducting these tests.\n\nGiven these clarifications and the strength of the ablation and extrapolation results, I believe the paper’s contributions are more robust than I initially assessed and I am inclined to raise my score.", "rebuttal": "Thank you for your insightful comments and questions. We address those in the following subsections.\n\n**1. Choice of moments (Ablation Study):** \nOur method's robustness is demonstrated by its strong performance using a relatively small, fixed set of motifs. To investigate this further, we conducted an ablation study, with results for graphons 2 and 4 from Table 2 presented in the table below. These results highlight a key finding: while performance generally improves as more motifs are added, this trend is not strictly monotonic. For instance, we observed a minor dip in performance after incorporating the eighth motif before the trend resumed. A similar non-monotonic trend was also observed for Graphon 4.\nThis behavior suggests that not all motifs contribute equally to the estimation; some are more informative, while others might introduce statistical noise, particularly higher-order motifs that require more samples for accurate approximation. An adaptive motif selection strategy could potentially optimize performance by identifying the most informative subgraphs for a given graphon, and we agree this is a valuable idea to explore.\nHowever, it is crucial to emphasize that these are minor fluctuations within a strong overall trend, and that adding motifs further than 6 does not provide a large advantage. The robustness of our current approach is confirmed by the fact that using a comprehensive set of motifs up to size $k$ consistently yields a superior estimation compared to using significantly fewer motifs. As shown in our tests on Graphon 2 and 4, even when performance dips slightly with the addition of a specific motif, the overall result remains highly effective. While statistical theory suggests all moments are needed to uniquely identify a distribution, our experiments affirm that a practical and powerful estimation can be achieved using a fixed set containing all motifs up to a small node count $k$ (note that 9 motifs are achieved with just $k=4$).\n\n\n\n| Motif | Avg GW (idx 2) | Std GW (idx 2) | Avg GW (idx 4) | Std GW (idx 4) |\n| :---: | :---: | :---: | :---: | :---: |\n| 1 | 0.089 | 0.012 | 0.151 | 0.009 |\n| 2 | 0.100 | 0.015 | 0.060 | 0.017 |\n| 3 | 0.036 | 0.008 | 0.037 | 0.012 |\n| 4 | 0.031 | 0.008 | 0.018 | 0.005 |\n| 5 | 0.029 | 0.008 | 0.017 | 0.005 |\n| 6 | 0.021 | 0.003 | 0.014 | 0.002 |\n| 7 | 0.024 | 0.003 | 0.018 | 0.004 |\n| 8 | 0.027 | 0.006 | 0.018 | 0.006 |\n| 9 | 0.026 | 0.002 | 0.013 | 0.003 |\n| 10 | 0.022 | 0.003 | 0.011 | 0.001 |\n| 11 | 0.023 | 0.005 | 0.012 | 0.002 |\n| 12 | 0.020 | 0.003 | 0.010 | 0.002 |\n| 13 | 0.020 | 0.002 | 0.010 | 0.001 |\n| 14 | 0.018 | 0.001 | 0.010 | 0.002 |\n| 15 | 0.020 | 0.002 | 0.010 | 0.001 |\n\n\n**2. Label assignment:** \nThe labels are assigned using soft label computation, as detailed in Line 8 of the MomentMixup pseudocode (Algorithm 1) in the appendix. Intuitively, soft labeling provides a more accurate target by reflecting the proportional mix of the original samples. This process helps the model establish a clearer decision boundary between classes, improving its ability to generalize to new, unseen data.\n\n**3. INR Generalization:** \nTo further test for generalization beyond the GW loss and centrality measures, we conducted an additional experiment. Following the experimental setup described in the paper, we trained a model on 9 motifs. We then evaluated its extrapolation performance on a different set of motifs, the 5-node subgraphs shown in the ORCA paper [1]. The results in the table below show that the moment estimations are highly accurate, indicating that the model successfully learned the true data distribution.\n\n| motif index | relative error(%) |\n| -- | -- |\n|            10 |                2.22421   |\n|            11 |                1.53611   |\n|            12 |                1.78493   |\n|            13 |                0.0728369 |\n|            14 |                0.204544  |\n|            15 |                1.03096   |\n|            16 |                1.89877   |\n|            17 |                0.461895  |\n|            18 |                0.153658  |\n|            19 |                0.371466  |\n|            20 |                1.74415   |\n|            21 |                1.50211   |\n|            22 |                1.10191   |\n|            23 |                2.46796   |\n|            24 |                0.139989  |\n|            25 |                1.04261   |\n|            26 |                3.08679   |\n|            27 |                1.75301   |\n|            28 |                2.06194   |\n|            29 |                4.01043   |\n|            30 |               11.0857    |\n\n**4. Heterogeneous graph classes:** \nWe thank the reviewer for this insightful comment. We plan to address this important concern by extending our framework to handle heterogeneous classes, and our preliminary results are  promising.\n\nThe key idea is to first partition the graphs within a class into structurally homogeneous clusters using their **moment vectors as features**. Graphs from the same generative mode will have similar moments, making them easily separable in this space. We then apply MomentNet to each cluster to learn a representative graphon for each distinct structural mode.\n\nWe have conducted preliminary experiments confirming the effectiveness of this approach, and we will include a detailed analysis in the camera-ready version.\n\nThis clustering-based strategy is a more explicit version of the principle already implicit in MomentMixup. Currently, by averaging moments different classes (Algorithm 1, Line 2), our method already mitigates some of this structural variance. This demonstrates the versatility of our moment-matching paradigm for modeling complex, multi-modal graph distributions.\n\n**5. Motif sampling efficiency:**\nTo address this question, we highlight an insightful result from our scalability experiments in Figure 2. This figure demonstrates that estimating the true distribution does not require large graphs. Even when large graphs are available, they can be subsampled, as our method's performance remains robust in this small-graph regime. The runtime plots further affirm that using smaller graphs can yield a high-quality estimation efficiently. While subsampling can be applied to any method, Figure 2 shows that our approach has a distinct advantage in these settings, making it particularly practical.\n\n**6. Comparison with diffusion-based model:** \nThe primary goal of our paper is to show that graphon estimation can be done without using a combinatorial loss function (Gromov-Wasserstein (GW) distance). To the best of our knowledge, there is no diffusion-based model that enables graphon estimation. It might be worth mentioning that our proposed method can be seen as a diffusion model with only a backward path, where we match the output distribution with our target based on moment matching.\n\n**7. INR ablation study:**\nWe thank the reviewer for raising this important point and apologize for the lack of clarity in our experimental description. We did not, in fact, use a single architecture for all experiments. Our approach involved selecting an architecture appropriate for the complexity of the target graphon distribution. For simpler graphons, we used a shallow 1-layer MLP, as its limited capacity makes it robust against overfitting to potentially noisy empirical moments. For more complex graphons with high-frequency details, we employed a SIREN architecture, which is standard for INR tasks and is better suited to modeling intricate structures.\n\nThis deliberate choice reflects the trade-off between model expressivity and regularization that the reviewer correctly identified. We recognize this was not made clear in the manuscript. To address this, we will update the experimental section in the camera-ready version to clearly state this as an hyperparameter choice.\n\n---\n\n\nWe hope these responses addresses your main concerns. Thanks once again for your constructive feedback and questions, which will strengthen the quality of the revised manuscript.\n\n\n\n\n## References:\n[1] T. Hocevar, et al. (Bioinformatics 2014) A combinatorial approach to graphlet counting"}, {"review_id": "VYdisiqckE", "reviewer": "Reviewer_K8VW", "summary": "This paper proposes MomentNet, a novel and theoretically principled approach for graphon estimation using implicit neural representations (INRs) trained via moment matching. It avoids costly latent variable inference and combinatorial Gromov-Wasserstein (GW) alignment by learning from empirical motif statistics extracted from observed graphs. The authors further introduce MomentMixup, a graph data augmentation strategy that interpolates motif vectors and generates synthetic graphs via the learned graphon.\nThe paper is well-structured and contains meaningful theoretical insights. It also reports performance improvements in both graphon estimation (on synthetic benchmarks) and graph classification (on small real datasets). However, I believe the paper in its current form does not provide sufficient experimental validation or analysis to support its claims fully.", "questions": "Suggestions for Improvement\n1. Include ablation experiments that isolate the effect of MomentNet (without mixup) vs. MomentMixup (with simple generators).\n2. Perform motif selection analysis, including importance ranking, sensitivity motif size/type, and robustness to noise.\n3. Test MomentNet on more complex graphons (e.g., high-frequency, oscillating, or hierarchical structures).\n4. Try estimating graphons from real-world graphs and visualizing or interpreting the learned functions.\n5. Add stronger augmentation baselines such as DropEdge, GraphTransplant, or SubgraphMix, to better situate MomentMixup.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n1. Theoretically grounded: The paper offers a rigorous upper bound on the cut distance between estimated and true graphons using a moment-based INR approximation, which is both novel and elegant.\n2. Conceptual simplicity: The use of empirical motifs to bypass latent node estimation is clever, computationally efficient, and scalable.\n3. Clear writing and organization: The overall exposition is solid and follows logical structure from motivation to theory to experiments.\n\n**Weaknesses**\n1. Weak Evaluation of MomentMixup\nWhile MomentMixup is a key contribution of the paper, the empirical support is limited: Only one baseline is considered (G-Mixup); Only four relatively small datasets are used (IMDB-B, IMDB-M, REDDIT-B, AIDS); The performance improvements presented are marginal in most settings.\n2. Fixed and Unanalyzed Motif Design\nThe method relies on a fixed set of motifs (up to 5 nodes) computed using the ORCA library, but provides no justification, selection criteria, or ablation analysis. The performance may heavily depend on motif relevance, redundancy, or sparsity. This weakens the generality and robustness of the proposed method, especially when applied to diverse graph types.\n3. Lack of Graphon Complexity in Experiments\nAll graphon estimation experiments are conducted on relatively smooth, synthetic graphons. The INR used is a shallow 1-layer MLP. There is no investigation into whether MomentNet can recover more complex or high-frequency graphons, or how its performance scales with harder tasks. This limits the scope and applicability of the method.", "was_revised": true, "final_justification": "This paper proposes MomentNet, a theoretically grounded approach for graphon estimation using implicit neural representations (INRs) trained via moment matching. It eliminates the need for costly latent variable inference and Gromov-Wasserstein alignment by learning from motif statistics in observed graphs. The authors also introduce MomentMixup, a graph data augmentation method that interpolates motif vectors to generate synthetic graphs via the learned graphon.\n\nThe authors have made valuable improvements, especially with the ablation studies and motif selection analysis, which address key concerns raised by the reviewers. Although I still have some doubts, such as the insufficient baseline comparison, I believe the interesting theoretical contributions make the paper potentially acceptable.", "rebuttal": "Thank you for your comments and feedback. We address these in the following subsections:\n\n**1. Graphon complexity and INR architecture**\nWe evaluated our method using stochastic block models and a bipartite graphon (items 12 and 13 in the appendix, Table 2) as hierarchical graph representations, as well as a cosine graphon as an oscillating instance for the scalability evaluation. The results of these experiments, presented in Figure 2, show that our method's performance was superior to SOTA approaches.\n\nWe agree that while a simple architecture can perform well on benchmark datasets, a more complex network is generally required to represent a highly complex function. This is why we treated the network as a hyperparameter (which we will make sure to clarify in the manuscript, as it is not there now), and select the best performing architecture for each graphon. This reflects the known limitations of modeling complex functions with small or shallow neural networks. Note that this is also true for other approaches that use INRs. \n\nDuring the rebuttal, we did not have time to run experiments tailored to your comment, but we will revise the paper to incorporate the points you raised and a summary of this response.\n\n**2. Motif selection analysis**\nWe thank the reviewer for the careful analysis and for raising these important points about our theoretical guarantees. We have included a thorough ablation test. Please, refer to the response to reviewer ogzT for a detailed explanation of this new analysis, which will be included as a new appendix in the camera-ready version of the paper.\n\n\nRegarding robustness to noise:\nThe generation of a graph from a graphon is an inherently random process (as detailed in the Graphons subsection of Section 2). Consequently, the moment vector computed from a single sampled graph is a random (noisy) observation of the true moment vector. By generating graphons independently and averaging over their associated vectors, we obtain an unbiased estimator of the actual moments.\nTherefore, the experiments we conducted inherently used these random observations of the true moment vector. Introducing other kinds of noise to the graphon or the graph sampling process is of interest but, unlike this statistical noise, would risk making the estimator biased.\n\n**3. Other data-augmentation baselines and evaluation of MomentMixup.**\n\n*Baselines:* We compared our method against G-Mixup [1], a SOTA approach. In their paper, the authors show that G-Mixup is superior to other methods like DropEdge and Subgraph Mixup (see Table 2 in [1]). Since G-Mixup represents a stronger and more relevant baseline, we focused our comparison on it. Including the scores for these weaker baselines would not alter the conclusions drawn from our results.\n\n*Evaluation of MomentMixup:* The limitations regarding the datasets are primarily because our method relies on structural proximity. Incorporating graph features into the graphon estimation process is left as future work, which will enable us to conduct experiments on a broader range of datasets. Even though some of the selected datasets are relatively small, our scalability analysis (Figure 2b, c) shows that our method outperforms others in graphon estimation. The results in Table 1 verify this claim. More specifically, for the AIDS dataset, which lacks large graphs, other approaches degraded in performance due to inaccurate graphon estimation, whereas our method excelled. The details of the datasets are provided in the following table. It is also worth mentioning that other methods are unable to estimate the graphon based on the moment vector and thus are not able to satisfy Proposition 1.\n| Dataset         | Total Graphs | Min Nodes | Max Nodes |\n|-----------------|--------------|-----------|-----------|\n| IMDB-BINARY     | 1000         | 12        | 136       |\n| IMDB-MULTI      | 1500         | 7         | 89        |\n| REDDIT-BINARY   | 2000         | 6         | 3782      |\n| AIDS            | 2000         | 2         | 95        |\n\nFurthermore, the marginal gains observed in data augmentation can be attributed to our focus on structural proximity, deliberately avoiding the incorporation of other factors like node features in this process. We plan to explore the integration of such features in our future work. We want to emphasize that our primary contribution is the estimation of scalable graphons using moments, which enables applications such as data augmentation and statistical network analysis, like the centrality measures mentioned in the appendix. A summary of this response will be incorporated in the revised paper.\n\n**4. Visualizing real-world graph distribution.**\nAs mentioned in the conclusion (line 361), we hypothesize that in real-world datasets, graphs within each class do not belong to a single specific distribution but rather to a mixture of graphons. In this paper, we focused on homogeneous graphs for the graphon estimation task. To address this comment, we have performed a preliminary experiment on moment-based clustering, to be able to create graphs from a class coming from a mixture of graphons. We couldn't report these preliminary results here due to the impossibility to include figures. If the paper gets accepted, we will expand the experiments and include them in the camera-ready version of the paper. This approach is effective because graphs generated from the same underlying graphon have very similar moment vectors. Consequently, when represented as points in the moment feature space, these graphs naturally form distinct clusters.\n\n\nThank you again for your feedback and suggestions, which we believe have clarified and strengthened our work.\n\n## References:\n[1] X. Han, et al. (PMLR 2022) G-Mixup: Graph Data Augmentation for Graph Classification"}, {"review_id": "6FKuOPPCBP", "reviewer": "Reviewer_ecYZ", "summary": "This paper proposes MomentNet, a scalable graphon estimator that employs moment matching with implicit neural representations (INRs). The method estimates graphons by matching empirical subgraph counts (\"moments\") derived via counting from observed graphs. The authors demonstrate theoretically that when the neural network can accurately approximate the motifs, the overall graphon estimation error remains bounded. Through moment matching, they circumvent computationally expensive Gromov-Wasserstein loss estimations.", "questions": "- Can you provide concrete examples where the computational advantage over SIGL becomes critical?\n- How sensitive is the method to Monte Carlo sampling variance during training?\n- Can you compute the actual bounds from Theorem 1 for your experimental settings?", "limitations": "While not covered in an explicit \"Limitations\" section, this is honestly discussed in the Conclusion.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths:\n\n**Overall:**\n\nThe central insight connecting motif approximation to graphon estimation quality (Theorem 1) is elegant and well-motivated. The idea of bypassing expensive Gromov-Wasserstein optimization through direct moment matching represents a meaningful algorithmic contribution. The paper is generally well-written.\n\n**Clarity** while good in general could be improved at two points:\n- ORCA and graphlets are fundamental to the approach but barely explained.\n- Strange wording: l14-15 “the estimated graphon achieves a provable upper bound in cut distance from the ground truth”\n\n**Reproducibility:** Code is provided and results seems reproducible \n\n## Weaknesses:\n\n**Critical moments-selection limitation not addressed:**\nThe authors acknowledge that relying on pre-selected moments is a major limitation but defer this to future work. While I appreciate this honest discussion, for a venue like NeurIPS with its strong practical focus, this seems like a fundamental issue that should be addressed in the current work. Without adaptive moment selection, the method's applicability remains quite limited, and it raises concerns about potential cherry-picking of motifs. This limitation significantly reduces the paper's practical significance, as the effectiveness of the approach becomes heavily dependent on domain expertise for motif selection. The contribution would be substantially more impactful if an automatic moment selection procedure were introduced and demonstrated to work well across different graph types.\n\n**Limited practical impact of computational gains:**\nWhile the polynomial runtime is nice theoretically, the experiments show SIGL running in ~250 seconds, which isn't prohibitive for most applications. The authors should demonstrate scenarios where existing methods become truly infeasible to strengthen their computational efficiency claims.\n\n**Missing technical validation:**\nNo discussion of Monte Carlo gradient estimation stability, which could be problematic for training. \nThe theoretical bounds in Theorem 1 are never computed for the experimental settings. Showing whether these bounds are tight would significantly strengthen the claims. \n\n## Summary:\nWhile the core idea has merit and Theorem 1 provides compelling theoretical motivation, the paper needs to address the fundamental moment selection problem and demonstrate clearer practical advantages before meeting the bar for NeurIPS. The theoretical contributions, though heavily building upon existing work, are sound and well-executed. The experimental gains are modest but show promise for the approach's potential.", "was_revised": true, "final_justification": "While I still have some doubts about the practical relevance of the polynomial runtime and the experimental gains, I acknowledge that choosing all motifs with up to 4 nodes might be a good general choice of considered motifs and I consider this as sufficiently resolved. I particularly like the theory of the paper and that it proposes a novel approach instead of something totally incremental.", "rebuttal": "Thanks for reviewing our paper and the feedback you provided. We address your comments and questions in the following subsections:\n\n**1. Clarity issues.**\n\nORCA and graphlets: As our proposed method is independent of the specific algorithm for graphlet and motif enumeration, we have adopted the ORCA toolkit for our implementation. A thorough explanation of the ORCA methodology, along with a detailed explanation of graphlets, is available in the original publication [1], to which we referred the interested readers. We will include a more detailed summary of these concepts in the final manuscript, if accepted.\n    \n Strange wording; \"the estimated graphon achieves a provable upper bound in cut distance from the ground truth\". We thank the reviewer for spotting this. We modified it so that the sentence in the camera-ready version will read as: \"the cut distance between the estimated graphon and the ground truth is provably upper-bounded.\"\n    \n**2. Ablation test for Moment selection.**\nWe thank the reviewer for the careful analysis and for raising these important points about our theoretical guarantees. We have included a thorough ablation test. Please, refer to the response to reviewer ogzT for a detailed explanation of this new analysis. This analysis will be included as a new appendix in the camera-ready version of the paper.\n\n\n**3. Computational cost concern compared with SIGL.**\n\nThe scalability evaluation in Figure 2 (Section 5.1.2) demonstrates the conditions under which our method achieves a decisive computational advantage over SIGL. A key insight from both the figure and a similar experiment in the appendix is that SIGL’s performance deteriorates on smaller graphs. This limitation benefits our approach: by subsampling a very large graph into a smaller, more manageable subgraph, we still outperform SIGL. In contrast, SIGL would require well over 250 s to obtain comparable results on the same subgraph, making such sampling ineffective for that method. Although this runtime is not explicitly plotted, it can be inferred from the reported data (this will be clarified in the camera-ready paper).\n\nTo further validate this observation, we constructed a dataset of ten graphs, each containing 2,000 nodes. Because both MomentNet and SIGL incur high computational costs when processing the full graphs, we extracted ten 50-node subgraphs from each 2,000-node graph and used these as inputs. We adopted the same dense-graph graphon class employed in the scalability analysis of MomentNet (Section 5.1.2). The results, summarized in the table below, confirm that our method outperforms SIGL in both accuracy and runtime in the large-graph regime. Crucially, while SIGL’s runtime increases sharply with graph size, our method maintains comparable performance even on the smaller subgraphs. A more comprehensive version of this experiment will be included in the camera-ready paper.\n\n| Method | Training Runtime (s) | GW Loss | Motif Counting Runtime (s) |\n| :--- | :---: | :---: | :---: |\n| **MomentNet** | $54.83 \\pm 18.69$ | $0.0548 \\pm 0.0016$ | $1.59 \\pm 0.24$ |\n| **SIGL** | $207.89 \\pm 18.4$ | $0.1085 \\pm 0.0156$ | - |\n\n**4. Can you compute the actual bounds from Theorem 1 for your experimental settings? The theoretical bounds in Theorem 1 are never computed for the experimental settings. Showing whether these bounds are tight would significantly strengthen the claims.**\n\n\nWe thank the reviewer for this very valuable suggestion. The primary purpose of our theoretical section is to provide a formal justification for our method's design and to formalize the intuition that its performance improves with access to more or larger graph samples. We argue that our guarantees, while relying on a standard assumption, are valid, as the assumption is empirically validated and the theoretical conditions are met in practical scenarios. We will cover next the different aspects and assumptions of the proposed theoretical characterization.\n\n*a. On Satisfying Assumption 1 (Achievable Motif Error)*\n\nThe reviewer is correct that we do not provide a formal optimization guarantee. However, Assumption 1 is standard in literature involving neural network estimators and is supported by two pillars: the Universal Approximation Theorem (guaranteeing a sufficiently expressive network *exists*) and the widespread empirical success of modern optimizers in finding high-quality solutions.\n\nWhile a formal proof is challenging, we demonstrate empirically that Assumption 1 is readily satisfied. Our loss function, $L(\\theta)$, is a direct proxy for the motif approximation error required by the assumption. The table below shows the final average loss for a benchmark graphon, using motifs up to size $k=4$ (9 total motifs).\n\n|#Motifs|avg_loss|std_loss|\n|---|---|---|\n|1|0.0|1e-06|\n|2|2e-06|1e-06|\n|3|1.4e-05|1.5e-05|\n|4|5e-06|3e-06|\n|5|1e-05|1e-05|\n|6|2e-05|1.4e-05|\n|7|3e-05|2.5e-05|\n|8|5.4e-05|3.7e-05|\n|9|5.8e-05|6.7e-05|\n\nThe optimization consistently drives the motif error to extremely small values (on the order of 1e-5), showing that achieving a small $\\delta_M$ is an empirical reality for our method, not just a theoretical hope.\n\n*b. On Sample Complexity and necessary probabilistic Bounds*\n\nGiven that a small motif error $\\delta_M$ is achievable, we now show that the overall probabilistic bound from Equation (6) is non-vacuous for realistic dataset sizes. We analyze this bound for $k=4$ and a conservatively large motif error of $\\delta_M = 0.07$ (which is orders of magnitude larger than our empirical results). The table below shows the failure probability (lower bound of $\\zeta$ in equation 6) for various numbers of graphs $P$ and nodes $n$.\n\n|$\\zeta$|$P=400$|$P=600$|$P=800$|$P=1000$|$P=1200$|$P=1400$|$P=1600$|$P=1800$|$P=2000$|\n|---|---|---|---|---|---|---|---|---|---|\n|$n=200$|11.63|11.45|11.27|11.10|10.93|10.76|10.59|10.43|10.26|\n|$n=250$|9.93|9.04|8.22|7.48|6.81|6.19|5.63|5.13|4.66|\n|$n=300$|7.87|6.37|5.16|4.18|3.39|2.74|2.22|1.80|1.46|\n|$n=350$|5.97|4.22|2.97|2.10|1.48|1.04|0.74|0.52|0.37|\n|$n=400$|4.42|2.68|1.62|0.99|0.60|0.36|0.22|0.13|0.08|\n|$n=450$|3.21|1.66|0.86|0.44|0.23|0.12|0.06|0.03|0.016|\n\nAlthough values > 1 are uninformative as probabilities, the table clearly shows the bound's exponential decay. Crucially, the guarantee becomes meaningful for realistic data regimes. For example, the REDDIT-B dataset has $P=2000$ graphs with an average $n \\approx 497$. Our analysis shows that in a comparable setting ($n=450$, $P=2000$), the failure probability $\\zeta$ is a practically useful **0.016**. This confirms the bound is not vacuous.\n\n*Conclusion*\n\nIn summary, our theoretical analysis provides a sound foundation for our method by formally connecting the quantity of input data ($P$ and $n$) to the final estimation error. We show that:\n1.  The core assumption of learning motifs accurately is empirically validated.\n2.  The theoretical conditions for our guarantee to hold are met within realistic data regimes.\n\nTherefore, the theory serves its purpose of providing a formal rationale for our moment-matching approach. We will add an appendix clarifying this perspective and summarizing these empirical findings to strengthen the paper.\n\n**5. Monte Carlo sampling variance.**\nBased on the relatively high quality of the results achieved by our method, we hypothesize that stable convergence is contingent upon a low Monte Carlo variance. To investigate this hypothesis directly, we designed an experiment to measure the gradient variance as a function of the number of MC samples. For this test, the parameters of the INR model were held constant while we estimated the gradient's standard deviation over 1,000 runs for varying numbers of samples, $L$. The results, summarized in the following table, show a clear inverse relationship: the standard deviation consistently decays as $L$ increases. This finding supports our hypothesis and underscores the importance of using a sufficient number of samples. We will add this experiment to the appendix of the camera-ready version of paper.\n\n| $L$    | mean_gradient | std_gradient |\n| :----- | :------------ | :----------- |\n| 100    | 0.013005      | 0.004484     |\n| 500    | 0.013107      | 0.002031     |\n| 1000   | 0.013030      | 0.001387     |\n| 5000   | 0.013019      | 0.000647     |\n| 10000  | 0.013052      | 0.000439     |\n| 20000  | 0.013009      | 0.000325     |\n| 50000  | 0.013013      | 0.000193     |\n| 100000 | 0.013019      | 0.000134     |\n\n\nWe conclude by thanking the reviewer for feedback and suggestions that, in our view, have contributed to clarify our contributions and strengthened the paper.\n\n## References:\n[1] T. Hocevar, et al. (Bioinformatics 2014) A combinatorial approach to graphlet counting"}, {"review_id": "lhpdgCwpcX", "reviewer": "Reviewer_3v3g", "summary": "The paper proposes MomentNet, an implicit-neural-representation (INR) estimator that fits a graphon by matching a fixed set of induced-motif densities (“moments”) from observed graphs.  This approach is claimed to be more scalable and avoids the need for latent variable estimation. They claim a finite-sample bound on the cut distance under an assumption of INR. And they also introduce MomentMixup, a data augmentation technique operating in moment space. Experiments on synthetic graphons and four small graph-classification datasets show modest gains over USVT and IGNR and parity with SIGL.", "questions": "1. **Theoretical validity**: Can you provide empirical evidence of when Assumption 1 holds? What are typical motif errors δ achieved in practice, and how do they relate to the theoretical requirements?\n\n2. **Large-scale evaluation**: Can you demonstrate performance on graphs with >5000 nodes to validate scalability claims? Include timing breakdown between Stage 1 (motif counting) and Stage 2 (INR training).\n\n3. **Motif selection**: What is the rationale for using only 4-node motifs when 5-node motifs are available? How does motif dictionary size affect estimation quality and computational cost?\n\n4. **Dense graph performance**: How does the method perform on dense graphs (edge density >0.5) with realistic node counts?\n\n5. **Statistical significance**: Can you provide paired t-tests for MomentMixup improvements and confidence intervals for comparisons?", "limitations": "### **Major Technical Issues**\n\ni) **Assumption 1 Analysis**  \n   The theoretical guarantee fundamentally depends on the INR’s ability to approximate empirical motif densities within tolerance $\\delta$. Refer Weakness 1.\n\nii) **Complexity Contradiction**  \n   The paper claims scalability but reveals $\\Theta(n^4)$ complexity for dense graphs. Refer Weakness 2. For the dense regime, we have:\n   $\n   T = O \\Bigl(\\bigl\\lceil P / M\\bigr\\rceil n_T^4 + N_e \\ (L \\cdot C_{INR} + |\\theta|)\\Bigr)\n   $\n   while SIGL [2] gives\n   $\n   T = O(P \\cdot N_e \\cdot n_T^2).\n   $\n   This makes SIGL asymptotically faster for large dense graphs, contradicting the main scalability claim.\n\n### **Limitations Assessment**\n\nThe authors acknowledge some limitations but miss critical issues:\n\ni) **Unaddressed**: Theoretical assumption verification, large-scale evaluation gaps, motif-selection methodology.\n\nii) **Insufficient**: No discussion of $\\Theta(n^4)$ complexity implications or energy consumption for large graphs.\n\n### **Writing Issues**\n\nSee Weakness 5: duplicated citations for [27] and [28], wrong reference [22]; unclear symbols.\n\n### **Review Summary**\n\nAccording to the above weaknesses and limitations, I maintain a Borderline Reject rating as there are several fundamental issues that prevent this work from meeting the NeurIPS standards before being resolved.\n\n### Reference\n\n[1] Xia, X et al. (AISTATS 2023) Implicit Graphon Neural Representation.  \n[2] Ali Azizpour et al. (AISTATS 2025) Scalable Implicit Graphon Learning.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### **Strengths**  \n1. **Clear Idea, Simple Pipeline** : Replacing Gromov-Wasserstein optimisation with direct moment matching is conceptually clean and easy to implement. It reduce optimization overhead present in methods like IGNR [1].\n2. **Continuous Representation** – Using an INR yields a resolution-free graphon that can be sampled at an arbitrary size.  \n\n### **Weaknesses:**\n\n1. **Vacuous Theoretical Guarantees** I carefully checked the theory and the provided supplementary material. Theorem 1 relies fundamentally on **Assumption 1**, which requires the INR to drive every motif error below $\\delta$. However: \n\n\ti) No optimization bounds are provided showing when this assumption can be satisfied. \n\n\tii) No sample complexity analysis demonstrates how many samples are needed in practice. \n\n\tiii) The condition requires $\\Omega(k^2/\\delta)$ samples per motif but provides no guidance on achievable $\\delta$ values.\n\n2. **Severe Scalability Limitations**  ($O(n^4)$ Dense Complexity) I read and checked the paper and Appendix D. There's a fundamental scalability problem: \n\n\ti) **Dense graphs**: Even with full parallelization, Stage 1 costs $\\Theta(n^4)$ due to 4-node graphlet counting. \n\n\tii) **Comparison with SIGL**: SIGL achieves $\\Theta(n^2)$ complexity, making it asymptotically superior for dense graphs. So the **\"Scalable\" claim is misleading**: The method only scales well for sparse graphs where degree $d = O(1)$.\n\n3. **Mixed and Questionable Empirical Results**\n\n\ti) **Graphon estimation**: MomentNet loses to SIGL on $4/13$ benchmark graphons.\n\n\tii) **Statistical significance**: MomentMixup improvements of $\\leq 2$ percentage points fall within $1\\sigma$ error bars on most datasets.\n\n\tiii) **No ablation studies**: No analysis of motif selection impact or dictionary size effects.\n\n4. **Issuses on Experimental Validation**\n\n\ti) **Limited motif analysis**: While ORCA can handle 5-node motifs, authors use only 9 motifs up to 4 nodes without ablation studies on motif dictionary size or selection impact.\n\n\tii)  **Limited scale**: Largest experiment far below the range where the number of nodes becomes prohibitive ($n > 5000$ nodes).\n\n\tiii) **Missing dense graph evaluation**: No experiments on realistically large dense networks.\n\n5. **Poor Writing and Citation Issues** During review, I found that,\n\n\ti) **Duplicate citations**: References [27] and [28] are identical papers with different labels.\n\n\tii) **Wrong citation item**: Reference [22] is in wrong format and seems to mix two papers in one item.\n\n\tii) **Notation inconsistencies**: Switching between $W$, $W^*$, $\\hat{W}_{\\theta}$ without clear distinction.\n\n6. **Methodological Concerns**\n\n\ti) **Inverse weighting scheme**: The loss function (Eq. 5) uses $w_i = 1/m_i$ weights without theoretical justification, potentially causing instability for small moment values.\n\n\tii) **Limited motif selection guidance**: No principled approach for choosing appropriate moments for different graph types.\n\n\tiii) **MomentMixup justification**: While Proposition 1 shows convex combinations of graphons differ from moment combinations, practical implications for data augmentation remain unclear.\n\n### Reference\n[1] Xia, X et al. (AISTATS 2023) Implicit Graphon Neural Representation.\n\n[2] Ali Azizpour et al. (AISTATS 2025) Scalable Implicit Graphon Learning.", "was_revised": true, "final_justification": "After the rebuttal and discussion with the author's rebuttal, the author has addressed my concerns about the previous version's mismatch, conducted extra ablation studies on the main issue of complexity. With the author's commitment to including all these fixes and experiment details in the revision, I update my rating from Weak Reject (3) to Weak Accept (4).", "rebuttal": "# Reviewer 4\n\nThanks for reviewing the paper. Answers to your comments and questions follow.\n\n## Weaknesses and Questions\n\n**1. Vacuous theoretical guarantees and theoretical validity**\nWe thank the reviewer for the careful analysis and for raising these important points about our theoretical guarantees. We have included a thorough analysis of the bound in Theorem 1, with empirical evidence showcasing its applicability. Please, refer to the response to reviewer ecYZ for a detailed explanation of this new analysis, that will be included as a new appendix in the camera-ready version of the paper.\n\n**2. Severe scalability limitations**\nThank you for this detailed review. As stated in the ORCA paper [1], \"experiments show that the bound is not tight.\" In line with this, we conducted empirical experiments and found the actual time complexity of counting motifs up to size four for clique graphs (highly dense) to be $\\Theta(n^3)$. Unfortunately, we cannot include our experimental plot due to NeurIPS guidelines preventing to post figures, but we will make sure to include it in the camera-ready version of the paper.\nWhile the theoretical complexity analysis of SIGL[2] indicates a faster runtime in the dense regime due to its quadratic complexity, our experiments in Figure 2c show that our method's runtime is still faster on larger, dense graphs. This can be attributed to the fact that the empirical time complexity of our method on the dense graphs in our dataset is lower than the theoretical bound and practically comparable to SIGL.\nA key insight from Figure 2 is that our method can subsample a graph to reduce its size while maintaining near-optimal performance, a capability that SIGL lacks. Given the parameters $P$ and $n_T$ in our time complexity, we can decrease $n_T$ in highly dense regimes to drastically reduce the runtime while ensuring a sufficient $P$ to preserve performance. Although not explicitly shown in Figure 2c, this can be easily deduced. Therefore, our claim of scalability remains valid even for highly dense graphs. We will add a comprehensive experiment on this trade-off to the appendix of the camera-ready version.\n\n**Large-scale evaluation**\nThe same argument mentioned in the previous part holds for experiments on graphs with more than 5000 nodes. Since our model does not require the full graph as input to the INR to perform well, we can leverage subsampling and decrease the $n_T$ parameter. This strategy allows us to achieve a significantly better runtime and maintain strong performance compared to SIGL. We will demonstrate this empirically in the comprehensive experiment mentioned previously. For the sake of the rebuttal, we present a focused experiment to specifically validate our claim on large graphs where scalability is a key challenge. The experiment is detailed in our response to Reviewer ecYZ's concern regarding the computational cost compared with SIGL. \nA extended version of this experiment will be included in the camera-ready version of the paper, if it gets accepted.\n\n**Dense graph performance**\nIn response to the reviewer's question about graphon estimation with dense graphs, we want to emphasize that our experiments already cover dense graphons. Specifically, Graphons 3, 4, 5, 6, 9, and 11 in Table 2 of the appendix are all dense graphs with an edge density greater than 0.5. The corresponding results are shown in Figure 2a. Additionally, the graphon used for the scalability analysis in Figures 2b and 2c is also dense. If the reviewer is interested in a particular graph structure that we have not addressed, we would appreciate the clarification.\n\n**3. Mixed and questionable empirical results**\n**3.i) MomentNet loses to SIGL on 3/14 benchmarks**\nWe acknowledge the reviewer's point regarding the 3 (out of 14) benchmark graphons where SIGL shows a slight performance advantage. We wish to place this result in the proper context:\n* **Competitive Performance:** As shown in Figure 2a, the performance difference on these few benchmarks is minimal. Conversely, MomentNet demonstrates superior or equivalent performance on the vast majority (11/14) of the benchmarks, showcasing its strong generalizability.\n* **A Favorable Trade-off for Scalability:** When analyzing large graphs sampled from any given graphon class, MomentNet has the ability to converge on a high-accuracy solution significantly faster than competing methods.\nIn summary, while SIGL may attain a marginal victory on a small subset of the graphons, MomentNet provides a more compelling overall package: state-of-the-art accuracy in most cases and superior scalability in all cases, rendering it a more versatile and practical method.\n\n**3.ii) Statistical significance**\nAlthough our focus was not on establishing a new state-of-the-art in graph classification, we aimed to provide a novel, scalable, and flexible alternative for the challenging task of graph data augmentation using mixup. As demonstrated, our results serve as a proof-of-concept that validates this as a viable approach to the graph data augmentation problem. We will make sure to relax the statements in this regard for the camera-ready version of the paper. It is also worth mentioning that the marginal gain in both g-mixup and SIGL is similarly small compared to previous SOTA methods. This is primarily because these methods rely solely on the graph structure for creating new samples and for classification; incorporating node features is not yet possible. As we state in the future work section of the conclusion, we aim to investigate how to incorporate features into this graph generation process, which will enable us to use a wider range of datasets. We plan to conduct statistical tests to validate the results and will add them to the paper in the next revision.\n\n**3.iii) Ablation studies and motif selection**\nWe thank the reviewer for the careful analysis and for raising these important points about our theoretical guarantees. We have included a thorough ablation test. Please, refer to the response to reviewer ogzT for a detailed explanation of this new analysis, that will be included as a new appendix in the camera-ready version of the paper.\nRegarding the computational complexity of higher-order motifs, our approach remains efficient. Even for graphons that are highly dependent on these more complex structures, our subsampling strategy allows for strong performance with a significantly smaller runtime compared to other baselines. We will add this experiment and the statement about complexity in the large-graph regime to the camera-ready version of the paper.\n\n**4. Issues on experimental validation**\n* **Limited motif analysis**: The ablation study is provided in the previous subsection. We also want to emphasize that our method is agnostic to methods for counting graphlets.\n* **Limited scale**: We addressed this potential weakness in Section 2 of our response.\n* **Missing dense graph evaluation**: We addressed this potential weakness in Section 2 of our response.\n\n**5. Poor writing and citation issues**\nWe apologize and thank you for highlighting these issues. They will be corrected in the camera-ready version, which will be carefully proofread.\n\n**6. Methodological concerns**\n* **Inverse weighting scheme**: We appreciate your concern regarding the potential instability of our approach. As demonstrated by our results for sparse graphons in Figure 2a, the training process is indeed stable. To further mitigate instability, particularly in cases of very low graph densities, we set the corresponding weights to 1. This weighting scheme was selected after an empirical evaluation against several alternatives (no weighting or exponential weighting schemes), where it demonstrated superior performance. We will clarify the details of this strategy in the appendix of camera-ready version of the paper.\n* **Limited motif selection guidance**: We addressed this potential weakness in Section 3 of our response.\n* **MomentMixup justification**: The practical implication of our approach is to introduce a data augmentation technique for graphs analogous to mixup[3] in other domains like computer vision. Just as mixup creates new training samples by interpolating between existing data points and their labels to improve generalization, our method of creating convex combinations of graphons generates novel, synthetic graphs. This encourages the model to learn a smoother, more robust decision boundary. Our rationale for using moment mixup over g-mixup[4] is to ensure that augmented samples remain structurally similar to a specific class. We define this structural proximity through subgraph densities, which are precisely captured by graph moments. As established in Proposition 1, performing mixup directly on graphons does not guarantee the preservation of these crucial moment-based structures.\n\nThank you again for your valuable feedback and suggestions, which we believe have contributed to clarifying and strengthening our work.\n\n## References:\n[1] T. Hocevar, et al. (Bioinformatics 2014) A combinatorial approach to graphlet counting \n\n[2] A. Azizpour et al. (AISTATS 2025) Scalable Implicit Graphon Learning\n\n[3] H. Zhang, et al. (ICLR 2018) mixup: Beyond Empirical Risk Minimization\n\n[4] X. Han, et al. (PMLR 2022) G-Mixup: Graph Data Augmentation for Graph Classification"}]

Author rebuttal:

Meta-review: This paper proposes MomentNet, a novel, scalable graphon estimation method using moment matching and implicit neural representations (INRs) of graphons. Given a set of graphs, all assumed to have been sampled from the same unknown ground-truth graphon, an INR representing a graphon is optimized to match the motif counts of the target graphs. The paper proposes a theorem for supporting the proposed method. 

All reviewers evaluated this paper positively, stating that the paper is clear, the method is novel, has good numerical properties, and is backed by theory. 

**Mandatory revision for camera-ready:** One significant shortcoming in the current presentation is that theorems are stated in the main paper without explicitly writing their assumptions, which creates a misleading impression of their significance. Once seeing the assumptions in the appendix, readers will realize that the theoretical results are weaker than they were initially led to believe. For example, **please move Assumption 1 to the main paper as it is a highly nontrivial condition of Theorem 1**, and hence not a small detail that can be ignored in the main paper. Moreover, the statement in Assumption 1 is in fact not formulated as an assumption. An assumption is a condition that you suppose on the parameters of the problem/theoretical setting. What you “assume” here is in fact a conjectured property. So change the title to a hypothesis or a conjecture, and move it to the main paper. Now, to make Theorem 1 rigorous, you need to formulate assumption 1 as a rigorous mathematical assumption on the parameters of the problem, deleting the sentence “Given a sufficiently expressive neural network architecture” which is an interpretation and not a mathematical statement. The assumption should simply be about the approximation error of the homomorphism densities. Hence, Theorem 1 should be clearly described as an approximation theorem, not an optimization theorem. 

Moreover, please introduce all notations throughout the paper. For example, $\delta_M$ and $\eta$ are not defined in Theorem 1.
Decision: Accept (poster)