Learning Unknown from Correlations: Graph Neural Network for Inter-novel-protein Interaction Prediction

1 Introduction

Protein-protein Interactions (PPIs) play an important role in most biological processes. In addition to direct physical binding, PPI also has many other, indirect ways of cooperation and mutual regulation, such as exchange reaction products, participate in signal relay mechanisms, or jointly contribute toward specific organismal functions [Szklarczyk et al., 2016]. It can be said that the study of PPIs and their interaction types are essential toward understanding cellular biological processes in normal and disease states, which in turn facilitate the therapeutic target identification and novel drug design [Skrabanek et al., 2008]. There are many experimental methods to detect PPI, where the most conventional and widely used high-throughput methods are yeast two-hybrid screening [Fields and Song, 1989]. However, the experimentbased methods are expensive and time-consuming, but more importantly, even if a single experiment has detected PPI, it cannot fully interpret its types [De Las Rivas and Fontanillo, 2010]. Evidently, we urgently need reliable computational methods that are learned from the accumulated PPI data to predict the unknown PPIs accurately.

1 Codes are available at https://github.com/lvguofeng/GNN PPI Extended version https://arxiv.org/abs/2105.06709

Despite long-term research works [Guo et al., 2008; Hashemifar et al., 2018; Chen et al., 2019] make noticeable progress, existing methods suffer from significant performance degradation when tested on unseen dataset. Take the state-of-the-art model PIPR [Chen et al., 2019] as an example, compared tested on trainset-homologous SHS148k testset with on a larger STRING testset, micro F1 score drops from 92.42 to 53.85. For further investigation, we divide the STRING testset into BS, ES and NS subsets, where BS denotes Both of the pair proteins in interaction were Seen during training, ES denotes Either (but not both) of the pair proteins was Seen, and NS denotes Neither proteins were Seen during training. As clearly shown in Figure 1, poor performance in the ES and NS subsets (collectively termed as inter-novelprotein interactions in this paper) is the main reason for the performance degradation.

On the other hand, current evaluations on the trainsethomologous SHS148k testset apply a protein-irrepective perinteraction randomized strategy to divide the trainset and testset, and consequently, BS comprises over 92% of the whole testset 1 and dominates the overall performance. The evaluations overlook the inter-novel-protein interactions, and are thus not instructive for the performance when tested on other datasets. As a result, in this paper we firstly design a new evaluation framework with two per-protein randomized data partition strategies. Instead of simple protein-independent randomization, we take also into consideration the distance between proteins and utilize Breadth-First and Depth-First Search methods to construct the testset. Comparison experiments between the trainset-homologous testset and the unseen STRING testset demonstrates the proposed evaluation can give consistent assessment across datasets.

Besides the evaluation, for the methodology existing works take PPIs as independent instances. Correlations between proteins have long been ignored. Intuitively, for predicting the type of interaction between protein A and B, the interaction between protein A and C, as well as B and C must provide useful information. The correlations can be naturally modeled and excavated with a graph, where proteins serve as the nodes and interactions as the edges. In this paper, the graph is processed with a graph neural network based model (GNN-PPI). As demonstrated in Figure 1, the introduction of correlations and the proposed GNN-PPI model have largely narrow the performance gap between BS, ES and NS subsets.

In summary, the contribution of this paper is three-fold:

1. We design a new evaluation framework that fully respects the inter-novel-protein interactions and give consistent assessment across datasets.
2. We propose to incorporate correlation between proteins into the PPI prediction problem. A graph neural network based method is presented to model the correlations.
3. The proposed GNN-PPI model achieves state-of-the-art performance in real datasets of different scales, especially for the inter-novel-protein interaction prediction.

2 RelatedWork

The primary amino acid sequences are confirmed to contain all the protein information [Anfinsen, 1972] and are extremely easy to obtain. Thus, there is a longstanding interest in using sequence-based methods to model proteinrelated tasks. The research work of PPI prediction and classification can be summarized into two stages. The early research is based on Machine Learning (ML) [Guo et al., 2008; Wong et al., 2015; Silberberg et al., 2014; Shen et al., 2007]. These methods provide feasible solutions, but their performance is limited by the PPI feature representation and model expressiveness. Deep Learning (DL) has recently been widely used in bioinformatics problems due to its powerful expressive ability, including PPI prediction and classification. These works [Li et al., 2018; Hashemifar et al., 2018; Chen et al., 2019; Sun et al., 2017] typically use Convolution Neural Networks or Recurrent Neural Networks to extract features from the amino acid sequence of the protein.

