# Learning Linear Embeddings for Non-Linear Network Dynamics with Koopman
Message Passing

King Fai Yeh  Corresponding Author<EMAIL_ADDRESS>Department of Computer
Science and Technology, University of Cambridge, UK  Paris Flood  Department
of Computer Science and Technology, University of Cambridge, UK  William
Redman  Interdepartmental Graduate Program in Dynamical Neuroscience,
University of California, Santa Barbara, USA  Pietro Liò  Department of
Computer Science and Technology, University of Cambridge, UK

###### Abstract

Recently, Koopman operator theory has become a powerful tool for developing
linear representations of non-linear dynamical systems. However, existing
data-driven applications of Koopman operator theory, including both
traditional and deep learning approaches, perform poorly on non-linear network
dynamics problems as they do not address the underlying geometric structure.
In this paper we present a novel approach based on Koopman operator theory and
message passing networks that finds a linear representation for the dynamical
system which is globally valid at any time step. The linearisations found by
our method produce predictions on a suite of network dynamics problems that
are several orders of magnitude better than current state-of-the-art
techniques. We also apply our approach to the highly non-linear training
dynamics of neural network architectures, and obtain linear representations
which can generate network parameters with comparable performance to networks
trained by classical optimisers.

##  1 Introduction

Dynamical systems theory has long been a valuable branch of mathematics,
finding applications in innumerable scientific fields. Systems fortunate
enough to have a linear characterisation have well-developed methodologies for
prediction, control, and interpretation, as their properties are defined by
their spectral decomposition. In contrast, non-linear systems do not have a
single, general theory which can determine their behaviour with universal
precision. At best, there are bespoke solution methods for select scenarios -
a frustrating state of affairs as non-linear phenomena are rich and
ubiquitous.

Koopman operator theory Koopman [1931], Mezić [2005], Budišić et al. [2012],
Brunton et al. [2022] has recently developed into an effective tool for
casting dynamics problems from non-linear to linear. The Koopman operator
progresses complex-valued measurements of a dynamical system linearly;
unfortunately, the operator is also infinite-dimensional. As a remedy, many
modern developments have focused on finding finite matrix approximations of
the Koopman operator. This problem is challenging as it generally involves
deriving potentially complex Koopman eigenfunctions.

Data-driven Koopman approaches have recently become extremely popular as they
have demonstrated remarkable efficacy (see Section 2 for further details).
However, current state-of-the-art methods do not perform well for non-linear
dynamics with an underlying network geometry, despite sometimes being
purposely designed for such a case. This is a deficiency that affects large
classes of non-linear phenomena.

Traditional approaches rely on in-depth analysis of a particular dynamical
system; theoretical data-driven pipelines make general assumptions on the
dynamics that impede their expressiveness. Existing deep learning approaches
usually do not take in inductive biases corresponding to the underlying
structures of particular dynamical systems.

In this paper, we present a novel, highly effective solution to this problem -
a Koopman message-passing neural network (KMPNN). Our approach exploits the
geometric structure of the dynamics when constructing a linear representation
for the network. It leverages several message-passing layers to explore the
neighbourhood of each node. These neighbourhood activations are then condensed
into a single, global linear representation of the state of the dynamics. This
layer enables control over the linear representation dimensions.

We run our approach on several network dynamical systems across a variety of
scientific disciplines such as epidemiology (disease spread across social
networks) and neuroscience (activation dynamics across the brain). Our
approach produces a significantly better linear representation, through which
we can predict dynamics trajectories several orders of magnitude more
accurately than the state-of-the-art.

To ramp up the complexity of the dynamics, we also evaluate our model on the
training dynamics of a suite of neural network architectures. To the best of
our knowledge, our approach again outperforms the best current methods at
producing training trajectories, with a performance close to classical
optimisers and a robustness to different architectural setups. On both types
of dynamics, our model can find a linear representation from the start of the
trajectories without the need for warm starts. Our results suggest that our
KMPNN autoencoder can be used as a general framework for dissecting complex
network dynamics due to its versatility across various levels of
sophistication.

##  2 Background

###  2.1 Koopman Operator Theory

Consider $\mathbf{x}_{t}\in\mathcal{X}\subseteq\mathbb{R}^{n}$ as the state of
a dynamical system at time step $t$. In discrete-time dynamical systems, a
dynamical map $f:\mathcal{X}\to\mathcal{X}$ is a function that advances the
system state by one time step: $\mathbf{x}_{t+1}=f(\mathbf{x}_{t})$. Consider
a class of measurement functions $g\in\mathcal{G}:\mathcal{X}\to\mathbb{C}$
producing complex-valued measurements of the system at a given state. The
Koopman operator $\mathcal{K}_{f}:\mathcal{G}\to\mathcal{G}$ for a dynamical
map $f$ is a linear operator defined by $\mathcal{K}_{f}(g)\triangleq g\circ
f$ Koopman [1931], satisfying:

$\mathcal{K}_{f}(g)(\mathbf{x}_{k})=g\circ
f(\mathbf{x}_{k})=g(\mathbf{x}_{k+1})$

Since infinite degrees of freedom are needed to characterise the entire set of
measurement functions, the Koopman operator is infinite-dimensional,
constraining the practical use of the operator. Consider a Koopman-invariant
subspace $\hat{\mathcal{G}}$ spanned by a set of measurement functions
$\\{g_{i}\\}^{m}_{i=1}$, such that $\mathcal{K}_{f}(g)\in\hat{\mathcal{G}}$
for any $g\in\hat{\mathcal{G}}$. By constraining the domain and co-domain of
$\mathcal{K}_{f}$ to this invariant subspace, the Koopman operator can be
represented with a finite matrix $\mathbf{K}\in\mathbb{C}^{m\times m}$
instead.

Consider a finite vector $\mathbf{g}\in\mathcal{X}\to\mathbb{C}^{m}$ of
measurement functions
$\mathbf{g}=\begin{bmatrix}g_{1}&g_{2}&\ldots&g_{m}\end{bmatrix}^{\intercal}$
with $g_{i}\in\hat{\mathcal{G}}$. Applying $\mathbf{g}$ to a state
$\mathbf{x}_{k}$ produces an embedding of measurements in $\mathbb{C}^{m}$,
satisfying:

$\mathbf{g}(\mathbf{x}_{k+t})\triangleq\mathcal{K}_{f}^{t}(\mathbf{g})(\mathbf{x}_{k})=\mathbf{K}^{t}(\mathbf{g}(\mathbf{x}_{k}))$

If $\mathbf{g}$ is invertible, we have
$\mathbf{x}_{k+t}=\mathbf{g}^{-1}(\mathbf{K}^{t}(\mathbf{g}(\mathbf{x}_{k})))$,
where $\mathbf{g}(\mathbf{x})$ effectively gives a linear representation to
the dynamical states.

A Koopman eigenfunction $\varphi:\mathcal{X}\to\mathbb{C}$ is a particular
type of measurement function satisfying
$\mathcal{K}_{f}(\varphi)=\lambda\cdot\varphi$. If $\mathbf{g}$ is constructed
as a vector of eigenfunctions $\boldsymbol{\varphi}$, the corresponding
$\mathbf{K}$ will be diagonal, filled with their eigenvalues. Finding Koopman
eigenfunctions allows for a decomposition of the action of the Koopman
operator Mezić [2005]:

$\mathcal{K}_{f}(g)(\mathbf{x}_{k})=g\circ
f(\mathbf{x}_{k})=\sum_{i=1}^{m}\lambda_{i}\varphi_{i}v_{i}$

