Change Point Detection in Dynamic Graphs with Decoder-only Latent Space Model
Authors: Yik Lun Kei
Jialiang Li
Hangjian Li
Yanzhen Chen
OSCAR HERNAN MADRID PADILLA
Venue: Accepted by TMLR ()

Abstract: This manuscript studies the unsupervised change point detection problem in time series of graphs using a decoder-only latent space model. The proposed framework consists of learnable prior distributions for low-dimensional graph representations and of a decoder that bridges the observed graphs and latent representations. The prior distributions of the latent spaces are learned from the observed data as empirical Bayes to assist change point detection. Specifically, the model parameters are estimated via maximum approximate likelihood, with a Group Fused Lasso regularization imposed on the prior parameters. The augmented Lagrangian is solved via Alternating Direction Method of Multipliers, and Langevin Dynamics are recruited for posterior inference. Simulation studies show good performance of the latent space model in supporting change point detection and real data experiments yield change points that align with significant events.

Published in Transactions on Machine Learning Research (04/2025)
Change Point Detection in Dynamic Graphs with Decoder-only Latent Space Model
Yik Lun Kei Deportment of Statistics University of California, Santa Cruz
gket@ucsc.edi
Jialiang Li
jl2356 edu
Department of Computer Science New Jersey Institute of Technology
Hangjian Li Walmart Global Tech
hangjian. hiw.iiiiiii@@ammaarr.mmm
Yanzhen Chen
imyanchen@@sst.hk
Department Information Systems, Business Statisties and Operations Monagement Hong Kong University of Science and Technology
Oscar Hernan Madrid Padilla
uscar.madriddSsta..k uclla edu
Department of Statistics and Data Science University of California, Los Angeles
Reviewed OpenReview: https: openneevw/e.e.veeu.. net/ permformm? id= DVeegV666
Abstract
This manuscript studies the unsupervised change point detection problem in time series of graphs using a decoder-only latent space model. The proposed framework consists of learn- able prior distributions for low-dimensional graph representations and of decoder that bridges the observed graphs and latent representations. The prior distributions of the latent spaces are learned from the observed data empirical Bayes to assist change point detec- tion. Specifically, the model parameters are estimated via maximum approximate likelihood, with a Group Fused Lasso regularization imposed on the prior parameters. The augmented Lagrangian solved via Alternating Direction Method of Multipliers, and Langevin Dy- namics are recruited for posterior inference. Simulation studies show good performance of the latent space model in supporting change point detection and real data experiments yield change points that align with significant. events.
1 Introduction
Networks are often used represent relational phenomena in numerous domains (Dwivedi al. 2021 He et al.] 2023 Han et al., 2023) and relational phenomena by nature progress in time. In recent decades, plethora of dynamic network models has been proposed to analyze the interaction between entities over time, including Temporal Exponential Random Graph Model (Hanneke et al. 2010 Krivitsky & Handcock 2014), Stochastic Actor-Oriented Model (Snijders) 2001 Snijders et al.) 2010). and Relational Event Model Butts 2008 Butts et al.) 2023). Although these interpretable models incorporate the temporal aspect for network analysis, network evolution is usually time-heterogencous. Without taking the structural changes across dynamic networks into account, learning from the time series may lead ambiguity, by confounding the structural patterns before and after change happens. Hence, it is practical for social acientists to first.

---

