Spectral embedding for dynamic networks with stability guarantees
Year: 2022

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.

heading: 1 Introduction
text: 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 a vector representation, Ŷ(t)i 2 Rd, for every node i and time t, which could be used for a diversity of downstream analyses, such as 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 it is reasonable to try to establish a certain statistical guarantee.
The novelty of this paper is not to propose a new procedure. Instead, it is 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 ) 2 {0, 1}n⇥n, where A(t)ij = 1 if nodes i and j form an edge at time t, UASE computes the rank d matrix factorisation of A := (A(1)| · · · |A(T )) to obtain A ⇡ X̂Ŷ> using the singular value decomposition (precise details later). The matrix Ŷ 2 RnT⇥d contains, as rows, the desired representations Ŷ(1)
1 , . . . , Ŷ(1)n , . . . , Ŷ (T ) 1 , . . . , Ŷ(T )n .
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The original motivation for UASE was to analyse multilayer (or multiplex) graphs under an appropriate extension of the random dot product graph model [17]. To evaluate UASE and other procedures on the task of dynamic network embedding, we instead consider the dynamic latent position model
A(t)ij ind⇠ Bernoulli ⇣ f n Z(t)i ,Z (t) j o⌘ , (1)
for 1  i < j  n, t 2 [T ], where Z(t)i 2 Rk represents the unknown position of node i at time t, and f : Rk ⇥ Rk ! [0, 1] is a symmetric function. This model is well-established [39, 22, 15, 16, 33, 23, 9, 43, 11, 10], with recent reviews by [20] and [45], and inference usually proceeds on the basis of a parametric model for f (e.g. logistic in the latent position distance [39]) and for the dynamics of Z(t)i (e.g. a Markov process [39]). The model also includes the dynamic degree-corrected, mixed-membership and standard stochastic block models as special cases, which were studied in [48, 52, 14, 29, 50, 49, 31, 4, 32, 19].
To make statistical sense of UASE under this latent position model, we must somehow connect its output Ŷ(t)i to Z (t) i . To this end we construct a canonical representative of Z (t) i , denoted Y (t) i , that UASE can be seen to estimate. Although we make some regularity assumptions on f and the Z(t)i , 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, we do not make a Markovian assumption on the evolution of Z(t)i 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 s and t respectively. In such cases, ideally we would have Ŷ(s)i ⇡ Ŷ (t) j . Two special cases are: 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).
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(t), alternately exhibit one form of stability and not the other. More generally, we find existing procedures [6, 27, 40, 8, 54, 7, 28, 5, 4, 32, 37, 19] tend to trade one type of stability off against the other, e.g. via user-specified cost functions. As a 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 so different from the others, we still feel it makes an interesting addition.
Our central contribution is to prove that UASE asymptotically provides both longitudinal and crosssectional stability: for two nodes, i and j, behaving similarly at times s and t respectively, we have Ŷ(s)i ⇡ Ŷ (t) j and, moreover, Ŷ (s) i and Ŷ (t) j 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 ! 1, but T fixed so that, for example, our results are relevant to the case of two large graphs. The alternative regime where T ! 1 grows but n is fixed is not easily handled by existing theory and to provide constant updates to UASE (or omnibus embedding) in a 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 a two-step dynamic stochastic block model, while highlighting the instability of omnibus and independent spectral embedding. In Section 3, we prove a central limit theorem for UASE under a dynamic latent position model, and demonstrate that the distribution satisfies both stability conditions. In Section 4, we review the stability of other dynamic network embedding procedures. Section 5 presents an example of UASE applied to a dynamic network of social interactions in a French primary school, with a dynamic community detection example given in the main text and a further classification example provided in the Appendix. Section 6 concludes.

