# Curriculum Negative Mining For Temporal Networks

Ziyue Chen<EMAIL_ADDRESS>Tongya Zheng<EMAIL_ADDRESS>Mingli
Song<EMAIL_ADDRESS>
###### Abstract

Temporal networks are effective in capturing the evolving interactions of
networks over time, such as social networks and e-commerce networks. In recent
years, researchers have primarily concentrated on developing specific model
architectures for Temporal Graph Neural Networks (TGNNs) in order to improve
the representation quality of temporal nodes and edges. However, limited
attention has been given to the quality of negative samples during the
training of TGNNs. When compared with static networks, temporal networks
present two specific challenges for negative sampling: positive sparsity and
positive shift. Positive sparsity refers to the presence of a single positive
sample amidst numerous negative samples at each timestamp, while positive
shift relates to the variations in positive samples across different
timestamps. To robustly address these challenges in training TGNNs, we
introduce Curriculum Negative Mining (CurNM), a model-aware curriculum
learning framework that adaptively adjusts the difficulty of negative samples.
Within this framework, we first establish a dynamically updated negative pool
that balances random, historical, and hard negatives to address the challenges
posed by positive sparsity. Secondly, we implement a temporal-aware negative
selection module that focuses on learning from the disentangled factors of
recently active edges, thus accurately capturing shifting preferences.
Extensive experiments on 12 datasets and 3 TGNNs demonstrate that our method
outperforms baseline methods by a significant margin. Additionally, thorough
ablation studies and parameter sensitivity experiments verify the usefulness
and robustness of our approach. Our code is available at
https://github.com/zziyue83/CurNM.

###### keywords:

Temporal Graph Neural Networks , Negative sampling , Curriculum learning ,
Disentanglement learning

††journal: Neural Networks

[1]organization=Department of Economics, University of California,
Berkeley,city=Berkeley, state=California, country=United States

[2]organization=Big Graph Center, School of Computer and Computing Science,
Hangzhou City University,city=Hangzhou, state=Zhejiang, country=China

[3]organization=State Key Laboratory of Blockchain and Data Security, Zhejiang
University,city=Hangzhou, state=Zhejiang, country=China

[4]organization=Hangzhou High-Tech Zone (Binjiang) Institute of Blockchain and
Data Security,city=Hangzhou, state=Zhejiang, country=China

##  1 Introduction

Temporal networks have gained popularity in recent years due to their capacity
to capture the evolving nature inherent in diverse domains, such as social
networks [18, 21, 28], recommendation systems [1, 16], financial transactions
[22], transport [26], and political networks [6, 11, 19]. Unlike their static
counterparts, these networks support additions, deletions, and changes in the
features of nodes and edges over time by modeling a sequence of time-stamped
events. To best leverage this temporal information, Temporal Graph Neural
Networks (TGNNs) [8, 16, 24, 25, 27, 30, 33] have been developed.

Similar to static graph models, TGNNs [24, 33] employ negative sampling
techniques to prevent the models from being overwhelmed by a disproportionally
high number of negative over positive samples and enhance the models’
efficiency. The most straightforward approaches often adopted are random
sampling and recent sampling [24, 33]. However, temporal networks introduce
two unique challenges that particularly undermine these approaches: positive
sparsity and positive shift. Positive sparsity emerges as the inclusion of a
temporal dimension significantly increases the negative-to-positive ratio by
the number of timestamps, compared to static graphs. Consequently, random
sampling in this context tends to produce a multitude of irrelevant and easily
distinguishable negative samples, offering little to no value. Positive shift,
on the other hand, occurs as the relationships between nodes change over time;
for instance, in recommendation systems, users’ preferences are likely to
evolve [16]. Ignoring this factor may result in training models on outdated
information, particularly in datasets spanning long periods.

Nonetheless, the negative sampling problem in temporal network learning has
been seldom explored. While such efforts are limited for TGNNs, there is a
wealth of strategies developed for static graphs. Whether by adopting
alternative distributions [4, 32, 36] or employing model-aware methods to
select negatives that closely resemble positives [5, 12, 17, 38, 39], these
existing strategies seek to enhance models’ performance by focusing on more
informative negative samples, specifically those that closely resemble
positive ones, during training. However, applying these strategies directly to
temporal networks is problematic due to positive sparsity. In particular,
given the scarcity of positive samples, using negative samples that are too
similar to positives can skew the classification boundary excessively towards
the negatives. This can lead to confusion within the model, particularly
during early epochs, and result in poor performance. Thus, a more gradual
transition from easy to hard negatives is needed. Moreover, positive shift
induces a negative shift, rendering existing methods for static graphs
ineffective for temporal networks. This highlights the need for components
that can incorporate recent information and update dynamically over time. Till
now, ENS [7] is the only negative sampling method specifically designed for
temporal networks. While targeting temporal networks, ENS adopts a heuristic,
global negative mining strategy instead of an adaptive, personalized approach,
leading to unstable performance. Additionally, it suffers from low efficiency
due to sampling from all historical edges.

To address these challenges, we introduce the CurNM method. Overall, CurNM is
a curriculum learning strategy that dynamically adjusts the learning
difficulty of negative samples based on the model’s performance, thereby
addressing the prevalent issue of steep difficulty curves in existing methods.
Subsequently, we incorporate two components to address the unique
characteristics of temporal networks. Firstly, to address positive sparsity,
we construct a negative pool for selection, which includes a mix of random
samples and historical neighbors, with hard negatives added if the model shows
strong learning progress. Starting with a relatively small negative pool also
helps maintain computational efficiency. Secondly, we design a negative
selection function that leverages temporal-aware disentanglement to capture
positive shifts and individual node preferences, which further enhances the
model’s granularity.

Our key contributions are summarized as follows:

  * 1.

We identify two crucial challenges of negative sampling in temporal networks,
i.e., positive sparsity and positive shift.

  * 2.

An efficient curriculum learning framework on negative sampling is tailored
for temporal networks to handle these two challenges.

  * 3.

Elaborate experiments on 12 temporal networks and 3 TGNNs show that our CurNM
can consistently boost the link prediction performance compared to baselines.

  * 4.

CurNM is highly portable and can be integrated as a plug-in into any TGNN with
minimal modifications.

##  2 Related Work

###  2.1 Temporal Graph Learning

Motivated by the significant progress of deep learning in Computer Vision [15]
and Natural Language Processing [20], learning dense embeddings for nodes has
become a de facto standard paradigm in graph learning [9, 23], unifying
different graph tasks into a graph representation learning task. Subsequently,
Graph Neural Networks [10, 14, 31], which take both graph structure and node
features into account, replaced skip-gram models [9, 23] for graph
representations. Influenced by the advances of static graph representation
learning, TGNNs have been proposed to handle the evolving dynamics of temporal
networks [29], updating node embeddings as time elapses.

Existing TGNNs can be classified into discrete-time and continuous-time TGNNs
based on their temporal natures [13]. On the one hand, discrete-time TGNNs [8,
22, 25, 27] focus on the sequential dynamics of a series of graph snapshots,
where the timespan of a snapshot depends largely on the graph domain. The
consequent discrete-time TGNNs include a combination of Recurrent Neural
Networks and Graph Neural Networks. DySAT [25], a typical discrete-time TGNN,
first learns the structural representations of nodes within each graph
snapshot and then aggregates across multiple snapshots using a temporal self-
attention layer.