where $v_{i}\in\mathbb{C}$ are Koopman modes. Such a decomposition is referred
to as the Koopman mode decomposition. It illustrates that the complex dynamics
can now be understood as evolving along exponential paths in the directions
defined by $\varphi_{i}v_{i}$. Additionally, the time scales over which
different dynamic phenomena exist can be assessed via the magnitude of the
$\lambda_{i}$. This makes Koopman mode decomposition a powerful tool for
analysis and prediction and has driven its use in many applied problems
Budišić et al. [2012], Mauroy et al. [2020], Brunton et al. [2022].

###  2.2 Related Work

Finding a basis for measurement functions for a Koopman-invariant subspace is
usually not straightforward. Traditional approaches attempt to construct a
basis with expert knowledge of the targeted dynamical system. Modern Koopman
analysis uses data-driven methods to approximate such a subspace, including
theoretical pipelines Tu et al. [2014b], Williams et al. [2015], Kaiser et al.
[2018], Fujii and Kawahara [2019], and more recent deep learning approaches
Lusch et al. [2018], Li et al. [2019], Otto and Rowley [2019], Yeung et al.
[2019], Azencot et al. [2020], Han et al. [2020], Shi and Meng [2022].

There have been several applications of Koopman analysis to the training
dynamics of deep neural networks. Dogra established a connection between
neural network training and dynamical systems via Koopman operator theory
Dogra [2020]. Researchers have then leveraged the relationship to accelerate
the training process Dogra and Redman [2020], Tano et al. [2020], Simanek et
al. [2022], Luo et al. [2022], by utilising the learned linear embeddings to
predict the evolution of network weights and to prune deep neural networks
Manojlovic et al. [2020], Redman et al. [2021].

The methods presented in this section have shown impressive results on various
non-linear phenomena. However, as we shall see in Section 4, even the state-
of-the-art approaches leave much to be desired when applied to dynamics
problems with network geometry.

###  2.3 Graph Neural Networks

Graph neural networks (GNN) are a class of neural networks designed for
processing data with graph structures. GNNs utilise message passing Gilmer et
al. [2017] to aggregate the local neighbourhood features for each node. For a
graph $G=(V,E)$ with node features $\mathbf{x}_{u}\in\mathbb{R}^{c}$ and edge
features $\mathbf{e}_{u\to v}\in\mathbb{R}^{d}$, a message passing iteration
is represented as:

$\mathbf{x}_{v}^{\prime}=\gamma(\mathbf{x}_{v},\square_{u\to v}\
\phi(\mathbf{x}_{v},\mathbf{x}_{u},\mathbf{e}_{u\to v}))$

$\phi$ generates a message on each edge $u\to v$ using its features and the
features of its two endpoints. $\square$ is a permutation-invariant aggregator
(e.g. sum, max) that combines the messages of a neighbourhood. $\gamma$ takes
the aggregated message and updates the node in question.

Different flavours of GNNs are created by varying the flexibility of the
message generation function $\phi$ and node update function $\gamma$ Kipf and
Welling [2016], Veličković et al. [2017], Gilmer et al. [2017], Shi et al.
[2020]. In the most generic settings, usually called message-passing neural
networks (MPNN), $\phi$ and $\gamma$ are fully-connected multi-layer
perceptrons (MLPs) Gilmer et al. [2017].

###  2.4 Network Dynamics

Table 1: Theoretical network dynamical systems from an ensemble of scientific
disciplines including genetics, neuroscience, epidemiology, and ecology
Bakhtiarnia et al. [2020].

Network Dynamics | Equation | Examples
---|---|---
Regulatory | $\frac{dx_{i}}{dt}=-x_{i}^{0.4}+\sum_{j\to i}A_{ij}\frac{x_{j}^{0.2}}{1+x_{j}^{0.2}}$ | Gene regulation
Neuronal | $\frac{dx_{i}}{dt}=-Bx_{i}+C\tanh(x_{i})\sum_{j\to i}A_{ij}\tanh(x_{j})$ | Activation dynamics between brain regions
Population | $\frac{dx_{i}}{dt}=-x_{i}^{0.5}+\sum_{j\to i}A_{ij}x_{j}^{0.2}$ | Birth-death processes
Epidemic | $\frac{dx_{i}}{dt}=-x_{i}+\sum_{j\to i}A_{ij}(1-x_{i})x_{j}$ | Social networks, Spread of epidemics
Mutualistic | $\frac{dx_{i}}{dt}=x_{i}(1-x_{i}^{2})+\sum_{j\to i}A_{ij}\frac{x_{i}x_{j}}{1+x_{j}}$ | Plant-pollinator relationships in ecology

Complex dynamical networks are geometric structures that can display non-
linear behaviour over time Bakhtiarnia et al. [2020]. Each node $u$ in the
graph is associated with a numerical quantity $\mathbf{x}_{u}$. This quantity
is governed by a specific differential equation concerning the quantities of
its local neighbourhood, usually in the form of:

$\frac{dx_{u}}{dt}=f(\mathbf{x}_{u})+\sum_{v\to u}A_{vu}\cdot
g(\mathbf{x}_{u},\mathbf{x}_{v})$

where $f$ and $g$ represent self-dynamics and neighbourhood impacts. $A_{vu}$
is an adjacency matrix storing the edge weight of $v\to u$. If the network is
unweighted, $A_{vu}=1$ for any edge $v\to u$. If the network is undirected,
$A_{vu}=A_{uv}$. Otherwise, if no edge exists between $v$ and $u$, $A_{vu}=0$.
Table 1 shows several complex networks commonly appearing in biological,
neural, and social dynamics.

##  3 Approach

This section presents a novel approach to learning a set of measurement
functions giving non-linear network dynamics a linear representation. In line
with the autoencoder developed by Lusch et al. [2018], our method learns a set
of Koopman eigenfunctions that produce measurements of the network which
correspond one-to-one with the actual network states. To exploit the intrinsic
geometric structures, we present the KMPNN autoencoder to improve the quality
of the linear representations obtained.

###  3.1 Problem Formulation

We hope to learn a set of Koopman eigenfunctions $\boldsymbol{\varphi}$, their
inverses $\boldsymbol{\varphi}^{-1}$ and a diagonal matrix $\mathbf{K}$
satisfying:

$\mathbf{x}_{k+t}=\boldsymbol{\varphi}^{-1}(\mathbf{K}^{t}(\boldsymbol{\varphi}(\mathbf{x}_{k})))$

where $\mathbf{x}_{k}$ and $\mathbf{x}_{k+t}$ are the network states at time
step $k$ and $k+t$. We can frame this as a trajectory prediction problem. For
a given state $\mathbf{x}_{k}$, we need to minimise the differences between
the actual $\mathbf{x}_{k+t}=f^{t}(\mathbf{x}_{k})$ and the predicted
$\hat{\mathbf{x}}_{k+t}=\boldsymbol{\varphi}^{-1}(\mathbf{K}^{t}(\boldsymbol{\varphi}(\mathbf{x}_{k})))$.
In other words, we are trying to find a latent space representation of the
dynamics such that one time step corresponds to one linear transformation in
the latent space. $\boldsymbol{\varphi}$ encodes network states into their
latent embeddings, $\mathbf{K}$ linearly advances the latent embeddings, and
$\boldsymbol{\varphi}^{-1}$ decodes latent embeddings back into the original
dynamics.

