# An embedding-based distance for temporal graphs

Lorenzo Dall’Amico a,†, Alain Barrat b, Ciro Cattuto a

aISI Foundation, Turin, 10126, Italy
b Aix-Marseille Univ, Université de Toulon, CNRS, CPT, Marseille 13009, France
†Corresponding to<EMAIL_ADDRESS>
###### Abstract

We define a distance between temporal graphs based on graph embeddings built
using time-respecting random walks. We study both the case of matched graphs,
when there exists a known relation between the nodes, and the unmatched case,
when such a relation is unavailable and the graphs may be of different sizes.
We illustrate the interest of our distance definition, using both real and
synthetic temporal network data, by showing its ability to discriminate
between graphs with different structural and temporal properties. Leveraging
state-of-the-art machine learning techniques, we propose an efficient
implementation of distance computation that is viable for large-scale temporal
graphs.

#### Keywords: Network science, Temporal networks, Graph distance, Graph
embedding

## Introduction

Graphs are ubiquitous mathematical entities formed by a set of _nodes_ and one
of _edges_ connecting them [1, 2, 3]. They can model a wide range of
interacting systems, such as social [4, 5], technological [6], spatial [7] and
biological networks [8] and owe their popularity to their ability to encode
the complex relational structure of these systems. Real-world systems,
moreover, often have temporal properties that cannot be encoded in static
graphs and call for modeling based on time-resolved network representations,
known as _temporal graphs_ [9]. Examples of these include transportation [10]
and ecological networks [11], face-to-face interactions [12, 13, 14],
collaboration networks [15, 16, 17], etc.

Given their ubiquitous use in representing such diverse kinds of systems, it
is crucial to be able to compare them. In fact, defining and computing a
similarity measure between pairs of graphs [18] underpins many important
applications and tasks, including machine learning tasks such as graph
classification. However, given graphs’ high dimensionality and structural
complexity, many different notions of _distance_ can be devised, capturing
different properties of interest. Because of this, many definitions of
distance for static graphs have been introduced, as reviewed in Refs. [19, 20,
21, 22, 23]. One of the simplest approaches is the _edit distance_ [24] that
counts the number of elementary changes (edge or node removal or addition)
needed to transform one graph into another. This method only accounts for
local information and suffers from the _curse of dimensionality_ [25].
Approaches involving the global graph structure are based on matrix inversion
[26, 27] but generally have a high computational cost, and approximations are
needed to achieve satisfactory computational performance. The above methods
are designed for graph pairs with known correspondence between their nodes, a
case we will refer to as _matched_ graphs. The more general case of
_unmatched_ graphs involves computing distances for pairs of graphs for which
a mapping between nodes is unavailable, and the graphs may have a different
size. In this case, one can extract and compare adequately chosen sets of
graph features, as done in Refs. [28, 29] or focus on the eigenvalues of
appropriate matrix representations [30, 31, 32, 33]. Also, in this case, the
computational complexity is a bottleneck, and approximate heuristics are often
required [19].

In the case of temporal graphs, the temporal dimension adds to the complexity
of graph comparison. Many of the aforementioned distance measures for static
graphs have been used to study temporal graphs [34], typically to compare the
state of the graph at different points in time [35, 36, 37]. Here, we study
the problem of comparing temporal graphs _as a whole_. In the temporal case,
few notions of distance have been proposed: Ref. [38] defines a method to
compare temporal graphs based on a set of features that can be tailored to a
specific research question; Ref. [39] addresses our same problem of temporal
graph comparison but assumes the graphs to be _matched_ and is computationally
inefficient; Ref. [40] only considers the _unmatched_ case and uses the
comparison of temporal paths statistics to provide a definition of
_dissimilarity_ (rather than distance).

Here, we propose a computationally efficient method to compute a distance
metric between pairs of temporal graphs, considering both the matched and
unmatched cases. We build our comparison on top of graph embeddings,
leveraging ideas from both the local and global approaches mentioned above,
and encoding differences at the topological as well as at the temporal levels.
Commented Python code for implementing our method is available at
github.com/lorenzodallamico/G-DynaDist.

## Temporal graphs definitions

Before delving into the details of our main contribution, let us first set
some basic definitions.

######  Definition 1 (Temporal graph)

A temporal graph $\mathcal{G}(\mathcal{V},\mathcal{E},\mathcal{W})$ is a tuple
where $\mathcal{V}$ is a set of $n$ nodes, $\mathcal{E}$ a set of temporal
edges between nodes, and $\mathcal{W}$ a set of edge weights. All edges
$e\in\mathcal{E}$ have the form $e=(i,j,t)$, representing an instantaneous
interaction between $i$ and $j$ at time $t$. $w_{e}$ indicates the positive
weight of edge $e$. The graph
$\mathcal{G}(\mathcal{V},\mathcal{E},\mathcal{W})$ can be represented with a
sequence of _weighted adjacency matrices_ , $\\{W_{t}\\}_{t=1,\dots,T}$, where
$T$ is the number of time points. Each of these matrices has size $n\times n$
and entries $(W_{t})_{ij}=w_{(i,j,t)}$ if $(i,j,t)\in\mathcal{E}$ and
$(W_{t})_{ij}=0$ otherwise. In the following, we will refer to these matrices
as “snapshots” of the temporal graph at given times, and to $T$ as the number
of snapshots.

This particular definition is commonly referred to as _snapshot graph_ [41].
In a more general description of temporal networks, each interaction may be
represented with a tuple $(i,j,t,\tau)$ where $\tau\in\mathbb{R}^{+}$ is an
_interaction duration_. We adopt the former notation because it is simpler to
handle in the following. The two notations are completely interchangeable
whenever the time is discrete and a finite temporal resolution $t_{\rm res}$
is set. In fact, all contacts with a duration within $t_{\rm res}$ are
considered to be instantaneous, and $(i,j,t,\tau)$ can be represented by a set
of interactions of unitary duration:
$\\{(i,j,t+\delta)\\}_{\delta\in\\{0,\dots,\tau-1\\}}$. For this reason,
Definition 1 is sufficiently general, as it can also describe interactions
lasting more than one temporal unit. For an arbitrary time resolution, the
weight $w_{e}$ associated with a temporal edge $e$ may be used to encode the
fraction of $t_{\rm res}$ the two nodes connected by $e$ spent in interaction.

Let us now introduce the concept of _matched_ and _unmatched_ graphs.

######  Definition 2 (Matched graphs)

Let $\mathcal{G}_{1}(\mathcal{V}_{1},\mathcal{E}_{1},\mathcal{W}_{1})$ and
$\mathcal{G}_{2}(\mathcal{V}_{2},\mathcal{E}_{2},\mathcal{W}_{2})$ be two
temporal graphs with $n_{1}$ and $n_{2}$, respectively. We say that
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are _matched_ if $n_{1}=n_{2}$ and
there exists a _known_ bijective function
$\pi:\mathcal{V}_{1}\to\mathcal{V}_{2}$ that maps each node of
$\mathcal{G}_{1}$ to a node of $\mathcal{G}_{2}$. The two graphs are otherwise
said to be _unmatched_.

When two graphs have the same size, mathematically, there are always many
possible mappings $\pi$ between their nodes, but for the _matched_ approach to
be valuable, a known mapping associated with an external notion of node
identity across the two graphs is necessary (e.g., nodes corresponding to the
same persons in two temporal social networks). An implicit consequence of
Definition 2 is that all graph pairs with a different number of nodes are
considered to be _unmatched_. We now state the requirements for our distance
measure and illustrate our main result.

Figure 1: Distance computation between two temporal graphs. The inputs to the
distance function are two temporal graphs $\mathcal{G}_{1}$ (top, orange
nodes) and $\mathcal{G}_{2}$ (bottom, green nodes), generally with a different
number of snapshots ($T_{1}=5$, $T_{2}=4$, in the example) and a different
number of nodes (here $n_{1}=6$, $n_{2}=5$). Each graph is represented as a
matrix $P\in\mathbb{R}^{n\times n}$, according to (1), with entry $(ij)$
encoding the probability that a walker goes from $i$ to $j$ following a time-
respecting random walk (the walker’s position for each time point is indicated
in blue). The matrices $P_{1,2}$ are then embedded using the EDRep algorithm,
mapping them to $X_{1}\in\mathbb{R}^{n_{1}\times d}$ and
$X_{2}=\mathbb{R}^{n_{2}\times d}$. Finally, the matched – (3) – and unmatched
– (4) – distances are calculated. Notice that a necessary condition to compute
$d_{\rm m}$ is that $n_{1}=n_{2}$.

