Temporal networks model a variety of important phenomena involving timed interactions between entities.
Existing methods for machine learning on temporal networks generally exhibit at least one of two limitations.
First, time is assumed to be discretized, so if the time data is continuous, the user must determine the discretization and discard precise time information.
Second, edge representations can only be calculated indirectly from the nodes, which may be suboptimal for tasks like edge classification.
We present a simple method that avoids both shortcomings: construct the line graph of the network, which includes a node for each interaction, and weigh the edges of this graph based on the difference in time between interactions. From this derived graph, edge representations for the original network can be computed with efficient classical methods.
The simplicity of this approach facilitates explicit theoretical analysis: we can constructively show the effectiveness of our method's representations for a natural synthetic model of temporal networks.
Empirical results on real-world networks demonstrate our method's efficacy and efficiency on both edge classification and temporal link prediction.

§ INTRODUCTION

Temporal networks, which are graphs augmented with a time value for each edge,  model a variety of important phenomena involving timed interactions between entities, including financial transactions, flights, and web browsing.
Common tasks for machine learning on temporal networks include classification of the temporal edges, as well as temporal link prediction, which involves predicting future links given some links in the past.
These tasks yield various applications, such as recommendation systems [Zhou et al., 2021] and detection of illicit financial transactions [Pareja et al., 2020].

As with most machine learning for graphs, the key to learning for temporal networks is creating effective vector representations, also called embeddings, for the network's components, namely the nodes and edges. These embeddings can either be made as part of an end-to-end framework, or created then passed to off-the-shelf classifiers for downstream tasks; for example, for the edge classification task, a logistic regression classifier can be trained using the training edges' embedding vectors and class labels, then applied at inference time on the test edges' vectors.

The node embedding task, in particular, has seen great interest, and many methods for `static' (i.e., non-temporal) networks have been proposed over the years [Belkin & Niyogi, 2001, Perozzi et al., 2014, Grover & Leskovec, 2016].
Edge embedding has seen less interest; there are some exceptions [Li et al., 2017, Bandyopadhyay et al., 2019], but generally, edge embeddings are created by first making node embeddings, then aggregating them, e.g., by taking the entrywise product of the two endpoint nodes' embeddings. There are a wide variety of methods for temporal network embedding, including ones based on matrix/tensor factorization [Dunlavy et al., 2011, Li et al., 2017, Zhang et al., 2018], random walks [Yu et al., 2018, Nguyen et al., 2018], graph convolutional networks [Pareja et al., 2020], and deep autoencoders [Goyal et al., 2018, Rahman et al., 2018, Goyal et al., 2020], but generally, these methods can be seen as variants of those for static networks. With some exceptions [Trivedi et al., 2017, Nguyen et al., 2018, Trivedi et al., 2019], these methods generally do not work directly with the continuous-valued times of temporal edges, but rather require that the times are discretized, yielding a sequence of static graphs.

These prior methods present some limitations. First, since most datasets have continuous-timed edges, the assumption that time is discretized requires the user to manually determine the discretization and discard precise time information. Second, prior methods generally return representations of nodes rather than edges, so edge representations can only be calculated indirectly from the nodes, which may be suboptimal for tasks like edge classification. Given that timestamps are associated with edges rather than nodes, and that  there are few public datasets where the nodes rather than edges are associated with a time-series of attributes or classes, it is intuitively more natural to derive edge embeddings directly.

We present a simple but novel framework to address these issues:

construct the line graph of the network, which converts each edge (timed interaction) of the network into a node, and connects interactions that share an endpoint node. Then, set the edge weights in this line graph based on differences in time between interactions, with interactions that occur closer together in time being connected with higher weights. From this derived graph, which directly represents topological proximity (i.e., adjacency of edges) and temporal proximity, temporal edge representations for the original network can be computed and exploited with efficient classical methods.
To our knowledge, ours is the first method that directly forms embeddings for continuous-time temporal edges without supervision and without aggregating node embeddings - see Table <ref>. Our method is significantly simpler than recent prior work, particularly compared to deep methods, allowing for more direct theoretical analysis: we propose the temporal stochastic block model (TSBM), which naturally extends the well-known stochastic block model (SBM) for static networks to temporal networks, and we show that our method can exploit time and community information in TSBMs to form effective representations.
Practically, our method's simplicity makes it easy to implement, yet it is accurate and efficient: in experiments on five benchmark real-world temporal networks, our approach achieves superior predictive and runtime performance relative to prior methods.

Node Representation-based

Edge Representation-based

1c|Discrete Time       c]@c@
TIMERS [Zhang et al., 2018]
EvolveGCN [Pareja et al., 2020]
$\cdots$     DyLink2Vec [Rahman et al., 2018]
1c|Continuous Time     c]@c@CTDNE [Nguyen et al., 2018]
DyRep [Trivedi et al., 2019]
This work

Problem studied in this work.

§ METHODOLOGY

Our approach starts with a sequence of timestamped edges:

A temporal graph $G=(V,E)$ is a set of vertices $V$ and a set of temporal edges $E$, where $E \subseteq V \times V \times \RR$. $t$ is the time of the temporal edge $(u,v,t)$.

Our approach centers around our proposed notion of `time-decayed line graphs' (TDLGs) which are derived from temporal graphs. Our notion of TDLGs extends the well-established idea of line graphs, which are derived from static (i.e., non-temporal), undirected graphs; the line graph of an undirected, unweighted graph is another undirected, unweighted graph that represents adjacencies between edges in the original graph. We propose to incorporate time information by using it to set the weights of the resulting line graph.
Specifically, given a temporal graph $G$, we construct a TDLG, which is a static weighted line graph $L_\text{TD}(G)$, as follows in Definition <ref>.

Given a temporal graph $G=(V,E)$, the associated time-decayed line graph is $L_\text{TD}(G)=(V_L,E_L,w)$, where $V_L = E$, $E_L = \{ \left( (u,v,t_1), (v,z,t_2) \right) : (u,v,t_1),(v,z,t_2) \in E \}$, and the edge weight function $w:E_L \to \RR_{+}$ evaluated on edge $\left( (u,v,t_1), (v,z,t_2) \right)$ is given by
$ \exp\left(- \frac{1}{2 \sigma_t^2} (t_1 - t_2)^2 \right) $
for some fixed $\sigma_t > 0$.

Thus, proximity of two temporal edges in the TDLG incorporates both topological proximity in the original graph as well as proximity in time. The parameter $\sigma_t$ controls how quickly proximity in the TDLG decays as difference in time grows. For a graph with $n$ nodes and $m$ edges, we can construct the weighted adjacency matrix $\mA \in \RR_+^{m \times m}$ of the TDLG as follows. Given the incidence matrix $\mB \in \{0,1\}^{n \times m}$, each column vector of which is $n$-dimensional, corresponds to an edge, and is $1$ for the edge's two endpoint nodes and 0 elsewhere; and also given the vector of times of the temporal edges $\vt \in \RR^m$:

\begin{equation}\label{eqn:tdlg_adj}
\mA_{ij} = \left( \vb_i^\top \vb_j \right) \cdot \exp\left(- \frac{(t_i - t_j)^2}{2 \sigma_t^2} \right),
\end{equation}

where $\vb_i$ and $\vb_j$ denote columns $i$ and $j$ of $\mB$. Note that $\mA$ is symmetric.

While self-loops in line graphs are generally removed, we keep them here for simplicity. The choice of Gaussian weight decay is somewhat arbitrary, and, in theory, the TDLG concept would also work with, e.g., Laplacian weight decay. We use Gaussian decay since it is well known and effective in practice.

We now describe our approach for temporal edge embedding, classification, and link prediction.

Temporal edge embedding and classification For downstream tasks, we seek temporal edge embeddings, that is, an informative real-valued vector for each temporal edge that can be provided to a classifier. For temporal edge $i$, we simply return the $i^\text{th}$ row of the TDLG adjacency matrix $\mA$. This returns an $m$-dimensional sparse vector as the feature vector. Note that we could reduce the dimensionality of these vectors, e.g., via eigendecomposition, but we find that this is not necessary.
We use the standard supervised learning pipeline for edge classification. Given training data comprising a set of temporal edges and the class labels of some fraction of these edges, the TDLG matrix $\mA$ is created using all of the edges, then a logistic regression classifier is trained using the edges for which the classes are known and the corresponding rows of $\mA$ as feature vectors. After this, the classifier can be used on the remaining rows to make predictions for the remaining edges.

