/10

Poster4 位审稿人

最低3最高4标准差0.4

ICML 2025

Learning Changes in Graphon Attachment Network Models

Xinyuan Fan,Bufan Li,Chenlei Leng,Weichi Wu

OpenReview PDF

提交: 2025-01-22更新: 2025-07-24

摘要

关键词

Graphon attachment networkssubgraph countschange-point detectionpiecewise polynomial signals

评审与讨论

审稿意见

评分: 32025-03-09

This paper introduces the Graphon Attachment Network Models (GAN-M), a new framework for modeling evolving networks by utilizing attachment probabilities inspired by graphon analysis. The authors extend the classical CUSUM method to accommodate graphon-inspired attachment probabilities through the use of subgraph counts, proposing a new statistic called WESUM. The paper claims that WESUM effectively detects structural changes in dynamic networks and provides theoretical guarantees for its performance.

给作者的问题

N/A

论据与证据

Claim 1: GAN-M extends graphon models to dynamic networks.

Evidence 1: The paper clearly outlines the limitations of static graphon models and shows how GAN-M integrates graphon functions with dynamic attachment processes. Additionally, the theoretical formulation provides a generalized approach that unifies both static and dynamic regimes.

Claim 2: WESUM effectively detects change-points in dynamic networks.

Evidence 2: Theoretical derivations establish consistency, and simulation results demonstrate high accuracy.

Claim 3: WESUM outperforms traditional change-point detection methods.

Evidence 3: The paper does not comprehensively compare WESUM against baseline methods beyond the synthetic cases. I recommend evaluations on common benchmarks to improve the experimental analysis.

方法与评估标准

The evaluation metrics used—change-point estimation error, normalized Hausdorff distance, and Averaged Rand Index (ARI)—are well-established in the field and effectively measure the accuracy of change-point detection. However, the evaluation is limited to a small number of simulated datasets, with no experiments conducted on real-world networks.

理论论述

The proofs for consistency and convergence rates are novel and well-structured. However, the assumptions underlying key theoretical claims are not explicitly discussed, making it difficult to assess their generality and practical applicability. For instance, Theorem 3.1 establishes error bounds and detection consistency, but it lacks a clear discussion on the realistic feasibility of its conditions. Clarifying these assumptions and their implications would improve the interpretability of the theoretical results. Adding examples or empirical tests of these assumptions would also improve clarity.

实验设计与分析

The experimental findings seem to confirm the theoretical predictions, but additional experiments with real-world dynamic networks would strengthen the claims.

补充材料

The supplementary material was not reviewed in full.

与现有文献的关系

The change-point detection literature is well-referenced, but the paper lacks citations and references for the use of graphons in other domains.

遗漏的重要参考文献

The paper has a general lack of citations. Specifically, there is a notable absence of references to prior works that integrate graphon theory in (graph) machine learning, despite the growing body of works [1,2,3,4,5,6] -- many recent studies leverage graphon-based representations for tasks such as graph classification, generative modeling, and large-scale network learning, yet none of these are cited or discussed.

Moreover, a broader discussion of related works—especially those addressing learning changes in evolving graphs using deep learning, probabilistic models, or spectral methods—would help clarify how this work improves upon prior research.

[1] Levie et al. A graphon-signal analysis of graph neural networks. NeurIPS 2023.

[2] Finkelshtein et al. Learning on large graphs using intersecting communities. NeurIPS 2024.

[3] Herbst et al. Higher-order graphon neural networks: approximation and cut distance. ICLR 2025.

[4] Ruiz et al. Graphon Neural Networks and the Transferability of Graph Neural Networks. NeurIPS 2021.

[5] Keriven et al. On the universality of graph neural networks on large random graphs. NeurIPS, 2021.

[6] Maskey et al. Generalization analysis of message passing neural networks on large random graphs. NeurIPS, 2022.

其他优缺点

Strengths:

The paper is novel, presenting the first integration of graphons and attachment models.
Despite the limited number of experiments, the empirical validation demonstrates the efficiency and practicality of WESUM.