On the other hand, continuous-time TGNNs focus on the sequential interactions
of nodes, thereby offering more fine-grained temporal information. Various
design paradigms exist for continuous-time TGNNs since temporal networks can
be seen as sequential dynamics of either nodes or a graph. JODIE [16] utilizes
two mutually updated RNNs to update user and item embeddings, alongside a
temporal attention layer that projects user embeddings after a certain time
since their last interaction. Conversely, TGN [24] presents a generic
framework on continuous temporal networks, simulating both RNNs [16, 30] and
TGNNs [33] with its flexible memory mechanism and GNNs. Recent state-of-the-
art continuous-time TGNNs [34, 37] have further explored the self-attention
mechanism on temporal networks, inspired by the advancement of Transformer
networks [2]. However, TGNNs typically employ random and recent negative
sampling [24, 33], with little attention given to the specific study of
negative sampling strategies within this domain.

###  2.2 Hard Negative Sampling

Negative sampling strategies [4, 5, 12, 17, 32, 36, 38, 39] have been abundant
in graph representation learning such as collaborative filtering and knowledge
graphs. These strategies are traditionally categorized into two types: static
and model-aware negative sampling.

Figure 1: An illustration of our CurNM method for temporal networks, which
progressively increases the difficulty of sampled negatives. $(a)$ illustrates
the pipeline of TGNNs in temporal network link prediction, where our CurNM
adds a Negative Pool and a Negative Selection module to the basic random
sampling approach. $(b)$ illustrates the construction of a fixed-size,
dynamically updated negative pool. $(c)$ shows the selection of negatives from
this pool based on the candidates’ disentangled distances and their temporal
proximity to the interactions. $(d)$ depicts the final negative samples used
for training TGNNs, which include selected negatives from $(c)$ combined with
random negatives. $(e)$ illustrates the process of selecting negatives in
random sampling, where irrelevant negatives are likely to be chosen at any
stage of training.

Static negative sampling strategies [20] select negative samples based on a
pre-defined probability distribution. The simplest and most common strategy is
random sampling, which uniformly selects negative samples from uninteracted
nodes. However, random sampling falls short in ensuring the quality of the
samples. In response, alternative distributions have been proposed. For
instance, NNCF [4] and NCEPLRec [32] adopt item-popularity-based sampling
distributions to preferentially select popular items as negative samples,
thereby mitigating the widespread popularity bias in recommender systems [3].
Despite these advancements, all these methods fail to adequately account for
distribution variations across different networks, thus leading to
unsatisfactory performance.

To tackle this challenge, model-aware negative sampling strategies leverage
models’ specific information to oversample negatives that closely resemble
positive samples, thereby tightening models’ decision boundaries and enhancing
accuracy. DNS [36] pioneers this approach by dynamically choosing negative
samples with the highest prediction scores. NSCaching [38] builds on this by
keeping a cache of hard negatives, whereas SRNS [5] introduces a variance-
based criterion to reduce the risk of false negatives. Moreover, MixGCF [12]
synthesizes hard negatives by infusing positive information into negative
samples. DENS [17] splits embeddings into relevant and irrelevant factors and
selects negatives that only differ in relevant factors from the positives. ANS
[39] combines factor-aware and augmentation techniques from these strategies;
it separates the hard and easy factors of negative items and synthesizes new
negatives by augmenting the easy factors. While these aforementioned
strategies have shown encouraging outcomes, their direct application to TGNNs
is disappointing due to their oversight of temporal networks’ unique
characteristics, particularly positive shift and positive sparsity.

To the best of our knowledge, ENS [7] is the only negative sampling method
specifically designed for temporal networks. ENS selects negative samples by
aiming to meet a difficulty target composed of the proportion of historical
neighbors and average temporal proximity. While ENS tries to tackle positive
sparsity by increasing the difficulty target by a predefined amount each
epoch, its heuristic approach fails to adapt to the varying needs of different
models and datasets. Moreover, although it addresses positive shift by
considering temporal proximity, this method requires evaluating all historical
edges to ensure accuracy, thereby consuming substantial resources. Finally,
ENS does not account for individual node preferences; it indiscriminately
prioritizes all nodes that have historically appeared, without distinguishing
historical neighbors, and fails to recognize that interactions between users
and items are often driven by certain key factors.

##  3 Problem Statement

#### Temporal Network

This section formulates the problem of negative sampling in temporal networks.
Let $G(V,E,T,X)$ be a temporal network where $V$ and $E$ denote the set of
nodes and edges, $T$ denotes the timestamps of interactions, and $X$ denotes
the node features. We denote the set of interactions by
$O^{+}=\\{(u,v^{+},t)|u,v^{+}\in V\text{ and }t\in T\\}$ where each tuple
$(u,v^{+},t)$ records an interaction between two nodes $u,v^{+}$ that occurs
at time $t$. By convention, we call $u$ source node and $v^{+}$ destination
node. These pairs form positive training samples. Conversely, we define the
complement of $O^{+}$ as $O^{-}=\\{(u,v^{-},t)|u,v^{-}\in V,t\in T\text{ and
}(u,v^{-},t)\notin O^{+}\\}$. This set contains all node pairs $u,v^{-}$ that
are not connected by an edge at time $t$ and is used to generate negative
samples. Our goal is to define a negative sampling strategy $f$ that selects
negative samples $(u,v^{-},t)$ from $O^{-}$ to enhance the performance of
existing TGNNs.

#### Historical Neighbor

$u,v^{\prime}$ are called neighbors at $t$ if $(u,v^{\prime},t)\in O^{+}$. If
there exists $(u,v^{\prime\prime},t^{\prime})\in O^{+}$ such that
$t^{\prime}\leq t$, $v^{\prime\prime}$ is called a historical neighbor of $u$
at $t$. In our context, we further restrict historical neighbors to nodes that
are not neighbors of $u$ at the current time, i.e.,
$(u,v^{\prime\prime},t)\notin O^{+}$. For each $(u,t)\in(V,T)$, we maintain a
set $H_{u,t}=\\{(v_{1},t_{1}),(v_{2},t_{2}),...,(v_{n},t_{n})\\}$ that records
all unique historical neighbors of $u$ at $t$ and their respective interaction
timestamps. In cases where $v_{i}$ interacts with $u$ multiple times before
$t$, we use the latest timestamp for $t_{i}$. Historical neighbors in our
method are then drawn from this set $H_{u,t}$.

##  4 Methodology

Overall, CurNM is a curriculum learning strategy that progressively increases
the difficulty of selected negatives based on performance on the validation
set, effectively addressing the steep difficulty curves found in existing
methods. Within this framework, we further develop two components. Firstly, to
tackle positive sparsity, we establish a negative pool consisting of
historical neighbors and random negatives, with hard negatives included when
the model exhibits sustained improvements. Secondly, we use a temporal-aware
disentangling technique to score the information of candidate negatives in the
negative pool, emphasizing those that differ from positives only in the most
critical dimensions, thus capturing positive shifts and individual
preferences. These informative negative samples are then fetched for training
TGNNs to ensure their performance and robustness.

This framework is illustrated in Figure 1, and the detailed workflow is
presented in Algorithm 1.

Algorithm 1 The training process with CurNM.

0: Training set $O^{+}=\\{(u,v^{+},t)\\}$, Negative set
$O^{-}=\\{(u,v^{-},t)\\}$, Temporal network model $F$.