Temporal link prediction We describe the full experimental setup for temporal link prediction in Section <ref>, but essentially, it amounts to binary temporal edge classification where the classes are $+1$ for true/positive edges $(u_i,v_i,t_i)$ and $-1$ for false/negative edges $(u'_i,v'_i,t'_i)$. The difference is that for temporal link prediction, we must additionally be able to form representations for negative edges, as well as for test edges (which are not given when training the classifier). Let subscripts $r$ and $e$ denote training and test edges, respectively. We deal with negative edges exactly the same as positive edges besides the class labels: the positive and negative training edges are concatenated, producing the training incidence matrix $\mB_r \in \{ 0,1 \}^{n \times m_r}$ and times vector $\vt_r \in \RR^{m_r}$, from which we construct the training TDLG adjacency matrix $\mA_{rr} \in \RR^{m_r \times m_r}$ according to Equation <ref>.

The classifier can then be trained using the rows of $\mA_{rr}$ as feature vectors and the edge labels (i.e., positive/negative edge). Now feature vectors for the test edges must each be $m_r$-dimensional and consider only proximity to training edges. Letting the test incidence matrix and test times vector be $\mB_e \in \{ 0,1 \}^{n \times m_e}$ and $\vt_e \in \RR^{m_e}$, the test edge feature vectors will be the rows of the matrix $\mA_{er} \in \RR^{m_e \times m_r}$, the $(i,j)$-th entry of which is given by

\begin{equation*}
\left( \vb_{e\:i} \cdot \vb_{r\:j} \right) \cdot \exp\left(- \frac{(t_{e\:i} - t_{r\:j})^2}{2 \sigma_t^2} \right),
\end{equation*}

which can be passed to the classifier for inference.

§ DEMONSTRATIVE EXAMPLE

To demonstrate the power of our TDLG method at capturing latent structure in temporal graphs, we introduce a simple, natural model for temporal networks based on the stochastic block model (SBM) [Holland et al., 1983]. Our model, called temporal SBM, comprises the union of several SBMs. A normal distribution is attached to each SBM, and the edges drawn from an SBM are given a time which is sampled from its distribution. The formal defintion follows in Definition <ref>.

Consider a set of $n$ nodes partitioned into two equal-sized communities $\{U,V\}$. For some integer $\Delta > 0$ and real numbers $0<\alpha_1,\alpha_2<1$, construct a random temporal edge set over this graph as follows:
Let there be $\frac{\Delta \cdot n}{2}$ temporal edges in each of two time periods; the times associated with edges in each time period are drawn from the normal distributions $\mathcal{N}(\mu_{1}, \sigma_{1}^2)$ and $\mathcal{N}(\mu_{2}, \sigma_{2}^2)$, respectively.
Of the edges in time period 1, let $(1-\alpha_{1}) \cdot \frac{\Delta \cdot n}{2}$ edges be drawn uniformly at random from $U \times V$, and let the remaining $\alpha_{1} \cdot \frac{\Delta \cdot n}{2}$ edges be drawn half each from $U \times U$ and $V \times V$. Similarly, of the edges in time period 2, let $(1-\alpha_{2}) \cdot \frac{\Delta \cdot n}{2}$ edges be drawn from $U \times V$, and the remaining $\alpha_{2} \cdot \frac{\Delta \cdot n}{2}$ edges be drawn half each from $U \times U$ and $V \times V$.

Here $\Delta$ is the expected degree of each node in each of the two SBMs (so the total degree of each node is $2\cdot \Delta$), and $\alpha_1,\alpha_2$ represent the fraction of edges in each SBM which are intra-community as opposed to inter-community.
Note that this definition can generalize straightforwardly to a union of an arbitrary number of SBMs, potentially with unequal community sizes.

We first construct a TSBM where it is not possible to distinguish any community structure if one ignores temporal information. This TSBM is visualized in Figure <ref>. The graph has $n=100$ nodes, with expected degrees $\Delta=40$, and the time distributions of the two SBMs are $\mathcal{N}\left(-1, (\sfrac{1}{2})^2 \right)$ and $\mathcal{N}\left(+1, (\sfrac{1}{2})^2 \right)$; the distributions have the same variance, but one occurs earlier on average.

Further, we set $\alpha_1=\sfrac{9}{10}$ and $\alpha_2=\sfrac{1}{10}$, so that the mean fraction of intra-community edges is $\tfrac{\alpha_1+\alpha_2}{2} = \sfrac{1}{2}$; this ensures that it is impossible to retrieve community structure without considering time, as is best illustrated in Figure <ref> in the union of the two SBMs, which is simply an Erdős–Rényi graph.

The motivating synthetic temporal network. The adjacency matrix of the early and late edges, as well as their union, then the distribution of times separated by the early and late edges. Note that the early edges are mostly in-group, whereas the late edges are mostly out-group.

We will show that our TDLG method can utilize the time information to recover the node communities.

Since our method produces embeddings for temporal edges, to demonstrate recovery of node communities, we must aggregate the edge embeddings into node embeddings.
Node embeddings can be straightforwardly constructed from edge embeddings as follows: for each node, return the mean of the embeddings of all edges incident on that node. This is described formally in Definition <ref>:

Suppose a network has $n$ nodes and $m$ edges, with incidence matrix $\mB \in \RR^{n \times m}$. Let $\tilde{\mB}$ be the matrix that results from dividing each row of $\mB$ by its sum. Given a matrix of $k$-dimensional edge embeddings $\mY \in \RR^{m \times k}$, produce a matrix of node embeddings $\mX \in \RR^{n \times k}$ via the matrix product $\mX = \tilde{\mB} \mY$.

In Figure <ref>, we show the result of applying our method to this TSBM. In particular, we construct the TDLG with $\sigma_t=\sfrac{1}{2}$

and show the TDLG adjacency matrix, temporal edge embeddings generated from this matrix, and node embeddings generated by Definition <ref>.
Note that while we generally use the raw rows of the TDLG adjacency matrix as edge embeddings (which produces sparse vectors), only in this section, for visualization purposes, we instead use dense eigenvector embeddings.
The embedding visualizations show that our method is recovering the community structure:
The edge embeddings roughly separate the 6 kinds of edges (i.e., edges in $U\times U$, $V \times V$, and $U \times V$ occurring in each of the two time periods), and

further, the node embeddings linearly separate the two node communities $U$ and $V$.

Results of applying our method to the motivating synthetic network of Figure <ref>. The line graph is ordered so that the early edges appear first. The embedding plots show top second and third eigenvectors (in terms of magnitude of eigenvalue) of the TDLG adjacency matrix. Note that the edge types are roughly separated in the edge embeddings, and the node types are linearly separated in the node embeddings.

§ THEORETICAL DISCUSSION

We now discuss our theoretical results, which concern the action of our TDLG method on the proposed TSBM family of synthetic graphs.
We present these results not only to show the power of the TDLG approach, but also to contrast with deep methods, the complexity of which often precludes explicit analysis.
In particular, under certain strong assumptions, our approach's simplicity allows us to give the exact expectation for the TDLG adjacency matrix $\mA$ for TSBMs.
Further, we can show constructively that the TDLG method is able to preserve and disentangle the node community structure of the TSBM: specifically, taking the temporal edge embeddings returned by our method and aggregating them into node embeddings via averaging over a node's incident edges (as in Definition <ref>) yields node embeddings which can distinguish the two node communities.
The assumptions for these two results are as follows: we analyze using the expected TDLG adjacency matrix and the expected incidence matrix, and we assume zero time variance within time periods of the TSBM; these assumptions all simplify the analysis by reducing variance, though perhaps via concentration bounds one could extend such results to the sampled setting [Spielman, 2012].
Also, we will consider TSBMs in the limit as $n\to\infty$ for simplicity of the resulting constant values, but the following analysis would carry through in general with different values.

Suppose $\mA \in \RR^{m \times m}$ is the expected TDLG adjacency matrix of a Temporal SBM graph with node communities $\{U,V\}$, time periods $\{1,2\}$, and zero time variance ($\sigma_{1}^2=\sigma_{2}^2=0$). $\mA$ has a $6 \times 6$ block structure where each block is constant-valued, that is, a multiple of an all-ones matrix $\mJ$ of some dimensionality. Letting subscripts denote time period, the block matrix is indexed by 6 edge sets: $(U \times U)_1$, $(V \times V)_1$, $(U \times V)_1$, $(U \times U)_2$, $(V \times V)_2$, and $(U \times V)_2$. In the limit as $n\to \infty$, the constant values of each block are given by the Kronecker product

code-for-first-row = ,code-for-first-col =

\[
% \begin{pNiceArray}{c:c:c}[first-col]
\begin{pNiceArray}{c|c|c}[first-col]
% & C_1 & \Cdots & & C_4\\
U \times U & \sfrac{8}{n} & 0 & \sfrac{4}{n} \\\hline%\hdashline
V \times V & 0 & \sfrac{8}{n} & \sfrac{4}{n} \\\hline
U \times V & \sfrac{4}{n} & \sfrac{4}{n} & \sfrac{4}{n}
\end{pNiceArray}
\quad \otimes \quad
\begin{pNiceArray}{c|c}[first-col,nullify-dots]
% & C_1 & \Cdots & & C_4\\
1 & 1 & \lambda\\\hline%\hdashline
2 & \lambda & 1
\end{pNiceArray} ,
\]

where $\gamma = \exp\left(-\tfrac{(\mu_1 - \mu_2)^2}{2\sigma_t^2}\right)$.

Note that writing $\mA$ as a Kronecker product involves some abuse of notation, and
the actual sizes of the edge sets (and hence the sizes of the blocks) are as given in Definition <ref>. In the order of Proposition <ref>, these sizes are $\alpha_1 \cdot \tfrac{\Delta \cdot n}{4}$, $\alpha_1 \cdot \tfrac{\Delta \cdot n}{4}$, $(1-\alpha_1) \cdot \tfrac{\Delta \cdot n}{2}$, $\alpha_2 \cdot \tfrac{\Delta \cdot n}{4}$, $\alpha_2 \cdot \tfrac{\Delta \cdot n}{4}$, and $(1-\alpha_2) \cdot \tfrac{\Delta \cdot n}{2}$.

We calculate an entry $\bm{A}_{ij}$ of this matrix. We first consider the effect of the time decay, then the effect of edge adjacency (i.e., $\vb_i^\top \vb_j$).

Given the assumption of zero time variance, there are only two possible values for each temporal edge's time, $\mu_1$ and $\mu_2$. This means effect of time decay on each entry of $\mA$ is multiplication by either $1$, if $i$ and $j$ occur at the same time, or otherwise $\gamma$.

Second, we calculate the expected value of $\vb_i^\top \vb_j$, that is, the expected number of endpoint nodes shared between edges $i$ and $j$.
Suppose both $i$ and $j$ are in $U \times U$. Since there are $\sfrac{n}{2}$ nodes in $U$, the probability of any two random nodes in $U$ being the same is $\sfrac{2}{n}$. There are 4 pairs of endpoints in $U$ between $i$ and $j$; in the assumed $n\to \infty$ limit, the 4 events of these pairs each having the same two nodes tend toward independence, so $\vb_i \cdot \vb_j = 4\cdot \sfrac{2}{n}$ = 8n. By similar logic, if $i$ is in $U \times U$ and $j$ is in $U \times V$, there are 2 pairs of endpoints that could be identical (each of $i$'s nodes in $U$ with the single node of $j$ in $U$), so $\vb_i \cdot \vb_j = 2\cdot \sfrac{2}{n}$ = 4n. The same holds if both $i$ and $j$ are in $U \times V$. Finally, if $i$ is in $U \times U$ and $j$ is in $V \times V$, there is zero chance of a shared endpoint. Remaining combinations follow by symmetry.

Combining the terms for time decay and edge adjacency, the expected TDLG adjacency matrix has the specified $6 \times 6$ block structure.

We now state the second result, about the ability to distinguish TSBM node communities using the TDLG method. This result requires that it is not the case that $\alpha_1 = \alpha_2 = \sfrac{1}{2}$; in this case of TSBM, the SBMs at both time periods are Erdős–Rényi, so there is no community structure to recover.

Suppose  is the expected TDLG adjacency matrix of a Temporal SBM graph with node communities $\{U,V\}$, time periods $\{1,2\}$, and zero time variance ($\sigma_{1}^2=\sigma_{2}^2=0$). Let $\mX \in \RR^{n \times m}$ be the mean-edge node embeddings resulting from treating the rows of $\mA$ as edge embeddings.
Assuming that $\gamma \neq 1$ and it is not the case that $\alpha_1 = \alpha_2 = \sfrac{1}{2}$, the node communities are distinguishable in $\mX$.

For brevity, the proof is deferred to Appendix <ref>. It essentially involves the same flavor of counting-based arguments as Proposition <ref>, though it is much more involved.
As part of this proof, we provide a description of part of the expected block structure of the resulting node embeddings $\mX$, similar to the preceding description of the TDLG adjacency matrix $\mA$. When time decay is not applied (i.e., by setting $\gamma=1$), we find that nodes in $U$ and $V$ become indistinguishable in the derived embeddings for TSBMs with $\alpha_1+\alpha_2=1$, as opposed to just when $\alpha_1 = \alpha_2 = 1/2$. These are TSBMs like the one from Figure <ref>, which do have community structure when considering time, but become Erdős–Rényi graphs when ignoring time.

We can write the block structure of the expected incidence matrix $\mB$ as follows:

code-for-first-row = ,code-for-first-col =

\[\mB = \quad
\begin{pNiceArray}{c:c:c:c:c:c}[first-col,first-row,nullify-dots]
& (U \times U)_1 & (V \times V)_1 & (U \times V)_1 & (U \times U)_2 & (V \times V)_2 & (U \times V)_2\\
U & \sfrac{4}{n} & 0 & \sfrac{2}{n} & \sfrac{4}{n} & 0 & \sfrac{2}{n} \\\hdashline
V & 0 & \sfrac{4}{n} & \sfrac{2}{n} & 0 & \sfrac{4}{n} & \sfrac{2}{n} \\
\end{pNiceArray},
\]

where the entries come from the same logic as for the edge adjacency terms for $\mA$, e.g., a random edge in $(U \times U)_1$ has two endpoints in $U$, and each is equal to some random node in $U$ with probability $\sfrac{2}{n}$, yielding $2\cdot \sfrac{2}{n}=\sfrac{4}{n}$ for the first entry. The sum of each row is

\[ \alpha_1 \cdot \tfrac{\Delta \cdot n}{2} \cdot \tfrac{4}{n} + (1-\alpha_1) \cdot \tfrac{\Delta \cdot n}{2} \cdot \tfrac{2}{n} + \alpha_2 \cdot \tfrac{\Delta \cdot n}{2} \cdot \tfrac{4}{n} + (1-\alpha_2) \cdot \tfrac{\Delta \cdot n}{2} \cdot \tfrac{2}{n} = 2\Delta ,\]

so the block structure of the row-normalized incidence matrix $\tilde{\mB}$ is

code-for-first-row = ,code-for-first-col =

\[\tilde{\mB} = \quad
\begin{pNiceArray}{c:c:c:c:c:c}[first-col,first-row,nullify-dots]
& (U \times U)_1 & (V \times V)_1 & (U \times V)_1 & (U \times U)_2 & (V \times V)_2 & (U \times V)_2\\
U & \sfrac{2}{(\Delta n)} & 0 & \sfrac{1}{(\Delta n)} & \sfrac{2}{(\Delta n)} & 0 & \sfrac{1}{(\Delta n)} \\\hdashline
V & 0 & \sfrac{2}{(\Delta n)} & \sfrac{1}{(\Delta n)} & 0 & \sfrac{2}{(\Delta n)} & \sfrac{1}{(\Delta n)} \\
\end{pNiceArray}.
\]

Finally, we can perform the matrix multiplication $\tilde{\mB}\mA$ to yield the expected mean-edge node embeddings. This node embedding matrix itself has a $2 \times 6$ block structure. We give the calculations for $3$ of these blocks, from which the rest follow by symmetry:

\begin{align*}
U , (U \times U)_1: &
\left( \tfrac{8}{n} \cdot \tfrac{2}{\Delta n} \cdot \tfrac{\alpha_1 \Delta n}{4} + \tfrac{4}{n} \cdot \tfrac{1}{\Delta n} \cdot \tfrac{(1-\alpha_1) \Delta n}{2} \right) + \gamma \left( \tfrac{8}{n} \cdot \tfrac{2}{\Delta n} \cdot \tfrac{\alpha_2 \Delta n}{4} + \tfrac{4}{n} \cdot \tfrac{1}{\Delta n} \cdot \tfrac{(1-\alpha_2) \Delta n}{2} \right) \\
&= \tfrac{2}{n}\left( (1+\alpha_1) + \gamma (1+\alpha_2) \right) \\
U , (V \times V)_1: &
\left( \tfrac{4}{n} \cdot \tfrac{1}{\Delta n} \cdot \tfrac{(1-\alpha_1) \Delta n}{2} \right) + \gamma \left( \tfrac{4}{n} \cdot \tfrac{1}{\Delta n} \cdot \tfrac{(1-\alpha_2) \Delta n}{2} \right) \\
&= \tfrac{2}{n}\left( (1-\alpha_1) + \gamma (1-\alpha_2) \right) \\
U , (U \times V)_1: &
\left( \tfrac{4}{n} \cdot \tfrac{2}{\Delta n} \cdot \tfrac{\alpha_1 \Delta n}{4} + \tfrac{4}{n} \cdot \tfrac{1}{\Delta n} \cdot \tfrac{(1-\alpha_1) \Delta n}{2} \right) + \gamma \left( \tfrac{4}{n} \cdot \tfrac{2}{\Delta n} \cdot \tfrac{\alpha_2 \Delta n}{4} + \tfrac{4}{n} \cdot \tfrac{1}{\Delta n} \cdot \tfrac{(1-\alpha_2) \Delta n}{2} \right) \\
&= \tfrac{2}{n}\left( 1 + \gamma \right).
\end{align*}

We can finally write the block structure of the mean-edge node embeddings themselves:

code-for-first-row = ,code-for-first-col =

\[\frac{\tilde{\mB} \mA}{\sfrac{2}{n}} =
\begin{pNiceArray}{c:c:c:c:c:c}[first-col,first-row,nullify-dots]
& (U \times U)_1 & (V \times V)_1 & (U \times V)_1 & (U \times U)_2 & (V \times V)_2 & (U \times V)_2\\
U & \begin{matrix}\phantom{+\gamma}(1+\alpha_1)\\+\gamma (1+\alpha_2)\end{matrix} & \begin{matrix}\phantom{+\gamma}(1-\alpha_1)\\+\gamma (1-\alpha_2)\end{matrix} & \begin{matrix}1+\gamma \end{matrix} &
\begin{matrix}\phantom{+\gamma}(1+\alpha_2)\\+\gamma (1+\alpha_1)\end{matrix} & \begin{matrix}\phantom{+\gamma}(1-\alpha_2)\\+\gamma (1-\alpha_1)\end{matrix} & \begin{matrix}1+\gamma \end{matrix} \\\hdashline
V & \begin{matrix}\phantom{+\gamma}(1-\alpha_1)\\+\gamma (1-\alpha_2)\end{matrix} & \begin{matrix}\phantom{+\gamma}(1+\alpha_1)\\+\gamma (1+\alpha_2)\end{matrix} & \begin{matrix}1+\gamma \end{matrix} &
\begin{matrix}\phantom{+\gamma}(1-\alpha_2)\\+\gamma (1-\alpha_1)\end{matrix} & \begin{matrix}\phantom{+\gamma}(1+\alpha_2)\\+\gamma (1+\alpha_1)\end{matrix} & \begin{matrix}1+\gamma \end{matrix}
\end{pNiceArray}.
\]

Note that the $U$ and $V$ row groups are distinct and not multiples of each other, and hence are linearly separable.

§ RELATED WORK

Node embeddings Many methods have been proposed over the years for the node embedding task. The best understood are the classical `spectral' methods based on eigendecomposition of the graph's adjacency matrix or Laplacian [Roweis & Saul, 2000, Belkin & Niyogi, 2001]. Perhaps the most famous non-spectral method is DeepWalk [Perozzi et al., 2014], which takes random walks on the graph, then, using a nonlinear, probabilistic objective, increases the similarity of the embeddings of nodes which frequently co-occur in the walks. Similar methods include node2vec [Grover & Leskovec, 2016], which adds bias to the random walks, and LINE [Tang et al., 2015], which increases scalability. GraRep [Cao et al., 2015] and NetMF [Qiu et al., 2018] incorporate both matrix factorization like the classical methods and nonlinear objectives like the recent ones, yielding good speed and performance. Unsupervised deep learning approaches, like VGAE [Kipf & Welling, 2016] and SDNE [Wang et al., 2016], involve deep autoencoders; besides this, there is a wide array of supervised deep models which implicitly form node representations, including graph convolutional networks (GCNs) [Kipf & Welling, 2017] and graph attention networks (GATs) [Veličković et al., 2018].

Edge embeddings
The task of creating vector representations for each edge, rather than each node, has seen less exploration. A common strategy is to simply create node embeddings, then process them into edge embeddings by aggregating the embeddings of the two endpoints of an edge. In particular, this is done by taking the mean, entrywise product, cross product, or concatenation of the two node embedding vectors. Notably, node2vec uses this strategy for link prediction; Shi et al., 2018 and Verma et al., 2019 are more examples where this is part of a larger framework.
More along the lines of our method, though still not involving temporal networks, Bandyopadhyay et al., 2019 produce edge representations in an unsupervised manner by embedding the nodes of the line graph of the original network.

The method of Li et al., 2017 implicitly takes a similar approach by taking a random walk on the edges and iteratively updating edge embeddings, as DeepWalk does for node embeddings.
Some graph deep learning approaches [Monti et al., 2018, Gong & Cheng, 2019] include layers which form edge embeddings, but do so as part of a supervised framework; by contrast, Zhou et al., 2018 propose an unsupervised deep method based on generative adversarial networks, though their approach is fairly complicated.
Also of note, though not directly applicable to the standard or temporal edge setting, several works in the area of knowledge graphs form embeddings of relations between entities [Bordes et al., 2013, Yang et al., 2014, Chen & Quirk, 2019].

Embeddings for temporal networks
Many methods for temporal network embedding can be seen as variants of those for static graphs.
Dunlavy et al., 2011 propose a variant of factorization-based approaches, intended for a dynamic network comprising snapshots of static graphs at consecutive intervals of time. It directly incorporates time information by stacking adjacency matrices of different time steps and employing tensor factorization.
DANE [Li et al., 2017] is another factorization approach, though it only factorizes matrices. To boost efficiency, rather than computing node embeddings from scratch for each snapshot, DANE iteratively updates the embeddings from the previous time step according to the change in the network; TIMERS [Zhang et al., 2018] is a similar approach which analyzes the growth of the error over iterative updates to determine when it is necessary to re-embed from scratch.
NetWalk [Yu et al., 2018] is a variant of random walk-based methods like DeepWalk; along the same lines, it saves time by efficiently updating embeddings at each snapshot using warm starts and reservoir sampling.
CTDNE [Nguyen et al., 2018] is another random walk method which incorporates time information using the constraint that the walks must obey time. Notably, like our method, CTDNE is designed for networks with continuous time rather than just snapshots of different time intervals.

Among unsupervised deep approaches, DynGEM [Goyal et al., 2018] is an autoencoder method which again uses warm starts for each snapshot, both for speed and to encourage embeddings to be approximately preserved across time steps; DynGraph2Vec [Goyal et al., 2020] more directly allows information at different snapshots to be integrated by employing an RNN to evolve representations across time steps.
The similarly-named DyLink2Vec [Rahman et al., 2018] is another deep autoencoder approach, which also integrates information across time steps; notably, like our method, it yields embeddings for links rather than nodes, though it works on snapshots rather than continuous time.
More recently, EvolveGCN [Pareja et al., 2020] proposes the interesting idea of using an RNN to evolve not the node embeddings, but the weights of a GCN model which generates embeddings for each snapshot.
Some deep methods also handle continuous time: using point processes,  Know-Evolve [Trivedi et al., 2017], HTNE [Zuo et al., 2018], and DyRep [Trivedi et al., 2019] model the occurrence of temporal edges, while Dynamic-Triad [Zhou et al., 2018] aims to capture structural information by modeling the closure of wedges into triangles over time.
Most of these approaches are principally node embedding methods from which edge embeddings can be generated by aggregation; to our knowledge, ours is the first work which directly forms embeddings for continuous-time temporal edges without supervision and without aggregating node embeddings.

§ EXPERIMENTS

We evaluate our method on two kinds of tasks, edge classification and temporal link prediction, on a collection of five real-world temporal network datasets. The statistics for these networks are provided in Table <ref>, but we defer discussion of these datasets to Appendix <ref>.

Statistics of datasets used in our experiments.

Dataset      # Nodes	     # Edges	     Time Span (days)

bitcoinalpha        3783	     24186	     1901

bitcoinotc          5881	     35592	     1903

escorts 		    10106	     50632	     2232

wikielect 		    7118	     107071	     1378

epinions 		    131828	     841372	     943

§.§ Edge classification

Experimental setup
We use a logistic regression classifier to which the input is a feature vector for each edge of the network and the target is a binary edge class.
We make random 70%/30% splits of training/test data, and report test AUC of binary classification across 10 trials with 10 random splits.

In addition to results for our TDLG method's sparse embeddings, we report results for several other methods.
We compare to results for some prior methods applied to these datasets: 1) CTDNE [Nguyen et al., 2018]; 2) TIMERS [Zhang et al., 2018]; 3) EvolveGCN [Pareja et al., 2020]; 4) DynGEM [Goyal et al., 2018]; 5) GCRN [Seo et al., 2018]; and 6) VGRNN [Hajiramezanali et al., 2019].
Note that these methods output $128$-dimensional dense embeddings, unlike our TDLG method, which outputs $m$-dimensional sparse embeddings; for an additional, direct comparison, we also report results for using the top $128$ eigenvectors (i.e., those with highest magnitude eigenvalues) of the TDLG adjacency matrix (`TDLG Dense').

With the exception of the methods we introduce and CTDNE, all other methods do not directly handle the continuous time stamps of the datasets; for these methods, we slot the edges into discrete snapshots by evenly dividing the full time span into 20 intervals.
All experiments are run on an Xeon Gold 6130 CPU and Tesla v100 16GB GPU; only the latter four methods (i.e., the deep methods) use the GPU, and we are unable to run these four methods on Epinions due to GPU memory limitations.

Hyperparameter selection For all embedding methods, we use the scikit-learn [Pedregosa et al., 2011] implementation of logistic regression; we increase the maximum iterations to $10^3$, and, since the edge classes are generally imbalanced across the datasets, we set the  option to `balanced,' which adjusts loss weights inversely in proportion to class frequency. We keep otherwise default options.

For our TDLG method, we set the time scale hyperparameter $\sigma_t$ as ratio of the standard deviation of the edges' times; calling this standard deviation be $\sigma_T$, we use $\sigma_t = 10^{-1} \cdot \sigma_T$, which is chosen by informal tuning.
In Appendix <ref>, we explore the impact of varying $\sigma_t$.
We use the implementation of Liu et al., 2020 for TIMERS and all deep methods, all with default hyperparameters.

For the Epinions dataset only, for our TDLG method, we modify the solver for sparse logistic regression to the `saga' solver, which is more scalable than the default `lbfgs' solver, and reduce the maximum number of iterations to 100 (the default value).

We first plot mean AUC and 95% confidence intervals for selected methods - our TDLG, CTDNE, TIMERS, EvolveGCN, and DynGEM - on all datasets in Figure <ref>. Our TDLG method achieves higher performance than the comparison methods on all datasets, often by a large margin.

Test AUC on the edge classification task for real-world datasets using our TDLG method, CTDNE, TIMERS, EvolveGCN, and DynGEM.

To compactly compare all 9 of the methods across these datasets, we aggregate the performance across the datasets as follows: we plot the mean across all datasets, excluding Epinions, of each method's test AUC. We exclude Epinions since we are unable to run some methods on this dataset. See Figure <ref> (left).
TDLG achieves the highest performance out of all these methods on all datasets; the dense variant of TDLG, which perhaps provides more direct comparison with other methods, sees reduced performance, but also outperforms all prior methods.
Tables of full experimental results are deferred to Appendix <ref>.

Test AUC on all three tasks, aggregated across datasets: mean performance over the evaluated real-world datasets, excluding Epinions.

Runtime We evaluate the time efficiency of our approach against the selected baseline methods. For this, we report the mean runtime in seconds for one trial of edge classification. Runtime constitutes one trial of learning embeddings, learning a logistic regression classifier on training data, and predicting on test data. See Figure <ref>. Across all five datasets, our TDLG method is the fastest, often by a significant margin.

Runtime (seconds) on the edge classification task.

§.§ Link Prediction

Experimental setup
Given the dataset of actual, `positive' edge tuples $(u_i,v_i,t_i)$, we generate an equal-sized set of fake, `negative' edges by independently shuffling the three columns (i.e., independently shuffling the set of first nodes, the set of second nodes, and the times). Note that this preserves the distribution nodes/times in of each of the columns. The task is to distinguish positive edges from negative ones.
We evaluate two different settings for link prediction. In the first, which we call temporal link outlier detection, the test edges are in the same time interval as the training edges. In the second, which we call temporal link prediction, the test edges are in an interval of time following that of the training data. We also call these settings `interpolative' and `extrapolative,' respectively. Prior work generally focuses on the latter setting, since it is more applicable, e.g., for predicting future events/behavior, but we also evaluate the former mainly out of scientific interest.

Specifically, given that we are splitting the data into 20 intervals, we consider intervals 1-19 to be `early' data and interval 20 to be `late' data. To share computational effort across the two settings, we train both classifiers on 70% of edges (both positive and negative) from the early intervals. For the interpolative setting, the test data comprises the remaining 30% of edges from the early intervals. For the extrapolative setting, the test data comprises all edges from the late interval.
Evaluating the link prediction task has greater computational cost compared to edge classification since the input graph changes across trials rather than just train/test splits of labels, requiring new embeddings to be made for each trial. For this reason, we only test the 5 selected methods from the previous section. We report mean AUC and 95% confidence intervals across 5 trials, each trial having different random shuffles producing different negative edges, as well as different 70%/30% train/test splits.

Hyperparameter selection We generally use the same hyperparameters as for edge classification, with one exception: since there is an equal number of positive and negative edges, we no longer set the  option to `balanced,' and all edges are given equal weight.

We plot mean AUC and 95% confidence intervals for all datasets, for both the interpolative and extrapolative settings of link prediction, in Figure <ref>.
As for edge classification, we also plot the aggregated (mean) performance across datasets in Figure <ref> (right).
In both settings, across all datasets, our TDLG method achieves the highest performance, often by a large margin.
We do find that the deep methods EvolveGCN and DynGEM generally perform better than CTDNE and TIMERS, and EvolveGCN in particular is competitive with TDLG on some datasets.

Test AUC on the interpolative (top) and extrapolative (bottom) link prediction tasks using our TDLG method, CTDNE, TIMERS, EvolveGCN, and DynGEM.

§ CONCLUSION

We present a novel framework for temporal edge embedding called the time-decayed line graph (TDLG). Unlike prior methods, our method works directly with continuous timestamps rather than requiring discretization of times, and directly generates temporal edge embeddings rather than requiring aggregation of node embeddings. Also in contrast to prior methods, ours has a very simple concept and high ease of implementation, since it is essentially based on creating a sparse matrix of proximities between temporal edges. We show that, despite its simplicity, our method achieves superior performance on several downstream tasks on benchmark temporal network datasets, while requiring less runtime. Its simplicity also facilitates theoretical demonstrations of its effectiveness on our proposed TSBM family of graphs.

An interesting direction for future work is further increasing scalability via reduction of the number of features. The TDLG method returns $m$ features per temporal edge based on proximities to all other temporal edges. Perhaps it is possible to efficiently reduce the feature space by only considering proximities to certain edges, e.g., edges with higher effective resistances. Along the same lines, it may also be interesting to explore ways of reducing the feature space by efficiently forming a low-rank representation of the TDLG adjacency matrix, for example, via a stochastic method.

[Bandyopadhyay et al., 2019]
Sambaran Bandyopadhyay, Anirban Biswas, M Narasimha Murty, and Ramasuri
Beyond node embedding: A direct unsupervised edge representation
framework for homogeneous networks.
arXiv preprint arXiv:1912.05140, 2019.

[Belkin & Niyogi, 2001]
Mikhail Belkin and Partha Niyogi.
Laplacian eigenmaps and spectral techniques for embedding and
Advances in neural information processing systems, 14, 2001.

[Bordes et al., 2013]
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana
Translating embeddings for modeling multi-relational data.
Advances in Neural Information Processing Systems, 26, 2013.

[Cao et al., 2015]
Shaosheng Cao, Wei Lu, and Qiongkai Xu.
Grarep: Learning graph representations with global structural
In Proceedings of the 24th ACM International on Conference on
Information and Knowledge Management, pp.  891–900, 2015.

[Chen & Quirk, 2019]
Muhao Chen and Chris Quirk.
Embedding edge-attributed relational hierarchies.
In Proceedings of the 42nd International ACM SIGIR Conference
on Research and Development in Information Retrieval, pp.  873–876, 2019.

[Dunlavy et al., 2011]
Daniel M Dunlavy, Tamara G Kolda, and Evrim Acar.
Temporal link prediction using matrix and tensor factorizations.
ACM Transactions on Knowledge Discovery from Data (TKDD),
50 (2):0 1–27, 2011.

[Gong & Cheng, 2019]
Liyu Gong and Qiang Cheng.
Exploiting edge features for graph neural networks.
In Proceedings of the IEEE/CVF conference on computer vision
and pattern recognition, pp.  9211–9219, 2019.

[Goyal et al., 2018]
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu.
Dyngem: Deep embedding method for dynamic graphs.
In IJCAI Workshop on Representation Learning for Graphs, 2018.

[Goyal et al., 2020]
Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo.
dyngraph2vec: Capturing network dynamics using dynamic graph
representation learning.
Knowledge-Based Systems, 187:0 104816, 2020.

[Grover & Leskovec, 2016]
Aditya Grover and Jure Leskovec.
node2vec: Scalable feature learning for networks.
In Proceedings of the 22nd ACM SIGKDD international conference
on Knowledge discovery and data mining, pp.  855–864, 2016.

[Hajiramezanali et al., 2019]
Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield,
Mingyuan Zhou, and Xiaoning Qian.
Variational graph recurrent neural networks.
Advances in Neural Information Processing Systems, 32, 2019.

[Holland et al., 1983]
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.
Stochastic blockmodels: First steps.
Social networks, 50 (2):0 109–137, 1983.

[Kipf & Welling, 2016]
Thomas N Kipf and Max Welling.
Variational graph auto-encoders.
arXiv preprint arXiv:1611.07308, 2016.

[Kipf & Welling, 2017]
Thomas N Kipf and Max Welling.
Semi-supervised classification with graph convolutional networks.
International Conference on Learning Representations, 2017.

[Kumar et al., 2016]
Srijan Kumar, Francesca Spezzano, VS Subrahmanian, and Christos Faloutsos.
Edge weight prediction in weighted signed networks.
In Data Mining (ICDM), 2016 IEEE 16th International Conference
on, pp.  221–230. IEEE, 2016.

[Kumar et al., 2018]
Srijan Kumar, Bryan Hooi, Disha Makhija, Mohit Kumar, Christos Faloutsos, and
VS Subrahmanian.
Rev2: Fraudulent user prediction in rating platforms.
In Proceedings of the Eleventh ACM International Conference on
Web Search and Data Mining, pp.  333–341. ACM, 2018.

[Leskovec & Sosič, 2016]
Jure Leskovec and Rok Sosič.
Snap: A general-purpose network analysis and graph-mining library.
ACM Transactions on Intelligent Systems and Technology (TIST),
80 (1):0 1, 2016.

[Leskovec et al., 2010]
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg.
Signed networks in social media.
In Proceedings of the SIGCHI Conference on Human Factors in
Computing Systems, pp.  1361–1370. ACM, 2010.

[Li et al., 2017]
Jundong Li, Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang, and Huan Liu.
Attributed network embedding for learning in a dynamic environment.
In Proceedings of the 2017 ACM on Conference on Information and
Knowledge Management, pp.  387–396, 2017a.

[Li et al., 2017]
Suxue Li, Haixia Zhang, Dalei Wu, Chuanting Zhang, and Dongfeng Yuan.
Edge representation learning for community detection in large scale
information networks.
In International Workshop on Mobility Analytics for
Spatio-temporal and Social Data, pp.  54–72. Springer, 2017b.

[Liu et al., 2020]
Jingxin Liu, Chang Xu, Chang Yin, Weiqiang Wu, and You Song.
K-core based temporal graph convolutional network for dynamic graphs.
IEEE Transactions on Knowledge and Data Engineering, 2020.

[Monti et al., 2018]
Federico Monti, Oleksandr Shchur, Aleksandar Bojchevski, Or Litany, Stephan
Günnemann, and Michael M Bronstein.
Dual-primal graph convolutional networks.
arXiv preprint arXiv:1806.00770, 2018.

[Nguyen et al., 2018]
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, pp.  969–976, 2018.

[Pareja et al., 2020]
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura,
Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson.
Evolvegcn: Evolving graph convolutional networks for dynamic graphs.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 34, pp.  5363–5370, 2020.

[Pedregosa et al., 2011]
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel,
M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos,
D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.
Scikit-learn: Machine learning in Python.
Journal of Machine Learning Research, 12:0 2825–2830,

[Perozzi et al., 2014]
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.
Deepwalk: Online learning of social representations.
In Proceedings of the 20th ACM SIGKDD international conference
on Knowledge discovery and data mining, pp.  701–710, 2014.

[Qiu et al., 2018]
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang.
Network embedding as matrix factorization: Unifying deepwalk, line,
pte, and node2vec.
In Proceedings of the Eleventh ACM International Conference on
Web Search and Data Mining, pp.  459–467, 2018.

[Rahman et al., 2018]
Mahmudur Rahman, Tanay Kumar Saha, Mohammad Al Hasan, Kevin S Xu, and Chandan K
Dylink2vec: Effective feature representation for link prediction in
dynamic networks.
arXiv preprint arXiv:1804.05755, 2018.

[Rossi & Ahmed, 2015]
Ryan A. Rossi and Nesreen K. Ahmed.
The network data repository with interactive graph analytics and
In AAAI, 2015.
URL <https://networkrepository.com>.

[Roweis & Saul, 2000]
Sam T Roweis and Lawrence K Saul.
Nonlinear dimensionality reduction by locally linear embedding.
science, 2900 (5500):0 2323–2326, 2000.

[Seo et al., 2018]
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson.
Structured sequence modeling with graph convolutional recurrent
In International Conference on Neural Information Processing,
pp.  362–373. Springer, 2018.

[Shi & Malik, 2000]
Jianbo Shi and Jitendra Malik.
Normalized cuts and image segmentation.
IEEE Transactions on pattern analysis and machine
intelligence, 220 (8):0 888–905, 2000.

[Shi et al., 2018]
Yu Shi, Qi Zhu, Fang Guo, Chao Zhang, and Jiawei Han.
Easing embedding learning by comprehensive transcription of
heterogeneous information networks.
In Proceedings of the 24th ACM SIGKDD International Conference
on Knowledge Discovery & Data Mining, pp.  2190–2199, 2018.

[Spielman, 2012]
Daniel Spielman.
Spectral graph theory.
Combinatorial Scientific Computing, 18, 2012.

[Tang et al., 2015]
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.
Line: Large-scale information network embedding.
In Proceedings of the 24th international conference on world
wide web, pp.  1067–1077, 2015.

[Trivedi et al., 2017]
Rakshit Trivedi, Hanjun Dai, Yichen Wang, and Le Song.
Know-evolve: Deep temporal reasoning for dynamic knowledge graphs.
In International Conference on Machine Learning, pp.  3462–3471. PMLR, 2017.

[Trivedi et al., 2019]
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha.
Dyrep: Learning representations over dynamic graphs.
In International Conference on Learning Representations, 2019.

[Veličković et al., 2018]
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero,
Pietro Lio, and Yoshua Bengio.
Graph attention networks.
International Conference on Learning Representations, 2018.

[Verma et al., 2019]
Janu Verma, Srishti Gupta, Debdoot Mukherjee, and Tanmoy Chakraborty.
Heterogeneous edge embedding for friend recommendation.
In European Conference on Information Retrieval, pp.  172–179. Springer, 2019.

[Wang et al., 2016]
Daixin Wang, Peng Cui, and Wenwu Zhu.
Structural deep network embedding.
In Proceedings of the 22nd ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, pp.  1225–1234, 2016.

[Yang et al., 2014]
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.
Embedding entities and relations for learning and inference in
knowledge bases.
arXiv preprint arXiv:1412.6575, 2014.

[Yu et al., 2018]
Wenchao Yu, Wei Cheng, Charu C Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang.
Netwalk: A flexible deep embedding approach for anomaly detection in
dynamic networks.
In Proceedings of the 24th ACM SIGKDD International Conference
on Knowledge Discovery & Data Mining, pp.  2672–2681, 2018.

[Zhang et al., 2018]
Ziwei Zhang, Peng Cui, Jian Pei, Xiao Wang, and Wenwu Zhu.
Timers: Error-bounded svd restart on dynamic networks.
In Thirty-second AAAI conference on artificial intelligence,

[Zhou et al., 2021]
Huachi Zhou, Qiaoyu Tan, Xiao Huang, Kaixiong Zhou, and Xiaoling Wang.
Temporal augmented graph neural networks for session-based
In Proceedings of the 44th International ACM SIGIR Conference
on Research and Development in Information Retrieval, pp.  1798–1802,

[Zhou et al., 2018]
Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang.
Dynamic network embedding by modeling triadic closure process.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 32, 2018a.

[Zhou et al., 2018]
Yang Zhou, Sixing Wu, Chao Jiang, Zijie Zhang, Dejing Dou, Ruoming Jin, and
Pengwei Wang.
Density-adaptive local edge representation learning with generative
adversarial network multi-label edge classification.
In 2018 IEEE International Conference on Data Mining (ICDM),
pp.  1464–1469. IEEE, 2018b.

[Zuo et al., 2018]
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, pp.  2857–2866, 2018.

[Bandyopadhyay et al., 2019]
Sambaran Bandyopadhyay, Anirban Biswas, M Narasimha Murty, and Ramasuri
Beyond node embedding: A direct unsupervised edge representation
framework for homogeneous networks.
arXiv preprint arXiv:1912.05140, 2019.

[Belkin & Niyogi, 2001]
Mikhail Belkin and Partha Niyogi.
Laplacian eigenmaps and spectral techniques for embedding and
Advances in neural information processing systems, 14, 2001.

[Bordes et al., 2013]
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana
Translating embeddings for modeling multi-relational data.
Advances in Neural Information Processing Systems, 26, 2013.

[Cao et al., 2015]
Shaosheng Cao, Wei Lu, and Qiongkai Xu.
Grarep: Learning graph representations with global structural
In Proceedings of the 24th ACM International on Conference on
Information and Knowledge Management, pp.  891–900, 2015.

[Chen & Quirk, 2019]
Muhao Chen and Chris Quirk.
Embedding edge-attributed relational hierarchies.
In Proceedings of the 42nd International ACM SIGIR Conference
on Research and Development in Information Retrieval, pp.  873–876, 2019.

[Dunlavy et al., 2011]
Daniel M Dunlavy, Tamara G Kolda, and Evrim Acar.
Temporal link prediction using matrix and tensor factorizations.
ACM Transactions on Knowledge Discovery from Data (TKDD),
50 (2):0 1–27, 2011.

[Gong & Cheng, 2019]
Liyu Gong and Qiang Cheng.
Exploiting edge features for graph neural networks.
In Proceedings of the IEEE/CVF conference on computer vision
and pattern recognition, pp.  9211–9219, 2019.

[Goyal et al., 2018]
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu.
Dyngem: Deep embedding method for dynamic graphs.
In IJCAI Workshop on Representation Learning for Graphs, 2018.

[Goyal et al., 2020]
Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo.
dyngraph2vec: Capturing network dynamics using dynamic graph
representation learning.
Knowledge-Based Systems, 187:0 104816, 2020.

[Grover & Leskovec, 2016]
Aditya Grover and Jure Leskovec.
node2vec: Scalable feature learning for networks.
In Proceedings of the 22nd ACM SIGKDD international conference
on Knowledge discovery and data mining, pp.  855–864, 2016.

[Hajiramezanali et al., 2019]
Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield,
Mingyuan Zhou, and Xiaoning Qian.
Variational graph recurrent neural networks.
Advances in Neural Information Processing Systems, 32, 2019.

[Holland et al., 1983]
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.
Stochastic blockmodels: First steps.
Social networks, 50 (2):0 109–137, 1983.

[Kipf & Welling, 2016]
Thomas N Kipf and Max Welling.
Variational graph auto-encoders.
arXiv preprint arXiv:1611.07308, 2016.

[Kipf & Welling, 2017]
Thomas N Kipf and Max Welling.
Semi-supervised classification with graph convolutional networks.
International Conference on Learning Representations, 2017.

[Kumar et al., 2016]
Srijan Kumar, Francesca Spezzano, VS Subrahmanian, and Christos Faloutsos.
Edge weight prediction in weighted signed networks.
In Data Mining (ICDM), 2016 IEEE 16th International Conference
on, pp.  221–230. IEEE, 2016.

[Kumar et al., 2018]
Srijan Kumar, Bryan Hooi, Disha Makhija, Mohit Kumar, Christos Faloutsos, and
VS Subrahmanian.
Rev2: Fraudulent user prediction in rating platforms.
In Proceedings of the Eleventh ACM International Conference on
Web Search and Data Mining, pp.  333–341. ACM, 2018.

[Leskovec & Sosič, 2016]
Jure Leskovec and Rok Sosič.
Snap: A general-purpose network analysis and graph-mining library.
ACM Transactions on Intelligent Systems and Technology (TIST),
80 (1):0 1, 2016.

[Leskovec et al., 2010]
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg.
Signed networks in social media.
In Proceedings of the SIGCHI Conference on Human Factors in
Computing Systems, pp.  1361–1370. ACM, 2010.

[Li et al., 2017]
Jundong Li, Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang, and Huan Liu.
Attributed network embedding for learning in a dynamic environment.
In Proceedings of the 2017 ACM on Conference on Information and
Knowledge Management, pp.  387–396, 2017a.

[Li et al., 2017]
Suxue Li, Haixia Zhang, Dalei Wu, Chuanting Zhang, and Dongfeng Yuan.
Edge representation learning for community detection in large scale
information networks.
In International Workshop on Mobility Analytics for
Spatio-temporal and Social Data, pp.  54–72. Springer, 2017b.

[Liu et al., 2020]
Jingxin Liu, Chang Xu, Chang Yin, Weiqiang Wu, and You Song.
K-core based temporal graph convolutional network for dynamic graphs.
IEEE Transactions on Knowledge and Data Engineering, 2020.

[Monti et al., 2018]
Federico Monti, Oleksandr Shchur, Aleksandar Bojchevski, Or Litany, Stephan
Günnemann, and Michael M Bronstein.
Dual-primal graph convolutional networks.
arXiv preprint arXiv:1806.00770, 2018.

[Nguyen et al., 2018]
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, pp.  969–976, 2018.

[Pareja et al., 2020]
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura,
Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson.
Evolvegcn: Evolving graph convolutional networks for dynamic graphs.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 34, pp.  5363–5370, 2020.

[Pedregosa et al., 2011]
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel,
M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos,
D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.
Scikit-learn: Machine learning in Python.
Journal of Machine Learning Research, 12:0 2825–2830,

[Perozzi et al., 2014]
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.
Deepwalk: Online learning of social representations.
In Proceedings of the 20th ACM SIGKDD international conference
on Knowledge discovery and data mining, pp.  701–710, 2014.

[Qiu et al., 2018]
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang.
Network embedding as matrix factorization: Unifying deepwalk, line,
pte, and node2vec.
In Proceedings of the Eleventh ACM International Conference on
Web Search and Data Mining, pp.  459–467, 2018.

[Rahman et al., 2018]
Mahmudur Rahman, Tanay Kumar Saha, Mohammad Al Hasan, Kevin S Xu, and Chandan K
Dylink2vec: Effective feature representation for link prediction in
dynamic networks.
arXiv preprint arXiv:1804.05755, 2018.

[Rossi & Ahmed, 2015]
Ryan A. Rossi and Nesreen K. Ahmed.
The network data repository with interactive graph analytics and
In AAAI, 2015.
URL <https://networkrepository.com>.

[Roweis & Saul, 2000]
Sam T Roweis and Lawrence K Saul.
Nonlinear dimensionality reduction by locally linear embedding.
science, 2900 (5500):0 2323–2326, 2000.

[Seo et al., 2018]
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson.
Structured sequence modeling with graph convolutional recurrent
In International Conference on Neural Information Processing,
pp.  362–373. Springer, 2018.

[Shi & Malik, 2000]
Jianbo Shi and Jitendra Malik.
Normalized cuts and image segmentation.
IEEE Transactions on pattern analysis and machine
intelligence, 220 (8):0 888–905, 2000.

[Shi et al., 2018]
Yu Shi, Qi Zhu, Fang Guo, Chao Zhang, and Jiawei Han.
Easing embedding learning by comprehensive transcription of
heterogeneous information networks.
In Proceedings of the 24th ACM SIGKDD International Conference
on Knowledge Discovery & Data Mining, pp.  2190–2199, 2018.

[Spielman, 2012]
Daniel Spielman.
Spectral graph theory.
Combinatorial Scientific Computing, 18, 2012.

[Tang et al., 2015]
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.
Line: Large-scale information network embedding.
In Proceedings of the 24th international conference on world
wide web, pp.  1067–1077, 2015.

[Trivedi et al., 2017]
Rakshit Trivedi, Hanjun Dai, Yichen Wang, and Le Song.
Know-evolve: Deep temporal reasoning for dynamic knowledge graphs.
In International Conference on Machine Learning, pp.  3462–3471. PMLR, 2017.

[Trivedi et al., 2019]
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha.
Dyrep: Learning representations over dynamic graphs.
In International Conference on Learning Representations, 2019.

[Veličković et al., 2018]
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero,
Pietro Lio, and Yoshua Bengio.
Graph attention networks.
International Conference on Learning Representations, 2018.

[Verma et al., 2019]
Janu Verma, Srishti Gupta, Debdoot Mukherjee, and Tanmoy Chakraborty.
Heterogeneous edge embedding for friend recommendation.
In European Conference on Information Retrieval, pp.  172–179. Springer, 2019.

[Wang et al., 2016]
Daixin Wang, Peng Cui, and Wenwu Zhu.
Structural deep network embedding.
In Proceedings of the 22nd ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, pp.  1225–1234, 2016.

[Yang et al., 2014]
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.
Embedding entities and relations for learning and inference in
knowledge bases.
arXiv preprint arXiv:1412.6575, 2014.

[Yu et al., 2018]
Wenchao Yu, Wei Cheng, Charu C Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang.
Netwalk: A flexible deep embedding approach for anomaly detection in
dynamic networks.
In Proceedings of the 24th ACM SIGKDD International Conference
on Knowledge Discovery & Data Mining, pp.  2672–2681, 2018.

[Zhang et al., 2018]
Ziwei Zhang, Peng Cui, Jian Pei, Xiao Wang, and Wenwu Zhu.
Timers: Error-bounded svd restart on dynamic networks.
In Thirty-second AAAI conference on artificial intelligence,

[Zhou et al., 2021]
Huachi Zhou, Qiaoyu Tan, Xiao Huang, Kaixiong Zhou, and Xiaoling Wang.
Temporal augmented graph neural networks for session-based
In Proceedings of the 44th International ACM SIGIR Conference
on Research and Development in Information Retrieval, pp.  1798–1802,

[Zhou et al., 2018]
Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang.
Dynamic network embedding by modeling triadic closure process.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 32, 2018a.

[Zhou et al., 2018]
Yang Zhou, Sixing Wu, Chao Jiang, Zijie Zhang, Dejing Dou, Ruoming Jin, and
Pengwei Wang.
Density-adaptive local edge representation learning with generative
adversarial network multi-label edge classification.
In 2018 IEEE International Conference on Data Mining (ICDM),
pp.  1464–1469. IEEE, 2018b.

[Zuo et al., 2018]
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, pp.  2857–2866, 2018.

§ APPENDIX

§.§ Proof of Proposition <ref>

We restate Proposition <ref> from Section <ref> and provide the deferred proof.
Note that we make a slight change to the notation to facilitate the proof.
As in Section <ref>, we assume the limit as number of nodes $n\to \infty$ for simplicity of the constant values, though it is not crucial to the analysis.

Suppose  is the expected TDLG adjacency matrix of a Temporal SBM graph with node communities $\{U,V\}$, time periods $\{1,2\}$, and zero time variance ($\sigma_{1}^2=\sigma_{2}^2=0$). Let $\tilde{\mX} \in \RR^{n \times m}$ be the mean-edge node embeddings resulting from treating the rows of $\mA$ as edge embeddings.
Assuming that $\gamma \neq 1$ and it is not the case that $\alpha_1 = \alpha_2$ = 12, the node communities are distinguishable in $\mX$.

Recalling Definition <ref> for mean-edge node embeddings, the node embeddings $\tilde{\mX} \in \RR^{n\times m}$ are given by the matrix product $\tilde{\mX} = \tilde{\mB} \mA$, where $\tilde{\mB}$ results from dividing each row of the incidence matrix $\mB \in \R^{n \times m}$ by its sum. Since the expected graph $\mA$ is $(2 \Delta)$-regular by Definition <ref> Earlier after introducing the definition we said that $\Delta$, rather than $2\Delta$ was the expected degree of each node. I think $2\Delta$ is correct so should fix earlier claim., we have $\tilde{\mX} = \left( \sfrac{1}{(2\Delta)} \right) \mB \mA$. For simplicity, for most of this proof, we will skip this division and take $\mX = \mB \mA$; note that $\mX$ are `sum-edge node embeddings,' which result from summing each the edge embeddings of each node's incident edge rather than taking the mean. I think you can do this all without doing the formula $\tilde{\mX} = \left( \sfrac{1}{(2\Delta)} \right) \mB \mA$. Just say that we will consider $\bv{BA}$ which is just an approximate a scaling of $\bv{\tilde B} \bv A$ since the graph is approximately regular.

We will consider the sum-edge node embeddings of two nodes, $u \in U$ and $v \in V$. Let $U' = U \setminus \{u\}$ and $V' = V \setminus \{v\}$. We calculate entries of the embeddings corresponding to $U' \times U'$, $V' \times V'$, and $U' \times V'$ for the two time periods, and show that the two nodes' embeddings are distinct under the assumptions on $\alpha_1,\alpha_2$ and $\gamma$.

We start with the expectation of node $u$'s embedding $\vx_u$, which is a single row of $\mX$ given by $\vb_u \mA$, where $\vb_u$ is the incidence vector of node $u$. Hence, $\vx_u$ is a sum of rows of $\mA$ corresponding to edges which are incident on node $u$.

I think $(u,v)$ is better and more standard notation than $u-v$ for an edge. For a path you can use $(u,v,w)$ This notation makes it easy to discuss paths with edges in different time periods.

Consider the row vector of $\mA$ corresponding to such an edge $u-w$ between distinct nodes $u$ and $w$: this vector has a nonzero entry exactly over columns of $\mA$ corresponding to edges incident to this edge $u-w$; in particular, by the assumption of zero time variance, the nonzero entries are $1$ if the incident edges are in the same time period, otherwise $\gamma$. These incident edges are of the form $w-z$ or $u-z$ for some node $z$. Since we ignore entries of the embedding vectors corresponding to columns of the latter type (due to only considering columns involving edges between $U',V'$ rather than $U,V$), the expectation of entries of $\vx_u$ can be calculated by counting the contributions of paths of length 2 of the form $u-w-z$ with $u \neq w,z$.

This actually confused me. If we look at a column corresponding to an edge in $U' \times U'$ then it is of the form $(w,v)$ for $w,z \in U'$. But it could still be incident to edges that touch $u$. And in fact, it is – these are the quantities we count. I think you need to say something like: focus on a particular entry of the embedding vector corresponding to an edge $(w,v) \in U' \times U'$. This entry is given by $b_u A_{w,v}$ where $A_{w,v}$ is the appropriate column, and so is the sum of edges incident to $u$ which are incident to $(w,v)$. Then you can compute its expectation right?
There is probably a better way to phrase what I am saying, but I don't see a contradiction between what you wrote and my preceding paragraph. What I am saying is that by ignoring columns involving $u$, we don't need to consider paths like $u_i-u-u_j$, i.e., clique paths.

First, consider the $(U' \times U')_1$ block of $\vx_u$. Contributions to this block must come from paths of the form $u \dashone u_i \dashone u_j$ or $u \dashtwo u_i \dashone u_j$ with $u_i,u_j \in U'$, where the number above the dash denotes the time period of the edge.

For the former possibility of $u \dashone u_i \dashone u_j$, there are $\alpha_1 \Delta$ such edges $u \dashone u_i$ (i.e., intra-community edges from $u$ in period 1), and for each node $u_i \in U'$, there are also $\alpha_1 \Delta$ edges of the form $u_i \dashone u_j$ to some node $u_j \in U'$. Hence the total number of $u \dashone u_i \dashone u_j$ paths is the product $\alpha_1^2 \Delta^2$, and since both edges in such paths are in period 1, there is no time decay.
For the latter possibility of $u \dashtwo u_i \dashone u_j$, there are $\alpha_2 \Delta$ edges $u \dashtwo u_i$ (intra-community edges from $u$ in period 2), and through each of these edges, there are $\alpha_1 \Delta$ such paths $u \dashtwo u_i \dashone u_j$; hence the total number of such paths is $\alpha_1 \alpha_2 \Delta^2$, and due to time decay, their total contribution is $\gamma \alpha_1 \alpha_2 \Delta^2$.
Therefore, the sum of the $(U' \times U')_1$ block of $\vx_u$ is $\left( \alpha_1^2 + \gamma \alpha_1 \alpha_2 \right) \Delta^2$. It follows that the sum of the $(U' \times U')_1$ block of $\tilde{\vx}_u$ is $\left( \sfrac{1}{(2\Delta)} \right) \left( \alpha_1^2 + \gamma \alpha_1 \alpha_2 \right) \Delta^2 = \left( \alpha_1^2 + \gamma \alpha_1 \alpha_2 \right) \tfrac{\Delta}{2} $. Since there are $\alpha_1 \tfrac{\Delta n}{4}$ edges in $(U' \times U')_1$, the expected value of an entry in this block is $\left( \alpha_1 + \gamma \alpha_2 \right)( \sfrac{2}{n} )$.

Second, consider the $(V' \times V')_1$ block of $\vx_u$. Contributions to this block must come from paths of the form $u \dashone v_i \dashone v_j$ or $u \dashtwo v_i \dashone v_j$ with $v_i,v_j \in V'$.
For the former possibility of $u \dashone v_i \dashone v_j$, there are $(1-\alpha_1) \Delta$ such edges $u \dashone v_i$ (i.e., inter-community edges from $u$ in period 1), and for each node $v_i \in V'$, there are $\alpha_1 \Delta$ edges of the form $v_i \dashone v_j$ to some node $v_j \in V'$ (intra-community edges from $v_i$ in period 1). Hence the total number of $u \dashone v_i \dashone v_j$ paths is the product $\alpha_1 (1-\alpha_1) \Delta^2$, and since both edges in such paths are in period 1, there is no time decay.
For the latter possibility of $u \dashtwo v_i \dashone v_j$, there are $(1-\alpha_2) \Delta$ edges $u \dashtwo v_i$ (inter-community edges from $u$ in period 2), and through each of these edges, there are $\alpha_1 \Delta$ such paths $u \dashtwo v_i \dashone v_j$; hence the total number of such paths is $\alpha_1 (1-\alpha_2) \Delta^2$, and due to time decay, their total contribution is $\gamma \alpha_1 (1-\alpha_2) \Delta^2$.
Therefore, the sum of the $(V' \times V')_1$ block of $\vx_u$ is $\left( \alpha_1 (1-\alpha_1) + \gamma \alpha_1 (1-\alpha_2) \right) \Delta^2$. As before, it follows that the expected value of an entry in the $(V' \times V')_1$ block of $\tilde{\vx}_u$, which also contains $\alpha_1 \tfrac{\Delta n}{4}$ edges/entries, is $\left( (1-\alpha_1) + \gamma (1-\alpha_2) \right) ( \sfrac{2}{n} )$.

Third, consider the $(U' \times V')_1$ block of $\vx_u$. Contributions to this block must come from paths of the form $u \dashone u_i \dashone v_i$, $u \dashone v_i \dashone u_i$, $u \dashtwo u_i \dashone v_i$, or $u \dashtwo v_i \dashone u_i$, with $u_i \in U'$ and $v_i \in V'$. As before, we sum the contributions each kind of path, yielding

\begin{equation*}
\left( \alpha_1 (1-\alpha_1) + (1-\alpha_1)^2 + \gamma \alpha_2 (1-\alpha_1) + \gamma (1-\alpha_2) (1-\alpha_1) \right) \Delta^2
= (1+\gamma)(1-\alpha_1)\Delta^2
\end{equation*}

for the sum of the $(U' \times V')_1$ block of $\vx_u$. It follows that the expected value of an entry in the $(U' \times V')_1$ block of $\tilde{\vx}_u$, which contains $(1-\alpha_1) \tfrac{\Delta n}{2}$ edges/entries, is $\left( 1 + \gamma \right) ( \sfrac{1}{n} )$.

Note that the expected values of entries in the $(U' \times U')_2$, $(V' \times V')_2$, and $(U' \times V')_2$ follow from these results by symmetry, by simply swapping $\alpha_1$ and $\alpha_2$. The embedding $\tilde{\vx}_v$ for the node in $V$ also follows by symmetry.
We can finally write the block structure of the mean-edge node embeddings $\tilde{\vx}_u$ and $\tilde{\vx}_v$ for these nodes. As with the expected adjacency matrix Proposition <ref>, the blocks are constant in value, and these values are given by $\sfrac{2}{n}$ times

code-for-first-row = ,code-for-first-col =

\[
\begin{pNiceArray}{c|c|c|c|c|c}[first-col,first-row,nullify-dots]
& (U' \times U')_1 & (U' \times U')_2 & (V' \times V')_1 & (V' \times V')_2 & (U' \times V')_1 & (U' \times V')_2\\
u & \begin{matrix}\phantom{+\gamma}\alpha_1\\+\gamma \alpha_2\end{matrix} & \begin{matrix}\phantom{+\gamma}\alpha_2\\+\gamma \alpha_1\end{matrix} &
\begin{matrix}\phantom{+\gamma}(1-\alpha_1)\\+\gamma (1-\alpha_2)\end{matrix} &
\begin{matrix}\phantom{+\gamma}(1-\alpha_2)\\+\gamma (1-\alpha_1)\end{matrix} &\begin{matrix}\tfrac{1}{2}(1+\gamma) \end{matrix} &\begin{matrix}\tfrac{1}{2}(1+\gamma) \end{matrix} \\\hline
v & \begin{matrix}\phantom{+\gamma}(1-\alpha_1)\\+\gamma (1-\alpha_2)\end{matrix} &
\begin{matrix}\phantom{+\gamma}(1-\alpha_2)\\+\gamma (1-\alpha_1)\end{matrix} & \begin{matrix}\phantom{+\gamma}\alpha_1\\+\gamma \alpha_2\end{matrix} & \begin{matrix}\phantom{+\gamma}\alpha_2\\+\gamma \alpha_1\end{matrix} &\begin{matrix}\tfrac{1}{2}(1+\gamma) \end{matrix} &\begin{matrix}\tfrac{1}{2}(1+\gamma) \end{matrix}
\end{pNiceArray}.
\]

As desired, the embeddings for nodes $u$ and $v$ are distinct as long as both $\gamma \neq 1$ and it is not the case that $\alpha_1 = \alpha_2$ = 12. Note that, as discussed in Section <ref>, the embeddings are not distinct if $\gamma=1$ and $\alpha_1+\alpha_2=1$.

§.§ Datasets

We use a collection of 5 temporal network datasets which are hosted on the repositories of Rossi & Ahmed, 2015 and Leskovec & Sosič, 2016. The statistics for these networks are provided in Table <ref>.
bitcoinalpha and bitcoinotc [Kumar et al., 2016, Kumar et al., 2018] are who-trust-whom networks of people who trade Bitcoin on the Bitcoin Alpha and Bitcoin OTC platforms. Each temporal edge involves one user rating another user's trustworthiness on a scale of -10 to +10 at some point in time; we binarize these ratings to positive and nonpositive to produce binary edge labels for classification. escorts is a bipartite network of sexual escorts and buyers; the edges are timed instances of a buyer rating an escorts from -1 to +1, which we again binarize as before. wikielect [Leskovec et al., 2010] is a network of Wikipedia users voting in administrator elections for or against other users to be promoted to administrator. Finally, epinions [Leskovec et al., 2010] is a who-trusts-whom network for the now-closed consumer review website Epinions.com.

§.§ Hyperparameter Sensitivity

Time scale hyperparameter As described in the main body of this paper, for our TDLG method, we set the hyperparameter $\sigma_t$ as ratio of the standard deviation of the edges' times. Letting this standard deviation be $\sigma_T$, we use $\sigma_t = \sigma_t' \cdot \sigma_T$. For all results in the main body, we use $\sigma_t' = 10^{-1}$, which we choose by informal tuning. Figure <ref> shows how test performance is impacted when varying $\sigma_t' \in [10^{-3},10^{+1}]$. Across the tested datasets (BitcoinAlpha, BitcoinOTC, Escorts, and WikiElect), we find that the highest test performance indeed occurs near $\sigma_t' = 10^{-1}$, though there is some variance in the optimal value across datasets. Performance also seems fairly robust with respect to this hyperparameter: for all tested datasets except Escorts, performance does not fall more than 5% relative to the best value of $\sigma_t'$ as it is varied across the tested range.

Edge classification performance when varying the time scale hyperparameter $\sigma_t$ (left) or normalization type (right). Mean test AUC across 5 trials as a proportion of the mean test AUC achieved by the best  or normalization type.

TDLG normalization It is common to somehow normalize the adjacency matrix $\mA$ prior to use in downstream tasks. We forego this procedure for all results in the main body of this paper, but here we test the impact of two kinds of normalization on the edge classification test.
Let $\mD \in \RR_+^{m \times m}$ denote the diagonal degree matrix, the diagonal entries of which are the row sums of $\mA$ (which are equivalent to the column sums). A common form of normalization, used in the spectral clustering algorithm of Shi & Malik, 2000 and many other works, is to set the normalized matrix

\[ \tilde{\mA} = \mD^{-1/2} \mA \mD^{-1/2};\]
this normalization has useful spectral properties, bounding eigenvalues within $[-1,+1]$.

We also test a second normalization procedure which aims to roughly preserve the total amount of edge weight associated with each edge. Since we assume that the original temporal graph is unweighted, meaning each edge weight is $1$, we seek for each row/column sum of the TDLG adjacency matrix to also be approximately $1$.
In particular, we set

\begin{equation*} \label{eqn:tdlg_norm}
\tilde{\mA} = \tfrac{1}{2} \left( \mD^{-1} \mA + \mA \mD^{-1} \right),
\end{equation*}

that is, we return the mean of the two matrices that result from dividing the rows/columns of $\mA$ by the row/column sums.
Note that this normalization preserves symmetry of the adjacency matrix. We observe that this second normalization scheme guarantees rough preservation of edge weight as follows. Because each row of $\mD^{-1} \mA$ sums to $1$, each row of $\tilde{\mA}$ sums to at least $\sfrac{1}{2}$. Further, since there are $m$ rows, the total sum of all entries in $\mD^{-1} \mA$ is $m$; similarly, $\mA \mD^{-1}$ sums to $m$ as well, so $\tilde{\mA}$ sums to $m$. Therefore, each edge, which in the original temporal graph was given exactly fraction $\sfrac{1}{m}$ of the total edge weight, is assigned at least fraction $\sfrac{1}{2m}$ of the total weight in the normalized TDLG.

As shown in Figure <ref> (right), across the tested datasets, we find that both normalization schemes ('Spectral' and 'Edge,' respectively) generally have a negative impact on performance, though the drop in performance is never more than around 6%. These results suggest that the simplest approach of skipping normalization is generally also the most performant.

§.§ Full Experimental Results

Tables <ref>, <ref>, and <ref> report the full performance results for edge classification, temporal link outlier detection (interpolative), and temporal link prediction (extrapolative), respectively, which were deferred in Section <ref>.

Complete results for edge classification: mean test AUC (%), as well as 95% confidence intervals, on the benchmark of datasets from Table <ref>. Methods are separated by non-deep vs deep.

height 0.75pt
BitcoinAlpha      BitcoinOTC     Escorts     WikiElect     Epinions
TDLG		   92.16 $\pm$ 00.52	   93.42 $\pm$ 00.29	   75.44 $\pm$ 00.29	   90.83 $\pm$ 00.06	   91.91 $\pm$ 00.03

TDLG (Dense)	   80.35 $\pm$ 00.65	   83.23 $\pm$ 00.28	   68.56 $\pm$ 00.30	   65.16 $\pm$ 00.24	   70.79 $\pm$ 00.10

CTDNE		   80.92 $\pm$ 00.61	   65.93 $\pm$ 00.55	   53.43 $\pm$ 00.55	   53.31 $\pm$ 00.24	   51.71 $\pm$ 00.09

TIMERS		   67.65 $\pm$ 00.40	   69.39 $\pm$ 00.50	   62.20 $\pm$ 00.46	   66.16 $\pm$ 00.20	   67.57 $\pm$ 00.08
EvolveGCN	   71.29 $\pm$ 00.84	   74.50 $\pm$ 00.58	   69.62 $\pm$ 00.31	   64.51 $\pm$ 00.16	   NA

DynGEM		   73.10 $\pm$ 00.79	   75.70 $\pm$ 00.57	   65.90 $\pm$ 00.37	   65.91 $\pm$ 00.26	   NA

GCRN		   65.59 $\pm$ 00.70	   71.66 $\pm$ 00.64	   60.00 $\pm$ 00.15	   58.17 $\pm$ 00.22	   NA

VGRNN		   68.55 $\pm$ 00.99	   67.24 $\pm$ 01.00	   65.40 $\pm$ 00.54	   64.10 $\pm$ 00.24	   NA

height 0.75pt

Complete results for temporal link outlier detection (interpolative): mean test AUC (%) and 95% confidence intervals.

height 0.75pt
BitcoinAlpha      BitcoinOTC     Escorts     WikiElect     Epinions
TDLG		   92.95 $\pm$ 00.30	   93.52 $\pm$ 00.12	   79.06 $\pm$ 00.49	   98.44 $\pm$ 00.05	   76.99 $\pm$ 00.07

CTDNE		   49.09 $\pm$ 00.82	   49.45 $\pm$ 00.49	   53.53 $\pm$ 00.45	   53.08 $\pm$ 00.27	   48.94 $\pm$ 00.28

TIMERS		   80.63 $\pm$ 00.75	   79.77 $\pm$ 00.79	   59.48 $\pm$ 00.69	   90.12 $\pm$ 00.24	   73.27 $\pm$ 00.11
EvolveGCN	   86.66 $\pm$ 01.61	   86.94 $\pm$ 02.08	   67.61 $\pm$ 02.39	   93.11 $\pm$ 00.47	   NA

DynGEM		   77.45 $\pm$ 01.01	   77.82 $\pm$ 01.37	   57.71 $\pm$ 02.26	   88.91 $\pm$ 02.69	   NA

height 0.75pt

Complete results for temporal link prediction (extrapolative): mean test AUC (%) and 95% confidence intervals.

height 0.75pt
BitcoinAlpha      BitcoinOTC     Escorts     WikiElect     Epinions
TDLG		   96.82 $\pm$ 01.87	   81.92 $\pm$ 01.79	   64.84 $\pm$ 00.99	   71.18 $\pm$ 01.23	   84.59 $\pm$ 00.63

CTDNE		   57.06 $\pm$ 10.00	   35.82 $\pm$ 05.28	   25.67 $\pm$ 00.38	   24.57 $\pm$ 00.58	   31.83 $\pm$ 00.50

TIMERS		   57.15 $\pm$ 04.76	   62.48 $\pm$ 04.29	   55.88 $\pm$ 00.86	   52.57 $\pm$ 00.63	   59.08 $\pm$ 00.65
EvolveGCN	   56.83 $\pm$ 14.45	   77.16 $\pm$ 04.36	   54.89 $\pm$ 01.27	   60.96 $\pm$ 02.95	   NA

DynGEM		   39.75 $\pm$ 28.75	   71.86 $\pm$ 06.33	   51.65 $\pm$ 02.86	   53.49 $\pm$ 04.95	   NA

height 0.75pt