Weaknesses

The introduction and motivation lacks a compelling real-world justification for why this specific integration of graphon and attachment models is needed. Furthermore, the writing style often seem dense with a short introduction and motivations to new terms—perhaps including an illustrative example would improve accessibility.
The paper does not discuss prior works that incorporate graphon theory into machine learning. It also sparsely discusses alternative approaches for dynamic graph modeling and change detection. Without this context, it is difficult to distinguish the novelty and significance of the proposed method.
The evaluation is restricted to a small number of simulated datasets, with no experiments conducted on real-world networks. This lack of practical validation raises concerns about the applicability of GAN-M and WESUM.
While the theoretical analysis is well-structured, some assumptions (e.g., Theorem 3.1) are not well explained, making it difficult to assess the practical feasibility of the theoretical results. A discussion on when these assumptions hold in real-world settings would enhance the paper’s interpretability.

其他意见或建议

N/A

作者回复

2025-04-01

Thank you for your time and effort in reviewing our manuscript, and for your recognition of our methods and theoretical results. We appreciate your acknowledgment of the novelty of our approach, as well as the effectiveness and practical applicability of our algorithm. Below, we will address the questions you raised.

1.Regarding the benchmarks.

Reply: Thank you for your question. We would kindly point out that we are unable to find a fair method for comparison. This is because the problem addressed in our paper presents the following three challenges: 1. The network size is varying; 2. The networks at different time points exhibit high correlation; 3. At the time points after the change, the network is generated by a mixture of multiple graphon functions. Most existing methods with theoretical guarantees typically require one of the following conditions: 1. The node labels across different time points must match; 2. The network must be generated by a single graphon function; 3. The network sequence must be independent or stationary. As we mentioned in Section 2.2, these methods are not directly applicable to our problem. We will clearly state this in the introduction.

2.Regarding the scale of the experiments and a real data example.

Clarification: Thank you for your question. We have added a larger real data example to demonstrate the effectiveness of our method on real-world data. We kindly refer you to Reviewer pfb1's first question for details. Additionally, we would like to point out that many similar studies in the literature adopted experiments with network sizes in the range of a few hundred, see, for example, [1,2].

3.Regarding the essential references.

Clarification: Thank you for your suggestion. Our paper lies at the intersection of graphon theory, dynamic network and change-point detection, thus, we focus on analyzing and comparing closely related works. As for the general literature on graphon representations used for graph classification, generative modeling, and large-scale network learning, as well as the use of deep learning, probabilistic models for change-point detection, we will provide a brief discussion in the appendix.

4.Regarding the motivation and an illustrative example.

Reply: Thank you for your question. We have added a real data example (see the response to question 2), which helps illustrate the motivation behind our paper and serves as a concrete example.

5.Regarding the discussion on alternative approaches for dynamic graph modeling and change detection.

Reply: Thank you for your question. Due to the vast literature and space limitations, we are unable to cover all the details. However, we will add some review papers to help readers gain a better understanding of the related background.

6.Regarding the discussion on assumptions.

Clarification: Thank you for your question. We kindly point out that we provide some comments after our theorem (see page 7). These assumptions and discussions are standard in the change-point literature (see, e.g., [2]) and are generally accepted (see, for example, Reviewer EyQT’s second paragraph on section "Theoretical Claims": "they are clear in the discussion: condition (6) is essentially a high-level requirement that jump size × sqrt(interval length) exceeds noise, a familiar trope in change detection"). Therefore, we believe that our discussion is generally sufficient.

[1] Peel, L., & Clauset, A. (2015). Detecting change points in the large-scale structure of evolving networks. In Proceedings of the AAAI conference on artificial intelligence (Vol. 29, No. 1).

[2] Wang, D., Yu, Y., & Rinaldo, A. (2021). Optimal change point detection and localization in sparse dynamic networks. The Annals of Statistics, 49(1), 203-232.

审稿意见

评分: 32025-03-13