1: for $e=1$ to $E_{0}$ do

2: Get the embeddings of nodes by $F$.

3: Sample a mini-batch $O^{+}_{\text{batch}}$ from $O^{+}$.

4: Update the difficulty level $\pi_{e}$ by Eq. 1.

5: for all $(u,v^{+},t)\in O^{+}_{\text{batch}}$ do

6: Check $\mathcal{C}_{\pi_{e}}$ whether to cache training negatives by Eq. 5.

7: if not $\mathcal{C}_{\pi_{e}}$ then

8: Get the negative pool $V_{u}^{-}$ by Eq. 4.

9: else

10: Get the negative pool $V_{u}^{-}$ by Eq. 7.

11: end if

12: Disentangle the relevant factors by Eq. 8 and Eq. 9.

13: Disentangle the irrelevant factors by Eq. 10.

14: Get the scores of node pairs by Eq. 13.

15: Select informative node pairs $O^{-}_{\text{sel}}$ by Eq. 2.

16: Update embeddings by Eq. 3.

17: if $\mathcal{C}_{\pi_{e}}$ then

18: Update $V_{u}^{hard}$ by Eq. 6.

19: end if

20: end for

21: end for

###  4.1 Curriculum Learning

To address the learning difficulty caused by positive sparsity, the curriculum
learning strategy adaptively increases the difficulty level of selected
negatives based on the learning performance of TGNNs. Additionally, these
selected negatives are accompanied by annealing random negatives for robust
training of TGNNs.

#### Adaptive Selected Negatives

Firstly, we introduce a sampling proportion $\pi_{e}$ that self-adjusts based
on the model’s performance at $e$-th epoch – shrinking when performance
improves and expanding otherwise – thus dynamically controlling the difficulty
level of selected negatives. By starting with a large $\pi_{e}$ to include
both easy and hard negatives and tightening it only if the model consistently
demonstrates improvements, this approach prevents the model from being
overwhelmed by overly challenging negatives. Furthermore, we utilize a
shrinkage rate $\gamma_{\text{shrink}}$ to control the adjustment steps of
$\pi_{e}$. A high $\gamma_{\text{shrink}}$ establishes a steep difficulty
curve for model learning, while a low $\gamma_{\text{shrink}}$ sets a flatter
curve. This strategy is written as

$\pi_{e+1}=\begin{cases}\pi_{e}-\gamma_{\text{shrink}},&\text{If performance
improves,}\\\ \pi_{e}+\gamma_{\text{shrink}},&\text{Otherwise}\end{cases}$ (1)

In addition, instead of the traditional method of selecting a set of negative
samples for each positive sample, we merge and evaluate all candidate
negatives at the minibatch level. As the learning difficulties vary across
source nodes, this approach allows us to focus on more informative nodes that
present greater difficulty while automatically eliminating nodes that are
easier to learn as $\pi_{e}$ shrinks. Technically, we select the top-scored
$n_{b}=\pi_{e}\times|b|\times M$ samples for each minibatch $b$ at $e$-th
epoch, where $|b|$ denotes the number of source nodes in minibatch $b$, and
$M$ represents the size of each source’s negative pool $V^{-}_{u}$.

$\begin{split}O^{-}_{\text{sel}}&=\text{arg
top}_{n_{b}}\\{\hat{s}_{uv^{-}}|\forall u\in b,v^{-}\in
V^{-}_{u}\\},\end{split}$ (2)

where $O^{-}_{\text{sel}}$ denotes the set of selected negatives, and
$\hat{s}_{uv^{-}}$ is a scoring function between node pairs for negative
selection, as defined by Eq. 13.

#### Annealing Random Negatives

To provide the model with additional space for exploration and adaptation,
especially in early epochs, each minibatch also includes $n_{b}$ random
negatives $O^{-}_{\text{rand}}$ in addition to $O^{-}_{\text{sel}}$. A weight
$\delta_{e}$ is applied to balance these two types. Initially, we assign a
higher weight to random negatives to enable the model to understand the basic
patterns. As the model gains experience, the emphasis gradually shifts toward
the selected, presumably more challenging negatives, enhancing the learning
depth. Following this intuition, we define
$\delta_{e}=\max\\{\pi_{e},\delta_{\text{min}}\\}$. $\delta_{\text{min}}$ is a
hyper-parameter that controls the minimum influence random negatives should
exert, ensuring that both contribute to the learning process. The loss for
each minibatch is computed as

$L=L_{pos}+\delta_{e}L_{O^{-}_{\text{rand}}}+(1-\delta_{e})L_{O^{-}_{\text{sel}}}+\lambda
L_{\text{con}}+\mu\lVert\Theta\rVert^{2}_{2},$ (3)

where $L_{pos}$, $L_{O^{-}_{\text{rand}}}$, and $L_{O^{-}_{\text{sel}}}$
denote the mean binary cross-entropy losses for positive samples, random
negatives, and selected negatives, respectively. $L_{\text{con}}$ is the
average contrastive loss as defined in Eq. 11, and
$\lVert\Theta\rVert^{2}_{2}$ is a regularization term.

###  4.2 Negative Pool

The negative pool, which is an essential component of the curriculum learning
strategy, is also constructed dynamically.

To ensure efficiency, we start the entire process by sampling a negative pool
$V^{-}_{u}$ of fixed size $M$ for each positive sample $(u,v^{+},t)$. During
the initial epochs, we sample $V^{-}_{u}$ as a mixture of historical neighbors
and random negatives, a simple approach to prevent overcrowding with easy
negatives. Random samples here serve a different purpose than before and are
included to capture newly emerging preferences not disclosed by users’
historical interactions. This process can be written as

$V^{-}_{u}=V^{\text{hist}}_{u}\cup V^{\text{rand}}_{u},$ (4)

where $|V^{-}_{u}|=M$, and a proportion hyper-parameter $\gamma_{\text{hist}}$
is used to balance between $|V^{\text{hist}}_{u}|=\gamma_{\text{hist}}*M$ and
$|V^{\text{rand}}_{u}|=(1-\gamma_{\text{hist}})*M$.

Once the model learns the fundamentals, we raise the difficulty level. We
introduce this advanced stage when sampling proportion $\pi_{e}$ falls below a
preset threshold $\tau$ for the first time. Since $\pi_{e}$ decreases only if
the model is learning well, this condition ensures that the model only
encounters more challenging negatives after it has adequately learned the
basics. The indicator $\mathcal{C}_{\pi_{e}}$ is determined as follows:

$\mathcal{C}_{\pi_{e}}=\mathbbm{1}(\pi_{e}\leq\tau).$ (5)

In this advanced stage, we implement a hard negative cache
$V^{\text{hard}}_{u}$ of size $\frac{M}{2}$ to store a subset of $V^{-}_{u}$
from the current epoch, focusing on likely false positives and those showing
less learning in previous epochs. The cached negatives are sampled
proportionally according to the negatives’ performance metrics, as outlined in
Eq. 6.

$V^{\text{hard}}_{u}\sim\\{p_{uv}-\alpha_{e}\times\text{std}(P_{uv})|\forall
v\in V^{-}_{u}\\},$ (6)