## Main result

In the following, we define two types of distance functions: $d_{\rm m},d_{\rm
u}$ between matched and unmatched graphs, respectively. The inputs to these
functions are two temporal graphs, $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$,
with a potentially different number of time points (snapshots) $T_{1}$ and
$T_{2}$. In both cases, the distances should fulfill the following standard
requirements [42]: i) non-negativity; ii) separation axiom; iii) symmetry; iv)
triangle inequality. In addition, both distances should also be able by design
to detect differences induced by the permutation of time indices. The matched
distance should also differentiate between temporal networks differing only by
a permutation of node indices, while the unmatched one should be invariant
with respect to such transformation.

Our proposed distances are computed in two steps: i) we generate a temporal
graph embedding, given by a matrix of size $(n\times d)$ (with $d$ independent
of $T$), that encodes relevant topological and temporal properties by
leveraging time-respecting random walks on the temporal network; ii) we define
the distance in the embedded space (separately treating the matched and the
unmatched cases). The distance computation pipeline is illustrated in Fig. 1,
and we now describe the steps outlined above in detail.

### Temporal graph embedding

Graphs are rich data representations, making it challenging to define simple
mathematical operations to manipulate them. Graph embeddings provide an
interesting avenue for doing so, as they yield a representation in vector
space that preserves some of the graphs’ relevant properties [43, 44, 45, 46].
In the case of temporal graphs, the additional challenge of dealing with their
temporal dimension has been tackled in many different ways: Ref. [47]
represents time as an additional dimension of an adjacency tensor; in
evolutionary spectral clustering [48, 49, 50, 51, 52], a different embedding
is obtained for each snapshot, and smoothness conditions are implemented on
their temporal evolution; more recent works [53, 54, 55] introduced approaches
based on time-respecting random walks, which encode relevant temporal
properties that are important for dynamical processes occurring on temporal
graphs.

We take the latter type of approach as our starting point to generate temporal
graph embeddings that are obtained as the solution to an optimization problem.
We define a loss function whose argument is a transition matrix $P$ that is
the limiting distribution of time-respecting random walks over the temporal
graph $\mathcal{G}$ to be embedded. $T$ being the number of snapshots of
$\mathcal{G}$, we consider an ensemble of random walks of length drawn
uniformly at random between $1$ and $T$, and starting from a randomly chosen
node at time $t=1$; at each time step $t$, the walker, situated, e.g., on node
$i$, can either move to a random neighbor of $i$ in the snapshot at time $t$
or stay in place on $i$; if the walker is situated on a node that is not
active at time $t$, _i.e._ which has no neighbors in this snapshot, the walker
stays in place with probability one. The graph snapshots on the left of Fig. 1
show examples of such time-respecting random walks on the input graphs.

Specifically, given a temporal graph $\mathcal{G}$, with $W_{t}$ the snapshot
adjacency matrices of Definition 1 at times $t=1,\cdots,T$, we define for each
snapshot $\hat{L}_{t}=(D_{t}+I_{n})^{-1}(W_{t}+I_{n})$, where $D_{t}$ is the
degree matrix $D_{t}={\rm diag}(W_{t}\bm{1}_{n})$ of the snapshot, $I_{n}$ is
the identity matrix of size $n$, and $\bm{1}_{n}$ is the $n$-sized unity
vector. We then define the matrix $P$ as

$\displaystyle
P=\frac{1}{T}\sum_{\tau=1}^{T}\hat{L}_{\tau}\hat{L}_{\tau-1}\cdots\hat{L}_{2}\hat{L}_{1}\,\,,$
(1)

The entries of $P$ (which is a probability matrix) depend on the graph
structure, the distribution of interaction durations, the correlation between
nodes’ interaction patterns, etc. In particular, they are not invariant under
permutations of the time indices. We remark that the random walks used here
can be of arbitrary length, hence the matrix $P$ is sensitive to all the time
scales of the temporal graph considered.

Given the above probability matrix $P$ and a chosen embedding dimensionality
$d$, we now want to generate, for each node $i$ of $\mathcal{G}$, a unitary
node embedding vector $\bm{x}_{i}\in\mathbb{R}^{d}$. To this aim, letting
$X\in\mathbb{R}^{n\times d}$ be the matrix storing in its rows these embedding
vectors, we write the loss function as:

$\displaystyle\mathcal{L}_{P}(X)$
$\displaystyle=-\sum_{i,j\in\mathcal{V}}\left[P_{ij}~{}{\rm
log}~{}Q_{ij}(X)-\frac{\bm{x}_{i}^{T}\bm{x}_{j}}{n}\right],$ (2)
$\displaystyle Q_{ij}(X)$
$\displaystyle=\frac{e^{\bm{x}_{i}^{T}\bm{x}_{j}}}{\sum_{k\in\mathcal{V}}e^{\bm{x}_{i}^{T}\bm{x}_{k}}}:=\frac{e^{\bm{x}_{i}^{T}\bm{x}_{j}}}{Z_{i}}~{}.$

This loss function is the sum of the cross entropies between the distributions
in the rows of $P$ and the variational distributions in the rows of $Q(X)$,
with the addition of a regularization term. The function $\mathcal{L}_{P}$
requires $\mathcal{O}(n^{2})$ operations to be evaluated, since $Z_{i}$ is
computed in $\mathcal{O}(n)$ operations for each $i$. We adopt the recently
proposed EDRep algorithm [56] that proposes an efficient approximation of
$Z_{i}$, making it possible to optimize $\mathcal{L}_{P}$ in $O(n)$
operations. We refer the reader to the _Methods_ section for further details.

The matrix $X$ obtained by optimizing $\mathcal{L}_{P}$ defines the embedding
of the temporal graph $\mathcal{G}$, and we now show how to leverage this
embedding procedure to define a distance between temporal graphs.

### Defining a distance between embeddings

We want to define a distance between temporal graph embeddings that quantifies
the similarity of the original temporal graphs according to the requirements
stated above. Notice that the output embedding vectors $\bm{x}$ are defined up
to an orthogonal transformation applied to the rows of $X$. In fact, suppose
$R\in\mathbb{R}^{d\times d}$ is an orthogonal matrix, and
$\tilde{\bm{x}}_{i}=R\bm{x}_{i}$, then
$\bm{x}_{i}^{T}\bm{x}_{j}=\bm{\tilde{x}}_{i}^{T}\bm{\tilde{x}}_{j}$ and the
loss function of (2) is $\mathcal{L}_{P}(\tilde{X})=\mathcal{L}_{P}(X)$.
Hence, our distance must be invariant under orthogonal transformations.
Moreover, as discussed above, the distance for unmatched graphs must also be
invariant with respect to node permutations.

Given these requirements, we now discuss separately our choices to define the
matched and unmatched distances. In the _Empirical evaluation_ section, we
show the efficacy of these choices with numerical tests.

#### Distance for matched graphs

Let $X_{1}$ and $X_{2}\in\mathbb{R}^{n\times d}$ be the embedding matrices of
two matched temporal graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$. To
satisfy the invariance requirements discussed above, rather than defining our
distance directly in terms of the matrices $X_{1}$ and $X_{2}$, we use the
auxiliary matrices $M_{X_{1}}=X_{1}X_{1}^{T}$ and $M_{X_{2}}=X_{2}X_{2}^{T}$
of size $n\times n$. These matrices are by construction invariant with respect
to orthogonal transformations of the embedding space and encode the global
structure of the corresponding temporal graphs (as the embeddings are
generated exploiting the whole networks’ structures). We define the distance
$d_{\rm m}$ between matched temporal graphs as:

$\displaystyle d_{\rm
m}(\mathcal{G}_{1},\mathcal{G}_{2}):=\|M_{X_{1}}-M_{X_{2}}\|_{\rm F}\,\,,$

where $\|\cdot\|_{\rm F}$ is the Frobenius norm. Each matrix $M$ encodes the
similarity in the embedding space between all pairs of nodes of the
corresponding temporal graph, and $d_{\rm m}$ quantifies thus the difference
between these similarity patterns. In the Methods section, we show that we
actually do not need to compute the large ($n\times n$) $M_{X_{1}}$ and
$M_{X_{2}}$ matrices, but that the distance can be computed using small
$d\times d$ matrices as follows:

$\displaystyle d_{\rm
m}(\mathcal{G}_{1},\mathcal{G}_{2})=\sqrt{\|X_{1}^{T}X_{1}\|_{\rm
F}^{2}+\|X_{2}^{T}X_{2}\|_{\rm F}^{2}-2\|X_{1}^{T}X_{2}\|_{\rm F}^{2}}\,\,,$
(3)

We can easily verify that $d_{\rm m}$ is a distance, as it satisfies all the
requirements mentioned above and is generally not invariant under the
permutation of node indices.

#### Distance for unmatched graphs

In (3), the term $X_{1}^{T}X_{2}$ implies that $X_{1,2}$ have the same size
and that their rows are ordered according to the same and known indexing of
the temporal graphs’ nodes. In the case of _unmatched_ graphs, this node
correspondence is not available, and the distance, as we discussed, should
also be invariant with respect to node permutations. We therefore define the
distance between unmatched graphs using auxiliary vectors. Specifically, we
denote with $\bm{\lambda}(A)$ the vector of ordered eigenvalues of a matrix
$A$ and define our distance between two _unmatched_ temporal graphs as

$\displaystyle d_{\rm
u}(\mathcal{G}_{1},\mathcal{G}_{2})=\left\|\bm{\lambda}\left(\frac{X_{1}^{T}X_{1}}{n_{1}}\right)-\bm{\lambda}\left(\frac{X_{2}^{T}X_{2}}{n_{2}}\right)\right\|_{2}\,\,,$
(4)

where $X_{1,2}$ are, as before, the embeddings matrices of the two graphs, and
$n_{1,2}=|\mathcal{V}_{1,2}|$ are their sizes. The sizes are used to normalize
the covariance matrices $X_{1}^{T}X_{1}$ and $X_{2}^{T}X_{2}$ so that their
eigenvalues are independent from graph size.

The covariance matrices $X_{1}^{T}X_{1}$ and $X_{2}^{T}X_{2}$ (of size
$d\times d$) are indeed an appropriate argument to define the distance $d_{\rm
u}$, since they are independent of the ordering of the nodes and any other
orthogonal transformation applied to the columns of $X$. However, directly
comparing the entries of $X_{1}^{T}X_{1}$ and $X_{2}^{T}X_{2}$ requires a one-
to-one correspondence between the embedding dimensions (the columns of $X$).
This mapping is unavailable because the EDRep algorithm makes no guarantees on
the correspondence between the dimensions of the embedding spaces of different
graphs. As a solution to this issue, we thus compare their spectra, which are
invariant with respect to orthogonal transformations of the rows of $X$. This
choice takes inspiration from the spectral static graph distance definitions –
such as Ref. [32] – in which graphs are compared by computing the distance
between the ordered sets of the eigenvalues of their matrix representations
(e.g., adjacency, Laplacian, non-backtracking, etc.)

### Computational complexity

As discussed in the Methods section, the computational complexity of the
embedding step is $\mathcal{O}\left(nd^{2}+d\cdot{\rm min}(n^{2},E)\right)$,
where $E=\sum_{t}|\mathcal{E}_{t}|$ is the total number of temporal edges. On
top of this, the distance $d_{\rm m}$ is then obtained with
$\mathcal{O}(nd^{2}+d^{2})$ additional operations, while $d_{\rm u}$ requires
$\mathcal{O}(nd^{2}+d^{3})$ additional operations.

## Empirical evaluation

We now proceed to evaluate the distance metrics we introduced, focusing in
particular on their ability to capture the differences in topological and
temporal properties of empirical temporal graphs. We carry out two evaluation
tests using both empirical and synthetic temporal graph data. We use, in
particular, empirical temporal graphs published by the SocioPatterns
collaboration (sociopatterns.org), that describe time-resolved, close-range
proximity interactions of humans and animals in a variety of real-world
environments. These data are known to exhibit rich multi-scale network
structures, complex temporal activity patterns, correlations between these
two, and other complex network features. Hence, they provide a natural
benchmark to assess the sensitivity of our distance definitions to specific
properties of real-world temporal graphs.

  * •

In the first evaluation test, we consider structurally different synthetic
temporal graphs of different sizes, and we cluster them using our temporal
graph distance $d_{\rm u}$, checking how well the clusters we find match the
graph generating methods we used, irrespective of graph size. We then repeat
the same task on empirical labeled data of human proximity in school settings.

  * •

In the second evaluation test, we use the empirical data to elucidate which of
the many properties of real temporal graphs are discriminated by the distances
we introduced. We proceed as follows: given an empirical temporal graph, we
apply a set of randomization operations, where each operation is designed to
preserve specific properties of the original data (e.g., the activity time
series of each node). We then attempt to discriminate the randomized temporal
graphs from one another using our distance definitions and quantify the
performance of such discrimination task. We test both $d_{\rm m}$ and $d_{\rm
u}$; however this evaluation strategy, by design, compares temporal graphs
with the same number of nodes.

### Discriminating between temporal graph classes

We define four families of temporal graphs as follows: first, we generate
static random graphs of different sizes using four standard generative models;
then, we turn these graphs into temporal graphs by assigning to each edge of
the static graph the activity time series (_i.e._ the set of timestamps in
which that edge was active) of a randomly chosen edge of the _Conference_
empirical data set (the largest among the empirical data sets we use). The
four generative models we use are: i) the Erdős-Renyi (ER) model [57]; ii) the
stochastic block model (SBM), capable of generating graphs with a known
community structure [58]; iii) the configuration model (CM), yielding graphs
with an arbitrary degree distribution [59]; iv) the geometric model (GM),
which generates edges based on proximity in a latent space [60]. Unlike the
first three, the latter model yields graphs with a high clustering
coefficient. Details on these generative models are provided in the Methods
section.

Figure 2: Validation of $d_{\rm u}$ on graphs of varying size. Panel A:
Clustering performance in terms of normalized mutual information (NMI) as a
function of the embedding dimensionality $d$ used in the embedding step shown
in Figure 1. The clustering task consists in recognizing four synthetic
temporal graph classes with an unsupervised algorithm based on the distance
$d_{\rm u}$. The synthetic graphs classes are obtained by generating a graph
from either of four models (stochastic block model (SBM), configuration model
(CM), Erdős-Renyi (ER), and geometric model (GM)) with constant degree equal
to $4.8$ and the temporal component is obtained from the activity time series
of an empirical graph as detailed in the main text. Inset of panel A: Scatter
plot of UMAP dimensionality reduction in two dimensions of the signature
vectors $\bm{\lambda}$ appearing in the definition of $d_{\rm u}$ given in
(4), with here $d=32$. Each point refers to a temporal graph; the color and
marker code refers to the generative model of its static component, while the
marker size is proportional to the number of nodes. Panel B: Each point is the
$2$-dimensional UMAP embedding of the signature vector $\bm{\lambda}$ of the
temporal graph obtained selecting two classes and a day of interaction for all
possible $(\texttt{class\\_1, class\\_2, day})$ triplets in the SocioPatterns
data sets describing proximity temporal graphs in schools. The color and
marker code are assigned according to the class label: the primary school
classes form a group on their own and the other three groups (_Other-Other_ ,
_Bio-Other_ , _Bio-Bio_) belong to the high school data sets, where _Bio_ are
the biology classes, and _Other_ the remaining ones. In all cases we use a
temporal resolution equal to $10$ minutes to create the temporal graphs from
the SocioPatterns data.