The authors propose an extension of graphons to model growing networks, where nodes are added over time and each new node forms connections to existing nodes. To this end, the authors define a so-called Graphon Attachment model, where starting from an initial graph new nodes iteratively generate undirected edges to existing nodes with a probability given by a function that depends on uniformly drawn real-valued node features. This model mimics existing uniform or preferential attachment models for growing networks, but allows to modulate attachment probabilities based on a customizable graphon function. The authors use this model to formulate and address the change point detection problem in growing networks. The proposed approach WESUM (which is an extension of CUSUM) is evaluated in a set of four synthetically generated growing networks with artificially introduced change points.

给作者的问题

The proposed model seems to be related to the fitness model proposed by Caldarelli more than 20 years. Here each node is assigned a real-valued fitness score (similar to the values U_i in the proposed model) and the link probability between nodes is calculated based on a symmetric function f(x,y) that takes into account the fitness scores of node pairs x,y. This paper has analytically studied the conditions for the distribution of fitness scores under which scale-free degree distributions (similar to those in the BA model) arise. Similar to the present work, this approach also generalizes a simple random graph model, which corresponds to a constant function f(x,y) that yields a single connection probability p. It would suggest that the authors discuss this in the paper.
Related to the previous point, I can not follow the claim that the proposed graphon model could be used to mimic the preferential attachment rule that is the basis of the BA model. A key aspect of this model is a positive feedback of node degrees, i.e. each node forming a link to a node x will further increase the probability that subsequently added nodes form an edge to x. Since the attachment probability given by the graphon exclusively depends on a real value uniformly drawn at the "birth time" of a node, such a feedback is impossible for the proposed model. The reference to Borgs et al., 2014 does not help to answer this question. Could the authors explain this?
The previous point is crucial since in the introduction the authors state that their framework "unified approach to analyzing networks, addressing both static and dynamic regimes, and opens the door to modeling a broader range of real-world applications, such as evolving citation networks or online social platforms.". In fact, it seems that the proposed graphon attachment model would not be suitable to model any growing network that is influenced by positive feedback of node degrees (which is the case for many real-world network). Please clarify this.
Why is there no comparison to existing methods for change point detection in growing graphs, e.g. those that I mentioned above? Do you address a novel problem that cannot be addressed with any existing technique? If so, you should clearly state this in the introduction.

论据与证据

The authors' strong claims regarding the real-world applicability of the proposed method, e.g. in online social networks or citation networks and its "wide-ranging implications across fields such as epidemiology, finance and the social sciences", are not substantiated by the experimental evaluation, which is limited to small-scale synthetically generated graphs.

方法与评估标准

I am concerned that the paper does not evaluate the proposed method against existing methods for change point detection, which makes it hard to judge its contributions compared to the state-of-the-art. Moreover, theexperimental evaluation is limited to rather small synthetic graphs and there is no analysis in real-world networks.

理论论述

I did not perform a detailed check of the theoretical claims.

实验设计与分析

I checked the soundness of experimental analysis, see my comments below.

补充材料

I checked the supplementary material, specifically the description of the model parameters used in the experimental evaluation.

与现有文献的关系

The paper is broadly related to graphon models, network growth models studied in network science, as well as existing techniques for change point detection in time series (on graphs). Given the broad existing literature in these three areas, I found the reference list rather limited, which is also due to the fact that there is no related work section that works out the research gap addressed by this work. In particular, there are closely related works on modelling growing networks and change point detection in dynamic networks that have not been discussed (see comments below).

遗漏的重要参考文献

The proposed graphon attachment model is closely related to the fitness-based model for scale-free networks that has been proposed in:

G Caldarelli et al: Scale-Free Networks from Varying Vertex Intrinsic Fitness, PRL, 2002

It is crucial that the authors discuss how their paper related to this work. Moreover, other well-known works have previously studied (heuristic) methods to detect change points in general dynamic networks or - more generally - explored topological consequences of different growth models, e.g.

Sun et al.: GraphScope: parameter-free mining of large time-evolving graphs, KDD 2007 Rossi et al.: Modeling dynamic behavior in large evolving graphs, WSDM 2013 L Peel and A Clauset: Detecting change points in the large-scale structure of evolving network, 2014 J Leskovec et al.: Graph evolution: Densification and shrinking diameters, TKDD 2007