We train our models on three types of loss functions Lusch et al. [2018]. The
first type is the reconstruction loss:

$\mathcal{L}_{recon}=||\
\mathbf{x}-\boldsymbol{\varphi}^{-1}(\boldsymbol{\varphi}(\mathbf{x}))\ ||$

which ensures the network dynamics are uniquely recoverable from the latent
embeddings. The second type is the linear prediction loss:

$\mathcal{L}_{linear}=||\
\boldsymbol{\varphi}(\mathbf{x}_{k+t})-\mathbf{K}^{t}(\boldsymbol{\varphi}(\mathbf{x}_{k}))\
||$

which enforces the latent space structure such that latent embeddings advance
linearly with $\mathbf{K}$. The third type is the dynamics prediction loss:

$\mathcal{L}_{pred}=||\
\mathbf{x}_{k+t}-\boldsymbol{\varphi}^{-1}(\mathbf{K}^{t}(\boldsymbol{\varphi}(\mathbf{x}_{k})))\
||$

This component ensures the decoder $\boldsymbol{\varphi}^{-1}$ works with the
structure of the latent space to predict future states. $||\cdot||$ refers to
the mean-squared error, averaged over time steps and the number of samples.
The overall loss function is a linear combination of the three, with weights
$\alpha_{1},\alpha_{2},\alpha_{3}\in\mathbb{R}^{+}$:

$\mathcal{L}=\alpha_{1}\mathcal{L}_{recon}+\alpha_{2}\mathcal{L}_{linear}+\alpha_{3}\mathcal{L}_{pred}$

###  3.2 KMPNN Autoencoder

Let $G=(V,E)$ be a graph with $n$ nodes, $m$ edges, and an adjacency matrix
$\mathbf{A}\in\mathbb{R}^{n\times n}$. The value of node $u$ at time step $t$
in the network dynamics is given by $v_{u,t}$. In our approach, an embedding
$\mathbf{x}_{u,t}$ for each node $u$ and time step $t$ is constructed:

$\mathbf{x}_{u,t}=\sigma_{N}(id_{u})\ ||\ w(v_{u,t})$

where $\sigma_{N}$ is a trainable lookup table encoding node identifiers, and
$w$ is an MLP encoding node values, with $||$ denoting concatenation.
$\sigma_{N}(id_{u})$ is node/neighbourhood-specific, while $w(v_{u,t})$
depends solely on the current state of a node. Concatenating these
representations gives an embedding for the node. The embedding of an edge
$u\to v\in E$ is constructed in a similar way:

$\mathbf{e}_{u,v}=\sigma_{E}(id_{u\to v})$

with $\sigma_{E}$ being a trainable lookup table encoding edge identifiers.
These higher-dimensional node and edge embeddings are created to enrich the
feature space of the network.

Denote the node embedding matrix $\mathbf{X}$ and edge embedding matrix
$\mathbf{E}$ by:

$\displaystyle\mathbf{X}=\begin{bmatrix}\mathbf{x}_{1}\mathbf{x}_{2}\dots\mathbf{x}_{n}\end{bmatrix}^{\intercal}\in\mathbb{R}^{n\times
c}$
$\displaystyle\mathbf{E}=\begin{bmatrix}\mathbf{e}_{u_{1},v_{1}}\mathbf{e}_{u_{2},v_{2}}\dots\mathbf{e}_{u_{m},v_{m}}\end{bmatrix}^{\intercal}\in\mathbb{R}^{m\times
c}$

with $c$ being the dimension of the trainable lookup tables. Apply two MPNN
layers $\Theta_{\mathbf{A}}$ and $\Theta_{\mathbf{A}}^{(1)}$ on node
embeddings $\mathbf{X}$ and $\mathbf{E}$:

$\displaystyle\mathbf{X}^{(1)}$
$\displaystyle=\Theta_{\mathbf{A}}(\mathbf{X},\mathbf{E})$
$\displaystyle\mathbf{X}^{(2)}$
$\displaystyle=\Theta_{\mathbf{A}}^{(1)}(\mathbf{X}^{(1)},\mathbf{E})$
$\displaystyle\mathbf{y}$ $\displaystyle=\phi(\mathbf{X}^{(2)})$

where $\phi:\mathbb{R}^{n\times c}\to\mathbb{R}^{h}$ is an MLP with $h$ being
the dimension of the linear latent space. Here we use MPNN layers over other
graph convolutions for their expressiveness, whereas the MLP provides the
flexibility to learn the message generation and node update functions. This
defines the graph encoder $\boldsymbol{\varphi}$ in our approach.

The latent representations after $t$ time steps are given by:

$\mathbf{\widetilde{y}}=\mathbf{K}^{t}\mathbf{\dot{y}}$

where $\mathbf{K}\in\mathbb{C}^{0.5h\times 0.5h}$ is a diagonal matrix and
$\mathbf{\dot{y}}\in\mathbb{C}^{0.5h}$. The vector $\mathbf{\dot{y}}$ is a
regrouping of $\mathbf{y}\in\mathbb{R}^{h}$ into pairs that represent the real
and imaginary components of complex numbers. In a slight abuse of notation,
the resulting product is subsequently arranged back into a real vector.
Complex eigenvalues are used in the diagonal matrix $\mathbf{K}$ to
accommodate periodic orbits in the dynamics. For ease of reading, we omit the
details of these operations from the equation above.

The graph decoder $\boldsymbol{\varphi}^{-1}$ can be defined in a similar way:

$\displaystyle\mathbf{\widetilde{X}}^{(2)}$
$\displaystyle=\phi^{-1}\left(\mathbf{\widetilde{y}}\right)$
$\displaystyle\mathbf{\widetilde{X}}^{(1)}$
$\displaystyle=\Theta_{\mathbf{A}}^{(1)^{\prime}}\left(\mathbf{\widetilde{X}}^{(2)},\mathbf{E}\right)$
$\displaystyle\mathbf{\widetilde{X}}$
$\displaystyle=\Theta_{\mathbf{A}}^{\prime}\left({\mathbf{\widetilde{X}}^{(1)},\mathbf{E}}\right)$

with $\phi^{-1}:\mathbb{R}^{h}\to\mathbb{R}^{n\times c}$ being an MLP as well.
Finally, a per-node MLP is applied to the activation of every node to obtain a
prediction value for each node representing its current state.

The KMPNN autoencoder exploits the “neighbourhood” concept in the geometry of
the dynamics. Each graph convolution layer uses MLPs for flexible message
generation and node updates. In the graph encoder, the last-layer activations
are concatenated and fed into a global MLP to create an overall latent
embedding. This step breaks the permutation-invariant property of graph neural
networks in general. Still, since the dynamics have the same geometry across
different trajectory runs, the property plays a less significant role in
achieving our aim.

##  4 Experiments

In this section, we evaluate our approach by measuring its performance in
predicting the trajectories of several network dynamical systems under random
initial states and comparing it against conventional Koopman analysis
baselines.

###  4.1 Experimental Setup

####  4.1.1 Datasets

We evaluate our approach on two types of dynamics: (1) synthetic network
dynamics governed by specific differential equations and (2) training dynamics
of neural networks. The synthetic dynamics are generated by following through
the equations from random initial states, which can be found in Table 1. These
dynamics are modelled as discrete-time dynamical systems by specifying a
$\Delta t$ per snapshot and approximating the following snapshot with the
composite trapezoidal rule.

