# Reconstructing Network Inputs with Additive Perturbation Signatures

Nick Moran, Chiraag Juvekar
Algorithmic Systems Group, Analog Devices
125 Summer Street, Boston MA
<EMAIL_ADDRESS><EMAIL_ADDRESS>
##  1 Introduction

In recent years, deep neural networks have delivered state-of-the-art results
on a wide variety of tasks in computer vision, natural language processing and
many other subfields. At the same time, the models driving this success have
become larger and more complex, requiring ever-growing computing power to
train and run. As a result, we have seen the rise of Machine Learning as a
Service (MLaaS)[1], in which models are trained and evaluated by third parties
rather than the end user.

This trend presents significant privacy concerns with regards to both the
training data used to build models, as well as the input data at inference
time. Given various levels of access to a trained model, its parameters,
and/or its outputs, how much information can an adversary recover about its
training data or its inputs?

In this work, we present preliminary results demonstrating the ability to
recover a significant amount of information about secret model inputs given
only very limited access to model outputs and the ability evaluate the model
on additive perturbations to the input.

##  2 Background

Significant work has been done on understanding and mitigating the ability of
an adversary to recover training data given acess to the trained model [4][6].
Less work has been done on the related problem of recovering inference inputs
given access to some subset of model outputs. Most similar to our setting is
the method presented in [8], in which model inputs are recovered given access
to a truncated set of class logits output by the model.

Homomorphic encryption has been proposed as a way to allow an untrusted third
party to perform inference on sensitive data in a way that limits disclosure
of inputs [2]. In this setting, the model owner receives only the encrypted
inputs, and may also receive only a limited amount of information about the
network outputs. In this work, we investigate whether even this limited
information is sufficient to recover sensitive inputs.

Figure 1: The method for calculating $\epsilon_{i}$ for a particular noise
direction. The chart shows how class confidences change as $\epsilon$
increases. The point at which the original class is no longer the most
probable defines the value of $\epsilon_{i}$.

##  3 Attack Setting & Notation

We consider the following scenario. A model $M$ is trained to perform a
classification task and made available to users. In this work we will
specifically consider a $M$ to be a convolutional neural network (CNN), and
will present results from the MNIST[3] classification task as a simple
baseline. A user has a sensitive input, $X$ (we will use $x$ to represent
other non-sensitive inputs), on which they would like to evaluate $M$. We will
denote by $M(X)$ the identity of the model’s top-1 prediction for $X$.
Inference is performed under encryption such that $X$ is kept secret even from
the owner of $M$. An adversary attempts to recover $X$ given access to the
following capabilities. The adversary (who may be the same as the model owner)
has black-box access to evaluate $M$ on their own inputs, and is further
capable of inducing the evaluation of $M$ on additive perturbations of $X$,
$\hat{X}=X+N$, where $N$ is chosen by the adversary, and can detect only
whether $M(X)\stackrel{{\scriptstyle?}}{{=}}M(\hat{X})$. In other words, the
adversary does not know the actual value of the most-probable class, neither
for $X$ nor $\hat{X}$. The goal of the adversary is to recover as much
information as possible about $X$.

This scenario is inspired by the setting of inference under homomorphic
encryption, in which the additive homomorphic property allows the injection of
additive perturbations to the input without exposing the initial value of the
input. In such a setting, the model’s final output may similarly be encrypted,
but changes in the top class may be exposed by changes in some down-stream
behavior. We note also that in many settings, an adversary may well have
access to the final output, and we should expect that access to such
information will further enhance the adversary’s capabilities.

##  4 Method

Our method works by measuring the sensitivity of the model to additive
perturbations to $X$ in a set of fixed directions, and training a decoder
model to predict the pixel-values of $X$ given these sensitivities. We begin
by selecting a set (in this work we use a set of size 100) of random
perturbation directions, which we will term $N=\\{N_{i}\\}$. Each perturbation
direction is a real-valued tensor of the same shape as $X$; in the case of
MNIST they are of shape $28\times 28$.

For a given input image, $x$, we compute a set of minimal $\epsilon_{i}$ such
that $M(x+\epsilon_{i}\cdot N_{i})\neq M(x)$ and $\epsilon_{i}>0$. This set
forms a fingerprint vector $E_{x}$ = [$\epsilon_{0}$, $\epsilon_{1}$,…] which
is the input to our decoder. This process is shown in Figure 1.

To train our decoder, we build a training set of ($E_{x}$,$x$) pairs. In this
work, we will assume for simplicity that the adversary has access to the same
training set as was used to train $M$, although this need not be the case. We
will use a variant of the generator architecture from [5], in which the input
vector is projected into a tensor with small spatial extent, which is then
upsampled and refined into a full-resolution image using convolution transpose
layers. The decoder is trained to minimize the $L_{2}$ error between the
ground truth $x$ and its reconstructions from $E_{x}$.

##  5 Results

Figure 2: Reconstructions (bottom row) of held-out test data (top row) from
100-element signatures.

Figure 2 shows the results of our method on images from the MNIST test set. We
observe first that the decoder is clearly able to recover the correct digit
class of each image, despite receiving only $E_{x}$ as input with no
information about class identities. Further, the decoder is able to recover a
significant amount of stylistic information such as digit angle.

Figure 3: Reconstructions (bottom row) of a single digit type and
corresponding original digits (top row).

Figure 3 shows the results of our method applied to a variety of samples of a
single digit type. These results more clearly demonstrate the ability of our
method to recover additional information beyond the image class alone.
Differences in orientation, stroke width, and curvature are all apparent in
the recovered images.

##  6 Future Work

Although the MNIST dataset is convenient for rapid prototyping, it also may
present a significantly easier task than other, more realistic datasets. On
larger datasets, it may not be possible to perform pixel-level recovery of
inputs. Instead, we hope to recover other, lower-dimensional attributes of the
data.

We currently select the perturbation directions uniformly at random. However,
we hypothesize that more cleverly-chosen perturbations may produce more
informative signals for the decoder. In particular, we intend to explore
directions derived from adversarial attacks[7], as well as directions obtained
by subtracting the centroids of training classes.

Finally, we are exploring possible defenses to this attack, either by training
models which are robust to this sort of inversion, or by altering inputs to
fool the decoder.

## References

  * [1] David Chappell.  Introducing Azure machine learning.  2015\.
  * [2] Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing.  Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy.  In International Conference on Machine Learning, pages 201–210, 2016.
  * [3] Yann LeCun.  The MNIST database of handwritten digits.  http://yann. lecun. com/exdb/mnist/.
  * [4] Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar.  Semi-supervised knowledge transfer for deep learning from private training data.  arXiv preprint arXiv:1610.05755, 2016.
  * [5] Alec Radford, Luke Metz, and Soumith Chintala.  Unsupervised representation learning with deep convolutional generative adversarial networks.  arXiv preprint arXiv:1511.06434, 2015.
  * [6] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In 2017 IEEE Symposium on Security and Privacy (SP), pages 3–18. IEEE, 2017.
  * [7] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199, 2013.
  * [8] Ziqi Yang, Ee-Chien Chang, and Zhenkai Liang.  Adversarial neural network inversion via auxiliary knowledge alignment.  arXiv preprint arXiv:1902.08552, 2019.


# Neural Embeddings for Protein Graphs

Francesco Ceccarelli
University of Cambridge
<EMAIL_ADDRESS>
&Lorenzo Giusti
Sapienza University
<EMAIL_ADDRESS>
Sean B. Holden
University of Cambridge
<EMAIL_ADDRESS>
&Pietro Liò
University of Cambridge
<EMAIL_ADDRESS>
The work was performed while the author was in Cambridge.

###### Abstract

Proteins perform much of the work in living organisms, and consequently the
development of efficient computational methods for protein representation is
essential for advancing large-scale biological research. Most current
approaches struggle to efficiently integrate the wealth of information
contained in the protein sequence and structure. In this paper, we propose a
novel framework for embedding protein graphs in geometric vector spaces, by
learning an encoder function that preserves the structural distance between
protein graphs. Utilizing Graph Neural Networks (GNNs) and Large Language
Models (LLMs), the proposed framework generates structure- and sequence-aware
protein representations. We demonstrate that our embeddings are successful in
the task of comparing protein structures, while providing a significant speed-
up compared to traditional approaches based on structural alignment. Our
framework achieves remarkable results in the task of protein structure
classification; in particular, when compared to other work, the proposed
method shows an average F1-Score improvement of 26% on out-of-distribution
(OOD) samples and of 32% when tested on samples coming from the same
distribution as the training data. Our approach finds applications in areas
such as drug prioritization, drug re-purposing, disease sub-type analysis and
elsewhere.