where $|V^{\text{hard}}_{u}|=\frac{M}{2}$, $p_{uv}$ denotes the probability
score of node pair $(u,v)$ at the current epoch, $P_{uv}$ records the
historical scores within the last five epochs, and std($\cdot$) is set to $0$
when results are not available. $\alpha_{e}$ is a hyper-parameter that
controls the importance of prediction standard deviation at the $e$-th epoch.
To manage potential instability in early learning stages, we initially assign
a modest weight to the standard deviation and gradually increase it.
Specifically, we use
$\alpha_{e}=\alpha_{\text{max}}\times\min(\frac{e}{E^{\prime}},1)$, where
$E^{\prime}$ is the epoch after which the weight remains constant, and
$\alpha_{\text{max}}$ is the maximum weight that standard deviations could
contribute to the performance metrics.

This hard negative cache then accounts for half of the negative pool in the
next epoch, while the remainder continues to be a mix of historical neighbors
and random samples, maintaining the previous proportion. Therefore, the new
updating strategy for each negative pool $V^{-}_{u}$ is written as

$V^{-}_{u}=V^{\text{hard}}_{u}\cup V^{\text{hist}}_{u}\cup
V^{\text{rand}}_{u},$ (7)

where
$\frac{|V^{\text{hist}}_{u}|}{|V^{\text{rand}}_{u}|}=\frac{\gamma_{\text{hist}}}{1-\gamma_{\text{hist}}}$
and $|V^{\text{hist}}_{u}|+|V^{\text{rand}}_{u}|=\frac{M}{2}$.

###  4.3 Negative Selection

The second critical component of our framework is the selection function used
to choose negative samples from the negative pool $V^{-}_{u}$. This process
consists of two steps: disentangle irrelevant factors of negative nodes and
score negative samples with time embeddings.

#### Irrelevant Factor Disentanglement

To facilitate TGNNs to differentiate positive from negative samples, we
disentangle nodes’ relevant and irrelevant factors, which is in line with DENS
[17].

For each positive sample $(u,v^{+},t)$, we construct a positive gate. This
gate leverages the embeddings of the source node $h_{u}$ and the destination
node $h_{v^{+}}$ to isolate the relevant factor $h_{v^{+}}^{r}$ of the
destination node $v^{+}$, illustrated as

$h_{v^{+}}^{r}=h_{v^{+}}\odot\sigma(W_{\text{src}}h_{u}+W_{\text{dst}}h_{v^{+}}+b_{p}),$
(8)

where $W_{\text{src}}$, $W_{\text{dst}}$ and $b_{p}$ are trainable parameters
shared by all positive samples, $\sigma$ is the sigmoid function, and $\odot$
is the element-wise product. This factor and the embedding $h_{v^{-}}$ of the
corresponding candidate negative $v^{-}\in V^{-}_{u}$ are then used as inputs
to isolate the relevant factor $h_{v^{-}}^{r}$ of the negative.

$h_{v^{-}}^{r}=h_{v^{-}}\odot\sigma(W_{p}h_{v^{+}}^{r}+W_{n}h_{v^{-}}+b_{n}),$
(9)

where $W_{p}$, $W_{n}$, and $b_{n}$ are trainable parameters shared by all
candidate negatives in the negative pool. Factors other than relevant factors
are denoted as irrelevant factors:

$h_{v^{+}}^{ir}=h_{v^{+}}\ominus h_{v^{+}}^{r},\quad
h_{v^{-}}^{ir}=h_{v^{-}}\ominus h_{v^{-}}^{r},$ (10)

where $h_{v^{+}}^{ir}$ and $h_{v^{-}}^{ir}$ denote irrelevant factors of the
destination node $v^{+}$ and the candidate negative $v^{-}$, respectively, and
$\ominus$ is element-wise subtraction.

To supervise the training of positive and negative gates, we introduce a four-
component contrastive loss $L_{\text{con}}$. These components dictate that
relevant factors mainly drive interactions in positive samples and the absence
of interactions in negative samples, while irrelevant factors do not and may
even favor negative samples. This approach is consistent with the procedure
used in DENS [17], written as

$L_{\text{con}}=-(s_{r,ir}^{+,+}+s_{r,r}^{+,-}+s_{ir,r}^{-,-}+s_{ir,ir}^{-,+}),$
(11)

where
$s_{g1,g2}^{sgn1,sgn2}=MLP(h_{u},h_{v^{sgn1}}^{g1})-MLP(h_{u},h_{v^{sgn2}}^{g2})$
is the scoring function between different factors, with $MLP(\cdot,\cdot)$
computing the probability score from the given embeddings, and a minus sign is
added to perform maximization.

#### Temporal Scoring Function

As our goal is for the model to predict neighbors based on relevant factors,
the most useful negatives for training are those that differ from the
positives only in their relevant factors. In practice, this involves selecting
negative samples from the negative pool $V^{-}_{u}$ by maximizing the
differences in relevant factors and minimizing the differences in irrelevant
factors. This approach is written as

$\displaystyle s_{uv^{-}}$ $\displaystyle=$ $\displaystyle\beta_{e}\times
s_{r,r}^{+,-}-(1-\beta_{e})\times s_{ir,ir}^{+,-},$ (12)

where $s_{uv^{-}}$ denotes the scoring function and $\beta_{e}$ is a hyper-
parameter that balances the contributions of relevant and irrelevant factors
at epoch $e$. Intuitively, we want the model to first learn which factors are
important and then understand how these factors drive interactions. This
entails initially focusing on aligning irrelevant factors and later shifting
to differentiating relevant factors. Specifically, we set
$\beta_{e}=\min(\frac{e}{E^{\prime\prime}},1)$, where $E^{\prime\prime}$ marks
the epoch from which the score is solely determined by relevant factors.

Additionally, to capture the unique aspects of temporal networks, we
incorporate three Time2Vec models to represent complex temporal patterns,
including recurrent and periodic behaviors. Therefore, the final temporal
scoring function used for selecting negative samples is written as

$\hat{s}_{uv^{-}}=t_{u,v^{+}}\ast(t_{u,v^{-}}\odot t_{v^{-}})\odot
s_{uv^{-}},$ (13)

where $t_{u,v^{+}}$, $t_{u,v^{-}}$, and $t_{v^{-}}$ are Time2Vec embeddings
for the timestamps of the positive sample, the interaction between $u$ and the
candidate negative $v^{-}\in V^{-}_{u}$, and the negative’s most recent
occurrence, respectively. Default inputs of 0 are provided into Time2Vec for
cases where the negative is not a historical neighbor or if it never occurs.
By incorporating the product of these three embeddings, we seek to prioritize
historical neighbors and recently popular nodes. The rationale is that these
negatives possess attributes that were favored by the source nodes not long
ago, and they might trick the model. So, by assigning more weight to these
negatives – particularly those that differ from positives only in relevant
factors – we can enhance the precision of the model’s decision boundary and
reduce the occurrence of false negatives.

##  5 Experiment

###  5.1 Datasets and Evaluation

#### Dataset

We evaluate the performance of our CurNM method on $12$ standardized datasets
obtained from DyGLib [35] and TGL [40]. These datasets encompass a broad
spectrum of domains, sizes, durations, and network features, and are intended
to represent a diverse array of datasets. According to Table 1, which
summarizes the statistics, social and interaction networks are typically
sparse, while social and economic networks often exhibit high recency and
repetition. These characteristics are expected due to the limited number of
relationships individuals can realistically maintain and the significant
impact of recent events and cyclic patterns on public attention and market
dynamics. Other features, such as average time proximity, present a more
diverse result across different domains. We divide these datasets into
training, validation, and test sets using a chronological split with ratios of
$70:15:15$ to prevent temporal data leakage during model training.