The weight/bias trajectories of neural network training are created by
applying mini-batch gradient descent on randomly-initialised neural networks,
with different non-trivial architectures, on a suite of tasks. Details about
these tasks are in Appendix A. After running through the entire training
dataset, the updated set of weights and biases becomes the state of the next
epoch. Note that neural network training dynamics are intrinsically discrete-
time dynamical systems.

We generate 10k trajectories for each dynamical system, with train,
validation, and test splits of 8k, 1k, and 1k, respectively. All initial
states in the synthetic dynamics are uniformly sampled within $[0,1]$, while
the initial weights and biases in the training dynamics are sampled in
$[-1,0.1]$. The number of snapshots for each dynamical system is carefully
chosen to ensure convergence whenever possible, usually between 50-500 time
steps. The graphs in the synthetic networks all consist of 100 nodes and 250
bidirectional edges, while the architectures of the neural networks range
between 50-300 parameters.

####  4.1.2 Baselines

We compare our approach against four data-driven baselines: dynamic mode
decomposition (DMD) Tu et al. [2014a], Extended DMD Folkestad et al. [2019],
Graph DMD Fujii and Kawahara [2019], and the Lusch autoencoder Lusch et al.
[2018]. DMD is a classical algorithm Schmid [2010] that identifies a best-fit
linear approximation to the Koopman operator of a dynamical system by seeking
the dominant eigenvalues and eigenvectors in the spectral decomposition of the
linear operator Rowley et al. [2009]. Extended DMD augments the identity
measurements in DMD by non-linear measurements before performing the
regression Williams et al. [2015]. Graph DMD is a state-of-the-art approach
that extends DMD to graph dynamics by utilising tensor-train decomposition to
maintain the tensor structure of the dynamics Fujii and Kawahara [2019]. The
Lusch autoencoder uses feedforward MLPs to approximate a set of measurement
functions that advance linearly upon being acted on by the Koopman operator,
such that the measurements produced uniquely represent the original dynamics
Lusch et al. [2018]. To ensure a fair comparison, the Lusch autoencoder used
in the experiments has a similar number of parameters as our proposed KMPNN
autoencoder.

####  4.1.3 Training

The parameters of the deep learning models were initialised uniformly random
in the range $(-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}})$ with $d$ being the
input dimension of their layers. The Adam optimiser used had a default
learning rate of $10^{-3}$ for optimisation. The models were trained on an
NVIDIA Titan Xp GPU, with each Lusch autoencoder taking 3-12 hours and the
KMPNN autoencoder taking 8-24 hours.

The Lusch autoencoder uses a 3-layer MLP for both its encoder and decoder.
Unless otherwise specified, both autoencoders are trained with a latent space
dimension being the closest power of 2 greater than the number of nodes in the
dynamics.

###  4.2 Synthetic Network Dynamics

Table 2: Prediction losses of our approach on synthetic network dynamics. The
Lusch and KMPNN autoencoders are trained with a latent space dimension of 256.
All entries for extended DMD and some for graph DMD are omitted as the
algorithm is unable to identify a system, or the identified system produced
out-of-scale predictions.

Baseline | Regulatory | Neuronal | Population | Epidemic | Mutualistic
---|---|---|---|---|---
DMD | 0.0726 | 0.8482 | 1.0638 | 0.0175 | 0.3891
Graph DMD | 0.4443 | - | - | 0.0465 | 1.1023
Lusch autoencoder | 0.0340 | 0.0282 | 0.0484 | 2.576e-3 | 0.0427
KMPNN autoencoder | 4.935e-5 | 4.716e-5 | 1.042e-4 | 8.142e-6 | 3.775e-4

Table 2 shows the prediction losses of the models in the trajectories of the
synthetic dynamics based on differential equations from a variety of
disciplines Bakhtiarnia et al. [2020]. The prediction loss can be interpreted
as the average squared deviation of each node between the predicted and actual
trajectories. Our model significantly outperforms existing baselines in
capturing a set of measurement functions and a linear Koopman operator to form
a Koopman-invariant subspace. This is reflected by the better prediction
performance with the linear representation captured by the measurement
functions in our approach.

In our experiments, the deep learning approaches show a substantial advantage
over theoretical baselines. DMD and Graph DMD fit a linear model to the
dynamics, so their inability to capture non-linearity could be expected.
Extended DMD assumes that a Koopman-invariant subspace can be approximated
with a library of candidate functions, relying on the library is sufficiently
expressive to represent the dynamics. When this is not the case, the
“invariant” system identified would be largely spurious, accounting for its
inability to produce sound predictions.

All baselines, except for Graph DMD, do not consider the inherent graph
structures of the dynamics. The baselines’ expressiveness could be constrained
without considering the dynamics’ structure, especially in the Lusch
autoencoder. Without the inductive bias, the Lusch autoencoder flattens the
graph dynamics before feeding into the MLPs. Being quadratic to the input
dimension, the fully-connected layers could impede the search for good minima
during optimisation.

Figure 1: Example of synthetic network dynamic trajectories and the
corresponding predictions made by DMD (purple dashed line), Graph DMD (orange
dashed line), Lusch autoencoder (green dashed line), and KMPNN autoencoder
(red dashed line). The x-axis and y-axis each represents a node.

(a) Epidemic dynamics

(b) Mutualistic dynamics

Figure 1 shows some qualitative results comparing the actual and predicted
trajectories of two nodes in the test samples. The KMPNN approach accurately
predicts the trajectories from unseen starting conditions. Most baselines
predict similarly well for population dynamics, likely because many of the
trajectories are close to being linear and do not converge. In contrast,
predictions in epidemic and mutualistic dynamics make the differences in
predictive power between the theoretical baselines, the Lusch autoencoder, and
our approach more evident. The prediction of our approach closely resembles
the actual trajectories, while other baselines are less successful in
capturing the dynamics, despite being able to arrive at a similar state
eventually.

###  4.3 Neural Network Training Dynamics

Table 3: Prediction losses of our approach on neural network training
dynamics. The architectures of the neural networks (whose training dynamics
are captured) are labelled with either $x$-fc or $y$-conv-$z$-fc. The former
refers to an architecture with $x$ fully-connected layers, the latter with $y$
sets of convolutional and max pooling layers followed by $z$ fully-connected
layers. Some extended and Graph DMD entries are omitted as the algorithm is
unable to identify a system, or the identified system produced out-of-scale
predictions.

| Linear | Classification | DE solver | Image classification
---|---|---|---|---
Baseline | 1-fc | 2-fc | 3-fc | 3-fc | 1-conv-2-fc | 2-conv-1-fc
DMD | 48.1506 | 0.0591 | 0.0886 | 0.0671 | 0.4245 | 0.3687
Extended DMD | - | 0.0710 | - | 0.1001 | - | -
Graph DMD | - | 0.0560 | 0.0954 | 0.0846 | - | -
Lusch autoencoder | 48.1532 | 0.0020 | 0.0305 | 0.0323 | 0.1203 | 0.2463
KMPNN autoencoder | 48.1291 | 0.0006 | 0.0276 | 0.0119 | 0.0366 | 0.1153

Table 3 shows the prediction losses of models in weight and bias training
dynamics of different neural networks. The difference in predictive abilities
of our approach and the Lusch autoencoder becomes much more evident (except
for the linear training trajectories for linear regression, which linear
approaches like DMD can already successfully capture). Backpropagation in
gradient descent stacks non-linear gradient terms one-within-another,
exponentially complexifying the gradient expressions. Since the non-linearity
in training dynamics requires a more complex set of measurement functions,
this can explain the widened performance difference between our approach, the
Lusch autoencoder, and other baselines. Figure 2 plots the predicted
trajectories of two weights/biases against their actual trajectory.

