Learning Changes in Graphon Attachment Network Models
Authors: Xinyuan Fan
Bufan Li
Chenlei Leng
Weichi Wu
Venue: ICML 2025 poster (2025)
Keywords: Graphon attachment networks
subgraph counts
change-point detection
piecewise polynomial signals
Primary area: general_machine_learning->sequential_network_and_time_series_modeling

Abstract: This paper introduces Graphon Attachment Network Models (GAN-M), a novel framework for modeling evolving networks with rich structural dependencies, grounded in graphon theory. GAN-M provides a flexible and interpretable foundation for studying network formation by leveraging graphon functions to define attachment probabilities, thereby combining the strengths of graphons with a temporal perspective. A key contribution of this work is 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. We propose a new statistic designed to learn changes in the resulting piecewise polynomial signals and develop an efficient method for change detection, supported by theoretical guarantees. Numerical experiments demonstrate the effectiveness of our approach across various network settings, highlighting its potential for dynamic network analysis.

Learning Changes in Graphon Attachment Network Models
Xinyuan Fan
Bufan Li'
Chenlei Leng? Weichi Wu
Abstract
properties of graphs. However, traditional graphon models are inherently static, limiting their applicability to dynamic systems where the network structure evolves over time.
This paper introduces Graphon Attachment Net- work Models (GAN-M), a novel framework for modeling evolving networks with rich structural dependencies, grounded in graphon theory. GAN- M provides a flexible and interpretable founda- tion for studying network formation by leveraging graphon functions to define attachment probabili- ties, thereby combining the strengths of graphons with a temporal perspective. A key contribution of this work is methodology for learning struc- tural changes in these networks over time. Our approach uses graph counts- frequencies of sub- structures such as triangles and stars-to capture shifts in network topology. We propose a new statistic designed to learn changes in the resulting piecewise polynomial signals and develop an effi- cient method for change detection, supported by theoretical guarantees. Numerical experiments demonstrate the effectiveness of our approach across various network settings, highlighting its potential for dynamic network analysis.
A defining characteristic of many real-world networks is their dynamic nature, where new nodes are introduced se- quentially over time, leading to a final network with an inherent node registration order. Such networks naturally arise in various contexts, including the World Wide Web, email communication, paper citation networks, and more, where new participants continuously join the system. For a comprehensive survey on dynamic graph models, we refer to Zaki et al. (2016). A widely studied model for describing this attachment process is the preferential attachment model (Barabási & Albert, 1999). In this model, new nodes are more likely connect to existing nodes with higher de- grees, encapsulating the "rich get richer" phenomenon. This mechanism produces networks with degree distributions that follow power laws, making it particularly suitable for modeling certain types of real-world networks. Nonetheless, preferential attachment focuses primarily on degree hetero- geneity and overlooks higher-order structural dependencies or temporal changes in the underlying network properties.
Motivated by the complementary strengths of graphons for characterizing large networks and attachment models for describing growth processes, we propose a novel framework called the Graphon Attachment Network Model (GAN- M). GAN-M models the attachment process using time- evolving graphons, effectively bridging the gap between static graphon theory and dynamic network growth. A defin- ing advantage of this framework lies in flexibility; when the underlying graphon remains constant, the resulting network conforms to a standard graphon model. However, when the graphon evolves over time, the framework introduces structural changes, enabling the modeling of more complex and realistic network dynamics. This capability provides unified approach to analyzing networks, addressing both static and dynamic regimes, and opens the door modeling broader range of real-world applications, such evolving citation networks or online social platforms.
1. Introduction
The learning, understanding, and application of networks have become increasingly crucial with the exponential growth of datasets represented as networks or graphs. The rise of large-scale networks has driven the development of mathematical frameworks for analyzing and interpreting these structures, with graph theory playing a central role (Lovász, 2012). A significant breakthrough in this area the graphon framework-short for "graph functions"-whie provides unified and powerful tool for understanding large networks. This framework is particularly appealing due to its functional characterization of network limits, repre- sented as a bivariate function that captures the asymptotic
'Department of Statistics and Data Science, Tsinghua Uni- versity, Beijing, China DDepartment of Statistics. University of Warwick, Coventry, UK. Correspondence to: Weichi Wu <wuwe- ichi @ waeeaal..tinnt waaillsiinguu.cu..c.....
Building on this foundation, we address the challenge of learning changes the dynamic process of graphons, Change detection in such dynamic models has far-reaching implications for network analysis and has garnered increas-
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Graphon Attachment Network Models
ing attention in recent years. For example, within the pref- erential attachment framework, several studies have inves- tigated change-point detection (Bhamidi et al., 2018; Bet et al., 2023; Kaddouri et al., 2024). Similarly, learning change points in time series of networks has been explored extensively (Lévy-Ledue & Roueff, 2009; Peel & Clauset, 2015; Wang et al., 2021; Zhang et al., 2024; Fan & Wu, 2024). We refer to Aminikhanghahi & Cook (2017); Chen & Chu (2023); Zhou et al. (2024) for reviews change- point detection methods. However, these approaches are largely confined to static networks or rely on assumptions of independence, making them unsuitable for dynamic net- works characterized by cumulative growth and evolving graphon structures. Our work extends these efforts by de- veloping methodologies tailored the GAN-M framework, providing a novel perspective on dynamic networks and their structural evolution.
To overcome these obstacles, we propose a novel extension of the CUSUM framework tailored to polynomial trends in highly dependent data. This statistic, which we term WE- SUM (Weighted Sum), incorporates weights to effectively account for the polynomial nature of subgraph evolution and the dependencies across time points. A key strength of WESUM lies in its robustness to dependence, making it well suited for dynamic network settings.
We provide rigorous theoretical guarantees for WESUM, in- cluding detection bounds and consistency for change-point estimation, and establish rates that highlight its efficiency in dynamic network analysis. Extensive simulation studies validate the effectiveness of our approach, demonstrating its superiority in identifying structural changes in dynamic and evolving networks compared to classical methods. By bridging graphon theory with dynamic network modeling, our work introduces fundamentally new class of change- point detection methodologies, providing powerful tools for understanding and analyzing complex network evolution.
From a methodological perspective, classical change-poin point detection methods such as CUSUM and MOSUM are not directly applicable to our setting due to three fundamen- tal challenges: (i) the adjacency matrices of the networks vary in size at different time points, reflecting the dynamic growth of the network, (ii) all edges in G. persist in Ge for t' 2 f, leading cumulative and irreversible network growth over time, and (iii) At the time points after the first change, the networks are generated by a mixture of mul- tiple graphon functions. These properties fundamentally distinguish our problem from classical change-point point detec- tion tasks, making it difficult to find suitable benchmark methods in simulations, and necessitate new methodologi- cal developments.
The remainder of this paper is structured as follows. Sec- tion 2 outlines the problem setup, providing a detailed de- scription of the graphon attachment network with change- points and its subgraph count properties. In Section 3, we introduce our proposed statistics and present the correspond- ing theoretical results. Section 4 presents the findings from our simulation studies. Section 6 concludes the paper and discusses potential directions for future research. Finally, detailed algorithms, simulation settings, and all technical proofs are provided in the appendix.
Notations: For graph G, let VGG) and E(G) denote its set of nodes and edges, respectively. For a vector x E R. the norm is defined as |||||| = (Ei= x²)) For a set S, |S] denotes the number of elements in S. For a real number x, [x]] represents the smallest integer greater than or equal to xr and [a]] represents the largest integer smaller than or equal to Let I(-) denote the indicator function. For two positive real numbers and b, we write A b = min(a, b) and a V 6 = max(a, b). For two sequences of positive real numbers an and b, we say a, = (bb,) if there exist positive constants N and C such that on an//b, /b, S C for n > N and a, x 6, if an (b,,, and 6, O(,,).
To address these challenges, we focus on subgraph counts, a well-established tool in network analysis (Bickel et al., 2011; Shao et al., 2022). A key conceptual contribution of our work, as established in Lemma 2.6, is that the expected counts of fixed subgraphs in GAN-M evolve as piecewise polynomial functions, where the order of the polynomial is determined by the size of the subgraph. This critical obser- vation reframes the problem of learning structural changes as identifying shifts in the coefficients of piecewise polyno- mial mean function, which represents a significant departure from classical approaches.
However, learning changes in piecewise polynomial trends presents unique challenge: classical CUSUM or MOSUM statistics are designed for mean shifts in independent or weakly dependent data and do not account for the evolving polynomial structure. Moreover, subgraph counts across time points exhibit strong dependencies, as they are in- fluenced by the cumulative growth of the network. This strong dependence invalidates the independence assump- tions underpinning most existing methods, rendering them unsuitable for our context.
2. Problem Setup
We introduce the Graphon Attachment Network Model (GAN-M), which combines the dynamic growth process of networks with the flexibility of graphon- based attach- ment probabilities.
Definition 2.1 (Graphon Attachment Network Model). Let G, denote the graph at time t, with A, as its adjacency matrix, for 1 < t S T. The model begins with an initial simple graph G1 containing m nodes (m 2 1), where each
2

---