For each model, we generate $250$ graphs with size uniformly distributed
between $n=200$ and $n=1800$ and constant average degree. We then deploy our
distance definition $d_{\rm u}$ to compute a pair-wise distance matrix between
all these temporal graphs. We use this matrix as an input for an unsupervised
clustering task and check whether this clustering can discriminate the four
groups of temporal graphs generated. The unsupervised clustering algorithm
only takes the distance matrix and the number of clusters $k$ (here $k=4$) as
inputs. Here, we first perform a spectral embedding using non-negative matrix
factorization (NMF) [61] extracting $k$ non-negative components and then
applying the k-means clustering algorithm with $k$ classes [62]. We note that
successively embedding and clustering is a standard approach, and using NMF is
most suited here since the distance matrix is non-negative. Finally, we
compare the original temporal graph labels with the partition labels yielded
by this unsupervised clustering informed by our temporal graph distances: we
quantify the match between the true partition and the inferred one using the
normalized mutual information (NMI), which yields a performance metric ranging
between $0$ (random guess) and $1$ (perfect reconstruction).

Figure 2A shows the normalized mutual information (NMI) between the known
temporal graph classes (associated with the four generative models) and the
discovered cluster labels as a function of the embedding dimension $d$. The
discrimination performance is low for small values of $d$, but for $d\gtrsim
8$ the accuracy is high and becomes insensitive to the specific $d$ value. The
inset in Figure 2A shows the output of UMAP algorithm [63] in two dimensions
when applied to the vectors $\bm{\lambda}\in\mathbb{R}^{32}$ used in the
distance $d_{\rm u}$. Each symbol corresponds to one temporal graph, the color
and marker shape indicate its generative model, and the marker size is
proportional to the number of graph nodes. We observe that graph size does not
appear to affect distances systematically, and that the $\bm{\lambda}$ vectors
used by the distance $d_{\rm u}$ allow us to discriminate all four generative
models. Indeed, we have verified that the distances $d_{\rm u}$ between the
graphs and the distances between their respective UMAP embedded vectors are
strongly related, with a highly significant Spearman correlation coefficient
of $\sim 0.92$.

We now carry out a test based on empirical data, using the SocioPatterns data
sets describing proximity temporal graphs in schools, _i.e._ , _Primary
school, High school 1, High school 2, High school 3_ (the latter three
correspond to data collections carried out in the same school in successive
years). In each of these graphs, the nodes are split into classes, and the
measurements are taken over multiple days. In the _Primary school_ data set
there are ten classes, divided into five grades (2 classes per grade). In the
_High school_ data sets, the classes are split according to the main topics
studied, and the data collections involved an increasing number of classes in
successive years. Namely, the _High school 1_ contains the data of the
students of three classes focusing on physics, chemistry and engineering; in
_High school 2_ , two classes focusing on maths and physics joined the data
collection; in _High school 3_ an additional maths and physics class and three
biology classes also joined. We split each of these data sets into a set of
temporal graphs obtained containing the contacts happening on a particular
data collection day and involving the nodes of only two classes. We consider
all the possible $(\texttt{class\\_1, class\\_2, day})$ triplets, obtaining in
this way a family of temporal graphs (with $352$ instances) with comparable
sizes. While the distance $d_{\rm u}$ can compare graphs of arbitrarily
different sizes, we want indeed here to set the hardest condition in which
these graphs cannot be told apart by simply looking at their size. For each
graph, we compute its signature $\bm{\lambda}$ of (4) and show the resulting
two-component UMAP embedding in Fig. 2B. In this case, the Spearman
correlation between the distances $d_{\rm u}$ and the distances between the
UMAP embedding vectors equals $0.88$. The color and marker coding refers in
the figure to a labeling denoting the type of the two interacting classes. All
primary school classes are treated equally, while in the high school case, we
only distinguish between biology classes and all the others. From the plot,
one can see that the distance can disentangle the networks formed from primary
school data from the ones containing high school data. Moreover, a less neat
but still visible distinction exists in the embeddings of (_Bio-Other_),
likely because biology students spent more time in the labs and had different
interaction patterns. This result confirms the ability of our distance to
capture information on the temporal graph at multiple levels.

### Discriminating between temporal graph randomizations

Here, we consider $9$ empirical SocioPatterns data sets, whose basic
properties are summarized in Table 1 of the Methods section. Following Ref.
[64], we select $6$ types of randomization operations $R_{i}$
($i=1,\ldots,6$), described in detail in the Methods section. In all cases, we
preserve the number of nodes and of snapshots of the original temporal graph.

Figure 3: Distance-based graph clustering for ensembles of graphs generated
according to different randomization techniques. Left panel: results for the
matched distance $d_{\rm m}$ of (3). Right panel: results for the unmatched
distance $d_{\rm u}$ of (4). Within each panel, each matrix corresponds to one
of the $9$ SocioPatterns temporal graphs described in Table 1. The rows and
columns of each matrix correspond to the same set of $6$ randomization
techniques we used, described in the Methods sections, and based on the
properties they preserve. _Random_ : preserves the number of temporal edges;
_Random delta_ : preserves the number of temporal edges and contact duration
distribution; _Active snapshot_ : preserves the number of edges at each time-
step and activity pattern of each node; _Time_ : preserves the aggregated
graph structure; _Sequence_ ; preserves the structure of each snapshot;
_Weighted degree_ : preserves the nodes’ cumulative interaction time. For each
pair of randomizations, we infer the randomization method of each temporal
graph via an unsupervised distance-based clustering algorithm, and we compare
the inferred randomization method with the known true one. Each matrix entry
reports (value and color coding) the accuracy of the inferred labels
(randomization methods), quantified as the normalized mutual information (NMI)
between the inferred and true labels.

To quantify the discriminative performance of our temporal graph distance, we
proceed as follows, separately for each empirical temporal graph: given the
empirical temporal graph and a pair of randomization operations ($R_{i}$,
$R_{j}$), we generate a set of $250$ realizations using $R_{i}$, labeled as
$0$, and a set of $250$ realizations using $R_{j}$, labeled as $1$, for a
total of $500$ temporal graphs. We then compute the matrix of distances
between these $500$ graphs and use it to cluster them in $2$ clusters,
following the same procedure used for Fig. 2a. Figure 3 reports the NMI values
between the real labels and the unsupervised algorithm result for each pair of
randomizations ($R_{i}$, $R_{j}$) and both the matched distance $d_{\rm m}$
(left panel) and the unmatched distance $d_{\rm u}$ (right panel). Within each
panel, each matrix refers to one empirical temporal graph, and its entries are
the NMI values described above. A high NMI entry indicates that our distance
discriminates well the temporal graphs generated according to the two
randomization procedures in the corresponding row and column of the matrix
entry, i.e., that the distance is sensitive to the properties preserved by
either $R_{i}$ or $R_{j}$. Low NMI values may either correspond to an
inability of the distance to capture those properties or simply reflect that
the empirical temporal graph is statistically random as far as those
properties are concerned, as observed in particular for several pairs of
randomizations in the _Baboons_ dataset. Thus, it is enough to find one
empirical data set for which the distance can distinguish between a pair of
randomizations to conclude that the distance is indeed sensitive to the
corresponding graph properties.

## Conclusions

We have here introduced a novel definition of distance between pairs of
temporal graphs. This definition entails two steps: first, the embedding of
the temporal graphs into an Euclidean space, and then the definition of a
distance measure in the embedded space. In the first step, we have considered
an embedding that exploits time-respecting random walks on the temporal
graphs. Indeed, such walks are known to depend on, and encode important
structural and temporal properties of these graphs [65, 9, 55, 40]. In the
second step, we have proposed two possibilities for the distance definition.
On the one hand, if a mapping is known between the nodes of the graphs to be
compared, we consider a distance definition that leverages such mapping. On
the other hand, we put forward in the more general case a definition that
makes it possible to compare graphs with arbitrarily different sizes (numbers
of nodes). Note that in both cases, as the size of the embedding matrix does
not depend on the number of temporal graph snapshots, it is possible to embed
temporal graphs with different lengths in the same embedding space and thus to
compute a distance between them. The evaluation of our pipeline on both
synthetic and empirical data sets has shown that the proposed distance can
capture structural differences (e.g., degree distribution, clustering
coefficient, or presence of communities) as well as temporal differences
(e.g., burstiness or node activity patterns) in the temporal graphs being
compared.