More recent work has focused on the feature representation of proteins. [Saha and others, 2020] proposes a novel deep multi-modal architecture, which extracts multi-modal information from protein structure and existing text information in biomedical literature. [Nambiar et al., 2020] proposes a Transformer based neural network to generate proteins pretrained embedding. In the latest research, [Yang et al., 2020] considers the correlation of PPIs and first proposed to use GCN[Kipf and Welling, 2016] to learn protein features in the PPI network automatically. However, their work cannot be extended to the multi-label PPI classification.

To the best of our knowledge, the current work of PPI has not been concerned with the problems of inter-novel-protein interactions. However, In the field of Drug-drug Interaction (DDI), [Deng et al., 2020] mentioned that the testset is divided according to whether the drug was seen during training, and the results show that the performance for the inter-noveldrug interactions is extremely degraded, but the original paper does not propose a solution.

3 Methodology

3.1 ProblemFormulation

Suppose we have protein set P = {p0, p1, ..., pn} and PPI set X = {xij = {pi, pj}|i ̸= j, pi, pj ∈ P, I(xij) ∈ {0, 1}}. I is the PPI indicator function, if I(xij) = 1, then it means that protein pi interacts with protein pj. Note that when I(xij) = 0, it may mean that protein pi and pj will not interact, or they have a potential interaction while it has not been discovered so far. In order to avoid unnecessary errors, we will not do any operation on unknown protein pairs (default ∀xij ∈ X, I(xij) = 1). We define PPI label space as L = {l0, l1, ..., ln} with n possible interaction types. For each PPI xij, its labels is represented as yij ⊆ L. In summary, the multi-type PPI dataset is defined as D = {(xij , yij)|xij ∈ X}. Considering the correlation of PPIs, we use protein as nodes and PPIs as edges to build the PPI graph G = (P, X ).

The task of multi-type PPI learning is to learn a model F : x → ˆ y from the training set Xtrain. For any protein pair xij ∈ Xtest, the model F predict ˆ yij as the set of proper labels for xij. The above-mentioned Xtrain and Xtest are obtained from X based on the evaluation, where Xtrain + Xtest = X . Further, according to whether protein p was seen during training, the protein set P is divided into known Pv = ⋃ Xtrain and unknown Pu = P - Ptrain. Moreover, as mentioned in section 1, Xtest can be divided into XBS,XES, and XNS, which defined as follows:

Since inter-novel-protein interactions are the main bottlenecks, we require the testset Xtest of the evaluation framework to meet condition |XBS| ≪ |XES| + |XNS|. Our goal is that under this evaluation, the model F learned from Xtrain can accurately predict the multi-label label of PPI in Xtest.

3.2 Overview

The GNN-PPI framework and evaluation are shown in Figure 2. We will introduce GNN-PPI from the following three aspects. First is Evaluation Framework. We propose two sets of heuristic data partition schemes based on the PPI network, and the generated testset meets the conditions |XBS| ≪ |XES| + |XNS|. Secondly, Protein feature encoding. We design Protein-Independent Encoding (PIE) and Protein-Graph Encoding (PGE) modules to encode protein features. The last is Multi-label PPI prediction. For unknown PPIs, we combine their protein feature encoded by the previous process, calculate their scores in different PPI types, and output its multi-label prediction.

3.3 Evaluation Framework

Generally, existing machine learning algorithms usually randomly divide part of the dataset as a testset to evaluate the performance of the model. However, in the PPI-related tasks, we have the following Corollary, derived from Erd˝os-R´enyi(ER) random graph model. [ERDdS and R&wi, 1959; Erd˝os and R´enyi, 1960]:

Corollary 1. Randomly divide the PPI dataset, select t ≤ 0.2 as the testset, then most of the proteins in the testset were seen in training.