Published in Transactions on Machine Learning Research (04/2025)
localize the change points in time series, and then study the networks within intervals, where no substantial change dilutes the network effects of interest.
More recently, considerable attention has been directed toward methodologies for change point detection in dynamic networks. Chen et al. (2020a) and Shen annnShen et al. (2023) employed embedding methods to detect both anomalous graphs and vertices in time series of networks. Park & Sohn (2020) combined the multi-linear tensor regression model with a hidden Markov model, detecting changes based on the transition between the hidden states. (Sulem et al. (2023) learned graph similarity function using Siamese graph neural network to differentiate the graphs before and after change point. Zhao et al. (2019) developed screening algorithm that is based on an initial graphon estimation to detect change points. Huang et al. (2020) utilized the singular values of the Laplacian matrices as graph embedding to detect the differences across time. Chen
& Zhang 2015). ). Chu & Chen (2019), and [Song & Chen (2022a) proposed a non- non-parametric approach to
delincate the distributional differences over time. Garreau & Arlot (2018) and [Song & Chen (2022b) exploited the patterns in high dimensions via a kernel- method. Madrid Padilla et al. (2022) identified change
points by estimating the latent. positions of Random Dot Product Graph (RDPG) models and by using a non-parametric version of the CUSUM statistic. Zhang et al. (2024) jointly trained a Variational Graph Auto- Auto-Encoder and Gaussian Mixture Model to detect change points. Chen et al. (2024) and AAhheyya ct al. 2024 considered network evolution in the Euclidean space and showed that the associated spectral estimates can localize the change points in network time series.
Inherently, network structures can be complex due to highly dyadic dependency. Acquiring a low-dimensional representation of a graph can summarize the enormous individual relations to promote downstream analysis
(Hoff et al. 2002 Handeock et al., 2007 Gallagher et al., 2021). In particular, Larroca et al. (2021), Marenco
et al. 2002)] Zhu et al. (2023), Chen et al. [2024), and Athreya et al. (0225 studied different latent space
models for dynamic graphs and focused on using node-level representation to detect changes in dynamic graphs. Furthermore, Sharifnia & Saghaei (2022) and Kei et al. (2023b) proposed to detect changes using an Exponential Random Graph Model (ERGM), which relics on user-specified network statistics to describe the structural patterns a priori. Given the complexity of dynamic network palterns, detecting change points in the data space can be challenging. Extending the framework of representation learning and network statistics, aim to infer the graph-level representations that induce the structural changes in the latent space to support change point detection.
In addition, generative frameworks recently showed promising results in myriad applications, such as text generation with Large Language Model (Devlin et al.] 2018 Lewis et al., 2019) and image generation with Diffusion Model (Ho et al., 2020 Rombach et al. 2022) Different from a graph generation task or network modeling task, we aim to explore how generative frameworks can assist the change point detection task for dynamic graphs. Specifically, (Simonovsky & Komodakis (0188) proposed a Graph Variational Auto-Encoder (VAE) for graph generation, with zero-mean Gaussian prior to regularize the latent space of graph-level
representations. In the VAE framework (Kingma 2013 Kipf & Welling 2016 Lee et al. 2017 Bhattacharyya
ct al. 2018), the regularization via Kullback Leibler (KL.) divergence ariscs from the Evidence Lower Bound (ELBO) for the marginal likelihood, encouraging the approximate posterior to be close to the fixed zero- mean Gaussian prior. Different from the VAE framework which involves an encoder, we focus on learning the mean of the Gaussian prior, with a decoder-only latent space model. In particular, we impose a Group Fused Lasso (GFL) regularization to the sequential differences of the prior parameters, so that the priors learned by minimizing the multivariate total variation can facilitate change point. detection.
To exploit representation learning and generative frameworks for change point detection in dynamic graphs, we make the following contributions in this manuscript:
We develop decoder-only architecture to bridge the observed networks and latent variables for our change point detection method. We assume the graphs are generated from the latent variables that follow Gaussian prior distributions. With the graph decoder, the latent variables are considered as the geveh representations of the observed networks.
The parameters of the Gaussian priors for graph-level representations are learned to facilitate change point detection. Specifically, we apply Group Fused Lasso (GFL.) regularization to promote sparsity
2

---

Published in Transactions on Machine Learning Research (04/2025)
in the sequential differences of the multivariate prior parameters, effectively smoothing out minor fluctuations and highlighting significant change points.
We derive Alternating Direction Method of Multipliers (ADMM) procedure to solve the optimiza- tion problem associated with our method. Without encoder, the model parameters are learned by inferring from the posterior via Langevin Dynamics. Experiments show good performance of the latent space model in supporting change point detection.
The rest of the manuscript is organized as follows. Section 2 specifies the proposed framework. Section 3 presents the objective function with Group Fused Lasso regularization and the ADMM procedure to solve the optimization problem. Section | discusses change points localization and model selection. Section illustrates the proposed method on simulated and real data. Section concludes the work with a discussion on the limitation and potential future developments.
S
2
Latent Space Model for Change Point Detection
2.1 Model Specification
For node set N (1,2, ,n), We denote the set of all possible node pairs as Y = N x N. In the adjacency matrix, Yij = 1 indicates an edge between nodes i and j, while Yıj 0 indicates no edge. The relations can be either undirected or directed. The undirected variant has Yij = Yjs for all (i.j) E W. Denote y' as a network at a discrete time point t. The observed data is a sequence networks y" ..""..
adjacency matrix y E {0, 1]mxa to represent graph network.
For each network y E {0,1)*xm, we assume there latent variable z' Rd such that the network y is generated from the latent variable with the following graph decoder:
y' ~ P(x11²)) II Bernoulli(ff;:ryy( (K.))Y
where r=)(=") = Plylz = 1|2²) the Bernoulli parameter for dyad ply and it is elaborated in Section 2.3 Conditioning on the latent variable z', we assume the network y dyadic independent. We also impose a learnable Gaussian prior to the latent variable
where 2e Rd is the mean vector be learned and Ia is identity matrix. With graph decoder P(y'lz'), consider 2² Rd graph-level representation for y E 10nx, In this work, estimate the prior parameters ( to facilitate change point detection in {T
2.2 Change Points
Anchored on the proposed framework, we specify the change points to be detected, in terms of the prior parameters 2 E Rd for = 1.....T. T. Let {Ct) K+1
k=0 C f1,2...., be a collection of ordered change points
with 1 = Co < Ci < ... < Ck < Ck+1 = such that.
c 11 Cct1
C2t1-1 1: 0, ...., K,
4 Cr + fuCti, k= K......--p.. and 4 CKC+ = Cx
The associated multiple change point detection problem comprises recovering the collection {Ck k=k from sequence of observed networks {v')T=,, where the number of change points K is also unknown. In practice, change point detection problem is often discussed in an unsupervised manner.
In this work, to facilitate change point detection for (y')E in the data space, we turn to learn the prior parameters {n')T the latent space. Intuitively, the consocutive prior parameters μ² and 4 are similar when no change occurs, but they are different when change emerges. For notational simplicity, we denote I E Txd x matrix where the 1-th corresponds to Jr Rdd with / I....,T.
3

---

Published in Transactions on Machine Learning Research (04/2025)
2.3 Choice of Graph Decoder
To facilitate change point detection in dynamic graphs, we choose to use the graph decoder that is standard and common in the literature (Kipf & Welling 2016 Hamilton et al. 2017 Pan et al. 2018 Yang et al, 2019 Chen et al. 2020b; Wang et al. 2021b). Specifically, the graph decoder P(y"Iz") is formulated with a Bernoulli parameter for dyad Vij E {0, as
(zg Plyls = 1|2") - (1(2')) (i,))
The h(-) is parameterized by neural networks with Rd 7 _ and g(-) is the element wise sigmoid function with g R=x* + [0, _|=x". In particular, we use neural networks, transferring the latent variable x' E Rd to U E R and V E R=**, We let the latent dimensions and be smaller than the number of nodes n, and the outputs neural networks are defined as
( E ER",,, for directed network, h(z)) = U E RRx" for undirected network.
Comparing to decoder that directly outputs an n by n matrix, the decoder via matrix multiplication can roduce the number of neural network parameters. While this decoder focuses homophily (the tendency for similar nodes to connect), exlension to consider heterophily (the lendency for dissimilar nodes to
connect) as in Luan et al. (2022), Zhu et al. (2023 Di Francesco et al. (2024). and Luan et al. (2024) is allowed for future development.
Figure gives an overview of the proposed Iramework, where graphs are sampled from latent variables in a top-down manner. Intuitively, the graph decoder can be helpful for learning graph-level representations bottom-up manner, compressing the enormous relations in y extract the structural patterns through node-level representations U and V as an intermediary. The graph decoder (=y''>z") with neural network parameter Φ, is shared across the time points i = I....,T. T. It is also worth pointing out the simplicity of our framework, without the need of encoders.
11 x
1
12122
N(n Ia)
N(u Ia) 4 ------- N( Ia)
N( La
UL V1
U2 V2
U3 V3
UT. VT
1x
Po(v?(=3
Polv"
y
y²
y
y
Figure 1: An overview of prior distributions and graph decoder for time-scrics of networks. The Group Fused Lasso regularization imposed on the sequential differences of prior parameters is elaborated in Section
3 Learning and Inference
3.1 Learning Priors from Dynamic Graphs
Inspired by Vert & Bleakley (2010) and Bleakley & Vert (011)) formulate the change point detection problem as Group Fused Lasso problem (Alaiz et al. 2013). Denote the log-likelihood of the distribution for y ".....g y" as 1(0, 14). We want to solve
T-1
$. fa arg mig - 1(0, 1)) +
|| ++1 - -
(2)
6.

---

Published in Transactions on Machine Learning Research (04/2025)
where À > 0 is a tuning parameter for the Group Fused Lasso penalty term.
The Group Fused Lasso penalty is useful for change point detection because it enforces piecewise constant patterns in the learned parameters, by minimizing the multivariate total variation. Specifically, the regular- ization term, expressed as the sum the le norms, encourages sparsity of the differences μ -4' E R while allowing multiple coordinates across the d dimensional differences change at the same time The latter often referred as grouping effect that could not be achieved with the penalty of the differences. Furthermore, since the regularization is imposed the prior parameters that relate to the likelihood of the data, the learned priors incorporate the structural changes from the observed graphs into the latent space, In summary, by penalizing the sum of soquential differences between the prior parameters, the proposed framework focuses on capluring meaningful structural changes while smoothing out minor variations.
Albeit the proposed framework Section 2 is straightforward, parameter learning is challenging. To solve the optimization problem in (2) that involves latent variables, we need to manipulate the objective function accordingly. We first introduce slack variable RX'x where De E I2 denotes the 1-th row of matrix v, and we rewrite the original problem as constrained optimization problem:
T-1
0 G, A = a min 1(6, 11) + p v21l2
(3)
subject to ==v.
Let w E Txd be the scaled dual variable. The augmented Lagrangian can be expressed as
w)) 11) | w'll +
wll
(4)
where K > 0 is a penalty parameter for the augmentation term.
In practice, gradient descent may not work well for objective function with Group Fused Lasso penalty. To this end, we introduce two more variables (7, B) Rixd (T(x-))xd to ease the optimization, by converting
it into Group Lasso problem Yuaan & Lin 2006). They are defined as
== and Br = 1't 11=1,
Reversely, the slack variable Rxxd can be reconstructed as
= 1T,77 X
where X is T (T - design matrix with X,; = 1 for i j and 0 otherwise. Substituting the v in
14)
with (y, B), the augmented Lagrangian is updated to
K [( u. 7, = 1( 4) + M B b μ 11,17 - X,3 + w|1
K 1
(5)
2
Thus, we can derive the following Alternating Direction Method of Multipliers (ADMM) procedure
Boyd
et al.
2011
Zhu 2017
Wang et al. 2019) to solve the constrained optimization problem in 3
((a+1) ((a+1) arg min 1(6, p1) + ((a) + (
(6)
T-1
B lla + K (11Mat11)
Ma+1): Ma+1))B((+11) B(a+1) = arg min A
w(n
(7)
7.8
t=1
W(a+1) H(a+1) - (((+1) (a),
(8)
where subscript a denotes the current ADMM itcration. We recursively implement the three updates until certain convergence criterion is satisfied. Essentially, ADMM decomposes the optimization problem in into smaller problems, solving each component with specific method derived in Section 3.2

---

Published in Transactions on Machine Learning Research (04/2025)
3.2 Parameters Update
3.2.1
Updating and
In this section, we derive the updates for the prior and graph decoder parameters. The prior parameters are inferred from the observed data as empirical Bayes. Denote the objective function in 6 as C( μ). Setting the gradients of L(Ø. p1) with respoct the prior paramcter p³ Rd zeros, we have the following:
Proposition 1. The solution for μ² at an ileration of our proposed ADMM procedure is weighted sum:
1 + PP(e" 1 (v' w')
between the conditional expectation of the latent variable under the posterior distribution P(= ly") and the difference between the slack and the scaled dual variables. The term w' E R denotes the t-th row of the scaled dual voriable Txx The derivation is provided in Appendir 7.1
Moreover, the gradient of L(Ø, μ) with respect the graph decoder parameter Φ is calculated as
V L(o. 1) = _ Ep(zlv') V log P(y')z'))
(10)
The parameter & can be updated efficiently through back-propagation.
Notably, calculating the solution in (9 and gradient in 110 requires evaluating the conditional expectation under the posterior distribution P(="Ty" x P'y"lz') x P(z"). We employ Langevin Dynamics, a short-run MCMC, to sample from the posterior distribution, approximating the conditional expectations (Xie et al. 2017 2018; Nijkamp al. 2020 Pang et al.) 2020). In particular, let subscript т be the time step of the Langevin Dynamics and let ó be a small step size. Moving toward the gradient of the posterior with respect to the latent variable, the Langevin Dynamics to draw samples from the posterior distribution is achieved by iterating the following:
2 2 + V log P(2'ly')] + V28c
2 + v log (u''''z)) (z) u²] + 28
(11)
where E NOO, Ia) is a random perturbation the process. The derivation provided in Appendix 7.2 Different from the VAE framework where latent variables are obtained through an encoder, we sampled the latent variables from the posterior distributions via Langevin Dynamics.
3.2.2 Updating y and
In this section, we derive the update in 7 which is equivalent to solving Group Lasso problem. The grouping effect allows the d dimensional differences to change at the same time t. With ADMM, the updates on and 3 do not require the observed network data (y'IT By adapting the derivation in Bleakley & Vert (2011), we have the following:
Proposition 2. [Bleakley & Vert, 2011] The Group Lasso problem to update B E (T--)) 1jxd is solved in a block coordinate descent manner, by ileralively applying the following equation to each row t:
Br. RX. XX (1- 1bbl12
- b.
(12)
where (+) max(:; 0) and
b. = -=xXX + w(a)) - -1,117 -x,--181.))
The derivation is provided in Appendia 7.3

---

Published in Transactions on Machine Learning Research (04/2025)
In particular, Sr. E RR becomes 0 when ||6e|22 S X. Also, the convergence of the procedure can be monitored by the Karush-Kuhn-Turce (KKT) conditions:
Be.
x + (a)) 11,17 X,) vBJ. * 0,
B
( + (l(a) 11,17 x S
Ap.. = 0.
Lastly, the minimum in 7 E IR- IRixd is achieved at
7 (1/T)),,, (M(a+1) + ((a) -x
The algorithm for the ADMM procedure is provided in Appendix 7.4 and details about the implementation are provided in Appendix 7.5
4 Change Point Localization and Model Selection
4.1 Change Point Localization
In this section, we provide two effective methods to localize the change points after parameter learning, and they can be used for different purposes. For the first approach, we resort to the prior distribution where x² ~ N(',, Iz). When no change occurs or μ¹ - 1 1- = 0, we have z' - ztt1 ~N 2Ig) and
(=' - 2' = 2 Xa.
Furthermore, the mean of over m samples follows a Gamma distribution:
- = md 2
T r mm 5
where 0 and & are the respective scale and shape parameters.
As we capture the structural changes in the latent space, we can draw samples from the learned priors reflect the sequential changes. In particular, for time point t, we sample 2 - -t-1 from N f,'-1,20 2Ia). and we perform the same transformation:
-
2 (2' 2'-1- 2
Then we compare the mean of of over m samples with quantile:
PP qthr)
(13)
T-1
where Ythr is the 1 - a/(T 1) quantile of the Gamma distribution for Th, when no change occurs. We consider the time point with oth Ath as the detected change point.
For the second approach, robust in practice, compared in the simulation study of Section 5.1
directly utilize the localizing method from Kei et al. 2023b which is more
F First, we calculate the differences
between consecutive time points in fa E TTxx xd as
Ap l 1 112
ViE [2,))
Then standardize the differences
Ap' median Ape
tt [2,T]
(14)
Std(Ap)
and construct a data-driven threshold defined as
Tehr mean AC) Z,, x std(ac)
(15)

---

Published in Transactions on Machine Learning Research (04/2025)
where 2y is the 9% quantile of the standard Gaussian distribution N/ 1). We declare change point C₁ when A > Tthr-
The data-driven threshold in 15 is intuitive, the standardized differences AC between two consecutive change points are close to zeros, while the differences that are at the change points are substantially greater than zeros. When traced in a plot over time t, the AC can exhibit the magnitude of structural changes, and the threshold that deviates from the mean provides a reasonable cut-off value for the standardized differences, as demonstrated Figures [T and [2] In summary, the localizing method derived from the prior distribution has statistical justification, while the localizing method with the data-driven threshold is more robust for different types of network data practice.
4.2 Model Selection
The optimization problem in 33 involves a tuning parameter that can yield different sets detected change points when is varied. In this work, we use Cross- Validation to select X. In particular, we split the original time series of graphs into training and testing sets: the training set consists of graphs at odd indexed time points and the testing set consists of graphs even indexed time points. Fixed learn the model parameters with the training set, and we evaluate the learned model with the testing set.
specific À value, we
For list of À values, we choose the À giving the maximal log-likelihood on the testing set. Note that the log- likellildd is approximated by Monte Carlo samples { drawn from the prior distribution P(z') as
T log P(y') =
Σ
Σ log Σ 1=1
II Po(0l1=0))
(t.f)EY
Further computational details are discussed Appendix 7.5 With the selected value, we learn the model parameters again with the full data, resulting the final set of detected change points.
5
Simulated and Real Data Experiments
5.1 Simulation Study
In this section, we implement the proposed method on simulated data. To evaluate the performance of change point detection, use three standard metrics in the literature that focus the number of change points, the time gap between the true and detected change points, and the coverage over the segmented time intervals. The first metric is the absolute error I - K| where Y and K are the respective numbers of the detected and true change points. The second metric described in Madrid Padilla et al. (2021) is the one-sided Hausdorff distance, which is defined as
d((ic) = max min |2 -
cEC REč
where è and C are the respective sets of detected and true change points. Also, report the reversed one-sided Hausdorff distance d(ClC). By convention, when Č 0, let d(cle) co and d(C(C) -co. The last metric described in van den Burg & Williams (0200) is the coverage of partition G by another partition G', which is defined as
LAnA A'
C(G,9'
= IAI
[A|
max A'eg'
A
Aeg
with A,A' C [1,2]. The 9 and g' are collections of intervals between consecutive change points for the respective ground truth and detected results.
We simulate dynamic graphs from thrce scenarios to compare the performance of the proposed and competitor methods: Separable Temporal Exponential Random Graph Model, Stochastic Block Model, and Recurrent Neural Networks. For each scenario with different numbers of nodes (50, 100), simulate 10 Monte
8

---

Published in Transactions on Machine Learning Research (04/2025)
Carlo trials of directed networks with time span T = 100. The true change points are located at t 51, 76), so the number of change points K = 3. Moreover, the K + = 4 intervals in the partition 9 are {51,..., 75), and A₁ = {76,... ,003. In each specification, we report the mcans and standard deviations over 10 Monte Carlo trials for the evaluation metrics. CPDlatenty denotes our proposed approach with the data-driven threshold in 15 using 90% quantile from slandard Normal distribution. We let the latent dimensions d = 10 and = 5 for the graph decoder. CPDlatente denotes our proposed approach with the localizing method in (13), using a 0.01 from Gamma distribution. We let the latent dimensions d = n/ 10 and k = 10 for the graph decoder. The mumber of samples drawn from the Gamma distribution is m = 1000 when d = 5 and m = 500 when d = 10.
A = (1.... 25],,..,,,,...... A2 = (,6,...,50), 50}, A3
Five competitors, gSeg (Chen & Zhang 2015 kerSeg (Song & Chen 2022b), CPDrdpg (Madrid Padilla et al. 2022), CPDnbs (Wang et al., 2021a), and CPDstergm (Kei et al.) 2023b). are provided for comparison. The gSeg method utilizes a graph- scan statistics and the kerSeg method employs a kernel-based framework to test the partition before and after a potential change point. The CPDrdpg method detects change points by estimating the latent positions from a RDPG model and by constructing a non-parametric CUSUM statistic that allows for temporal dependence. The CPDnbs method detects change points by combining sample splitting with wild binary segmentation (WBS) and by maximizing the inner product of two CUSUM statistics computed from the samples. The CPDstergm method fits a STERGM with user-specified network statistics to detect change points based on the total variation of estimated parameters.
For CPDstergm, we first use two network statistics, edge count and mutuality, in both formation and dissolution models to let p 4. We then add one more network statistic, number of triangles, to let p = 6 another specification. For CPDrdpg, we let the number of intervals for WBS be W = 50, and the number of leading singular values of an adjacency matrix in the scaled PCA algorithm be d = 5. For CPDnbs, we let the number of intervals for WBS be W = 15 and we set the threshold to the order of n (T)). For kerSeg, we use the approximated p-value of fGKCP1, and we set a = 0.001. For gSeg, we use the minimum spanning tree to construct the similarity graph, with the approximated p-value of the original edge count scan statistic, and we set a= 0.05. Moreover, as gSeg and kerSeg are general meth for change point detection, we use networks (nets.) and network statistics (stats.) as two types of input data. Throughout the paper, we choose these scttings because they produce good performance average for the competitors. Changing these settings enhance their performance some specifications, while severely jeopardizing their performance on other specifications.
let
Scenario 1: Separable Temporal Exponential Random Graph Model
In this scenario, apply time homogeneess Separable Temporal Exponential Random Graph Model (STERGM) between change points to simulate sequences of dynamic networks (Krivitsky & Handcock, 2014). We use three network statistics, edge count, mutuality, and number of triangles, in both formation (F) and dissolution (D) models. The = 6 parameters for each time point are
2, 2, 2, 2, 1,
UUA
0z. 03
1.5, 1, 11, 2, 1, 15, tE Au
Figure 2 exhibits examples of simulated networks. Visually, STERGM produces adjacency matrices that are sparse, which is often the case in real world social networks.
Table 1 displays the means and standard deviations of the evaluation metrics for comparison. Since the dynamic networks are directly sampled from STERGM, the CPDstergm method with correctly specified network statistics (p = 6) achieves the best performance, in terms of greater converge of time intervals. However, when the network statistics are mis-specified with p = 4, the performance of CPDstergm is sub- stantially worsened, with greater time gaps between the true and detected change points. The deteriorating performance of CPDstergm emphasizes the importance of graph-level fealures in change point detection. Similarly, while the CPDrdpg method detects the correct mumbers of change points on average, the time gaps between the true and detected change points are large. Similarly, the detected change points from the CPDnbs method also have greater time gaps. Moreover, using either networks (nets.) or network statistics (stats.) cannot. improve the performance of gSeg and kerSeg methods. The binary segmentation approach
9

---

Published in Transactions on Machine Learning Research (04/2025)
100
34 67 100
34
100
34
67
100
67
100
100 34
100
Figure 2: Examples of networks simulated from STERGM with number of nodes 100. The edge density is approximately 15% for each network. In the first row, from left to right, each plot corresponds to the network at t = 25, 50, 75 respectively. In the second row, from left to right, each plot corresponds to the network at = 26, 51, 76 respectively (the change points).
tends detect excessive numbers of change points, capturing noises from the data. In this sccnario, although the CPDstergm method with p 6 achieves the best performance, the true network statisties usually not known the modeler a priori. Our CPDlatent method, without the need of specifying network statistics, can achieve good performance on average.
Scenario Stochastic Block Model
In this scenario, we use Stochastic Block Model (SBM) to simulate sequences of dynamic networks, and we impose time-dependent mechanism in the simulation process as in Madrid Padilla al. (022). Two probability matrices P, P,Q+ E [0, 1|nXn are constructed and they defined as
0.5, i le [3], and Qú
S0.45, i,j B, le [3]. 0.2,
Púj
0.3, otherwise,
otherwise,
where B1, B2, B3 are evenly sized clustors that form a partition of (1....,n).. Then a sequence of matrices E' E [0, 1|ax are arranged for (. = ,,...,7 such that
E = [Pay LE AE Us,
[Qi.. tE A4
Lastly, the networks are simulated with 0.5 as the time-dependent mechanism. For 1 = 1,..., let flg ~ Bernoulliç Ely) and
T T 1, we
Bernoulli(pf + E V 1, (amnoulli(11p@aaa11
y = 0.
With p > 0, the probability to form an edge for i.j becomes greater time t when there exists an edge at time 1, and the probability becomes smaller when there does not exist edge time t. Figure TigureBexhine exhibits
10

---

Published in Transactions on Machine Learning Research (04/2025)
Table 1: Means (standard deviations) of evaluation metrics for dynamic graphs simulated from STERGM. The best coverage metric bolded.
Method
- K|
d(Clc) +
a(cic) 4
C(),9')
CPDlatent
0.1 (0.3)
4.3 (5.7)
2.6 (1.3)
90.87%
CPDlatent
0.4 (0.6)
4.2 (6.9)
3.4 (3.4)
90.97%
CPDrdpg
0.9 (1.6)
8.7 (9.5)
8.5 (6.0)
76.27%
CPDnbs
1.2 (0.6)
4.6 (3.9)
11.0 (0.9)
75.80%
CPDstergmp
1.5 (0.8)
11.7 (7.5)
10.5 (2.3)
67.68%
50
CPDstergm
0.2 (0.4)
1.6 (1.2)
3 (3.5)
91.54%
gSeg (nets.)
12.3 (0.5)
0 (0.0)
19 (0.0)
27.90%
gSeg (stats.)
15.8 (0.7)
1.5 (0.5)
20.1 (0.3)
24.55%
kerSeg (nets.)
9.7 (0.9)
1.4 (0.9)
17.9 (1.2)
37.62%
kerSeg (stats.)
9.4 (0.7)
3.9 (1.3)
18 (1.8)
35.86%
CPDlatentN
(0.0)
3.9 (1.3)
3.9 (1.3)
91.33%
CPDlatente
0.7 (1.3)
3.1 (1.3)
6.0 (4.0)
88.55%
CPDrdpg
0.8 (1.0)
4.5 (2.0)
8.2 (4.7)
80.54%
CPDnbs
1.4 (0.5)
4.9 (3.7)
11.0 (0.9)
72.99%
CPDstergm
0.7 (0.6)
21.9 (10.3)
7.6 (4.3)
67.21
100
CPDstergm
0 (0.0)
1.1 (0.3)
1.1 (0.3)
94.01%
gSeg (nets.)
12 (0.0)
(0.0)
19 (0.0)
28.00%
gSeg (stats.)
14.5 (2.3)
3.3 (3.6)
20.2 (0.4)
26.13%
kerSeg (nets.)
9.3 (0.8)
10.0)
17.7 (0.6)
37.62%
kerSeg (stats.)
8.5 (0.8)
4.5 (1.4)
17.3 (1.7)
36.92%
100
100
67
34
100
100
34
100
100
34
67
100
67
34
100
Figure 3: Examples of networks simulated from SBM with number of nodes 100. The edge density is approximately 30% for each network. In the first row, from left to right, cach plot corresponds to the network at 1 -25, 50, 75 respectively. In the second row, from left to right, each plot corresponds to the network at = 21, 76 respectively (the change points).
11

---

Published in Transactions on Machine Learning Research (04/2025)
examples of simulated networks. Visually, SBM produces adjacency matrices with block structures, where mutuality serves important pattern for the homophily within communities.
Table 2 displays the means and standard deviations of the evaluation metrics for comparison. As expected, both CPDstergm methods with = and p p= 6 that utilize mutuality as a network statistic for detection achieve good performance, in terms of greater converge of time intervals. The CPDrdpg method also produce relatively good performance, but the time gaps between the true and detected change points are large. Similarly, the CPDnbs method also produces change points that have greater time gaps from the ground truth. Furthermore, using network statistics (stats.) with mutuality included for both gSeg and kerSeg methods improve their performance substantially, comparing to using networks (nets.) as input for detection. This again emphasizes the significance of using graph-level representation in change point detection for dynamic networks. Lastly, our CPDlatent method, which infers the features in the latent space that induce the structural changes, achieves the best performance this scenario.
Table 2: Means (standard deviations) of evaluation metrics for dynamic networks simulated from SBM. The best coverage metrie is bolded.
n
Method
K K| 4
d(cic)
d(ciC) 4
C(G,9') 1
CPDlatenty
0 (0.0)
0.1 (0.3)
0.1 (0.3)
99.80%
CPDlatenta
0.3 (0.6)
0.1 (0.3)
3.1 (6.2)
96.70%
CPDrdps
1.4 (1.8)
2.2 (1.2)
8.2 (6.0)
81.01%
CPDnbs
1.6 (0.5)
3.8 (3.6)
11.4 (1.2)
73.13%
CPDstergmp=4
0.1
(0.0)
2.4 (4.2)
97.04%
50
CPDstergmped
0.3 (0.5)
(0.0)
4.6 (5.6)
94.74%
gSeg (nets.)
12.9 (1.8)
(0.0)
19.4 (0.8)
27.20%
gSeg (stats.)
2.2 (0.7)
Inf (na)
-Inf (na)
49.21%
kerSeg (nets.)
6.4 (1.4)
0 (0.0)
16.6 (2.0)
45.50%
kerSeg (stats.)
0.9 (1.2)
0 (0.0)
5.6 (6.8)
93.50%
CPDlatenty
0.1 (0.3)
0.1 (0.3)
1.3 (3.6)
98.60%
CPDlatentg
0.5 (0.7)
0.2 (0.4)
5.1 (6.1)
94.81%
CPDrdpg
0.3 (0.6)
1.5 (0.5)
2.5 (2.0)
91.05%
CPDnbs
1.8 (0.6)
3.5 (3.3)
12.3 (1.3)
72.04%
CPDstergmp=1
0 (0.0)
10.0)
1 (0.0)
98.04%
100
CPDstergmpss
0 (0.0)
(0.0)
1 (0.0)
98.04%
gSeg (nets.)
12.3 (0.9)
0 (0.0)
19 (0.0)
27.80%
gSeg (stats.)
2 (0.4)
Inf (na)
-Inf (na)
55.75%
kerSeg (nets.)
6 (0.8)
0 (0.0)
15.2 (2.0)
47.00%
kerSeg (stats.)
0.9 (0.7)
(0.0)
9.6 (7.6)
93.40%
Scenario 3: Recurrent Neural Networks
In this scenario, Specifically, we sample latent variables z from pre-defined priors, and we randomly initialize the RNNs with uniform weights. The graphs are then generated by the matrix multiplication defined by Equation 1 using the outputs U and V from RNNs. The parameters for the pre-defined priors are
Recurrent Neural Networks (RNNs) to simulate sequences of dynamic networks.
W(-1, 0.1 tE Ai U. W55, 0.1 AEA.AL
12

---

Published in Transactions on Machine Learning Research (04/2025)
Similar to the previous two scenarios, the simulation using RNNNs also imposes time-dependent mechanism across the dynamic networks. Figure exhibits examples of simulated networks. Visually, RNNs produce adjacency matrices that are dense, and no discernible pattern can be noticed.
34
100
34
100
34
67
100
100
100
100
67
100 34
100
Figure 4: Examples of networks generated from RNNs with number of nodes 100. The edge density is approximately 50% for each network. In the first row, from left to right, cach plot corresponds to the network at 1 25, 50, 75 respectively. In the second row, from left to right, each plot corresponds to the network at = 26, 51, 76 respectively (the change points).
Table displays the means and standard deviations of the evaluation metrics for comparison. Because significant. structural pattern or suitable network statistics can be determined priori, neither CPDstergm method with 4 nor with methods that utilize the mis-specifiod network statistics (stats.) cannot produce satisfactory performance. The CPDrdpg method that focuses on node-level representation also does not perform well for networks with complex structures. Notably, the kerSeg method that exploits the features high dimension with networks (nets.) as input data can produce good performance. The CPDnbs method that assumes the networks are generated from inhomogeneous Bernoulli models and uses weighted averages of adjacency matrices also achieve good performance. Tastly, our CPDlatent method that first infers the graph-level representations from the networks and then utilizes them to detect change points yields the best performance in this scenario.
6 can detect the change points accurately. Likewise, both gSeg and kerSeg
5.2 Degree Distributions and Shared Partner Distributions Comparison
Besides the ability to detect change points, our proposed framework includes decoder that can sample graphs from latent variables. Consider the originally simulated networks as ground truth. To evaluate the model's goodness of fit, we compare the degree distributions and shared partner distributions (Hunter & Handcock (006)) between the generated graphs and ground truth, as in Hunter al. (2008a), Hunter et al. (2008b), Kolaczyk & Csárdi (2014) and [Handoock
first estimate the model parameters using the simulated data that excludes the graphs at time E {10, ....... 1003. Then sample z--1 from the estimated priors (f'-11, 1, Ia) to generate g'-1 with the learned decoder, out-of-sample forecasts for the networks at t {10, 20...., 100). For each time point, we generate = 200 networks and we visualize the degree and shared partners distributions. If the corresponding distributions are similar, it indicates that the graph decoder effectively captures the underlying structures, and the generated graphs closely resemble the originally simulated graphs. Figures D and 7 display the degree distributions and Figures and 10 display the shared partner distributions of the generated graphs predicted from the learned decoder for Scenarios 1, 2, and 3 respectively.
al. (2022). Specifically,
13

---

Published in Transactions on Machine Learning Research (04/2025)
Table 3: Means (standard deviations) of evaluation metrics for dynamic networks simulated from RNNs.
The best coverage metric bolded.
Method
R Kl
d(Cic) +
d(cic) 4
C(9,9')
CPDlatent
0 (0.0)
1.8 (0.7)
1.8 (0.7)
94.77%
CPDlatent
0.3 (0.6)
1.7 (0.6)
3.2 (3.0)
93.04%
CPDrdpg
2.4 (1.6)
12.7
11.2 (5.3)
58.07%
CPDnbs
0.1 (0.3)
3.5 (6.8)
1.2 (0.4)
93.87%
CPDstergmp
2.0 (1.7)
6.0 (7.7)
15.2 (4.9)
72.10%
50
CPDstergm
1.0 (0.4)
18.5 (9.4)
14.3 (2.9)
60.25%
gSeg (nets.)
2.3 (0.6)
Inf (na)
Inf (na)
29.42%
gSeg (stats.)
2.9 (0.3)
Inf (na)
Inf (na)
2.47%
kerSeg (nets.)
1.5 (0.9)
1.4 (0.7)
5.3 (3.3)
89.25%
kerSeg (stats.)
2.8 (0.4)
Inf (na)
-Inf (na)
9.89%
CPDlatentN
(0.0)
2.5 (0.7)
2.5 (0.7)
91.96%
CPDlatente
0.2 (0.6)
2.1 (0.7)
2.8 (1.8)
92.34%
CPDrdpg
1.5 (1.0)
12.3(88)
10.4 (3.7)
60.15%
CPDnbs
0.1 (0.3)
2.5 (2.5)
3.3 (3.4)
90.74%
CPDstergmp
2.0 (1.4)
(8.0)
14.1 (3.1)
60.37%
100
CPDstergmy=6
1.2 (1.3)
20.6 (12.6)
15.2 (5.9)
53.21%
gSeg (nets.)
(0.0)
Inf (na)
-Inf (na)
0%
gSeg (stats.)
2.9 (0.3)
Inf (na)
IIn (na)
4.27%
kerSeg (nets.)
1.4 (0.7)
1.9 (0.7)
5.4 (1.9)
88.95%
kerSeg (stats.)
3 (0.0)
Inf (na)
- Inf (na) 0%
Since the networks simulated from STERGM are sparse, the node degrees for both simulated and generated graphs are low in Figure 5 The sparsity challenges the decoder to capture the structural patterns, which ex- plain why some peaks in the degree distributions are not fully covered by the generated graphs. Nevertheless, for nodes with low degrees on the left tails, the trends are well captured by the decoder. Similarly, due to the sparsity, the majority of edges has fewer shared partners in Figure S Though the generated networks tends to over-cstimate the numbers of edges with particular numbers of shared partners, the decreasing trends are captured by the decoder.
Next, the networks simulated from SBM have strong inter-block interactions and the networks simulated from RNNs are dense, resulting in higher node degrees for the simulated and generated graphs in Figures and 7 For these two scenarios, both the tails and peaks of the degree distributions are fully covered by the generated graphs. Similarly, the numbers of shared partners for edges have wider ranges in Figures and 10 and the overall trends are well captured by the decoder. For all three scenarios, the slight discrepancy in the alignment may be due to the decoder being shared across the time points, balancing the structural variation over time. In summary, the overall trends of the corresponding distributions for the generated graphs align with those for the simulated graphs, suggesting the generated graphs are similar the ground truth and the learned decoders have captured the underlying graph structures.
5.3 Real Data Experiments
In this section, we apply the proposed method to two real data, and we align the detected change points with significant events for interpretation. In practice, the number and location of change points for real data are typically unknown, so there no widely accepted ground truth for either the change points or their corresponding events in this unsupervised learning problem. Besides validating the detected change points with significant events in the literature, attempt heuristic approach to compare the results across
14

---

Published in Transactions on Machine Learning Research (04/2025)
23-
20-
23-
20-
20-
15.
Counc
Court
Count
30
Degree
Degree
Degree
Degree
Degree
80
-100
20-
20-
20-
20-
Counc
COurt
Court
30
70
10
50
Degree
Degroe
Degree
Degree
Degree
Figure 5: Degree distributions for the generated graphs predicted from decoder at different time points for the number of nodes 100 and sample size 200. The red lines correspond to the degree distributions of graphs simulated from STERGM.
1-10
t
t-30
t
20-
20
20
20-
20-
10
15-
25-
15-
Count
Court
Court
10
10
10
10-
3-
10
50
50
00
10
20
al Degree
d0
50
60
0
20
30
40
50
1
30 Degree
40
50
62
10
20
30 Degree
40
d0
d0
Deggree
Degree
60
80
90
100
20-
20
20
20-
20-
10
15-
25-
15-
Court
10
10
3-
10 50 Degree
50
60
10
20
10 Degree
3/
50
6b
0
20
30 Degree
40
50
10
20
30 Degree
40
50
63
10
2b
30
40
50
60
Degree
Figure 6: Degree distributions for the generated graphs predicted from decoder at different time points for the number of nodes 100 and sample size s 200. The red lines correspond to the degree distributions of graphs simulated from SBM.
different detection methods as a supplementary evaluation. Specifically, we fit Degree-Corrected Stochastic Block Models (DCSBM) (Kareer & Newman 2011 Zhao et al.] 2012) to the networks between consecutive detected change points, and we evaluate the log- likelihhood of out-of-sample networks that were excluded during model fitting. We choose DCSBM, generalization of Stochastic Block Model (SBM), because SBM is well known approximation of graphons, which among the most general worw model in the literature
15

---

Published in Transactions on Machine Learning Research (04/2025)
20
t=50
23-
20-
23-
20-
20-
15
15
Counc
Court
10
16
4b do 76 Degree
30
10 s0 60
db
6
90 do
db vo
10
4b Degree
30
ab
26
50 do
Degree
Degree
Degree
80
1=90
t=100
23-
20-
20-
20-
15
COunc
Court
10
16
da Degree
50
26
30
10
50 Degree
60
80
6
90 do Degree
6b 76
10
46
10 db
20 50 d0 db
10
Degree
Degree
Figure 7: Degree distributions for the generated graphs predicted from decoder at different time points for the number of nodes 100 and sample size 200. The red lines correspond to the degree distributions of graphs simulated from RNNs.
500-
300
300
Count
Court
200
200
200
200
130
100
100
10
t0
10 digge-wise Shared Partners
F.dgewls Shared Partters
-ige Shared Partners
Edge -wise Shared Partners
Edge-wise Shared Partners
100
500
400
300
300
330
Count
Court
300
230
200
200
130
100
Edge-wbs Shared Partners
Edge-wise Shared Partners
Edge-wise wiie Shared Partners
Edge wile Shared Partners
Edge Sige-wise--. Shared Partners
Figure& 8: Lidge-wise shared partner distributions for the generated graphs predicted from decoder at different time points for the number of nodes 100 and sample size 200. The red lines correspond to the edge-wise shared partner distributions of graphs simulated from STERGM.
Airoldi et al. 2013 Olhede & Wolfe 2014 Gao et al. 2015). Moreover, DCSBM does not favor either the
proposed or competitor methods terms fitting the model. Intuitively, a higher log-likelihood suggests that the detected change points segment the time series in way that better capture the unchanged patterns within each interval. Additional details this evaluation procedure provided in Appendix 7.6
16

---

Published in Transactions on Machine Learning Research (04/2025)
520
400
400
400
400
Couns
300
200
Cours
100
200
200-
200
200
100
100-
100
100
16 25 Edge-wise Shared Parthers
12 is
24 Edge-wise Shared Partners
12
13
Edge-wise se Shared Partners
Edge wise Shared Partners
Edge-wise Shared Partners
60
90
100
400
420
400
300
200
300
300-
Court
Court
200-
200
200
100
120
100
100-
0-
16 25
12 is Edge-wise Shared Partners
20 24 Edge-wise Shared Partnors
13
Edge-wise Shared Partnors
Edge-wisc Shared Partners
Edge-wise Shared Partners
Figure 9: Edge-wise shared partner distributions for the generated graphs predicted from decoder at different time points for the number of nodes 100 and sample size 200. The red lines correspond to the edge-wise shared partner distributions of graphs simulated from SBM.
t= 10
t= 20
t 30
- 40
t
400
400
400
Count
Count
Count
200
200
200
200-
8
26c
db d0
20
3b
d0
10
26
10
de
10
20
40
db
10
20
10
do
do
Edge-wise Shared Partners
Edge-wise Shared Partners
Edge -wise Shared Partners
Edge-wise Shared Partners
Edge-wbie Shared Partners
= 60
t= 70
t 80
=
90
t 100
400
400
Count
Count
200
200
200
200-
0
2/
db d0
20
3b
10
5
10
2/ 10
de
d0
0
10
20
40 db
10 d0
10
do
d0
Edge-wis Shared Paitters
Edge-wise Shared Partners
Edge loge-wisee Shared Partners
Edge-wise Shared Partners
Edge Shared Partners
Figure 10: Edge-wise shared partner distributions for the generated graphs predicted from decoder at dif- ferent time points for the number of nodes n = 100 and sample size s = 200. The red lines correspond the edge-wise shared partner distributions of graphs simulated from RNNss
5.3.1 MIT Cellphone Data
The Massachusctts Institute of Technology (MIT) cellphone data (Fagle Pentland 2006) depicts human interactions via phone call activities among n 96 participants spanning T 232 days. In the constructed undirected networks, edge y 1 indicates that participant i and participant, had made phone calls
17

---

Published in Transactions on Machine Learning Research (04/2025)
day t, and vij 0 otherwise. The data ranges from 2004-09-15 to 2005-05-04, covering the winter break in the MIT academic calendar.
We apply our proposed method to detect change points using the data-driven threshold, and we use network statistics as imput data to the gSeg, kerSeg, and CPDstergm methods. Specifically, we use the number of edges, isolates, and triangles capture the frequency of connections, the sparsity of social interaction, and the transitive association among participants, respectively. Moreover, the CPDrdpg and CPDnbs methods directly utilize networks input data. Figure 11 displays the magnitude of Equation (14) and the change points detected by the proposed and competitor methods. Table Table@rrovides provides list of potential events, aligning
with the detected change points from our method. In general, the magnitude in Figure 11 reflects the scale of structural changes from the observed networks.
g5eg
ker5
Dstergm
C Dnbs
Magnitude
2004-10-23
2004-12-17
2005-01-18
2005-02-22
2009-04-02
Detected Change Points
Detected change points from the proposed and competitor (blue) methods on the MIT Cellphone Data. The threshold (red horizontal line) is calculated by (15) with 2o.9- The dates of the detected change points for the competitor methods are displayed in Appendix 7.6.
Figure 11:
Without specifying the structural patterns in advance to search for change points, our method can punc- tually detect the beginning of the winter break, which is the major event that alters the interaction among participants. As the largest spike in our results of Figure 11 the beginning of the winter break is also de- lected by the competitor methods effectively. Moreover, our method detects change point on 2004-10-23, corresponding to the annual sponsor meeting that occurred on 2004-10-21. More than two-thirds of the participants have attended the meeting, focusing achieving project goals throughout the week (Eagle & Pentland 2006). However, the CPDstergm and CPDrdpg methods struggle to detect this change point. Furthermore, the proposed and competitor methods detect change points related to the spring break, while our method detects two additional change points associated to federal holidays.
The primary discrepancies between the results in Figure II are the two federal holidays on 2005-01-17 and 2005-02-21, which are overlooked by some of the competitor methods. In particular, the gSeg, kerSeg, and CPDrdpg methods identify change points slightly earlier than 2005-01-18, while the CPDstergm method does not detect change point around that period. These discrepancies may be affected by the overlap between the winter break and other holidays around the end of 2004. The detected change points in January 2005 by the competitor methods also suggest that the Martin Luther King day detected by our method is a reasonable change point after the winter break. Moreover, the CPDstergm method detects a clustering of change points during the sponsor meeting around 1004-10-23, which is an indication of overfitting. The result may absorb the excessive noise during that period, such that a clear and single change point cannot be determined. In summary, our result overlaps with the combined results from the competitors, validating the effectiveness of the proposed methods.
18

---

Published in Transactions on Machine Learning Research (04/2025)
Table 4: Potential nearby events aligned with the detected change points from our proposed method on the MIT cellphone data.
Detocted change points
Potential nearby events
2004-10-23
2004-10-21 Sponsor meeting
2004-12-17
2004-12-18 to 2005-01-02 Winter break
2005-01-18
2005-01-17 Martin Luther King Day
2005-02-22
2005-02-21 Presidents Day
2005-04-02
2005-03-21
to 2005-03-25 Spring break
Finally, Table 5 presents comparison of the log-likelihodd values for out-of-sample graphs evaluated using the fitted DCSBM. Although this evaluation procedure is heuristic, the log- likelihood can potentially indicate how well the detected change points capture the unchanged patterns within each segmented interval. To assess robustness and sensitivity, we also compare the results by selectively remóving graphs at different time gaps, specifically At = {15, 20, 25, 30) for T 232. The higher log-likelihood values associated with change points detected by our method suggest that it identifies more meaningful segmentation compared to competitor methods.
Table 5: Log-likelihooe values of the out-ol-sample graphs evaluated using the fitted DCSBM corresponding to their respective intervals in the MIT cellphone data.
At
CPDlatent
CPDubs
CPDrdpg
CPDstergm
kerSeg
gSeg
15
3393.38
3595.74
-3968.61
-3718.24
-4026.17
3891.61
20
-2441.86
2617.12
-2612.46
-2760.73
2592.96
2604.36
25
-1903.14
-2056.03
-2067.39
-2172.59
-2005.87
-2123.85
30
-1869.47
-1901.00
-1956.27
-1906.28
-1991.85
-1914.86
5.3.2 Enron Email Data
The Enron email data, analyzed by Priebe al. (2005). Park et al. (2012). and Peel Clauset (2015
portrays the communication patterns among employees before the collapse giant energy company. The data of focus consists of T 100 weekly undirected networks, ranging from 2000-06-05 to 2002-05-06 for 100 employees. We use the same configuration described in Section 5.3.1 for the proposed and competitor methods to detect change points. Figure 12 displays the magnitude of Equation (14) and the
detected change points from the proposed and competitor methods. Furthermore, Table 6 provides a list of potential events, aligning with the detected change points from our method. In general, the magnitude in Figure reflects the scale of structural changes from the observed networks.
Table 6: Potential nearby events aligned with the detected change points from our proposed method on the Enron email data.
Detected change points
Potential nearby events
2000-10- 10-16
2000-11-01 FERC exonerated Enron
2001-06-11
2001-06-21 CEO publicly confronted
2001-09-24
2001-09-26 Internal employee meeting
2001- 12-0-
2001-12-02 Enron filed for bankruptcy
In 2001, Enron underwent a multitude of major and overlapping incidents, making it difficult to associate the detected change points with specific real events. Despite the turmoil, method detects four signifi-
19

---

Published in Transactions on Machine Learning Research (04/2025)
g5eg
kgr
CPDstergm
CP Drdppp
CP Dnbss
Magnitude
2000-10-16
2001-06-11
2001 2001-09-24
2001-12-03
Detected Change Points
Detected change points from the proposed and competitor (blue) mothods on the Enron email data. The threshold (red horizontal line) is calculated by (15) with Zo.9. The dates of the detected change points for the competitor methods are displayed in Appendix 7.6.
Figure 12:
cant change points that closely align with pivotal moments in Enron's timeline. Throughout 2000, Enron orchestrated rolling blackouts, causing staggering surges in electricity prices that peaked at twenty times the standard rate. Thence, the first change point, detected on 2000-10-16 by our method, aligns with the Federal Energy Regulatory Commission (FERC) exonerating Enron of wrongdoing on 2000-11-01. As a major event with chain reaction throughout 2000, this change point is also detected by the gSeg, kerSeg, CPDrdpg, and CPDnbs methods. Subsequently, a second change point, detected on 2001-06-11, aligns with the CEO confronted by an activist on 2001-06-21 in protesting against Enron's role in the energy crisis. This public incident is also detected by the kerSeg, CPDrdpg, and CPDnbs methods while overlooked by the other competitor methods.
The next two change points are associated with more pronounced shifts in network palterns, indicated by the two substantially large spikes in Figure 12, Specifically, the third change point, detected on 2001-09-24, coincides with an internal employee mocting on 2001-09-26, during which the CEO reassured employces that Enron's ' stock was good buy and the company's accounting methods were legal and appropriate. Following this meeting, Enron's s stock saw final surge before continuing sharp decline. Finally, our method detects change point on 2001-12-03, aligning with Enron filing for bankruptcy on 2001-12-02, marking the collapse of the largest energy company in the U.S.
Based on the results in Figure 12 the primary discrepancies between the proposed and competitor methods are observed at the endpoint of the time span. In particular, four competitor methods have detected change points in February 2002, corresponding to events after Enron filed for bankruptey in December 2001, While the magnitude exhibits two small spikes on the right in Figure 12 they do not exceed the threshold in red be doclared as change points by our method. The scale of changes communication patterns among employees is smaller for the events in February 2002, comparing to the scale of changes in communication patterns during bankruptey.
Besides lowering the threshold to include these change points, the discrepancy suggests potential extension to improve the proposed framework. Perhaps we could specify the priors for the graph-level representalions as x² ~ Ni [") and incorporate both the mean ęe' and covariance E' into the penalty term of the objective function. For example, adaptively adjust the changes at different scales, the inverse of the covariance E' e axdd may serve a scaling factor for the difference μ²+1_ p² Rd, thereby enhancing the magnitudes. By learning the covariances of the graph-level representations and monitoring their consecutive
20

---

Published in Transactions on Machine Learning Research (04/2025)
shifts over time, the latent space regularized in this way could potentially capture more subtle variations in the data space. Furthermore, the ADMM procedure would require an update for Σ', and the quadratic form for the localization method would need to be modified as (z' - -= - (==)===--1--- ~ x.. where the inverse of the covariance is also used for standardization. As there are different ways to incorporate the covariances into the regularization lerm and learning the positive semi-definite covariance via neural network is challenging, we consider this improvement as a potential direction for future development.
The result for gSeg and kerSeg methods can be affected by the choices of network statistics, which may not be representative enough to capture the structural changes. For CPDstergm, the absence of change points in 2000 and the clustering of four change points in late 2001 indicate the detection is sensitive to the noise where network structures shift rapidly during bankruptey, rendering the detected change points unreliable as the model overfitted. In summary, the overlap between the proposed and competitor methods validates the effectiveness of the proposed methods.
Finally, Table compares the log-likelihood with the fitted DCSBM across different methods. Although this is a heuristic evaluation approach, the log-likelihood values provide information into how well the detected change points maintain structural coherence within each interval. To assess robustness and sensitivity, we examine the results by selectively removing graphs at varying time gaps, specifically At = {3, 6, 9, 12] for T = 100. The log-likelihood values based on the change points detected by our method are higher most of the time, suggesting that our approach identifies more reasonable change points compared to competitor methods heuristically.
Table 7: Log- liccliidl values of the out-of-sample graphs evaluated using the fitted DCSBM corresponding to their respective intervals in the Euron email data.
Al CPDlatent
CPDnbs
CPDrdgp
CPDstergm
kerSeg
gSeg
3
9863.13
-10340.97
- -10485.42
- -11681.16
-9936.28
11697.72
5068.16
-4944.41
-4821.8
-5558.92
-5025.10
-4967.78
-2994.83
-3315.66
-3238.66
-3190.70
-3217.85
-3274.96
12
-2482.73
-2507.28
-2570.34
-2518.89
-2540.31
-2592.20
6
Discussion
This paper proposes to detect change points in time series of graphs using a decoder-only latent space model. Intrinsically, dynamic network structures can be complex due dyadic and temporal dependencies, making inference for dynamic graphs challenging task. Learning low-dimensional graph representations can extract useful fcatures to facilitate change point detection in time scries of graphs. Specifically, we assume each observed network is generated from latent variable through graph decoder. We also impose prior distributions to the graph-level representations, and the priors are learned from the data as empirical Bayes. The optimization problem with Group Fused Lasso penalty on the prior parameters is solved via ADMM, and experiment results demonstrate that generative model useful for change point detection.
Several extensions to our proposed framework are possible for future development. Besides binary networks, relations by nature have degree of strength, which are denoted by generic values. Moreover, nodal and dyadic attributes are important components in network data. Hence, models that can generate weighted edges, well as nodal and dyadic attributes, can capture more information about the network dynamics (Fellows & Handcock 2012 Krivitsky, 2012; Kei et al. 2023a). Furthermore, the number of nodes and their attributes are subjected to change over time. Exlending the framework to allow varying network size and to detect node-level anomalies can provide granular insights of network changes (Simonovsky & Komodakis 2018 Shen et al. (023). Also, improving the scalability and computational efficiency for representation learning is crucial (Killick al. 2012 Gallagher al., (021). especially for handling large and weighted graphs. While our framework demonstrates the ability in change point detection, the development of more sophisticated
21

---

Published in Transactions on Machine Learning Research (04/2025)
neural network architectures enhance the model's capacity other meaningful tasks Handcock et al.
2007
Kolar et al. 2010: Yu et al. 2021 Madrid Padilla et al. 2023
Code Availability
The codes are available at http::///ggthbbcccaaaaalllee///p
Acknowledgments
We thank Mark Handcock and Ying Nian Wu for helpful comments on this work. Also, we are extremely grateful for the constructive comments provided by the anonymous reviewers and Action Editors.
References
Edo M Airoldi, Thiago B Costa, and Stanley H Chan. Stochastic blockmodel approximation of graphon: Theory and consistent estimation. Advances in Neural Information Processing Systems, 26, 2013.
Carlos M Alaíz, Alvaro Barbero, and José R Dorronsoro. Group fused lasso. In Artificial Nearal Nelworks and Machine Learning ICANN 2013: 23rd International Conference on Artificial Neural Networks Sofia, Bulgaria, September 10-13, 2013. Proceedings 23, pp. 66-73. Springer, 2013.
Arash A. Amini, Aiyou Chen, Peter J. Bickel, and Elizaveta Levina. Pseudo-likelihodd methods for commu- nity detection in large sparse networks. The Annals of Statistics, 41(4):2097 2122, 2013.
Avanti Athreya, Zachary Lubberts, Youngser Park, and Carey Priebe. Fuclidean mirrors and dynamics in network time series. Journal of the American Statistical Association, pp. 1-4 2024.
Avanti Athreya, Zachary Lubberts, Youngser Park, and Carcy Priebe. Euclidean mirrors and dynamics in network time series. Journal of the American Statistical Association, pp. 1-12, 2025.
Apratim Bhaltacharyya, Berni Schiele, and Mario Fritz. Accurate and diverse sampling of sequences based on a "best of many" sample objective. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8485-8493, 2018.
Kevin Bleakley and Jean-Philippe Vert. The group fused lasso for multiple change-point detection. arxio preprint arXie:1106.44 2011.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Fekstein, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine Learning, 3(1):1 122, 2011.
Carter Butts. A relational event framework for social action. Sociological Methodology, 38(1):155-22 200, 2008.
Carter T Butts, Alessandro Lomi, Tom AB Snijders, and Christoph Stadtfeld. Relational event models in network science. Network Science, 11(2):175-18, 2023.
Guodong Chen, Jesús Arroyo, Avanti Athreya, Joshua Cape, Joshua T Vogelstein, Youngser Park, Chris White, Jonathan Larson, Weiwei Yang, and Carey E Priebe. Multiple network embedding for anomaly detection in time series of graphs. arXiv preprint arXiv:2008. 10055, 2020a.
Hao Chen and Nancy Zhang. Graph-based based change-point detection. The Annals of Statistics, 43(1):139 176, 2015.
Tianyi Chen, Zachary Lubberts, Avanti Athreya, Youngser Park, and Carey Priebe. Euclidean mirrors and first-order changepoints in network time series. arXio preprint ar (ix::2405..1117 11111, 2024.
22

---

Published in Transactions on Machine Learning Research (04/2025)
Zhenxing Chen, Bo Liu, Meiqing Wang, Peng Dai, Jun Lv, and Liefeng Bo. Generative adversarial attributed network anomaly detection. In Proceedings of the 29th ACM International Conference on Informalion & Knowledge Management, pp. 1989 1992, 2020b.
Lynna Chu and Hao Chen. Asymptotic distribution-free change-point detection for multivariate and non- euclidean data. The Annals of Statistics, 47(1):382-415 -1442-144,, 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirections transformers for language understanding. arXiv preprint arXiv:1810.04880 04805, 2018.
Andrea Giuseppe Di Francesco, Francesco Caso, Maria Sofia Bucarelli, and Fabrizio Silvestri. Link prediction under heterophily: A physics-inspired graph neural network approach. arXiv preprint arXiv:2402. 14802, 2024.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:21 10. 07875, 2021.
Nathan Eagle and Alex (Sandy) Pentland. Roality mining: sensing complex social systems. Personal and Ubiquitous Compuling, 10(4):255 268, 2006.
Ian Fellows and Mark S. Handcock. Exponential-famin random network models, 2012.
Ian Gallagher, Andrew Jones, and Patrick Rubin- Delann-ee Spectral embedding for dynamic networks with stability guarantees. Advances in Neural Information Processing Systems, 14:101 2021.
Chao Gao, Yu Lu, and Harrison H. Zhou. Rate-optimal graphon estimation. The Annals of Statistics, 43 (6):2624 2652, 2015.
Damien Garreau and Sylvain Arlot Consistent change-point detection with kernels. Electronic Journal of Statistics, 12(2):4440 4486, 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Mingqi Han, Eric A Bushong, Mayuko Segawa, Alexandre Tiard, Alex Wong, Morgan R. Brady, Milica Momcilovic, Dane M Wolf, Ralph Zhang, Anton Petcherski, et al. Spatial mapping of mitochondrial networks and bioenergetics in lung cancer. Nature, 615(7953):712 719, 2023.
Mark S Handcock, Adrian E Raftery, and Jeremy M Tantrum. Model-based clustering for social networks. Journal of the Royal Statistical Society: Series A (Statistics in Society), 370(2):301-354, 2007.
Mark S. Handcock, David R. Hunter, Carter T. Butts, Steven M. Goodreau, Pavel N. Krivitsky, and Martina Morris. ergm: Fit, Simulate and Diagnose Exponential- Family Models for Networks. The Statnet Project /https://statnet... org). 2022. URL httpp:://CAANN... http:/CCANN.RProjeettt org packageeekggg package version 4.3.2.
Steve Hanneke, Wenjie Fu, and Eric P Xing. Discrete temporal models of social networks. Flectronic Journal of Statistics, 4:585 605, 2010.
Xiaoxin Hc, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of vit/mlp-minge mixer to graphs. In International Conference on Machine Learning, 12724-12745. PMLR, 2023.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:68400-8811, 2020.
Peter Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the american Statistical association, 97(460): 2002.
23

---

Published in Transactions on Machine Learning Research (04/2025)
Shenyang Huang, Yasmeen Hitti, Guillaume Rabusseau, and Reihanch Rabbany. Laplacian change point detection for dynamic graphs. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 349 358, 2020.
David R Hunter and Mark Handcock. Inference in curved exponential family models for networks. Journal of computational and graphical statistics, 15(3):565-58) 583, 2006.
David R Hunter, Steven M Goodreau, and Mark Handcock. Goodness of fit of social network models. Journal of the american statistical associalion, 103(481):248 258, 2008a.
David R. Hunter, Mark S. Handcock, Carter T. Butts, Steven M. Goodreau, and Martina Morris. ergm: A package to fit, simulate and diagnose exponential-famil models for networks. Journal of Statistical Software, 24(3):1-22 29, 2008b.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical Review E-Statistical, Nonlinear, and Soft Matter Physics, 83 (3)))0116177 2011.
Yik Lun Kei, Yanzhen Chen, and Oscar Hernan Madrid Padilla. A partially separable model for dynamic valued networks. Computational Stalistics & Data Analysis, 187:107811, 2023a.
Yik Lun Kei, Hangjian Li, Yanzhen Chen, and Oscar Hernan Madrid Padilla. Change point detection separable model for dynamic networks. Xiv preprinl or arXiv:2303.176. 2023b.
Rebecca Killick, Paul Fearnhead, and Idris Eekley. Optimal detection of changepoints with a linear computational cost. Journal of the American Statistical Association, 107(500):1590 1598, 2012.
Diederik P Kingma, Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 2013.
Thomas N Kipf and Max Welling, Variational graph auto-encoders. arXiv preprint arXim:661100330) 2016.
Eric D Kolaczyk and Gábor Csárdi. Statistical analysis of network data with R, volume 65. Springer, 2014.
Mladen Kolar, Le Song, Amr Ahmed, and Eric P Xing. Estimating time-varying networks. The Annals of
Applied Statistics, pp. 94-123, 2010.
Pavel N Krivitsky. Exponential-family random graph models for valued networks. Electronic journal of statistics, 6:1100, 2012.
Pavel N Krivitsky and Mark S Handcock. A separable model for dynamic networks. Journal of the Royal Statistical Society, Series B, Statistical Methodology, 76(1):29, 2014.
Federico Larroca, Paola Bermolen, Marcelo Fiori, and Gonzalo Mateos. Change point detection in weighted and directed random dot product graphs. In 2021 29th European Signal Processing Conference (EU- -SPCO), pp. 1810-1814. IEEE, 2021.
Namhoon Lee, Wongun Choi, Paul Vernaza, Christopher B Choy, Philip HS Torr, and Manmohan Chan- draker. Desire: Distant future prediction in dynamic scenes with interacting agents. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 336 345, 2017.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. Bart: Denoising requence-to-sqquee pre-training for natural language generation, translation, and comprehension. arXiv preprint 1910.11. 2019.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao- Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35:1362-1375, 2022.
Sitao Luan, Chenqing Hua, Qincheng Lu, Liheng Ma, Lirong Wu, Xinyu Wang, Minkai Xu, Xiao-Wen Chang, Doina Precup, Rex Ying, et al. The heterophilic graph learning handbook: Benchmarks, models, theoretical analysis, applications and challenges. arXio preprint ar 0770:24407.09618, 2024.
24

---

Published in Transactions on Machine Learning Research (04/2025)
Carlos Misael Madrid Padilla, Haotian Xu, Daren Wang, Oscar Hernan Madrid Padilla, and Yi Yu. Change point detection and inference in multivariable nonparametric models under mixing conditions. arXiv preprint arX::22001.11441 2023.
Oscar Hernan Madrid Padilla, Yi Yu, Daren Wang, and Alessandro Rinaldo. Optimal nonparametric multi- variate change point detection and localization. IEEE Transactions on Information Theory, 68(3):1922 1944, 2021.
Oscar Hernan Madrid Padilla, Yi Yu, and Carey E Priebe. Change point localization in dependent dynamic nonparametric random dot product graphs. The Journal of Machine Learning Research, 23(1:100661 10719, 2022.
Bernardo Marenco, Paola Bermolen, Marcelo Fiori, Federico Larroca, and Gonzalo Mateos. Online change point detection for weighted and directed random dot product graphs. IEEE Transactions on Signal and Information Processing over Networks, 8:144-183 1444119,,.110 2022.
Erik Nijkamp, Mitch Hill, Tian Han, Song- Chun Zhu, and Ying Nian Wu. On the anatomy of meme-based maximum likelihood learning of energy--bar based models, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5272-5280, 2020.
Sofia C Olhede and Patrick Wolfe. Network histograms and universality of blockmodel approximation. Proceedings of the National Academy of Sciences, 111(41):14722 144477777722147 2014.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. arXiv preprint arxvv:1802.04 04407, 2018.
Bo Pang, Tian Han, Erik Nijkamp, Song-Chun Zhu, and Ying Nian Wu. Learning latent space energy-based prior model. Advances in Neural Information Processing Systems, 33:21994 22008, 2020.
Jong Hee Park and Yunkyu Sohn. Detecting Structural Changes in Longitudinal Network Data. Bayesian Analysis, 15(1):133 157, 2020.
Youngser Park, Carey Priebe, and Abdou Youssef. Anomaly detection in time series of graphs using fusion of graph invariants. IEEE journal of selected topics in signal processing, 7(1):67-77) 75, 2012.
Leto Peel and Aaron Clauset. Detecting change points in the large-scale structure of evolving networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Carey E Priebe, John M Conroy, David J Marchette, and Youngser Park. Scan statistics on enron graphs. Computational & Mathematical Organization Theory, 11:229-247, 2005.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10684-10695, 2022.
S Golshid Sharifnia and Abbas Saghaei. A statistical approach for social network change detection: an ergm based framework. Communications in Statistics- Theory and Methods, 51(7):2259 2222922000 2022.
Cencheng Shen, Jonathan Larson, Ha Trinh, Xihan Qin, Youngser Park, and Carey E Priebe. Discover- ing communication pattern shifts in large-scale labeled networks using encoder embodding and vertex dynamics. IEEE Trunsuctions on Network Science and Engineering, 2023.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Newral Networks and Machine Rearning-TCAMe 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27, pp. 412 422. Springer, 2018.
Tom AB Snijders. The statistical evaluation of social network dynamics. Sociological methodology, 31(1): 361-395 395, 2001.
25

---

Published in Transactions on Machine Learning Research (04/2025)
Tom AB Snijders, Gerhard G Van de Bunt, and Christian EG Steglich. Introduction to stochastic actor- based models for network dynamics. Social networks, 32(1):44 60, 2010.
Hoseung Song and Hao Chen. Asymptotic distribution-Ffe free changepoint detection for data with repeated obscrvations. Biometrika, 109(3):783-77) 2022a.
Hoscung Song and Hao Chon. New kernel-basee change-poing detection. arXiv preprint 2022b.
Deborah Sulem, Henry Kenlay, Mihai Cucuringu, and Xiaowen Dong. Graph similarity learning for change- point detection in dynamic networks. Machine Learning, pp. 1-44, 2023.
Gerrit JJ den Burg and Christopher KI Williams. An evaluation of change point detection algorithms. arXiv preprinl ar arxi:20003.062 2020.
Jean- Jean-Philippe Vert and Kevin Bleakley, Fast detection of multiple change-points shared by many signals using group lars. Advances in Neural Information Processing Systems, 23, 2010.
Daren Wang, Yi Yu, and Alessandro Rinaldo. Optimal change point detection and localization in sparse dynamic networks. The Annals of Statistics, 49(1):203 232, 2021a.
Juexin Wang, Anjun Ma, Yuzhou Chang, Jianting Gong, Yuexu Jiang, Ren Qi, Cankum Wang, Hongjum Fu, Qin Ma, and Dong Xu. segnn is novel graph neural network framework for single-cell rna-seq analyses. Nature communications, 18(1))1882, 2021b.
Y. X. Rachel Wang and Peter J. Bickel. Likelihood-based model selection for stochastic block models. The Annals of Statistics, 45(2):500- - 528, 2017. doi: 10. 10.1144/6-A0011457 URL https://doi.orgee 1214/
16- A0S1457
Yu Wang, Wotao Yin, and Jinshan Zeng. Global convergence of admm in nonconvex nonsmooth optimization. Journal of Scientific Computing, 78:29 63, 2019.
Jianwen Xie, Song-Chmn Bang-Chm Zhu, and Ying Nian Wu. Syuthesizing dynamic patterns by spatial-temporal generative convnet. In Proceedings of the ieee conference on computer vision and pattern recognition, pp. 7093-7101, 2017.
Jianwen Xie, Yang Lu, Ruiqi Gao, Song-Chur Zhu, and Ying Nian Wu. Cooperative training of descriptor and generator networks. IEEE transactions on pattern analysis and machine intelligence, 42(())277-45, 2018.
Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Lau, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. Advances in neural information processing systems, 32, 2019.
Yi Yu, Oscar Hernan Madrid Padilla, Daren Wang, and Alessandro Rinaldo. Optimal network online change point localisation. arXiv preprint (XX:::2001.05477 2021.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68(1):49 67, 2006.
Xinxun Zhang, Pengfei Jiao, Mengzhou Gao, Tianpeng Li, Yiming Wu, Huaming Wu, and Zhidong Zhao. Vggm: Variational graph gaussian mixture model for unsupervised change point detection in dynamic networks. IEFE Transactions on Information Forensics and Security, 2024.
Yunpeng Zhao, Elizaveta Levina, and Ji Zhu. Consistency of community detection networks under degree- corrected stochastic block models. The Annals of Statistics, 40(4):2266 2292, 2012.
Zifeng Zhao, Li Chen, and Lizhen Lin. Change-point detection in dynamic networks via graphon estimation. arXiv preprint or 1908 1000008000 01823, 2019.
26

---

Published in Transactions on Machine Learning Research (04/2025)
Xiaojing Zhu, Cantay Caliskan, Dino P Christenson, Konstantinos Spiliopoulos, Dylan Walker, and Eric D Kolaczyk. Disentangling positive and negative partisanship in social media interactions using coevolving latent space network with attractors model. Journal of the Royal Statistical Society Series A: Statistics in Society, 186(3):4633 46633)463-488, 2023.
Yunzhang Zhu. An augmented admm algorithm with application to the generalized lasso problem. Journal of Compulational and Graphical Stalislics, 26(1):195 204, 2017.
7 Appendix
7.1 Updating μ and Φ
In this section, we derive the updates for prior parameter μ E RR'xd and graph decoder parameter Φ. Denote the objective function in Equation (6) as L(ø, μ)) and denote the set of parameters {Φ, 14} as 0. We first calculate the gradient of log- log-likeldhood ((0) in L(Ø,, μJ) with respect to 0:
Ve ((0) Vo Σ log P(y")
VollD')
Ply')
Σ P(y*) Vo / P(y', z')d='
Σ 1
Ply)) / P(y', 2²))
VV)[Voolll log P(y', x²) dz
p(y',***)
Vo lo P(u', dz
P(y')
Σ
/ P(=t(1g)) Volog log P(y', z²) dz
Ep(x))0)) Vo log |())) )1)))))p(()))
T
Ep(x')0)) Vo log P(u')=1) + Σ Ep(x
(vo (Vo log P(z)))
Note that the expectation in the gradient is now with respect to the posterior distribution P(z" yy) P(y"lz²) x P(=f). Furthermore, the gradient of L(Ø, u)) with respect to the prior parameter 4² E Rd at a specific time point is
Ve L(b. (1) = -Bp(z(v9) Vue log P(z') + k(pp" v² + w²)
= - ( (z' 1²) + kl(p' vs + w
Setting the gradient V L(),p) to zeros and solve for jt, we have
0 -Ep(s (z + (1 + n)) - k(v² -w0)
(1 + x) Ep(z) +x(x" - -w")
n² I+ Ep wy)(')) + k
I + (v' w²)
27

---

Published in Transactions on Machine Learning Research (04/2025)
Evidently, the gradient of [( pi) with respect to the graph decoder parameter Φ is
v f(o. m)) E Ep(zi ( log P(v'lz)))
The paramoter Φ can be updated efficiently through back-propagation.
7.2 Langevin Dynamics
Calculating the solution in (9) and the gradient in (10) requires evaluating the conditional expectations under the posterior distribution P(="ly") x ((y) x P(z"). In this section, we discuss the Langevin Dynamics sample zt & TRd from the posterior distribution P(=*ly") that is conditional on the observed network y' E [0,1)axm. The Langovin Dynamics, short run MCMC, achieved by itcrating the following:
+ = + V log p + V28e
= V log Ply (2)) 21 log P(2") - V log P(y")] + V
= 2 + V log 2²) (z - 1² n²) + 2õe
where r is the time stop and 5 the step size of the Langovin Dynamics. The error term e ~ NO0 Ia) serves as random perturbation to the sampling process. The gradient of the graph decoder P(y*|=*) with respect the latent variable z' can be calculated efficiently through propaaappaa Essentially, we use MCMC samples to approximate the conditional expectation Ep(zt (-) in the solution (9) and the gradient (10..
7.3 Group Lasso for Updating /
In this section, we present the derivation to update B in Proposition 2 which is equivalent solving a Group Lasso problem (Yuan & Lin 2006). We adapt the derivation from Bleakley & Vert (2011) for our proposed ADMM algorithm. Denote the objective function in 77) L(,,8). When Br. # 0, the gradient of L(7, B) with respect to Br,, is
V.,, C(7, 3) - - Be.
x..,( + W(a) IT.17 X. - -1, 11,e..112
where X., E Rxx1 is the t-th column of matrix X E (T and Br.. RIxd is the t-th row of matrix B E l)xd, Morcover, we denote B_t,. E 1)x= as the matrix obtained by replacing the t-th row of matrix B with a zero vector, and X.,+ E (T denoted similarly.
Setting the above gradient zeros, we have
Be.- = (RX. + 1Br
b.
(16)
where
b. = =X=xXX((((a4 + W(a) 1T,17 X -.,. E Rlxd
Calculating the Euclidean norm of [66 on both sides and rearrange the terms, we have
| = (sX.,, x.. ((bb,ll A).
Plugging 1/8r,112 into 16) for substitution, the solution of Br,. is arrived at
Br. x.T.X., (1 A
||bell2) )o.
Moreover, when Br.. 0, the subgradient v of 1|Br,.112 needs satisfy that ||u||2 S Because
0 E Xv xX.T w(a) 1T,17 X ..):
28

---

Published in Transactions on Machine Learning Research (04/2025)
obtain the condition that Bt. becomes 0 when l|bel22 A. Therefore, iteratively apply the following to update Bt, for each block = 1,..., 1:
Be. KX RX,,X.; (1-
l bt
where ()) = max(: 0).
7.4 ADMM Procedure
The procedure to solve the problem in (3) via ADMM is presented in Algorithm 1 The steps to transform between v and () within an ADMM iteration are omitted for succinctness. The complexity of the proposed algorithm is at least of order A(T'ss + BTnk + DT)) with additional gradient calculation for neural networks in sub-routines. Specifically, for each of iterations of ADMM, we update the prior parameter fe Rd for all time points, and each update involves I steps of MCMC for & samples. Then we calculate the gradients neural networks for all T time points and run B iterations of Adam optimizer. The output of neural networks has dimensions by k. Lastly, we run iterations of block coordinate descent for the sequential differences. Essentially, ADMM decomposes complex optimization problem into smaller problems, targeting individual component one at time.
Algorithm Latent Space Group Fused Lasso
1: Input: learning iterations A, D, tuning parameter X, penalty parameter k, learning rates observed data {y 1y')=1 inilialization {Φa), M(1): (1)) w(1)
2: for a = 1, 1,................ ,A do
for f= 1, , do
draw samples ;i....,,,, 2 from P(= (y') according to (la+1) I+x (s- Ei= 2/) + Itn (v' ww²)
11
end for
7: for b b 1...., do
8: Φ1++1) = (()) x V 14
9: end for
10: Set 7()) = M(a) and ((1) 3(a)
11:
for d 1.... D do
Let ((d+1) be updated according to 12 for = 1, 1,...,
12:
T
((d+1) (1/T)11,T (M(++) ((a) X ((d+1))
13:
14: end for
15: Set Mat1) = (d+1) and B(a+1) B(d+1)
16: W(a+1) = (a+1) M(a+1) + ((()
17: end for
18: f ((a+))
19: Output: learned prior parameters
7.5 Practical Guidelines
7.5.1
ADMM Implementation
In this section, provide practical guidelines for the proposed framework and ADMM algorithm. For Langevin Dynamic sampling, set 8 = 0.5, and draw 200 samples for each time point t. To detect change points using the data-driven threshold in (15), we let the tuning parameter X {10, 20, 50, 100). To detect change points using the localizing method with Gamma distribution in (13) we let the tuning parameter = (5, 10, 20, 50}. For each X, we run A = 50 iterations of ADMM. Within each ADMM iteration, we run B 20 iterations of gradient descent with Adam optimizer for the graph decoder and 20 iterations of block coordinate descent for Group Lasso. We run our experiment with Tesla T4 GPU. The running time for the simulated study is about two hours for scenario with all sequences and
29

---

Published in Transactions on Machine Learning Research (04/2025)
cross-validation on the tuning parameter X. The running time for the real data experiment is approximately twenty to thirty minutes including cross-validation on the tuning parameter X.
Since the proposed generative model is probability distribution for the observed network data, in this work we stop ADMM learning with the following stopping criteria:
I(@(a+1): M()))) - (() (()()))Haa))
S Etol.
(17)
(( ((a))
The log- likelihood 1(6 (i) is approximated by sampling from the prior distribution p(z"), as described Section 4.2 Hence, we stop the ADMM procodure until the above criteria is satisfied for af consecutive iterations. In Section 5 we set etol 10-5 and a' 5.
Here we also elaborate on the computational aspect of the approximation of the log- likelihoood.. To calculate the product of edge probabilities for the conditional distribution P(y"l2",, we have the following:
T
log P(y')= = Σ 1=1
Σ log ((2))=
1=1
T
log EE p(()
II
P(vil|z* [=)]
log
P( [
1=1
u=1 (KJ))Y
1 expl
log
log P(y ((vl)>=1)))
(i,))r
log s + log
exp Ct
expf Σ
log 1og(P(1l/1<))) - c3
u=1
(N,))Y
Σ
( + log
expl
Σ (KJ)Y
Log[P(yt (((ا)==))]]
- Tooog
where O' E R is the maximum value of E(ijer log[P(v()) over m samples but within time point t.
We also update the penalty parameter to improve convergence and to reduce reliance on its initialization. In particular, after the a-th ADMM itcration, we calculate the respective primal and dual residuals:
T
(a) primal
1 x
Σ
1 and raual
1 x
Dt 1
T
T
d
(a)
Throughout, we initialize the penalty parameter 6 10. We jointly update the penalty parameter and the scaled dual variable as in Boyd et al. (001] with the following conditions:
(a)
K(a+1) = 2k(a), w(a+1) =
2 (a)s
if primal > 10 x r
K(a+1)= 2 [(a); (((+1) = 2w) if
1
(a)
dual x (a)
primal
7.5.2 Post-Procesee Processing
Since neural networks may be over-fitted for statistical model in change point detection, track the following Coefficient of Variation signal-to-noise ratio when we learn the model parameter with the full time series data:
Coefficient of Variation mean Ap)
sd( (A))
30

---

Published in Transactions on Machine Learning Research (04/2025)
We choose the learned parameter j with the largest Coefficient of Variation final output.
By convention, we also implement two prot-procsssing steps to finalize the detected change points. When the gap between two consecutive change points is small or Cx- < Eape: we preserve the detected change point with greater AÇ value to prevent clusters of nearby change points. Moreover, the endpoints of a time span are usually not of interest, we remove the C₂ smaller than a threshold cend and the C₁ greater than T - fend- In Section
5
we set Expe = 5 and fend = 5.
7.6 Real Data Experiments
Besides aligning the detected change points with significant real events for interpretation. we can use the Degree-Corrected Stochastic Block Models (DCSBM) (Karrer & Newman 2011 Zhao et al. 2012) to heuris- tically compare the change points detected by the proposed and competitor methods. Specifically, we first remove a pre-specified subset of graphs from the time series, and we fit a DCSBM to the remaining graphs within each interval segmented by two consecutive detected change points. For each removed graph, we com- pute its log-likelihood value under the fitted DCSBM corresponding to its assigned interval. Heuristically, higher log-likelihood indicates that the removed graph is more structurally stable within its interval, thereby supporting the validity of the detected change points.
To implement this supplementary evaluation procodure, we use the nett package (Amini et al. 2013 in R to fit the DCSBM. For two consecutive change points, we consider the time series between them and we exclude the graphs a pre-specified subset. The remaining graphs in the interval are used to compute the average adjacency matrix and fitted to the DCSBM. We let the number of community be K 3, 5} and we use the lowest BIC score (Wang & Bickel| 2017) to choose the optimal number of community for that interval. Lastly, calculate the log- loeliioel of the removed graphs with the node labels estimated by the nett package.
The Regree-Corrected Stochastic Block Model (DCSBM) extends the Stochastic Block Model (SBM) by incorporating degree heterogeneity. The expected adjacency matrix under the DCSBM is given by E(Ay]e) = 0,0, Pay.yy where 0, the degree parameter for node i, c E (1....,K) is the community assignment of node i, and Pej,, E [0, 1 is the block probability matrix. The nett package fits DCSBM by maximizing the following conditional log pseudo likelooikel (Amini et al.
2013
1(T,, (1 (bi)) = log Σ
II k=
ik
With an initialized label vector e = (ei,..., for e, E (1,...,K,, the expectation expecatton--axxiiiann maximization (EM) am iteratively implements the following updates until convergence:
mi m== gpim
Σ Tabak Σ nud,"
T
THl
Ouk
Σk k=l 1 Th I
with node degree di,...,dh, dn. The label vector is updated as G, = arg max, ui, and the block sums are caleulated as byz = E, Anj I(e, = k) for node i = i and block k: = I.
Once the updated node labels (ei,..., en) are obtained, the nett package in R calculates the block sum BRI = Eig Aig 1(c; = k. = 1), node parameter 0, = de/ E, Bereey and the log-likelihood of DCSBM:
1(0;A) A) = Σ Aig log log(O,0,Be,r))
Σ BEi + Σ BER Σ 03) 1,1
Σ k
T& log
T4k
K
kee=
Although this is an heuristic evaluation approach, the log-likelihodd values can potentially provide informa- tion on how well the detected change points have segmented the entire time span into intervals, in which the network patterns are relatively stable.
In Section 5.3 we apply the evaluation procedure to real data. For the MIT cellphone data with T 232, we remove the graphs at time equals to multiples of At (15, 20, 25, 30) respectively. For the Enron Email
31

---

Published in Transactions on Machine Learning Research (04/2025)
data with T 100, remove the graphs at time t equals multiples of At 63, 12) respectively. For completeness, Table g provides the dates of detected change points from the competitor methods on the respective MIT cellphone data and Enron email data.
Table 8: Dates of detected change points from the competitor methods.
Data
Method
Dates of Detected Change Points
CPDnbs
2004-10-30, 2004-12-17, 2005-01-18, 2005-02-19, 2005-03-11, 2005-03-31
MIT
CPDrdpg
2004-12-17, 2005-01-06, 2005-03-11
cellphone
CPDstergm
2004-10-13, 2004-10-24, 2004-11-02, 2004-11-16, 2004-12-17, 2005-03-24
data
kerSeg
2004-10-18, 2004-12-17, 2005-01-05, 2005-04-02
gSeg
2004-11-01, 2004-12-11, 2004-12-18, 2005-01-10, 2005-03-11
CPDnbs
2000-09-04, 2001-02-05, 2001-06-11, 2001-09-03, 2001-11-26
Enron email
CPDrdpg
2000-10-09, 2001-01-08, 2001-05-21, 2001-08-13, 2001-09-17, 2001-12-10, 2002-02-04
CPDstergm
2001-08-20, 2001-10-15, 2001-12-10, 2002-02-04
data
kerSeg
2000-07-10, 2000-10-20 2001-05-21, 2002-02-11, 2002-03-25
gSeg
2000-07-10, 2000-10-16,
2001-12-31, 2002-02-11, 2002-03-25
32


Reviews:
[{"review_id": "EhTacGV6ld", "reviewer": "Reviewer_kLsW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Compared to the previous version, the new draft addresses most of the previous concerns. The algorithm's complexity has been added, and a new simulation study with proper evaluations has been included, which significantly alleviates previous doubts about the method's power and validity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a generative model that learns a prior distribution for the low-dimensional representation of graph data. This model is then used to detect change points in time series of graphs by analyzing changes in the latent representations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Perhaps I overlooked it, but could you please include the environment used to run the method, as well as the time it took for each real data set and simulation?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vgYjxsuWZP", "reviewer": "Reviewer_6BDy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper presents a method for detecting change points in specific graph models. To this end, by leveraging a generative model, the optimization problem, utilizing Group Lasso and ADMM, is well-posed and appropriately formulated.\n\nWeaknesses:\nConversely, the proposed method tends to work well only for specific graph models. For example, as described in the paper, if the assumption that the latent variable z follows a particular Gaussian distribution or that the resulting graphs are formed based on a Bernoulli distribution does not hold, the performance of the method may deteriorate.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a generative model-based approach for detecting change points in dynamic graphs by leveraging low-dimensional latent representations and a decoder-only architecture. The incorporation of learnable Gaussian priors and Group Fused Lasso (GFL) regularization effectively highlights significant structural changes while smoothing minor fluctuations. The authors employ Alternating Direction Method of Multipliers (ADMM) for optimization and Langevin Dynamics for posterior inference.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions:\n1. As mentioned in the weaknesses, the proposed method is designed for change point detection in specific graph models, whereas the competing methods in the simulation study (Section 5) are nonparametric approaches that do not require strong assumptions. Since the proposed method is naturally expected to perform better on data that aligns with its assumptions, a direct comparison with nonparametric methods may not be entirely appropriate. It would be beneficial to compare the proposed method with other approaches that also target similar types of structured data.\n2. Given the distributional assumption on the latent variable z, the proposed method seems to focus primarily on detecting mean shifts in the data. Is it possible to extend this approach to detect changes in variance as well? If so, the model selection process based on the chi-square distribution would likely need to be updated accordingly.\n3. The real data examples were evaluated by fitting Random Dot Product Graph models and assessing log-likelihood values. However, can it be guaranteed that the given datasets indeed follow such graph structures? If not, how should the results be interpreted?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oBPPZaXaU9", "reviewer": "Reviewer_Fgoe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As I mentioned before, I believe that the main contribution and thus biggest strength of the paper is the proposal of the model and the cost in Equation (2), and the method to solve the resulting optimization problem.\n\nHowever, the manuscript still has several shortcomings, particularly regarding some of the claims and the provided evidence, some of which are also highlighted in the \"Changes Since Last Submission\". \n\n* I appreciate the effort by the authors of trying to verify the expressiveness of the proposed method by including the degree distribution of generated as well as actual graphs. However, generating a graph with a given degree distribution is fairly straightforward (e.g. a simple configuration model), and the actual difficulty is to reflect structural features of the graph (e.g. clustering coefficient, shortest paths, etc.). The authors cite the *ergm* package (ref. Hunter et al. (2008b)) to justify why they chose the degree distribution, but in the examples Hunter et al. (2008b) shows several other indicators (see figure 5 of Hunter et al. (2008b), where they display the minimum geodesic distance, edge-wise shared partners, triad census and degree distribution). For further examples see for instance Sec. 6.2.4.2 of the classic book \"Statistical Analysis of Network Data\" by Eric D. Kolaczyk. \n\n* I also appreciate that the authors have added the CPDrdpg method as another baseline. However, the methods of  Larroca et al (2021) and Marenco et al (2022) can be easily added as their code is publicly available (as indicated in those papers, you can obtain the code from https://github.com/git-artes/cpd_rdpg). In particular, I agree that the former is basically CPDrdpg, but the latter is significantly different. The other method asked for by the previous action editor (Gong et al. (2023)) is pertinent, but an implementation is not available as stated by the authors.\n\n* Authors claim that detected change-points in the real-life data is unreasonable and unrealistic for the other methods. The evidence provided to this end is to measure the likelihood of certain graphs (one every 25 for MIT and one every 7 for Enron, which are removed) under an RDPG model between change-points. To this end, they fit the model to the mean of all but the removed graphs between detected change points. Although interesting, I found some important details missing. How many graphs fall on each observed interval? Why not, for instance, consider all graphs and measure this likelihood for every one, by adjusting in all but this graph (*à la* Leave-one-out cross-validation). But maybe more fundamentally: Why choose an RDPG model when the authors are proposing a new model?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "I was one of the reviewers of the previous submission. Since the main contributions remain the same, this section will be very similar to my previous review. The article studies the problem of Change-Point Detection in the context of graphs. That is to say, we observe a set of $T$ graphs (indexed by $t$ which is assumed to correspond to a certain temporal notion) and we would like to detect if and when the generative process underlying each graph changes.\n\nTo this end, the authors propose a generative model, where a latent vector $\\mathbf{z}\\in\\mathbb{R}^d$ is assumed to exist, which in turn generates the graph through an inhomogeneous Bernoulli model. In particular, an edge between nodes $i$ and $j$ exists with probability given by $g(\\mathbf{U}\\mathbf{U}^\\top)$ (for the undirected case), where $\\mathbf{U}=MLP(\\mathbf{z})$ is a multi-layer perceptron (which maps the input d-dimensional vector to a $n\\times k$ matrix, being $n$ the number of nodes) and $g(\\cdot)$ is a point-to-point sigmoid.\n\nInstead of trying to find (fit) $\\mathbf{z}$ for each $t$, the paper studies an approach very similar to a Variational Autoencoder (VAE), where $\\mathbf{z}$ is random and a certain prior distribution is assumed (in this case an uncorrelated Gaussian vector). The problem then becomes how to fit the mean of this distribution $\\boldsymbol{\\mu}$  for each $t$, and a change-point will be flagged if the change between time-steps is high enough. Actually, two methods are proposed, although the second one, a relatively simple heuristic, proves to work best in practice.\n\nI still believe that the main contribution is presenting an objective function specially tailored for CPD, and a method to solve the resulting optimization problem. Instead of using ELBO as in most VAEs, the authors considered the log-likelihood plus a regularization term that penalizes differences between consecutive $\\boldsymbol{\\mu}$ (instead of the KL-divergence of ELBO). Experimental results including synthetic as well as real-world data confirm the competitiveness of the proposal w.r.t. other methods.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Given my comments above, I would request three major changes:\n1. Further verify the expressiveness of the proposed model by measuring and comparing other indicators of the graphs. I would be explicit in the manuscript about the limitations of the proposed method in terms of, at least, its impossibility to express non PSD connectivity matrices (and thus negating heterophilic behavior of the nodes). \n2. Comparing against Marenco et al. (2022) should be straightforward and I would add it to the comparison. A comparison to Gong et al. (2023) would require an implementation, but the authors may undertake its implementation and publish it (and BTW, thanks for the code).\n3. I insist that further discussion about the detected change-points in the real-world dataset is necessary. A simple graph of the number of edges and non-isolated nodes is enough to see that there are effectively change-points at February and March 2002 which for some reason are ignored by the proposed method due to the chosen threshold.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is a resubmission of a [previous version](https://openreview.net/forum?id=FVygyCbzon). The reviewers found that this version has been significantly improved and it addresses the previous raised concerns. All three reviewers support acceptance of the paper, and agree that any remaining concerns can be addressed in follow-up research.

The reviewers recognize the promisingness of the method. In particular, they find the model itself, as well as the proposed optimization algorithm, to be the main strength of the paper. Quoting Reviewer Fgoe, the paper introduces "interesting features that open some research avenues".

One concern, raised by Reviewer Fgoe, is on the robustness of the algorithm. In particular, the proposed approach is unable to detect some simple changes in the Enron dataset. The authors have suggested plausible explanations for this, but further evaluation would be needed to confirm these explanations.
Decision: Accept (poster)