The problem and method considered in the present work should be contrasted to those earlier works.

其他优缺点

The theoretical approach to link subgraph count statistics to changes in the graphon function in section 2.1 is interesting and seems to be a contribution of this work.

其他意见或建议

I am a bit puzzled by the guiding question of the paper, which is stated in section 2: "Do structural changes in the function h_{T,t} esult in shifts in the stochastic behavior of G_t and vice versa?". I do not think that this is an interesting research question, since it is h_{T,t} that defines the connection probability in the graph, which thus clearly affects the "stochastic behavior" of the graph. Also, the question how differences in the connection probability function (e.g., in the fitness model, see above) affect the connectivity patterns of growing networks has been studied extensively both analytically as well as experimentally in the network science literature. I would thus recommend to reformulate the guiding research question of the paper.

The authors seem to confuse some terms from the network science literature. They state that GAN-M allows to generate networks with heavy-tail degree distributions that "inherit small-world properties". However, the term small-world networks refers to networks that combine a small diameter or avg. shortest path length with a larger than expected clustering coefficient (see Watts and Strogatz, 1998), which is neither an implication of the heavy-tail degree distribution nor can be reproduced by preferential attachment model.

作者回复

2025-04-01

We sincerely appreciate the time and effort you dedicated to reviewing our manuscript and providing insightful feedback. We are grateful for your recognition of the interest and soundness of our work. In the following, we will address the questions you raised.

1.Regarding the comparison with existing methods.

Clarification: Thank you for your question. We would kindly point out that we are unable to find a fair method for comparison due to our innovative formulation. For more details, we kindly refer you to Reviewer VGrc's first question.

2.Regarding a real data example.

Clarification: Thank you for your question. We have added a larger real data example and we kindly refer you to Reviewer pfb1's first question for details.

3.Regarding the connection to fitness-based models.

Reply: Thank you for your question. After careful examination, we found that the fitness model in G. Caldarelli et al., 2002 shares certain connections with the graphon model in our paper. The key difference lies in that, in the fitness model, the link function can depend not only on the fitness values of nodes $i$ and $j$ but also on additional factors, such as the maximum fitness in the entire network or a threshold related to network size. This additional dependence is what enables the fitness model to generate power-law degree distributions. In contrast, within the graphon framework, power-law degree distributions can be achieved through unbounded graphon functions, as discussed in Borgs et al., 2014. Despite this distinction, the underlying ideas are similar. Meanwhile, we would like to mention that the graphon function can be viewed as a graph limit (Lovász, 2012). This serves as a key reason for grounding our model within graphon theory. In summary, we appreciate your insightful observation and will incorporate a discussion on the connection between our model and the fitness model into the final manuscript.

4.Regarding the essential references.

Reply: Thank you for your suggestion, which enriched the comprehensiveness of our reference. We will add a brief discussion of these papers into our manuscript.

5.Regarding "Do structural changes in the function $h_{T,t}$ result in shifts in the stochastic behavior of $G_t$ and vice versa?".

Clarification: We must kindly point out that your statement - "since it is $h_{T,t}$ that defines the connection probability in the graph, which thus clearly affects the 'stochastic behavior' of the graph" - is not entirely accurate. In fact, there exist cases where $h_{T,t}$ changes, yet the stochastic behavior of the graph remains unchanged. Examples of such cases can be found in Remark 2.2. This is precisely why we define the change-points based on a non-zero cut norm (see also Lovász (2012)), rather than simply setting $h_{T,t} \neq h_{T,t+1}$ . In this paper, our objective is to detect changes in the stochastic behavior of the graph.

6.Regarding "inherit small-world properties".

Reply: Thank you for your question. Considering Watts and Strogatz (1998), we have decided to remove this phrase from the paper to avoid any potential misunderstanding. We appreciate your insightful comment.

7.Regarding the connection to the preferential attachment model and the "positive feedback" mechanism.