heading: 2 Motivating example
text: Suppose it is of interest to uncover dynamic community structure, including communities changing, merging or splitting. The dynamic stochastic block model [52, 50] provides a 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 1 and 2, we have the following inter-community link probability matrices,
B(1) =
0
BBBB@
0.08 0.02 0.18 0.10
0.02 0.20 0.04 0.10
0.18 0.04 0.02 0.02
0.10 0.10 0.02 0.06
1
CCCCA , B(2) =
0
BBBB@
0.16 0.16 0.04 0.10
0.16 0.16 0.04 0.10
0.04 0.04 0.09 0.02
0.10 0.10 0.02 0.06
1
CCCCA .
At time 1 there are four communities present, for example, a node of community 1 connects with a node of community 3 with probability 0.18. At time 2, this matrix changes so that communities 1 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 1. 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 d1 = 4 and d2 = 3. For visualisation, we show the leading two dimensions for each embedding. Given the dynamics described above, we contend that the following properties would be desirable:
1. Cross-sectional stability: The embeddings for communities 1 and 2 at time 2 are close. 2. Longitudinal stability: The embeddings for community 4 at times 1 and 2 are close.
Figure 1 illustrates 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 merge at
time 2), whereas independent spectral embedding only has cross-sectional stability (the red point cloud is at different locations over the two time points).

