Reviewer 4

Thanks for reviewing the paper. Answers to your comments and questions follow.

Weaknesses and Questions

1. Vacuous theoretical guarantees and theoretical validity We 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.

2. Severe scalability limitations Thank 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. While 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. A 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.

Large-scale evaluation The 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. A extended version of this experiment will be included in the camera-ready version of the paper, if it gets accepted.

Dense graph performance In 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.

3. Mixed and questionable empirical results 3.i) MomentNet loses to SIGL on 3/14 benchmarks We 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:

• 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.
• 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. In 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.

3.ii) Statistical significance Although 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.

3.iii) Ablation studies and motif selection We 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. Regarding 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.

4. Issues on experimental validation

• 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.
• Limited scale: We addressed this potential weakness in Section 2 of our response.
• Missing dense graph evaluation: We addressed this potential weakness in Section 2 of our response.

5. Poor writing and citation issues We apologize and thank you for highlighting these issues. They will be corrected in the camera-ready version, which will be carefully proofread.

6. Methodological concerns

• 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.
• Limited motif selection guidance: We addressed this potential weakness in Section 3 of our response.
• 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.

Thank you again for your valuable feedback and suggestions, which we believe have contributed to clarifying and strengthening our work.

References:

[1] T. Hocevar, et al. (Bioinformatics 2014) A combinatorial approach to graphlet counting

[2] A. Azizpour et al. (AISTATS 2025) Scalable Implicit Graphon Learning

[3] H. Zhang, et al. (ICLR 2018) mixup: Beyond Empirical Risk Minimization

[4] X. Han, et al. (PMLR 2022) G-Mixup: Graph Data Augmentation for Graph Classification

Thanks for reviewing our paper and the feedback you provided. We address your comments and questions in the following subsections:

1. Clarity issues.

ORCA 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.

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."

2. Ablation test for Moment selection. We 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.

3. Computational cost concern compared with SIGL.

The 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).

To 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.

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.

We 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.

a. On Satisfying Assumption 1 (Achievable Motif Error)

The 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.

While 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).

The 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.

b. On Sample Complexity and necessary probabilistic Bounds

Given 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$.

Although 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.

Conclusion

In 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:

1. The core assumption of learning motifs accurately is empirically validated.
2. The theoretical conditions for our guarantee to hold are met within realistic data regimes.

Therefore, 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.

5. Monte Carlo sampling variance. Based 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.

We conclude by thanking the reviewer for feedback and suggestions that, in our view, have contributed to clarify our contributions and strengthened the paper.

References:

[1] T. Hocevar, et al. (Bioinformatics 2014) A combinatorial approach to graphlet counting

Thank you for your insightful comments and questions. We address those in the following subsections.

1. Choice of moments (Ablation Study): Our 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. This 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. However, 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$).

2. Label assignment: The 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.

3. INR Generalization: To 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.

4. Heterogeneous graph classes: We 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.

The 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.

We have conducted preliminary experiments confirming the effectiveness of this approach, and we will include a detailed analysis in the camera-ready version.

This 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.

5. Motif sampling efficiency: To 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.

6. Comparison with diffusion-based model: The 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.

7. INR ablation study: We 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.

This 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.

---

We 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.

References:

[1] T. Hocevar, et al. (Bioinformatics 2014) A combinatorial approach to graphlet counting

Thank you for your comments and feedback. We address these in the following subsections:

1. Graphon complexity and INR architecture We 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.

We 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.

During 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.

2. Motif selection analysis We 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.

Regarding robustness to noise: The 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. Therefore, 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.

3. Other data-augmentation baselines and evaluation of MomentMixup.

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.

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.

Furthermore, 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.

4. Visualizing real-world graph distribution. As 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.

Thank you again for your feedback and suggestions, which we believe have clarified and strengthened our work.

References:

[1] X. Han, et al. (PMLR 2022) G-Mixup: Graph Data Augmentation for Graph Classification

You're welcome. Additionally, note that for the paper you referenced [1], a report [2] seemingly indicates that the G-Mixup may not be as advantageous as claimed by the authors. A 2025 survey [3] also summarizes newer methods that have emerged in the field.

[1] Han, Xiaotian, et al. "G-mixup: Graph data augmentation for graph classification." International conference on machine learning. PMLR, 2022.

[2] Omeragic, Ermin, and Vuk Đuranović. "[Re] G-Mixup: Graph Data Augmentation for Graph Classification." NeurIPS 2023, https://neurips.cc/virtual/2023/poster/74183.

[3] Zhou, Jiajun, et al. "Data augmentation on graphs: A technical survey." ACM Computing Surveys 57.11 (2025): 1-34.