Figure 2: Example of weight and bias trajectories and the corresponding
predictions made by DMD (purple dashed line), Lusch autoencoder (green dashed
line), and KMPNN autoencoder (red dashed line). The x-axis and y-axis each
represents a weight/bias.

(a) DE solver: 3-fc

(b) Image classification: 1-conv-2-fc

####  4.3.1 Optimisation Performance

Figure 3: Example of actual and predicted loss trajectories made by DMD
(purple dashed line), Lusch autoencoder (green dashed line), and KMPNN
autoencoder (red dashed line).

(a) DE solver: 3-fc

(b) Image classification: 1-conv-2-fc

We look into the loss trajectories of the neural networks using the weights
and biases predicted by the models. Figure 3 shows a qualitative comparison
between the actual loss trajectories and the loss trajectories using predicted
weights and biases. Despite being unable to predict the exact trajectory on
which the weights and biases evolve, our approach can find a trajectory with a
similar loss (if not better) performance that can be represented linearly in
the Koopman-invariant subspace. The predicted trajectories often avoid
training instability, converging along a smoother path.

A similar evaluation methodology as Dogra and Redman [2020] is adopted to
quantify the optimisation performance of our approach. We look at the
optimisation performance $r$, the ratio of the differences between the initial
loss and the final loss in the actual trajectory to that of the predicted
trajectory:

$r=\frac{l_{0}-l_{pred}}{l_{0}-l_{true}}$

with $l_{0}$ being the initial training loss, and $l_{pred}$ and $l_{true}$
being the final training losses in the predicted and actual trajectories,
respectively. The closer $r$ is to 1, the closer the final loss of the
predicted trajectory is to the actual trajectory. The average values for $r$
(in percentages) are tabulated in Table 4, which shows the weight and bias
trajectories predicted using our approach indeed have a similar optimisation
performance as backpropagation.

Table 4: Optimisation performances of weights and biases predicted with our approach. Linear | Classification | DE solver | Image classification
---|---|---|---
1-fc | 2-fc | 3-fc | 3-fc | 1-conv-2-fc | 2-conv-1-fc
100.3% | 98.6% | 92.2% | 87.6% | 100.6% | 90.5%

####  4.3.2 Latent Space Dimensions

An interesting observation comes from analysing how many latent dimensions are
required for the measurement functions to capture the training dynamics. The
dynamics of two neural networks are studied, including a 2-layer MLP on the
classification task (with 106 parameters) and a 3-layer CNN on the image
classification task (with 194 parameters). Table 5 reports the prediction
losses and optimisation performances of the KMPNN autoencoder equipped with a
count of measurement functions varying along powers of 2.

Our approach can learn a representation for the training dynamics of neural
networks with $>100$ parameters, starting from random initialisations, using
$<10$ linearly-evolving eigenfunctions. The possibility of a low-dimensional
linear representation provides another perspective for the general over-
parametrisation phenomena of neural networks and is in line with work studying
the dynamics present during deep neural network training Gur-Ari et al.
[2018], Turjeman et al. [2022].

Table 5: Prediction losses and optimisation performances $r$ (in percentages)
of our approach evaluated on the training dynamics of a 2-fc MLP and a
1-conv-2-fc CNN with latent dimension varying among powers of 2.
Dimension | 2-fc MLP | 1-conv-2-fc CNN
---|---|---
4 | 0.0130 / 90.1% | 0.4536 / 0.1%
8 | 0.0030 / 98.2% | 0.0562 / 100.7%
16 | 0.0022 / 98.5% | 0.0647 / 100.6%
32 | 0.0015 / 98.5% | 0.0805 / 100.5%
64 | 0.0006 / 98.4% | 0.0513 / 100.7%
128 | 0.0005 / 98.0% | 0.0393 / 100.6%

####  4.3.3 Robustness to Variations

We show the robustness of our KMPNN autoencoder by evaluating it on training
dynamics with varying specifications. Our approach maintains a similar
optimisation performance when applied to the training dynamics of neural
networks with different non-linearity activation functions, optimisers, and
randomised mini-batches. More details can be found in Appendix B.

####  4.3.4 Comparison with Previous Approaches

There have been several approaches Dogra and Redman [2020], Tano et al. [2020]
attempting to identify a linear relationship on which the weights and biases
evolve. The linear Koopman operators identified by both papers are local to a
single perceptron/layer at a specific training instance. The operator Tano et
al. [2020] identified only applies to a few training epochs ahead, while the
one by Dogra and Redman [2020] is valid only after training has entered basins
of local loss minima.

Our approach suffers from none of these limitations. The KMPNN autoencoder can
identify a globally linear operator (and a set of measurement functions)
representing the entire neural network’s dynamics. The same operator can apply
to any randomly initialised trajectory. The operator identified is also valid
from the beginning to the end of the training process without requiring
proximity to any loss minima.

##  5 Conclusion

We have presented a novel, highly effective approach for finding a linear
representation of non-linear network dynamics. We successfully demonstrated
that the linear representation produced by our approach provides better
predictions of the dynamics than the state-of-the-art. Although our approach
takes more wall clock time to train, it significantly outperforms existing
traditional and deep learning approaches for non-linear dynamics problems,
including neural network training dynamics. In the latter problem, the linear
representations extracted are significantly smaller than the respective
network sizes.

The optimisation performance of the weights and biases predicted in neural
network training are on par with classical optimisers while robust to
architectural and training configuration variations. The linearisation is also
more versatile than previous approaches Dogra and Redman [2020], Tano et al.
[2020].

The KMPNN autoencoder presented in this paper has significant potential for
application to other nonlinear network dynamics problems. We hope this success
will lead future efforts to address further challenges in the application of
Koopman operatory theory to complex non-linear systems. For example, as neural
networks tend to have many parameters, each of which our approach treats as a
node, the KMPNN is limited by the amount of GPU memory available when applied
to larger and denser architectures. A direction for future research could be
to scale our approach to bigger networks by reducing the memory footprint of
the KMPNN autoencoder.