The detailed proof of the corollary is elaborated in the extended version 1 . It can be inferred from this corollary that the performance of the testset obtained by random division only reflects the predictive ability of the PPI between known Pv. In the real world, there are still many proteins and their PPIs that have not been discovered. We perform empirical studies by comparison of two different time points, 2021/01/25 and 2020/04/11, of the Homo sapiens subset of BioGRID database. We found that the newly discovered proteins exhibit some BFS-like or DFS-like local patterns. Even if the PPIs have been discovered, most of their types remain relatively unexplored. Therefore, we need a brand-new evaluation that can reflect the model's predictive performance on the internovel-protein interactions. The next content will introduce the evaluation framework we design.

We design two heuristic evaluation schemes based on the

Algorithm 1 Data Partition Algorithm

Input: Protein set P; PPI set X; Testset size N; Root node selection threshold t; Search order S ∈ {BFS, DFS};

Output: Xtrain; Xtest;

• 1: Build PPI graph G = (P,X)

▷ Root node selection

• 2: repeat
• 3: Randomly select a protein as root node proot.
• 4: until |N(proot)| < t ▷ N returns the neighbors ▷ Testset construction
• 5: Xtest = ∅, pcur = proot
• 6: repeat
• 7: Xcur = {{pcur, pk}|pk ∈ N(pcur)}
• 8: Xtest = Xtest ∪Xcur
• 9: pcur = Search Next(G, pcur, S)
• 10: until |Xtest| ≥ N

▷ Trainset construction

• 11: Xtrain = X -Xtest
• 12: return Xtrain,Xtest

PPI network, namely BFS and DFS. They simulated two scenarios of unknown proteins Pu in reality:

1. Pu interact tightly with each other, and they exist in the form of clusters in the PPI network (See Figure 3 (b)).
2. Pu are sparsely distributed in the PPI network and have little interaction with each other (See Figure 3 (c)).

We select a root node proot, fix the size of the testset N, and then use the Breadth-First Search (BFS) algorithm in the PPI network to obtain the proteins Pu that meet the scenario 1. All PPIs related to these proteins are the generated testset. For scenario 2, we just need to simply randomly select proteins to form Pu. However, in order to maintain the PPI network connectivity of Xtrain and Xtest, we use the Depth-First Search (DFS) algorithm to simulate. The details of the data partition algorithm are shown in Algorithm 1, where we will not show the details of the BFS and DFS algorithms but use the Search Next function to return the next protein of the current protein pcur in different search algorithms. The N(p) returns all neighbors of protein p. And we controls the degree of the root node |N(proot)| < t to simulate newly discovered proteins (Usually few proteins interact with them).

3.4 Protein Feature Encoding

Previous work [Chen et al., 2019] has proved that protein features based on the amino acid sequence are beneficial to the performance improvement of PPI-related tasks. Therefore, we design a Protein-Independent Encoding (PIE) module, which contains Conv1d with pooling, BiGRU, and fully connected (FC) layer, to generate protein feature representations as input to the PPI network.

The subsequent Protein-Graph Encoding (PGE) module is the core of GNN-PPI. Inspired by PPI network being widely used in bioinformatics computing, we construct PPI network G = (P,X), and convert the original independent learning tasks F(xij |pi, pj , θ) → ˆ yij into graph-related learning tasks F(xij|G, θ) → ˆ yij. Recently, GNN is the most effective graph representation learning method, its main idea is the recursive neighborhood aggregation scheme, where each node computes a new feature by aggregating the previous features of its neighbor nodes. After k iterations, a node is represented by its transformed feature, which captures the structural information within the node's k-hop neighborhood. More specifically, the GNN of the k-th iteration is

where gk p is the feature of node p at the k-th iteration. The design of Agg(·) and Update(·) are the keys to different GNN architectures. In this paper we use Graph Isomorphism Network (GIN) [Xu et al., 2018], where the sum of the neighbor node features is used as the aggregation function, and multilayer perceptrons (MLPs) is used to update the aggregated features. Then, GIN updates node features as

where ϵ can be a learnable parameter or a fixed scalar.

3.5 Multi-Label PPI Prediction

With the feature of protein learned from the previous stages for the PPI xij, we use the dot product operation to combine the features of pi and pj , and then use a fully connected layer (FC) as classifier for multi-label PPI prediction, expressed as ˆ yij = FC(gpi · gpj ). The PIE and PGE modules are jointly training in an end-to-end way. Given a training set Xtrain and its ground-truth multi-label interaction Ytrain, we can use the multi-task binary cross-entropy as the loss function:

Different from the algorithm that considers PPI independently, GNN-PPI learns to combine protein neighbors to generate feature representations. Therefore, for the Xtest constructed by our proposed BFS or DFS, GNN-PPI can also be based on its neighbors to generate suitable feature representations for multi-type PPI prediction. On the other hand, even if the PPI network G ′ = (Pv, Xtrain) used in the training process is constructed with only Xtrain, it can perform well for unknown PPI xij ∈ Xtest. (See details in Table 4)

4 Experiment

4.1 Dataset

We use multi-type PPI data from the STRING database 2 [Szklarczyk et al., 2019] to evaluate our proposed GNN-PPI. The STRING database collected, scored, and integrated most publicly available sources of protein-protein interaction information and built a comprehensive and objective global PPI network, including direct (physical) and indirect (functional) interactions. In this paper, we focus on the multi-type classification of PPI by STRING. It divides PPI into 7 types, namely reaction, binding, post-translational modifications (ptmod), activation, inhibition, catalysis, and expression. Each pair of interacting proteins contains at least one of them. [Chen et al., 2019] randomly select 1,690 and 5,189 proteins from the Homo sapiens subset of STRING that shares < 40% of sequence identity to generate two subsets, namely SHS27k and SHS148k, which contain 7,624 and 44,488 multi-label PPIs. At the same time, we use all PPIs of Homo sapiens as our third dataset, namely STRING, which contains 15,335 proteins and 593,397 PPIs. We will use these three PPI datasets of different sizes to evaluate GNN-PPI and other PPI methods in the following content.

2 https://string-db.org/

4.2 Experimental Details

Experimental Settings and Metrics

We select 20% of PPIs for testing, using our proposed BFS, DFS, and original evaluation (Random). The BFS or DFS partition algorithm has completely different results for different root nodes. To simulate the realistic scene mentioned in Section 3.3, the root node's degree should not be too large. We set the root node degree threshold t = 5. To eliminate the influence of the randomness of data partitioning on the performance of PPI methods, we repeat experimental results under 3 different random seeds. We use the protein features based on amino acid sequence, refer to [Chen et al., 2019] using embedding method to represent each amino acid 1 . We adopt Adam algorithm [Kingma and Ba, 2014] to optimize all trainable parameters. The other hyper-parameters settings are shown in the extended version 1 .

We evaluate the multi-label PPI prediction performance using micro-F1. This is because micro-averaging will emphasize the common labels in the dataset, which gives each sample the same importance. Since the different PPI types in the datasets we used are very imbalanced, micro-F1 may be preferred.

Baselines

We compare GNN-PPI against a variety of baselines, which can be categorized as follows:

1. Machine Learning based: We choose three representative machine learning (ML) algorithms, SVM [Guo et al., 2008], RF [Wong et al., 2015], and LR [Silberberg et al., 2014]. The input feature of the algorithms uniformly selects common handcrafted protein features, AC [Guo et al., 2008] and CTD [Du et al., 2017], of which CTD use seven attributes for the division 1 .

1. Deep Learning based: We choose three representative deep learning (DL) algorithms in PPI prediction, PIPR [Chen et al., 2019], DNN-PPI [Li et al., 2018] and DPPI [Hashemifar et al., 2018]. We construct the same architecture and hyper-parameters settings as the original papers and modify the output of the original implementation from a binary class to multi-label. The protein input feature based on the amino acid sequence is consistent with GNN-PPI.

4.3 Results and Analysis