Clarification: Thank you for your question. We first kindly clarify that our model is grounded in graphon theory rather than designed to mimic the preferential attachment model. In fact, our model (including the previously mentioned fitness model) is fundamentally different from the preferential attachment model (see also [1]). Our framework is broad enough to encompass standard random graph models (e.g., SBM, RDPG) while also generating networks with power-law degree distributions. The "positive feedback" mechanism is one of many important network mechanisms, but there are also networks that possess characteristics where positive feedback seems inappropriate (see also [2]). While our model has the potential to reflect positive feedback on node degrees (e.g., by introducing dependence between edges), this is beyond our scope and will be a promising future work.

[1] Nguyen, K., & Tran, D. A. (2011). Fitness-based generative models for power-law networks.

[2] Broido, A. D., & Clauset, A. (2019). Scale-free networks are rare.

审稿意见

评分: 32025-03-14

This work proposes a methodology for learning structural changes in these networks over time. Our approach uses graph counts—frequencies of substructures such as triangles and stars—to capture shifts in network topology, called GAN-M.

update after rebuttal

The authors provided two useful examples in their rebuttal. I remain positive on this work and my original review.

给作者的问题

One thing I am missing is what is the final objective of detecting the changes. e.g., fraud detection? What is the formulation of a task where one wants to "automatically" detect changes in the graph? the changes themselves, I assume, are not of interest, but rather whether they are correlated with some label.

论据与证据

Yes

方法与评估标准

It is difficult to evaluate such dynamic approaches within the scope of publicly available large-scale data; therefore, IMHO, the current evaluation is good enough.

理论论述

实验设计与分析

It is difficult to evaluate such dynamic approaches within the scope of publicly available large-scale data; therefore, IMHO, the current evaluation is good enough.

补充材料

与现有文献的关系

The discussed problem or detecting changes in the graph is interesting and connects well to recent literature on dynamic graphs.

遗漏的重要参考文献

其他优缺点

其他意见或建议

作者回复

2025-04-01

Thank you for taking the time and effort to review our manuscript and for providing positive feedback. We appreciate your recognition of the interesting nature of our work. Below, we will address the questions you raised.

1.Regarding the final objective of detecting the changes.

Reply: Thank you for your question. The detection of change-points provides valuable information about the dynamics of the system, which helps make more precise piecewise modeling, retrospective analysis, and other applications. To better reply your question, we first provide two motivating examples, and provide a real data example for further illustration.

The first example is the citation network, where two nodes (papers) are connected when there is a citation relationship between them. It is a growing network that reflects the academic community. A change-point could indicate a shift in the research landscape, which might result from a groundbreaking paper that reshapes the direction of research in a field, or from changes in legislation and regulations affecting the academic community.

Our second example is the email network constructed by connecting two nodes (individuals) if they have exchanged emails. This network represents communication relationships within an institution or a company, and it grows continuously as the number of individuals and emails increases. Detecting jump points in an email network can reveal changes in communication patterns, which may be caused by organizational restructuring, significant events, or the retirement of influential individuals.

In the following, we provide a real data example. The email-Eu-core network data, previously used in [1], was constructed using email data from a large European research institution. The dataset captures all emails between members over a period of 803 days, involving 986 individuals (nodes). In our analysis, individuals are sequentially added to the network based on the time of their first email connection with colleagues. Two individuals are connected in the network if they have an email interaction between them. From this, we can observe that the dataset closely aligns with the proposed model. Both exhibit a growing number of nodes, and incoming nodes have a likelihood of establishing connections with existing ones.

The network exhibits substantial variability in node degrees. Specifically, the maximum degree is 345, the mean degree is 22, and the minimum degree is 1. This highlights the heterogeneous nature of the nodes. For threshold we set $\tau = \max_{j=1,\dots,T-h} \max_{j<t<j+h} |\tilde{X}_{j,j+h}^t(H)| \log(T), h=6\log(T)$ . We kindly refer you to our section 4 for more details regarding choosing the threshold.