The methodology we have developed is actually very general and customizable,
as several other choices could be made in both steps of the method, namely the
choices of the embedding method and of the distance. Our choices are based on
two main motivations: i) a theoretical one, given the importance of time-
respecting random walks in encoding information on temporal graphs, and thus
in generating distributed representations of temporal graphs [65, 9, 55]; ii)
a numerical one, which led us to choose the EDRep algorithm of Ref. [56]
because of its efficiency and scalability and the possibility to obtain
definitions of distance that can as well be efficiently computed. Moreover,
the results obtained from our evaluation procedures support these choices a
posteriori.

Our work entails some limitations worth mentioning. First, our evaluation
strategy has focused on a limited set of temporal graphs, namely on graphs
obtained from data describing proximity events between individuals. These
graphs are however known to feature a broad variety of representative complex
structural and temporal patterns such as temporally changing community
structures, burstiness, broad distributions of event durations, etc [12, 14].
Second, we have considered only the cases either of fully matched graphs
(bijection between the sets of nodes) or of no known matching. An interesting
intermediate situation would be the one of partially matched graphs, in which
only a subset of nodes is matched between the two graphs. Tackling this
challenging setting would form an interesting extension of this work.

Defining a distance between temporal graphs opens the door to a wealth of
potential applications, of which our evaluation procedures are only possible
examples. Such a distance can, on the one hand, support data analysis of
temporal graph data by extending the procedure of Fig. 3 to a large set of
randomizations [47]. Indeed, as discussed, the inability to distinguish pairs
of randomizations of a given temporal graph can be regarded as a statistical
property of the graph itself. On the other hand, computing a distance between
graphs can provide a crucial model validation tool: many generative models for
temporal graphs are proposed based on various mechanisms of interactions, and
model validation is often simply based on the comparison of a set of
statistical properties [38], while our distance definition makes comparison
possible at a global level. In addition, the distance could be used in the
process itself of generating synthetic temporal graphs, by informing deep
generative models such as _GANS_ [66], which have proved extremely powerful in
generating realistic data [67, 68]. Generating synthetic contact data with
realistic structural and temporal properties could then be used to simulate
processes of interest in public health research [69, 70, 71, 72, 73, 74].
Finally, empirical (temporal) graphs are hard to anonymize [75, 76, 73] and,
to minimize the risk of node re-identification, it might be needed to perform
some perturbation operations on the graph before making it publicly available.
However, such operations risk destroying some important patterns and
information contained in the data. A way to tackle this issue could be to find
a trade-off between re-identification risk and information loss, and the
distance we have defined could be used to quantify the latter.

## Methods

### The EDRep algorithm

The EDRep algorithm [56] was recently proposed to efficiently generate
embeddings given a probability matrix encoding the affinity between the
embedded items. This is done by optimizing the cost function of (2) under the
constraint $\|\bm{x}_{i}\|=1$ and obtaining a low-dimensional representation
of the information encoded in the matrix $P$. A known problem of this type of
cost function is the computational complexity because the normalization
constants $Z_{i}=\sum_{k\in\mathcal{V}}e^{\bm{x}_{i}^{T}\bm{x}_{k}}$ require
$\mathcal{O}(n^{2})$ to be calculated. However, Ref. [56] describes an
efficient way to estimate all the $Z_{i}$ values in $\mathcal{O}(n)$. This is
accomplished by first subdividing the nodes into $q$ groups based on the
embedding matrix $X$. Here $q$ is a parameter of the algorithm, and larger $q$
values generally lead to a higher accuracy, but very good results are obtained
already for $q=1$. Second, for each $a=1,\dots,q$, one computes the mean
$\bm{\mu}_{a}$ and the covariance matrix $\Omega_{a}$ of the set of embedding
vectors of the nodes in group $a$. Denoting the number of nodes in group $a$
by $\pi_{a}$, one obtains the estimation of $Z_{i}$ as

$\displaystyle Z_{i}\approx\sum_{a=1}^{q}\pi_{a}~{}{\rm
exp}\left\\{\bm{x}_{i}^{T}\bm{\mu_{a}}+\frac{1}{2}\bm{x}_{i}^{T}\Omega_{a}\bm{x}_{i}\right\\}\,\,.$

Coming to the algorithm’s computational complexity, given that our choice of
$P$ is the sum of matrix products, the algorithm can be deployed in two forms:
one in which $P$ is never formally computed and the sequence
$\\{\hat{L}_{t}\\}_{t=1,\dots,T}$ is fed to the algorithm; and one in which
$P$ is explicitly computed. Letting $X\in\mathbb{R}^{n\times d}$ be the matrix
storing the embedding vectors in its rows, the computational complexity is
determined by the matrix product $PX$ needed to obtain the gradient of
$\mathcal{L}$. In the former case, this is computed in
$\mathcal{O}(nd^{2}+dE)$ operations, where $E=\sum_{t=1}^{T}|\mathcal{E}_{t}|$
is the number of temporal edges. In the second case, instead, the complexity
is given by the number of non-zero entries of $P$, which cannot exceed
$n^{2}$. The former implementation is particularly convenient when $n$ is
large, and the $\hat{L}_{t}$ matrices are very sparse. This is because $P$ may
be dense, even if the snapshots are sparse, and for large $n$, $P$ might not
even fit in the computer’s memory. Conversely, for small graphs, $n^{2}$ may
be smaller than the number of temporal edges, making the latter implementation
more convenient.

### Matched distance definition

From (3), we have

$\displaystyle d^{2}_{\rm
m}(X,Y)=\sum_{i,j\in\mathcal{V}}\left[(M_{X})_{ij}-(M_{Y})_{ij}\right]^{2}$
$\displaystyle=\sum_{i,j\in\mathcal{V}}\left[(M_{X})_{ij}(M_{X})_{ij}+(M_{Y})_{ij}(M_{Y})_{ij}-2(M_{X})_{ij}(M_{Y})_{ij}\right]$
$\displaystyle\overset{(a)}{=}\sum_{i,j\in\mathcal{V}}\left[(M_{X})_{ij}(M_{X})_{ji}+(M_{Y})_{ij}(M_{Y})_{ji}-2(M_{X})_{ij}(M_{Y})_{ji}\right]$
$\displaystyle=\sum_{i\in\mathcal{V}}\left[(M_{X}M_{X}^{T})_{ii}+(M_{Y}M_{Y}^{T})_{ii}-2(M_{X}M_{Y}^{T})_{ii}\right]$
$\displaystyle={\rm tr}(M_{X}M_{X}^{T})+{\rm tr}(M_{Y}M_{Y}^{T})-2{\rm
tr}(M_{X}M_{Y}^{T})$ $\displaystyle\overset{(b)}{=}{\rm tr}(XX^{T}XX^{T})+{\rm
tr}(YY^{T}YY^{T})-2{\rm tr}(XX^{T}YY^{T})$ $\displaystyle\overset{(c)}{=}{\rm
tr}(X^{T}XX^{T}X)+{\rm tr}(Y^{T}YY^{T}Y)-2{\rm tr}(Y^{T}XX^{T}Y)$
$\displaystyle\overset{(d)}{=}\|X^{T}X\|_{\rm F}^{2}+\|Y^{T}Y\|_{\rm
F}^{2}-2\|X^{T}Y\|_{\rm F}^{2}\,,$

where in $(a)$ we exploited that $M_{X}$ and $M_{Y}$ are symmetric, in $(b)$
we used the definition of $M_{X},M_{Y}$, in $(c)$ we used that property of the
trace stating that ${\rm tr}(AB)={\rm tr}(BA)$, and finally in $(d)$ we
applied the definition of the Frobenius norm.

### Temporal graph randomizations

In Table 1 we summarize the properties of the temporal graphs we used to
conduct our tests.