##  1 Introduction

Proteins are organic macro-molecules made up of twenty standard amino acids.
Almost all interactions and reactions which occur in living organisms, from
signal transduction, gene transcription and immune function to catalysis of
chemical reactions, involve proteins [1]. The comparison of proteins and their
structures is an essential task in bioinformatics, providing support for
protein structure prediction [2], the study of protein-protein docking [3],
structure-based protein function prediction [4] and many further tasks.
Considering the large quantity of protein data stored in the Protein Data Bank
(PDB) [5] and the rapid development of methods for performing protein
structure prediction (for example, AlphaFold2 [6]), it is desirable to develop
methods capable of efficiently comparing the tertiary structures of proteins.

Generally, protein comparison methods can be divided into two classes:
alignment-based methods [7, 8, 9] and alignment-free methods [10, 11, 12, 13].
The former aim at finding the optimal structural superposition of two
proteins. A scoring function is then used to measure the distance between each
pair of superimposed residues. For such methods (for example [14, 15]) the
superposition of the atomic structures is the main bottleneck as it has been
proven to be an NP-hard problem [16]. On the other hand, alignment-free
methods try to represent each protein in the form of a descriptor, and then to
measure the distance between pairs of descriptors [10]. Descriptors need to
satisfy two requirements: 1) their size should be fixed and independent of the
length of proteins; 2) they should be invariant to rotation and translation of
proteins.

The template modeling score (TM-score) [17] is a widely used metric for
assessing the structural similarity between two proteins. It is based on the
root-mean-square deviation (RMSD) of the atomic positions in the proteins, but
considers the lengths of the proteins and the number of residues that can be
superimposed. TM-score has been shown to be highly correlated with the
similarity of protein structures and can be used to identify structurally
similar proteins, even when they have low sequence similarity. Unfortunately,
computing TM-scores is computationally intractable even for relatively small
numbers of proteins. TM-align [15], one of the popular alignment-based
methods, takes about 0.5 seconds for one structural alignment on a 1.26 GHz
PIII processor. As such, computing TM-scores for existing databases,
containing data for millions of proteins, is unaffordable. While several deep
learning methods for protein comparison have been developed (for example,
DeepFold [18] and GraSR [10]) they suffer from major drawbacks: 1) they are
trained by framing the protein comparison task as a classification
problem—that is, predicting if two proteins are structurally similar—and hence
fail to directly incorporate TM-scores in the loss function formulation; 2)
they produce latent representations (embeddings) which do not integrate the
information contained in the protein sequences and structures; 3) they usually
do not exploit the inductive bias induced by the topology of graph-structured
proteins, and they fail to consider different geometries of the latent space
to match well the underlying data distribution.

In this paper, we address the aforementioned limitations of current protein
embedding methods by proposing an efficient and accurate technique that
integrates both protein sequence and structure information. In detail, we
first construct protein graphs where each node represents an amino acid in the
protein sequence. We then generate features for each amino acid (node in the
graph) using Large Language Models (LLMs) before applying Graph Neural
Networks (GNNs) to embed the protein graphs in geometric vector spaces while
combining structural and sequence information. By incorporating TM-scores in
the formulation of the loss function, the trained graph models are able to
learn a mapping that preserves the distance between the input protein graphs,
providing a way to quickly compute similarities for every pair of unseen
proteins. We evaluated the proposed approach and its ability to generate
meaningful embeddings for downstream tasks on two protein datasets. On both,
the proposed approach reached good results, outperforming other current state-
of-the-art methods on the task of structural classification of proteins on the
SCOPe dataset [19].

Contribution The main contributions of this paper can be summarised as follow:
(i) A novel learning framework for generating protein representations in
geometric vector spaces by merging structural and sequence information using
GNNs and LLMs. (ii) A quick and efficient method for similarity computation
between any pair of proteins. (iii) An evaluation of the ability of our
embeddings, in both supervised and unsupervised settings, to solve downstream
protein classification tasks, and a demonstration of their superior
performance when compared to current state-of-the-art methods. Our approach
finds a plethora of applications in the fields of bioinformatics and drug
discovery.

##  2 Background and Related Work

Several alignment-based methods have been proposed over the years, each
exploiting different heuristics to speed up the alignment process. For
example, in DALI [20], Monte Carlo optimization is used to search for the best
structural alignment. In [8] the authors proposed combinatorial extension (CE)
for similarity evaluation and path extension. An iterative heuristic based on
the Needleman–Wunsch dynamic programming algorithm [21] is employed in TM-
align [15], SAL [22] and STRUCTAL [23]. Examples of alignment-free approaches
are Scaled Gauss Metric (SGM) [11] and the Secondary Structure Element
Footprint (SSEF) [13]. SGM treats the protein backbone as a space curve to
construct a geometric measure of the conformation of a protein, and then uses
this measure to provide a distance between protein shapes. SSEF splits the
protein into short consecutive fragments and then uses these fragments to
produce a vector representation of the protein structure as a whole. More
recently, methods based on deep learning have been developed for the task of
protein structure comparison. For instance, DeepFold [18] used a deep
convolutional neural network model trained with the max-margin ranking loss
function [24] to extract structural motif features of a protein, and learn a
fingerprint representation for each protein. Cosine similarity was then used
to measure the similiarity scores between proteins. DeepFold has a large
number of parameters, and fails to exploit the sequence information and the
topology of graph-structured data. GraSR [10] employs a contrastive learning
framework, GNNs and a raw node feature extraction method to perform protein
comparison. Compared to GraSR, we present a general framework to produce
representations of protein graphs where the distance in the embedding space is
correlated with the structural distance measured by TM-scores between graphs.
Finally, our approach extends the work presented in [25], which was limited to
biological sequence embeddings, to the realm of graph-structured data.

##  3 Material and Methods

The core approach, shown in Figure 1,

Figure 1: We learn an encoder function that preserves the structural distance,
measured by the TM-score, between two input proteins. We construct protein
graphs by combining sequence and structure information as shown in Figure 2. A
distance function $d$ defines the shape of the latent space. The generated
embeddings can be used for a variety of applications in bioinformatics and
drug discovery. (For simplicity, this Figure depicts a 3-dimensional latent
space.)

is to map graphs into a continuous space so that the distance between embedded
points reflects the distance between the original graphs measured by the TM-
scores. The main components of the proposed framework are the geometry of the
latent space, a graph encoder model, a sequence encoder model, and a loss
function. Details for each are as follows.

#### Latent space geometry

The distance function used ($d$ in Figure 1) defines the geometry of the
latent space into which embeddings are projected. In this work we provide a
comparison between Euclidean, Manhattan, Cosine and squared Euclidean
(referred to as Square) distances (details in Appendix B).

#### Graph encoder model

The encoder performs the task of mapping the input graphs to the embedding
space. A variety of models exist for this task, including linear, Multi-layer
Perceptron (MLP), LSTM [26], CNN [27] and Transformers [28]. Given the natural
representation of proteins as graphs, we chose GNNs as encoder models. We have
constructed the molecular graphs of proteins starting from PDB files. A PDB
file contains structural information such as 3D atomic coordinates. Let
$G=(V,E)$ be a graph representing a protein, where each node $v\in V$ is a
residue and interaction between the residues is described by an edge $e\in E$.
Two residues are connected if they have any pair of atoms (one from each
residue) separated by a Euclidean distance less than a threshold distance. The
typical cut-off, which we adopt in this work, is 6 angstroms (Å) [29].

#### Sequence encoder model

Given the graph representation of a protein, each node $v$ of the graph (each
residue) must be associated with a feature vector. Typically, features
extracted from protein sequences by means of LLMs have exhibited superior
performances compared to handcrafted features. We experimented with five
different sequence encoding methods: 1) a simple one-hot encoding of each
residue in the graph, 2) seven physicochemical properties of residues as
extracted by [30], which are assumed to influence the interactions between
proteins by creating hydrophobic forces or hydrogen bonds between them, 3) the
BLOcks SUbstitution Matrix (BLOSUM) [31], which counts the relative
frequencies of amino acids and their substitution probabilities, 4) features
extracted from protein sequences employing a pre-trained BERT-based
transformer model (ProBert [32]), and 5) node features extracted using a a
pre-trained LSTM-based language model (SeqVec [33]). Table 1