We applied our algorithm using subgraph patterns, including line segments, triangles, and rectangles. For subgraph line segments, three change points were detected at nodes 166, 422, and 759. For subgraph triangles, two change points were identified at nodes 432 and 795. Similarly, for rectangles, two change points were detected at nodes 434 and 795. The plots of counted subgraphs, including line segments, triangles, and rectangles, along with the jump point detection results, are presented in the following three figures available at the provided link: https://imgur.com/a/ib3Sx8H.

These plots provide valuable insights into the observed shifts. For triangles and rectangles, the rate of subgraph count growth before the first change point is notably higher than after it. This likely reflects an initial surge in network activity, where frequent interactions and tasks lead to a denser connection structure in the early stages. The second change point, occurring at node 795, marks a significant increase in subgraph counts. This shift may correspond to the entry of a key figure into the network, altering connectivity dynamics and driving the observed structural change.

For line segment subgraphs, the last two detected change points closely align with those identified using triangles and rectangles, demonstrating the robustness of our method to subgraph selection. However, an additional change point is detected at node 166 when using line segments. This provides a more detailed view of early-stage connectivity changes, supporting our claim that subgraphs with fewer nodes can be particularly effective if they capture critical structural shifts.

[1] Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. "Motifs in Temporal Networks." In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, 2017.

审稿意见

评分: 42025-03-17

The authors introduce the Graphon Attachment Network Model (GAN-M), a new theoretical framework for evolving graphs that integrates graphon theory with network growth dynamics. In GAN-M, nodes arrive sequentially and form edges with existing nodes according to a time-dependent graphon function $h_{T,t}(x,y)$ The paper’s theoretical contribution is a change-point detection methodology for GAN-M: it leverages subgraph counts (frequencies of motifs like edges, stars, triangles) as time-series signals to detect structural changes in the underlying graphon. the authors prove that the expected count of any fixed subgraph evolves as a polynomial in time within each phase where the graphon is stati.. the paper also proposes a Weighted CUSUM (WESUM) statistic tailored to handle the polynomial trends and strong temporal dependencies in subgraph count data. Finanly the authors propose an efficient multi-scale detection algorithm to estimate both the number and locations of change-points, with theoretical guarantees on its performance. In summary, the paper provides a strong theoretical paper for modeling dynamically evolving networks via GAN-M, and offers provably consistent methods to learn if and when the underlying graphon function changes over time.

给作者的问题

q1. How sensitive is the change detection performance to the choice of subgraph $H$ ? In particular, could there be a situation where a change in the graphon affects certain motifs but not others q2. The theoretical results assume a threshold $τ$ that depends on unknown model parameters. In practice, how do the authors suggest setting $τ$ ?

论据与证据

The paper’s theoretical claims are well-articulated and generally well-supported by proofs. The central claim is that the proposed WESUM-based procedure can consistently detect change-points in GAN-M. This is shown in Theorem 3.1, which under certain conditions guarantees that with high probability the estimated number of change-points $\hat K$ equals the true number $K$ , and each estimated change time is within a small error $ϵ$ of the truth.

The conditions include a signal-to-noise ratio (SNR) assumption requiring a minimum jump size in the graphon’s subgraph densities and a minimum spacing between changes relative to the time horizon and thus ensuring changes are distinguishable from random fluctuations. These conditions are standard in change-point analysis and are well-justified here given the strong temporal dependencies. The proofs of theoretical results are provided in a detailed appendix, and they appear sound. For instance, the proof of Theorem 3.1 handles the dependency across time by introducing the $T^{,|V(H)|-1/2}$ term in the SNR condition, reflecting the variance inflation due to cumulative network growth. The authors reference established results (e.g. building on techniques from Fan & Wu (2024) and Yu et al. (2022)) to support their argument. I haven't found anys gaps in these proofs.

Also, all key lemmas (such as Lemma 2.5 on the polynomial form of subgraph counts) are stated clearly and proved in the supplementary material. The assumptions made (e.g. piecewise-constant graphon segments, no edge deletions, bounded number of change-points) are reasonable for theory development, though they may restrict applicability slightly (see Weaknesses).