## References

  * uci [1991] Uci machine learning repository: Wine data set, 1991.  URL https://archive.ics.uci.edu/ml/datasets/wine.
  * uci [1998] Uci machine learning repository: Optical recognition of handwritten digits data set, 1998.  URL https://archive.ics.uci.edu/ml/datasets/Optical+Recognition+of+Handwritten+Digits.
  * Azencot et al. [2020] O. Azencot, N. B. Erichson, V. Lin, and M. Mahoney.  Forecasting sequential data using consistent koopman autoencoders.  In _International Conference on Machine Learning_ , pages 475–485. PMLR, 2020.
  * Bakhtiarnia et al. [2020] A. Bakhtiarnia, A. Fahim, and E. M. Miandoab.  Data-driven discovery of social network dynamics.  In _2020 4th International Conference on Smart City, Internet of Things and Applications (SCIOT)_ , pages 39–45, 2020.  doi: 10.1109/SCIOT50840.2020.9250195.
  * Brunton et al. [2022] S. L. Brunton, M. Budišić, E. Kaiser, and J. N. Kutz.  Modern koopman theory for dynamical systems.  _SIAM Review_ , 64(2):229–340, 2022.
  * Budišić et al. [2012] M. Budišić, R. Mohr, and I. Mezić.  Applied koopmanism.  _Chaos: An Interdisciplinary Journal of Nonlinear Science_ , 22(4):047510, 2012.
  * Dogra [2020] A. S. Dogra.  Dynamical systems and neural networks.  _arXiv preprint arXiv:2004.11826_ , 2020.
  * Dogra and Redman [2020] A. S. Dogra and W. T. Redman.  Optimizing neural networks via koopman operator theory.  _CoRR_ , abs/2006.02361, 2020.  URL https://arxiv.org/abs/2006.02361.
  * Duchi et al. [2011] J. Duchi, E. Hazan, and Y. Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12(61):2121–2159, 2011.  URL http://jmlr.org/papers/v12/duchi11a.html.
  * Folkestad et al. [2019] C. Folkestad, D. Pastor, I. Mezic, R. Mohr, M. Fonoberova, and J. Burdick.  Extended dynamic mode decomposition with learned koopman eigenfunctions for prediction and control, 2019.  URL https://arxiv.org/abs/1911.08751.
  * Fujii and Kawahara [2019] K. Fujii and Y. Kawahara.  Dynamic mode decomposition in vector-valued reproducing kernel hilbert spaces for extracting dynamical structure among observables.  _Neural Networks_ , 117:94–103, sep 2019.  doi: 10.1016/j.neunet.2019.04.020.  URL https://doi.org/10.1016%2Fj.neunet.2019.04.020.
  * Gilmer et al. [2017] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl.  Neural message passing for quantum chemistry.  _CoRR_ , abs/1704.01212, 2017.  URL http://arxiv.org/abs/1704.01212.
  * Gur-Ari et al. [2018] G. Gur-Ari, D. A. Roberts, and E. Dyer.  Gradient descent happens in a tiny subspace.  _arXiv preprint arXiv:1812.04754_ , 2018.
  * Han et al. [2020] Y. Han, W. Hao, and U. Vaidya.  Deep learning of koopman representation for control.  _CoRR_ , abs/2010.07546, 2020.  URL https://arxiv.org/abs/2010.07546.
  * Kaiser et al. [2018] E. Kaiser, J. N. Kutz, and S. L. Brunton.  Sparse identification of nonlinear dynamics for model predictive control in the low-data limit.  _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , 474(2219):20180335, nov 2018.  doi: 10.1098/rspa.2018.0335.  URL https://doi.org/10.1098%2Frspa.2018.0335.
  * Kingma and Ba [2015] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  In Y. Bengio and Y. LeCun, editors, _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.  URL http://arxiv.org/abs/1412.6980.
  * Kipf and Welling [2016] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  _CoRR_ , abs/1609.02907, 2016.  URL http://arxiv.org/abs/1609.02907.
  * Koopman [1931] B. O. Koopman.  Hamiltonian systems and transformations in hilbert space.  _Proceedings of the National Academy of Sciences of the United States of America_ , 17(5):315–318, 1931.  ISSN 00278424.  URL http://www.jstor.org/stable/86114.
  * Li et al. [2019] Y. Li, H. He, J. Wu, D. Katabi, and A. Torralba.  Learning compositional koopman operators for model-based control, 2019\.  URL https://arxiv.org/abs/1910.08264.
  * Luo et al. [2022] D. Luo, J. Shen, R. Dangovski, and M. Soljačić.  Koopman operator learning for accelerating quantum optimization and machine learning.  _arXiv preprint arXiv:2211.01365_ , 2022.
  * Lusch et al. [2018] B. Lusch, J. N. Kutz, and S. L. Brunton.  Deep learning for universal linear embeddings of nonlinear dynamics.  _Nature Communications_ , 9(1), 2018.  doi: 10.1038/s41467-018-07210-0.
  * Manojlovic et al. [2020] I. Manojlovic, M. Fonoberova, R. Mohr, A. Andrejcuk, Z. Drmac, Y. G. Kevrekidis, and I. Mezic.  Applications of koopman mode analysis to neural networks.  _CoRR_ , abs/2006.11765, 2020.  URL https://arxiv.org/abs/2006.11765.
  * Mauroy et al. [2020] A. Mauroy, Y. Susuki, and I. Mezić.  _Koopman operator in systems and control_.  Springer, 2020.
  * Mezić [2005] I. Mezić.  Spectral properties of dynamical systems, model reduction and decompositions.  _Nonlinear Dynamics_ , 41(1):309–325, 2005.
  * Otto and Rowley [2019] S. E. Otto and C. W. Rowley.  Linearly recurrent autoencoder networks for learning dynamics.  _SIAM Journal on Applied Dynamical Systems_ , 18(1):558–593, 2019.
  * Redman et al. [2021] W. T. Redman, M. Fonoberova, R. Mohr, I. G. Kevrekidis, and I. Mezic.  An operator theoretic perspective on pruning deep neural networks.  _CoRR_ , abs/2110.14856, 2021.  URL https://arxiv.org/abs/2110.14856.
  * Rowley et al. [2009] C. W. Rowley, I. Mezić, S. Bagheri, P. Schlatter, and D. S. Henningson.  Spectral analysis of nonlinear flows.  _Journal of fluid mechanics_ , 641:115–127, 2009.
  * Schmid [2010] P. J. Schmid.  Dynamic mode decomposition of numerical and experimental data.  _Journal of fluid mechanics_ , 656:5–28, 2010.
  * Shi and Meng [2022] H. Shi and M. Q. H. Meng.  Deep koopman operator with control for nonlinear systems, 2022.  URL https://arxiv.org/abs/2202.08004.
  * Shi et al. [2020] Y. Shi, Z. Huang, S. Feng, H. Zhong, W. Wang, and Y. Sun.  Masked label prediction: Unified message passing model for semi-supervised classification, 2020.  URL https://arxiv.org/abs/2009.03509.
  * Simanek et al. [2022] P. Simanek, D. Vasata, and P. Kordik.  Learning to optimize with dynamic mode decomposition.  In _2022 International Joint Conference on Neural Networks ({IJCNN})_. IEEE, jul 2022.  doi: 10.1109/ijcnn55064.2022.9892364.  URL https://doi.org/10.1109%2Fijcnn55064.2022.9892364.
  * Tano et al. [2020] M. E. Tano, G. D. Portwood, and J. C. Ragusa.  Accelerating training in artificial neural networks with dynamic mode decomposition.  _CoRR_ , abs/2006.14371, 2020.  URL https://arxiv.org/abs/2006.14371.
  * Tu et al. [2014a] J. H. Tu, , C. W. Rowley, D. M. Luchtenburg, S. L. Brunton, and J. N. K. and.  On dynamic mode decomposition: Theory and applications.  _Journal of Computational Dynamics_ , 1(2):391–421, 2014a.  doi: 10.3934/jcd.2014.1.391.  URL https://doi.org/10.3934%2Fjcd.2014.1.391.
  * Tu et al. [2014b] J. H. Tu, , C. W. Rowley, D. M. Luchtenburg, S. L. Brunton, and J. N. K. and.  On dynamic mode decomposition: Theory and applications.  _Journal of Computational Dynamics_ , 1(2):391–421, 2014b.  doi: 10.3934/jcd.2014.1.391.  URL https://doi.org/10.3934%2Fjcd.2014.1.391.
  * Turjeman et al. [2022] R. Turjeman, T. Berkov, I. Cohen, and G. Gilboa.  The underlying correlated dynamics in neural training.  _arXiv preprint arXiv:2212.09040_ , 2022.
  * Veličković et al. [2017] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio.  Graph attention networks, 2017.  URL https://arxiv.org/abs/1710.10903.
  * Williams et al. [2015] M. O. Williams, I. G. Kevrekidis, and C. W. Rowley.  A data–driven approximation of the koopman operator: Extending dynamic mode decomposition.  _Journal of Nonlinear Science_ , 25(6):1307–1346, jun 2015.  doi: 10.1007/s00332-015-9258-5.  URL https://doi.org/10.1007%2Fs00332-015-9258-5.
  * Yeung et al. [2019] E. Yeung, S. Kundu, and N. Hodas.  Learning deep neural network representations for koopman operators of nonlinear dynamical systems.  In _2019 American Control Conference (ACC)_ , pages 4832–4839. IEEE, 2019.
  * Zeiler [2012] M. D. Zeiler.  ADADELTA: an adaptive learning rate method.  _CoRR_ , abs/1212.5701, 2012.  URL http://arxiv.org/abs/1212.5701.