Table 1: Investigated node attributes and their dimensions. BERT and LSTM features are extracted using LLMs pre-trained on protein sequences (ProBert [32] and SeqVec [33]). Feature | Dimension
---|---
One hot encoding of amino acids | 20
Physicochemical properties | 7
BLOcks SUbstitution Matrix | 25
BERT-based language mod | 1024
LSTM-based language model | 1024

summarizes the node features and their dimensions, while Figure 2

Figure 2: Graph representation of a protein, which combines sequence and
structure. Starting from protein data (a PDB file from, for example, UniProt
[34] or PDB [5]), we extract protein sequence and structure information. We
construct graphs where each node represents an amino acid in the protein
sequence. We then generate features for each node in the graph using Large
Language Models pre-trained on protein sequences.

depicts the process of constructing a protein graph with node features,
starting from the corresponding protein data.

#### Loss function

The loss function used, which minimises the MSE between the graph distance and
its approximation as the distance between the embeddings, is

$L\left(\theta,G\right)=\sum_{g_{1},g_{2}\in
G}\left(\text{TM}\left(g_{1},g_{2}\right)-d\left(\text{GNN}_{\theta}\left(g_{1}\right),\text{GNN}_{\theta}\left(g_{2}\right)\right)\right)^{2}$
(1)

where $G$ is the training set of protein graphs and $\text{GNN}_{\theta}$ is
the graph encoder. The TM-score is a similarity metric in the range (0,1],
where 1 indicates a perfect match between two structures. Since the
formulation of the loss is expressed in terms of distances, we reformulate the
TM-scores as a distance metric by simply computing
$\text{TM}(g_{1},g_{2})=1-\text{TM}_{\text{score}}(g_{1},g_{2})$. By training
neural networks to minimize the loss in Equation 1, we encourage the networks
to produce latent representations such that the distance between these
representations is proportional to the structural distance between the input
graphs.

##  4 Protein Datasets

We evaluated the proposed approach on two protein datasets. First, we
downloaded the human proteome from UniProt111https://www.uniprot.org and sub-
selected 512 protein kinases. To obtain the TM-scores to train the graph
models, we evaluated the structural similarity using TM-align [15]. All-
against-all alignment yielded a dataset composed of 130,816 total comparisons.
Every kinase in the dataset is categorized in one of seven family groups: a)
AGC (63 proteins), b) CAMK (82 proteins), c) CK1 (12 proteins), d) CMGC (63
proteins), e) STE (48 proteins), f) TK (94 proteins), and g) TKL (43
proteins). The number of nodes in the graphs ranges from 253 to 2644, with an
average size of approximately 780 nodes. The average degree in the graphs is
approximately 204, the average diameter of the graphs is approximately 53
nodes and the maximum diameter is 227 nodes. We further used SCOPe v2.07
(March 2018) as a benchmark dataset [19]. This dataset contains 13,265 protein
domains classified in one of seven classes: a) all alpha proteins (2286
domains), b) all beta proteins (2757 domains), c) alpha and beta proteins
(a/b) (4148 domains), d) alpha and beta proteins (a+b) (3378 domains), e)
multi-domain proteins (alpha and beta) (279 domains), f) membrane and cell
surface proteins and peptides (213 domains), and g) small proteins (204
domains). We again used TM-align with all-against-all settings to construct a
dataset of approximately 170 millions comparisons. To reduce the computational
time and cost during training, we randomly sub-sampled 100 comparisons for
each protein to create a final dataset of 1,326,500 comparisons. For this
dataset, the number of nodes in the graphs ranges from 30 to 9800, with an
average size of approximately 1978 nodes. The average degree is approximately
90, the average diameter of the graphs is approximately 9 nodes and the
maximum diameter is 53 nodes. Compared to benchmark graph datasets (for
example [35] and [36]) we evaluated our approach on graphs of significantly
larger size (84 and 13 times more nodes than the molecular graphs in [35] and
[36], respectively).

##  5 Experimental Results

#### Experimental settings

We evaluate the proposed framework using Graph Convolutional Networks (GCNs)
[37], Graph Attention Networks (GATs) [38], and GraphSAGE [39] (Appendix A).
All the models were implemented with two graph layers in PyTorch geometric
[40] to learn protein embeddings of size 256. Adam optimizer [41] with a
learning rate of 0.001 was used to train the models for 100 epochs with a
patience of 10 epochs. The batch size was set to 100. We used 4 attention
heads in the GAT architecture. For each model, Rectified Linear Units (ReLUs)
[42] and Dropout [43] were applied after each layer, and mean pooling was
employed as readout function to obtain graph-level embeddings from the learned
node-level representations. Finally, each experiment was run with 3 different
seeds to provide uncertainty estimates.

#### Kinase embeddings

For the generation of the embeddings, we used 80% of the kinase proteins for
training and the remaining 20% for testing. Table 2

Table 2: MSE results for different feature types, distance functions and graph encoder models on the kinase dataset. We use gold , silver , and bronze  colors to indicate the first, second and third best performances, respectively. For each model, the best scores are consistently reached with LSTM-extracted features and Euclidean geometry of the embedding space. Across all models, GAT embeddings exhibit the best performance. For all the models, MSE scores are lower for features extracted by means of LLMs (BERT and LSTM) compared to handcrafted feature extraction methods (one-hot, biochemical and BLOSUM). Model | Feature | Distance
---|---|---
|  | Cosine | Euclidean | Manhattan | Square
GCN | One hot | $0.0194\pm 0.002$ | $0.0380\pm 0.003$ | $0.0192\pm 0.001$ | $0.0729\pm 0.004$
Physicochemical | $0.0343\pm 0.012$ | $0.0483\pm 0.009$ | $0.0397\pm 0.003$ | $0.1109\pm 0.007$
BLOSUM | $0.0327\pm 0.071$ | $0.0271\pm 0.043$ | $0.0450\pm 0.013$ | $0.0697\pm 0.023$
BERT | $0.0110\pm 0.003$ | $0.0103\pm 0.001$ | $0.0131\pm 0.006$ | $0.0138\pm 0.009$
LSTM | $0.0105\pm 0.002$ | $0.0088\pm 0.004$ | $0.0156\pm 0.001$ | $0.0107\pm 0.004$
GAT | One hot | $0.0171\pm 0.001$ | $0.0320\pm 0.012$ | $0.0171\pm 0.011$ | $0.0758\pm 0.009$
Physicochemical | $0.0295\pm 0.007$ | $0.0328\pm 0.006$ | $0.0220\pm 0.004$ | $0.0856\pm 0.023$
BLOSUM | $0.0245\pm 0.012$ | $0.0163\pm 0.009$ | $0.0124\pm 0.011$ | $0.0307\pm 0.009$
BERT | $0.0091\pm 0.018$ | $0.0095\pm 0.008$ | $0.0078\pm 0.009$ | $0.0133\pm 0.011$
LSTM | $0.0088\pm 0.009$ | $0.0073\pm 0.004$ | $0.0086\pm 0.006$ | $0.0101\pm 0.009$
Graph SAGE | One hot | $0.0243\pm 0.002$ | $0.0227\pm 0.011$ | $0.0156\pm 0.009$ | $0.0424\pm 0.010$
Physicochemical | $0.0301\pm 0.004$ | $0.0266\pm 0.008$ | $0.0310\pm 0.011$ | $0.0578\pm 0.009$
BLOSUM | $0.0285\pm 0.007$ | $0.0172\pm 0.008$ | $0.0342\pm 0.002$ | $0.0368\pm 0.007$
BERT | $0.0097\pm 0.011$ | $0.0089\pm 0.007$ | $0.0101\pm 0.007$ | $0.0107\pm 0.009$
LSTM | $0.0093\pm 0.003$ | $0.0084\pm 0.005$ | $0.0143\pm 0.007$ | $0.0094\pm 0.008$