Graphon Attachment Network Models
node is assigned a random value U1, U2,.................. ...................... Un ~ 1), drawn independently.
fitness model, the link function can depend not only on the fitness values of nodes i and j but also additional factors, such the maximum fitness in the entire network or a threshold related to the network size. In this paper, we ground our model within graphon theory, as the graphon function can be viewed as a graph limit (Lovász, 2012). Moreover, our GAN-M extends the graphon model two key aspects: (i) the graphon function is allowed to depend T, t; and (ii) GAN-M allows the specification of an initial sample graph G1.
For t >> 1, the graph G2 is formed recursively. Given the values Ui...., Um+e-2 and the adjacency matrix A the adjacency matrix A, is updated by attachment as follows:
Preserve all existing edges: for 1 S i S + t- 2, set A. 1 (i,
Assign (m + t - 1, m + + 1) = 0, ensuring no self-loops for the new node.
A notable strength of the GAN-M lies in its triangular ar- ray structure, which allows ltr, to adapt to the final net- work size T. This adaptability enables GAN-M to gener- ate networks with pronounced degree heterogeneity, where the maximum, average, and minimum node degrees dif- fer substantially. Such heterogeneity reflects real-world network characteristics (Ke & Wang, 2024). For exam- ple. in Scenario of Section A.2, we set hT.,( y) T-006 (xy) 0.9 ^ 1, showcasing the model's ability to pro- duce networks with diverse degree distributions. This versa- tility underscores the model's capacity to represent complex network dynamics and structural diversity.
Draw Um+t-1 (0, 1). independently of all random variables generated in the previous steps.
Form edges between the new node j == m + 1 1 and each existing node (1 S i S m+t 2) independently, with probability:
(i.)) = 1 -)) hrr,(U,
where hT, : 10, + [o, 1] is a symmetric measur- able function defining the attachment probability.
A key innovation in GAN-M is the evolution of the graphon Ior, over time, allowing attachment probabilities to change as the network grows. This raises fundamental question:
Definition 2.1 focuses on undirected simple graphs but can be readily extended to directed graphs with minimal modi- fications. The GAN-M framework models the attachment process such that new edges form only between the new node and existing nodes, reflecting a growth mechanism similar to the preferential attachment model. However, un- like the preferential attachment model, GAN-M incorporates graphon-based based approach, where the symmetric measur- able function lyT,e referred to as a graphon, governs the attachment probabilities. This integration allows GAN-M to capture complex and evolving network structures effec- tively.
Do structural changes in the function Iy. result in shifts in the stochastic behavior of G2 and vice versa?
In real-world networks, such changes often signal shifts in underlying dynamics, such as variations in user behavior, modifications to system policies, or external influences on network growth. Learning and interpreting these changes is crucial for applications such as social network analysis, epidemic modeling, and communication networks, where the nature of connections evolves over time.
The GAN-M framework generalizes several well- established network models, offering significant flexibility. Specifically, when hr, = h for a fixed function h. GAN-M reduces to the traditional graphon network (Lovász, 2012). Furthermore, by setting lyr, = prh, where Pr + O, the model generates a sparse graphon network. Additionally, the model encompasses Lp-graphons as introduced by Borgs et al. (2019; 2018). The flexibility of GAN-M is fur- ther enhanced by allowing the initial graph to be any simple finite graph, enabling the network to evolve from a wide range of starting configurations. This feature accommodates various real-world scenarios by incorporating eriisxxiting structures. A similar approach, where the network starts with a seeded graph, is also employed in the preferential attachment model (Bubeck et al., 2015; Hormozdiari al., 2007).
Thus, we formalize the change detection problem as follows. Assume the existence of time points 1) {No..... 7K4hh J. where 1 = To < 771 < ... < Уı < n = T + 1, at which the graphon functions fr,, un- dergo changes. Specifically, lyr, differs from hy if and only if = 7) for some S k < K. The precise notion of "difference"" between graphon functions is clarified in the following remark.
Remark 2.3 (Identifiability of a graphon). Identifiability issues are inherent in any graphon model. For instance, consider two graphons: hy (z, = xy and fo v) (1 x1 y). Although hı # h2 for almost all (z, 1j. they are "essentially the same" because the ran- dom variables U, and 1 - U, are interchangeable under measure- preserviie transformations. More formally, let & [0, 1] + [0, be a measure- measure-preserring preserving map. and de- fine hi (z. y) = hh (1(((x), ((y)). Then, for every graph H,
Remark 2.2. The fitness model (Caldarelli et al., 2002) shares certain connections with the graphon model. In the
3

---