##  Appendix A Datasets of Neural Network Training Trajectories

Different tasks are formulated to study the dynamics prediction models’
abilities and limitations. Neural networks of various depths, equipped with
different types of non-linearity, are trained to tackle the tasks. Trajectory
datasets are created by training the neural networks with random initial
conditions for a fixed number of epochs. After each epoch, weights, biases,
and training losses are collected to form the training trajectories.

The following is the list of tasks studied in the experiments:

Linear regression The linear regression problem is based on a synthetic
dataset generated using the formula:

$y_{i}=\mathbf{w}\cdot\mathbf{x}_{i}+b+\epsilon_{i}$

with $\epsilon_{i}$ sampled from a Gaussian distribution. 20 features are
synthesied, and 2000 sampels are collected. 1-layer feedforward network is
trained for this problem.

Classification The task is based on the classic wine dataset, which results
from a chemical analysis of wines grown in the same region in Italy but
derived from 3 different cultivars uci [1991]. The task is to classify each
wine into 1 of the 3 classes using the quantities of its 13 constituents. The
dataset consists of 178 samples.

Two feedforward NNs are trained for this problem:

  * •

2-layer Linear $\rightarrow$ Activation $\rightarrow$ Linear $\rightarrow$
Softmax

  * •

3-layer Linear $\rightarrow$ Activation $\rightarrow$ Linear $\rightarrow$
Activation $\rightarrow$ Linear $\rightarrow$ Softmax

Image classification The task is based on the digits dataset, which includes
1800 handwritten digits in 8x8 bitmaps uci [1998]. The objective is to
classify each bitmap as 1 of the 10 digits.

This task aims to study the models’ performance in predicting the dynamics of
convolutional neural networks (CNN). To reduce memory usage, only images from
2 classes are included so that the CNN can be slightly scaled down.

Define a convolutional layer as ”Convolution $\rightarrow$ Activation
$\rightarrow$ Average Pooling”. Two CNNs are trained for this problem:

  * •

1-conv 2-fc CNN Convolutional layer $\rightarrow$ Linear $\rightarrow$
Activation $\rightarrow$ Linear

  * •

2-conv 1-fc CNN Convolutional layer $\rightarrow$ Convolutional layer
$\rightarrow$ Linear

DE solver A neural network differential equation (DE) solver is trained to
solve for $f(x)$, where:

$f^{\prime}(x)-f(x)=y$

with $f(1)=0$ as the initial conditions.

The DE solver in the experiment comprises 3 layers, each separated by a non-
linear activation layer. The inputs are uniformly sampled over a range on
which the loss is evaluated.

The tasks are selected to include both synthetic and real-world problems.
Input normalisation (i.e., standardising each dimension to a mean of 0 and
variance of 1) is applied to some task datasets to make the weights and biases
evolve within a narrower range in training.

The initial weights and biases are sampled from $(-1,1)$. The neural networks
are then trained with mini-batch gradient descent so that the training process
corresponds precisely to the mathematical framework outlined in the last
chapter. To avoid complex dynamics (e.g., involving momentum), the SGD
(Stochastic Gradient Descent) optimiser is used in the study. In Appendix B,
some of these configurations are altered to analyse the models’ robustness to
variations.

To keep the training time of baselines within a reasonable limit, the weights
and biases are sampled per 10 epochs to shorten the trajectories. This
augmentation would have a minimal effect on the predictions, as the objective
of the predictions is to capture the overall trends instead of transient
fluctuations.

##  Appendix B Robustness to Architectural and Training Variations

This section aims to showcase the robustness of our KMPNN autoencoder when
confronted with training trajectories with various specifications.

###  B.1 Non-linearity

To investigate the versatility of our KMPNN autoencoder on different non-
linearity types, the model is evaluated on the training trajectories of the
same neural architectures equipped with different non-linear activation
functions. The model is again evaluated on the dynamics of a 2-layer MLP and a
3-layer CNN. The optimisation performances $r$ are as follows:

| ELU ($\alpha=1$) | ReLU | Leaky ReLU | Sigmoid | Tanh
---|---|---|---|---|---
Classification: 2-fc | 98.6% | 97.3% | 96.7% | 99.2% | 98.5%
Image: 1-conv-2-fc | 96.9% | 83.6% | 93.5% | 100.6% | 98.0%

In general, the losses of neural architectures equipped with sigmoid, tanh,
and ELU are better predicted than ReLU and leaky ReLU. This might suggest that
smoothness of activation functions play a role here since sigmoid, tanh, and
ELU (with $\alpha=1$) are smooth functions, while the gradients of ReLU and
leaky ReLU are discontinuous at $x=0$. Nevertheless, the loss performances are
robust regardless of the choice of activation functions.

###  B.2 Optimisers

In this section, our approach is evaluated on the training trajectories
produced by 4 different optimisers, which include SGD, Adagrad Duchi et al.
[2011], Adadelta Zeiler [2012] and Adam Kingma and Ba [2015]. The optimisation
performances are:

| SGD | Adagrad | Adadelta | Adam
---|---|---|---|---
Classification: 2-fc | 98.6% | 98.1% | 94.2% | 98.8%
Image: 1-conv-2-fc | 100.6% | 95.7% | 97.7% | 99.2%

As shown, our approach is robust across the choice of optimisers.

###  B.3 Stochastic Training

Recall that the training trajectories used throughout the experiments are
generated with mini-batch gradient descent, i.e., training data are grouped
into small batches for multiple passes in an epoch. However, most training
pipelines now use shuffled batches to improve generalisation. To show that our
approach is robust against variance among random mini-batches, this subsection
reports the optimisation performances of our KMPNN autoencoder when applied to
stochastic trajectories:

| SGD | Adagrad | Adadelta | Adam
---|---|---|---|---
Classification: 2-fc | 99.9% | 97.4% | 99.7% | 99.6%
Image: 1-conv-2-fc | 97.8% | 99.4% | 99.3% | 99.1%

The results show that our approach can withstand variances among random mini-
batches in training data.


11institutetext: MIPS, University of Haute-Alsace, Mulhouse, France
22institutetext: MDPI AG, Basel, Switzerland

#  Towards a Semantic Search Engine for
Scientific Articles

Bastien Latard 1122 Jonathan Weber 11
Germain Forestier 11 Michel Hassenforder 11

###### Abstract