shows the MSE values for the graph encoders, using different choices for
distance functions and node features. For each model, the best scores are
consistently reached with LSTM-extracted features and Euclidean geometry of
the embedding space. Across all models, GAT embeddings exhibit the lowest MSE,
followed by GarphSAGE and GCN. From Table 2, it is clear that using pre-
trained language models to extract node features from protein sequences leads
to better results. MSE scores for all distances across all encoder models are
lower when using BERT and LSTM features. Furthermore, the LSTM-extracted
features perform consistently better compared to the BERT ones. BLOSUM and
Physicochemical features are also usually associated with higher MSE for all
distances and models, indicating that they are poorly correlated to TM-scores.

#### Fast inference of TM-scores

We employed the trained GAT architectures from Table 2 to predict the TM-
scores for the kinase pairs in the test set. In Figure 3,

Figure 3: Actual versus predicted TM-scores. Using LSTM features and Euclidean
geometry (left) results in predictions which follow more tightly the red line
of the oracle compared to BLOSUM features in the Manhattan space (right).

we show the predicted versus actual TM-scores for two combinations of features
and embedding geometries. The left plot in Figure 3 uses LSTM-extracted
features and Euclidean space, while the right one shows predictions for BLOSUM
features and Manhattan space. The complete quantitative evaluations, measured
by Pearson correlation between model predictions and true TM-scores for all
distances and features, are reported in Appendix D.1. As in Table 2, the best
performances are reached when employing LSTM and BERT features while BLOSUM
and Physicochemical features lead to the poorest performances (Appendix D.1).
The highest correlation score, reflecting the results reported in Table 2, is
reached when employing LSTM features and Euclidean distance (Figure 3). It is
worth noticing that, for the 26,164 comparisons in the test set, the proposed
approach took roughly 120 seconds to compute TM-scores. Executing TM-align
with the same number of comparisons took 57,659 seconds ($\approx 16$ hours).
Details of the TM-score inference times for all the models are given in
Appendix D.2. The major speed-up provided by performing inference using
machine learning models makes the proposed approach applicable to datasets
comprising millions of proteins.

#### Ablation study: structure removal

Coupling GNNs with LLMs provides a means of integrating the information coming
from the structure and sequence of proteins. To analyse the benefits of
exploiting the topology induced by the graph structures, we performed an
ablation study which disregards such information. DeepSet [44] considers
objective functions defined on sets, that are invariant to permutations. Using
a DeepSet formulation, we constructed protein graphs with features where each
node is only connected to itself. As for the graph models, we trained DeepSet
to minimize the loss function in Equation 1 and report the results in Table 3.

Table 3: MSE values for an ablation study which disregards the topological information induced by the structure of the protein graphs. We use gold , silver , and bronze  colors to indicate the first, second and third best performances, respectively. By ignoring the neighborhood and the structural information, the MSEs are significantly higher (p-value of t-test $<0.05$) compared to GNNs. Model | Feature | Distance
---|---|---
|  | Cosine | Euclidean | Manhattan | Square
DeepSet | One Hot | $0.1742\pm 0.003$ | $0.0421\pm 0.002$ | $0.0358\pm 0.001$ | $0.0714\pm 0.003$
Physicochemical | $0.1766\pm 0.010$ | $0.0437\pm 0.006$ | $0.0464\pm 0.004$ | $0.0900\pm 0.006$
BLOSUM | $0.1553\pm 0.003$ | $0.0381\pm 0.009$ | $0.0558\pm 0.008$ | $0.0914\pm 0.008$
BERT features | $0.0132\pm 0.004$ | $0.0129\pm 0.005$ | $0.0192\pm 0.005$ | $0.0220\pm 0.004$
LSTM features | $0.0141\pm 0.003$ | $0.0116\pm 0.010$ | $0.0348\pm 0.006$ | $0.0200\pm 0.007$

Similarly to Table 2, the best MSE scores are reached when using LSTM features
and Euclidean geometry. The scores in Table 3, computed by disregarding the
graph connectivity and neighborhood information, are significantly higher than
those reported in Table 2 (p-value of t-test $<0.05$ compared to GCN, GAT and
GraphSAGE). By considering patterns of local connectivity and structural
topology, GNNs are able to learn better protein graph representations compared
to models which only exploit sequence-derived features.

#### Downstream task of kinase classification

To prove the usefulness of the learned embeddings for downstream tasks, we set
out to classify each kinase into one of the seven family groups (AGC, CAMK,
CK1, CMGC, STE, TK, TKL). Using the embeddings generated by the GAT models, we
trained an MLP, composed of 3 layers of size 128, 64 and 32 respectively, and
a SoftMax classification head. The accuracy of classification, computed as the
average result of 5-fold cross-validation, for each feature type and distance
function is reported in Figure 4.

Figure 4: Accuracy of classification for kinase family prediction using the
embeddings generated by the GAT models. The highest accuracy value of 93.7% is
reached with LSTM features and the Square distance function.

The results are consistent with Table 2: the best accuracies are obtained when
using LSTM- and BERT-extracted sequence features, while handcrafted feature
extraction methods (one hot, BLOSUM and physicochemical) provide the poorest
performance. The highest accuracy values of 93.7% and 92.48% are reached with
LSTM features and Square and Euclidean distance functions, respectively.

#### Embedding out of distribution samples

Being able to use pre-trained models for related or similar tasks is essential
in machine learning. We tested the ability of the proposed graph models to
generalize to new tasks by generating embeddings for the 13,265 proteins in
the SCOPe dataset after being trained only on kinase proteins. Given the
better performance provided by the use of LSTM features, in this section we
constructed protein graphs with LSTM attributes and used a 3-Layer MLP as
before to assign the GAT-generated protein embeddings from the SCOPe dataset
to the correct class. Results of this evaluation, measured as average F1-score
across 5 folds for each distance function, are shown in Table 4 (F1-Score out
of distribution (OOD)).

Table 4: Out of distribution (OOD) classification results on SCOPe proteins (F1-Score (OOD)). We use gold , silver , and bronze  colors to indicate the first, second and third best performances, respectively. Despite the different training data, the GAT model with Euclidean and Square geometry outperforms all other approaches trained on SCOPe proteins. Classification results for embeddings generated after training on SCOPe proteins are also shown (F1-Score); in this case, the proposed approach outperforms the others by a larger margin for all choices of latent geometries. Model | Distance | F1-Score (OOD) | F1-Score
---|---|---|---
GAT | Cosine | $0.6906\pm 0.0044$ | $0.8290\pm 0.008$
Euclidean | $0.8204\pm 0.006$ | $0.8557\pm 0.002$
Manhattan | $0.7055\pm 0.006$ | $0.8481\pm 0.007$
Square | $0.8185\pm 0.004$ | $0.8406\pm 0.006$
SGM [11] | - | - | $0.6289$
SSEF [13] | - | - | $0.4920$
DeepFold [18] | - | - | $0.7615$
GraSR [10] | - | - | $0.8124$

Euclidean and Square geometry of the embedding space exhibited the best
classification performances. Despite being trained on OOD samples, the
proposed framework with Euclidean and Square geometry still managed to
outperform the current state-of-the-art trained and tested on SCOPe proteins,
as shown in Table 4. The superior performance, despite the different training
data, suggests the ability of the proposed approach to learn meaningful
protein representations by 1) merging structural and sequence information into
a single pipeline, and 2) capturing different and relevant properties of the
geometries of the latent space into which embeddings are projected.

#### Protein structural classification

We constructed protein graphs with LSTM features and trained the proposed GAT
architectures on the SCOPe dataset. The resulting MSE scores are reported in
Appendix D.3. The lowest score was again reached when using Euclidean geometry
for the latent space. Using this model, we projected the protein embeddings
onto two dimensions using t-SNE [45] as shown in Figure 5.

Figure 5: t-SNE visualization of the learned embeddings, coloured by protein
structural family. The proposed approach generates protein embeddings which
recapitulate the different families in the SCOPe dataset.

The high-level structural classes as defined in SCOPe were captured by the
proposed embeddings. While not directly trained for this task, combining
structural and sequence information allowed us to identify small, local
clusters representing the different protein families in the SCOPe dataset. We
employed supervised learning and trained a 3-layer MLP classifier to label
each protein embedding in the correct family. Results of this evaluation,
measured as average F1-score across 5 folds, are shown in Table 4 (F1-Score).
When directly trained on SCOPe proteins, the proposed approach outperforms the
others by a large margin for all choices of geometries (Table 4).

#### Multimodal (sequence and structure) phylogenetic reconstruction