方法与评估标准

The framework is well-poised to the problem of dynamic graphon modeling and change detection. By using graphon theory , the authors describe large random graphs and connect subgraph counts to underlying graphon parameters (homomorphism densities).

I find the use of subgraph counts as summary statistics a smart choice: subgraph frequencies (like edges, wedges, triangles) are sensitive to structural patterns and have known expectations in graphon models, that makes them effective signals for detecting changes in $h_{T,t}$ .

The choice to use a multi-scale interval scanning algorithm (Algorithm 1’s random interval distillation) as the search procedure is also well-motivated. It resembles Wild Binary Segmentation or seeded segmentation techniques designed for detecting multiple changes efficiently. This approach provides a nice way to search for breaks without brute-force checking every time split. The evaluation criteria for success are clearly defined in theory (correct recovery of change-points and bounded localization error) and align with how change-point methods are typically assessed.

理论论述

The paper’s theorems and lemmas appear to be correct and well-proved. Lemma 2.5, is based on a carefu reasoning on the attachment process and seems correct (the result aligns with intuition, since adding $n$ new nodes to a graph should produce subgraph counts that are polynomial in $n$ ). Theorem 3.1 is the main theoretical result, and its statement is plausible and consistent with known results in change-point theory. It effectively gives consistency (no false/missed change-points in the large- $T$ limit) and a convergence rate for localization error. The proof (provided in the appendix) is quite involved but builds on established techniques: it decomposes the problem into showing that with high probability each true change-point will be triggered by the WESUM statistic on some interval, and false alarms are controlled by the threshold choice.

The authors cite and adapt the proof strategy from recent literature (e.g. Fan & Wu, 2024; Yu et al., 2022) to handle the dependencies. I did not find any obvious mathematical errors in the statements. The conditions (i) and (ii) in Theorem 3.1 are a bit complex but they are clear in the discussion: condition (6) is essentially a high-level requirement that jump size × sqrt(interval length) exceeds noise (a familiar trope in change detection)