We now give a more detailed description of the randomization techniques we
adopted, defined in terms of the quantities they preserve. According to the
method, it may be more convenient to represent the temporal graph as a
sequence of instantaneous interactions $(i,j,t)$, as a sequence of
interactions with a duration $(i,j,t,\tau)$, or as a sequence of weighted
adjacency matrices $W^{(t)}$ [64]. Before randomization, time is discretized
at the scale of $10$ minutes in each data set, and the cumulative interaction
time in each $10$-minute window is used as weight.

  1. 1.

_Random_. Temporal edges are represented as $(i,j,t)$ and all three indices
are randomized, avoiding self-edges ($i$ and $j$ randomized between $1$ and
$n$, and $t$ between $1$ and $T$).
Preserved quantities: number of temporal edges.

  2. 2.

_Random delta_. Temporal edges are represented as $(i,j,t,\tau)$. Once again,
$i,j,t$ are randomized ($t$ is sampled between $1$ and $T-\tau$), while $\tau$
is preserved.
Preserved quantities: number of temporal edges and contact duration
distribution.

  3. 3.

_Active snapshot_. At each time step $t$, the edges are randomly replaced
between active nodes at $t$, _i.e._ that had at least one neighbor in the
original snapshot.
Preserved quantities: number of edges at each time-step and activity pattern
of each node.

  4. 4.

_Time_. Temporal edges are represented as $(i,j,t)$ and only the index $t$ is
randomized.
Preserved quantities: aggregated graph structure.

  5. 5.

_Sequence_. The graph is represented as a sequence of weighted adjacency
matrices $W^{(t)}$ and the randomization acts on the indices $t$.
Preserved quantities: the structure of each snapshot.

  6. 6.

_Weighted degree_. Temporal edges are represented as $(i,j,t)$ and all three
indices are randomized as in _Random_ but with the constraint that each node
has the same number of contacts as in the original network.
Preserved quantities: nodes weighted degree.

Table 1: Summary properties of the SocioPatterns time-resolved proximity networks used here. _Graph name_ is used to identify the graphs; _Description_ provides concise information on the context where data were collected; $n$ is the number of graph nodes; _Duration_ is the temporal span of the dataset, and _$T$_ is the number of graph snapshots. Graph name | Description | $n$ | Duration | T
---|---|---|---|---
_Primary school_ | Children of $10$ classes | $242$ |  $2$ days | $194$
[77, 70] | of a primary school |  |  |
_High school 1_ | Students of $3$ classes | $126$ |  $4$ days | $453$
[78] | of a high school in $2011$ |  |  |
_High school 2_ | Students of $5$ classes | $180$ |  $7$ days | $1215$
[78] | of a high school in $2012$ |  |  |
_High school 3_ | Students of $9$ classes | $327$ |  $5$ days | $605$
[79] | of a high school in $2013$ |  |  |
_Baboons_ [80] | A group of baboons | $13$ |  $27$ days | $3986$
_Households_ [81] | People of a village | $86$ |  $26$ days | $1926$
| in Malawi |  |  |
_Hospital_ [82] | Patients and health-care | $75$ |  $5$ days | $579$
| workers of a hospital |  |  |
_Conference_ [12] | People at a medical | $405$ |  $2$ days | $190$
| conference |  |  |
_Office_ [83] | Office workers in an | $92$ |  $19$ days | $1646$
| office building |  |  |

### Synthetic models

We here provide a formal definition of the models used to generate the
synthetic graphs under analysis. Even though we considered four models, three
of these can be generated from the _degree corrected stochastic block model_
[58] by changing its parameters.

######  Definition 3 (Degree corrected stochastic block model)

Let $\mathcal{V}$ be a set of $n$ nodes and $\bm{\ell}\in[k]^{n}$ be a vector
mapping each node to a class. Further let $C\in\mathbb{R}^{k\times k}$ be a
positive symmetric matrix and $\bm{\theta}\in\mathbb{R}^{n}$ be a vector
satisfying $\bm{\theta}^{T}\bm{1}_{n}=n$. The entries of the graph adjacency
matrix $A\in\ [0,1]^{n\times n}$ are generated independently (up to symmetry)
at random with probability

$\mathbb{P}(A_{ij}=1)={\rm
min}\left(1,\theta_{i}\theta_{j}\frac{C_{\ell_{i},\ell_{j}}}{n}\right)\,.$

The vector $\bm{\ell}$ contains the labels and gives a community structure in
the case in which $C_{a,a}>C_{a,b}$ for $b\neq a$, meaning that there is a
higher probability that two nodes in the same community will get connected.
The value $\theta_{i}$ is proportional to the expected degree of node $i$. For
this reason, if one chooses $\bm{\theta}=\bm{1}_{n}$ and
$\bm{\ell}=\bm{1}_{n}$, one gets the Erdős-Renyi model, in which every node
has the same expected degree, and there are no communities. The configuration
model, instead, is obtained by letting $\bm{\ell}=\bm{1}_{n}$, but changing
the value of $\bm{\theta}$ to create an arbitrary degree distribution that we
choose to be a (properly rescaled) uniform distribution between $3$ and $10$
raised to the power $4$. Finally, the stochastic block model is obtained from
a labeling vector different from $\bm{1}_{n}$ and letting
$\bm{\theta}=\bm{1}_{n}$. We consider $k=5$ communities of equal size with
$C_{a,b}=20\delta_{ab}+(1-\delta_{ab})$, with $\delta$ the Kroeneker symbol.

Let us finally introduce the random geometric model.

######  Definition 4 (Random geometric model)

Let $\mathcal{V}$ be a set of $n$ nodes. For each $i\in\mathcal{V}$ let
$\bm{x}_{i}\in\mathbb{R}^{2}$ be a random vector with norm $\|\bm{x}_{i}\|\leq
1$. The entries of the graph adjacency matrix $A\in[0,1]^{n\times n}$ are
generated independently (up to symmetry) at random with probability

$\displaystyle\mathbb{P}(A_{ij}=1)=e^{-\beta\|\bm{x}_{i}-\bm{x}_{j}\|}\,,$

for some positive $\beta$.

Note that even though the entries of $A$ are drawn at random, this model can
generate graphs with a high clustering coefficient because the probability
depends on the relative distance of a fixed embedding. In our simulations, we
set $\beta=20$.

## Acknowledgments

LD and CC acknowledge support from the Lagrange Project of the ISI Foundation
funded by CRT Foundation and from Fondation Botnar (EPFL COVID-19 Real Time
Epidemiology I-DAIR Pathfinder). AB acknowledges support from the Agence
Nationale de la Recherche (ANR) project DATAREDUX (ANR-19-CE46-0008).