Table 1: Statistical Overview of the Datasets. Average Proximity is the
average step difference between nodes and their historical neighbors, Recency
is the percentage of current interactions that replicate the last, Repetition
is the proportion of repeated edges, $d_{\text{max}}$ represents the maximum
temporal node degree.

Dataset | Domain | Bipartite | $|V|$ | $|E|$ | Average Proximity | Recency | Repetition | Density | $d_{\text{max}}$ | Time Span
---|---|---|---|---|---|---|---|---|---|---
uci | Social | No | 1900 | 59835 | 58 | 34% | 77% | 5.63E-07 | 1.55E+03 | 194 days
USLegis | Politics | No | 226 | 60396 | 103 | 40% | 72% | 1.98E-01 | 1.20E+03 | 11 congresses
CanParl | Politics | No | 735 | 74478 | 34 | 25% | 39% | 1.97E-02 | 2.38E+03 | 13 years
enron | Social | No | 185 | 125235 | 1004 | 45% | 98% | 3.23E-04 | 2.15E+04 | 4 years
WIKI | Social | Yes | 9228 | 157474 | 62 | 79% | 88% | 2.42E-08 | 1.94E+03 | 1 month
MOOC | Interaction | No | 7047 | 411749 | 30 | 20% | 57% | 4.80E-08 | 1.95E+04 | 1 month
UNtrade | Economics | No | 256 | 507497 | 890 | 83% | 96% | 4.84E-01 | 1.22E+04 | 31 years
REDDIT | Social | Yes | 10985 | 672447 | 67 | 61% | 88% | 1.67E-08 | 5.87E+04 | 1 month
myket | Interaction | Yes | 17989 | 694121 | 26 | 5% | 21% | 6.18E-09 | 1.53E+04 | 6.5 months
UNvote | Politics | No | 202 | 1035742 | 1570 | 92% | 98% | 7.09E-01 | 1.59E+04 | 71 years
LASTFM | Interaction | Yes | 1980 | 1293103 | 1713 | 10% | 88% | 5.14E-07 | 5.18E+04 | 1 month
Flights | Transport | No | 13170 | 1927145 | 822 | 40% | 84% | 1.82E-04 | 3.47E+04 | 1 month

#### Evaluation Metrics

We use average precision (AP) as our primary evaluation metric. Specifically,
we compare AP for each dataset across all combinations of TGNNs and sampling
methods, since typically only the optimal setup is used in practice.
Additionally, given that we conduct experiments across 12 datasets, we
evaluate the overall performance of each sampling method using average rank.

These two metrics are assessed across two scenarios: transductive and
inductive negative evaluation. In the transductive setting, our test includes
a mix of half-random and half-historical (TRANS) negative samples. Given that
our method is specifically tailored to enhance performance against hard
negatives, we anticipate improved predictive accuracy for historical neighbors
[35]. However, it is crucial to preserve the model’s capability to accurately
predict random negatives. In this context, TRANS provides a robust benchmark
for assessing our method’s ability to balance these two objectives.
Conversely, the inductive test involves only nodes not seen during training
and thus provides a valuable indicator of our method’s generalizability to new
data. This evaluation draws on code from DyGLib [35].

###  5.2 Experiment Setting

#### Baselines

We compare our method against two commonly adopted negative sampling
strategies – random sampling and recent sampling [24, 33] – along with ENS
[7], the only existing method known to us tailored for temporal networks.
Random sampling selects negative samples based on a uniform distribution.
Recent sampling selects the latest historical neighbors as negatives, offering
a straightforward approach to addressing issues of positive sparsity and
positive shift. Finally, ENS trains models using a predetermined proportion of
random negatives and historically appearing nodes while ensuring that the
average temporal proximity reaches a specified level.

We conduct our experiments on JODIE [16], TGN [24], and DySAT [25], three
well-established models that exhibit superior performance on our datasets with
random sampling.

#### Implementation Details

For a fair comparison, we follow default implementations in TGL [40]. In all
experiments, the Adam optimizer is used with a learning rate of $0.0001$ and a
mini-batch size of $200$. We perform each experiment for up to $400$ epochs
and repeat it with $5$ different random seeds. All methods are executed with a
48-core CPU, 128GB of memory, and a 24G P5000 GPU.

The contrastive loss coefficient $\lambda$ and the $L_{2}$ regularization
coefficient $\mu$ are set to ensure a balanced treatment across different loss
components. The remaining hyperparameters are carefully tuned through grid
search. The size of the negative pool $M$ is tested within $\\{4,8,12,16\\}$;
the proportion of historical neighbors $\gamma_{\text{hist}}$ within
$\\{0.3,0.4,0.5,0.6,0.7\\}$; and the hard negative cache’s initiation
threshold $\tau$ within $\\{0.3,0.5,0.7\\}$. The stopping epoch $E^{\prime}$
and the maximum weight $\alpha_{\text{max}}$ for $\alpha_{e}$ are explored
over $\\{\frac{E_{0}}{10},\frac{E_{0}}{2},E_{0}\\}$ and
$\\{0,0.006,0.012,0.024\\}$ respectively, where $E_{0}$ denotes the maximum
number of epochs. Similarly, $E^{\prime\prime}$ for $\beta_{e}$ and
$\delta_{\text{min}}$ for $\delta_{e}$ are searched within
$\\{\frac{E_{0}}{10},\frac{E_{0}}{2},E_{0}\\}$ and $\\{0.3,0.5,0.7\\}$. All
chosen values are included in the code. We will elaborate on tests involving
$\alpha_{e}$, $\beta_{e}$, $\pi_{e}$, and $\delta_{e}$ in a later section.

###  5.3 Experimental Results

As shown in Table 2, our method consistently achieves the best ranks in both
historical and inductive settings, underscoring its efficacy.

Table 2: Average Precision of link prediction across 12 datasets and three
TGNNs. bold denotes the best performance achieved for each dataset, -
indicates failed results, Avg Rank refers to the average ranks of each
sampling method.