One minor point is that the theory assumes the number of change-points $K$ is not too large (they mention the case “when $K$ is bounded” in commentary) . This is common in proving consistency, but it would be interesting to know if the result could extend to growing $K$ (e.g. $o(T)$ ) – the paper does not explicitly address that scenario. Another subtlety is the selection of the threshold $τ$ in Algorithm 1: Theorem 3.1 assumes $τ$ falls in a certain range dependent on unknown constants, but in practice one must set $τ$ without knowing $κ_k$ . The authors might rely on theory to choose $τ$ conservatively, but a more data-driven threshold choice could be discussed. Despite these minor considerations, the theoretical claims are solid. All major results are either proved or referenced, and I did not spot any gaps. The appendix appears to contain full proofs (the complete proof of Theorem 3.1 is given, building on Lemma C.1 from a cited source for the random interval coverage argument .

实验设计与分析

The paper includes simulation experiments (Section 4) that empirically validate the theoretical claims. If anything, adding some real-world data or at least a synthetic example with a known ground truth graphon change could further strengthen the paper.

补充材料

The appendix and supplementary materials are thorough. The authors include pseudocode for their algorithms (Algorithms 1 and 2) and detailed descriptions of the simulation settings in Appendix A.

与现有文献的关系

This work lies at the intersection of graph theory (graphons, network models) and statistical change-point detection,

遗漏的重要参考文献

One omission of references is the work by Peel and Clauset (2015) on detecting change-points in the large-scale structure of evolving networks.

其他优缺点

Check my previous comments.

其他意见或建议

It would be valuable if the authors include a brief discussion on choosing the subgraph statistic $H$ .
if possible, the authors should demonstrate the method on a small real dynamic network dataset

作者回复

2025-04-01

We sincerely appreciate your review of our manuscript and your positive evaluation of our work. We are grateful for your recognition of the theoretical contributions of our paper, including your comments and affirmations regarding our theorem conditions, proofs, and underlying ideas. Additionally, we appreciate your acknowledgment of the soundness of our methodology and the validity of our simulation approach, as well as your careful examination and insightful feedback on our proofs. We fully acknowledge and value all these aspects. Furthermore, we thank you for the constructive questions for improvement, and we will discuss them in detail below.

1.Regarding the allowance for the divergence of $K$ .

Clarification: Thank you for your insightful question. When $K$ diverges, our theoretical framework remains valid without any modifications. Our condition (6), which is a signal-to-noise ratio requirement, does not necessitate the boundedness of any term in it; rather, it only requires that the combined terms collectively satisfy the signal-to-noise ratio condition. For instance, in a classical case where change-points are equally spaced and the jump magnitude is bounded away from zero, our framework allows $K$ to diverge at a rate of $T^{1/(|V(H)|+0.5)}$ , up to logarithmic factors. We will incorporate this discussion into the paper to provide a clearer commentary. Thank you again for your valuable insight.

2.Regarding threshold selection challenge.

Reply: Thank you for the opportunity to clarify the challenge of choosing the threshold. As stated in the last paragraph of page 7, our choice was guided by theoretical considerations that hold asymptotically under standard scenarios. Empirically, it has shown satisfactory performance. However, we acknowledge that selecting an appropriate threshold remains an active area of research in change-point detection (e.g., [1,2,3]).

Regarding omission of references

Reply: Thank you for your valuable suggestion. We will add this reference into our manuscript to enhance the comprehensiveness of our bibliography.

4.Regarding the choice of the subgraph statistic $H$ , its sensitivity, and the possibility of different motifs being affected differently by changes.

Reply: From our theory, it is evident that a smaller size for $H$ leads to a better detection bound. Considering that subgraph counts serve as the moments of the network, this selection method also aligns with lower-order principle in moment estimation. Therefore, we recommend using smaller subgraphs, such as line segments or triangles, for change-point detection, which also aligns with the findings in our simulations. Furthermore, we can integrate information from various subgraphs, as described in Remark 3.2.

Regarding sensitivity, after further simulations, we found that when the size of the subgraph $H$ remains the same (although its specific shape may vary), our method exhibits robustness. Moreover, when the size of the subgraph increases, a larger sample size is needed to achieve similar performance, which is also consistent with our theoretical results.

For instance, in Scenario 3 (SBM model), we tried five subgraphs: line segments, triangles, connected triple, rectangles, and closed paths of length 4. It turned out that the results for the triangles and the connected triple are similar, while those for the rectangles and the closed paths of length 4 also exhibit similarity. Additionally, the triangle slightly outperforms the rectangle. We will add these discussions into the appendix of our paper. Thank you for your valuable feedback.

Finally, there are cases where some motifs are affected while others are not. This is a common limitation of statistical methods based on subgraphs (for example, a similar issue occurs in [4]). However, when integrating information from multiple motifs (see Remark 3.2), as long as one of these motifs is affected, our method is capable of detecting the change-point. Therefore, in practice, this limitation can be alleviated. Thank you for your valuable suggestions, which help to improve our paper.

Regarding a real-world data or synthetic example.

Reply: Thank you for your suggestion. We have applied our method to a real dataset. We kindly refer you to our response to the first question of Reviewer pfb1 for details.

[1] Zhao, W., Zhu, X., & Zhu, L. (2023). Detecting multiple change points: The PULSE criterion.

[2] Baranowski, R., Chen, Y., & Fryzlewicz, P. (2019). Narrowest-over-threshold detection of multiple change points and change-point-like features.

[3] Cho, H., & Fryzlewicz, P. (2024). Multiple change point detection under serial dependence: Wild contrast maximisation and gappy Schwarz algorithm.

[4] Shao, M., Xia, D., Zhang, Y., Wu, Q., & Chen, S. (2022). Higher-order accurate two-sample network inference and network hashing.

最终决定Accept (poster)

2025-05-01

All reviewers are positive leaning about this work and believe it makes a strong theoretical contribution in modeling evolving graphs by utilizing techniques from graphon literature and preferential attachment