Because of the data deluge in scientific publication, finding relevant
information is getting harder and harder for researchers and readers. Building
an enhanced scientific search engine by taking semantic relations into account
poses a great challenge. As a starting point, semantic relations between
keywords from scientific articles could be extracted in order to classify
articles. This might help later in the process of browsing and searching for
content in a meaningful scientific way. Indeed, by connecting keywords, the
context of the article can be extracted. This paper aims to provide ideas to
build such a smart search engine and describes the initial contributions
towards achieving such an ambitious goal.

##  1 Introduction

Keeping up-to-date in a specific research field is a tedious and complex task.
This is mandatory as it allows researchers to increase their knowledge on a
domain and acquire latest ideas. Hence, choosing the correct approach is the
first step of any research work. Despite—or because of—the data deluge in
scientific publication, researchers spend a significant amount of time
searching for articles related to their scientific interests.

An editorial from Nature [1] clearly expressed the continued frustration of
the scientific community concerning the incredible potential that text mining
of scientific literature represents. However, text miners often face the
barrier of publishers’ legal restrictions (i.e., closed access). The average
growth of scientific literature is estimated to be 3 million new articles per
year from journals and conferences over the last 4 years, with 3.3 million
articles produced in 2016 (http://www.scilit.net). This massive amount of data
is published by more than 6000 publishers in around 47,000 scientific
journals. These de-centralised and separated platforms further complicate the
research process because scientists are unable to go through them all in order
to search for relevant articles. Thus, they have to rely on big databases or
indexing companies which provide either an incomplete corpus due to selection
criteria or only display articles from their own platforms. Moreover, their
search engines often offer very limited search functionalities, and this is
the problem we want to tackle.

To tackle this problem, our approach consists in using semantic relations
between keywords to extract the main categories of the articles. This approach
simultaneously validates both the context of the article and the context of
the word, thus providing the correct category. Effendy and Yap [2] discussed
the potential of using semantic mining tools to extract the best category of a
conference. This is exactly what our framework aims to do.

##  2 Method

Our approach uses BabelNet [3] which is a multilingual lexicographic and
encyclopaedic database based on the smart superposition of semantic lexicons
(WordNet, VerbNet) together with other collaborative databases (Wikipedia and
other Wiki data). A query for a term through BabelNet returns ”dictionary
entries”, synonyms, categories or domains. Each synset $S$ contains the
relative categories $C$, domains $D$ and synonyms $syn$ within the specific
concept:

$S=\\{C,D,syn\\}$ (1)

Assuming that synonyms of keywords might be an interesting way to connect
several articles, BabelNet is the knowledge database on which our framework
will rely. However, BabelNet lacks specificity and searching for one word can
return synsets from various different contexts. For example, ”flight” returns
36 synsets, from a South Korean movie to the verb ’to fly’. Consequently, a
method to filter out unrelated synsets is mandatory.

Because synonyms are too specific, and domains are too general, categories
have been naturally chosen in order to identify overlapping between synsets
from different keywords. Indeed, if several keywords share the same category,
then this is potentially the correct category in regards to the article
context. In addition, the greater the number of keywords sharing the same
category, the higher the confidence. Thus, connecting the returned synsets
based on their categories is an interesting way to naturally filter out all of
the unrelated synsets.

This approach does filter some content, but still returns ”living people;
English-language films; celestial mechanics; American films” as the main
categories for keywords ”nonlocal gravity; celestial mechanics; dark matter”.
Constant noise (*_singer, *_album, etc.), meaningless in our scientific
context, has been identified. A parameter can now be set in order to force the
automatic filtering of identified noise. Most of the remaining noise is
finally naturally filtered out, and ”celestial mechanics” is finally returned
as the main category.

Our final goal is to apply this valuable added knowledge to all articles from
the scientific literature database, Scilit (http://www.scilit.net), developed
by MDPI (http://www.mdpi.com). To validate our approach, a manual analysis on
a subset of 595 articles from seven journals (six about Physical Science and
one about Pediatrics) has been conducted. We evaluated the correctness of the
categories based on the connection of keywords by their synsets. This approach
provides good precision—from 96% to 100%—depending on the threshold which
identify the data as correct not. Indeed, strictly selecting only categories
shared by three different keywords or more leads to a high degree of
confidence (100% precision), but a recall of 9%. By being more tolerant and
considering all categories shared by at least two keywords, precision slightly
decreased (96%) but we significantly gain in recall (47%). Moreover, similar
proportions are observed for Children, the journal about Pediatrics (from 100%
to 92%). This validates that our approach may be used in several domains.

The main drawback of our approach is that correct categories have been
identified for only 22% of the articles within the subset. Figure 1
illustrates the reason for the law recall and coverage of our approach.

Figure 1: Limits of the exact search: only one keyword from three return data.

One of the reasons for this law coverage is that BabelNet often returns no
result for composed keywords (multi-word keywords), as shown in Figure 1,
where no data is returned for two of three keywords. In our approach—proposing
only categories shared by at least two keywords—the degree of confidence is
not high enough to return the categories. We will investigate further a way to
propose some categories from these composed keywords in our future work. In
doing so, we aim to significantly gain in recall, and cover many more
articles.

##  3 Perspectives

Making scientific recommender systems smarter is crucial in order to help
scientists in their mandatory and tedious bibliographical research phase. The
approach proposed could be the first step in building such a smart system.
Indeed, analysing the correctness of the main category based on the
overlapping of the keywords category confirms the logic of our approach. In
the future, we plan to extend the search in order to extract categories from
composed keywords. Splitting on spaces would provide some data for sub-
keywords. Then, applying the same logic as described in our approach (i.e.,
connect by common category) will filter out unrelated items, and categories
from connected items might be used for the global category connection. By
taking the example from Figure 1, splitting ”flapping flight” on spaces will
return 3 and 25 synsets, respectively for ”flapping” and ”flight”:

Figure 2: The category ”Aerodynamics” is returned as the main category of
”flapping flight”. Other categories are filtered out by this connection.

This further search will successfully identify ”Aerodynamics” as the main
category of ”flapping flight”. Thus, our approach would connect ”Aerodynamics”
based on both keywords. Extracting the part-of-speech (with a syntactical
analyser like SyntaxNet [4] or CoreNLP [5]) from long keywords could be an
interesting extra source of information for refining requests on BabelNet.
Finally, Figure 3 shows the main logic of our next contribution: to process in
a smarter way the keywords that do not return any satisfactory results. Later,
we might also generate a graph inherited from the BabelNet’s synsets as in [6]

Figure 3: Illustration of the general logic of our approach in a future work

## References

  * [1] (Editorial), N.:  Gold in the text?  Nature 483(7388) (March 2012) 124–124
  * [2] Effendy, S., Yap, R.H.C.:  The Problem of Categorizing Conferences in Computer Science.  In: TPDL, Springer (September 2016) 447–450
  * [3] Navigli, R., Ponzetto, S.P.:  BabelNet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network.  Artificial Intelligence 193 (December 2012) 217–250
  * [4] Andor, D., Alberti, C., Weiss, D., Severyn, A., Presta, A., Ganchev, K., Petrov, S., Collins, M.:  Globally normalized transition-based neural networks.  ACL (2016)
  * [5] Manning, C.D., Surdeanu, M., Bauer, J., Finkel, J.R., Bethard, S., McClosky, D.:  The Stanford CoreNLP Natural Language Processing Toolkit., ACL (2014) 55–60
  * [6] Franco-Salvador, M., Cruz, F.L., Troyano, J.A., Rosso, P.:  Cross-domain polarity classification using a knowledge-enhanced meta-classifier.  Knowledge-Based Systems 86 (September 2015) 46–56