Dataset | Model | Transductive | Inductive
---|---|---|---
Random | Recent | ENS | CurNM | Random | Recent | ENS | CurNM
uci | DySAT | 0.763 | 0.787 | 0.763 | 0.764 | 0.726 | 0.727 | 0.737 | 0.741
| JODIE | 0.839 | 0.564 | 0.855 | 0.848 | 0.636 | 0.542 | 0.648 | 0.640
| TGN | 0.824 | 0.651 | 0.849 | 0.832 | 0.677 | 0.662 | 0.700 | 0.695
USLegis | DySAT | 0.505 | 0.602 | 0.564 | 0.539 | 0.480 | 0.584 | 0.510 | 0.517
| JODIE | 0.492 | 0.527 | 0.501 | 0.515 | 0.597 | 0.596 | 0.618 | 0.620
| TGN | 0.808 | 0.797 | 0.833 | 0.868 | 0.763 | 0.730 | 0.789 | 0.809
CanParl | DySAT | 0.586 | 0.539 | 0.597 | 0.577 | 0.672 | 0.630 | 0.674 | 0.664
| JODIE | 0.572 | 0.569 | 0.570 | 0.652 | 0.533 | 0.539 | 0.530 | 0.570
| TGN | 0.747 | 0.705 | 0.713 | 0.791 | 0.626 | 0.624 | 0.604 | 0.650
enron | DySAT | 0.744 | 0.727 | 0.742 | 0.742 | 0.704 | 0.698 | 0.703 | 0.706
| JODIE | 0.800 | 0.752 | 0.801 | 0.826 | 0.724 | 0.693 | 0.716 | 0.739
| TGN | 0.771 | 0.842 | 0.824 | 0.848 | 0.730 | 0.811 | 0.769 | 0.787
WIKI | DySAT | 0.836 | 0.844 | 0.843 | 0.887 | 0.821 | 0.804 | 0.823 | 0.834
| JODIE | 0.791 | 0.734 | 0.786 | 0.818 | 0.701 | 0.701 | 0.712 | 0.728
| TGN | 0.906 | 0.883 | 0.908 | 0.917 | 0.856 | 0.837 | 0.860 | 0.868
MOOC | DySAT | 0.699 | 0.611 | 0.720 | 0.710 | 0.684 | 0.592 | 0.686 | 0.681
| JODIE | 0.670 | 0.564 | 0.679 | 0.679 | 0.580 | 0.574 | 0.576 | 0.577
| TGN | 0.764 | 0.621 | 0.774 | 0.767 | 0.688 | 0.653 | 0.663 | 0.690
UNtrade | DySAT | 0.527 | 0.534 | 0.528 | 0.527 | 0.538 | 0.556 | 0.539 | 0.542
| JODIE | 0.609 | 0.655 | 0.603 | 0.613 | 0.609 | 0.680 | 0.610 | 0.619
| TGN | 0.644 | 0.660 | 0.647 | 0.665 | 0.661 | 0.665 | 0.660 | 0.681
REDDIT | DySAT | 0.835 | 0.813 | 0.842 | 0.840 | 0.823 | 0.814 | 0.829 | 0.819
| JODIE | 0.823 | 0.781 | 0.835 | 0.829 | 0.787 | 0.777 | 0.794 | 0.797
| TGN | 0.878 | 0.848 | 0.890 | 0.878 | 0.874 | 0.853 | 0.871 | 0.877
myket | DySAT | 0.668 | 0.738 | 0.665 | 0.667 | 0.596 | 0.689 | 0.592 | 0.596
| JODIE | 0.674 | 0.664 | 0.685 | 0.688 | 0.530 | 0.533 | 0.545 | 0.537
| TGN | 0.694 | 0.679 | 0.692 | 0.702 | 0.582 | 0.539 | 0.581 | 0.588
UNvote | DySAT | 0.510 | 0.502 | 0.508 | 0.516 | 0.511 | 0.499 | 0.509 | 0.519
| JODIE | 0.684 | 0.639 | 0.696 | 0.714 | 0.694 | 0.635 | 0.698 | 0.703
| TGN | 0.681 | 0.601 | 0.693 | 0.709 | 0.650 | 0.594 | 0.660 | 0.673
LASTFM | DySAT | 0.701 | 0.640 | 0.704 | 0.754 | 0.709 | 0.622 | 0.712 | 0.738
| JODIE | 0.536 | 0.549 | 0.551 | 0.558 | 0.549 | 0.526 | 0.558 | 0.571
| TGN | 0.742 | 0.603 | 0.740 | 0.700 | 0.706 | 0.596 | 0.701 | 0.676
Flights | DySAT | 0.737 | 0.699 | - | 0.511 | 0.710 | 0.689 | - | 0.521
| JODIE | 0.736 | 0.484 | - | 0.772 | 0.656 | 0.605 | - | 0.689
| TGN | 0.771 | 0.573 | - | 0.807 | 0.696 | 0.665 | - | 0.747
Avg Rank | 2.75 | 3.19 | 2.18 | 1.72 | 2.64 | 3.28 | 2.39 | 1.56

#### Transductive Setting

In the transductive setting, our method delivers the best results across 8
datasets, with its overall average rank nearly half a point better than the
second-best method, ENS, and more than a point ahead of random and recent
samplings. This suggests that our method outperforms all existing methods in
predicting historical recurrence while maintaining strong performance in
predicting random samples.

At the dataset level, our method excels in relatively dense networks with
frequent recurrence of recent historical interactions (low Average Time
Proximity), such as USLegis, CanParl, and Flights, where it surpasses the best
existing methods by around 5%. This demonstrates that our method, by utilizing
temporal-aware disentangled factors for selection, can more accurately
distinguish between enduring and transient relationships over time. In
networks with high repetition and recency effects – typically favorable for
recent sampling – such as enron, UNtrade, and UNvote, our method still
outperforms recent sampling. Furthermore, it achieves an average improvement
of nearly 5% over the best random sampling and nearly 3% over ENS, showcasing
its effectiveness in capturing periodic and recurrent patterns. These results
confirm our method’s capability in addressing positive shift.

In very sparse networks, our method also outperforms random sampling across
all datasets and, on average, surpasses ENS and recent sampling. Even where it
does not lead, it remains competitively close to the top performer. The only
exception is myket, whose sparsity, recency, and repetition make it akin to a
static network, rendering ENS and CurNM – methods designed for temporal
networks – less effective. Despite this, the overall performance indicates
that our method successfully circumvents the steep gradient curve prevalent in
hard negative sampling, effectively addressing positive sparsity even in less
favorable scenarios.

#### Inductive Setting

The inductive setting allows us to compare our method’s generalizability
against existing methods by evaluating their performances on unseen nodes.
When comparing inductive to transductive settings, the average ranks of ENS
and recent sampling worsen, suggesting that their heuristic strategies might
not be generalizable and could lead to overfitting on seen nodes. On the
contrary, the average rank of random sampling improves, indicating its
robustness despite relatively weaker performance. Finally, our CurNM method
consistently achieves the best across 9 datasets and delivers a higher average
rank in the inductive setting compared to the transductive setting. This
confirms that our method not only performs well but is also robust and highly
generalizable.

At the dataset level, our method consistently outperforms or matches the
existing methods in almost all datasets, with insignificant declines in only
two cases (again, with myket being an outlier).

###  5.4 Complexity Analysis

Theoretically, CurNM adds a negative mining process with a time complexity of
$O(|E|\times n\times d)$ to TGNNs, which originally have a complexity of
$O(L\times|E|\times n\times d)$. Here, $L$ denotes the number of layers, $|E|$
is the number of edges, and $n$ represents the number of positive and negative
samples per node, with nonlinear operations simplified to $O(d)$.

Empirically, CurNM maintains high efficiency by limiting $n$ with a relatively
small negative pool, sized at $M=8$. Table 3 presents a runtime comparison
between CurNM and baseline methods on the TGN model, which demonstrates the
best overall performance among the three TGNNs evaluated. According to Table
3, CurNM adds minimal computational load compared to basic random and recent
sampling, consistently requiring about twice the time regardless of dataset
size. Moreover, it is significantly more efficient than the state-of-the-art
ENS on large datasets, requiring approximately one-seventh of the time on
Flights, the largest dataset tested.

Table 3: Comparison of average runtimes per epoch between CurNM and baseline
methods on the TGN model. $Ratio_{Rand}$, $Ratio_{Rec}$, and $Ratio_{ENS}$
represent the ratio of CurNM runtime to Random, Recent, and ENS runtimes,
respectively.

