# Reprogramming Language Models for Molecular Representation Learning

Ria Vinod
Department of Electrical Engineering and Computer Science
University of California, Berkeley
<EMAIL_ADDRESS>
&Pin-Yu Chen
IBM Research
Yorktown Heights, NY
<EMAIL_ADDRESS>
Payel Das
IBM Research
Yorktown Heights, NY
<EMAIL_ADDRESS>
Work done during internship at IBM Research

###### Abstract

Recent advancements in transfer learning have made it a promising approach for
domain adaptation via transfer of learned representations. This is especially
when relevant when alternate tasks have limited samples of well-defined and
labeled data, which is common in the molecule data domain. This makes transfer
learning an ideal approach to solve molecular learning tasks. While
Adversarial Reprogramming has proven to be a successful method to repurpose
neural networks for alternate tasks, most works consider source and alternate
tasks within the same domain. In this work, we propose a new algorithm,
Representation Reprogramming via Dictionary Learning (R2DL), for adversarially
reprogramming pretrained language models for molecular learning tasks,
motivated by leveraging learned representations in massive state of the art
language models. The adversarial program learns a linear transformation
between a dense source model input space (language data) and a sparse target
model input space (e.g., chemical and biological molecule data) using a k-SVD
solver to approximate a sparse representation of the encoded data, via
dictionary learning. This method achieves the baseline established by state of
the art toxicity prediction models trained on domain-specific data using only
a standard well-trained text classifier, thereby establishing avenues for
domain-agnostic transfer learning for tasks with molecule data.

##  1 Introduction

Deep learning has proven to be an extremely successful tool for various
applications for the natural sciences. While works like MoleculeNet have made
significant progress in publishing benchmarks on various molecular learning
tasks, curating substantial, well-structured and labeled molecule datasets
remains a critical constraint in training high performing models from scratch
to establish baselines for a multitude of tasks [1]. A lack of substantive
training datsets motivates transfer learning to be a natural approach to solve
problems in the molecule data domain, as it has proven to be a successful
technique to solve new tasks using learned representations from source model
domains [2]. In this paper, we consider an empirically successful transfer
learning method, adversarial reprogramming, where a learned function
adversarially perturbs input samples to the model such that the model can
perform a task chosen by the adversary [3]. The motivations of the transfer
learning approach lie in the recent successes of powerful general language
models [4], and being able to leverage these learned representations when
applied to molecule data that can be treated as sequence data. However, the
adversarial reprogramming method is well suited to models operating within a
continuous input space (such as images), but discrete input spaces require
that we learn a mapping between source-model space and target-model space.
Reprogramming of text classifiers and language models has been explored [5],
as well as knowledge injection for general language models [6], but such
approaches do not investigate mappings between domains that require a very
high representational capacity (from language data to molecule data). This
shift in domain poses a significant challenge through the reduction of
dimensionality of the input space. We end up with an overdetermined system, as
we have more observations in the source-model input space than in the target-
model input space. To address this, we use a dictionary learning approach to
encode a sparse representation of the embeddings of the input data to the pre-
trained language model (text classifier). Training the adversarial program
(AP) via dictionary learning enables us to approximate a linear transformation
(mapping) between the input spaces of the source and target models, it learns
the optimal coefficients of the atoms in our molecule data to represent the
dictionary. When compared to the baselines of training AMP models from
scratch, repurposing a sentiment classifier via R2DL outperforms the baseline
for AMP/non-AMP (90.01 % vs 88.0 %) and achieves approximately the same
progress on toxicity prediction (89.34 % vs 93.7 %).

##  2 Related Work

###  2.1 Adversarial Machine Learning and Reprogramming

Adversarial attacks on ML models in discrete input spaces have been found to
cause models to misclassify input samples by manipulating tokens in sequence
data [7]. Adversarial Reprogramming (AR) is a technique [3] that is able to
repurpose a model (without significant changes to the architecture and
parameters) by training an adversary to optimally transform input data such
that we can choose the output of the model. This method has been proven to be
successful in both, white-box and black-box settings [8]. The depth and the
size of large general language models make them ideal candidates to be
adversarially reprogrammed, as modifying the internal architecture or
finetuning over 1 billion parameters is infeasible for a traditional transfer
learning approach. The work in [5] assumes an exposed model, where they use
the learned parameters of the pre-trained source model to generate context-
based vocabulary map. However, the hypothesis of comparable vocabulary size
does not hold when the source data are English vocabularies (on the order of
$\sim$ 10 million) and the target data are amino acids (on the order of $\sim$
20). To that end, we introduce dictionary learning to train our AP.

###  2.2 Dictionary Learning

Typical amino acid/nucleotide representations of biological molecules or
widely used SMILES representation of chemical molecules have fewer distinct
tokens than that of language data. The significant reduction in dimensionality
of the embedded space of English data to molecule data makes finding a mapping
non-trivial. Results in [9] demonstrate that that representation learning
algorithms have an advantage in transfer learning methods as they capture
features relevant to alternate tasks. We require a mapping with high
representational capacity. Work in [10] demonstrates that a sparse encoding is
distributed and highly expressive: we can represent $O(2^{k})$ input regions
with only $O(N)$ parameters. Distributed representations can be clustered to
extract relevant features where component extraction algorithms can find the
optimal representation (a dictionary). We use a k-SVD approximation algorithm
[11] to mitigate computational expenses.

##  3 Representation Reprogramming via Dictionary Learning (R2DL): Algorithm
and Method

###  3.1 Problem Formulation