heading: 3 Theoretical background and results
text: We consider a sequence of random graphs distributed according to a dynamic latent position model, in which the latent position sequences (Z(t)i )t2[T ] (where we use the shorthand [T ] = {1, . . . , T}) are independent of each other, and identically distributed according to a joint distribution F on ZT , for a bounded subset Z of Rk. We emphasise that for a fixed i the latent positions Z(t)i and Z (t0) i 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 L2(Rk ⇥Rk), and consequently may define a compact, self-adjoint operator A on L2(Rk) by setting
Ag(x) =
Z
Rk f(x, y)g(y)dy (2)
for all g 2 L2(Rk). The operator A has a—possibly infinite—sequence of non-zero eigenvalues 1 2 . . . with corresponding orthonormal eigenfunctions u1, u2, . . . 2 L2(Rk), such that Auj = juj (for further details, see for example [35]). We shall make the simplifying assumption that A has a finite number of non-zero eigenvalues, in which case f admits a canonical eigendecomposition
f(x,y) = DX
i=1
iui(x)ui(y), (3)
assumed to hold everywhere, where after relabelling we may assume that | 1| . . . | D|. Several families of functions satisfy the finite rank assumption D < 1, such as the multivariate polynomials [35]. Moreover, several existing statistical models can be written as dynamic latent position network models in which D < 1, including the dynamic mixed membership, degreecorrected, and standard stochastic block models. To assume D < 1, 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 [46] 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 [41]. In such a setting, we anticipate that UASE is still consistent and stable if d 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(1), . . . ,A(T ) are jointly distributed according to a multilayer random dot product graph model.
The multilayer random dot product graph model (MRDPG, see [17]) is a multi-graph analogue of the generalised random dot product graph model [36], and is characterised by the existence of matrices ⇤(t) 2 Rd⇥dt and random matrices X 2 Rn⇥d and Y(t) 2 Rn⇥dt (generated according to some joint distribution G) such that
A(t)ij ind⇠ Bernoulli Xi⇤ (t)Y(t)>j
(4)
for each t 2 [T ] and i, j 2 [n], where Xi and Y(t)j denote the ith and jth rows of X and Y(t) respectively.
We refer the reader to the supplemental material for full details of the proof of Theorem 1, but note that given knowledge of the function f and the underlying distribution F we can construct explicit
maps ' : RTk ! Rd and 't : Rk ! Rdt , producing row vectors, and matrices ⇤(t) 2 Rd⇥dt such that
f(Z(t)i ,Z (t) j ) = Xi⇤ (t)Y(t)>j , (5)
where Xi = '(Zi),Y (t) j = 't(Z (t) j ) and Zi = (Z (1) i | · · · |Z (T ) i ) 2 RTk, for each t 2 [T ] and i, j 2 [n]. Consequently, each Gram matrix P(t) =
f(Z(t)i ,Z (t) j ) i,j2[n] (6)
admits a factorisation into a product of low-rank matrices, in which the matrix whose rows are the vectors '(Zi) appears as a common factor. The dimensions dt and d are precisely the ranks of the matrices P(t) and their concatenation P = (P(1)| · · · |P(T )) respectively. In the theory that follows we 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 [55]).
We can extend our model to incorporate a range of sparsity regimes by scaling the function f by a sparsity factor ⇢n, which we assume is either constant and equal to 1, or else tends to zero as n grows, corresponding to dense and sparse regimes respectively. When this factor is present, the maps ' and 't are scaled by a factor of ⇢ 1/2 n .
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 a common factor in the decomposition of each of the Gram matrices P(t) that gives rise to the stability properties previously demonstrated in the embeddings Ŷ(t), as this matrix in a sense acts as an anchor for the individual point clouds.
In [17] UASE is used to obtain two multi-graph 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 ) 2 {0, 1}n⇥n, embedding dimension d
1: Form the matrix A = (A(1)| · · · |A(T )) 2 {0, 1}n⇥Tn (column concatenation) 2: Compute the truncated singular value decomposition UA⌃AV>A 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̂ = VA⌃ 1/2 A 2 RTn⇥d and create sub-embeddings Ŷ(t) 2
Rn⇥d where Ŷ = (Ŷ(1); . . . ; Ŷ(T )) (row concatenation) return node embeddings for each time period Ŷ(1), . . . , Ŷ(T )
Replacing A with P in this construction yields the noise-free embeddings Ỹ(t), whose rows are known to be linear transformations of the vectors 't(Z (t) i ) (see the supplemental material for further details). A desirable property of UASE is that since the matrices A(t) follow an MRDPG model there exist known asymptotic distributional results for the embeddings Ŷ(t). In order to ensure the validity of these results, we will make the assumption that the sparsity factor ⇢n satisfies ⇢n = !(n 1 logc(n)) for some universal constant c > 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 n. To achieve this for less than logarithmic growth would be impossible, by any algorithm, because it would violate the information-theoretic sparsity limit for perfect community recovery under the stochastic block model [1]. 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. to sparsity or heterogeneous degrees), such as based on the regularised Laplacian [3] or non-backtracking matrices [21], but it is an open and interesting question how to extend them to the dynamic graph setting to achieve both cross-sectional and longitudinal stability.
The first of our distributional results states that after applying an orthogonal transformation—which leaves the structure of the resulting point cloud intact—the embedded points Ŷ(t)i converge in the Euclidean norm to the noise-free embedded points Ỹ(t)i as the graph size grows:
Proposition 2. There exists a sequence of orthogonal matrices W̃ 2 O(d) such that
max i2{1,...,n}
Ŷ(t)i W̃ Ỹ (t) i
= O ⇣ log 1/2 (n)
⇢1/2n n1/2
⌘ (7)
with high probability for each t.
The matrices W̃ are unidentifiable in practice, but are defined to be the solution to the one-mode orthogonal Procrustes problem
W̃ = argmin Q2O(d) kUAQ UPk2F + kVAQ VPk2F , (8)
where k·k2F 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̃(t) 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 ⇣ = (⇣1| · · · |⇣T ) ⇠ F , and for z 2 Z define
⌃t(z) =
8 <
: E⇣
h f(z, ⇣t) 1 f(z, ⇣t) · '(⇣)>'(⇣) i if ⇢n = 1
E⇣ h f(z, ⇣t) · '(⇣)>'(⇣) i if ⇢n ! 0. . (9)
Then there exists a deterministic matrix R⇤ 2 Rd⇥d and a sequence of orthogonal matrices W 2 O(d) such that, given z 2 Z , for all y 2 Rd and for any fixed i 2 [n] and t 2 [T ],
P ⇣ n1/2(Ŷ(t)i W̃ Ỹ (t) i )W  y | Z (t) i = z ⌘ ! y,R⇤⌃t(z)R > ⇤ . (10)
As in our previous results, the matrices W and R⇤ can be explicitly constructed given knowledge of the underlying function f and distribution F (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 methods, 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 (z0, t0) are exchangeable if f(z, ⇣t) = f(z0, ⇣t0) with probability one, where ⇣ = (⇣1| · · · |⇣T ) ⇠ F , and that the positions are exchangeable up to degree if f(z, ⇣t) = ↵f(z0, ⇣t0) for some ↵ > 0. Equivalently, (z, t) and (z0, t0) are exchangeable if conditional on Z(t)i = z and Z (t0) j = z 0 the ith row of P(t) and jth row of P(t 0 ) are equal with probability one. Definition 4. Given a generic method for dynamic network embedding, with output denoted (Ẑ(t)i )i2[n];t2[T ], define the following stability properties:
1. Cross-sectional stability: Given exchangeable (z, t) and (z0, t), Ẑ(t)i and Ẑ (t) j are asymptoti-
cally equal, with identical error distribution, conditional on Z(t)i = z and Z (t) j = z 0.
2. Longitudinal stability: Given exchangeable (z, t) and (z, t0), Ẑ(t)i and Ẑ (t0) i are asymptoti-
cally equal, with identical error distribution, conditional on Z(t)i = Z (t0) i = z.
The following result then shows that UASE exhibits both types of stability:
Corollary 5. Conditional on Z(t)i = z and Z (t0) j = z 0, the following properties hold:
1. If (z, t) and (z0, t0) are exchangeable then Ŷ(t)i and Ŷ (t0) j are asymptotically equal, with
identical error distribution. 2. If (z, t) and (z0, t0) are exchangeable up to degree then Ŷ(t)i and ↵Ŷ (t0) j are asymptotically
equal and, under a sparse regime, their error distributions are equal up to scale, satisfying ⌃t(z) = ↵⌃t0(z0).
We can gain insight into our theoretical results by applying them in the context of common statistical models. Under the dynamic stochastic block model of Section 2, a pair (z, t) and (z0, t0) are
exchangeable if and only if the corresponding rows of B(t) and B(t 0 ) are identical. Proposition 3 then predicts that the point cloud obtained via UASE should decompose into a finite number of Gaussian clusters, as we observe in Figure 1. Moreover, when combined with Corollary 5 the equality of the fourth rows of B(1) and B(2) implies that we should expect identical clusters (centre and shape) corresponding to the fourth community at both time points (indicating longitudinal stability) and similarly the equality of the first and second rows of B(2) tells us that the communities should be indistinguishable at the second time point (indicating cross-sectional stability), behaviours we observe in Figure 1. Under degree-correction [18, 29], Corollary 5 indicates that we should at least observe cross-sectional and longitudinal stability along ‘rays’ representing communities, a behaviour that is exhibited in Figure 2.

heading: 4 Comparison
text: In this section we investigate the stability properties of alternatives to UASE. Table 1 shows the stability of the three embedding algorithms described in Section 2 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(1), . . . ,P(T ). A method found to be unstable in this noise-free condition is not expected to be stable when the matrices are replaced by their noisy observations A(1), . . . ,A(T ).
[40, 8, 4, 32, 37, 19] Joint embedding argminŶ(1),...,Ŷ(T ) ↵ P t CS(Ŷ
(t),A(t)) Neither [27, 7, 54, 5, 28] +(1 ↵) P t CT(Ŷ (t), Ŷ(t+1))
The omnibus method computes the spectral embedding of the matrix Ã 2 {0, 1}nT⇥nT where the block Ãs,t 2 Rn⇥n is given by (A(k) +A(`))/2 2 Rn⇥n and we denote by P̃ 2 [0, 1]nT⇥nT the noise-free counterpart of Ã. If (z, t) and (z, t0) are exchangeable, then, conditional on Z(t)i = Z (t0) i = z, the rows P̃n(t 1)+i and P̃n(t0 1)+i are equal. However, if (z, t) and (z0, t) are exchangeable, then, in general, P̃n(t 1)+i 6= P̃n(t 1)+j when Z (t) i = z and Z (t) j = z
0. One can demonstrate that two rows of P̃ are equal if 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(t) 2 {0, 1}n⇥n. If (z, t) and (z0, t0) are exchangeable, then, conditional on Z(t)i = z and Z (t0) j = z 0, the rows P(t)i and P (t0) j are equal. If t = t
0 the embeddings of nodes i and j are equal, however, embeddings between different graphs are subject to (possibly indefinite) orthogonal transformations Q(t) which, if P(t) 6= P(t0), differ in a non-trivial way (i.e. beyond simply reflecting the ambiguity of choosing eigenvectors in the spectral decomposition of P(t)). Therefore, independent adjacency spectral embedding provides cross-sectional but not longitudinal stability. The same arguments extend to other independent embeddings.
Separate embedding covers a collection of embedding techniques separately applied to time-averaged matrices, Ā(t) = P k wkA (t k) where wk are non-negative weights, and A(t) may be replaced by
another matrix representation of the graph such as the normalised Laplacian. The weights may be constant, e.g. wk = 1/t for all k [40, 4], exponential forgetting factors wk = (1 )k [8, 19], chosen to produce a sliding window [32], based on a time series model [37], and more. In general, temporal smoothing results in two nodes behaving identically at time t 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., w0 = 1 and wk = 0, reducing to independent embedding).
Joint embedding techniques generally aim to find an embedding to trade-off two costs: a ‘snapshot cost’ (CS) measuring the goodness-of-fit to the observed A(t), and a ‘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):
argmin Ă(1),...,Ă(T ) ↵
TX
t=1
kA(t) Ă(t)k2F + (1 ↵) T 1X
t=1
kĂ(t) Ă(t+1)k2F , (11)
where ↵ 2 [0, 1], subject to a low rank constraint on Ă(1), . . . , Ă(T ), where Ŷ(t) is the spectral embedding of Ă(t). It is easy to see that a change affecting only a fraction of the nodes will result in a change of all node embeddings, precluding both cross-sectional and longitudinal stability (again apart from contrived cases, e.g. when ↵ = 1).
For the complexity calculations, we assume a dense regime in which the k-truncated singular value decomposition of an m-by-n matrix is O(kmn) [13]. Independent embedding is more efficient than UASE, on account of P t dt  dT , 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.

heading: 5 Real data
text: The Lyon primary school data set shows the social interactions at a French primary school over two days in October 2009 [44]. 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 radiofrequency identification devices worn by participants (10 teachers and 232 students gave consent to be included in the experiment) were in close proximity over an interval of 20 seconds and recorded as a pair of anonymous identifiers together with a timestamp. The data are available for download from the Network Repository website1 [34].
A 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 a 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(1), . . . ,A(20) each with n = 242 nodes. Where a node is not active in a given time window, it is still included in the graph as 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 A = (A(1)| · · · |A(20)), an estimated embedding dimension d̂ = 10 was obtained using profile likelihood [55] and we construct the embeddings Ŷ(1), . . . , Ŷ(20) 2 Rn⇥10, taking approximately five seconds on a 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 a degree-corrected stochastic block model, and the distance along the ray is a measure of the node’s activity level [25, 30, 38]. 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).
1https://networkrepository.com

heading: 5.1 Clustering
text: Following recommendations regarding community detection under a degree-corrected stochastic block model [38], we analyse UASE using spherical coordinates ⇥(t) 2 [0, 2⇡)n⇥9, for t 2 [T ]. Since UASE demonstrates cross-sectional and longitudinal stability, we can combine the embeddings into a single point cloud ⇥ = (⇥(1)>| · · · |⇥(T )>)> 2 RnT⇥9 where each point represents a student or teacher in a particular time window. This allows us to detect people returning to a previous behaviour in the dynamic network. We fit a Gaussian mixture model with varying covariance matrices to 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 a posteriori Gaussian cluster membership to each student in each time window.
Figure 3 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 in class 1A spend their classroom time (as opposed to break time) assigned to cluster 1 or cluster 25. This highlights the importance of longitudinal stability in UASE, as we are detecting points in the embedding returning to some part of latent space.
There are also instances of multiple school classes being assigned the same cluster at the same time period, for example, on the morning of day 1, classes 5A and 5B are mainly in cluster 28 suggesting
they are having a joint lesson, and we 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 1A–2B) mingle to form a larger cluster, as do the older students (classes 4A–5B), potentially explained by the cafeteria needing two sittings for lunch for space reasons [44]. This highlights the importance of cross-sectional stability in UASE, as it allows the grouping of nodes behaving similarly in a specific time window, irrespective of their potentially different past and future behaviours.

heading: 6 Conclusion
text: We prove that an existing procedure, UASE, allows dynamic network embedding with longitudinal and cross-sectional stability guarantees. These properties make a range of subsequent spatio-temporal analyses possible using ‘off-the-shelf’ techniques for clustering, time series analysis, classification and more. While our goal is to facilitate exploratory data analysis across a 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 identity, for example, across online social networks. We hope to raise awareness of such possibilities, for instance, in the context of network data anonymisation.
Funding Transparency Statement
Andrew Jones and Patrick Rubin-Delanchy’s research was supported by an Alan Turing Institute fellowship. Ian Gallagher’s research was supported by an EPSRC PhD studentship.

Review summaries:
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.

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.