## References

  * [1] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  science, 286(5439):509–512, 1999.
  * [2] Mark EJ Newman.  The structure and function of complex networks.  SIAM review, 45(2):167–256, 2003.
  * [3] A. Barrat, M. Barthélemy, and A. Vespignani.  Dynamical processes on complex networks.  Cambridge University Press, Cambridge, 2008.
  * [4] John Scott.  Trend report social network analysis.  Sociology, pages 109–127, 1988.
  * [5] Stanley Wasserman and Katherine Faust.  Social Network Analysis: Methods and Applications.  Structural Analysis in the Social Sciences. Cambridge University Press, 1994.
  * [6] Luıs A Nunes Amaral, Antonio Scala, Marc Barthelemy, and H Eugene Stanley.  Classes of small-world networks.  Proceedings of the national academy of sciences, 97(21):11149–11152, 2000.
  * [7] Marc Barthélemy.  Spatial networks.  Physics reports, 499(1-3):1–101, 2011.
  * [8] Eric Alm and Adam P Arkin.  Biological networks.  Current opinion in structural biology, 13(2):193–202, 2003.
  * [9] Petter Holme and Jari Saramäki.  Temporal networks.  Physics reports, 519(3):97–125, 2012.
  * [10] Ling Zhao, Yujiao Song, Chao Zhang, Yu Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li.  T-gcn: A temporal graph convolutional network for traffic prediction.  IEEE transactions on intelligent transportation systems, 21(9):3848–3858, 2019.
  * [11] Benjamin Blonder, Tina W Wey, Anna Dornhaus, Richard James, and Andrew Sih.  Temporal dynamics and network analysis.  Methods in Ecology and Evolution, 3(6):958–972, 2012.
  * [12] Ciro Cattuto, Wouter Van den Broeck, Alain Barrat, Vittoria Colizza, Jean-François Pinton, and Alessandro Vespignani.  Dynamics of person-to-person interactions from distributed rfid sensor networks.  PloS one, 5(7):e11596, 2010.
  * [13] Alain Barrat, Ciro Cattuto, Vittoria Colizza, Francesco Gesualdo, Lorenzo Isella, Elisabetta Pandolfi, J-F Pinton, Lucilla Ravà, Caterina Rizzo, Mariateresa Romano, et al.  Empirical temporal networks of face-to-face human interactions.  The European Physical Journal Special Topics, 222(6):1295–1309, 2013.
  * [14] Alain Barrat and Ciro Cattuto.  Temporal networks of face-to-face human interactions.  In Temporal Networks, pages 191–216. Springer, 2013.
  * [15] Gecia Bravo-Hermsdorff, Valkyrie Felso, Emily Ray, Lee M Gunderson, Mary E Helander, Joana Maria, and Yael Niv.  Gender and collaboration patterns in a temporal scientific authorship network.  Applied Network Science, 4(1):1–17, 2019.
  * [16] Remy Cazabet, Pablo Jensen, and Pierre Borgnat.  Tracking the evolution of temporal patterns of usage in bicycle-sharing systems using nonnegative matrix factorization on multiple sliding windows.  International Journal of Urban Sciences, 22(2):147–161, 2018.
  * [17] Trine Agervig Carstensen, Anton Stahl Olafsson, Nynne Marie Bech, Thea Schmidt Poulsen, and Chunli Zhao.  The spatio-temporal development of copenhagen’s bicycle infrastructure 1912–2013.  Geografisk Tidsskrift-Danish Journal of Geography, 115(2):142–156, 2015.
  * [18] Aurélien Bellet, Amaury Habrard, and Marc Sebban.  Metric learning.  Synthesis lectures on artificial intelligence and machine learning, 9(1):1–151, 2015.
  * [19] Peter Wills and François G Meyer.  Metrics for graph comparison: a practitioner’s guide.  Plos one, 15(2):e0228728, 2020.
  * [20] Mattia Tantardini, Francesca Ieva, Lucia Tajoli, and Carlo Piccardi.  Comparing methods for comparing networks.  Scientific reports, 9(1):1–19, 2019.
  * [21] Hartle Harrison, Klein Brennan, McCabe Stefan, Daniels Alexander, St-Onge Guillaume, Murphy Charles, and Hébert-Dufresne Laurent.  Network comparison and the within-ensemble graph distance.  Proc. R. Soc. A, 476:20190744, 2020.
  * [22] Claudio DT Barros, Matheus RF Mendonça, Alex B Vieira, and Artur Ziviani.  A survey on embedding dynamic graphs.  ACM Computing Surveys (CSUR), 55(1):1–37, 2021.
  * [23] Guixiang Ma, Nesreen K Ahmed, Theodore L Willke, and Philip S Yu.  Deep graph similarity learning: A survey.  Data Mining and Knowledge Discovery, 35(3):688–725, 2021.
  * [24] Alberto Sanfeliu and King-Sun Fu.  A distance measure between attributed relational graphs for pattern recognition.  IEEE transactions on systems, man, and cybernetics, (3):353–362, 1983.
  * [25] Richard E Bellman and Stuart E Dreyfus.  Applied dynamic programming, volume 2050.  Princeton university press, 2015.
  * [26] Danai Koutra, Joshua T Vogelstein, and Christos Faloutsos.  Deltacon: A principled massive-graph similarity function.  In Proceedings of the 2013 SIAM international conference on data mining, pages 162–170. SIAM, 2013.
  * [27] Nathan D Monnig and François G Meyer.  The resistance perturbation distance: A metric for the analysis of dynamic networks.  Discrete Applied Mathematics, 236:347–386, 2018.
  * [28] Michele Berlingerio, Danai Koutra, Tina Eliassi-Rad, and Christos Faloutsos.  Netsimile: A scalable approach to size-independent network similarity.  arXiv preprint arXiv:1209.2684, 2012.
  * [29] James P Bagrow and Erik M Bollt.  An information-theoretic, all-scales approach to comparing networks.  Applied Network Science, 4(1):1–15, 2019.
  * [30] Neural Nets WIRN10 B Apolloni et al.  An introduction to spectral distances in networks.  In Neural Nets WIRN10: Proceedings of the 20th Italian Workshop on Neural Nets, volume 226, page 227. IOS Press, 2011.
  * [31] Yutaka Shimada, Yoshito Hirata, Tohru Ikeguchi, and Kazuyuki Aihara.  Graph distance for complex networks.  Scientific reports, 6(1):1–6, 2016.
  * [32] Leo Torres, Pablo Suarez-Serrato, and Tina Eliassi-Rad.  Graph distance from the topological view of non-backtracking cycles.  arXiv preprint arXiv:1807.09592, 2018.
  * [33] Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alexander Bronstein, and Emmanuel Müller.  Netlsd: hearing the shape of a graph.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2347–2356, 2018.
  * [34] Claire Donnat and Susan Holmes.  Tracking network dynamics: A survey using graph distances.  The Annals of Applied Statistics, 12(2):971–1012, 2018.
  * [35] Naoki Masuda and Petter Holme.  Detecting sequences of system states in temporal networks.  Scientific reports, 9(1):1–11, 2019.
  * [36] Valeria Gelardi, Joël Fagot, Alain Barrat, and Nicolas Claidière.  Detecting social (in) stability in primates from their temporal co-presence network.  Animal Behaviour, 157:239–254, 2019.
  * [37] Nicola Pedreschi, Christophe Bernard, Wesley Clawson, Pascale Quilichini, Alain Barrat, and Demian Battaglia.  Dynamic core-periphery structure of information sharing networks in entorhinal cortex and hippocampus.  Network Neuroscience, 4(3):946–975, 2020.
  * [38] Didier Le Bail, Mathieu Génois, and Alain Barrat.  Flow of temporal network properties under local aggregation and time shuffling: a tool for characterizing, comparing and classifying temporal networks.  arXiv preprint arXiv:2310.09112, 2023.
  * [39] Vincent Froese, Brijnesh Jain, Rolf Niedermeier, and Malte Renken.  Comparing temporal graphs using dynamic time warping.  Social Network Analysis and Mining, 10(1):1–16, 2020.
  * [40] Xiu-Xiu Zhan, Chuang Liu, Zhipeng Wang, Huijuang Wang, Petter Holme, and Zi-Ke Zhang.  Measuring and utilizing temporal network dissimilarity.  arXiv preprint arXiv:2111.01334, 2021.
  * [41] Giulio Rossetti and Rémy Cazabet.  Community discovery in dynamic networks: a survey.  ACM computing surveys (CSUR), 51(2):1–37, 2018.
  * [42] Mikhael Gromov, Misha Katz, Pierre Pansu, and Stephen Semmes.  Metric structures for Riemannian and non-Riemannian spaces, volume 152.  Springer, 1999.
  * [43] Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang.  A comprehensive survey of graph embedding: Problems, techniques, and applications.  IEEE Transactions on Knowledge and Data Engineering, 30(9):1616–1637, 2018.
  * [44] Palash Goyal and Emilio Ferrara.  Graph embedding techniques, applications, and performance: A survey.  Knowledge-Based Systems, 151:78–94, 2018.
  * [45] Mengjia Xu.  Understanding graph embedding methods and their applications.  SIAM Review, 63(4):825–853, 2021.
  * [46] Ilya Makarov, Dmitrii Kiselev, Nikita Nikitinsky, and Lovro Subelj.  Survey on graph embeddings and their applications to machine learning problems on graphs.  PeerJ Computer Science, 7:e357, 2021.
  * [47] Laetitia Gauvin, André Panisson, and Ciro Cattuto.  Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach.  PloS one, 9(1):e86028, 2014.
  * [48] Yun Chi, Xiaodan Song, Dengyong Zhou, Koji Hino, and Belle L Tseng.  Evolutionary spectral clustering by incorporating temporal smoothness.  In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 153–162, 2007.
  * [49] Xuanmei Qin, Weidi Dai, Pengfei Jiao, Wenjun Wang, and Ning Yuan.  A multi-similarity spectral clustering method for community detection in dynamic networks.  Scientific reports, 6(1):1–11, 2016.
  * [50] Fuchen Liu, David Choi, Lu Xie, and Kathryn Roeder.  Global spectral clustering in dynamic networks.  Proceedings of the National Academy of Sciences, 115(5):927–932, 2018.
  * [51] Kevin S Xu, Mark Kliger, and Alfred O Hero III.  Adaptive evolutionary clustering.  Data Mining and Knowledge Discovery, 28(2):304–336, 2014.
  * [52] Lorenzo Dall’Amico, Romain Couillet, and Nicolas Tremblay.  Community detection in sparse time-evolving graphs with a dynamical bethe-hessian.  Advances in Neural Information Processing Systems, 33:7486–7497, 2020.
  * [53] Yuan Zuo, Guannan Liu, Hao Lin, Jia Guo, Xiaoqian Hu, and Junjie Wu.  Embedding temporal network via neighborhood formation.  In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2857–2866, 2018.
  * [54] Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim.  Continuous-time dynamic network embeddings.  In Companion proceedings of the the web conference 2018, pages 969–976, 2018.
  * [55] Koya Sato, Mizuki Oka, Alain Barrat, and Ciro Cattuto.  Predicting partially observed processes on temporal networks by dynamics-aware node embeddings (dyane).  EPJ Data Science, 10(1):22, 2021.
  * [56] Lorenzo Dall’Amico and Enrico Maria Belliardo.  Efficient distributed representations beyond negative sampling.  arXiv preprint arXiv:2303.17475, 2023.
  * [57] Paul Erdős, Alfréd Rényi, et al.  On the evolution of random graphs.  Publ. math. inst. hung. acad. sci, 5(1):17–60, 1960.
  * [58] Brian Karrer and Mark EJ Newman.  Stochastic blockmodels and community structure in networks.  Physical review E, 83(1):016107, 2011.
  * [59] Béla Bollobás.  A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.  European Journal of Combinatorics, 1(4):311–316, 1980.
  * [60] Jesper Dall and Michael Christensen.  Random geometric graphs.  Physical review E, 66(1):016121, 2002.
  * [61] Cédric Févotte and Jérôme Idier.  Algorithms for nonnegative matrix factorization with the $\beta$-divergence.  Neural computation, 23(9):2421–2456, 2011.
  * [62] James MacQueen et al.  Some methods for classification and analysis of multivariate observations.  In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pages 281–297. Oakland, CA, USA, 1967\.
  * [63] Tim Sainburg, Leland McInnes, and Timothy Q Gentner.  Parametric umap embeddings for representation and semisupervised learning.  Neural Computation, 33(11):2881–2907, 2021.
  * [64] Laetitia Gauvin, Mathieu Génois, Márton Karsai, Mikko Kivelä, Taro Takaguchi, Eugenio Valdano, and Christian L Vestergaard.  Randomized reference models for temporal networks.  SIAM Review, 64(4):763–830, 2022.
  * [65] Raj Kumar Pan and Jari Saramäki.  Path lengths, correlations, and centrality in temporal networks.  Phys. Rev. E, 84:016105, Jul 2011.
  * [66] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  Advances in neural information processing systems, 27, 2014.
  * [67] Faezeh Faez, Yassaman Ommi, Mahdieh Soleymani Baghshah, and Hamid R Rabiee.  Deep graph generators: A survey.  IEEE Access, 9:106675–106702, 2021.
  * [68] Hamed Alqahtani, Manolya Kavakli-Thorne, and Gulshan Kumar.  Applications of generative adversarial networks (gans): An updated review.  Archives of Computational Methods in Engineering, 28:525–552, 2021\.
  * [69] Anna Machens, Francesco Gesualdo, Caterina Rizzo, Alberto E. Tozzi, Alain Barrat, and Ciro Cattuto.  An infectious disease model on empirical networks of human contact: bridging the gap between dynamic network data and contact matrices.  BMC Infectious Diseases, 13(1):1–18, 2013.
  * [70] Valerio Gemmetto, Alain Barrat, and Ciro Cattuto.  Mitigation of infectious disease at school: targeted class closure vs school closure.  BMC infectious diseases, 14(1):1–10, 2014.
  * [71] Dina Mistry, Maria Litvinova, Ana Pastore y Piontti, Matteo Chinazzi, Laura Fumanelli, Marcelo FC Gomes, Syed A Haque, Quan-Hui Liu, Kunpeng Mu, Xinyue Xiong, et al.  Inferring high-resolution human mixing patterns for disease modeling.  Nature communications, 12(1):323, 2021.
  * [72] Giulia Cencetti, Gabriele Santin, Antonio Longa, Emanuele Pigani, Alain Barrat, Ciro Cattuto, Sune Lehmann, Marcel Salathe, and Bruno Lepri.  Digital proximity tracing on empirical contact networks for pandemic control.  Nature communications, 12(1):1655, 2021.
  * [73] Ana-Maria Creţu, Federico Monti, Stefano Marrone, Xiaowen Dong, Michael Bronstein, and Yves-Alexandre de Montjoye.  Interaction data are identifiable even across long periods of time.  Nature Communications, 13(1):313, 2022.
  * [74] Elisabetta Colosi, Giulia Bassignana, Diego Andrés Contreras, Canelle Poirier, Pierre-Yves Boëlle, Simon Cauchemez, Yazdan Yazdanpanah, Bruno Lina, Arnaud Fontanet, Alain Barrat, and Vittoria Colizza.  Screening and vaccination against covid-19 to minimise school closure: a modelling study.  The Lancet Infectious Diseases, 22(7):977–989, 2022.
  * [75] Lars Backstrom, Cynthia Dwork, and Jon Kleinberg.  Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography.  In Proceedings of the 16th international conference on World Wide Web, pages 181–190, 2007.
  * [76] Daniele Romanini, Sune Lehmann, and Mikko Kivelä.  Privacy and uniqueness of neighborhoods in social networks.  Scientific reports, 11(1):20104, 2021.
  * [77] Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-François Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne Régis, Bruno Lina, et al.  High-resolution measurements of face-to-face contact patterns in a primary school.  PloS one, 6(8):e23176, 2011.
  * [78] Julie Fournet and Alain Barrat.  Contact patterns among high school students.  PLoS ONE, 9(9):e107878, 09 2014.
  * [79] Rossana Mastrandrea, Julie Fournet, and Alain Barrat.  Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys.  PloS one, 10(9):e0136497, 2015.
  * [80] Valeria Gelardi, Jeanne Godard, Dany Paleressompoulle, Nicolas Claidière, and Alain Barrat.  Measuring social networks in primates: wearable sensors versus direct observations.  Proceedings of the Royal Society A, 476(2236):20190737, 2020.
  * [81] Laura Ozella, Daniela Paolotti, Guilherme Lichand, Jorge P Rodríguez, Simon Haenni, John Phuka, Onicio B Leal-Neto, and Ciro Cattuto.  Using wearable proximity sensors to characterize social contact patterns in a village of rural malawi.  EPJ Data Science, 10(1):46, 2021.
  * [82] Philippe Vanhems, Alain Barrat, Ciro Cattuto, Jean-Francois Pinton, Nagham Khanafer, Corinne Régis, Byeul-a Kim, Brigitte Comte, and Nicolas Voirin.  Estimating potential infection transmission routes in hospital wards using wearable proximity sensors.  PLoS ONE, 8:e73970, 09 2013.
  * [83] Mathieu Génois and Alain Barrat.  Can co-location be used as a proxy for face-to-face contacts?  EPJ Data Science, 7(1):1–18, 2018.