We are given a pretrained classifier, $X$, a source-task dataset
$\\{V_{S}\\}^{n}_{i=1}$ and target-task dataset $\\{V_{T}\\}^{m}_{j=1}$. The
embedded matrices are $V_{T}$ and $V_{S}$ respectively. We can encode an
output label mapping function $h:l_{V_{S}}\longmapsto l_{V_{T}}$. We then aim
to train an adversarial program (AP) $f_{\theta}$ that finds the optimal
coefficients $\theta$ of our atoms in $V_{T}$ to represent a sparse encoding
of the dictionary, $V_{S}$ such that $V_{T}=V_{S}\theta$. The AP $f_{\theta}$
is used to perform the target task through the transformation
$h(X(f_{\theta}(t_{i}))$ where $t_{i}$ is a molecule data sample. While we do
not make any modification the parameters or architecture of $X$, we assume
access to the gradient $\nabla_{\theta}X$ for loss evaluation during training.

###  3.2 Adversarial Program

To reprogram the pretrained classifier, we use a similar structure as
introduced in [5], $f_{\theta}:t_{i}\longmapsto s_{i}$ where $t_{i}\in V_{T}$
and $s_{i}\in V_{S}$. Dimension of the input space of $V_{S}$ and $V_{T}$ is
$|V_{S}|$, and $|V_{T}|$ respectively, where $|V_{T}|\ll|V_{S}|$. The AP
$f_{\theta}$ is parametrized by $\theta\in\mathbf{R}^{|V_{S}|\times|V_{T}|}$,
which represents the coefficients of the atoms in $V_{T}$ such that
$V_{T}=V_{S}\theta$ and $V_{S}$ is our dictionary. The observation of
$|V_{T}|\ll|V_{S}|$ requires that our mapping has high representational
capacity, so we encode a sparse representation of $V_{S}$, to extract relevant
features from the embeddings of the source-model vocabulary
$\\{V_{S}\\}^{n}_{i=1}$ for the alternate task. To that end, approximate the
dictionary, we use a k-SVD solver to optimize over the cross entropy loss for
updates to $\theta$.

###  3.3 k-SVD

We define $\theta\in\mathbf{R}^{|V_{S}|\times|V_{T}|}$ and use $\theta_{t}$ to
denote its $t$-th column, where a signal (embedding vector) $v_{t}$, can be
represented as a sparse linear combination of the signal atoms of columns of
$V_{S}$, $v_{t}=V_{S}\theta_{t}$. $v_{t}$ is the representation of the AMP
input sample in the dictionary space and satisfies
$||v_{t}-V_{s}\theta_{t}||_{p}\leq\epsilon$. An exact solution
$\theta_{t}^{*}$ such that $v_{t}=V_{S}\theta_{t}^{*}$ is computationally
expensive to find, and is subject to various convergence traps, so for the
purpose of our efficient AP approach we approximate $v_{t}\approx
V_{s}\theta_{t}$ by limiting the number of iterations to converge to a
solution for $v_{t}$. Our optimization problem for finding the optimal sparse
representation of input data samples in $V_{T}$ is then minimize
$||\theta||_{0}$ subject to $||v_{t}-V_{s}\theta_{t}||_{1}\leq\epsilon$ to
enforce a sparse solution [11], where $||\cdot||_{0}$ denotes the $l_{0}$
norm. While algorithms exist to choose an optimal dictionary (an exact
solution to k-SVD) that can be continually updated [11], we penalize
computational expense over performance for the purpose of maintaining an
efficient solution (at the cost of statistically insignificant improvements in
accuracy) by using a predetermined number of steps for an approximate
solution, $V_{S}$ that encodes the atoms of $V_{T}$. $\theta$ is then used to
evaluate the cross entropy loss on $h(X(f_{\theta}(V_{T}))$, which will be
updated in the AP $f_{\theta}$.

##  4 Experiments

Input: Pretrained sentiment classifier $X$, source model training data
$\\{V_{S}\\}^{n}_{i=1}$, target model training data $\\{V_{T}\\}^{m}_{j=1}$,
maximum number of iterations $T_{1}$ for updates to $\theta$, number of
iterations $T_{2}$ for k-SVD, output-label mapping function $h$(·), step size
$\\{\alpha_{i}\\}^{T_{1}}_{i=1}$

Output: Optimal adversarial program parameters $\theta$

1\. Random initialization of $\theta$;

2\. Define objective function for k-SVD from (1) ;

3\. while  _$t_{1}\leq T_{1}$_ do

4\. while  _$t_{2}\leq T_{2}$_ do

use approximate k-SVD to solve $V_{T}\approx V_{S}\theta$ ;

$t_{2}\longleftarrow t_{2}+1$ ;

end while

#Loss evaluation for $\theta$ ;

$\theta\longleftarrow\theta-\alpha_{t_{1}}\cdot\nabla_{\theta}h(X(f_{\theta}(t_{i}))$;

$t_{1}\longleftarrow t_{1}+1$ ;

end while

Algorithm 1 Representation Reprogramming via Dictionary Learning (R2DL)

###  4.1 Baseline

To benchmark the performance of R2DL we compare it with the current
established benchmark of a trained classifier using the same AMP training data
set [12].

Table 1: Baseline AMP Classification (Train from Scratch) Attribute | Data-Split | Accuracy | Screening Threshold
---|---|---|---
Train | Valid | Test | Majority Class | Test
{Toxic, non-Toxic} | 8153 | 1019 | 1020 | 82.73 | 93.7 | -1.573
{AMP, non-AMP} | 6489 | 811 | 812 | 82.68.9 | 88.0 | 7.944

###  4.2 Restricted Training Data Setting

To further investigate the efficacy of the transfer learning approach, we
compare the performance of R2DL versus the model trained from scratch with AMP
data, with a restricted training data set. The test accuracies indicate that
R2DL performs better when fewer labeled training data samples are available.
Tables 2 and 3 show that when trained in a setting with fewer labeled data
samples, R2DL outperforms the train from scratch method after the threshold of
approximately 5000 samples. Below 5000 samples, both methods approximate
random prediction, with R2DL not successfully transferring any learned
representations 1115000 AMP training samples and below were excluded from the
results below as they showed statistically insignificant test accuracy..

Table 2: Restricted Data Setting: Toxicity Prediction Task |  AMP Sequences Training Samples |  R2DL Test Accuracy |  Bi-LSTM Test Accuracy (train from scratch)
---|---|---|---
Toxicity Prediction |  5000 |  42.12 |  37.34
Toxicity Prediction |  6000 |  62.98 |  49.62
Toxicity Prediction |  7000 |  86.23 |  82.78
Toxicity Prediction |  8153 |  89.34 |  93.7
Table 3: Restricted Data Setting: AMP Prediction Task |  AMP Sequences Training Samples |  R2DL Test Accuracy |  Bi-LSTM Test Accuracy (train from scratch)
---|---|---|---
AMP Prediction |  3500 |  59.82 |  64.52
AMP Prediction |  4500 |  72.76 |  68.41
AMP Prediction |  5500 |  84.17 |  74.34
AMP Prediction |  6489 |  90.01 |  88.0

###  4.3 Repurposing Sentiment Classifiers

BERT and GPT-3 are 2 of the most common powerful language models, that
generalize well across various NLP tasks, dealing with language (sequence)
data. In this experiment, we use BERT, a bidirectional transformer, tuned for
the sentiment classification task on the IMDB movie review dataset. As R2DL
assumed access to the gradients of the source model ($\nabla X$), this
approach works in a semi-black box setting given that we access but do not
modify the internal architecture. In this task, we use sentiment
classification as the source task, in which there are 2 output classes
(positive, negative), and AMP toxicity classification as the target task
(toxic, non-toxic). The output-label mapping $h$ is then a simple 1-1
correspondence between (positive, toxic) and (negative, non-toxic). The input
data of the source model (BERT) is tokenized on a word-level which form the
atoms for our dictionary representation of $V_{S}$. The input data to the
target task, AMP sequences, are tokenized on a character level with only 7
distinct tokens. The embeddings of a source vocabulary token, $v_{s}$, is then
represented as a weighted combination of the atoms of the AMP sequence tokens.
Using the $l^{0}$ norm in our objective function, 100 k-SVD iterations and
$\epsilon=0.045$, we are able to achieve accuracy on the order of the
benchmark when trained from scratch in table 1. Table 4 shows accuracies for
sentiment classification source models and the target task, and Table 5 shows
accuracies as we increase the number of k-SVD iterations for a convergent
solution.

Table 4: AR for Sentiment Classifiers: Toxicity Prediction Source Model |  AMP Sequence Samples |  k-SVD Iterations |  Training Accuracy |  Test Accuracy
---|---|---|---|---
BERT (Bidirectional Transformer) |  8153 |  100 |  84.78 |  87.23
BERT (Bidirectional Transformer) |  8153 |  200 |  85.23 |  86.93
Bi-LSTM |  8153 |  100 |  76.34 |  81.25
Table 5: k-SVD Iterations vs. Accuracy Source Model | AMP Sequence Samples | k-SVD Iterations | Training Accuracy | Test Accuracy
---|---|---|---|---
BERT | 8153 | 100 | 84.78 | 87.23
BERT | 8153 | 200 | 82.24 | 85.61
BERT | 8153 | 300 | 85.12 | 89.34

Table 5 shows the stagnation of performance with k-SVD iterations. We see that
R2DL acheives the performance (89.34 %) of the baseline (93.7.0 %) when the
pretrained classifier is a bidirectional transformer. Intuitively, we can
understand why more expressive models have an increased representational
capacity that can be leveraged to transfer relevant features from the
pretrained classifier. Additionally, more precise k-SVD solutions beyond 100
iterations are not correlated with increased performance, and only increase
computational cost, making this approach less efficient.

##  5 Conclusion

This work formalizes the argument for finding sparse representations of dense
input data for cross domain transfer learning. In a setting where access to
well structured and labelled data is limited, we can leverage representations
in deep models through adversarial reprogramming and approximating a sparse
coding. This approach demonstrated a either higher or comparable performance
across different tasks when compared to training from scratch, but at a much
lower cost and also performed better on fewer target task training samples.
Our results provide new insights for domain-agnostic transfer learning, and
establishes avenues for several molecular learning tasks that have been
constrained by a lack of access to well-defined datasets.

##  6 Future Work

Immediate plans for this work include evaluating cost effectiveness of this
approach with analysis of computational complexity and time. Future plans for
this work extend to representation learning tasks for molecules with multi-
dimensional structures (Simplified molecular-input line-entry system -
SMILES). We also plan to explore meta-learning capabilities for generalization
with respect to various molecular learning tasks, variable length molecule
sequences, and variable sequence structures. Planned target tasks in the
molecule domain include graph generation and genetic code classification.

## References

  * [1] Zhenqin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay S. Pande.  Moleculenet: A benchmark for molecular machine learning.  CoRR, abs/1703.00564, 2017.
  * [2] S. J. Pan and Q. Yang.  A survey on transfer learning.  IEEE Transactions on Knowledge and Data Engineering, 22(10):1345–1359, 2010.
  * [3] Gamaleldin F. Elsayed, Ian Goodfellow, and Jascha Sohl-Dickstein.  Adversarial reprogramming of neural networks.  2019\.
  * [4] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  CoRR, abs/1810.04805, 2018.
  * [5] Paarth Neekhara, Shehzeen Hussain, Shlomo Dubnov, and Farinaz Koushanfar.  Adversarial reprogramming of sequence classification neural networks.  2019\.
  * [6] Anne Lauscher, Olga Majewska, Leonardo F. R. Ribeiro, Iryna Gurevych, Nikolai Rozanov, and Goran Glavaš.  Common sense or world knowledge? investigating adapter-based knowledge injection into pretrained transformers.  arXiv preprint arXiv:2005.11787, 2020.
  * [7] Nicolas Papernot, Patrick D. McDaniel, Ananthram Swami, and Richard E. Harang.  Crafting adversarial input sequences for recurrent neural networks.  CoRR, abs/1604.08275, 2016.
  * [8] Yun-Yun Tsai, Pin-Yu Chen, and Tsung-Yi Ho.  Transfer learning without knowing: Reprogramming black-box machine learning models with scarce data and limited resources.  2020\.
  * [9] Yoshua Bengio, Aaron C. Courville, and Pascal Vincent.  Unsupervised feature learning and deep learning: A review and new perspectives.  CoRR, abs/1206.5538, 2012.
  * [10] Ian Goodfellow, Honglak Lee, Quoc V. Le, Andrew Saxe, and Andrew Y. Ng.  Measuring invariances in deep networks.  pages 646–654, 2009.
  * [11] M. Aharon, M. Elad, and A. Bruckstein.  K-svd: An algorithm for designing overcomplete dictionaries for sparse representation.  IEEE Transactions on Signal Processing, 54(11):4311–4322, 2006\.
  * [12] Payel Das, Tom Sercu, Kahini Wadhawan, Inkit Padhi, Sebastian Gehrmann, Flaviu Cipcigan, Vijil Chenthamarakshan, Hendrik Strobelt, Cicero dos Santos, Pin-Yu Chen, et al.  Accelerating antimicrobial discovery with controllable deep generative models and molecular dynamics.  arXiv preprint arXiv:2005.11248, 2020.


# Nonvanishing and Abundance
for cones of movable divisors

G. Bini, M.C. Brambilla, C. Fontanari, E. Postinghel  Gilberto Bini,
Dipartimento di Matematica e Informatica, Università degli Studi di Palermo,
Via Archirafi 34, 90138 Palermo, Italy<EMAIL_ADDRESS>Maria Chiara
Brambilla, Università Politecnica delle Marche, Via Brecce Bianche, 60131
Ancona, Italy<EMAIL_ADDRESS>Claudio Fontanari, Dipartimento di
Matematica, Università degli Studi di Trento, Via Sommarive 14, 38123 Povo,
Trento, Italy<EMAIL_ADDRESS>Elisa Postinghel, Dipartimento di
Matematica, Università degli Studi di Trento, Via Sommarive 14, 38123 Povo,
Trento, Italy<EMAIL_ADDRESS>
###### Abstract.

Let $\overline{\textrm{Mov}}^{k}(X)$ be the closure of the cone
$\textrm{Mov}^{k}(X)$ generated by classes of effective divisors on a
projective variety $X$ with stable base locus of codimension at least $k+1$.
We propose a generalized version of the Log Nonvanishing Conjecture and of the
Log Abundance Conjecture for a klt pair $(X,\Delta)$, that is: if
$K_{X}+\Delta\in\overline{\textrm{Mov}}^{k}(X)$, then
$K_{X}+\Delta\in\textrm{Mov}^{k}(X)$. Moreover, we prove that if the Log
Minimal Model Program, the Log Nonvanishing, and the Log Abundance hold, then
so does our conjecture.

###### Key words and phrases:

Nonvanishing Conjecture, Abundance Conjecture, Movable Cone

###### 1991 Mathematics Subject Classification:

14E30

##  1\. Introduction

Let $X$ be a normal projective variety of dimension $n$ and fix an integer $k$
with $0\leq k\leq n-1$.

The cone $\textrm{Mov}^{k}(X)\subset N^{1}(X)_{\mathbb{R}}$ is the cone
generated by numerical classes of effective Cartier divisors $D$ such that the
stable base locus of $|D|$ has codimension at least $k+1$ in $X$. The cone
$\overline{\textrm{Mov}}^{k}(X)$ is the closure of $\textrm{Mov}^{k}(X)$ in
$N^{1}(X)_{\mathbb{R}}$.

In particular, $\textrm{Mov}^{0}(X)=\textrm{Eff}(X)$ is the cone of effective
divisors and $\overline{\textrm{Mov}}^{0}(X)=\overline{\textrm{Eff}}(X)$ is
the cone of pseudoeffective divisors. Next, $\overline{\textrm{Mov}}^{1}(X)$
is just the standard movable cone. Finally,
$\textrm{Mov}^{n-1}(X)=\textrm{Sem}(X)$ turn out to be the cone of semiample
divisors by the Theorem of Zariski-Fujita (see for instance [6], Remark
2.1.32) and $\overline{\textrm{Mov}}^{n-1}(X)={\textrm{Nef}}(X)$ is the nef
cone.

The cones $\textrm{Mov}^{k}(X)$ form a natural filtration:

$\textrm{Sem}(X)=\textrm{Mov}^{n-1}(X)\subseteq\textrm{Mov}^{n-2}(X)\subseteq\ldots\subseteq\textrm{Mov}^{1}(X)\subseteq\textrm{Mov}^{0}(X)=\textrm{Eff}(X)$

Taking closures, we obtain a similar filtration of the corresponding closed
cones.

In [3], the cones $\overline{\textrm{Mov}}^{k}(X)$ were denoted by
$\mathcal{D}_{k}(X)$ and called _the cones of divisors that are ample in
codimension $k$_, following the terminology introduced in [10].

If $X$ is a Mori Dream Space, then we have
$\textrm{Mov}^{k}(X)=\overline{\textrm{Mov}}^{k}(X)$ for $k\in\\{0,1,n-1\\}$
by definition and the same holds also for all other values of $k$ by [3],
Theorem 1.1. For an arbitrary $X$, the cones $\textrm{Mov}^{k}(X)$ need not be
closed, but the canonical divisor $K_{X}$ is expected to behave well at least
with respect to $\textrm{Mov}^{0}(X)$ and $\textrm{Mov}^{n-1}(X)$. Indeed, we
have the following celebrated conjectures in birational geometry:

######  Conjecture 1.

_(Log Nonvanishing)_ Let $(X,\Delta)$ be a projective klt pair. If
$K_{X}+\Delta\in\overline{\textrm{Eff}}(X)=\overline{\textrm{Mov}}^{0}(X)$,
then $K_{X}+\Delta\in\textrm{Eff}(X)=\textrm{Mov}^{0}(X)$.

######  Conjecture 2.

_(Log Abundance)_ Let $(X,\Delta)$ be a projective klt pair with $\dim(X)=n$.
If $K_{X}+\Delta\in{\textrm{Nef}}(X)=\overline{\textrm{Mov}}^{n-1}(X)$, then
$K_{X}+\Delta\in\textrm{Sem}(X)=\textrm{Mov}^{n-1}(X)$.

Both conjectures are true for $n\leq 3$ by [5] and for $K_{X}+\Delta$ big and
arbitrary $n$ by Kawamata-Shokurov Basepoint free theorem, but are widely open
in general (see for instance [8]).

In this paper we introduce a natural generalization of the above conjectures
for $\overline{\textrm{Mov}}^{k}(X)$ with $0\leq k\leq n-1$. Namely, we
propose the following:

######  Conjecture 3.

Let $(X,\Delta)$ be a projective klt pair with $\dim(X)=n$ and fix an integer
$k$ with $0\leq k\leq n-1$. If
$K_{X}+\Delta\in\overline{\textrm{Mov}}^{k}(X)$, then
$K_{X}+\Delta\in\textrm{Mov}^{k}(X)$.

The statement of Conjecture 3 for $1\leq k\leq n-2$ is formally the same as
the one for $k=0$ and for $k=n-1$, but it turns out to be substantially
weaker. Indeed, the assumption in the case $k=n-1$ is very explicit:
$K_{X}+\Delta\in{\textrm{Nef}}(X)=\overline{\textrm{Mov}}^{n-1}(X)$ means that
the degree of $K_{X}+\Delta$ on every irreducible curve on $X$ is nonnegative,
and the same is true also in the case $k=0$: indeed,
$K_{X}+\Delta\in\overline{\textrm{Eff}}(X)=\overline{\textrm{Mov}}^{0}(X)$
means precisely that the degree of $K_{X}+\Delta$ on any irreducible member of
a family of curves covering $X$ is nonnegative, by the main result in [2]. On
the other hand, such a _strong duality_ between divisors and curves on $X$ may
fail in the intermediate cases $1\leq k\leq n-1$ even for a toric threefold
(see [10], Example 1). A weaker form of duality, involving divisors and curves
on the (small) birational models of $X$, still holds for any $k$, at least for
Fano type varieties and Mori Dream Spaces (see [4], Theorem 1.1 and Corollary
1.1), and more generally for smooth projective varieties (see [9], Corollary
3.3 and Remark 3.4), but such a formulation is admittedly less effective than
in the two classical cases $k=n-1$ and $k=0$.

Our main result concerning Conjecture 3 is the following:

######  Theorem 1.

Let $(X,\Delta)$ be a projective klt pair with $\dim(X)=n$ and fix an integer
$k$ with $0\leq k\leq n-1$. Assume that the Log Minimal Model Program, the Log
Nonvanishing Conjecture, and the Log Abundance Conjecture hold for every pair
$(X^{\prime},\Delta^{\prime})$ with $f:X\dashrightarrow X^{\prime}$ an
isomorphism in codimension $k$ and $\Delta^{\prime}=f_{*}\Delta$. If
$K_{X}+\Delta\in\overline{\textrm{Mov}}^{k}(X)$, then
$K_{X}+\Delta\in\textrm{Mov}^{k}(X)$.

As a consequence of Mori theory in dimension three, we obtain the following
unconditional result:

######  Corollary 1.

Let $(X,\Delta)$ be a projective klt pair with $\dim(X)=3$. If
$K_{X}+\Delta\in\overline{\textrm{Mov}}^{1}(X)$, then
$K_{X}+\Delta\in\textrm{Mov}^{1}(X)$.

In particular, by taking $K_{X}=0$ and by replacing an effective divisor $D$
with $\varepsilon D$ with $0<\varepsilon<<1$, we deduce for K-trivial
threefolds that an effective divisor lying on the boundary of
$\overline{\textrm{Mov}}^{1}(X)$ is indeed movable, exactly as in the case of
Fano varieties (or, more generally, of Mori Dream Spaces):

######  Corollary 2.

Let $X$ be a projective normal threefold with trivial canonical bundle. Then
we have
$\overline{\textrm{Mov}}^{1}(X)\cap\textrm{Eff}(X)=\textrm{Mov}^{1}(X)$.

More generally, as a consequence of Theorem 1, the same equality
$\overline{\textrm{Mov}}^{1}(X)\cap\textrm{Eff}(X)=\textrm{Mov}^{1}(X)$ holds
for projective normal varieties $X$ of arbitrary dimension with trivial
canonical bundle, provided that the Log Minimal Model Program, the Log
Nonvanishing Conjecture, and the Log Abundance Conjecture hold for every small
birational modification $X^{\prime}$ of $X$. This fact is remarkable because
in the statement of the Morrison-Kawamata Cone Conjecture (see for instance
[7], Conjecture 3.3 (2)) the cone
$\overline{\textrm{Mov}}^{1}(X)\cap\textrm{Eff}(X)$ plays a crucial role.

Finally, since by [1] the Log Minimal Model Program holds for varieties of log
general type, we get:

######  Corollary 3.

Let $(X,\Delta)$ be a projective klt pair with $\dim(X)=n$ and fix an integer
$k$ with $0\leq k\leq n-1$. If $K_{X}+\Delta\in\overline{\textrm{Mov}}^{k}(X)$
is big, then $K_{X}+\Delta\in\textrm{Mov}^{k}(X)$.

We work over the complex field $\mathbb{C}$.

##  2\. Proof of Theorem 1

Since
$K_{X}+\Delta\in\overline{\textrm{Mov}}^{k}(X)\subseteq\overline{\textrm{Mov}}^{0}(X)=\overline{\textrm{Eff}}(X)$,
by the Log Nonvanishing assumption on $(X,\Delta)$ we have
$K_{X}+\Delta\in\textrm{Eff}(X)$.

We claim that there exists $f:X\dashrightarrow X^{\prime}$ an isomorphism in
codimension $k$ (i.e. a birational map with exceptional locus of codimension
at least $k+1$ in $X$) with $K_{X^{\prime}}=f_{*}K_{X}$ such that
$K_{X^{\prime}}+\Delta^{\prime}$ is nef, where $\Delta^{\prime}=f_{*}\Delta$.
Indeed, by the Log Minimal Model Program assumption on $(X,\Delta)$ there
exists a birational map $f:X\dashrightarrow X^{\prime}$ with
$K_{X^{\prime}}=f_{*}K_{X}$ and $K_{X^{\prime}}+\Delta^{\prime}$ nef. If by
contradiction there is a subvariety $V$ in the exceptional locus of $f$ of
codimension at most $k$ in $X$, then there is a $k$-moving curve class $C$
sweeping out $V$ such that $(K_{X}+\Delta).C<0$. Now, since
$K_{X}+\Delta\in\overline{\textrm{Mov}}^{k}(X)$, there exists a sequence of
$\mathbb{R}$-divisors $D_{i}\in\textrm{Mov}^{k}(X)$ converging to
$K_{X}+\Delta$; in particular, we have $D_{i}.C<0$ for any $i$ sufficiently
large. It follows that $V$ is contained in the (stable) base locus of $D_{i}$,
a contradiction.

Next, by the Log Abundance assumption on $(X^{\prime},\Delta^{\prime})$, since
$f_{*}(K_{X}+\Delta)=K_{X^{\prime}}+\Delta^{\prime}$ is nef then it is
semiample, in particular $f_{*}(K_{X}+\Delta)\in\textrm{Mov}^{k}(X^{\prime})$.
Hence we may conclude by invoking the previous claim and applying the
following Lemma to $D:=K_{X}+\Delta$.

######  Lemma 1.

Let $D$ be an effective Cartier divisor on a normal projective variety $X$ and
let $f:X\dashrightarrow X^{\prime}$ be an isomorphism in codimension $k$. If
$f_{*}D\in\textrm{Mov}^{k}(X^{\prime})$, then $D\in\textrm{Mov}^{k}(X)$.

###### Proof.

By contradiction, assume that $D\notin\textrm{Mov}^{k}(X)$, so that there
exists a subvariety $W$ in the stable base locus of $D$ of codimension at most
$k$ in $X$. Since by assumption the exceptional locus of $f$ has codimension
at least $k+1$ in $X$, it follows that $f_{|W}:W\dashrightarrow f(W)$ is
birational, in particular we have $\dim f(W)=\dim W$. We claim that $f(W)$ is
contained in the stable base locus of $f_{*}(D)$. Indeed, we have
$|f_{*}(D)|=f_{*}|D|$ since $f$ is an isomorphism in codimension $k\geq 1$ and
$f(W)$ is contained in every element of $f_{*}|D|$ since $W$ is contained in
every element of $|D|$. From the claim it follows that
$f_{*}D\notin\textrm{Mov}^{k}(X^{\prime})$, a contradiction.

∎

## Acknowledgements

We are grateful to Paolo Cascini and Vladimir Lazić for sharing their
realiable insights on birational geometry with us. The authors are members of
GNSAGA of INdAM (Italy). This project has been developed in April 2024 as a
Research in Pairs program at CIRM, Trento (Italy). The forth author’s research
is funded by the European Union under the Next Generation EU PRIN 2022
_Birational geometry of moduli spaces and special varieties_ , Prot. n.
20223B5S8L.

## References

  * [1] C. Birkar, P. Cascini, C. Hacon, J. McKernan: Existence of minimal models for varieties of log general type. J. Amer. Math. Soc. 23 (2010), 405–468.
  * [2] S. Boucksom, J.-P. Demailly, M. Păun, Th. Peternell: The pseudo-effective cone of a compact Kähler manifold and varieties of negative Kodaira dimension. J. Algebraic Geom. 22 (2013), 201–248.
  * [3] M.C. Brambilla, O. Dumitrescu, E. Postinghel, L. Santana Sanchez: Duality and polyhedrality of cones for Mori dream spaces. ArXiv:2305.18536 (2023).
  * [4] S. R. Choi: Duality of the cones of divisors and curves. Math. Res. Lett. 19 (2012), 403–416.
  * [5] S. Keel, K. Matsuki, J. McKernan: Log abundance theorem for threefolds. Duke Math. J. 75 (1994), 99–119.
  * [6] R. Lazarsfeld: Positivity in algebraic geometry I. Springer-Verlag, Berlin, 2004.
  * [7] V. Lazić, K. Oguiso, Th. Peternell: The Morrison-Kawamata cone conjecture and abundance on Ricci flat manifolds. In: Uniformization, Riemann-Hilbert Correspondence, Calabi-Yau Manifolds & Picard-Fuchs Equations. Adv. Lect. Math. 42, Int. Press, Somerville, MA, 2018, 157–185.
  * [8] V. Lazić and Th. Peternell: On generalised abundance, I. Publ. Res. Inst. Math. Sci. 56 (2020), 353–389.
  * [9] B. Lehmann: The movable cone via intersections. ArXiv:1111.3928 (2012).
  * [10] S. Payne: Stable base loci, movable curves, and small modifications, for toric varieties. Math. Z. 253 (2006), 421–431.


# Temporal Graph ODEs for Irregularly-Sampled Time Series

Alessio Gravina1,, Daniele Zambon2, Davide Bacciu1, Cesare Alippi2,3
1University of Pisa, Pisa, Italy
2The Swiss AI Lab IDSIA, Università della Svizzera italiana, Lugano,
Switzerland
3Politecnico di Milano, Milan, Italy
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author.

###### Abstract

Modern graph representation learning works mostly under the assumption of
dealing with regularly sampled temporal graph snapshots, which is far from
realistic, e.g., social networks and physical systems are characterized by
continuous dynamics and sporadic observations. To address this limitation, we
introduce the Temporal Graph Ordinary Differential Equation (TG-ODE)
framework, which learns both the temporal and spatial dynamics from graph
streams where the intervals between observations are not regularly spaced. We
empirically validate the proposed approach on several graph benchmarks,
showing that TG-ODE can achieve state-of-the-art performance in irregular
graph stream tasks.

##  1 Introduction

Representation learning for graphs has been gaining increasing attention over
recent years. Such popularity often builds on the fact that complex phenomena
are frequently understood as systems of interacting entities described as a
graph. For such a reason, learning on graph-structured data through Deep Graph
Networks (DGNs) Bacciu et al. (2020); Wu et al. (2021) has been adopted for
solving problems in a variety of fields, such as biology, social science, and
sensor networks Gilmer et al. (2017); Zitnik et al. (2018); Monti et al.
(2019); Derrow-Pinion et al. (2021); Gravina et al. (2022); Bacciu et al.
(2024).

Graph-based processing methods turned out to be extremely effective in
processing spatio-temporal data too Li et al. (2018); Wu et al. (2019b); Bai
et al. (2021); Chen et al. (2022); Zambon and Alippi (2022); Marisca et al.
(2022); Jiang and Luo (2022); Errica et al. (2023); Cini et al. (2023a). Such
a scenario is a setting where the temporal modeling accounts for functional
dependencies – assimilated, in a broad sense, as spatial relationships –
existing among the interacting entities. Real-world complex problems described
as temporal graphs, e.g., those associated with social interactions, call for
novel methods that can move beyond the common assumptions found in most of the
methods proposed until now. Indeed, such problems require dealing with mutable
relational information, irregularly and severely under-sampled data.

Some recent works propose to model input-output data relations as a continuous
dynamic described by a learnable ordinary differential equation (ODE), instead
of discrete sequences of layers commonly used in deep learning. Neural ODE-
based approaches have been exploited to model non-temporal data, including
message-passing functions for learning node-level embeddings Poli et al.
(2019); Chamberlain et al. (2021); Eliasof et al. (2021); Rusch et al. (2022);
Gravina et al. (2023). Notably, relying on ODEs has shown promising for
modeling complex temporal patterns from irregularly and sparsely sampled data
Chen et al. (2018); Rubanova et al. (2019); Kidger et al. (2020).

In this paper, we formulate Temporal Graph Ordinary Differential Equation (TG-
ODE), a general continuous-time modeling framework for temporal graphs that
encompasses some methods from the literature as its specific instances, and
demonstrate that TG-ODE can be an effective design choice to operate with
irregularly and sparsely sampled observations. TG-ODE is designed through the
lens of ODEs for effective learning of irregularly sampled temporal graphs.
With TG-ODE, a differential equation is learned directly from data to solve a
downstream task and predictions are trajectories obtained by numerical
integration of the learned ODE.

The key contributions of this work can be summarized as follows:

  1. (i)

we introduce TG-ODE, a general modeling framework suited for handling
irregularly sampled temporal graphs;

  2. (ii)

we introduce new benchmarks of synthetic and real-world scenarios for
evaluating forecasting models on irregularly sampled temporal graphs; and

  3. (iii)

we conduct extensive experiments to demonstrate the benefits of our method and
show that TG-ODE outperforms state-of-the-art DGNs on all benchmarks.

Finally, we stress that, other than the outstanding empirical performance
achieved by even simple TG-ODE instances, the framework allows us to
reinterpret many state-of-the-art DGNs as a discretized solution of an ODE,
thus facilitating their extension to handle graph streams with irregular
sampling.

##  2 Problem statement

We consider a dynamical system of interacting entities $u\in\mathcal{V}$,
which we refer to as _nodes_ , that is described by a Cauchy problem defined
on an ODE of the form

$\frac{d\mathbf{X}(t)}{dt}=F(\mathbf{X}(t),\mathbf{E}(t),\mathbf{z}(t)),$ (1)

with initial condition $\mathbf{X}(0)=\mathbf{X}_{0}$. System state
$\mathbf{X}(t)=\\{\mathbf{x}_{u}(t):u\in\mathcal{V}(t)\\}$ is a function of
time $t$ and collects the node-level states
$\mathbf{x}_{u}(t)\in\mathbb{R}^{d_{x}}$ associated with each node
$u\in\mathcal{V}(t)$. The node set $\mathcal{V}(t)$ is allowed to vary over
time. We denote the dynamic set of edges encoding the node relations as
$\mathcal{E}(t)\subseteq\mathcal{V}(t)\times\mathcal{V}(t)$.
$\mathbf{E}(t)=\\{\mathbf{e}_{uv}(t):(u,v)\in\mathcal{E}\\}$ is a set of edge-
level attributes $\mathbf{e}_{vu}(t)\in\mathbb{R}^{d_{e}}$ defining the type
or strength of the interaction between nodes $u,v\in\mathcal{V}(t)$. The
system can also be driven by vector $\mathbf{z}_{u}(t)\in\mathbb{R}^{c}$
accounting for exogenous variables relevant to the problem at hand, such as
weather conditions, hour of the day, or day of the week. Accordingly, for all
$u\in\mathcal{V}(t)$, we write

$\frac{d\mathbf{x}_{u}(t)}{dt}=F\left(\mathbf{x}_{u}(t),\mathbf{z}_{u}(t),\\{\mathbf{x}_{v}(t)\\}_{v\in\mathcal{N}_{u}(t)},\\{\mathbf{e}_{vu}(t)\\}_{v\in\mathcal{N}_{u}(t)}\right),$
(2)

to emphasize the local dependencies of node state $\mathbf{x}_{u}(t)$ at a
time $t$ from its neighboring nodes
$v\in\mathcal{N}_{u}(t)=\\{v\in\mathcal{V}(t):(v,u)\in\mathcal{E}(t)\\}$ at
the corresponding time.

We express any solution of ODE (1) as the temporal graph

$\mathcal{G}(t)=\left(\mathcal{V}(t),\mathcal{E}(t),\mathbf{X}(t),\mathbf{E}(t)\right)$
(3)

defined for $t\geq 0$. However, we assume to observe system (1) only as a
(discrete) sequence of snapshot graphs

$\mathcal{G}=\\{\mathcal{G}_{t_{i}}:i=0,1,2,\dots,T\\}$ (4)

that arrive at irregular timestamps, i.e., the sampling is not uniform and, in
general, $t_{i}-t_{i-1}\neq t_{i+1}-t_{i}$. Each snapshot
$\mathcal{G}_{t}=(\mathcal{V}_{t},\mathcal{E}_{t},\overline{\mathbf{X}}_{t},\mathbf{E}_{t})$
corresponds to an observation of the system state at a specific timestamp
$t\in\mathbb{R}$. Edge set $\mathcal{E}_{t}$ contains the functional relations
between the nodes $u,v\in\mathcal{V}_{t}$ at time $t$ (thus, $\mathcal{E}_{t}$
can vary over time), while
$\overline{\mathbf{X}}_{t}=\\{\overline{\mathbf{x}}_{t,v}:v\in\mathcal{V}_{t}\\}$
gathers the observed node states, with $\overline{\mathbf{x}}_{t,v}$ the state
of node $v$ associated to the observed graph snapshot at time $t$. Edge
attributes, if present, are denoted as $\mathrm{e}_{u,v}\in\mathbf{E}_{t}$.
Figure 1 visually summarizes this concept.

Figure 1: An example of a non-uniform sampling of a temporal graph with
snapshots over a set of 5 nodes.

In this paper, we address the problem of learning a model of the differential
equation underlying the observed data, which is subsequently exploited to
provide estimates of unobserved system’s node states and make forecasts. To
ease readability, in the following we drop the time variable $t$.

##  3 Temporal Graph Ordinary Differential Equation

To learn the function $F$ in (2), we consider a family of models

$f_{\theta}(\mathbf{x}_{u},\mathbf{z},\\{\mathbf{x}_{v}\\}_{v\in\mathcal{N}_{u}},\\{\mathbf{e}_{vu}\\}_{v\in\mathcal{N}_{u}})$
(5)

parameterized by vector $\theta$, and optimized so that the solution
$\hat{\mathbf{x}}$ of the differential equation

$\frac{d\mathbf{x}_{u}}{dt}=f_{\theta}\left(\mathbf{x}_{u},\mathbf{z}_{u},\\{\mathbf{x}_{v}\\}_{v\in\mathcal{N}_{u}},\\{\mathbf{e}_{vu}\\}_{v\in\mathcal{N}_{u}}\right),\quad\forall
u\in\mathcal{V}$ (6)

minimizes the discrepancy with the observed sequence of graphs in (4). We
follow the message-passing paradigm Gilmer et al. (2017) and instantiate (6)
as

$\frac{d\mathbf{x}_{u}}{dt}=\phi_{U}\left(\mathbf{x}_{u},\mathbf{z}_{u},\rho\left(\\{\phi_{M}(\mathbf{x}_{u},\mathbf{x}_{v},\mathbf{e}_{vu})\\}_{v\in\mathcal{N}_{u}}\right)\right),$
(7)

with message function $\phi_{M}$, aggregation operator $\rho$ (e.g., the
mean), and update function $\phi_{U}$. Note that functions
$\phi_{U},\phi_{M},$ and $\rho$ have learnable parameters $\theta$, which are
shared across all nodes and time steps. An example of a message passing
operator is when
$\phi_{M}(\mathbf{x}_{u},\mathbf{x}_{v},\mathbf{e}_{vu})=\mathbf{x}_{v}$,
$\rho$ is the mean, and $\phi_{U}$ is a dense feed-forward network of its
inputs. We refer to the above framework in (7) as Temporal Graph Ordinary
Differential Equation (TG-ODE).

We observe that, since our framework relies on ODEs, it can naturally deal
with snapshots that arrive at an arbitrary time. Indeed, the original Cauchy
problem can be divided into multiple sub-problems, one per snapshot in the
temporal graph. Here, the $i$-th sub-problem is defined for all
$u\in\mathcal{V}_{t}$ as

$\begin{cases}\frac{d\mathbf{x}_{u}}{dt}=\phi_{U}\left(\mathbf{x}_{u},\mathbf{z}_{u},\rho\left(\\{\phi_{M}(\mathbf{x}_{u},\mathbf{x}_{v},\mathbf{e}_{vu})\\}_{v\in\mathcal{N}_{u}}\right)\right),\\\
\mathbf{x}_{u}(0)=\psi(\overline{\mathbf{x}}_{t_{i-1},u},\hat{\mathbf{x}}_{u}(t_{i-1}))\end{cases}$
(8)

in the time span between the two consecutive timestamps, i.e.,
$t\in[t_{i-1},t_{i}]$, where $\psi$ is a function that combines the $i$-th
observed state of the node $u$ related to the snapshot graph
$\mathcal{G}_{t_{i-1}}$ in (4) (i.e., $\overline{\mathbf{x}}_{t_{i-1},u}$) and
the prediction $\hat{\mathbf{x}}_{u}(t_{i-1})$ obtained by solving (8) at the
previous step. When given, we consider the true – potentially variable –
topology $\mathcal{E}(t)$ to define the neighborhoods for
$t\in[t_{i-1},t_{i}]$, otherwise, we set
$\mathcal{E}(t)\equiv\mathcal{E}_{t_{i-1}}$ for every $t$, i.e., equal to the
last observed topology associated with $\mathcal{G}_{t_{i-1}}$. Accordingly,
we optimize $\theta$ in order to minimize the mean of some loss $\mathcal{L}$,

$\frac{1}{T}\sum_{i=1}^{T}\frac{1}{|\mathcal{V}_{t_{i}}|}\sum_{u\in\mathcal{V}_{t_{i}}}\mathcal{L}(\overline{\mathbf{x}}_{t_{i},u},\hat{\mathbf{x}}_{u}(t_{i}))$
(9)

where prediction $\hat{\mathbf{x}}_{u}(t_{i})$ at time $t_{i}$ is obtained by
solving (8).

Figure 2: The continuous processing of node $u$’s state in a discrete-time
dynamic graph with irregularly-sampled snapshots over a set of 4 nodes and
fixed edge set. At the top, the node-wise ODE function $f_{\mathcal{\theta}}$
defines the evolution of the states $\mathbf{x}_{u}(t)$. At the bottom, the
discretized solution of the node-wise ODE, which corresponds to our framework
TG-ODE. The node embedding $\mathbf{x}_{u}^{\ell}$ is computed iteratively
over a discrete set of points by leveraging the temporal neighborhood and
self-representation at the previous step.

We observe that for most ODEs it is not possible to compute analytical
solutions. For such a reason, it is common practice to resort to numerical
approximations that leverage discretization strategies (e.g., forward Euler’s
method). In this case, the solution is computed through iterative applications
of the method over a discrete set of points in the time interval and, as
observed in Chen et al. (2018); Haber and Ruthotto (2017), the process can be
assimilated to that of a Recurrent Neural Network (RNN). For simplicity, here
we employ the forward Euler’s method according to which a solution to (8) is
obtained by the recursion

$\mathbf{x}_{u}^{\ell+1}=\mathbf{x}_{u}^{\ell}+\epsilon\phi_{U}\left(\mathbf{x}_{u}^{\ell},\mathbf{z}_{u}(t_{\ell}),\rho\left(\\{\phi_{M}(\mathbf{x}_{u}^{\ell},\mathbf{x}_{v}^{\ell},\mathbf{e}_{vu}^{\ell})\\}_{v\in\mathcal{N}_{u}(t_{\ell})}\right)\right),$
(10)

starting from initial condition
$\mathbf{x}_{u}^{0}=\mathbf{x}_{u}(0)=\psi(\overline{\mathbf{x}}_{t_{i-1},u},\hat{\mathbf{x}}_{u}(t_{i-1}))$
and is reiterated until $\epsilon\ell\geq t_{i}-t_{i-1}$. In (10),
$\epsilon\ll t_{i}-t_{i-i}$ is the step size, while $\ell$ indicates the
generic iteration step, and $t_{\ell}=t_{i-1}+\epsilon\ell$. Finally, a
solution $\hat{\mathbf{x}}(t)$ to (8) in the interval $[t_{i-1},t_{i}]$ is
provided by the discretization
$\hat{\mathbf{x}}_{u}(t_{i-1}+\epsilon\ell)=\mathbf{x}_{u}^{\ell}$, for all
$\ell$, and interpolated elsewhere. The process is visually summarized at the
bottom of Figure 2.

We acknowledge that not all resulting ODEs allow unique solutions and yield
numerical stable problems. Generally, numerical stability is associated with
the ODE to solve rather than the input data. Thus, a proper design of the
considered family of ODEs in (7) can prevent stability issues. Indeed, the
solution of a Cauchy problem exists and is unique if the differential equation
is uniformly Lipschitz continuous in its input and continuous in $t$, as
states in the Picard–Lindelöf theorem Coddington and Levinson (1955). Thus,
different implementations of (7) should address the continuous behavior of the
differential equation. We note that this theorem holds for our model if the
underlying neural network has finite weights and uses Lipshitz non-
linearities, e.g., the tanh.

By (10) and the generality of the message passing in (7), we observe that TG-
ODE allows us to cast basically any standard DGN through the lens of an ODE
for temporal graphs with irregular timestamps. Secondly, we stress that, even
though TG-ODE is solved here by means of the forward Euler’s method, other
discretization methods can still be utilized. To conclude, our framework can
be implemented using the aggregation function that is most suitable for the
given task and the discretization method that best fits the computational
resources and problem at hand, such as Veličković et al. (2018); Hu et al.
(2020); Choi et al. (2023); Eliasof et al. (2024a). As a demonstration of
this, in Section 5 we explore the neighborhood aggregation scheme proposed in
Du et al. (2017). Thus, (7) can be reformulated as

$\frac{d\mathbf{x}_{u}}{dt}=\sigma\left(\sum_{k=0}^{K}\,\,\sum_{v\in\mathcal{N}_{u}^{k}\cup\\{u\\}}\alpha_{u,v}^{(k)}\,{\mathbf{x}_{v}\theta_{k}}\right),$
(11)

where $\sigma$ is an activation function, $K$ is the number of hops in the
neighborhood, $\theta_{k}$ is the $k$-th weight matrix, $\mathcal{N}_{u}^{k}$
is the $k$-hop neighborhood of $u$, and $\alpha_{u,v}^{(k)}$ is a
normalization term. For instance,
$\alpha_{u,v}^{(k)}=\left(\hat{d}_{v}^{(k)}\hat{d}_{u}^{(k)}\right)^{-1/2}$
weighs according to the degrees $\hat{d}_{v}^{(k)}$ and $\hat{d}_{u}^{(k)}$ of
nodes $v$ and $u$ in the $k$-hop graph; other choices can include edge
attributes as well. We note that $\theta_{k}$ is a parameter specific to the
$k$-hop neighborhood of node $u$. Thus, it allows the model to learn different
transformation patterns at different distances from the considered node $u$.

##  4 Related work

##### Deep Graph Networks for static graphs

In the static graph domain, most DGNs can be generalized by the concepts
introduced by MPNN Gilmer et al. (2017), which is designed to capture and
propagate information between nodes in a graph through a message-passing
mechanism. Thus, each node updates its state by exchanging information with
its neighboring nodes. MPNN can be formulated as

$\mathbf{x}_{u}^{\ell}=\phi_{U}\left(\mathbf{x}_{u}^{\ell-1},\sum_{j\in\mathcal{N}_{u}}\phi_{M}\left(\mathbf{x}_{u}^{\ell-1},\mathbf{x}_{v}^{\ell-1},\mathbf{e}_{uv}\right)\right)$
(12)

where $\phi_{U}$ and $\phi_{M}$ are respectively the update and message
functions, which are responsible for computing neighbor states and updating
the node’s state accordingly. Most of the state-of-the-art DGNs can be derived
by (12). Indeed, the definition of the message and update function allows
implementing DGNs with different properties Kipf and Welling (2017);
Veličković et al. (2018); Hamilton et al. (2017); Xu et al. (2019); Defferrard
et al. (2016); Hu et al. (2020); Du et al. (2017).

We can extend the abovementioned DGNs to the domain of temporal graphs by
selecting appropriate operators in (7) and, in turn, it allows us to tailor
the TG-ODE to exploit relational inductive biases and fulfill given
application requirements. For instance, by considering a graph attentional
operator Veličković et al. (2018) in (7), we can implement an anisotropic
message passing within the temporal graph during the update of node states.

##### Deep Graph Networks for temporal graphs

Given the sequential structure of temporal graphs, a natural choice for many
methods has been to extend Recurrent Neural Networks to graph data. Indeed,
most of the models presented in the literature can be summarized as a
combination of DGNs and RNNs.

Some approaches adopt a stacked architecture, where DGNs and RNNs are used
sequentially Seo et al. (2018); Pareja et al. (2020), enabling to separately
model spatial and temporal dynamics. Other approaches integrate the DGN inside
the RNN Li et al. (2019); Chen et al. (2022); Seo et al. (2018); Li et al.
(2018); Zhao et al. (2020); Bai et al. (2021), allowing to jointly capture the
temporal evolution and the spatial dependencies in the graph. We refer to Cini
et al. (2023b) and Gravina and Bacciu (2024) for a deeper discussion.

Differently from these approaches, which are intrinsically designed to deal
with regular time series, TG-ODE can naturally handle arbitrary time gaps
between observations. This makes our framework more suitable for realistic
scenarios, in which data are irregular over time.

##### Continuous Dynamic Models

NeuralODE (NODE) Chen et al. (2018) has emerged as an effective class of
neural network models suitable for learning systems’ continuous dynamics,
drawing a connection between RNNs and ODEs. Despite the similarity with RNNs,
such architectures can deal with irregular time series since the continuously-
defined dynamics can naturally incorporate data that arrive at arbitrary times
Chen et al. (2018); Rubanova et al. (2019).

Inspired by the NODE approach, GDE Poli et al. (2019) links DGNs for static
graphs with ODEs. In the static graph domain, ODE-based architectures have
been proposed with different aims, such as preserving long-range dependencies
Gravina et al. (2023), reducing the computational complexity of message
passing Wang et al. (2021); Wu et al. (2019a), and mitigating the over-
smoothing phenomena Eliasof et al. (2021); Rusch et al. (2022); Kang et al.
(2024).

In the temporal domain, TDE-GNN Eliasof et al. (2024b) employs higher-order
ODEs to capture the temporal graph dynamic, while NDCN Zang and Wang (2020)
extends GDE to learn continuous-time dynamics on both static and temporal
graphs by diffusing input features until the termination time. MTGODE Jin et
al. (2022) adopts an ODE-based approach to deduce missing graph topologies
from the time-evolving node features in regularly sampled temporal graphs.
Differently, Huang et al. (2020) and Huang et al. (2021) propose an ODE-based
model in the form of a variational auto-encoder for learning latent dynamics
from sampled initial states. To infer missing observations, the methods
consider both past and future neighbors’ information. This prevents them from
being used in an online setting, where data becomes available in a sequential
order. Lastly, STG-NCDE Choi et al. (2022) employs a stacked architecture of
two neural controlled differential equations to model temporal and spatial
information, respectively. In the STG-NCDE’s paper, irregular data are
considered, yet they are handled by making them regular via interpolation.

In contrast to these approaches, in this paper we explicitly address
irregularly-sampled temporal graphs and we propose a simple model to showcase
the effectiveness and efficiency of the TG-ODE framework in working with such
data, eliminating the need for additional strategies, such as interpolation.
It should be noted that while many of the ODE-based approaches mentioned
earlier can be viewed as instances of the introduced TG-ODE framework, our
model is specifically designed to demonstrate the benefits of this approach.

##  5 Experiments

We provide an empirical assessment of our method against related temporal DGN
models from the literature111We release the code implementing our methodology
and reproducing our empirical analysis at https://github.com/gravins/TG-ODE..
First, we test the efficacy in handling dynamic graphs with irregularly
sampled time series by evaluating the models on several heat diffusion
scenarios (see Section 5.1). Afterward, we assess and discuss the performance
on real graph benchmarks on traffic forecasting problems (see Section 5.2). We
report in Table 1 the grid of hyper-parameters employed in our experiments by
each method. We carried out the experiments on 7 nodes of a cluster with 96
CPUs per node.

Table 1: The grid of hyper-parameters employed during model selection for the heat diffusion tasks (_Heat_) and graph benchmark tasks (_Bench_). The $\epsilon$ hyper-parameter is only used by our method (i.e., TG-ODE), and embedding dim equal to None means that no encoder and readout are employed. Hyper-parameters | Values
---|---
_Heat_ | _Bench_
Learning rate |  $10^{-2}$, $10^{-3}$, $10^{-4}$
Weight decay |  $10^{-2}$, $10^{-3}$
$\psi$ |  concat, sum, $\psi(\overline{\mathbf{x}},\hat{\mathbf{x}})=\overline{\mathbf{x}}$
Activation fun. | tanh, relu, identity
Embedding dim. | None, 8 | 64, 32
$\epsilon$ | $10^{-3}$ | 1, 0.5, $10^{-1}$, $10^{-2}$, $10^{-3}$
# hops | 5 | 1, 2, 5

###  5.1 Heat diffusion

In this section, we focus on simulating the heat diffusion over time on a
graph. The data is composed of irregularly sampled graph snapshots providing
the temperature of the graph’s nodes at the given timestamp. We address the
task of predicting the nodes’ temperature at future (irregular) timestamps.

####  5.1.1 Datasets

In our experiment, we consider a grid graph consisting of 70 nodes, each of
which is characterized by an initial temperature $\mathbf{x}_{u}(0)$ randomly
sampled in the range between $0$ and $0.2$. We randomly alter the initial
temperature profile by generating hot and cold spikes located at some nodes. A
hot spike is characterized by a temperature between $10$ and $15$, while a
cold spike is between $-15$ and $-10$. Each altered node has a 40% chance of
being associated with a cold spike and 60% with a hot spike. We considered two
different experimental scenarios depending on the number of altered nodes. In
the first scenario, we alter the temperature of a single node. In the second
one, we alter the temperature of one third of the graph’s nodes. We will refer
to these settings as single-spike and multi-spikes, respectively.

We collected the ground truth by simulating the heat diffusion equation
through the forward Euler’s method with step size $\epsilon=10^{-3}$. Figure 3
illustrates two snapshot graphs from the simulated heat diffusion.

(a)

(b)

Figure 3: (a) A grid graph consisting of 70 nodes in which each node is
characterized by an initial temperature. Darker colors correspond to colder
temperatures, while brighter colors mean warmer temperatures. (b) The heat
diffusion simulation is computed through 1000 steps forward Euler’s method
leveraging $-\mathbf{L}\mathbf{X}(t)$ as diffusion.

The training set consists of 100 randomly selected timestamps over the 1000
steps used to simulate the diffusion process. The validation and test sets are
generated from two different simulations similar to the one used for building
the training set. However, validation and test sets are obtained through
500-step simulations, and only 50 of them are kept as validation/test sets. We
simulated seven different diffusion functions, i.e.,
$-\mathbf{L}\mathbf{X}(t)$, $-\mathbf{L}^{2}\mathbf{X}(t)$,
$-\mathbf{L}^{5}\mathbf{X}(t)$, $-\tanh(\mathbf{L})\mathbf{X}(t)$,
$-5\mathbf{L}\mathbf{X}(t)$, $-0.05\mathbf{L}\mathbf{X}(t)$, and
$-(\mathbf{L}+\mathcal{N}_{0,1})\mathbf{X}(t)$. Here, $\mathcal{N}_{0,1}$
stands for a noise sampled from a standard normal distribution, and
$\mathbf{L}$ is the normalized graph Laplacian.

####  5.1.2 TG-ODE and baseline models

We explored the performance of TG-ODE leveraging the aggregation scheme in Du
et al. (2017) and the forward Euler’s method as discretization procedure, for
simplicity. Thus, the nodes’ states for the entire snapshot are updated as

$\mathbf{X}^{\ell}=\mathbf{X}^{\ell-1}+\epsilon\sigma\left(\sum_{k=0}^{K}\mathbf{L}^{k}\mathbf{X}^{\ell-1}\theta_{k}\right),$
(13)

where $K$ corresponds to the number of neighborhood hops and $\theta_{k}$ is
the $k$-th weight matrix. We recall that other choices of aggregation and
discretization schemes are possible. We compared our method with six common
DGNs for dynamic graphs: A3TGCN Bai et al. (2021), DCRNN Li et al. (2018),
TGCN Zhao et al. (2020), GCRN-GRU Seo et al. (2018), GCRN-LSTM Seo et al.
(2018), and NDCN Zang and Wang (2020). We note that whenever we used the NDCN
model with embedding dimension set to none (see Table 1), the resulting model
corresponds to DNND Liu et al. (2023).

Moreover, we considered two additional baselines: NODE Chen et al. (2018) and
LB-baseline. NODE represents an instance of our approach that does not take
into account node interactions. Instead, LB-baseline returns the same node
states received as input (i.e., , the prediction of
$\overline{\mathbf{X}}_{t_{i+1}}$ is
$\hat{\mathbf{X}}(t_{i+1})=\overline{\mathbf{X}}_{t_{i}}$) and provides a
lower bound on the performance we should expect from the learned models.

We designed each model as a combination of three main components. The first is
the encoder which maps the node input features into a latent hidden space; the
second is the temporal graph convolution (i.e., TG-ODE or the DGN baselines)
or the NODE baseline; and the third is a readout that maps the output of the
convolution into the output space. The encoder and the readout are Multi-Layer
Perceptrons that share the same architecture among all models in the
experiments.

To allow all considered baseline models to handle irregular timestamps, we
used a similar strategy employed for TG-ODE. Specifically, we selected the
unit of time, $\tau$, and then we iteratively applied the temporal graph
convolution for a number of steps equal to the ratio between the time
difference between two consecutive timestamps and the time unit, i.e.,
$\\#steps=(t_{i+1}-t_{i})/\tau$.

We performed hyper-parameter tuning via grid search, optimizing the Mean
Absolute Error (MAE). We trained the models using the Adam optimizer for a
maximum of 3000 epochs and early stopping with patience of 100 epochs on the
validation error.

####  5.1.3 Results

We present the results on the heat diffusion tasks in Table 2 and Table 3,
using the $log_{10}(\mathrm{MAE})$ as performance metric in both the single-
spike and multi-spikes scenarios. The first observation is that TG-ODE has
outstanding performance compared to literature models and the baseline.
Despite its simpler architecture, our method produces an error that is
significantly lower than the runner-up in each task. In the single-spike
setting, TG-ODE achieves a $log_{10}(\mathrm{MAE})$ that is on average 308% to
628% better than the competing models in each task.

Table 2: Test $log_{10}(\mathrm{MAE})$ score and std in the single-spike heat
diffusion experiments, averaged over 5 separate runs.

$-\mathbf{L}\mathbf{X}(t)$ $-\mathbf{L}^{2}\mathbf{X}(t)$
$-\mathbf{L}^{5}\mathbf{X}(t)$ $-\tanh(\mathbf{L})\mathbf{X}$
$-5\mathbf{L}\mathbf{X}(t)$ $-0.05\mathbf{L}\mathbf{X}(t)$
$-(\mathbf{L}+\mathcal{N}_{0,1})\mathbf{X}(t)$ LB-baseline -0.557 -0.572
-0.562 -0.538 -0.337 -0.565 -0.837 NODE -2.828±0.063 -2.657±0.053 -2.139±0.005
-2.711±0.136 -2.313±0.016 -3.983±0.003 -2.059±0.005 A3TGCN -0.834±0.145
-0.902±0.093 -0.819±0.036 -0.890±0.035 -1.084±0.004 -0.653±0.001 -0.781±0.094
DCRNN -1.320±0.163 -0.913±0.242 -0.867±0.305 -1.273±0.075 -1.098±0.154
-0.964±0.366 -1.150±0.375 GCRN-GRU -0.474±0.232 -0.633±0.004 -0.464±0.064
-0.621±0.047 -0.695±0.002 -0.640±0.019 -0.490±0.094 GCRN-LSTM -0.430±0.140
-0.323±0.019 -0.405±0.053 -0.351±0.097 -0.511±0.157 -0.428±0.140 -0.367±0.790
NDCN -1.497±0.034 -1.337±0.070 -0.350±0.328 -1.485±0.075 -1.097±0.046
-2.408±0.183 -0.414±0.155 TGCN -0.825±0.108 -0.900±0.143 -0.804±0.074
-0.834±0.149 -1.051±0.020 -0.653±0.001 -0.781±0.094 Ours -4.087±0.171
-3.106±0.181 -2.265±0.053 -4.166±0.140 -2.351±0.036 -4.811±0.198 -2.069±0.001

Table 3: Test $log_{10}(\mathrm{MAE})$ score and std in the multi-spikes heat
diffusion experiments, averaged over 5 separate runs.

$-\mathbf{L}\mathbf{X}(t)$ $-\mathbf{L}^{2}\mathbf{X}(t)$
$-\mathbf{L}^{5}\mathbf{X}(t)$ $-\tanh(\mathbf{L})\mathbf{X}(t)$
$-5\mathbf{L}\mathbf{X}(t)$ $-0.05\mathbf{L}\mathbf{X}(t)$
$-(\mathbf{L}+\mathcal{N}_{0,1})\mathbf{X}(t)$ LB-baseline 0.490 0.517 0.552
0.523 0.256 0.561 0.666 NODE -1.708±0.016 -1.426±0.021 -1.093±0.004
-1.671±0.006 -1.198±0.016 -2.749±0.016 -0.979±0.047 A3TGCN 0.443±0.087
0.244±0.124 0.174±0.071 0.509±0.058 0.187±0.010 0.628±0.023 0.328±0.060 DCRNN
-0.140±0.092 -0.143±0.111 -0.123±0.132 -0.122±0.120 -0.421±0.227 -0.002±0.125
-0.212±0.333 GCRN-GRU 0.586±0.003 0.614±0.004 0.639±0.002 0.610±0.002
0.440±0.003 0.629±0.001 0.719±0.003 GCRN-LSTM 0.584±0.001 0.610±0.002
0.637±0.002 0.612±0.003 0.440±0.005 0.631±0.002 0.705±0.002 NDCN 0.120±0.325
-0.070±0.056 0.315±0.245 -0.128±0.020 0.146±0.107 -1.357±0.053 0.384±0.013
TGCN 0.404±0.236 0.313±0.072 0.113±0.071 0.493±0.056 0.113±0.086 0.615±0.023
0.364±0.134 Ours -4.259±0.037 -3.705±0.143 -1.314±0.249 -3.572±0.010
-2.350±0.083 -4.567±0.109 -1.021±0.002

Interestingly, not all DGN-based models are capable of improving the results
of the LB-baseline. This situation suggests that such approaches attempt to
merely learn the mapping function between inputs and outputs rather than
learning the actual latent dynamics of the system. Such behavior becomes more
evident in the more complex multi-spike scenario. Here, our method achieves up
to almost 2080% better $log_{10}(\mathrm{MAE})$ score and more literature
models fail in improving the performance with respect to the LB-baseline.
These results indicate that capturing the latent dynamics is fundamental, in
particular, when the time intervals between observations are not regular over
time. We conclude that such methods from the literature might not be suitable
for more realistic settings characterized by continuous dynamics and sporadic
observations.

Finally, we observe that GCRN-GRU and GCRN-LSTM generate the highest error
levels, while DCRNN, NDCN, and NODE are the best among the baselines. Since
literature models use RNN architectures to learn temporal patterns, it is
reasonable to assume that the poor performance might be due to the limited
capacity of RNNs to handle non-uniform time gaps between observations. In
contrast, ODE-based models (NODE, NCDN and ours) demonstrate enhanced learning
capabilities in this scenario. The performance gap between our model and the
considered baselines is an indication that the diverse spatial patterns
learned by different DGN architectures can heavily impact the performance of
the performed tasks.

###  5.2 Graph Benchmarks

This section introduces a set of graph benchmarks whose objective is to assess
traffic forecasting performance from irregular time series; similar to the
heat diffusion tasks, we predict the future node values given only the past
history.

####  5.2.1 Datasets

We considered six real-world graph benchmarks for traffic forecasting: MetrLA
Li et al. (2018), Montevideo Rozemberczki et al. (2021), PeMS03 Guo et al.
(2022), PeMS04 Guo et al. (2022), PeMS07 Guo et al. (2022), and PeMS08 Guo et
al. (2022); we report additional details about the datasets in Table 4. We
used a modified version of the original datasets where we employed irregularly
sampled observations. We will refer to the datasets by using the subscript “i”
– e.g., MetrLAi – to make apparent the difference from the original versions.

We generated irregular time series by randomly selecting a third of the
original graph snapshots for most of the experiments; ratios from 3% to 94%
are studied in Figure 5. We considered a temporal data splitting in which 80%
of the previously selected snapshots are used as training set, 10% as
validation set, and the remaining as test set.

Table 4: Statistics of the original version of the datasets. | # Steps | # Nodes | # Edges | Timespan
---|---|---|---|---
MetrLA | 34,272 | 207 | 1,515 | 01/03 - 30/06 2012
Montevideo | 739 | 675 | 690 | 01/10 - 31/10 2020
PeMS03 | 26,208 | 358 | 442 | 01/09 - 30/11 2018
PeMS04 | 16,992 | 307 | 209 | 01/01 - 28/02 2018
PeMS07 | 28,225 | 883 | 790 | 01/05 - 31/08 2017
PeMS08 | 17,856 | 170 | 137 | 01/07 - 31/08 2016
Table 5: Test $\mathrm{MAE}$ score and std in the traffic forecasting setting, averaged over 5 separate runs. $\dagger$ means gradient explosion. | MetrLAi | Montevideoi | PeMS03i | PeMS04i | PeMS07i | PeMS08i
---|---|---|---|---|---|---
LB-baseline | 58.191 | 0.442 | 165.015 | 211.230 | 314.710 | 227.380
A3TGCN |  5.731±0.011 |  0.378${}_{\pm 4\cdot 10^{-4}}$ |  28.897±0.733 |  32.221±1.355 |  38.303±0.795 |  30.652±0.995
DCRNN | $\dagger$ |  0.332±0.001 |  18.652±0.136 | $\dagger$ | $\dagger$ | $\dagger$
GCRN-GRU |  8.438±0.004 |  0.332±0.001 |  49.360±18.619 |  53.389±4.728 |  68.785±5.787 |  51.787±10.872
GCRN-LSTM |  8.440±0.009 |  0.333±0.002 |  62.210±0.923 |  52.427±4.162 |  151.824±17.654 |  80.567±24.891
NDCN |  8.471±0.022 |  0.435±0.021 | $\dagger$ |  127.202±0.334 | $\dagger$ |  129.667±44.385
TGCN |  5.832±0.125 |  0.380${}_{\pm 4\cdot 10^{-4}}$ |  28.506±0.332 |  33.059±1.063 |  38.750±1.429 |  33.114±1.963
Ours | 2.828±0.001 | 0.327${}_{\pm 6\cdot 10^{-5}}$ | 17.423±0.012 | 24.739±0.014 | 26.081±0.004 | 18.818±0.021

####  5.2.2 TG-ODE and baseline models

For these experiments, we considered the same models, baseline and
architectural choices of the heat diffusion experiments. Since NODE does not
take into account interactions between nodes for its predictions, we choose
not to include it as a baseline in this scenario. Hyper-parameter tuning has
been performed by grid search, optimizing the MAE. Optimizer settings are the
same as for the previous experiments.

####  5.2.3 Results

Table 5 reports the traffic forecasting results in terms of $\mathrm{MAE}$.
Similarly to the heat diffusion scenario, TG-ODE shows a remarkable
performance improvement compared to literature models, achieving an MAE that
is up to 202% better than the runner-up model. Moreover, as reported in Figure
4, we observe that TG-ODE is $2\times$ to $13\times$ faster than the other
approaches under test. NDCN is the sole method matching the speed of our
approach. However, it’s noteworthy that NDCN utilizes only one neighbor hop,
thereby simplifying the final computation.

Figure 4: Average time per epoch (measured in seconds) and std computed using
an Intel Xeon Gold 6240R CPU @ 2.40GHz. Each time is obtained using 5 neighbor
hops (when possible) and embedding dimension equal to 64. The graph size is
computed as $size=\\#steps*\\#edges$.

We observe that the baseline performs poorly in these benchmarks, suggesting
that such tasks are more complex than the ones based on heat diffusion.
Despite all DGN models outperforming the LB-baseline, they still produce an
error that is on average double than that of TG-ODE, highlighting the added
value of our approach when dealing with temporal graphs characterized by
irregular sampling.

Finally, we comment that the DCRNN and NDCN suffered from gradient issues in
most of the tasks. We believe this is due to their inability to learn the
latent dynamics of the system when the models’ outputs are not computed over a
regular time series.

####  5.2.4 Impact of the sample sparsity

To demonstrate the effectiveness of our approach, we study the prediction
performance under different sparsity levels. We consider here the PeMS04
dataset. In this analysis, we systematically decreased the number of
considered graph snapshots in the time series. This reduction makes the
resulting task more challenging than the original one, as the snapshots become
more sparse over time – the expected difference $t_{i+1}-t_{i}$ gets larger.
Additionally, the model has fewer data to learn the task, thereby amplifying
the task complexity. We generated the irregular time series by randomly
selecting 500, 1000, 2000, 4000, 8000, or 16000 graph snapshots from the
original dataset (from 3% to 94% of the original data), resulting in varying
degrees of sparsity. For each dataset size, we used an 80/10/10 temporal data
split and performed hyper-parameter tuning, as previously done in this
section.

Figure 5: Test $\mathrm{MAE}$ scores and std of TG-ODE on PeMS04, averaged
over 5 runs, for different sparsity levels.

Figure 5 illustrates the performance of our method, TG-ODE, at various degrees
of data sparsity. As expected, we observe that as the number of samples
increases, the test MAE decreases. Notably, TG-ODE maintains robust
performance even with higher degrees of sparsity, with a decrease in
performance by only $\sim$7 points when reducing the size from 16000 to 4000
samples. While the prediction error is indeed relatively large when
considering only 3-7% of the original data, we comment that it is still
substantially better than that of the LB-baseline and comparable to that of
the other DGN’s which used 33% of the data. Overall, the model exhibits
excellent performance even in situations of high to extreme sparsity (i.e.,
less than 8000 samples). The observed outcome supports the effectiveness of
TG-ODE, emphasizing its potential for real-world applications with irregularly
sampled temporal graphs.

##  6 Conclusions

We have presented Temporal Graph Ordinary Differential Equation (TG-ODE), a
new general framework for effectively learning from irregularly sampled
temporal graphs. Thanks to the connection between ODEs and neural
architectures, TG-ODE can naturally handle arbitrary time gaps between
observations, allowing to address a common limitation of DGNs for temporal
graphs, i.e., the restriction to work solely on regularly sampled data.

To demonstrate the benefits of our approach, we conducted extensive
experiments on ad-hoc benchmarks that include several synthetic and real-world
scenarios. The results of our experimental analysis show that our method
outperforms state-of-the-art models for temporal graphs by a large margin.
Furthermore, our method benefits from a faster training, thus suggesting
scalability to large networks.

Despite being appealing for many realistic application setups, we acknowledge
that not all resulting ODEs allow unique solutions and yield numerical
stability problems, thus requiring some additional care from the user.

Looking ahead to future developments, we intend to broaden the investigation
of more sophisticated numerical methods to solve the learned temporal graph
ODE, e.g., using adaptive multistep schemes Ascher and Petzold (1998).
Extending the proposed framework to the problem of reconstructing missing data
is another interesting research direction to consider.

## Acknowledgments

This work has been supported by EU-EIC EMERGE (Grant No. 101070918), by the EU
NextGenerationEU programme under the funding schemes PNRR-PE-AI (PE00000013)
FAIR - Future Artificial Intelligence Research, and by the Swiss National
Science Foundation project HORD-GNN (FNS 204061).

## References

  * Ascher and Petzold [1998] Uri M. Ascher and Linda R. Petzold.  Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations.  Society for Industrial and Applied Mathematics, USA, 1st edition, 1998\.
  * Bacciu et al. [2020] Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda.  A gentle introduction to deep learning for graphs.  Neural Networks, 129:203–221, 2020.
  * Bacciu et al. [2024] Davide Bacciu, Federico Errica, Alessio Gravina, Lorenzo Madeddu, Marco Podda, and Giovanni Stilo.  Deep Graph Networks for Drug Repurposing With Multi-Protein Targets.  IEEE Transactions on Emerging Topics in Computing, 12(1):177–189, 2024.
  * Bai et al. [2021] Jiandong Bai, Jiawei Zhu, Yujiao Song, Ling Zhao, Zhixiang Hou, Ronghua Du, and Haifeng Li.  A3T-GCN: Attention Temporal Graph Convolutional Network for Traffic Forecasting.  ISPRS International Journal of Geo-Information, 10(7), 2021.
  * Chamberlain et al. [2021] Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi.  GRAND: Graph neural diffusion.  In International Conference on Machine Learning, pages 1407–1418. PMLR, 2021.
  * Chen et al. [2018] Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud.  Neural ordinary differential equations.  In Advances in neural information processing systems, 2018.
  * Chen et al. [2022] Jinyin Chen, Xueke Wang, and Xuanheng Xu.  GC-LSTM: graph convolution embedded LSTM for dynamic network link prediction.  Applied Intelligence, 52(7):7513–7528, May 2022.
  * Choi et al. [2022] Jeongwhan Choi, Hwangyong Choi, Jeehyun Hwang, and Noseong Park.  Graph Neural Controlled Differential Equations for Traffic Forecasting.  Proceedings of the AAAI Conference on Artificial Intelligence, 36(6):6367–6374, Jun. 2022.
  * Choi et al. [2023] Jeongwhan Choi, Seoyoung Hong, Noseong Park, and Sung-Bae Cho.  GREAD: Graph Neural Reaction-Diffusion Networks.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 5722–5747. PMLR, 23–29 Jul 2023.
  * Cini et al. [2023a] Andrea Cini, Ivan Marisca, Filippo Maria Bianchi, and Cesare Alippi.  Scalable Spatiotemporal Graph Neural Networks.  Proceedings of the AAAI Conference on Artificial Intelligence, 37(6):7218–7226, Jun. 2023.
  * Cini et al. [2023b] Andrea Cini, Ivan Marisca, Daniele Zambon, and Cesare Alippi.  Graph Deep Learning for Time Series Forecasting.  arXiv preprint arXiv:2310.15978, 2023.
  * Coddington and Levinson [1955] Earl A. Coddington and Norman Levinson.  Theory of Ordinary Differential Equations.  TATA McGraw-Hill, USA, 1955.
  * Defferrard et al. [2016] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering.  In Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
  * Derrow-Pinion et al. [2021] Austin Derrow-Pinion, Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Marc Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, Peter W. Battaglia, Vishal Gupta, Ang Li, Zhongwen Xu, Alvaro Sanchez-Gonzalez, Yujia Li, and Petar Velickovic.  ETA Prediction with Graph Neural Networks in Google Maps.  In Proceedings of the 30th ACM CIKM, page 3767–3776, New York, NY, USA, 2021. Association for Computing Machinery.
  * Du et al. [2017] Jian Du, Shanghang Zhang, Guanhang Wu, José M. F. Moura, and Soummya Kar.  Topology adaptive graph convolutional networks.  arXiv preprint arXiv:1710.10370, 2017.
  * Eliasof et al. [2021] Moshe Eliasof, Eldad Haber, and Eran Treister.  PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations.  In Advances in neural information processing systems, 2021.
  * Eliasof et al. [2024a] Moshe Eliasof, Eldad Haber, and Eran Treister.  Feature Transportation Improves Graph Neural Networks.  Proceedings of the AAAI Conference on Artificial Intelligence, 38(11):11874–11882, Mar. 2024.
  * Eliasof et al. [2024b] Moshe Eliasof, Eldad Haber, Eran Treister, and Carola-Bibiane B Schönlieb.  On the temporal domain of differential equation inspired graph neural networks.  In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 1792–1800. PMLR, 02–04 May 2024.
  * Errica et al. [2023] Federico Errica, Alessio Gravina, Davide Bacciu, and Alessio Micheli.  Hidden Markov Models for Temporal Graph Representation Learning.  In Proceedings of the 31st European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN), 2023\.
  * Gilmer et al. [2017] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl.  Neural Message Passing for Quantum Chemistry.  In Proceedings of the 34th International Conference on Machine Learning, volume 70, page 1263–1272. JMLR.org, 2017.
  * Gravina and Bacciu [2024] Alessio Gravina and Davide Bacciu.  Deep Learning for Dynamic Graphs: Models and Benchmarks.  IEEE Transactions on Neural Networks and Learning Systems, pages 1–14, 2024.
  * Gravina et al. [2022] Alessio Gravina, Jennifer L. Wilson, Davide Bacciu, Kevin J. Grimes, and Corrado Priami.  Controlling astrocyte-mediated synaptic pruning signals for schizophrenia drug repurposing with deep graph networks.  PLOS Computational Biology, 18(5):1–19, 05 2022.
  * Gravina et al. [2023] Alessio Gravina, Davide Bacciu, and Claudio Gallicchio.  Anti-Symmetric DGN: a stable architecture for Deep Graph Networks.  In International conference on learning representations (ICLR), 2023\.
  * Guo et al. [2022] Shengnan Guo, Youfang Lin, Huaiyu Wan, Xiucheng Li, and Gao Cong.  Learning Dynamics and Heterogeneity of Spatial-Temporal Graph Data for Traffic Forecasting.  IEEE Transactions on Knowledge and Data Engineering, 34(11):5415–5428, 2022.
  * Haber and Ruthotto [2017] Eldad Haber and Lars Ruthotto.  Stable Architectures for Deep Neural Networks.  Inverse problems, 34(1):014004, 2017.
  * Hamilton et al. [2017] William L. Hamilton, Rex Ying, and Jure Leskovec.  Inductive Representation Learning on Large Graphs.  In Advances in neural information processing systems, 2017.
  * Hu et al. [2020] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec.  Strategies for Pre-training Graph Neural Networks.  In International conference on learning representations (ICLR), 2020\.
  * Huang et al. [2020] Zijie Huang, Yizhou Sun, and Wei Wang.  Learning Continuous System Dynamics from Irregularly-Sampled Partial Observations.  In Advances in neural information processing systems, volume 33, pages 16177–16187. Curran Associates, Inc., 2020.
  * Huang et al. [2021] Zijie Huang, Yizhou Sun, and Wei Wang.  Coupled graph ode for learning interacting system dynamics.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, page 705–715, New York, NY, USA, 2021. Association for Computing Machinery.
  * Jiang and Luo [2022] Weiwei Jiang and Jiayun Luo.  Graph neural network for traffic forecasting: A survey.  Expert Systems with Applications, 207:117921, 2022.
  * Jin et al. [2022] Ming Jin, Yu Zheng, Yuan-Fang Li, Siheng Chen, Bin Yang, and Shirui Pan.  Multivariate time series forecasting with dynamic graph neural odes.  IEEE Transactions on Knowledge and Data Engineering, 2022.
  * Kang et al. [2024] Qiyu Kang, Kai Zhao, Qinxu Ding, Feng Ji, Xuhao Li, Wenfei Liang, Yang Song, and Wee Peng Tay.  Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FROND.  In The Twelfth International Conference on Learning Representations, 2024.
  * Kidger et al. [2020] Patrick Kidger, James Morrill, James Foster, and Terry Lyons.  Neural Controlled Differential Equations for Irregular Time Series.  In Advances in neural information processing systems, 2020.
  * Kipf and Welling [2017] Thomas N. Kipf and Max Welling.  Semi-Supervised Classification with Graph Convolutional Networks.  In International conference on learning representations (ICLR), 2017\.
  * Li et al. [2018] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu.  Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting.  In International conference on learning representations (ICLR), 2018\.
  * Li et al. [2019] Jia Li, Zhichao Han, Hong Cheng, Jiao Su, Pengyun Wang, Jianfeng Zhang, and Lujia Pan.  Predicting Path Failure In Time-Evolving Graphs.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, page 1279–1289, New York, NY, USA, 2019\. Association for Computing Machinery.
  * Liu et al. [2023] Bing Liu, Wei Luo, Gang Li, Jing Huang, and Bo Yang.  Do we need an encoder-decoder to model dynamical systems on networks?  In Edith Elkind, editor, Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pages 2178–2186. International Joint Conferences on Artificial Intelligence Organization, 8 2023.  Main Track.
  * Marisca et al. [2022] Ivan Marisca, Andrea Cini, and Cesare Alippi.  Learning to Reconstruct Missing Data from Spatiotemporal Graphs with Sparse Observations.  In Advances in neural information processing systems, pages 1–17, 2022.
  * Monti et al. [2019] Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael M. Bronstein.  Fake News Detection on Social Media using Geometric Deep Learning.  arXiv preprint arXiv:1902.06673, 2019.
  * Pareja et al. [2020] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson.  EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs.  In Proceedings of the 34th AAAI Conference on Artificial Intelligence, 2020.
  * Poli et al. [2019] Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo Park.  Graph neural ordinary differential equations.  arXiv preprint arXiv:1911.07532, 2019.
  * Rozemberczki et al. [2021] Benedek Rozemberczki, Paul Scherer, Yixuan He, George Panagopoulos, Alexander Riedel, Maria Astefanoaei, Oliver Kiss, Ferenc Beres, Guzman Lopez, Nicolas Collignon, and Rik Sarkar.  PyTorch Geometric Temporal: Spatiotemporal Signal Processing with Neural Machine Learning Models.  In Proceedings of the 30th ACM International Conference on Information and Knowledge Management, page 4564–4573, 2021.
  * Rubanova et al. [2019] Yulia Rubanova, Ricky T. Q. Chen, and David K Duvenaud.  Latent Ordinary Differential Equations for Irregularly-Sampled Time Series.  In Advances in neural information processing systems, volume 32. Curran Associates, Inc., 2019.
  * Rusch et al. [2022] T Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein.  Graph-coupled oscillator networks.  In International Conference on Machine Learning, pages 18888–18909. PMLR, 2022.
  * Seo et al. [2018] Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson.  Structured Sequence Modeling with Graph Convolutional Recurrent Networks.  In Neural Information Processing, pages 362–373, Cham, 2018. Springer International Publishing.
  * Veličković et al. [2018] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph Attention Networks.  International conference on learning representations (ICLR), 2018\.
  * Wang et al. [2021] Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin.  Dissecting the Diffusion Process in Linear Graph Convolutional Networks.  In Advances in Neural Information Processing Systems, volume 34, pages 5758–5769. Curran Associates, Inc., 2021.
  * Wu et al. [2019a] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying Graph Convolutional Networks.  In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 6861–6871. PMLR, 09–15 Jun 2019.
  * Wu et al. [2019b] Z Wu, S Pan, G Long, J Jiang, and C Zhang.  Graph WaveNet for Deep Spatial-Temporal Graph Modeling.  In The 28th IJCAI. International Joint Conferences on Artificial Intelligence Organization, 2019.
  * Wu et al. [2021] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu.  A Comprehensive Survey on Graph Neural Networks.  IEEE Transactions on Neural Networks and Learning Systems, 32(1):4–24, 2021.
  * Xu et al. [2019] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How Powerful are Graph Neural Networks?  In International conference on learning representations (ICLR), 2019\.
  * Zambon and Alippi [2022] Daniele Zambon and Cesare Alippi.  AZ-whiteness test: A test for signal uncorrelation on spatio-temporal graphs.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 11975–11986. Curran Associates, Inc., 2022.
  * Zang and Wang [2020] Chengxi Zang and Fei Wang.  Neural Dynamics on Complex Networks.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, page 892–902, New York, NY, USA, 2020\. Association for Computing Machinery.
  * Zhao et al. [2020] Ling Zhao, Yujiao Song, Chao Zhang, Yu Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li.  T-GCN: A Temporal Graph Convolutional Network for Traffic Prediction.  IEEE Transactions on Intelligent Transportation Systems, 21(9):3848–3858, 2020.
  * Zitnik et al. [2018] Marinka Zitnik, Monica Agrawal, and Jure Leskovec.  Modeling polypharmacy side effects with graph convolutional networks.  Bioinformatics, 34(13):i457–i466, 06 2018.