Discovering the hierarchical structure defined by evolutionary history is
pivotal in numerous biological applications [46]. Inference of phylogeny is
traditionally performed using sequence similarity. Here, we explore the
ability of the proposed embeddings to recapitulate such hierarchy in
unsupervised settings. To this end, we downloaded P53 tumour proteins from 20
different organisms from UniProt [34] and generated protein embeddings using
our GAT architecture pre-trained on SCOPe proteins. Hierarchical clustering of
these embeddings, shown in Appendix E, demonstrates that the proposed
multimodal combination results in a consistent evolutionary tree, extending
phylogenetic analysis from sequence only to a combination of structure and
sequence.

##  6 Conclusion and Future Developments

#### Limitations

We acknowledge several limitations of our work. First, the training of the
proposed models relies on the availability of structural distance scores
between protein graphs. While computing these is too expensive for large-scale
analysis, it is feasible to produce sufficient structural comparisons to build
a training set. In addition, more complex geometries like hyperbolic [47] or
product spaces [48] could be able to capture more expressive protein
representations. Finally, our approach is an alignment-free method; while
faster, due to the lack of structural alignment, the accuracy of alignment-
free methods is generally inferior to alignment-based methods. Using deep
learning architectures to extract accurate superposition information could
prove beneficial for fast and more accurate protein structural comparisons.

#### Broader Impacts

This work proposes a novel and efficient framework for comparing and analyzing
protein structures. By exploiting the power of GNNs and LLMs, we generated
embeddings that capture both structure and sequence information, and
demonstrated that these lower-dimensional representations are useful to
accurately solve downstream tasks of protein classification. A wide range of
biomedical and chemical applications would benefit from the accurate
representation of protein structures, such as molecular design [49], protein
property prediction [50], protein-protein and protein-ligand interaction
prediction [51, 52]. Importantly, protein structures play a critical role in
drug discovery, as they are often the target of drug molecules. The
effectiveness of a drug and its propensity to cause unintended effects depend
on how well it binds and specifically interacts with its intended target [50].
Measuring these factors involves expensive and time-consuming experiments. To
speed up the study of drug-target interactions, learning to efficiently
represent proteins is pivotal in modelling the protein targets of small
molecules and their binding affinities and specificities [53, 54]. Several
other examples of areas of application of the proposed approach are given in
Appendix F.

#### Conclusion

In this paper, we presented a novel framework for generating both structure-
and sequence-aware protein representations. We mapped protein graphs with
sequence attributes into geometric vector spaces, and showed the importance of
considering different geometries of the latent space to match the underlying
data distributions. We showed that the generated embeddings are successful in
the task of protein structure comparison, while providing an accurate and
efficient way to compute similarity scores for large-scale datasets, compared
to traditional approaches (Appendix D.2). The protein graph representations
generated by our approach showed state-of-the-art results for the task of
protein structural classification on the SCOPe dataset. This work opens
opportunities for future research, with potential for significant
contributions to the fields of bioinformatics, structural protein
representation and drug discovery (Appendix F).

#### Future Developments

While evaluated on the task of protein structure comparison, the proposed
framework offers a general approach to project input graphs into geometric
spaces. Assessing its capabilities when applied to small molecules (for
example drugs) and omics data is left for future work. Furthermore,
topological deep learning [55] is a rapidly-emerging area of research whose
success has been shown in a wide range of areas [56, 57, 58, 59]. Compared to
GNNs, which model the pairwise interactions on graph-structured data, several
recent approaches consider more complex topological spaces such as simplicial
complexes [60] or cell complexes [61]. Developing new strategies for graph
representation which exploit higher-order structures could prove more suitable
for modelling real-world complex systems, such as protein and gene regulatory
networks.