Graphon Attachment Network Models
the homomorphism densities hom H, hf) and hom hom(H, hy) are identical, where hom H, ha) is the homomorphism den- sity defined in (1) in Section 2.1. Consequently, the two graphons are indistinguishable.
features of the network at time 1. Therefore, it is natural to consider various statistics of the network, and the partie- ular statistic we focus on is the moments of the network, specifically subgraph counts (Bickel et al., 2011).
Following Lovász (2012), we measure the difference be- tween two graphons h1 and h2 using the cut norm:
For a given graphon hr,, and a deterministic simple graph (e.g. H- = A). we define the homomorphism density as:
hom(H, (H, hr = / 10.111001 (jE((H)
60(h1 h2)
II
hr hr,
II dr
/ Jsxr (2, v) - h2(()()), ((V)) da dy
(EV(H) (I)
= inf sup +Ee S.TC(O.1]
where V(H) and E(H) represent the node and edge sets of H. respectively.
where & denotes the set of all invertible meeaure-pprsserving maps. We say that h1 and h2 differ if 61 h2) & O.
Next, suppose that G, is a graphon attachment network at time t (where t Z (VH)). We define the subgraph count of H in G2 as: Σ
Thus, when we state that f differs from hr, we mean that & hT + O.
Remark 2.4 (Networks observed within intervals). In the definition of the GAN-M, we assume that the time stamps of each network Ge are available; however, this may not always be the case in practice. In many real-world scenarios, networks are observed at fixed intervals, with multiple nodes added after each period. In such cases, we can treat these newly added nodes as belonging to the same time step L. We can then reorder these nodes arbitrarily, "unfold" them for analysis, and later "collapse" them back after learning the point of change. This approach is illustrated in Figure 1. Since the localization error in change-point detection cannot be smaller than (1), the theoretical results presented in this paper hold as long as the number of nodes entering the network at each time step (which may vary) remains bounded. We also note that a similar collapsing technique is employed in the preferential attachment model and its asso- ciated branching process; for further details, Garavaglia & van der Hofstad (2018) and Garavaglia et al. (2022).
Nu (G.)=
II
I(p(u)),(()) E E(G.))
(VV WVEE(H)
where op denotes an injective mapping from V(H) to V(G)).
Remark 2.5 (Cut Norm and Homomorphism Density). Sub- graph counts provide a natural and effective approach for learning changes in our model, as they are directly related to the cut norm and homomorphism density (Lovász, 2012, Corollary 10.34 and Lemma 10.32). Specifically, the fol- lowing properties hold:
1. 8-(KT, hr,2) 0 hom(H, hT for every simple graph H.
hom H, hTr1)
2. Let k be positive integer. If for every simple graph H with k nodes, we have hhom(H, hrr,)) hom H, hr;2) I 2-k² then 6n hr S
50
log(k)
The subgraph counts Nu (G.) defined above satisfy the fol- lowing key property, which is essential for the development of our main methodology:
Change-ain
Q-
Lemma 2.6. In the context of this paper, suppose that Tjk S < 11+1 for some 0 S ke S K. Then, we have
E[N,, (G.)]=(ttt = (t-Tk) (t-T)))V(H)
(V)) hom (H, hT ) ( where Q (t) is polynomial of degree (V(H)- -1 in L.
Figure 1. A diagram illustrating the process of the "unfold and collapse" method when multiple nodes enter the network the same time.
This lemma is central to our approach, as it provides a clear and precise approximation for the expected subgraph counts at each time step t, accounting for potential structural changes in the network. The polynomial term Q Q (t) captures the gradual transition in network structure, while the leading term (t - ( (VH)) hom (H, hT directly links the subgraph counts to the change in the graphon function hy, at the change points. This relationship is pivotal learning structural changes in the graph over time.
2.1. Subgraph Counts
Our objective is to learn K, the number of change points, and n, their locations, from the final observation Gy and its adjacency matrix Ar. Intuitively, a change in G2 corre- sponds to a change in AG, which manifests in observable
4

---

Graphon Attachment Network Models
2.2. Why Not CUSUM?
where
CUSUM is a popular method for change-point detection. Let us first review the CUSUM statistic. Consider sample X,,, where E (s,e] is integer indexing the time of
( = Σ (H.. 05 O
(4)
X. To identify a change point within (s, e), the CUSUM procedure constructs a statistic of the form
and the coefficients ( are determined through projection procedure. For clarity, the subscripts for 8, t, and e are omitted in the following:
1 VE
e- X,
Σ r=
X
ak (0, ,,,,0,,11 2",
(e ())
1=
(2) The appeal of the CUSUM procedure lies in its ability to identify& time point E (s, e] such that I. is maxi- mized. Moreover, the method is highly visualizable, making it intuitive and easy to interpret in practical applications.
+ (s ( 1)²
(s + 1)(V(H1
s +
(s (s+2) 2)
(s + 2)
Uo
e
e²
dlvmm
Up = (UK-1, ak 1),
However, the CUSUM method is not applicable in the con- text of this paper. First, the size of G, increases over time, which makes it impossible to directly use the adjacency matrix A, as X, in (2). Secondly, the CUSUM statistic is designed detect changes in piecewise constant signals, while subgraph count (G,) has piecewise polyno- mial expectation. Direct application of CUSUM would lead to failure, as the population version of the statistic at the true change-poing location is no longer maximized. Therefore, it is necessary to develop a new statistic tailored for learning changes in piecewise polynomial signals, while retaining the structure and advantages of the CUSUM framework.
Pv. Un Uk) UK,
Wx (1 - PU.)aa
W # O, we set
WR
(wita(s + 1),". whhh (e))
(5)
VW Wr
otherwise, the vector is set to zero.
To understand the connection between the statistic (3) and the classical CUSUM statistic, we summarize some key properties below, Detailed proof' are provided in the appendix:
3. Learning Changes via WESUM
1. Reduction to CUSUM: When [V()] O, the statis- tic X {,,(H) reduces to the classical CUSUM statistic, which is designed to learn changes in piecewise con- stant signals.
We introduce the WESUM (Weighted SUM) statistic, a novel extension of the classical CUSUM framework, specif- ically designed to address the challenges posed by graphon attachment networks. Unlike standard methods, WESUM utilizes subgraph counts NH (G.) learn structural changes in the dynamic and cumulative growth of networks. By handling issues such as evolving network sizes and strong dependencies, WESUM provides an interpretable and ef- ficient solution, marking a significant advancement in the analysis of time-cvolving graphons.
2. Orthogonality of Coefficients: The coefficients (h satisfy:
Σ (w) =1, r=++1
r Twikk (r) = 0.
r=s+1
for a 5 m S (V These conditions ensure that the coefficients are orthogonal to polynomial trends up to order |V (H),, thereby maintaining the classical CUSUM property.
3.1. WESUM
The construction of WESUM is guided by two key princi- ples. First, the coefficients of weights must be orthogonal to the polynomial vector up to order [V()),, ensuring that polynomial trends are removed. Second, the statistic should attain its maximum at the change point, allowing for precise localization. With these objectives in mind, we define the statistic as follows:
3. Maximum at Change Point: When (s, el contains exactly one change point Me, the population version of the statistic (denoted (H)) satisfies:
i (H) = max P (H), rE(s.))
M(MI Σ K=
ensuring that the statistic highlights the change point, and the location can be precisely localized using arg max in Algorithm in Section A.
X! (1)
(x (H))
2
(3)
5

---

Graphon Attachment Network Models
In summary, the WESUM statistic retains the interpretability and effectiveness of the classical CUSUM procedure, while extending its utility to higher-order trends and complex network structures.
(i) There exists a constant Co > 0 such that
min KA. A AI111)++122 k
2 co
(6)
(ū) The threshold T in Algorithm 1 satis- fies CoTIV(H)-1/3100 1/2 (T)(TT)
3.2. Algorithms
T
C2 ming Kg KgAlv(H))+17) C/TIV( (o (T))
Building on the construction of WESUM, we adapt stan- dard multiple change-poid detection algorithms, originally designed for the CUSUM statistic, by replacing it with our proposed statistic. Specifically, we employ the random in- terval distillation procedure from Fan & Wu (2024), along with the seeded intervals method from Kováes al. (2023), to enhance computational efficiency. Detailed descriptions of these algorithms can be found in Algorithm 1 and Algo- rithm 2, provided in Appendix A.I.
where Co and C1 are sufficiently large positive con- stants.
Under these conditions, the learned K and "n.....,9 ob- tained from Algorithm I and Algorithm 2 satisfy
P K Pk=
= K, max Iskc
1h - -nell= $c) 21-C2T
where
In summary, the proposed change-point detection algorithm proceeds as follows:
TIV(H)--1/2 [ogg(T]
Ir 172
c c=
ming Kik
1. Line 2-12 in Algorithm I; Construct an initial set of in- tervals 1 = {(3m: mm])m= based on seeded intervals.
and C22 C3 > O are constants.
2. Line 13-18 in Algorithm For each interval (sm: em]] E I, compute the maximum value of the statistic, maxr:s.. <tScm 1X........ I. and retain those in- tervals where the computed value exceeds predeter- mined threshold T.
A few comments on this theorem are in order:
1. Signal-to-Noise Ratio Condition:
Equation (6) estab- lishes a signal-to-noise ratio condition, which links the minimal jump magnitude (ming K&)) and spacing (A) to the sample size (T). This ensures that the signal is suf- ficiently distinguishable from noise. Notably, equation (6) does not necessitate the boundedness of any term in it; instead, it only requires that the combined terms collectively satisfy the signal-to-noise ratio condition.
3. Line 19-33 in Algorithm 1: Apply the distillation method from Fan & Wu (2024) to refine the retained intervals, resulting in a set of disjoint intervals S = (lk, r The cardinality |S*| learns the total number of change-points, K.
2. Correlations in Subgraph Counts: Due strong cor- relations between Nur (G.) and Nu (G--1), the term T (H)))112 appears in (6), reflecting the impact of temporal dependencies in the data.
4. Algorithm 2: Expand each interval [d,, ri] to @x), and lear the location of the k-th change-point as 7) arg maxxle<<rrr [X S.
3. Minimal Spacing and Jump Magnitude: When the number of Stange-points (K) is bounded and ming Ki is bounded away from zero, the minimal spacing A can be as small as -1)
The time complexity of Algorithm/ I and Algorithm 2 is O(T log( ensuring that the method is efficient and scal- able for large networks.
log (T).
Conversely, if A x T,, the jump magnitude (ming K&)) can be as small as log(T) These results highlight the flexibility of our method in accommodating varying levels of sparsity and signal strength.
3.3. Theoretical Results
Denote A =
1 - 1 as the minimal spacing between change-points or boundary points. Let Hl be a deterministic finite simple graph, and let τ4 = hom (H, hT..... hom (H, hy. ,)l for < S K denote the jumping magnitude at each change-point. The key theoretical guarantee for the consis- tency of change-point detection and localization is stated in the following theorem:
4. Consistency and Localization Error: The theorem guarantees that, with high probability, the learned num- ber of thange-point (K) equals the true number (K). Additionally, the localization rate e/ A decreases as T increases, satisfying E/A = o(1) by (6). This ensures consistency, a fundamental property in change-poin detection, as discussed in Fan & Wu (2024) and Yu al. (2022).
Theorem 3.1. Assume the following conditions hold:
6

---

Graphon Attachment Network Models
7502000
Triangees
12000
Type
Pspected
5000000
Sampled
0
100 250
300
100 200
350
Figure An illustrative example of the change-point detection procedure. Let 7 = 300 and 17 1 200, with br, y) (x y) for 1 S t S 200, and , y) 1/6 for 201 t S 300. The left panel shows sample network, displaying only induced subgraphs 10k + for k = ...... 29. The middle panel plots the subgraph counts NH((G) for H (triangle) alongside their expected values. Using Algorithm with T /log T' we estimate K and 5 {[87, 225) Finally, applying Algorithm 2, localize the change-point at fj = 202, close to the true value = 200.
0.10
0.05
coefficient
0
coefficient
0.00
0.0
2
-0.05
3
-0.1
-0.10
250
500
750
1000
250
500
750
1000
Figure 3. Plots of wit((r) (r) for 0, e= 1000, and several values of Left figure: t 500; Right figure: 750.
5. Choice of H: From (6), it is evident that a smaller size for H leads to better detection bound. Therefore, we recommend using smaller subgraphs, such as * A. or μ. for change-point detection, which aligns with the findings in simulations.
4. Simulation Studies
In this section, we evaluate the performance of the proposed method through a series of simulation experiments. We use three commonly adopted evaluation metrics from the literature (e.g., Wang et (2021), Wang al. (2020)):
Remark 3.2 (Utilizing multiple subgraphs). A natural ques- tion arises regarding which subgraphs are most suitable for learning changes. While determining the optimal choice of subgraphs may be interesting avenue for further explo- ration, we can instead consider using multiple subgraphs simultaneously, such as H we aggregate the information from these subgraphs by re- taining an interval if the statistic corresponding to at least one of the subgraphs exceeds its pre-specified threshold. This approach enables the simultancous use of different graph structures in the change-point detection process. The subsequent steps of the procedure, including the distilla- tion method (line 19-33 in Algorithm 1) and change-poin localization (Algorithm 2), remain unchanged. It is straight- forward to verify that, under this aggregation subgraphs, Theorem 3.1 still holds, ensuring both consistency and ac- curate localization of change-poing
The difference between the learned and true number of change-poine K K, where K denotes the number of learned change-points and K represents the true number.
A. or H.. In this case,
The normalized Hausdorff distance H n)/T, where H (f) defined as
H(i. n) max
max min x y) max min (x yl xxE yEn
yEa mEn
where a smaller value of H(i, 7T indicates better performance.
The Averaged Rand Index (ARI), as defined by Rand (1971) and Hubert & Arabie (1985), which ranges from

---

Graphon Attachment Network Models
Table 1. Summary of results for Scenarios 1-4.
K
K
Hn,, n/ (x10-
Scenario
Parameter(s)
Subgraph
ARI
<-1
0
2 1
0
92
9.40
0.85
0.75
A
97
8.07
0.86
(With Degree
0
95
4.64
0.92
0.65
Heterogeneity)
A
0
99
5.47
0.90
98
1.93
0.96
0.5
A
99
4.40
0.92
T 200
A
95
9.94
0.87
(Triangle Detection)
400
A
94
7.11
0.88
100
0.26
1.00
(C1, =(0.12, 0.04)
A
95
1.65
0.98
1
90
10
18.81
0.87
(SBM)
100
0.24
1.00
0..14.0.04)
A
100
0.63
0.99
B
97
17.94
0.87
(Ci...., C4)
91
1.58
0.98
= (0.06, 0.02,
A
89
10
2.71
0.97
0.01)
19
6.77
0.92
(RDPG)
97
0.57
0.99
(0.07, 0.02,
A
0
87
13
2.49
0.97
0.05, 0.01)
H
13
85
6.13
0.94
0 to 1. A higher ARI value indicates a more accurate
the convergence rate appears to be slower for larger sub- graphs. Thus, we recommend using the smallest subgraphs, such as triangles, in practical applications. Overall, these findings highlight the effectiveness our method across a wide range of network settings, including dense, sparse, and hegrre-hhteroogneouus networks.
estimation.
For the subgraphs. we choose H = A. or H, as these are commonly used in the literature (e.g., Maugis et al. (2020), Shao et al. (2022)). The threshold chosen based on a data-driven approach inspired by Fan Wu (2024). Specifically, we use
Algorithm
5. A real data example
max max (X] ( log(T); = j=1.... T TccSttt+
The email-Eu-core network data (Paranjape et al., 2017) was constructed using email communications from large European research institution. This dataset captures all email interactions among members over period of 803 days, involving 986 individuals (nodes). In analysis, individuals are added the network sequentially based on the timestamp of their first email interaction with colleagues. Two individuals are connected in the network if they have exchanged emails. The dataset is particularly suitable for the GAN-M model, as it exhibits a growing number of nodes, with incoming nodes having likelihood of establishing connections with existing nodes.
where h = 3 log TJ or ( log T.. When we suspect severe degree heterogeneity, we use [6 log T]: otherwise, we use [3 log T..
Due to space constraints, the specific settings for the four simulations are provided in Appendix A.2. In each simula- tion setting, repeat the experiment 100 times and report the mean values for (f). n)/T, ARI, and the difference K K.
From the results Tables I, we observe that in Scenario 1, as a decreases (i.e., the magnitude of the jump increases), the detection accuracy improves for both
The network exhibits substantial variability in node de- grees. Specifically, the maximum degree is 345, the mean degree is 22, and the minimum degree is 1, high- lighting the heterogeneous nature of the nodes. As recommended in Section 4, we set the threshold as max maxx<r<j=n 1 (HT) log()). with h [6log(T)] We applied our algorithm using
and A. A similar trend is evident in Scenario 2. It is important to note that in Scenario 2, the jump magnitude ming 6j. is generally small, which necessitates sufficiently large sam- ple size for accurate estimation, even when the number of points Shange-pointss larger signal levels enhance estimation accuracy. However,
change-
is known in advance. In Scenarios 3 and 4,
8

---

Graphon Attachment Network Models
1999
de-00
2000
Tharges
3e-00
52003
Type
258834
Type
706
B835 2
0c-00
250
2003
130
1006
The counted subgraphs, along with the change-point detection results, are presented from left to right using line segments. triangles, and rectangles the selected subgraph structures, respectively.
Figure 4.
subgraph patterns, including line segments, triangles, and rectangles. For line segments, three change points were detected at nodes 166, 422, and 759. For triangles, two change points were identified at nodes 432 and 795. Sim- ilarly, for rectangles, two change points were detected at nodes 434 and 795, We visualize the counted subgraphs, including line segments, triangles, and rectangles, along with the change-point detection results in Figure 4.
addressing the long-standing challenge of change-poin point de- tection in dynamic networks.
Our approach underpinned by rigorous theoretical guar- antees, including consistency and convergence rates, which affirm the robustness of the method across range of scenar- ios. Moreover, the performance of our technique is validated through extensive simulation studies, highlighting its supe- rior accuracy and adaptability in diverse network settings.
Figure provides 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 that after it. This likely reflects an initial surge in network ac- tivity, where frequent interactions and tasks lead to 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 key figure into the network, altering connectivity dynamics and driving the observed structural change.
This work opens up several exciting avenues for future re- search. Notably, the extension of our statistic learn abrupt changes in graphons holds great promise for applications in more intricate dependency structures, such as locally sta- tionary processes. Furthermore, the deeper exploration of graphon attachment networks and the development of gen- eralized models for dynamic networks are essential steps toward advancing the field.
Acknowledgments
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 across different subgraph selections. However, an additional change point is detected at node 166, providing a more detailed view of early-stage connectivity changes. This observation supports the notion that subgraphs with fewer nodes can be more effective in capturing structural shifts.
Weichi Wu is supported by NSFC No. 12271287.
Impact Statement
This paper marks the first effort to integrate graphon and attachment models. The introduction of the WESUM statis- tic lays the foundation for future research in dynamic and evolving network modeling and data-driven change detec- tion methods, with wide-ranging implications across fields such as epidemiology, finance, and the social sciences.
6. Summary
In this paper, we introduce the graphon attachment network model, a novel and dynamic extension of traditional static networks. offering a robust framework for modeling and understanding the evolution of complex networks over time. By demonstrating that expected subgraph counts exhibit piecewise polynomial structure, we provide powerful new tool for learning structural changes in evolving networks. Building on this insight, we develop the WESUM statis- tic, novel method specifically designed to learn depen- dent changes in piccewise polynomial signals, effectively
References
Aminikhanghahi, S. and Cook, D. A survey of methods for time series change point detection. Knowledge and Information Systems, 51(2):339-367, 2017.
Bai, T., Wang, L., Yin, D., Sun, K., Chen, Y., Li, W., and Li, D. Deep learning for change detection in remote sensing: a review. Geo-spatial Information Science, 26

---

Graphon Attachment Network Models
(3):262-288, 2023.
De Ryck, T., De Vos, M., and Bertrand, A. Change point detection in time series data using autoencoders with time-invariant representation. IEEE Transactions Signal Processing, 69:3513-3524, 2021.
Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. Science, 286(5439):099-51, 1999.
Bet, G., Bogerd, K., Castro, R. M., and van der Hofstad, R. Detecting a late changepoint in the preferential attach- ment model. arXiv preprint arXiv:2310.02603 2023.
Duan, Y., Liu, J., Chen. S., Chen, L., and Wu, J. G-prompt: Graphon- based prompt tuning for graph classification. Information Processing & Management, 61():103633, 2024.
Bhamidi, S., Jin, J., and Nobel, A. Change point detection in network models: Preferential attachment and long range dependence. The Annals of Applied Probability, 28(1): 35-78, 2018.
Fan, X. and Wu, W. Random interval distillation for detec- tion of change-points in Markov chain Bernoulli networks. arXiv preprint arXiv:2403.00600 2024.
Bickel, P. J., Chen, A., and Levina, E. The method of moments and degree distributions for network models.
Fan, X., Ma, F,, Leng, C., and Wu, W. Low-rank ap-
The Annals of Statistics, 39(5),2280, 2011.
proaches to graphon learning in networks. arXiv preprint arXiv:2501.18755 2025.
Borgs, C. and Chayes, J. Graphons: A nonparametric method to model, estimate, and design algorithms for massive networks. In Proceedings of the 2017 ACM Con- ference on Economics and Computation, pp. 665-672, 2017.
Follain, B., Wang, T. and Samworth, R. J. High- dimensional changepoint estimation with heterogeneous missingness. Journal of the Royal Statistical Society Se- ries B: Statistical Methodology, 84(3):1033-1055, 2022.
Borgs, C., Chayes, J. T., Cohn, H., and Zhao, An 1 theory of sparse graph convergence it: Ld convergence, quotients and right convergence. The Annals of Probability, 46(1): 337-396, 2018.
Gallagher, S. and West, J. Reconceptualizing and expanding the positive feedback network effects model: case study. Journal of Engineering and Technology Management, 26 13):131-14,, 2009.
Borgs, C., Chayes, J., Cohn, H., and Zhao, Y. An 12t theory of sparse graph convergence i: Limits, sparse random graph models, and power law distributions. Transactions of the American Mathematical Society, 372(5):301933062 2019.
Garavaglia, A. and der Hofstad, R. From trees graphs: collapsing continuous-timg branching processes. Journal of Applied Probability, 55(3):900-919, 2018.
Garavaglia, A., Hazra, R. S., van der Hofstad, R., and Ray, Universality of the local limit of preferential attachment models. arXiv preprint arXiv:22 2022.
Bubeck, S., Mossel, E.,, and Ráez, M. Z.. On the influence of the seed graph in the preferential attachment model. IEEE Transactions on Network Science and Engineering, 2(1):30-39, 2015.
Han, X., Jiang, Z.., Liu, N., and Hu, X. G-mixup: Graph data augmentation for graph classification. In Internu- tional Conference on Machine Learning, pp. 8230-8248. PMLR, 2022.
Caldarelli, G., Capocci, A., De Los Rios, P., and Munoz, M. A. Scale-free networks from varying vertex intrinsic fitness. Physical Review Letters, 89(25):258702, 2002.
Hormozdiari, F., Berenbrink, P., Pržulj, N., and Sahinalp, S. C. Not all scale-free networks are born equal: the role the seed graph in PPI network evolution. PLOS Computational Biology, 3(7)ee 18, 2007.
Chan, S. and Airoldi, A consistent histogram estimator for exchangeable graph models. In International Confer- ence on Machine Learning, pp. 208-216. PMLR, 2014.
Chen, H. and Chu, L. Graph-based change-point analysis. Annual Review of Statistics and Application, 10(1): 475-499, 2023.
Hornung, G. and Barkai, N. Noise propagation and signal- ing sensitivity in biological networks: role for positive feedback. PLoS Computational Biology, 4(1):e8, 2008.
Chen, H., Qi, Z., and Shi, Z. Remote sensing image change detection with transformers. IEEE Transactions on Geo- science and Remote Sensing, 60:1-14, 2021.
Hubert, L. and Arabie, P. Comparing partitions. Journal of Classification, 2:193-218, 1985.
Crespi, B. J. Vicious circles: positive feedback in major evolutionary and ecological transitions. Trends in Ecology & Evolution, 19(1)):227 633, 2004.
Jiang, B., Li, J., and Yao, Q. Autoregressive networks.
Journal of Machine Learning Research, 24(227):1-6) 2023.
10

---

Graphon Attachment Network Models
Kaddouri, I., Naulet, Z., and Gassiat, É. On the impos- sibility of detecting late change-point in the prefer- ential attachment random graph model. arXiv preprint arXiv:2407.18685, 2024.
Rand, W. M. Objective criteria for the evaluation of cluster- ing methods. Journal of the American Statistical associa- tion, 666336)88468850, 1971.
Rossi, R. A., Gallagher, B., Neville, J., and Henderson, K. Modeling dynamic behavior in large evolving graphs. In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, pp. 667-676, 2013.
Ke, Z. T. and Wang, J. Optimal network membership esti- mation under severe degree heterogeneity. Journal of the American Statistical Association, pp. 1-15, 2024.
Kovács, S., Bühlmann, P., Li. H., and Munk, A. Seeded binary segmentation: general methodology for fast and optimal changepoint detection. Biometrika, 110(1):249- 256, 2023.
Ruiz, I.,, Chamon, I.., and Ribeiro, A. Graphon neural networks and the transferability of graph neural networks. Advances in Neural Information Processing Systems, 33: 1702-1712, 2020.
Leskovec, J., Kleinberg, J., and Faloutsos, C. Graph evolu- tion: Densification and shrinking diameters. ACM Trans- actions on Knowledge Discovery from Data (TKDD), (1):2-es, 2007.
Ruiz, L., Wang, Z., and Ribeiro, A. Graphon and graph neural network stability. In ICASSP 2021 1021 IEEE In- ternational Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5255-5259, IEEE, 2021.
Lévy-Leduc, C. and Roueff, F. Detection and localization of change-points in high-dimensional network traffic data. The Annals of Applied Statistics, pp. 637-662, 2009.
Shafique, A., Cao, G., Khan, Z., Asad, M., and Aslam, M. Deep learning-based change detection in remote sensing images: A review. Remote Sensing, 14(4):871, 2022.
Li, J., Fearnhead, P., Fryzlewicz, P., and Wang, T. Au- tomatic change-point detection in time series via deep learning. Journal of the Royal Statistical Society Series the
Shao, M., Xia, D., Zhang, Y., Wu, Q., and Chen, S. Higher- order accurate two-sample network inference and network hashing. arXiv preprint 22x.::2288.0777. 2022.
B: Statistical Methodology, 86(2):733-285, 2024.
Lovász, L. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
Sun, J., Faloutsos, C., Papadimitriou, S., and Yu, P.S. Graph- scope: parameter-free mining of large time-evolving graphs. In Proceedings of the 13th ACM SIGKDD Inter- national Conference Knowledge Discovery and Data Mining, pp. 687-696 2007.
Maugis, P.-A., Olhede, S., Priebe, C., and Wolfe, Testing for equivalence of network distribution using subgraph counts. Journal of Computational and Graphical Statis- fics, 293))455-4465 2020.
Truong, C., Oudre, L., and Vayatis, N. Selective review of offline change point detection methods. Signal Process- ing, 167:107299 2020.
Newman, M. E. Clustering and preferential attachment in growing networks. Physical Review E, 64(2)022102, 2001.
Wang. D., Yu, Y., and Rinaldo, A. Univariate mean change point detection: Penalization, cusum and optimality. Elec- tronic Journal of Statistics, 14: 1917-19119,,, 2020.
Padilla, O. H. M., Yu, Y., and Priebe, C. Change point localization in dependent dynamic nonparametric random dot product graphs. The Journal of Machine Learning Research, (011):10661110777 2022.
Wang. D., Yu, Y., and Rinaldo, A. Optimal change point detection and localization in sparse dynamic networks. The Annals of Statistics, 49(1): (011):233222) 2021.
Paranjape, A., Benson, A. R., and Leskovec, J. Motifs in temporal networks. In Proceedings of the Tenth ACM In- ternational Conference on Web Search and Data Mining, pp. 601-610, 2017.
Wu, W. and Zhou, Z. Multiscale jump testing and estimation under complex temporal dynamics. Bernoulli, 30(3): 2372-2398, 2024.
Peel, L. and Clauset, A. Detecting change points in the large-scale structure of evolving networks. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1), Feb. 2015.
Xu, J. Rates of convergence of spectral methods for graphon estimation. In International Conference on Machine Learning, pp. 5-33-543444 5442, 2018.
Poncela, J., Gómez-Gardenes J., Floría, L. M., Sánchez, A., and Moreno, Y. Complex cooperative networks from evolutionary preferential attachment. PLoS One, 3(6): e2449, 2008
Yu, Y., Chatterjee, S., and Xu, H. Localising change points in piecewise polynomials of general degrees. Electronic Journal of Statistics, 16(1):1855-189)) 2022.

---

Graphon Attachment Network Models
Zaki, A., Attia, M., Hegazy, D., and Amin, S. Compre- hensive survey dynamic graph models. International Journal of Advanced Computer Science and Applications, 7(2). 2016.
Zhang, Y., Zhang, Sun, Y., and Wang. J. Change point detection in dynamic networks via regularized tensor de- composition. Journal of Computational and Graphical Statistics, 33(2):515-522 2024.
Zhou, Y., Gao, S., Guo, D., Wei, X., Rokne, J., and Wang, H. A survey of change point detection in dynamic graphs. IEEE Transactions on Knowledge and Data Engineering. 2024.
12

---

Graphon Attachment Network Models
A. Appendix
A.1. Algorithms
Algorithm I takes the subgraph counts (N+(GG) and threshold r as inputs and outputs the learned number of change-points K and set of intervals 5 These intervals are then used to learn the locations of sounge-pointss via Algorithm 2. The algorithm consists of several steps:
In Lines 2-7, utilize the original seeded intervals from Kovács et al. (2023). In Lines 8-12, these intervals are modified by inserting equally spaced points and partitioning them to ensure that each change-point is vell-positioned within an interval, as described in Lemma A.I. This modification is primarily for technical proof purposes. The total length of all intervals in I OT' 7), which ensures that the method is efficient in practice.
(T 11+1-1 πк) represent the minimal spacing between change-points. If A + as T + co, then for any Tkk 1 k S K, there exists interval [s,e] E such that 1h 0.125A < 7nk 0.025 and тl 0.025A
Lemma A.1. Let A mirk- - -1 K-...-11 {1k+11 m A (m
YN 0.125A.
In Lines 13-18, we gather the intervals (sm Cml E S where max;:s.. <t<emm fm contain no coange-points. In Lines 19-33, we select endpoints from S to form new intervals. This step, which does not involve (G.) or is based on the general approach described in Fan & Wu (2024).
> r, aiming to exclude intervals that
To localize the change-points, we take arg max within the slightly lengthened intervals. Intuitively, discussed in Section 3.1, in the population version, we have f2l (H) max; fs (H) when the interval [s,e] contains only one change- point V/-- Thus, taking the arg max in the sample version provides an estimator vi close to Mak- This approach is a natural extension of CUSUM methods.
A.2. Settings of Simulation Studies
Scenario 1: Model with Degree Heterogeneity. We set = 400 and // = 300, and define the graphon function (x, v) as follows:
1 A T 0.6 (xy)
-0 t 300,
(r,
(7)
1A (ATT-06(rr)) 0.9 t 2 300,
where a = 0.75, 0.65, 0.5. This graphon is designed to induce degree heterogeneity in the resulting network. To illustrate
this, we summarize the degree quantiles from sampled network generated by three different graphons: (I) lTT, y) 1 1A --6 0.6 (xy)) -0.9, (II) (r, 3)
(xyy) and (III) mixture of the two graphons, corresponding to a 0.5 in (7), in Table 2. The table shows significant variability in the minimum, maximum, and average degrees, with small subset of nodes displaying exceptionally high degrees. These results demonstrate the presence of degree heterogeneity, feature commonly observed in real-world networks.
Table Quantiles of node degrees in sample network generated under Scenario 1.
Model
T
Min
25%
Quantile
Mean
Median
75%
Quantile
Max
400
17
35
65.81
46
76
378
(I)
1000
31
60
126.03
81
132
999
4000
55
99
240.94
147
242
3999
400
11
22.75
34.07
29
39
169
(II)
1000
35.75
58.93
45
63.25
567
4000
35
63
103.67
76
106
1901
400
24
47
91.82
68
112
399
(III)
1000
55
86.75
182.59
116
204
999
4000
107
161
376.79
220
367
3999
Scenario 2: Triangle Detection. We set T = 200,400, and 1 = 0.87, and define the graphon function (TT y) as
follows:
(0.5+4))(0.5+4)))
(2, y)
17, 1.8
0.1118.
t 17.
13

---

Graphon Attachment Network Models
Algorithm 1 Random Interval Distillation for Piecewise Polynomial Signals
1: Input: (G.)))
2: For 1 5 k [log (T)
let
3: n -2[2(k-))2] 1,
4: L T22k-11/22
5: JR= Rn-1"
T-44,
6: I (0=1(((( [i 1)Jx []]
7: Let I* -Ulg and use the notation 1" {s em) ) Let I Ø.
8: while 1< m MM do
9: Let b = [((44 - i) + m/44], for = 0, 0,,,...,44
Add all intervals (bim, 6 with i < into the set 1.
11: end while
12: Use the notation / = {(mm: Cm mmmm
13: = 2.
14: while 1 S m S M do
15: if max <ldem { smiim
> r then
S= {8m J.
end if
18: end while
19: S -S,ii
20: while | 0 do
21: r. -min(v: 3u, (u, v] E $}.
22: r" = =r;, u = max fu:
23: 5= = [(u,o) E S: (u,)) Ø3.
i=it
25: end while
26: -- = S, i 1.
27: while |$1> > 0 do
28: 1R+11- = max (u: Ee, (u, u] E 5}.
29: u' = 1ootl-i
min (u", v| E $). 30: Š $= v) S v1, (u" v*) & Ø).
31: i=i+l.
32: end while
33: k - r1,,,,
Output: K and S*
Algorithm 2 Localization Procedure
I: Input: {N (G.)) S* from Algorithm
2: i= = K 18* Suppose S = {14,, rx])
3: Let Å = min
letra 14-1- 2
(T 1
^ ( -1)
2
4: while i < K do
5:
14 Á/2], = [r + 4/2
6: f): = arg <igr snees
X1
7: i=i+1
8: end while
9: Output: v = (i..". ... )
In this scenario, we observe that hom(+4 lT,,) remains constant for all t. As result, is not suitable for learning the change point at 77. Instead, we use A to learn the structural change in this case.
Scenario 3: Stochastic Block Model. We set T 450 with change-points at r
0.57, (0.37,0.57.0.87) meaning the
14

---

Graphon Attachment Network Models
change-points unequally spaced. The graphon function (v,,( y) is defined
if 0.37 or
Ci 111
(T v)
C2 + 1.5(z, 0.57 < < elsewhere
where [(x, y) [[xxx] = [3y]). We set the parameter values (Ci, C2) (0.12, and (0.14,0.04)
Scenario 4: Random Dot Product Graph. We set = 450 with change-points at 17 = {0.47, 0.77, 0.9T", indicating unequally spaced change-points. The graphon function (r, y) is defined as:
if < 0.4T or 0.77 S 0.97
Ci Czay,
1r,,(2,))
C2 Casy,
elsewhere.
We set the parameters (C1, C2 C3, C4) (0.06, 0.02, 0.04, 0.01) for the first case, and (C,, C2, C3, C4) (0.07, 0.02, 0.05, 0.01) for the second. It is important to note that the graphs in this scenario sparse.
A.3. Sensitivity
Table 3. Results for sensitivity analysis, Scenarios 3.
K
K
H n//T
Scenario
Parameter(s)
Subgraph
ARI
<
-1
0
>
1
(x (x10-2)
0
100
0
0.26
1.00
A
2
95
3
1.65
0.98
(C1, C2) -0.12,
A
0
100
0.31
1.00
=
H
90
10
18.81
0.87
II
90
19.01
0.87
3 (SBM)
100
0.24
1.00
A
100
0.63
0.99
(0.14.0.04)
A
0
100
0.24
1.00
1
0
97
3
17.94
0.87
II
96
18.76
0.87
To show that algorithm is robust to different choices of subgraphs, we repeat the experiment in Scenario (SBM model) and evaluate five types of subgraphs: line segments, triangles, connected triples, rectangles, and closed paths of length 4. The results indicate that triangles and connected triples yield similar outcomes, while rectangles and closed paths of length 4 also show comparable results. Additionally, triangles slightly outperform rectangles. This suggests that in application of our algorithm, the number of nodes is more significant than the specifie shapes of the subgraphs.
A.4. Additional simulations with larger sizes
To demonstrate that our algorithm can handle large sample sizes, we repeat the experiment in Scenario 3 (SBM model) with a sample size of 7 800. We present the results our algorithm under different threshold choices in Table Recall that the threshold is defined
[X (x3+ (ogg) with h log T..
(8)
j=1 - -hjtttth
We conduct experiments with lo = 4, 5, 6. It turns out that our algorithm performs well.
A.5. Broader literature
In the literature, the graphon model has been widely employed in areas such as graph classification (Han et al., 2022; Duan et al., 2024), graph neural networks (Ruiz et al., 2020: 2021), and large-scale network learning (Chan & Airoldi, 2014; Xu, 2018; Fan al., 2025). In addition, has been used to explain phenomena such the asymptotic normality of subgraph
15

---

Graphon Attachment Network Models
Table 4. Results for larger network sizes with sensitivity analysis, Scenarios 7
800.
K
K
Híi, 7)/T
Scenario
Threshold (see (8)
Parameter(s)
Subgraph
ARI
0
(x10-
(C1, C2)
0
100
0
0.14
1.00
=(0.12, 0.04)
A
0
97
0.32
1.00
k = 4
0
100
0
0.14
1.00
(0.14,0.04)
A
0
98
2
0.22
1.00
(C1, C2)
0
100
0.13
1.00
=00.12,0004 0.04)
A
0
100
0.30
1.00
3 (SBM)
==
100
0.13
1.00
(0.14, 0.04)
A
0
100
0.23
1.00
(C1. C2)
0
100
0
0.15
1.00
=00.12,000 0.04)
4
7
93
0
1.75
0.99
k: =
0
100
0
0.14
1.00
(0.14, 0.04)
4
3
97
0
0.97
0.99
counts (Bickel et al., 2011) and to facilitate hypothesis testing for graph equivalence (Maugis et al., 2020). For overview of the development of its theory, we refer to Lovász (2012); Borgs & Chayes (2017).
For change point detection methods, probabilistic approaches include Jiang et al. (2023); Padilla et al. (2022); Follain et al. (2022); Wu Zhou (2024); Zhang et al. (2024), whereas deep learning-base -baiin approaches include De Ryck et al. (2021), Chen al. (2021); Li al. (2024) and those Shafique et (2022); Bai et al. (2023). We refer Truong et al. (2020); Zhou al. (2024) for a review.
There also works that investigated (heuristic) methods for detecting change points in dynamic networks, explored the topological consequences of various network growth models (e.g.. Leskovec et al. (2007); Sun et al. (2007); Rossi et al. (2013); Peel & Clauset (2015)).
A.6. The "positive feedback" mechanism and potential extensions of GAN-M
The positive feedback associated with node degrees, as suggested by reviewer, is a compelling issue that represents an important mechanism beyond the graphon framework. Positive feedback implies that when node forms a link to an existing node æ, it increases the probability that subsequently added nodes will also form edges to a. Networks exhibiting positive feedback are prevalent 2009). Current research on this topic largely focuses on preferential attachment models, see Newman (2001); Poncela et al. (2008) for a comprehensive review.
variety applications (Crespi, 2004; Hornung & Barkai, 2008; Gallagher West,
Our model has the potential to be extended to incorporate such positive feedback mechanism, and we outline possible implementation:
Remark A.2 (A hybrid model of Graphon Attachment Network and Preferential Attachment). Let G, denote graph at time with A, as its adjacency matrix, for 1 < S T. Let (i) denote the degree the node in Gr i.., de(i) = E, Ac(i, j). The model begins with an initial simple graph G containing m nodes (m 2 1), where each node is assigned random value U1, U2.... ...., Um (0, 1), drawn independently.
For 1, the graph Ge is formed recursively. Given the values U Un+e-2 and the adjacency matrix A,-1, the adjacency matrix A, is updated as follows:
1. Preserve all existing edges: for S i,j < m + + - 2, set Atli,)) At-1(i,j). Assign Ar(m + +/ +1 1)) ensuring no self-loops for the new node.
2. Draw Vm+t-1 Bernoullipp) independently all random variables generated in the previous steps, with p being a pre-specified parameter.
3. If Vm+t-1 = 1: Draw Um+i-1 ~ U(0, 1), independently of all random variables generated in the previous steps. Form edges between the new node j = m + and each existing node (1 S E m + - 2) independently, with
16

---

Graphon Attachment Network Models
probability:
= - hr, (U,,
where hr, [0,1]2 - [0, is symmetric measurable function defining the attachment probability.
4. If - 0: Select node from the existing nodes according to the following rule: the probability of selecting each node is proportional its degree. Form an edge between node and the new node + 1.
The above model a hybrid of the GAN-M and the preferential attachment model, retaining certain characteristics of the latter, which allows the model to incorporate a positive feedback mechanism. We leave further investigation into its dynamic properties and change-point detection for future work.
A.7. Proofs
Proof of Lemma 2.6. Since the size of the initial graph m fixed, we can assume without loss generality that m 1. Additionally, assume without loss of generality that V(G,) = (1,2,..., With a slight abuse of notation, when we refer 11,2 l2 V(G.), we are referring to the indices 1, and time 1,, 12 simultaneously, so 1 V t2 is well-defined. We have
.t).
((N)(GG) U1,".. ;U))
II (:V (G.) WVEE(H)
E
P(c(u)p(v) E E(G)) U1,"".
Σ
II
hwwe Up())
(VV(H)-V(G.) WEE((
Consequently,
((NH(G.))
VVCC))V(CC) (a.jjvE))
E
II
hr (Up(t), Up(T))
II dUp(u)
uE WE E(H)
WEV(H)
IV(DI
Σ
Σ H
II (
(Tpp Up(e))
II uEV(H)
dU p(u).
(9)
V: mm mc=0
Note that
E
I Jo.1Imam
II (TTp(a)vipt)) (Up()) (U(()),Upp()) Up(o))
II wEV(H)
dU p(u)
(H WVEE(H)
Σ
II hTT:(U Up(())
II wEV(H)
dU
=
WHEE(H)
[V(H)|-1
Th m1)
II 10.1ivm (E)
hTmee (Unr Uv) II dU
uEV(H)
Th mn) ]
(H,
(t ma) [V() hom(H, (H, m1) + Q¹ (
where - Similarly, for mg 2 1.
(t) a polynomial order [VH)) with respect to t.
I Jo.juamm
II
(Us) Up(n))
II
dU
(:( Sma =mg = -0(( (t),
MEE (I)
REV(H)
17

---

Graphon Attachment Network Models
where (iv (1) is polynomial of order [V(H) -n with respect to I. Then, by (9), have
B(NH(G,)) = (L (1-1)k) (V() mo + QIv(H))-1((),
where Q(v(H))-1(1) polynomial of order [V( - with respect to t.
Proof of Lemma A.I. We follow the notations in Algorithm 1. Recall that A is the minimal spacing of change-points. By the proof of Theorem C.1 in Kováes et al. (2023), for each 77,, there exists an interval (s fmml E 7 such that sm 2 7 A.
em mh + A. em am 2 A, and
em
7k I
ee
smn)
Thus, we have em 2 7h + and s S 7k
A
Next, consider the of 45 chosen points {bm 0, ...... 44] from (sm= em].
We have
1 = 16
Cm
mm
A
22
for all i * j. Therefore, the subinterval [nx + 0.0255,, 7] +
A contains at least
0.11 +
1 2 points from the set
(1:2 i : 443 for sufficiently large A. Similarly, there is at least point in the set (1/a o,..., .4) that falls into the subinterval [m 0.125 ?] 0.025A].
Thus, there exist D' [7k 0.125A, 7K 0.025A] and by E [nx + 0.025 7 0.125A].
Proof of Theorem 3.1. We divide the proof into two parts. In Step show that
& P ( K), n [b, covers ny and rj 11 s j=1
A
2 21-7-1
where the intervals (g.r, ry] are obtained by Algorithm 1. In Step prove the final result.
J.c Let ftk (H) = I u (r,)) and (H) = v v (FA
Step By Lemma A.6, we have
P(A) 1-7-1
where
A=
X (H) - Fo. (H) 111 Vlo(T
sup s.t.csttee
All the analysis in the rest of this proof is conducted on the event A. For (s, E I, when (s, c| contains no change-poie point, by construction, ft. 0 for all 0 < k < [V(H)), so (2,(()) O. Then, implies
(H) sup Xt (H) CTIV(H)-112 (oo(T) (og(TT.
s<ce
Thus, choosing > CTIV(H) [T) excludes intervals without change-points.
For the change-poie point Me. by Lemma A.1, there exists an interval (s, e] E I in Algorithm 1 such that
0.125A < 8 < 0.0254, TJk + 0.025A < 6 < + 0.125A z
Moreover, by Lemma 2.6, EN (G.) is polynomial function of degree IV [H)) in t, with the leading coefficient given by hom H, lm...) for < t < 1). and by hom(H, H, lTT.o..) for Th < < e. Then, by Lemma A.3, we have
j**(H) (H) 2 col hom(H, (H, hT hom H, by 1 ) (H))+1122
18

---

Graphon Attachment Network Models
where co constant that depends only on [V(H), As result, this interval be retained as long as the event A occurs, and we choose col hom H, bu. hom H, hr - V (T) /lo((T)
The remaining part of this step follows directly from the properties of random interval distillation described in Lines 19-32 of Algorithm 1. A detailed proof can be derived by following the argument presented in Theorem 3.1 of Fan & Wu (2024). Finally, we obtain
k [yrryl covers ni and ry - + 21-T
P [K [k=
PRR-
KJ. n
Step 2. By the arguments in Step 1, for Me, with high probability, we have that [L,, ru] covers Y and ты - 4. S A/4. Following the same argument as Theorem 3.1 of Fan & Wu (2024), there exists an interval (s, e] E such that 77s S T4 S e,
8 E 14 I Tik. |e- - 77: I A/8, and |s 7a I A/8 Thus, we have rkk S Th + A/8 and l 2 T]s A/8. Recall the definition of A in Line 3 of Algorithm 2. By construction, it is straightforward to verify that 72/8 /8 < Å 9 Therefore, we have 8/ 4/2 [/2] E [me 11A/16, тạ 7 16] and ex Lrx Á/2j [m 7A/16, 16, 7/2 116/16].
Assume without loss of generality that ii ny- Similar to the proof of Lemma A.3, let l = IV (V()), and let (a, b) = a T for two vectors and b. Let u....., 21 be the orthogonalized and normalized vectors based on the columns of Un (defined in (5)). Let am = (0, 0, 1T ..... ,.....,e.. (e& b)m) for 8k + < S 6k. and let W be the coefficients from (5) based on an Let wh = w (WW) W m
By construction (5). for any b, the vectors uo u....., u. w wf are mutually orthogonal. Let X,- NH for notational simplicity. Then, for 8& <
<b S ex, we have
(X (o )²= (ilos wpy Os + E(x (sx u,)² 2 + > (xl w
i=0
1=0
where C3 is constant that depends on 8k, Ck. and X (oc++))e is the vector (X slyt, Xo,,) )T By the nature of orthogonal projection, we derive that
(X& Saiek C33 + ||Pv XI (ox 11:ek 11 2= C3 + PI (s 12 C3 11 X 11:b 12 I| 1 (
where V = (uo...., ..., uz, wp- ..... w
1
8k + 1
(sk + 1)2 (sk + 2)²
(8k + 1)²
0
0
0
1
Sk +
(sk 2)
0
0
0
Vi =
1
0
0
0
1
b+1
(b (b+1 1)2
(b + 1)t
1
1'
(ek - b)d
Ck
ek
8k +
(Sk + 1)2
(8k + 1)²
1
12
1
1
3g + 2
(8k + 2)²
(sk + 2)
2
22
V -
:
62
(ek - b)
(ek b)²
(ek b)¹
Since (X 8a,ex
) > ve qh S4.ek
)a by Algorithm 2, we derive that
PP IP
X (( 1| IPP you-au X X 1:el
[|P X ( 112 ||P IPyye--u X 1mm+ +1ez
(10)
Note that span sV?) span(V55-11) (k), and as result, by subtracting the term (recall that assume îi mc).
|P ca- X (sx+1):Aee 112 I| [|Pya- 1aa--a 9e X +1:ma 11 + || Puge fup--y - Xl(me41)eell
19

---

Graphon Attachment Network Models
from both sides of (10), have
vga "n X tin 112 11 in (1i 2 || V ((n 112 Vg2
y2 X (ss- 1))ma 1| 1I 1i (s 112 p1zT -i
(Gw+ 1yop. 112
(1I)
For the right-hand side, recall that assume fis TTk- Moreover, note that EXX is polynomial on (u, e] for all < < Tl implying |x Sp Consequently, (I Pvg-- u11 ut1 Ex 0. This gives
|| VV 1gth - X (02+1))p 1 -111 v2 th 2 X (1 11 Pyge in X (on 11?
|| - 11)mm 11? -1((T 1.th *x ) ()u+1))m 112 10-111111 ||x (0a++)::))
+ I1(T- P Pvou-nn -m | (1) 1|2 -11 11
11 11(T Py Spp )X (1)++)) 11
=-I(4 Vgre - )(X [X) (oot+)n 112 |1(1- -P 117h 1 )(X EX EX (oat))))))
+ II(T Pv PVmu )xX EX) (00x)(0++11))))) 1):mm 1!2
= -I1p Vynu-au (X
11?
|| vgth (X - EX (ea+
- || Pi (X EX (xx)((6+1))
(12)
For |PP 1/
-o (X- - EXX (ox (ox +1): 11 note that with probability greater than 1 1 1
IP 1pPv 2 (X- EE) (su 112 1|V 1i ((V3) ( ) ( (V (k) T (X EX (xx 11?
= =I(( - [on,Tv,""' fix ) 1/2 (
(X- - EX ((x ? 5k) T(
Σ
( [ 11 )0) T - EX (X))((
S ((V)) - log(T")
(13)
where C₁ is a constant, e, lle, ((V2)-*)) Tv ( - T Thus, we have
0, 1, (0....,,11,
....................... T)T and the last inequality follows from Lemma A.7, noting that
for all 1 $ s iill+1 The other two terms in (12) can be handled similarly.
(12) 2 22
(14)
For the left-hand side of (11), by Lemma 6 in (Yu et al., 2022), we have
|| P 1e X X(mn +1)=x1) 1|2 ||P Vg 9 X (00 + 1)
11?
P vo* " X (lm 1|
<
P you EX (the +1)ex 2 + || vg -n EX (1)m 1| + |P Yox vou-ne EX (ne + +1)ex 1|
-11 PPaaa-o (X- EX) (0n 1) 11 + IP vgu
pou-a ne (X - EX (mn +1)m ( 112 + yo d (X- EX) Iom + 1) 112
(15)
Recall that Kg ChommH, hT.mm) hom(H, .)1 for 5 S K. By Proposition 8 in Yu al. (2022), we have
- I|p y. i (xx 1|2 + P| 1
in E. +1 -11 " [EX((n 1|?
2 c [le:
77k 21+1 A Imx - 21+1] c || 1 21+1 A In
7 21-1
(16)
where a is constant that depends only on I. Furthermore, by following the arguments in (13), we have that with probability greater than 1 - C/T.
IP -Ilpyre - (X ((x ||P pama-ou (X - -EX) 1) 1| 1 ||P yye-nu (X EX) 1)oepl 112 < 21 log(T).
(17)
20

---

Graphon Attachment Network Models
Assume for the contradiction that for any constant Cg 0, there exists To N such that for all T >> To.
(TaV log(T) aivhii
i 176 2 Css
(18)
ming K
Then by (18), (16), and (6), have
a [7/16] A 1ix m7/ 11 2 8 (og(())
where e is the constant in (16). This implies that
P ve -i X 10 + 1jonk 1| |PP 1 de X (Ah 1):me 11 ||P Vg un X (n 11
(on++mm) 4 V pg yg in E. (ou 112 + Vg E. (ox +1)mm 112 + || vg " EX (on + +1)0, 1:2
G [174/16]2 2+1 A hh Tk ?/+1]
(19)
where we use the inequalities in (15), (16) and (17). Then by (11), (12), (14), and (19), we have
8C4 T2 log(T).
X 7 21+1
1m Mel m
4
This gives
* [|74/16] 1774/16/2+1 21 1 7M [2+ 8Cac (7a1))1111()))111ogg
Note that 17 - f7al S 144- - mk < A/8 S 74 /6, therefore,
8Ca p (H log (T): x hi 7lu 21+1
C₁
8CC (2( log (T) min& x
21-1
177 - nx 1
The above result contradicts (18). Recall that [H)), and the result follows.
A.8. Lemmas
Lemma A.3. Let f(t), 0 S t T, be a function such that
f(t) Σ
Ooot Σ
at -n) 2 m)
1=0
1=0
where Unj, ai are coefficients satisfying Ont F and | < 11 S T - is a change-point. For an integer i [1,T], let fort EE= k (r) for 0 < k I I, and define för = v ( where the coefficients wh (r) are defined
in (5). Then the following hold:
1. For every Sttt2
ST T, we have fö.r 2 fo.r-
2. For every [ < < T, we have
- 2 aia [1 214 ^ (t - 21]
(2
where a > 0 a constant that depends only on l.
3.
Nr Z V سجة
where A = (T-n) - 7) and at > is constant that depends only on l.
21

---

Graphon Attachment Network Models
Remark A.4. For simplicity, we prove the result for fürr with 0 < s T. but the same result holds for Sae with DSSciSeST,
Proof. Let (a,b) a for vectors and b. Let uo, " ,
denote the orthogonalized and normalized vectors
based the columns of Uo (defined in (5)) with 0,e = T. Let of. (0,... 0, 1 (T' - b)** for 1 S b S T, and let W be the coefficients from (5) based on at. Let w W By the construction in (5), for any b, the vectors uo: " ur w ... w are mutually orthogonal. In the following proof, we use f as a shorthand for the vector T.
W
((),, ... ((())) Note that for any b,
for
U, wfy2
Y=U
Proof the first result: Note that f span uo, u1,"
ut, wg: ... w/) }. Then we have
=
(f. us +
(f, y
(20)
2=0
i=0
11
Σ
(U,u?))
1=0
On the other hand, for + 7, f not necessarily a linear combination of ugg U1," ur, wg: ... w/. Therefore,
1113 2
(f,
1=0
2=0
As result, L x 2 () 2 and the first result follows. Proof of the second result: By (20), we have
(f w Σ (f, (w?? wi)),
(f, = Σ
(f, (w wi),
1=0
(f, (f, Σ (f, (/)()(( (w? wt))
Then
wf) Σ (f, Wff. (w) w
(f, Σ _f wi)
(),u))2 Σ (J.WXX (w wf)-
22

---

Graphon Attachment Network Models
Therefore,
(f0,))² (P0,T))2
E (s, 10
Σ
(S. up?
1=0
1=0
E(,,
(S, u2)
+
Σ
(S. w - Σ
( u
(J, (J, (0))
i=0
-=
i= j=0
Σ (s, wp
Σ
Us w
Σ (f, u;)u
Σ
(s. w
Note that the above quantity is the residual of f projecting onto "o. u1 wy. ... w/, and consequently, onto
NA, .. Wi, ag: ... af- Then for b 2 17 7 1, we have
(8x) - (f
cor" (6,0441 0o -r -2011 5
min
a41441 Σ c((1 TT)
min co.- 4t
(f(1), .f....f(bb)) f(b))
c:(1'
bT)
(21)
By (21), and since 1) 1 1,b b 1 1, apply Proposition 8 in Yu al. (2022) obtain
2
min
(1(), .. ((b) Σ G(1
89)
2 Ea [1 ^ (b - 2])
where & is a constant depending on l. Thus, the result follows.
Proof of the third result: By taking T the second result and noting that forr 0 from (5), the result follows.
Lemma A.5. For & defined in (5), we have for any 0.
(*) - -ENn(G.)) 22 28)=2==00 cmmt expp (0-mmeopp(-mrreaaaaa
P sup
6.l.c.k
Proof. Recall that m is the size of the initial graph. Define Ar(p(u), (())) I(v(u))(() e E(G+)). For the triple (s, e),, we have
wit (n) = Σ (b)((r)
Σ
II I(p(u)p()) E E(G.))
r=st1
P.V(H)-V(G.) uvEE(H)
Σ
II
Ar(p(u),
r=st1
(VV(H)-VVGG) WVEE(H)
where the sum is over the possible assignments of p V(H) + V(G)). Let
(Ar .... AT + 2. + 1))
Σ
wrr((r)
Σ
II
Ar(p(u),<(v)).
r=st1
(.V(H)-V WFEE(H)
23

---

Graphon Attachment Network Models
For u ST + 1, we derive that
2).
Ar(u, v). ...................... Ar (T + m - m --1)) 1))
D0,t,0 ( (T (1,),... Ar (ol, "rrl"".",rrrT"" Ar(T+mm-----
+m 2,7 1))l
1 (r)
Σ
E (I(((1))))) = wv) + +[+((())( =vn)
r=st1
-VV (EE((M)
2
Σ
E I(p(i)()) (u
r=st1
(G.)
[/ Se,
2
r=
2
(whee (r))²
Σ
$ 2e 3/H) I(u S Se.
(22)
Here, we applied the Barchy-Schwarzieee inequality and the fact that 2 = 1. Moreover, we have
T+m 2 T+
2e 3/0
2 I(u se, 4( + m - 1)21v(m)-1
(23)
By combining (22) and (23) and using McDiarmid's inequality, we get for any = > 0,
IP
Σ
a
(N -N,((.)) 2 U,,... Ur) 2exp (- + m 1)2
62
Consequently, we have
E²
P
Σ
with
2:) 2exp
2(T m 1EII(E)--1
P
sup e.t.e.k
Σ
(G.))
2
<2IV(H) + m - 1-)3 exp
-xx
2(T + m 1)
1=s+1
Since m is fixed, the result follows.
Lemma A.6. Recall {1,(11) defined in (3), and let
T Σ
(ENN))) Pa((1)= =
Σ
(1))2
7=841
Then, for some large constant C> 0,
P
sup s.t.eiacte
Et - (H) S 1CT1V(0)111/100" (2 21 21-T"
-
Proof. Let E, = NH((G)) (N.H(.,,, st.k 8tth (H) - Ft.k (HH), and
IV(HI
at (H) =
Σ
( (H)).
k=
24

---

Graphon Attachment Network Models
Thus, Ed Er=st1 (r)) By Lemma A.5, have for any O.
(ND())) - (N+((.)) -BN 26 smm1 (- T22
sup s,t.ech
Note that |x (H) fa.e (H) I E,e (H). Therefore, we have
IVB Σ k=
P sup siriie
X1 ()) fa (H) 20) SP
sup stteeaatee
(E (H)) 2
P
sup
(H)
2 cie
s,1,e,k
C2E² (
2 Cm1 T exp
where C1, C,, Cm are positive constants. Finally, for
C2E²
C exp
ST
(2I
we can choose = CTT (TT for some constant C
Lemma A.7. Suppose that ast1, ast2. ae is a sequence of real numbers such that Er=ot1 a, 1. Then, for any
8 > 0, we have
Σ at (NH( (END)ENN))G)) 22 5C3 ( (-c.rRi())))
P
r=s+1
where C5, Co >> O constants. Consequently, have
P
Σ
2 CCTIV(M--1/2 V1o((T) _
r=s+1
for some constant C7 > O.
Proof. The proof follows directly from the proof of Lemma A.5.
25


Reviews:
[{"review_id": "PEdNkgEHOx", "reviewer": "Reviewer_EyQT", "summary": "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.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n1.**Regarding the allowance for the divergence of $K$.**\n\n**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.\n\n2.**Regarding threshold selection challenge.**\n\n**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]). \n\n3. **Regarding omission of references**\n\n**Reply:** Thank you for your valuable suggestion. We will add this reference into our manuscript to enhance the comprehensiveness of our bibliography.\n\n4.**Regarding the choice of the subgraph statistic $H$, its sensitivity, and the possibility of different motifs being affected differently by changes.**\n\n**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. \n\nRegarding 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. \n\nFor 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.\n\nFinally, 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. \n\n5. **Regarding a real-world data or synthetic example.**\n\n**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.\n\n [1] Zhao, W., Zhu, X., & Zhu, L. (2023). Detecting multiple change points: The PULSE criterion.\n \n [2] Baranowski, R., Chen, Y., & Fryzlewicz, P. (2019). Narrowest-over-threshold detection of multiple change points and change-point-like features.\n \n [3] Cho, H., & Fryzlewicz, P. (2024). Multiple change point detection under serial dependence: Wild contrast maximisation and gappy Schwarz algorithm.\n \n [4] Shao, M., Xia, D., Zhang, Y., Wu, Q., & Chen, S. (2022). Higher-order accurate two-sample network inference and network hashing.", "claims_and_evidence": "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.\n\n 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.\n\nAlso,  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).", "methods_and_evaluation_criteria": "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).\n\nI 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}$. \n\nThe 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.", "theoretical_claims": "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. \n\nThe 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)  \n\nOne 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 .", "experimental_designs_or_analyses": "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.", "relation_to_broader_scientific_literature": "This work lies at the intersection of graph theory (graphons, network models) and statistical change-point detection,", "essential_references_not_discussed": "One omission of references is the work by Peel and Clauset (2015) on detecting change-points in the large-scale structure of evolving networks.", "other_strengths_and_weaknesses": "Check my previous comments.", "other_comments_or_suggestions": "1. It would be valuable if the authors include a brief discussion on choosing the subgraph statistic $H$.\n2. if possible, the authors should demonstrate the method on a small real dynamic network dataset", "questions_for_authors": "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\nq2. The theoretical results assume a threshold $τ$ that depends on unknown model parameters. In practice, how do the authors suggest setting $τ$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uJKp8T7YhP", "reviewer": "Reviewer_pfb1", "summary": "This work proposes a methodology for learning structural changes in these networks over time. Our\napproach uses graph counts—frequencies of substructures such as triangles and stars—to capture\nshifts in network topology, called GAN-M.\n\n## update after rebuttal\n\nThe authors provided two useful examples in their rebuttal. I remain positive on this work and my original review.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n1.**Regarding the final objective of detecting the changes.**\n\n**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.**\n\nThe 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.\n\nOur 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.\n\nIn 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.\n\nThe 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.\n\nWe 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.\n\nThese 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.\n\nFor 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.\n\n[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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "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.", "theoretical_claims": "No", "experimental_designs_or_analyses": "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.", "relation_to_broader_scientific_literature": "The discussed problem or detecting changes in the graph  is interesting and connects well to recent literature on dynamic graphs.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "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.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hI7kbzWDax", "reviewer": "Reviewer_x61N", "summary": "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.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n1.**Regarding the comparison with existing methods.**\n\n**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.\n\n2.**Regarding a real data example.**\n\n**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.\n\n3.**Regarding the connection to fitness-based models.**\n\n**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.\n\n4.**Regarding the essential references.**\n\n**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. \n\n5.**Regarding  \"Do structural changes in the function $h_{T,t}$ result in shifts in the stochastic behavior of $G_t$ and vice versa?\".**\n\n**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.\n\n6.**Regarding \"inherit small-world properties\".**\n\n**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.\n\n7.**Regarding the connection to the preferential attachment model and the \"positive feedback\" mechanism.**\n\n**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.\n\n[1] Nguyen, K., & Tran, D. A. (2011). Fitness-based generative models for power-law networks.\n\n[2] Broido, A. D., & Clauset, A. (2019). Scale-free networks are rare.", "claims_and_evidence": "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.", "methods_and_evaluation_criteria": "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.", "theoretical_claims": "I did not perform a detailed check of the theoretical claims.", "experimental_designs_or_analyses": "I checked the soundness of experimental analysis, see my comments below.", "relation_to_broader_scientific_literature": "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).", "essential_references_not_discussed": "The proposed graphon attachment model is closely related to the fitness-based model for scale-free networks that has been proposed in: \n\nG Caldarelli et al: Scale-Free Networks from Varying Vertex Intrinsic Fitness, PRL, 2002\n\nIt 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. \n\nSun et al.: GraphScope: parameter-free mining of large time-evolving graphs, KDD 2007\nRossi et al.: Modeling dynamic behavior in large evolving graphs, WSDM 2013\nL Peel and A Clauset: Detecting change points in the large-scale structure of evolving network, 2014\nJ Leskovec et al.: Graph evolution: Densification and shrinking diameters, TKDD 2007\n\nThe problem and method considered in the present work should be contrasted to those earlier works.", "other_strengths_and_weaknesses": "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.", "other_comments_or_suggestions": "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.\n\n\n- 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.", "questions_for_authors": "- 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.\n\n- 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?\n\n- 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.\n\n- 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.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0EptpNKUC4", "reviewer": "Reviewer_VGrc", "summary": "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.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n1.**Regarding the benchmarks.**\n\n**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.\n\n2.**Regarding the scale of the experiments and a real data example.**\n\n**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].\n\n3.**Regarding the essential references.**\n\n**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. \n\n4.**Regarding the motivation and an illustrative example.**\n\n**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. \n\n5.**Regarding the discussion on alternative approaches for dynamic graph modeling and change detection.**\n\n**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.\n\n6.**Regarding the discussion on assumptions.**\n\n**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.\n\n[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).\n\n[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.", "claims_and_evidence": "Claim 1: GAN-M extends graphon models to dynamic networks.\n\nEvidence 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.\n\nClaim 2: WESUM effectively detects change-points in dynamic networks.\n\nEvidence 2: Theoretical derivations establish consistency, and simulation results demonstrate high accuracy.\n\nClaim 3: WESUM outperforms traditional change-point detection methods.\n\nEvidence 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.", "methods_and_evaluation_criteria": "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.", "theoretical_claims": "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.", "experimental_designs_or_analyses": "The experimental findings seem to confirm the theoretical predictions, but additional experiments with real-world dynamic networks would strengthen the claims.", "relation_to_broader_scientific_literature": "The change-point detection literature is well-referenced, but the paper lacks citations and references for the use of graphons in other domains.", "essential_references_not_discussed": "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. \n\nMoreover, 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.\n\n[1] Levie et al. A graphon-signal analysis of graph neural networks. NeurIPS 2023.\n\n[2] Finkelshtein et al. Learning on large graphs using intersecting communities. NeurIPS 2024.\n\n[3] Herbst et al. Higher-order graphon neural networks: approximation and cut distance. ICLR 2025.\n\n[4] Ruiz et al. Graphon Neural Networks and the Transferability of Graph Neural Networks. NeurIPS 2021.\n\n[5] Keriven et al. On the universality of graph neural networks on large random graphs. NeurIPS, 2021.\n\n[6] Maskey et al. Generalization analysis of message passing neural networks on large random graphs. NeurIPS, 2022.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is novel, presenting the first integration of graphons and attachment models. \n\n2. Despite the limited number of experiments, the empirical validation demonstrates the efficiency and practicality of WESUM.\n\nWeaknesses\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. 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.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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
Decision: Accept (poster)