Dataset | Random | $Ratio_{Rand}$ | Recent | $Ratio_{Rec}$ | ENS | $Ratio_{ENS}$ | CurNM
---|---|---|---|---|---|---|---
uci | 8.0 | 1.86 | 8.6 | 1.73 | 10.8 | 1.38 | 14.9
USLegis | 8.8 | 1.86 | 8.6 | 1.91 | 12.1 | 1.36 | 16.4
CanParl | 11.3 | 1.47 | 11.4 | 1.46 | 17.1 | 0.97 | 16.6
enron | 16.4 | 1.7 | 17.0 | 1.64 | 17.7 | 1.58 | 27.9
WIKI | 22.7 | 1.45 | 23.4 | 1.41 | 28.5 | 1.15 | 32.9
MOOC | 39.9 | 2.09 | 43.4 | 1.92 | 152.7 | 0.55 | 83.3
UNtrade | 65.6 | 1.83 | 71.8 | 1.67 | 154.6 | 0.78 | 120.1
REDDIT | 84.9 | 1.76 | 116.7 | 1.28 | 290.8 | 0.51 | 149.0
myket | 79.3 | 2.18 | 89.2 | 1.94 | 1133.9 | 0.15 | 172.8
UNvote | 116.0 | 1.91 | 138.4 | 1.6 | 422.3 | 0.52 | 221.0
LASTFM | 161.2 | 2.29 | 156.2 | 2.36 | 1019.0 | 0.36 | 368.8
Flights | 221.8 | 2.1 | 231.7 | 2.01 | 3222.5 | 0.14 | 466.6

###  5.5 Ablation Study

The ablation study detailed in Figure 2 examines the effects of adaptive
$\pi_{e}$, annealing random negatives, hard negative cache, factor
disentanglement, and temporal-aware embeddings in our method on the TGN model.
Due to space constraints, we present our study using six datasets here. In
both transductive and inductive settings, the complete CurNM model delivers
the most robust performance across the datasets. The most significant decline
in performance is observed when random negatives are removed, validating our
claim that a steep difficulty curve can confuse the model. In datasets like
USLegis, CanParl, and enron, where our model achieves strong results, the
removal of temporal-aware embeddings and adaptive $\pi_{e}$ also leads to
substantial performance drops. This underscores their critical role in
addressing the networks’ positive sparsity and positive shift. Although the
impact of removing disentanglement and hard negative cache is less pronounced,
their absence can still result in up to a 3% performance decline, suggesting
their importance in enhancing the granularity of learning within the model.

Figure 2: Ablation studies on different components.

###  5.6 Hyper-Parameter Sensitivity

#### Impact of Strategies for $\alpha_{e},\beta_{e}$, and $\delta_{e}$

We investigate our assumptions about the structures of $\alpha_{e},\beta_{e}$,
and $\delta_{e}$ by testing an increasing strategy (e.g.,
$\alpha_{e}=\min(\frac{e}{E^{\prime}},1)$), a decreasing strategy (e.g.,
$\alpha_{e}=\max(0,1-\frac{e}{E^{\prime}})$), and a constant strategy (e.g.,
$\alpha_{e}=0.5$). Our findings in Figure 3 confirm that, as expected, our
current approach yields the most robust results. This underscores the
effectiveness of our dynamic strategies, which progressively guide the model
to focus on relevant factors of informative nodes, thereby achieving a
smoother and more advantageous learning curve.

#### Impact of Strategies for $\pi_{e}$ and $\gamma_{\text{shrink}}$

Under the framework where $\pi_{e}$ should shrink as learning progresses, we
explore two approaches: a linear strategy and an adaptive strategy. The linear
strategy consistently reduces the $\pi_{e}$ by a set amount each epoch,
whereas the adaptive strategy only does so when there’s an improvement in the
selected performance metric. For our baseline, both methods start with
$\pi_{e}=100\%$, with a shrinkage rate $\gamma_{\text{shrink}}=3\%$, and the
$\pi_{e}$ can decrease to a minimum of $10\%$. The choice of
$\gamma_{\text{shrink}}=3\%$ is based on that models generally stabilize after
approximately $30$ epochs, and having a larger $\pi_{e}$ before this phase to
capture more information would be beneficial. The adaptive strategy
outperforms the linear one. We then experiment with a slower
($\gamma_{\text{shrink}}=2\%$) and a faster shrinkage rate
($\gamma_{\text{shrink}}=5\%$). Figure 3 shows that
$\gamma_{\text{shrink}}=3\%$ yields the best results.

Figure 3: Parameter sensitivity studies on
$\alpha_{e},\beta_{e},\delta_{e},\text{ and }\pi_{e}$.

##  6 Conclusion

In this paper, we identify two unique challenges of negative sampling in
temporal networks – positive sparsity and positive shift. Our proposed CurNM
method employs a dynamically updated negative pool and a curriculum learning
strategy to adaptively adjust the difficulty level of negative samples during
training, thus addressing the common challenge of positive sparsity.
Furthermore, we implement a temporal-aware negative selection function to
effectively capture positive shift. Our method’s efficacy is demonstrated
through extensive experiments against 3 algorithms and 12 datasets. Although
CurNM demonstrates superior performance, it requires tuning several hyper-
parameters to optimize its performance. In the future, we aim to simplify
these designs to reduce the need for extensive parameter tuning.

## Declaration of interests

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Acknowledgements

This work was supported by the Joint Funds of the Zhejiang Provincial Natural
Science Foundation of China [grant number LHZSD24F020001]; Zhejiang Province
”JianBingLingYan+X” Research and Development Plan [grant number 2024C01114];
Ningbo Natural Science Foundation [grant number 2023J281]; and Zhejiang
Province High-Level Talents Special Support Program ”Leading Talent of
Technological Innovation of Ten-Thousands Talents Program” [grant number
2022R52046].