## References

  * Morris et al. [2022] Rhiannon Morris, Katrina A Black, and Elliott J Stollar.  Uncovering protein function: from classification to complexes.  _Essays in Biochemistry_ , 66(3):255–285, 2022\.
  * Kryshtafovych et al. [2019] Andriy Kryshtafovych, Torsten Schwede, Maya Topf, Krzysztof Fidelis, and John Moult.  Critical assessment of methods of protein structure prediction (CASP)—Round XIII.  _Proteins: Structure, Function, and Bioinformatics_ , 87(12):1011–1020, 2019.
  * Lensink et al. [2018] Marc F Lensink, Sameer Velankar, Minkyung Baek, Lim Heo, Chaok Seok, and Shoshana J Wodak.  The challenge of modeling protein assemblies: the CASP12-CAPRI experiment.  _Proteins: Structure, Function, and Bioinformatics_ , 86:257–273, 2018.
  * Gherardini and Helmer-Citterich [2008] Pier Federico Gherardini and Manuela Helmer-Citterich.  Structure-based function prediction: approaches and applications.  _Briefings in Functional Genomics and Proteomics_ , 7(4):291–302, 2008.
  * Berman et al. [2003] Helen Berman, Kim Henrick, and Haruki Nakamura.  Announcing the worldwide protein data bank.  _Nature Structural & Molecular Biology_, 10(12):980–980, 2003.
  * Senior et al. [2020] Andrew W Senior, Richard Evans, John Jumper, James Kirkpatrick, Laurent Sifre, Tim Green, Chongli Qin, Augustin Žídek, Alexander WR Nelson, Alex Bridgland, et al.  Improved protein structure prediction using potentials from deep learning.  _Nature_ , 577(7792):706–710, 2020.
  * Akdel et al. [2020] Mehmet Akdel, Janani Durairaj, Dick de Ridder, and Aalt DJ van Dijk.  Caretta–a multiple protein structure alignment and feature extraction suite.  _Computational and structural biotechnology journal_ , 18:981–992, 2020.
  * Shindyalov and Bourne [1998] Ilya N Shindyalov and Philip E Bourne.  Protein structure alignment by incremental combinatorial extension (CE) of the optimal path.  _Protein engineering_ , 11(9):739–747, 1998.
  * Kihara and Skolnick [2003] Daisuke Kihara and Jeffrey Skolnick.  The PDB is a covering set of small protein structures.  _Journal of molecular biology_ , 334(4):793–802, 2003.
  * Xia et al. [2022] Chunqiu Xia, Shi-Hao Feng, Ying Xia, Xiaoyong Pan, and Hong-Bin Shen.  Fast protein structure comparison through effective representation learning with contrastive graph neural networks.  _PLoS computational biology_ , 18(3):e1009986, 2022.
  * Røgen and Fain [2003] Peter Røgen and Boris Fain.  Automatic classification of protein structure by using Gauss integrals.  _Proceedings of the National Academy of Sciences_ , 100(1):119–124, 2003.
  * Budowski-Tal et al. [2010] Inbal Budowski-Tal, Yuval Nov, and Rachel Kolodny.  FragBag, an accurate representation of protein structure, retrieves structural neighbors from the entire PDB quickly and accurately.  _Proceedings of the National Academy of Sciences_ , 107(8):3481–3486, 2010.
  * Zotenko et al. [2006] Elena Zotenko, Dianne P O’Leary, and Teresa M Przytycka.  Secondary structure spatial conformation footprint: a novel method for fast protein structure comparison and classification.  _BMC Structural Biology_ , 6:1–12, 2006.
  * Holm and Sander [1993] Liisa Holm and Chris Sander.  Protein structure comparison by alignment of distance matrices.  _Journal of molecular biology_ , 233(1):123–138, 1993.
  * Zhang and Skolnick [2005] Yang Zhang and Jeffrey Skolnick.  TM-align: a protein structure alignment algorithm based on the TM-score.  _Nucleic acids research_ , 33(7):2302–2309, 2005\.
  * Lathrop [1994] Richard H Lathrop.  The protein threading problem with sequence amino acid interaction preferences is NP-complete.  _Protein Engineering, Design and Selection_ , 7(9):1059–1068, 1994.
  * Zhang and Skolnick [2004] Yang Zhang and Jeffrey Skolnick.  Scoring function for automated assessment of protein structure template quality.  _Proteins: Structure, Function, and Bioinformatics_ , 57(4):702–710, 2004.
  * Liu et al. [2018] Yang Liu, Qing Ye, Liwei Wang, and Jian Peng.  Learning structural motif representations for efficient protein structure search.  _Bioinformatics_ , 34(17):i773–i780, 2018.
  * Fox et al. [2014] Naomi K Fox, Steven E Brenner, and John-Marc Chandonia.  SCOPe: Structural Classification of Proteins—extended, integrating SCOP and ASTRAL data and classification of new structures.  _Nucleic acids research_ , 42(D1):D304–D309, 2014\.
  * Holm and Sander [1999] Liisa Holm and Chris Sander.  Using dali for structural comparison of proteins.  _Current opinion in structural biology_ , 9(3):408–415, 1999.
  * Needleman and Wunsch [1970] Saul B Needleman and Christian D Wunsch.  A general method applicable to the search for similarities in the amino acid sequence of two proteins.  _Journal of molecular biology_ , 48(3):443–453, 1970.
  * Krishna et al. [1997] S Sri Krishna, Indraneel Majumdar, Nick Grishin, Daron Standley, Emily Rubinson, Luan Wei, and Burkhard Rost.  The PDB is a covering set of small protein structures.  _Journal of molecular biology_ , 267(3):638–657, 1997.
  * Zhang and DeLisi [1997] Cheng Zhang and Charles DeLisi.  A unified statistical framework for sequence comparison and structure comparison.  _Proceedings of the National Academy of Sciences_ , 94(11):5917–5922, 1997.
  * Wang et al. [2016] Liwei Wang, Yin Li, and Svetlana Lazebnik.  Learning deep structure-preserving image-text embeddings.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5005–5013, 2016.
  * Corso et al. [2021] Gabriele Corso, Zhitao Ying, Michal Pándy, Petar Veličković, Jure Leskovec, and Pietro Liò.  Neural distance embeddings for biological sequences.  _Advances in Neural Information Processing Systems_ , 34:18539–18551, 2021.
  * Cho et al. [2014] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.  Learning phrase representations using RNN encoder-decoder for statistical machine translation.  _arXiv preprint arXiv:1406.1078_ , 2014.
  * Fukushima [1980] Kunihiko Fukushima.  Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position.  _Biological cybernetics_ , 36(4):193–202, 1980\.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Chen et al. [2021] Jianwen Chen, Shuangjia Zheng, Huiying Zhao, and Yuedong Yang.  Structure-aware protein solubility prediction from sequence through graph convolutional network and predicted contact map.  _Journal of cheminformatics_ , 13(1):1–10, 2021\.
  * Meiler et al. [2001] Jens Meiler, Michael Müller, Anita Zeidler, and Felix Schmäschke.  Generation and evaluation of dimension-reduced amino acid parameter representations by artificial neural networks.  _Molecular modeling annual_ , 7(9):360–369, 2001\.
  * Henikoff and Henikoff [1992] Steven Henikoff and Jorja G Henikoff.  Amino acid substitution matrices from protein blocks.  _Proceedings of the National Academy of Sciences_ , 89(22):10915–10919, 1992.
  * Brandes et al. [2022] Nadav Brandes, Dan Ofer, Yam Peleg, Nadav Rappoport, and Michal Linial.  ProteinBERT: a universal deep-learning model of protein sequence and function.  _Bioinformatics_ , 38(8):2102–2110, 2022.
  * Heinzinger et al. [2019] Michael Heinzinger, Ahmed Elnaggar, Yu Wang, Christian Dallago, Dmitrii Nechaev, Florian Matthes, and Burkhard Rost.  Modeling aspects of the language of life through transfer-learning protein sequences.  _BMC bioinformatics_ , 20(1):1–17, 2019.
  * uni [2023] Uniprot: the universal protein knowledgebase in 2023.  _Nucleic Acids Research_ , 51(D1):D523–D531, 2023\.
  * Sterling and Irwin [2015] Teague Sterling and John J. Irwin.  ZINC 15 – ligand discovery for everyone.  _Journal of Chemical Information and Modeling_ , 55(11):2324–2337, 11 2015.  doi: 10.1021/acs.jcim.5b00559.  URL https://doi.org/10.1021/acs.jcim.5b00559.
  * Dwivedi et al. [2022] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini.  Long range graph benchmark.  _Advances in Neural Information Processing Systems_ , 35:22326–22340, 2022.
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Hamilton et al. [2017] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30, 2017.
  * Fey and Lenssen [2019] Matthias Fey and Jan E. Lenssen.  Fast Graph Representation Learning with PyTorch Geometric.  In _ICLR Workshop on Representation Learning on Graphs and Manifolds_ , 2019.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Nair and Hinton [2010] Vinod Nair and Geoffrey E Hinton.  Rectified linear units improve restricted boltzmann machines.  In _International conference on machine learning_ , pages 807–814, 2010.
  * Srivastava et al. [2014] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: a simple way to prevent neural networks from overfitting.  _The journal of machine learning research_ , 15(1):1929–1958, 2014.
  * Zaheer et al. [2017] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola.  Deep sets.  _Advances in neural information processing systems_ , 30, 2017.
  * Van der Maaten and Hinton [2008] Laurens Van der Maaten and Geoffrey Hinton.  Visualizing data using t-SNE.  _Journal of machine learning research_ , 9(11), 2008.
  * De Bruyn et al. [2014] Alexandre De Bruyn, Darren P Martin, and Pierre Lefeuvre.  Phylogenetic reconstruction methods: an overview.  _Molecular Plant Taxonomy: Methods and Protocols_ , pages 257–277, 2014.
  * Nickel and Kiela [2017] Maximillian Nickel and Douwe Kiela.  Poincaré embeddings for learning hierarchical representations.  _Advances in neural information processing systems_ , 30, 2017.
  * Gu et al. [2019] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré.  Learning mixed-curvature representations in product spaces.  In _International Conference on Learning Representations_ , 2019.
  * Elton et al. [2019] Daniel C Elton, Zois Boukouvalas, Mark D Fuge, and Peter W Chung.  Deep learning for molecular design—a review of the state of the art.  _Molecular Systems Design & Engineering_, 4(4):828–849, 2019.
  * Wieder et al. [2020] Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Seidel, and Thierry Langer.  A compact review of molecular property prediction with graph neural networks.  _Drug Discovery Today: Technologies_ , 37:1–12, 2020.
  * Gainza et al. [2020] Pablo Gainza, Freyr Sverrisson, Frederico Monti, Emanuele Rodola, D Boscaini, MM Bronstein, and BE Correia.  Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning.  _Nature Methods_ , 17(2):184–192, 2020.
  * Yang et al. [2020] Fang Yang, Kunjie Fan, Dandan Song, and Huakang Lin.  Graph-based prediction of Protein-protein interactions with attributed signed graph embedding.  _BMC bioinformatics_ , 21(1):1–16, 2020.
  * Ma et al. [2018] Tengfei Ma, Cao Xiao, Jiayu Zhou, and Fei Wang.  Drug similarity integration through attentive multi-view graph auto-encoders.  _arXiv preprint arXiv:1804.10850_ , 2018.
  * Jiang et al. [2020] Mingjian Jiang, Zhen Li, Shugang Zhang, Shuang Wang, Xiaofeng Wang, Qing Yuan, and Zhiqiang Wei.  Drug–target affinity prediction using graph neural network and contact maps.  _RSC advances_ , 10(35):20701–20712, 2020.
  * [55] Mustafa Hajij, Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzmán-Sáenz, Karthikeyan Natesan Ramamurthy, Tolga Birdal, Tamal K Dey, Soham Mukherjee, Shreyas N Samaga, et al.  Topological Deep Learning: Going Beyond Graph Data.
  * Xu et al. [2018] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ , 2018.
  * Bodnar et al. [2021] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein.  Weisfeiler and lehman go cellular: Cw networks.  _Advances in Neural Information Processing Systems_ , 34:2625–2640, 2021.
  * Suk et al. [2022] Julian Suk, Lorenzo Giusti, Tamir Hemo, Miguel Lopez, Konstantinos Barmpas, and Cristian Bodnar.  Surfing on the Neural Sheaf.  In _NeurIPS 2022 Workshop on Symmetry and Geometry in Neural Representations_ , 2022.
  * Bodnar et al. [2022] Cristian Bodnar, Francesco Di Giovanni, Benjamin Chamberlain, Pietro Liò, and Michael Bronstein.  Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns.  _Advances in Neural Information Processing Systems_ , 35:18527–18541, 2022.
  * Ebli et al. [2020] Stefania Ebli, Michaël Defferrard, and Gard Spreemann.  Simplicial Neural Networks.  In _Advances in Neural Information Processing Systems Workshop on Topological Data Analysis and Beyond_ , 2020.
  * Hajij et al. [2020] Mustafa Hajij, Kyle Istvan, and Ghada Zamzmi.  Cell Complex Neural Networks.  In _Advances in Neural Information Processing Systems Workshop on TDA & Beyond_, 2020.
  * Scarselli et al. [2008] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini.  The graph neural network model.  _IEEE Trans. on neural networks_ , 20(1):61–80, 2008.
  * 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 _International conference on machine learning_ , pages 1263–1272. PMLR, 2017.
  * Jumper et al. [2021] J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Žídek, A. Potapenko, et al.  Highly accurate protein structure prediction with AlphaFold.  _Nature_ , 596(7873):583–589, 2021.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc., 2019.  URL http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.
  * Moreau and Tranchevent [2012] Yves Moreau and Léon-Charles Tranchevent.  Computational tools for prioritizing candidate genes: boosting disease gene discovery.  _Nature Reviews Genetics_ , 13(8):523–536, 2012\.
  * Zhou et al. [2021] Hao Zhou, Juan Felipe Beltrán, and Ilana Lauren Brito.  Functions predict horizontal gene transfer and the emergence of antibiotic resistance.  _Science Advances_ , 7(43):eabj5056, 2021.
  * Gligorijević et al. [2021] Vladimir Gligorijević, P Douglas Renfrew, Tomasz Kosciolek, Julia Koehler Leman, Daniel Berenberg, Tommi Vatanen, Chris Chandler, Bryn C Taylor, Ian M Fisk, Hera Vlamakis, et al.  Structure-based protein function prediction using graph convolutional networks.  _Nature communications_ , 12(1):3168, 2021.
  * Zhao et al. [2022] Chenguang Zhao, Tong Liu, and Zheng Wang.  PANDA2: protein function prediction using graph neural networks.  _NAR genomics and bioinformatics_ , 4(1):lqac004, 2022.
  * Hu et al. [2016] Jessica Xin Hu, Cecilia Engel Thomas, and Søren Brunak.  Network biology concepts in complex disease comorbidities.  _Nature Reviews Genetics_ , 17(10):615–629, 2016\.
  * Rai et al. [2018] Aparna Rai, Pramod Shinde, and Sarika Jalan.  Network spectra for drug-target identification in complex diseases: new guns against old foes.  _Applied Network Science_ , 3:1–18, 2018.
  * Barabási et al. [2011] Albert-László Barabási, Natali Gulbahce, and Joseph Loscalzo.  Network medicine: a network-based approach to human disease.  _Nature reviews genetics_ , 12(1):56–68, 2011\.