Table 1 compares the performance of different methods under different evaluations and different datasets. Firstly, consider the impact of different evaluations, we can see that any method in Table 1 perform well under Random partition. However, under BFS or DFS partition, except for GNN-PPI, the performance of other methods declines clearly. Moreover, the performance under the DFS is generally higher than that of the BFS, which means that the clustered distribution of unknown proteins in the PPI network is harder to learn than discrete distribution. Next, observe the performance on different datasets. Regardless of the evaluations, the performance of any method will improve as the data size increases. However, the problems mentioned above will not be trivially solved by increasing the amount of data. Finally, comparing different methods, we can see that DL-based methods are generally better than ML-based, and GNN-PPI can achieve state-ofthe-art performance. However, under the Random partition, the advantage of GNN-PPI over DL-based methods will be smaller as the dataset size increases. The most prominent advantage of GNN-PPI is that under the BFS or DFS partition, and for the inter-novel-protein interactions, it can still learn useful feature representations from protein neighbors so as to obtain good performance in PPI prediction. In summary, the experimental results show that GNN-PPI can effectively improve the prediction accuracy of inter-novel-protein interactions. However, how to further push the performance to be comparable as Random partition is still a problem worthy of further discussion, and it is also our future work.

We make a more in-depth analysis of performance between PIPR and GNN-PPI on Xtest, as shown in Table 2. Observing the proportions of different subsets of the testset, we can find that under Random partition, more than 92% test samples belong to XBS, which is consistent with our corollary 1. PIPR performs well on the randomly divided testset (81.58 in SHS27k, 92.42 in SHS148k, and 94.23 in STRING), but if we further investigate the testset, we will find that PIPR performs very poorly for inter-novel-protein interactions (xij ∈ XES or XNS), but it is dominated by XBS, which has accurate performance and a high proportion. According to the results of Table 1 and Table 2, with sufficient XES and XNS data, we can assert that the methods which treats PPI as an independent sample (represented by PIPR), cannot accurately predict inter-novel-protein interactions. On the contrary, our proposed GNN-PPI can still perform well under BFS and DFS. Moreover, as the data size increases, the performance of GNN-PPI is better (e.g., 82.41 vs. 54.31 in STRING-BFS and 90.19 vs. 67.84 in STRING-DFS).

Next, we study the ability of different evaluations to assess the model's generalization. We take the trained model's test performance on the larger dataset STRING as the model's true generalization ability. If the gap between the trainset-homologous test performance and the generalization is smaller, then the evaluation can better reflect the model's generalization. The experimental results are shown in Table 3. It can be seen that the previous evaluation (Random), whether it is for PIPR or GNN-PPI, the test performance on the STRING dataset has severely dropped. Like our speculation, it cannot reflect the generalization of the model. On the contrary, under the evaluation of BFS or DFS, its test performance can truly reflect the performance of the model, no matter it is good or bad (e.g. 66.13 vs. 63.74 in PIPR-SHS148kBFS and 71.19 vs. 67.43 in GNN-PPI-SHS27k-DFS). In fact, the testset obtained by BFS or DFS is theoretically the same as the sample tested on STRING. The only difference is the proportion of different types of PPI (BS, ES and NS). Testing On the STRING, the proportion of NS is higher.

Finally, we study the impact of the PPI network graph construction method (mentioned in 3.5) in the GNN-PPI. There are two graph construction methods, graph construct by all data (GCA, G = (P,X)) and graph construct by trainset (GCT, G = (Pv, Xtrain)). The experimental results are shown in Table 4. It can be seen that the performance of GCA all exceeds that of GCT, which is reasonable because the graph construction of GCA accesses more complete information than GCT. Compared with BFS, in the case of DFS, the performance of GCT is closer to GCA, which seems to indicate that the protein neighbors are more complete, the performance will be better. What is more noteworthy is that GCT is still much higher than non-graph algorithms, which shows the superiority of GNN in processing the few-shot learning for multi-label PPI prediction task. Moreover, for unknown proteins, we often cannot know their neighbors in advance. The effectiveness of GCT shows that the trained model is robust to newly discovered proteins and their interactions.

5 Conclusion

In this paper, we study the significant performance degradation of existing PPI methods when tested in unseen dataset. Experimental results show that this problem is due to the poor performance of the model for inter-novel-protein interactions. However, current evaluation overlook the inter-novel-protein interactions, and are thus not instructive for the performance when tested on unseen datasets. Therefore, we design a new evaluation framework with two per-protein randomized data partition startegies, namely BFS and DFS, and propose a GNN based method GNN-PPI to model the correlations between PPIs. Our experimental results show that GNN-PPI outperforms state-of-the-art PPI prediction methods regardless of the evaluation is original or our proposed, especially for the inter-novel-protein interactions prediction.