## References

  * Bennett and Lanning, [2007] Bennett, J. and Lanning, S. (2007).  The netflix prize.
  * Brown et al., [2020] Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. (2020).  Language models are few-shot learners.  ArXiv, abs/2005.14165.
  * Chen et al., [2020] Chen, J., Dong, H., Wang, X., Feng, F., Wang, M., and He, X. (2020).  Bias and debias in recommender system: A survey and future directions.  ACM Transactions on Information Systems, 41:1–39.
  * Chen et al., [2017] Chen, T., Sun, Y., Shi, Y., and Hong, L. (2017).  On sampling strategies for neural network-based collaborative filtering.  In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
  * Ding et al., [2020] Ding, J., Quan, Y., Yao, Q., Li, Y., and Jin, D. (2020).  Simplify and robustify negative sampling for implicit collaborative filtering.  ArXiv, abs/2009.03376.
  * Fowler, [2006] Fowler, J. H. (2006).  Legislative cosponsorship networks in the us house and senate.  Social Networks, 28(4):454–465.
  * Gao et al., [2024] Gao, K., Liu, C., Wu, J., Du, B., and Hu, W. (2024).  Towards a better negative sampling strategy for dynamic graphs.  Neural Networks: The Official Journal of the International Neural Network Society, 173:106175.
  * Goyal et al., [2018] Goyal, P., Chhetri, S. R., Mehrabi, N., Ferrara, E., and Canedo, A. (2018).  Dynamicgem: A library for dynamic graph embedding methods.  ArXiv, abs/1811.10734.
  * Grover and Leskovec, [2016] Grover, A. and Leskovec, J. (2016).  node2vec: Scalable feature learning for networks.  Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
  * Hamilton et al., [2017] Hamilton, W. L., Ying, Z., and Leskovec, J. (2017).  Inductive representation learning on large graphs.  In Neural Information Processing Systems.
  * Huang et al., [2020] Huang, S., Hitti, Y., Rabusseau, G., and Rabbany, R. (2020).  Laplacian change point detection for dynamic graphs.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.
  * Huang et al., [2021] Huang, T., Dong, Y., Ding, M., Yang, Z., Feng, W., Wang, X., and Tang, J. (2021).  Mixgcf: An improved training method for graph neural network-based recommender systems.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD ’21, pages 665–674, Virtual Event, Singapore. Association for Computing Machinery.
  * Kazemi et al., [2019] Kazemi, S. M., Goel, R., Jain, K., Kobyzev, I., Sethi, A., Forsyth, P., Poupart, P., and Borgwardt, K. M. (2019).  Representation learning for dynamic graphs: A survey.  J. Mach. Learn. Res., 21:70:1–70:73.
  * Kipf and Welling, [2016] Kipf, T. and Welling, M. (2016).  Semi-supervised classification with graph convolutional networks.  ArXiv, abs/1609.02907.
  * Krizhevsky et al., [2012] Krizhevsky, A., Sutskever, I., and Hinton, G. E. (2012).  Imagenet classification with deep convolutional neural networks.  Communications of the ACM, 60:84 – 90.
  * Kumar et al., [2019] Kumar, S., Zhang, X., and Leskovec, J. (2019).  Predicting dynamic embedding trajectory in temporal interaction networks.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.
  * Lai et al., [2023] Lai, R., Chen, L., Zhao, Y., Chen, R., and Han, Q. (2023).  Disentangled negative sampling for collaborative filtering.  In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, WSDM ’23, pages 96–104, Singapore, Singapore. Association for Computing Machinery.
  * Liu et al., [2021] Liu, C., Wu, J., Liu, W., and Hu, W. (2021).  Enhancing graph neural networks by a high-quality aggregation of beneficial information.  Neural Networks, 142(C):20–33.
  * MacDonald et al., [2015] MacDonald, G. K., Brauman, K. A., Sun, S., Carlson, K. M., Cassidy, E. S., Gerber, J. S., and West, P. C. (2015).  Rethinking agricultural trade relationships in an era of globalization.  BioScience, 65(3):275–289.
  * Mikolov et al., [2013] Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J. (2013).  Distributed representations of words and phrases and their compositionality.  In Neural Information Processing Systems.
  * Panzarasa et al., [2009] Panzarasa, P., Opsahl, T., and Carley, K. M. (2009).  Patterns and dynamics of users’ behavior and interaction: Network analysis of an online community.  Journal of the Association for Information Science and Technology, 60:911–932.
  * Pareja et al., [2019] Pareja, A., Domeniconi, G., Chen, J., Ma, T., Suzumura, T., Kanezashi, H., Kaler, T., and Leisersen, C. E. (2019).  Evolvegcn: Evolving graph convolutional networks for dynamic graphs.  ArXiv, abs/1902.10191.
  * Perozzi et al., [2014] Perozzi, B., Al-Rfou, R., and Skiena, S. S. (2014).  Deepwalk: online learning of social representations.  Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining.
  * Rossi et al., [2020] Rossi, E., Chamberlain, B. P., Frasca, F., Eynard, D., Monti, F., and Bronstein, M. M. (2020).  Temporal graph networks for deep learning on dynamic graphs.  ArXiv, abs/2006.10637.
  * Sankar et al., [2018] Sankar, A., Wu, Y., Gou, L., Zhang, W., and Yang, H. (2018).  Dynamic graph representation learning via self-attention networks.  ArXiv, abs/1812.09430.
  * Schäfer et al., [2014] Schäfer, M., Strohmeier, M., Lenders, V., Martinovic, I., and Wilhelm, M. (2014).  Bringing up opensky: A large-scale ads-b sensor network for research.  In IPSN-14 Proceedings of the 13th International Symposium on Information Processing in Sensor Networks, pages 83–94.
  * Seo et al., [2016] Seo, Y., Defferrard, M., Vandergheynst, P., and Bresson, X. (2016).  Structured sequence modeling with graph convolutional recurrent networks.  In International Conference on Neural Information Processing.
  * Shetty and Adibi, [2004] Shetty, J. and Adibi, J. (2004).  The enron email dataset database schema and brief statistical report.
  * Skarding et al., [2020] Skarding, J., Gabrys, B., and Musial, K. (2020).  Foundations and modeling of dynamic networks using dynamic graph neural networks: A survey.  IEEE Access, 9:79143–79168.
  * Trivedi et al., [2019] Trivedi, R. S., Farajtabar, M., Biswal, P., and Zha, H. (2019).  Dyrep: Learning representations over dynamic graphs.  In International Conference on Learning Representations.
  * Velickovic et al., [2017] Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio’, P., and Bengio, Y. (2017).  Graph attention networks.  ArXiv, abs/1710.10903.
  * Wu et al., [2019] Wu, G., Volkovs, M., Soon, C. L., Sanner, S., and Rai, H. (2019).  Noise contrastive estimation for one-class collaborative filtering.  In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR’19, pages 135–144, Paris, France. Association for Computing Machinery.
  * Xu et al., [2020] Xu, D., Ruan, C., Körpeoglu, E., Kumar, S., and Achan, K. (2020).  Inductive representation learning on temporal graphs.  ArXiv, abs/2002.07962.
  * [34] Yu, L., Sun, L., Du, B., and Lv, W. (2023a).  Towards better dynamic graph learning: New architecture and unified library.  ArXiv, abs/2303.13047.
  * [35] Yu, L., Sun, L., Du, B., and Lv, W. (2023b).  Towards better dynamic graph learning: New architecture and unified library.  ArXiv, abs/2303.13047.
  * Zhang et al., [2013] Zhang, W., Chen, T., Wang, J., and Yu, Y. (2013).  Optimizing top-n collaborative filtering via dynamic negative item sampling.  In Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval.
  * Zhang et al., [2023] Zhang, Y., Xiong, Y., Liao, Y., Sun, Y., Jin, Y., Zheng, X., and Zhu, Y. (2023).  Tiger: Temporal interaction graph embedding with restarts.  Proceedings of the ACM Web Conference 2023.
  * Zhang et al., [2019] Zhang, Y., Yao, Q., Shao, Y., and Chen, L. (2019).  Nscaching: Simple and efficient negative sampling for knowledge graph embedding.  In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 614–625. IEEE.
  * Zhao et al., [2023] Zhao, Y., Chen, R., Lai, R., Han, Q., Song, H., and Chen, L. (2023).  Augmented negative sampling for collaborative filtering.  In Proceedings of the 17th ACM Conference on Recommender Systems.
  * Zhou et al., [2022] Zhou, H., Zheng, D., Nisa, I., Ioannidis, V., Song, X., and Karypis, G. (2022).  Tgl: A general framework for temporal gnn training on billion-scale graphs.  Proc. VLDB Endow., 15:1572–1580.