##  Appendix A Graph Architectures

###  A.1 Graph Neural Networks

Graph Neural Networks (GNNs) are a class of neural networks that operate on
data defined over graphs. Since their introduction [62], GNNs have shown
outstanding results in a broad range of applications, from _computational
chemistry_ [63] to  _protein folding_ [64]. The key idea is to exploit the
inductive bias induced by the topology of graph-structured data, represented
by the connectivity structure, to perform graph representation learning tasks.

A graph $G=(V,E)$ is a structure that consists of a set $V$ of $n$ nodes and a
set of edges $E$. In this context, each node $v\in V$ is equipped with a
$d$-dimensional feature vector $\mathbf{x}_{v}$, and these can be grouped into
a feature matrix $\mathbf{X}\in\mathbb{R}^{n\times d}$ by stacking all the
$n=|V|$ feature vectors vertically. The connectivity structure of $G$ is fully
captured by the adjacency matrix $\mathbf{A}$, in which the entry $i,j$ of
$\mathbf{A}$ is equal to $1$ if node $i$ is connected to node $j$ and $0$
otherwise. Here, $\mathbf{A}$ is symmetric (that is,
$\mathbf{A}=\mathbf{A}^{T}$). In GNNs, each layer consists of a nonlinear
function that maps a feature matrix into a new (hidden) feature matrix,
accounting for the pairwise relationships in the underlying graph captured by
its connectivity. Formally,

$\mathbf{H}^{(l)}=f(\mathbf{H}^{(l-1)};\mathbf{A})$ (2)

where $\mathbf{H}^{(l)}$ is the hidden feature matrix at layer $l$ and
$\mathbf{H}^{(0)}=\mathbf{X}$. Among the plethora of neural architectures that
have this structure, one of the most popular is the Graph Convolutional
Network [37], which implements Equation 2 as

$\mathbf{H}^{(l)}=\sigma(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}\mathbf{H}^{(l-1)}\mathbf{W}^{(l)})$
(3)

where $\mathbf{W}^{(l)}$ is a learnable weight matrix,
$\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$, $\tilde{\mathbf{D}}$ is a diagonal
matrix whose entries are
$\tilde{\mathbf{D}}_{ii}=\sum_{j}{\tilde{\mathbf{A}}_{ij}}$ and $\sigma$ is a
pointwise nonlinear activation function (for example, Sigmoid, Tanh, ReLU).

###  A.2 Graph Attention Network

The Graph Attention Network (GAT) [38] is a type of GNN that uses attention
mechanisms to capture dependencies between nodes in a graph. The key idea
behind GATs is to learn a different weight for each neighboring node in the
graph using a shared attention mechanism. This allows a GAT to attend to
different parts of the graph when computing the representation of each node.
The GAT layer can be mathematically expressed as

$h_{i}^{(l+1)}=\sigma\left(\sum_{j\in\mathcal{N}_{i}}\alpha_{ij}^{(l)}\mathbf{W}^{(l)}\mathbf{h}_{j}^{(l)}\right)$
(4)

where $\mathbf{h}_{i}^{(l)}$ denotes the representation of node $i$ at layer
$l$, $\mathcal{N}_{i}$ represents the set of neighbouring nodes of $i$,
$\alpha_{ij}^{(l)}$ represents the attention weight between nodes $i$ and $j$
at layer $l$, $\mathbf{W}^{(l)}$ is the weight matrix at layer $l$, and
$\sigma$ is the activation function. The coefficients computed by the
attention mechanism can be expressed as:

$\alpha_{ij}=\frac{\exp\left(\mathrm{LeakyReLU}\left(\mathbf{a}^{\top}[\mathbf{W}^{(l)}\mathbf{h}_{i}^{(l)}||\mathbf{W}^{(l)}\mathbf{h}_{j}^{(l)}]\right)\right)}{\sum_{k\in\mathcal{N}_{i}}\exp\left(\mathrm{LeakyReLU}\left(\mathbf{a}^{\top}[\mathbf{W}^{(l)}\mathbf{h}_{i}^{(l)}||\mathbf{W}^{(l)}\mathbf{h}_{k}^{(l)}]\right)\right)}$
(5)

where $[\cdot||\cdot]$ denotes concatenation, $\mathbf{a}^{\top}$ is a
trainable weight vector, and $\mathrm{LeakyReLU}$ is the Leaky Rectified
Linear Unit activation function.

###  A.3 GraphSAGE

GraphSAGE [39] is a type of GNN that learns node representations by
aggregating information from the local neighborhood of each node. GraphSAGE
learns a set of functions to aggregate the representations of a node’s
neighbors, and then combine them with the node’s own representation to compute
its updated representation. The GraphSAGE layer can be mathematically
expressed as

$h_{i}^{(l+1)}=\sigma\left(\mathbf{W}^{(l)}\cdot\mathrm{CONCAT}\left(\mathrm{AGGREGATE}\left({\mathbf{h}_{j}^{(l)}:j\in\mathcal{N}_{i}}\right),\mathbf{h}_{i}^{(l)}\right)\right)$
(6)

where $\mathbf{h}_{i}^{(l)}$ denotes the representation of node $i$ at layer
$l$, $\mathcal{N}_{i}$ represents the set of neighbouring nodes of $i$,
$\mathrm{AGGREGATE}$ is a learnable aggregation function that combines the
representations of a node’s neighbors, $\mathrm{CONCAT}$ is the concatenation
operation, $\mathbf{W}^{(l)}$ is the weight matrix at layer $l$, and $\sigma$
is the activation function.

##  Appendix B Distance Functions

The proposed approach is to map graphs into a continuous space so that the
distance between embedded points is correlated to the distance between the
original graphs measured by the TM-score. We explored different distance
functions in the embedding space, and we give here their definitions. Given a
pair of vectors p and q of dimension $k$, the definitions of the Manhattan,
Euclidean, Square and Cosine distances are as follows:

$\text{Manhattan:
}d(\textbf{p},\textbf{q})=\|\textbf{p}-\textbf{q}\|_{1}=\sum_{i=0}^{k}|p_{i}-q_{i}|$
(7) $\text{Euclidean:
}d(\textbf{p},\textbf{q})=\|\textbf{p}-\textbf{q}\|_{2}=\sqrt{\sum_{i=0}^{k}(p_{i}-q_{i})^{2}}$
(8) $\text{Square:
}d(\textbf{p},\textbf{q})=\|\textbf{p}-\textbf{q}\|_{2}^{2}=\sum_{i=0}^{k}(p_{i}-q_{i})^{2}$
(9) $\text{Cosine:
}d(\textbf{p},\textbf{q})=1-\frac{\textbf{p}\cdot\textbf{q}}{\|\textbf{p}\|\|\textbf{q}\|}=1-\frac{\sum^{k}_{i=0}p_{i}q_{i}}{\sqrt{\sum^{k}_{i=0}p_{i}^{2}}\sqrt{\sum^{k}_{i=0}q_{i}^{2}}}.$
(10)

##  Appendix C Datasets

#### Kinase proteins

We downloaded the human proteome from UniProt222https://www.uniprot.org and
sub-selected 512 protein kinases. We also used UniProt to download the PDB
files for the kinases.

#### SCOPe v2.07

The 40% identity filtered subset of SCOPe
v2.07333https://scop.berkeley.edu/help/ver=2.07 is used to train and validate
our approach. Out of the total of 14,323 domains, 1,058 domains were removed
during the data collection process. The remaining 13,265 domains were used for
training and testing. For both datasets, we computed ground truth TM-scores by
performing all-against-all comparisons using TM-align [15]. We used 80% of the
comparisons for training and 20% for testing. We repeated all the experiments
with 3 different seeds.

##  Appendix D Additional experiments and details

###  D.1 TM-scores predictions

We employed the trained GAT architectures from Table 2 to predict the TM-
scores for the kinase pairs in the test set. Results of this evaluation,
measured by Pearson correlation between model predictions and true TM-scores,
are shown in Table 5.

Table 5: Pearson correlation coefficients between predicted and actual TM-scores for the GAT model for different choices of node features and distance functions. We use gold , silver , and bronze  colors to indicate the first, second and third best performances, respectively. The highest score is reached with LSTM-extracted features and Euclidean geometry.  Feature | Distance
---|---
| Cosine | Euclidean | Manhattan | Square
One-Hot | $0.661$ | $0.384$ | $0.637$ | $0.226$
Physicochemical | $0.463$ | $0.358$ | $0.534$ | $0.166$
BLOSUM | $0.484$ | $0.658$ | $0.761$ | $0.468$
BERT features | $0.849$ | $0.870$ | $0.837$ | $0.785$
LSTM features | $0.861$ | $0.879$ | $0.858$ | $0.839$

Using features learned by LLMs exhibits superior performance compared to other
feature extraction methods. The highest score is reached with LSTM-extracted
features and Euclidean geometry of the embedding space.

###  D.2 TM-scores inference times

Table 6

Table 6: Wall-clock estimates for the GNN models and TM-align on different percentages of the test set. Among the GNNs, GAT is the slowest at computing TM-scores, followed by GraphSAGE and GCN, both on GPU and CPU. However, TM-score computation with any of the GNN architectures is significantly faster than TM-align, even on CPU. Test Size (%) | Model | GPU Inference (s) | CPU Inference (s)
---|---|---|---
26164 (20%) | GCN | $88.3\pm 2.04$ | $474.78\pm 1.98$
GAT | $125.8\pm 2.26$ | $1570.1\pm 3.21$
GraphSAGE | $98.2\pm 3.46$ | $618.2\pm 2.56$
TM-align | - | $57659.3\approx 16\text{ hr}$
13082 (10%) | GCN | $49.2\pm 0.53$ | $231.1\pm 3.01$
GAT | $59.3\pm 2.34$ | $773.6\pm 3.14$
GraphSAGE | $49.3\pm 0.04$ | $313.9\pm 2.23$
TM-align | - | $29156.2\approx 8\text{ hr}$
6541 (5%) | GCN | $23.2\pm 0.18$ | $119.6\pm 1.76$
GAT | $30.1\pm 0.70$ | $3882\pm 3.26$
GraphSAGE | $25.6\pm 1.42$ | $153.1\pm 3.01$
TM-align | - | $15019.9\approx 4\text{ hr}$

provides inference times for the different graph models (GCN, GAT and
GraphSAGE) and TM-align [15]. We show the inference times on GPU and CPU for
the graph models, and CPU time for TM-align. Time estimates for different
percentages of the test set (20%, 10%, 5%) are reported. For the graph models,
we also report standard deviations by estimating the times over 5 different
runs. The GNN architectures are significantly faster than TM-align, even on
CPU. Our approach represents a fast (Table 6) and accurate (Table 5) way to
compute protein structural similarities even on large-scale datasets.

###  D.3 MSE results on SCOPe proteins

Table 7

Table 7: MSE scores for different distance functions and LSTM features on the SCOPe dataset. We use gold , silver , and bronze  colors to indicate the first, second and third best performances, respectively. Model | Distance | MSE
---|---|---
GAT | Cosine | $0.008048$
Euclidean | $0.006294$
Manhattan | $0.010655$
Square | $0.008793$

reports the MSE scores for different distance functions and LSTM features on
the SCOPe dataset. The best MSE is again reached with LSTM-extracted features
and Euclidean geometry of the embedding space.

###  D.4 Computational Resources and Code Assets

In all experiments we used NVIDIA® Tesla V100 GPUs with 5,120 CUDA cores and
32GB GPU memory on a personal computing platform with an Intel® Xeon® Gold
5218 CPU @ 2.30GHz CPU using Ubuntu 18.04.6 LTS. The models have been
implemented in PyTorch [65] and PyTorch Geometric
library444https://github.com/pyg-team/pytorch_geometric/ [40]. PyTorch, NumPy,
SciPy are made available under the BSD license, Matplotlib under the PSF
license, and PyTorch Geometric is made available under the MIT license.

##  Appendix E Phylogenetic reconstruction

Phylogenetic reconstruction refers to the task of inferring evolutionary
relationships based on morphological or physiological characters. Typical
phylogenetic reconstruction makes use of sequence similarity only. Here, we
explore the ability of the proposed embeddings to recapitulate phylogenies in
unsupervised settings. To this end, we downloaded P53 tumour proteins from 20
different organisms from UniProt [34] and generated protein embeddings using
our GAT architecture pre-trained on SCOPe proteins. A common method for Tree
Estimation, Neighbor-Joining, was used to build the phylogenetic tree, shown
in Figure 6.

Figure 6: Phylogenetic tree for P53 tumor protein across 20 species.

The proposed embeddings managed to accurately recapitulate the evolutionary
relationships among the 20 species (Figure 6). Our embeddings (structure- and
sequence-aware) offer an extension to traditional methods for phylogenetic
reconstruction from sequence only to a combination of structure and sequence.

##  Appendix F Bioinformatics applications

There are several areas of bioinformatics research where structural
representation of proteins finds useful applications. We now give a few
examples.

#### Protein-protein interaction

Proteins rarely carry out their tasks in isolation, but interact with other
proteins present in their surroundings to complete biological activities.
Knowledge of protein–protein interactions (PPIs) helps unravel cellular
behaviour and functionality. Generating meaningful representations of proteins
based on chemical and structural information to predict protein-pocket ligand
interactions and protein-protein interactions is an essential bioinformatics
task [52].

#### Protein function

The structural features of a protein determine a wide range of functions: from
binding specificity and conferring of mechanical stability, to catalysis of
biochemical reactions, transport, and signal transduction. While the
experimental characterization of a protein’s functionality is a challenging
and intense task [66], exploiting graph representation learning ability to
incorporate structural information facilitates the prediction of protein
function [67, 68, 69].

#### Small molecules

The design of a new drug requires experimentalists to identify the chemical
structure of the candidate drug, its target, its efficacy and toxicity and its
potential side effects [70, 71, 72]. Because such processes are costly and
time consuming, drug-discovery pipelines employ in silico approaches.
Effective representations of protein targets of small molecules (drugs) has
the potential to dramatically speed up the field of drug discovery.