Spectral embedding for dynamic networks with stability guarantees
Authors: Ian Gallagher
Andrew Jones
Patrick Rubin-Delanchy
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph
dynamic network
stochastic block model
spectral embedding
clustering
time series analysis

Abstract: We consider the problem of embedding a dynamic network, to obtain time-evolving vector representations of each node, which can then be used to describe changes in behaviour of individual nodes, communities, or the entire graph. Given this open-ended remit, we argue that two types of stability in the spatio-temporal positioning of nodes are desirable: to assign the same position, up to noise, to nodes behaving similarly at a given time (cross-sectional stability) and a constant position, up to noise, to a single node behaving similarly across different times (longitudinal stability). Similarity in behaviour is defined formally using notions of exchangeability under a dynamic latent position network model. By showing how this model can be recast as a multilayer random dot product graph, we demonstrate that unfolded adjacency spectral embedding satisfies both stability conditions. We also show how two alternative methods, omnibus and independent spectral embedding, alternately lack one or the other form of stability.

Spectral embedding for dynamic networks with stability guarantees
Ian Gallagher
Andrew Jones University of Bristol, UK
University of Bristol, UK
ian. www.gallagherrrrssoll..aa uc.
Patrick Rubin-Delanchy
University of Bristol, UK
Abstract
We consider the problem of embedding a dynamic network, to obtain time-evolving vector representations of each node, which can then be used describe changes in behaviour of individual nodes, communities, or the entire graph. Given this open-ended remit, argue that types of stability in the spatio-temporal positioning of nodes are desirable: to assign the same position, up to noise, to nodes behaving similarly position, up to noise, to a single node behaving similarly across different times (longitudinal stability). Similarity behaviour is defined formally using notions of exchangeability under a dynamic latent position network model. By showing how this model can be recast multilayer random dot product graph, we demonstrate that unfolded adjacency spectral embedding satisfies both stability conditions. We also show how two alternative methods, omnibus and independent spectral embedding, alternately lack one or the other form of stability.
given time (cross-sectional stability) and constant
Introduction
Consider a dynamic network in which nodes come and go, change abruptly or evolve, alone or in communities, and form connections accordingly. Our goal is to find vector representation, Y gd, for every node and time t, which could be used for a diversity of downstream analyses, such clustering, time series analysis, classification, model selection and more. This problem is known as dynamic (or evolutionary) network (or graph) embedding, and a great number of scalable and empirically successful techniques have been put forward, with recent surveys by [47 51) We consider, among these, a subset about which is reasonable to try to establish a certain statistical guarantee.
The novelty of this paper is not to propose new procedure. Instead, it to demonstrate that an existing procedure, unfolded adjacency spectral embedding (UASE) [17], has two important stability properties. Given a sequence of symmetric adjacency matrices A (1) A (T) E {0, 1
where A (t) if nodes and form an edge at time UASE computes the rank d matrix factorisation of A = (A.))... A (T) to obtain A x X using the singular value decomposition (precise details later). The matrix Y IaTxx contains, rows, the desired representations Y (1) (T) (T).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The original motivation for UASE was to analyse multilayer (or multiplex) graphs under an appropri- ate extension of the random dot product graph model [А]. To evaluate UASE and other procedures on the task of dynamic network embedding, we instead consider the dynamic latent position model
A
(1) and Bernoulli (2,,),
(I)
for 1 s S n1 E [T], where Z E R represents the unknown position of node at time t,
and ʃ RR x R + [0, 1] is symmetric function.
This model is well-established 39 22
13
16
2
43
with recent reviews by [20]
and 45 and inference usually proceeds on the basis of parametric model for f (e.g. logistic in
the latent position distance [39] and for the dynamics of z,") (e.g. a Markov process (9]). The
model also includes the dynamic Regree-corrected mixed membership and standard stochastic block
models as special cases, which were studied in 4% 22 14 29 50
40
31
19
To make statistical sense of UASE under this latent position model, we must somehow connect its output (1) to zZ") To this end we construct a canonical representative of ((t) denoted Y!O that UASE can be seen to estimate. Although we make some regularity assumptions on and the z they are not modelled in an explicit, parametric way, and UASE can clearly be used in practice without having a specific model in mind. For example, do not make Markovian assumption on the evolution of z and UASE can be used to uncover periodic behaviours.
The key purpose of imposing a dynamic latent position model is to allow us to put down certain embedding stability requirements. Using this framework, we can define precisely what we mean by two nodes, i and j. behaving "similarly" at times and \ respectively. In such cases, ideally we would have ( ( Two special cases are: to assign the same position, up to noise, nodes behaving similarly at given time (cross- sectional stability) and constant position, up to noise, to a single node behaving similarly across different times (longitudinal stability).
To achieve both cross-sectional and longitudinal stability is generally elusive. We show that two plausible alternatives, omnibus (26) and independent embedding of each A(), alternately exhibit one form of stability and not the other. More generally.
find existing procedures [6] 27 40 & (4 7
28
5 32 37 [9 tend to trade one type of stability off against the other, e.g. via user-specified
cost funetions. As side-note, it could be observed that omnibus embedding is not being evaluated on a task for which it was designed, since in the theory of (26) the graphs are identically distributed. Because the technique is different from the others, still feel it makes interesting addition.
Our central contribution is to prove that UASE asymptotically provides both longitudinal and cross- sectional stability: for two nodes, and j. behaving similarly at times s and respectively, we have {-))) ~ (+( and, moreover, Y-(1)) and Y²(()) have asymptotically equal error distribution. We emphasise that these properties hold without requiring any sort of global stability the network could vary wildly over time but certain nodes still stay fixed. In the asymptotic regime considered, we have n xo, but T fixed so that, for example, our results are relevant to the case of two large graphs. The alternative regime where - oo grows but n is fixed not easily handled by existing theory and to provide constant updates to UASE (or omnibus embedding) in streaming context presents significant computational challenges.
The remainder of this article is structured as follows. Section 2 gives a pedagogical example demonstrating the cross-sectional and longitudinal stability of UASE in two-step dynamic stochastic block model, while highlighting the instability of omnibus and independent spectral embedding. In Section 3] we prove central limit theorem for UASE under a dynamic latent position model, and demonstrate that the distribution satisfies both stability conditions. In Section Ei we review the stability of other dynamic network embedding procedures. Section 5 an example of UASE applied to dynamic network of social interactions in a French primary school, with dynamic community detection example given the main text and a further classification example provided in the Appendix. Section concludes.

---

2 Motivating example
Suppose it is of interest to uncover dynamic community structure, including communities changing. merging or splitting. The dynamic stochastic block model [52 50 provides simple explicit model for this, in which two nodes connect at a certain point in time with probability only dependent on their current community membership. Suppose that at times and 2, have the following inter-community link probability matrices,
0.08
0.02
0.18
0.10
0.16
0.16
0.04
0.10
B
0.02
0.20
0.04
0.10
B
0.16
0.16
0.04
0.10
0.18
0.04
0.02
0.02
0.04
0.04
0.09
0.02
0.10
0.10
0.02
0.06
0.10
0.10
0.02
0.06
At time I there are four communities present, for example, a node of community connects with a node of community 3 with probability 0.18. At time 2, this matrix changes that communities and 2 have merged, community 3 has moved, whereas community 4 is unchanged. For simplicity, in this example, the community membership of each node is fixed across time-steps.
We simulate a dynamic network from this model over these two time steps, on n = 1000 nodes, equally divided among the four communities and investigate the results of three embedding techniques: UASE, omnibus, and independent spectral embedding, displayed in Figure I Note that the different techniques produce embeddings of different dimensions; UASE embeds into d 4 dimensions, omnibus embedding d 7, while independent spectral embedding has di and d2 3. For visualisation, we show the leading two dimensions for each embedding. Given the dynamics described above, contend that the following properties would be desirable:
1. Cross-sectional stability: The embeddings for communities and 2 at time 2 are close.
2. Longitudinal stability: The embeddings for community 4 at times 1 and 2 are close.
UASE y(t)
Omnibus Y!U
Independent V!U
0.4
0.4
0.2
0.2
-0.2
-022
-0.2
-0.4
UASE
Omnibus 21
Independent 2
0.4
0.4
0.4
0.2
0.2
-0.2
0.2
-0.2
-044
-0.4
-0.3
-0.2
-01
-0.4
-0.3
-0.2
-0.5
-0.4
-0.3
-0.2
-0.1
Community 1
Community 2
Community 3
Community 4
Figure 1: First two dimensions of the embeddings for the adjacency matrices (1) and (2) using three different techniques: UASE, omnibus and separate embedding. The points coloured according to true community membership, with the black dots showing the fitted community centroid and the ellipses fitted 95% level Gaussian contour.
Figure I iillustrates that UASE has both properties: the blue and orange point clouds merge at time 2, and the red point cloud has the same location and shape over the two time points. On the other hand, omnibus embedding only has longitudinal stability (the blue and orange point clouds don't 't merge
3

---

time 2), whereas independent spectral embedding only has cross-sectional stability (the red point cloud different locations over the two time points).
Theoretical background and results
We consider sequence of random graphs distributed according dynamic latent position model, in which the latent position sequences (E12) (where we use the shorthand [T] ......,T)) are independent of each other, and identically distributed according to a joint distribution F on 2 for bounded subset Z of RR We emphasise that for fixed the latent positions Z and z may have different distributions - we are imposing exchangeability over the nodes (invariance to node labelling), but not over time.
By extending the function f to be zero outside of its domain of definition, we may view it as an element of 1.2 (TR x RR), and consequently may define compact, self-adjoint operator A I,2 (R²) by setting
Ag(x)= f f(z,y)gu)d
for all E ).R The operator A has a-possibly sequnit of non-zero eigenvalues A 2 A2 2 with corresponding orthonormal eigenfunctions U1, U2,... E (IK such that Auj AyU (for further details, see for example (35).. We shall make the simplifying assumption that A has finite number of non-zero eigenvalues, in which case f admits a canonical eigendecomposition
D
y(x,y) Σ X,ux(x)u
(3)
assumed to hold everywhere, where after relabelling may assume that [^i] 2 1.. |Ap|_
Several families of functions satisfy the finite rank assumption D < co, such as the multivariate polynomials B35 Moreover, several existing statistical models can be written as dynamic latent position network models in which D < oo, including the dynamic mixed membership, degree- corrected, and standard stochastic block models. To assume D < oo, more generally, is tantamount to a claim that, for large n, A (t) has 'low' approximate rank: an overwhelming proportion of its eigenvalues are close to zero. Large matrices with low approximate rank are routinely encountered across numerous disciplines, and the study [o] provides a hypothesis for this "puzzling" general observation. However, given a real network, we might reject the hypothesis that f has low rank (we must then also reject any type of stochastic block model), for example on the basis of triangle counts In such setting, we anticipate that UASE is still consistent and stable dl is allowed to grow sufficiently slowly with n and there exist asymptotic results for adjacency spectral embedding, for the single graph case, showing convergence in Wasserstein distance under assumptions on eigenvalue decay which can be related to the smoothness of f [24]. However, even if we could obtain such results for UASE, they would not be as powerful as those we present here for the finite rank case, where we show uniform consistency with asymptotic Gaussian error.
Theorem 1.
The adjacency matrices A (l),..., A (T) are jointly distributed according to a multilayer random dot product graph model.
The multilayer random dot product graph model (MRDPG, see 1r] is a multi graph analogue of the generalised random dot product graph model [36), and is characterised by the existence of matrices (0) E dk and random matrices X E Roxd and ( e Runde (generated according to some joint distribution () such that
A (t) and
Bernoulli ( ("))
(4)
for each t E [T] and j.j E [n]. where X, and ( denote the ith and jth rows of X and (1) respectively.
We refer the reader to the supplemental material for full details of the proof of Theorem D but note
that given knowledge of the function f and the underlying distribution F we can construct explicit

---

maps pp: RT - IRd and R - RR, producing row vectors, and matrices A (1) E Rdxd such that
s(z -3") X.A (B)
(5)
- where X; = (Z.), Y
(Z, and Z. ...1i1?) E R for each t E [7] and
i.j [n]. Consequently, each Gram matrix
p(0
(s(Z)) ) [.sE(M)
(6)
admits factorisation into a product of low-rank matrices, in which the matrix whose rows are the vectors (Zz,) appears as a common factor. The dimensions de and d are precisely the ranks of the
matrices ((t) and their concatenation P = (P(") ... (P(T) respectively. In the theory that follows will assume that the dimension d is known and fixed, whereas in practice we would usually have to estimate it (for example by using profile likelihood [55l).
We can extend our model to incorporate range of sparsity regimes by scaling the function f by sparsity factor Pn. which we assume is either constant and equal to or else tends to zero as n grows, corresponding to dense and sparse regimes respectively. When this factor is present, the maps &p and (P: are scaled by a factor of pkl
Realising our model as an MRDPG allows us to make precise statements about the asymptotic behaviour of the point clouds obtained through UASE. In particular, it is the existence of common factor in the decomposition of each of the Gram matrices p(O) that gives rise to the stability properties previously demonstrated in the embeddings (t), this matrix in sense acts an anchor for the individual point clouds.
In 117 UASE is used to obtain two multi-grape embeddings; the algorithm below retains only one- the 'dynamic' component.
Algorithm 1 Unfolded adjacency spectral embedding for dynamic networks
input symmetric adjacency matrices A (1) ..... A (T) E (0,1)*x 1)mX", embedding dimension d
1: Form the matrix A (A (A AA (27) E {0, 1]"xIn (column concatenation)
2: Compute the truncated singular value decomposition UAΣAVA of A, where ΣA contains the d largest singular values of A, and UA, VA the corresponding left and right singular vectors
3: Compute the right embedding Y = V E RTuxd and create sub-embeddings ()))) E
gaxd where Y = (Y))),.... ...; (()) (row concatenation)
return node embeddings for each time period (1) 1.... (2)
Replacing A with P in this construction yields the noise-free embeddings ()) whose known to be linear transformations of the vectors (zz(Zz)) (see the supplemental material for further details). A desirable property of UASE that since the matrices (+) follow an MRDPG model there
exist known asymptotic distributional results for the embeddings ()) In order to ensure the validity of these results, will make the assumption that the sparsity factor Pn. satisfies Pa. w(n - log (n)) for some universal constant > 1.
In the results to follow, UASE is shown to be consistent and stable in a uniform sense, i.e. the maximum error of any position estimate goes to zero, under the assumption that the average network degree grows polylogarithmically in To achieve this for less than logarithmic growth would be impossible, by any algorithm, because would violate the perfect community recovery under the stochastic block model [I]] In practice this means that the embedding will have high variance when the graphs have few edges. Several approaches have been proposed to make single graph embeddings more robust (e.g. sparsity heterogeneous degrees), such as based on the regularised Laplacian [3] or con-backtracking matrices [21]. but it an open and interesting question how extend them the dynamic graph setting achieve both cross-sectional and longitudinal stability.
sparsity limit for
The first of our distributional results states that after applying orthogonal transformation-whire leaves the structure of the resulting point cloud intact the embedded points v-(") converge in the Euclidean norm to the noise-free embedded points Y the graph size grows:
5

---

Proposition 2. There exists sequence of orthogonal matrices W E O(d) such that
max
! W Y | (
log (m) pn n//2
(7)
(E
with high probability for each
The matrices W are unidentifiable in practice, but are defined to be the solution to the one-mode orthogonal Procrustes problem
W arg min |U - Upl1 + - -
QEO(d)
where I|-11p- denotes the Frobenius norm. We emphasise that the matrix W is the same for each embedding, and so similar behaviour in the noise-free embeddings Y is captured by UASE
Our second result states that after applying a second orthogonal transformation the above error converges in distribution to a fixed multivariate Gaussian distribution:
Proposition 3. Let Ç = (G. 16r) F, and for z E Z define
Ee [(2, (1 f(z, ()) (p()) ((())((())))))))))))((()())))) x()) Ec f(z, Sr) :p(c) ((())
if Pr. =
E2(z)=
(9)
if Pr. + 0.
Then there exists a deterministic matrix R. E Rdd and a sequence of orthogonal matrices W E O(d)
such that, given z E Z, for all y E Id and for any fixed E [n] and E (T).
11 (// ( S 2 - - + R. R.E,
(10)
As in our previous results, the matrices W and R., can be explicitly constructed given knowledge of the underlying function ʃ and distribution (again, we defer full details to the supplemental material). Note that as in Proposition 2 both constructed matrices are common to all embeddings.
We can now demonstrate one of the key advantages that UASE holds over other embedding meth- ods, namely that UASE exhibits both cross-sectional and longitudinal stability, in a sense that we shall now define. We say that two space-time positions (z,t) and (z', t') are exchangeable (z, ()) f(z', (v)) with probability one, where Ç {= (G1 ... (Cr)) ~ F, and that the positions are exchangeable up to degree if fzz, &e) fz((z', (tr for some > 0. Equivalently, (z, and (z',
exchangeable if conditional Z and Z ((t) z the ith row of (()) and jth row of p(t") are equal with probability one.
Definition Given generic method for dynamic network embedding, with output denoted (2 (2) Ne (])aE(]) define the following stability properties:
1. Cross-sectional stability: Given exchangeable (z, t) and (z',t). 2,(0) and 2, are asymptoti-
cally equal, with identical error distribution, conditional on z(") and Z =z'.
2. Longitudinal stability: Given exchangcable (z, t) and (z, t'), 2 and ( are asymptoti-
cally equal, with identical error distribution, conditional z z
The following result then shows that UASE exhibits both types of stability:
Corollary 5. Conditional on z z and Z = z', the following properties hold:
If (z, t) and (z', (') are exchangeable then { and (t') are asymptotically equal, with identical error distribution.
2. If (z, !) and (z'. (L' are exchangeable up degree then { and Y (t') are asymptotically
equal and, under a sparse regime, their error distributions are equal up to scale, satisfying (2) = er (z').
We can gain insight into our theoretical results by applying them in the context common statistical models. Under the dynamic stochastic block model of Section pair (z, t) and (z', (t) are

---

exchangeable if and only if the corresponding rows of ( and (+) are identical. Proposition then predicts that the point cloud obtained via UASE should decompose into finite number of Gaussian clusters, as we observe in Figure T Moreover, when combined with Corollary 5 the equality of the fourth rows of B and (2) implies that we should expect identical clusters (centre and shape) corresponding the fourth community both time points (indicating longitudinal stability) and similarly the equality of the first and second rows of B(22 tells us that the communities should be indistinguishable at the second time point (indicating cross-sectional stability), behaviours we observe in Figure @ Under degree-correction T8] 29), Corollary indiiates that should at least observe cross-sectional and longitudinal stability along 'rays' representing communities, behaviour that is exhibited in Figure
4 Comparison
In this section we investigate the stability properties of alternatives to UASE Table shows the stability of the three embedding algorithms described in Section and two wider classes of algorithms, described below. For alternatives to UASE, it will be considered sufficient to establish whether an embedding is stable when applied to the Gram matrices p ,,,),, A method found to be unstable in this noise-free frise-free condition is not expected to be stable when the matrices are replaced by their noisy observations A (1) A
.....
Table I: Classes of dynamic network embedding algorithms: a brief description, the algorithm complexity and its cross- poos--ectional/longiuuiaa stability. In the three latter classes, one may replace ( with other matrix representations of the graph (e.g. the normalised Laplacian). Further details in main text.
Algorithm
Description
Complexity
Stability
UASE 177
Embed A (A) (T))
O(dTn²)
Both
Omnibus
26
Embed A; Ag,t = (A()) + (1)2
O(dT2n²)
Longitudinal
Independent
Embed A (t)
OEE, dn²))
Cross-sectional
Separate embedding
Embed À (t) = =3 W4 A (1-h)
Neither
40
2
57
19
Joint embedding
arg min (1)).... ViT a E, CS((())) +(1 a) E, Y((1))
Neither
A
2X
The omnibus method computes the spectral embedding of the matrix E 10,TTTTx07 where the [0. 1 [T=Tx*] x the
block A, E Raxa is given by (A (4) + A (9) 2 E R and we denote by P E
noise-free counterpart of A. If (z, t) and (z, t') are exchangeable, then, conditional on Z z the rows P p((-11)+s and P +n equal. However, if (z, () and (z', t) are exchangeable, then, in general, Pn(t-1)+i # P Pn(t-1)+j when z(th z and z = z'. One can demonstrate that two rows of P are equal and only if the corresponding nodes' embeddings are too. Therefore, omnibus embedding provides longitudinal but not cross-sectional stability.
Independent adjacency spectral embedding computes the spectral embeddings of the matrices A (1) {0, 1) 1 If (z,, t) and (z', .') exchangeable, then, conditional Z and Z,6² z'.
the rows p(f) and pf(') are equal. If t' the embeddings of nodes and j are equal, however, embeddings between different graphs are subject to (possibly indefinite) orthogonal transformations
Q(() which, if (()) * p(t') differ in non-trivial way (i.e. beyond simply reflecting the ambiguity of choosing eigenvectors in the spectral decomposition of P(f). Therefore, independent adjacency spectral embedding provides cross-sectional but not longitudinal stability. The same arguments extend to other independent embeddings.
Separate embedding covers collection of embedding techniques separately applied to time averraed matrices, A (1) Σx wt A (t-k) where wk non-negative weights, and A (t) may be replaced by
7

---

another matrix representation of the graph such as the normalised Laplacian. The weights may be constant, e.g. W/: = 1/t for all 40
exponential forgetting factors w/; = (1- [[ chosen to produce sliding window 22 based on a time series model [7), and more. In general, temporal smoothing results in two nodes behaving identically at time being embedded differently if their past or future behaviours differ, whereas the act of embedding the matrices separately will result in the same issues of alignment encountered in independent adjacency spectral embedding. Therefore, those methods can have neither cross-sectional nor longitudinal stability, except in special cases where one can contrive to have one but not other (e.g., wg = and wa 0, reducing to independent embedding).
Joint embedding techniques generally aim to find an embedding to trade-off two costs: 'snapshot cost' (CS) measuring the goodness-of-fit to the observed (+), and 'temporal cost' (CT) penalising change over time. These are then combined into a single objective function, for example, as [28] (where we have replaced the normalised Laplacian by the adjacency matrix):
T + (1- - - 1
T-1 Σ
arg min a A AOT
A A
(11)
where a E [o, 11, subject to a low rank constraint on A (T), where Y) is the spectral embedding of À (*), It is easy to see that a change affecting only a fraction of the nodes will result in change of all node embeddings, precluding both cross-sectional and longitudinal stability (again apart from contrived cases, e.g. when a = 1))
For the complexity calculations, we assume dense regime in which the k-truncated singular value decomposition an m-by-n matrix (kmn) [K]
Independent embedding more efficient than UASE, on account of Σ de df, but UASE is more efficient than omnibus embedding, because of the linear versus quadratic growth in T, while d rank(P) is often larger than d.
Real data
The Lyon primary school data set shows the social interactions at French primary school over two days in October 2009 [4. The school consisted of 10 teachers and 241 students from five school years, each year divided into two classes. Face-to-face interactions were detected when radio- frequency identification devices worn by participants (10 teachers and 232 students gave consent to be included the experiment) were in close proximity over an interval of 20 seconds and recorded as pair of anonymous identifiers together with timestamp. The data are available for download from the Network Repository website 34
time series of networks was created by binning the data into hour-long windows over the two days, from 08:00 to 18:00 each day. If at least one interaction was observed between two people in particular time window, an edge was created to connect the two nodes in the corresponding network. This results in a time series of graphs A ( ......,. A (20) each with n = 242 nodes. Where a node not active in given time window, it is still included in the graph an isolated node. This is compatible with the theory and method, and the node is embedded to the zero vector at that time point.
Given the unfolded adjacency matrix = [1 ... A (20), an estimated embedding dimension d 10 was obtained using profile likelihood 55 and we construct the embeddings Y (2)) E R=x10 taking approximately five seconds
2017 MacBook Pro. Figure 2 shows the first two dimensions of this embedding to visualise some of the structure in the data. Similar plots and discussion for both individual spectral embedding and omnibus embedding are given in the Appendix.
From this plot, we observe clustering of students in the same school class. For time windows corresponding to classroom time, for example, 09:00-10:00 and 15:00-16:00, the embedding forms rays of points in 10-dimensional space, with each ray broadly corresponding to a single school class. This is to be expected under degrec-corrected stochastic block model, and the distance along the ray is a measure of the node's 's activity level [25] 30 3X) However, not all time windows exhibit this structure, for example, the different classes mix more during lunchtimes (time windows 12:00-13:00 and 13:00-14:00).
http://heetoriirppssttryyyy
8

---

Day 1, 08:00-09:00
Day 1, 09:00-10:00
Day 1. 10:00-11:00
Day 11:00-12:00
Day 1, 12:00-13:00
0.2
0.0
-0.4
Day 1, 13:00-14:00
Day 1, 14:00-15:00
Day 1, 15:00-16:00
Day 16:00-17:00 17:00
Day 1, 17:00-18:00
0.0
-0.2
2, 08:00-09:00
Day 2. 09:00-10:00
Day 10:00-11:00
Day 11:00-12:00
12:00-13:00
0.0
-02
2. 13:00-14:00
Day 2, 14:00-15:00
Day 15:00-16:00
Day 16:00-17:00
17:00-18:00
0.4
-0,
0.0
0.2
0.4
0.0
0.2
0.4
0.0
0.2
0.4
0.0
0.2
0.4
0.0
0.2
0.4
Class 1A
Class 2A
Class 3A
Class 4A
Class
Teacher
Class 18
Class 2B
Class 3B
Class 4B
Class
Figure 2: First two dimensions of the embeddings ())) Y (20) of the unfolded adjacency matrix
A = (A ... A (20)). The colours indicate different school years while the marker type distinguish the school classes within each year.
5.1 Clustering
Following recommendations regarding community detection under a degree-corrected stochastic
block model 3 analyse UASE using spherical coordinates (!) [0, 2n7 for t [7]. Since UASE demonstrates cross-sectional and longitudinal stability, we can combine the embeddings into a single point cloud θ = (I(I)T ... (T( E Tx*x where each point represents a student teacher in particular time window. This allows behaviour in the dynamic network. We fit a Gaussian mixture model with varying covariance matrices the non-zero points in + with 20-50 clusters increasing in increments of 5, with 50 random initialisations, taking approximately five minutes on a 2017 MacBook Pro. Using the Bayesian Information Criterion, we select the best fitting model (30 clusters) and assign the maximum posteriori Gaussian cluster membership to each student in each time window.
detect people returning to previous
Figure shows how students in the ten classes move between these clusters over time. Each class has one or two clusters unique to it, for example, the majority of students class 1A spend their classroom time (as opposed to break time) assigned to cluster cluster 25. This highlights the importance of longitudinal stability in UASE, as we are detecting points in the embedding returning some part of latent space.
There are also instances multiple school classes being assigned the same cluster the same time period, for example, the morning of day classes 5A and 5B mainly in cluster 28 suggesting

---

Day
Day 2
Class
14
25
29
25
25
Class 18
24
24
17
29
Class 2A
11
11
11
Class 28
29
29
10
10
10
Class 3A
20
Class 38
18
18
20
Clsss 4A
12
12
12
12
Class 48
14
14
14
19
14
Class 5A
23
23
23
23
23
21
21
class
58
16
30
30
30
30
08:00-09:00
09:00-00:00
10:00 11:00
11:00-12:00
12:00-13:00
13:00-14:00
14:00-15:00
15:00-16:00
16:00-17:00
17:00-18:00
08:00-09.00
09:00-10:00
10:00-11 1100
11:00- 12:00
12:0013:00
13:00: 14:00
15:00
16:0016:00
16:00-1 7:00
17:00-18:00
12:00-130
14:00-15:
15:00-
Figure 3: Bar chart showing the Gaussian cluster assignment of school classes over time. The height of each coloured bar represents the proportion of students, in that class and at that time, assigned to the corresponding Gaussian cluster, the total available height representing 100%. If the coloured bars do not sum to the full available height, the difference represents the proportion of inactive students. For legibility, only bars representing over 35% of the class labelled with the cluster number.
they are having a joint lesson, and see this behaviour again on day 2 with classes 3A and 3B in cluster 20, In the lunchtime periods, particularly on day 1, the younger students (classes IA-2B) mingle to form larger cluster, as do the older students (classes 4A-5B), potentially explained by cafeteria needing two sittings for lunch for space reasons [4)] This highlights the importance of cross cooss-ccctinaal stability in UASE, as it allows the grouping of nodes behaving similarly in specific time window, irrespective of their potentially different past and future behaviours.
6 Conclusion
We prove that existing procedure, UASE, allows dynamic network embedding with longitudinal and cross-sectional stability guarantees. These properties make range of subsequent spatio-temporal analyses possible using tfff-the-shelf techniques for clustering, time series analysis, classification and more. While our goal is to facilitate exploratory data analysis across range of scientific disciplines, there could be a privacy concern in the possibility of matching a node's behaviour between two graphs, despite being labelled differently. This could be exploited to compromise someone's 's identity, for example, across online social networks. We hope to raise awareness of such possibilities, for instance, in the context of network data anonymisation.
10

---

Funding Transparency Statement
Andrew Jones and Patrick Rubin-Delane Seoiin-elanchy's research was supported by an Alan Turing Institute fellowship. Ian Gallagher's research was supported by an EPSRC PhD studentship.
References
[1] Abbe, E. (2017). Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446 6531.
[2] Agterberg, J., Tang, M., and Priebe, C. E. (2020). On two distinct sources of nonidentifiability in latent position random graph models. arXiv preprint arXiv:2003.14250
[3] Amini, A., Chen, A., Bickel, P. J., and Levina, E. (2013). bieudo-lkellhoodd methods for community detection in large sparse networks. The Annals of Statistics, (rriiticss41(00 41(4):2097-2122,
[4] Bhattacharyya, S. and Chatterjee, S. (2018). Spectral clustering for multiple sparse networks: I. arXiv preprint arXiv: 10594.
[5] Chen, H. and Li, J. (2018). Exploiting structural and temporal evolution in dynamic link prediction. In Proceedings of the 27th ACM International Conference Information and Knowledge Management, pages 427-436.
[6] Chi, Y., Song, X., Zhou, D., Hino, K., and Tseng, B. L. (2007). Evolutionary spectral clustering by incorporating temporal smoothness. Proceedings of the 13th ACM SIGKDD international conference Knowledge discovery and data mining, pages 153-162.
[7] Deng, D., Shahabi, C.,, Demiryurek, U., Zhu, L., Yu, R., and Liu, Y. (2016). Latent space model for road networks to predict time-varying traffic. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1525-1534.
[8] Dunlavy, D. M., Kolda, G., and Acar, E. (2011). Temporal link prediction using matrix and tensor factorizations. ACM Transactions Knowledge Discovery from Data (TKDD), 5(2):1-27.
[9] Durante, D. and Dunson, D. B. (2014). Nonparametric Bayes dynamic modelling of relational data. Biometrika, 101(4):883-898.
[10] Durante, D., Mukherjee, N., and Steorts, R. C. (2017). Bayesian learning of dynamic multilayer networks. The Journal of Machine Learning Research, 18(1):1414-1442.
[11] Friel, N., Rastelli, R., Wyse, J., and Raftery, A. E. (2016). Interlocking directorates in Irish companies using latent space model for bipartite networks. Proceedings of the National Academy of Sciences, 113(24):6629-663) 66334
[12] Gao, S.. Denoyer, L., and Gallinari, P. (2011). Temporal link prediction by integrating content and structure information. In Proceedings of the 20th ACM international conference on Information and knowledge management, pages 1169-1174.
[13] Gu, M. and Eisenstat, S. C. (1996). Efficient algorithms for computing strong rank rank-revealing qr factorization. SIAM Journal on Scientific Computing. 17(4):848-86) 869.
[14] Ho, Q. Song, L., and Xing, E. (2011). Evolving cluster mixed-membershhi blockmodel for time-evolving networks. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 142-350. JMLR Workshop and Conference Proceedings.
[15] Hoff, D. (2011). Hierarchical multilinear models for multiway data. Computational Statistics Data Analysis, 55(1)5530-543.
[16] Hoff, P. D. et al. (2011). Separable covariance arrays via the Tucker product, with applications multivariate relational data. Bayesian Analysis, 179-1199.
[17] Jones, A. and Subin-Delanchy (2021). The multilayer random dot product graph. arXiv preprint 20X1v.2007.10455

---

[18] Karrer, B. and Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Phys. Rev. E (3). 83())016107, 10.
[19] Keriven, N. and Vaiter, S. (2020). Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model. arXiv preprini arXiv:2002.0228 02892.
[20] Kim, B., Lee, K. H., Xue, L.,, and Niu, X. (2018). A review of dynamic network models with latent variables. Statistics surveys, 12:105.
[21] Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L.,, and Zhang, P. (2013).
Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 11065)):00355-2099
[22] Lee, N. H. and Priebe, C. E. (2011). A latent process model for time series of attributed random graphs. Statistical inference for stochastic processes, 14(3):231-253.
[23] Lee, N. H., Yoder, J., Tang, M., and Priebe, C. E. (2013). On latent position inference from doubly stochastic messaging activities. Multiscale Modeling & Simulation, 11(3):683-718.
[24] Lei, J. (2021). Network representation using graph root distributions. The Annals of Statistics, 49(2):745-768.
[25] J.,, and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. Ann. Statist., 43(1)2215-237.
[26] Levin, K., Athreya, A., Tang, M., Lyzinski, V., Park, Y., and Priebe, C. E. (2017). A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference. arXiv preprint arXiv: 700.00935.
[27] Lin, Y.RR., Chi, Y., Zhu, S., Sundaram, H., and Tseng, B. L. (2008). Facetnet: framework for analyzing communities and their evolutions in dynamic networks. In Proceedings of the 17th international conference on World Wide Web, pages 685-694.
[28] Liu, F., Choi, D., Xie, L., and Roeder, K. (2018). Global spectral clustering in dynamic networks. Proceedings of the National Academy of Sciences, 115(5):927-932.
[29] Liu, S., Wang, S., and Krishnan, R. (2014). Persistent community detection in dynamic social networks. In Pacific-Asia Conference Knowledge Discovery and Data Mining, pages 78-89. Springer.
[30] Lyzinski, V., Sussman, D. L., Tang, M., Athreya, A., and Priebe, C. (2014). Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding. Electron. J. Stat., 8(2):2905- 2922.
[31] Matias, C. and Miele, V. (2015). Statistical clustering of temporal networks through a dynamic stochastic block model. arXiv preprint 1rXivv/506.077
[32] Pensky, M., Zhang, T., al. (2019). Spectral clustering in the dynamic stochastic block model. Electronic Journal of Statistics, 13(1):678-709
[33] Robinson, L. F. and Priebe, C. E. (2012). Detecting time-dependent structure in network data via new class of latent process models. arXiv preprint arXiv:1212.333
[34] Rossi, R. A. and Ahmed, N. (2015). The network data repository with interactive graph analytics and visualization. In AAAI.
[35] Rubin-Delanchy. P. (2020). Manifold structure in graph embeddings. In Proceedings of the Thirty-fourth Conference on Neural Information Processing Systems.
[36] Rubin- Rubin-Delanchy, P., Cape, J., Priebe, C. E.,, and Tang, M. (2020). statistical interpre- tation of spectral embedding: the generalised random dot product graph. arXiv preprint 3.
[37] Sanna Passino, F., Bertiger, A. S., Neil, J. C., and Heard, N. A. (2019). Link prediction in dynamic networks using random dot product graphs. arXiv preprint 19111:191..10419.
12

---

[38] Sanna Passino, F., Heard. N. A., and Rubin-Delancee P. (2020). Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel. arXiv e-prints, pages arXiv-2011.
[39] Sarkar, P. and Moore, A. W. (2005). Dynamic social network analysis using latent space models. ACM SigKDD Explorations Newsletter, 7(2):31-40.
[40] Scheinerman, E. R. and Tucker, K. (2010). Modeling graphs using dot product representations. Computational statistics, 25(1):1-16.
[41] Seshadhri, C., Sharma, A., Stolman, A., and Goel, A. (2020). The impossibility of low-rank representations for triangle-rich complex networks. Proceedings of the National Academy of Sciences, 1 11((1)):63115500
[42] Seto, S., Zhang. W., and Zhou, Y. (2015). Multivariate time series classification using dynamic time warping template selection for human activity recognition. In 2015 IEEE Symposium Series on Computational Intelligence, pages 1399-1406. IEFE.
[43] Sewell, D. K. and Chen, Y. (2015). Latent space models for dynamic networks. Journal of the American Statistical Association, 1106512):1446-15577
[44] Stehlé, J., Voirin, N., Barrat, A., Cattuto, C., Isella, L., Pinton, J.-F., Quaggiotto, M., Van den Broeck, W., Régis, C., Lina, B., al. (2011). High-resolution measurements of face-to-face contact patterns in a primary school. PloS one, 6(8):e23176.
[45] Turbbull, K. (2020). Advancements in latent space network modelling. PhD thesis, Lancaster University.
[46] Udell, M. and Townsend, A. (2019). Why are big data matrices approximately low rank? SIAM Journal on Mathematics of Data Science, 1(1):144-160.
[47] Xie, Y., Li, C., Yu, B., Zhang, C., and Tang, Z. (2020). A survey dynamic network embedding. arXiv preprint arXiv:2006. 08093.
[48] Xing, E. P., Fu, W., Song, L., et al. (2010). A state-space mixed membership blockmodel for dynamic network tomography. Annals of Applied Statistics, 4(2):535-566.
[49] Xu, K. (2015). Stochastic block transition models for dynamic networks. In Artificial Intelli- gence and Statistics, pages 1079-100 1087. PMLR.
[50] Xu, K. S. and Hero, A. O. (2014). Dynamic stochastic blockmodels for time-evolving social networks. IEEE Journal of Selected Topics Signal Processing, 8(4):552-562.
[51] Xue, G., Zhong, M., Li, J., Chen, J., Zhai, C., and Kong, R. (2021). Dynamic network embedding survey. arXiv preprint arXiv:2103. 15447.
[52] Yang, T., Chi, Y., Zhu, S., Gong, Y., and Jin, R. (2011). Detecting communities and their evolutions in dynamic social networks- Bayesian approach. Machine learning, 82(2):157-189.
[53] Zhao, B., Lu, H., Chen, S., Liu, J., and Wu, D. (2017). Convolutional neural networks for time series classification. Journal of Systems Engineering and Electronics, 28(1):162-11) 169.
[54] Zhu, I.., Guo, D., Yin, J., Ver Steeg, G., and Galstyan, (2016). Scalable temporal latent space inference for link prediction in dynamic social networks. IEEE Transactions on Knowledge and Data Engineering. 28 28(10)2776-2777.
[55] Zhu, M. and Ghodsi, A. (2006). Automatic dimensionality selection from the scree plot via the use of profile likelihood. Computational Statistics & Data Analysis, 51(2)918-933
13


Reviews:
[{"review_id": "zzLkBTMjMB4", "reviewer": "Reviewer_BPvN", "summary": "The paper studies the problem of stability of an embedding of a dynamic network. This corresponds to deriving a time varying vectorial representation for each node such that nodes behaving similarly at a given time have similar positions (cross-sectional stability), and a node behaving similarly across different times has a constant position (longitudinal stability). Assuming  a dynamic random geometric graph model, the authors show for this model that (1) the unfolded adjacency spectral embedding (UASE) procedure satisfies the aforementioned stability properties, and (2) other methods such as omnibus or time-averaged spectral embedding lack one form of stability.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The problem studied is an interesting one since dynamic/multi-layer graph related problems appear in many applications. The main issue I have is that the overall presentation of the paper lacks clarity in general, which makes it quite difficult to follow and understand at many places. I have elaborated on this below. Keeping aside this issue for now, I think the technical results in the paper are interesting. However, I am not completely convinced whether they are strong enough for acceptance. The UASE method is but one of several other (much more robust) methods that exist in the literature for handling dynamic or more generally, multi-layer graphs. Therefore, while it is interesting to mathematically analyze UASE, I am currently inclined to believe that this is insufficient for acceptance.\n\nFurther remarks:\n\n1.\tWhen the latent position model is defined, it will be good to explain at that point how the SBM and other standard community models are obtained as special cases. This is presently done much later on pg. 5.\n\n2.\tThe parameter $d$ determines the length of the vector in the embedding, but it should be explained how one can choose this, and what it intuitively corresponds to. For e.g., in the setting where the graphs are identical copies of each other, does it correspond to the number of communities? \n\n3.\tThere needs to be a notations paragraph that outlines the notation used throughout, this will improve the exposition. Moreover, at some places, it will help to specify the dimensions of the underlying quantities. For e.g. in line 10, $\\mathbf{Z}_i \\in \\mathbb{R}^{k \\times T} ?$ for $i=1,\\dots,n$?\n\n4.\tIn line 110, what is GRDPG? In the eigendecomposition of f in eq. (2), there needs to be some explanation on how the smoothness of f is related to the eigenvalues, and some examples of f for which $D < \\infty$. \n\n5.\tProposition 1 is particularly difficult to interpret – partially because of unclear notation (what are the sizes of $\\mathbf{X}, \\mathbf{Y}$ and $\\mathbf{\\Lambda}$? How are $\\mathbf{X}, \\mathbf{\\Lambda}$ defined?), and partially because no explanation is provided as to why this proposition is useful. \n\n6.\tAs a general remark, it will help to divide a section using “\\paragraph” with an appropriate heading for each paragraph in order to make the exposition clearer for the reader. \n\n7.\tIn eq. (4), it is unclear to me what the parameter $d$ corresponds to intuitively and how we can choose it, this is related to my comment earlier. In line 134, the sparsity factor has a $\\sqrt{n}$ in the denominator but shouldn’t this perhaps be $n$ (in light of the error scaling in theorem 2). The statement of theorem 2 should also have the condition on $\\rho_n$. It is also not clear to me how the bound depends on $d$. Clearly $d$ can depend on $n$ so it can’t be hidden within big-Oh. For the same reason, it should also be clarified how $\\rho_n$ depends on $d$.\n\n8.\tIt is important to sketch the proof ideas for Theorems 2 and 3 since these are the main results of the paper. Also, in Corollary 5, the first bullet perhaps has a typo since $t’$ should be $t$? In the second bullet, what does “under a sparse regime mean”?\n\n-------------------------------- Post author response ---------------------------\n\nI thank the authors for their detailed response to my comments and for the clarifications regarding certain technical aspects which I hope will be taken into account in the revision. However, I personally do not find the results in the paper to be strong enough in their current form, and so, I will keep my original score of 5. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Section 6 does discuss potential societal impact, but I couldn’t find a discussion on the limitations of the results in the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "around 12 hours"}, "extra_text": {}}, {"review_id": "mnLJdeETlt", "reviewer": "Reviewer_irCJ", "summary": "The paper analyses several consistency (stability) properties of the unfolded adjacency embedding (UASE), a spectral embedding method for dynamically evolving graphs. Specifically it is shown that UASE yields cross-sectionally and longitudinally stable embeddings. This is contrasted with other (spectral) embedding methods which generally do not achieve these properties.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The paper mainly focuses on the analysis of a particular spectral embedding method, UASE, and establishes some important properties of this spectral embedding. The obtained results are overall interesting and appear to have been established in a rigorous way (admittedly I did not check all the fine details).\n\nIn my view, the strongest contribution of this paper is a theoretical one (as encapsulated by the provided theorems); the results are not groundbreaking but significant enough, in my opinion, as the proven stability properties are important for application purposes.\nMy strongest concerns with the paper are with respect to the presentation of the results and the novelty of this work.\n\nIn terms of presentations I found the paper to be of very mixed quality. The introduction, the motivating example and the examples read sufficiently well. However, I found the the \"main sections\" 3 and 4 to be relatively poorly written and difficult to parse.\nA few examples:\n- \"We can associate to the function f a compact, self-adjoint operator\" --> how is this done precisely? Are we effectively assuming that we have a graphon like structure here?\n- the acronyms GRDPG, RDPG etc are never defined, \\Phi is not defined and moreover there is another map \\phi appearing before, which may lead to confusion\n- the linear maps in Proposition 1, and in particular the dimension d_t are never really explained.\n\nOne major point that is not discussed at all is the low-rank assumption on f that is made and its consequences, which seems crucial.\nHow can this be relaxed? What effects would there be if the assumption is dropped? Would t be sufficient if the eigenvalues are decaying fast enough?\n\nSimilarly the assumption on the sparsity of the results would appear to merit more discussion. It appears that the authors consider effectively dense graphs; whereas in most practical applications we would encounter sparse networks.\n\nIt would also be of interest to get some insight into how these theoretical results differ from previous results on (low rank network models) in terms of the additional difficulties etc. that are encountered in the proofs. At first glance it seems that the results presented here are reasonably straightforward extensions of results that have been obtain on random dot product graphs etc.\n\n---------------\nUpdate after author response.\n\nAs said in my review my strongest concern was with the presentation of some of the results, and the answer provided by the authors appears satisfying to me. I have thus raised my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The discussion on the limitations of the methods appear to be very short. In particular the assumption of an underlying low-rank distribution and of the sparsity level are not discussed in sufficient detail in my opinion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "j06AI7vZqZ8", "reviewer": "Reviewer_x9sR", "summary": "This paper studies the problem of embedding dynamic networks, i.e., providing a node embedding representation for a network that varies with time (a vector representation for each node at each time point). The paper provides a theoretical development showing that an existing method denominated unfolded adjacency spectral embedding (UASE) satisfies desirable stability properties in the embedding across time and across nodes.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The paper nicely motivates the need for stable embeddings for dynamic networks in the introduction. The example in Section 2 is a good illustration of the main concept, though somewhat naive. In particular, the fact that finding independent embeddings for each time point (right column) leads to embeddings that are not stable across time is quite expected, but I think that it is fine to show this as a motivation. I enjoyed the mathematical exposition in Section 3, which is the bulk of the contribution. The result is shown for a fairly general setting, and the discussion after corollary 5 about implications for specific random graph models is helpful. \n\nSection 4, on the other hand, is in my view a weak point of the paper. After having established a stability result for UASE, the authors want to show that other methods are not stable. To do this, they start with a high-level somewhat imprecise categorization of the existing methods into three classes, where the distinction between class 1 and 3 is very thin and the authors justify through an example in (9). The authors then give a few examples of how some of the methods in these categories are not stable. Somewhat ambiguous sentences like “seemingly never providing both [types of stability]” are a bit in contrast with the mathematical precision of Section 3.\n\nThe experiments in Section 5 are modest but achieve their objective. Since the paper is not proposing a new methodology but rather a theoretical analysis of stability, there is no need for exhaustive experimentation.\n\nAll in all, I deem this paper as a nice analytical contribution to a timely problem.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no comment.", "review_text": "", "extra_scores": {"ethical_concerns": "no comment.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "H7G0FA4l1tw", "reviewer": "Reviewer_YyaY", "summary": "In this paper the authors study the problem of graph embedding for a series of time-evolving graphs, under the general Random Dot Product Graph framework. They focus on the UASE strategy, comparing it with omnibus and vanilla ASE of each graph, and they provide empirical and theoretical proofs of its capability to preserve the locations of nodes along time, and also to capture relationships between similar nodes in each embedding.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "As stated by the authors, the originality of the paper is not on the UASE method itself, but in the analysis of its properties and the proofs of the results regarding those stability properties. The related work is correctly cited, including some recent papers, and a couple of very relevant reviews. And the difference between this work and the existing literature is clear.\nAs far as I understand, the results are new.\n\nThe paper is also techically sound. The results on the convergence of the embeddings are in line with previous recent results, and provide important properties. \nThe experimental evaluation is correct and convincing. However, I would have liked to see the performance of omnibus and independent ASE for the Lyon dataset, to further show the strenghts of UASE respect to those two.\nAlso, I think there should be a comparison on the complexity of the three methods. Basically all three are based on a spectral decomposition, but the dimension of the matrices are different (and in the case of independent ASE, there are T decompositions of $n\\times n$ matrices).\n\n\nThe paper is very well written. Both the introduction and the motivating example are very didactical and illustrative. There are some very minor undefined concepts, but in general the quality of the presentation is excellent.\n\nI think the results of this paper are important. It provides a very useful (existing) technique, UASE, now with theoretical guarantees of spatial and temporal consistency.\n\nMinor comments:\n\nIn Fig1, the \"First two dimensions of the embeddings\" are shown, for the tree methods. I couldn't find the original dimension of the embedding used for this example (is it 2 originally?)\n\n(very minor) The MRDPG abbreviation is not defined per se. It is written (multilayer RDPG) two lines above the use of MRDPG.\nAlso, it would be nice to add a sentence saying that the MRDPG is like a RDPG model but for the concatenaton of the adjacency matrices, or something short like that.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is a line, stating that the case when T grows presents significant computational challenges. I think this should be further stressed.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper's main contribution is to prove that a specific spectral embedding scheme applied to time-varying graphs, which associates to each node a corresponding time series, ensures in a particular latent position model of random graph two types of stability (cross-sectional and longitudinal). The theory is supplemented by experiments done on a dataset from school in Lyon, France describing student relationships over time. The reviewers generally appreciated the paper's contribution, one review evaluating the results to be slightly below the bar for acceptance. 
In agreement with the reviews, I believe the paper's objective to be of interest and to be successfully achieved by the authors' work. While the results may in retrospect appear natural and somehow not very surprising, I would not hold this against the authors, hence my recommendation to accept. 
Decision: Accept (Poster)