# A Comprehensive Python Library for Deep Learning-Based Event Detection in
Multivariate Time Series Data

1st Menouar Azib  Akkodis, France
<EMAIL_ADDRESS>2nd Benjamin Renard  Akkodis, France
<EMAIL_ADDRESS>3rd Philippe Garnier  Université de Toulouse,
France
<EMAIL_ADDRESS>4th Vincent Génot  Université de Toulouse,
France
<EMAIL_ADDRESS>5th Nicolas André  Université de Toulouse, France
<EMAIL_ADDRESS>
###### Abstract

Event detection in time series data is crucial in various domains, including
finance, healthcare, cybersecurity, and science. Accurately identifying events
in time series data is vital for making informed decisions, detecting
anomalies, and predicting future trends. Despite extensive research exploring
diverse methods for event detection in time series, with deep learning
approaches being among the most advanced, there is still room for improvement
and innovation in this field. In this paper, we present a new deep learning
supervised method for detecting events in multivariate time series data. Our
method combines four distinct novelties compared to existing deep-learning
supervised methods. Firstly, it is based on regression instead of binary
classification. Secondly, it does not require labeled datasets where each
point is labeled; instead, it only requires reference events defined as time
points or intervals of time. Thirdly, it is designed to be robust by using a
stacked ensemble learning meta-model that combines deep learning models,
ranging from classic feed-forward neural networks (FFNs) to state-of-the-art
architectures like transformers. This ensemble approach can mitigate
individual model weaknesses and biases, resulting in more robust predictions.
Finally, to facilitate practical implementation, we have developed a Python
package to accompany our proposed method. The package, called eventdetector-
ts, can be installed through the Python Package Index (PyPI). In this paper,
we present our method and provide a comprehensive guide on the usage of the
package. We showcase its versatility and effectiveness through different real-
world use cases from natural language processing (NLP) to financial security
domains.

###### Index Terms:

Event Detection in Time Series, Regression, Python Package, Information
Retrieval, Natural Language Processing (NLP)

##  I Introduction

In recent years, deep learning techniques have shown promising results in
various domains, including event detection in time series data. Notably, [1,
2, 3] provide comprehensive reviews of state-of-the-art deep learning and
graph-based techniques for time series anomaly detection, respectively.
Additionally, to the best of our knowledge, the most comprehensive anomaly
detection benchmarks are provided by [4, 5]. These works demonstrate the
potential of advanced machine learning techniques for detecting events in time
series data.

Unlike traditional binary classification methods, where each time step is
labeled as an event or non-event, our approach is based on regression.
Regression enables the prediction of continuous values, offering more nuanced
information about event presence and strength in the time series. This
approach is advantageous for complex and noisy data, where events may be less
defined or easily distinguished from non-events. The regression approach can
predict a continuous output variable, which can be beneficial when dealing
with events that vary in intensity or magnitude. This flexibility allows the
model to capture more detailed information about the event, such as its
duration or severity. In real-world data, events often occur amidst background
noise. Binary classification might struggle with this, as it requires a clear
distinction between event and non-event classes. Regression, on the other
hand, can handle this complexity better by predicting a continuous spectrum of
values. The output of a regression model can provide more interpretable
results. For instance, a higher predicted value could indicate a stronger or
more significant event. This can provide more precise and actionable insights
for decision-making. In many real-world scenarios, events of interest are rare
compared to non-events. This leads to imbalanced data, which can pose
challenges for binary classification models. Regression models can potentially
handle such scenarios better by focusing on predicting the event’s
characteristics rather than just its occurrence. Using regression, our method
provides more precise and accurate insights into event characteristics within
the time series data.

Secondly, our method does not require labeling each time step within a
dataset, which can be a time-consuming and labor-intensive process. Instead,
our method only requires reference events to be defined as time points or
intervals of time, making it more efficient and practical to use. Thirdly, our
method utilizes a stacked ensemble learning meta-model which allows for
improved performance by leveraging the strengths of multiple base models and
optimizing their predictions [6]. This approach enhances the overall accuracy
and robustness of event detection.

Finally, to facilitate practical implementation, we have developed a Python
package that accompanies our proposed method. This package provides an easy-
to-use interface for applying our method to real-world datasets and allows
users to quickly and easily detect events in their own time series data. We
provide detailed documentation and examples to help users get started with our
package and apply it to their own data. Overall, our method offers a powerful
and flexible approach for detecting events in multivariate time series data
that is both accurate and efficient.

The rest of this paper is organized as follows: In Section 2, we provide a
detailed description of the regression aspect of our method, explaining how it
differs from traditional binary classification approaches. In Section 3, we
present our stacked ensemble learning approach, which combines the strengths
of multiple base models to improve the accuracy and robustness of event
detection. In Section 4, we describe the design and implementation of the
Python package, which provides an easy-to-use interface for applying our
method to real-world datasets. In Section 5, we showcase the usage of the
package and demonstrate the effectiveness of the method through a series of
experiments on different real-world datasets from NLP to financial security.
Finally, in Section 6, we conclude the paper by summarizing our key findings
and contributions. We highlight the strengths and limitations of our method
and discuss potential future directions for research in this area.

##  II Regression Based Approach

###  II-A Data

In our approach, we require two pieces of data: one representing the time
series (dataset) $S$, and the other representing the list of reference events
(or ground truth events) $E$. The time series $S$ can be represented as
follows:

$\displaystyle S:\mathbb{R}$ $\displaystyle\rightarrow\mathbb{R}^{f}$ (1)
$\displaystyle t$ $\displaystyle\mapsto S(t)$

where $t$ represents the time index and $S(t)$ is a vector of $f$ features
observed at time $t$. The list of reference events $E$ is represented either
by a single time value or an interval. Each reference event in the list can be
represented as a tuple $(t_{start},t_{end})$, where $t_{start}$ and $t_{end}$
are the start and end times of the event, respectively. If the event is
represented by a single time value, then $t_{start}=t_{end}$. This list of
reference events serves as the ground truth for evaluating the performance of
the proposed event detection method.

Within the package, the time series $S$ and the events $E$ are typified as
follows:

⬇ 1import pandas as pd 2from typing import Union 3 # Time Series ‘S‘ 4dataset:
pd.DataFrame 5events: Union[list, pd.DataFrame]

The dataset variable represents the time series data in a Pandas DataFrame
format, where the index represents the time and the columns represent the
features ($f$). The events variable represents the reference events in either
a list or Pandas DataFrame format. They can have either one column to
represent the midtime of events or two columns to represent the beginning and
ending time of each event.

###  II-B Sliding Windows

The proposed method is based on regression, so we must create a scalar
parameter for this task based on the required time series $S$ and a list of
reference events $E$. To achieve this, we use a sliding window approach to
divide the time series data into overlapping windows. Each window is
represented by a fixed-size ($width$) segment of observations, and the windows
are shifted along the time axis by a fixed step size $step$. We associate each
window with a real value called the overlapping parameter $op\in[0,1]$, which
is computed as follows:

$op(w_{i},e_{j})=\dfrac{{\text{duration}(w_{i}\cap
e_{j})}}{{\text{duration}(w_{i}\cup e_{j})}}$ (2)

where $w_{i}$ represents the $i$-th window in the time series, which is a
matrix of observations spanning the duration of the window. Each row of the
matrix corresponds to a time step within the window, and each column
corresponds to one of the $f$ features observed at that time step. On the
other hand, $e_{j}$ represents the $j$-th event in the list of reference
events.

To facilitate the comparison between the reference events and the sliding
windows, we convert the reference events into fixed-size intervals denoted by
$width\\_events$. This can be done by extending or truncating each reference
event to match the desired interval size. The choice of interval size should
be carefully considered, as it can affect the performance of the method. A
larger interval size provides more flexibility in matching the reference
events with the sliding windows, but it also increases the risk of false
positives. On the other hand, a smaller interval size reduces the risk of
false positives, but it also increases the risk of false negatives. In
practice, the optimal interval size can be determined through experimentation
on a validation set.

The overlapping parameter measures the degree of overlap between a window and
an event. If the window $w_{i}$ and the event $e_{j}$ do not intersect, the
overlapping parameter will be 0, indicating no relevance between them. On the
other hand, when $w_{i}$ and $e_{j}$ overlap, $op$ will be greater than 0,
with the maximum value reached when a perfect match is observed. The value 1
is reached in case of a perfect match and when the sliding windows and the
event windows have the same width.

To associate a single value of $op$ to each sliding window $w_{i}$, we take
the maximum of the overlapping values among all events:

$op(w_{i})=\max_{e_{j}\in E}op(w_{i},e_{j})$ (3)

This means that for each sliding window, we select the event with the highest
degree of overlap as the most relevant event. The overlapping parameter
$op(w_{i})$ provides a measure of how well the window aligns with the most
relevant event, which can be used to guide a regression model in predicting
the presence or absence of events in the time series data. Fig. 1 illustrates
this concept with a visual representation of the sliding windows and their
corresponding overlapping parameters.

Figure 1: A visual illustration of the overlapping parameter $op$ between
sliding windows $w_{i,i>0}$ and an event $e_{j}$: (a) demonstrates the
scenario when they have the same width, (b) depicts the case when the event is
half the width of $w_{i}$, and (c) illustrates that the peak of the
overlapping parameter $op$ is achieved at the midpoint of the relevant event
associated with windows $w_{i}$

###  II-C Principle of Event Detection

The principle of event detection using sliding windows and the overlapping
parameter $op$ is rooted in training a deep learning model $M$. This model
learns to predict the $op$ value for unseen windows $w_{p,p>0}$. Once trained,
model $M$ can be applied to any window $w_{p}$ to obtain a predicted value of
$op_{p}$. These predicted $op_{p}$ values can then be used to identify
features indicative of events. Typically, the maximum values (peaks) in
$op_{p}$ correspond to the mid-times of potential events, as illustrated in
Fig. 1.

These peaks can be identified and analyzed to extract the events represented
by the following intervals:

$e_{q}=\left[t_{q}-\dfrac{width\\_events}{2},t_{q}+\dfrac{width\\_events}{2}\right]$

where $t_{q}$ represents the mid-time of the q-th peak and $width\\_events$ is
the width of events. The extracted events can then be compared with ground
truth events to evaluate the model’s performance. For a theoretical discussion
on the existence of model $M$, based on universal approximation theorems,
please refer to [7].

##  III Stacked Ensemble Learning

To enhance the robustness of predicting $op$, we employ a stacked ensemble
learning approach. This approach combines multiple deep learning models to
improve the overall performance of the system. The concept behind stacked
ensemble learning is to use the predictions of several base models as input to
a meta-model, which then makes the final prediction. This allows the system to
leverage the strengths of multiple models and reduce the impact of their
individual weaknesses. By combining different models, the stacked ensemble can
achieve better performance and improved robustness compared to using a single
model alone. For more details, please refer to [7].

##  IV The Package

The section of most interest to practitioners is where we present the package
and explain how all the parameters we have discussed can be used and
initialized. The package can be found here.

###  IV-A MetaModel

The first thing to do when using this package is to instantiate the MetaModel
object. This object serves as the foundation for building and training the
stacked ensemble meta-model. It provides a convenient interface for
configuring the various parameters of the method and managing the training
process. To initialize the MetaModel object, we need to provide several
arguments, including the time series dataset, the reference events, the
sliding window width, the events width, and the output directory where the
results and models will be saved.

The MetaModel class provides several optional arguments for customization.
Comprehensive documentation for the MetaModel object and its methods,
including a complete list of optional arguments, is available here.

To initialize the meta-model, follow the steps outlined in the provided code
snippet:  ⬇ 1from eventdetector_ts.metamodel.meta_model 2 import MetaModel
3meta_model = MetaModel( 4 dataset=dataset, 5 events=events, 6 width=width, 7
width_events=width_events, 8 output_dir=output_dir)
9meta_model.prepare_data_and_computing_op()
10meta_model.build_stacking_learning()

###  IV-B Event Extraction Optimization

In practice, deep learning models used for regression tasks can sometimes
generate noisy predictions. In our case, this noise can cause problems when
estimating peak locations, leading to the identification of false events. To
address this issue, we smooth the predictions using a Gaussian filter.
However, to optimize the event extraction process, we need to fine-tune
several parameters. These include the size of the Gaussian filter, its
standard deviation, and the threshold used for peak consideration. By
optimizing these parameters, we can more accurately identify predicted events
and improve the overall performance of the meta-model. We evaluate the
performance of this process using metrics such as the F1-Score, which combines
precision and recall to provide a balanced evaluation of the algorithm’s
ability to correctly identify events. The goal is to maximize the F1-Score by
simultaneously optimizing both precision and recall. For more details, please
refer to [7]. To apply this process and run the event extraction optimization,
we can call the following method:  ⬇
1meta_model.event_extraction_optimization()

###  IV-C Visualizing and Evaluating Results

The final step is to visualize the results, including the losses of the
stacked models and the meta-model, true/predicted $op$, true/predicted events,
and a histogram illustrating the time shift between the true and predicted
events. This offers a visual assessment of the meta-model’s performance and an
evaluation of its ability to predict the target events. We can make use of the
plot_save method provided by the package to generate and save these plots. To
create and save these plots, we can utilize the following code snippet:

⬇ 1meta_model.plot_save(show_plots=True)

##  V Application Scenarios and Performance Evaluation

In this section, our goal is to showcase the versatility and simplicity of our
method by demonstrating its wide range of applications. We emphasize its
effectiveness in delivering robust and accurate results for event detection in
time series data, as well as its adaptability for information retrieval in
NLP. To do this, we present five distinct cases. Four of these cases revolve
around information retrieval in textual data within the NLP domain, while the
remaining case addresses credit card fraud detection in the field of financial
security. This diverse set of scenarios illustrates the flexibility and
applicability of our method and underscores its usability across various
domains.

###  V-A Datasets

####  V-A1 Credit Card Fraud Detection

The first case is focused on the detection of credit card fraud, utilizing a
dataset provided by [8]. This dataset contains transaction data, encompassing
both legitimate and fraudulent credit card transactions. Credit card fraud is
a significant concern within the financial industry, involving the
unauthorized use of someone else’s credit card information for fraudulent
purposes. The dataset represents a time series with a time sampling of 1
second, comprising 492 frauds (events) out of 284,807 transactions. Notably,
this dataset exhibits a high level of class imbalance, with the positive class
(frauds) accounting for only 0.172% of all transactions. The initial dataset
was made for binary classification, where a column represents fraud events. To
be used by our package, we have converted this column into a list of reference
events represented as time points based on the time sampling of the dataset.

####  V-A2 Information Retrieval in Textual Data for NLP

In our second evaluation scenario, we shift our focus towards the extraction
of keywords and the identification of adjectives for part of speech tagging
(POS) in textual data. For detailed insights into keyword extraction, please
consult [9, 10, 11, 12, 13, 14]. Additionally, for further information on part
of speech tagging, refer to [15]. To conduct this evaluation, we draw upon two
extensive English texts sourced from the Wikipedia dump [16]. One of these
texts centers around Autism [17], while the other delves into Anarchism [17].
To effectively utilize our package, originally tailored for real-time series
data and temporal events, we must first convert these texts into real-time
series. Subsequently, we’ll establish a mapping between keywords and
adjectives to represent them as real-time events.

To convert a text into a real-time series, we initially tokenize the text into
individual words [18]. Following tokenization, we leverage word embedding
techniques like Word2Vec [19, 20, 21]. Word2Vec transforms words into dense
numerical representations within a high-dimensional space, typically
comprising 300 features.

The code snippet illustrating this process can be found here.

Given that keywords and adjectives may occur at various positions within the
text (which has been transformed into a time series), we establish a mapping
between these positions and corresponding timestamps based on the index of the
obtained time series. This mapping enables us to convert occurrences of
keywords and adjectives within the text into temporal values. Subsequently, by
specifying a value for the event’s width ($width\\_events$), we represent them
as temporal events. For this evaluation, we have selected a set of 20
reference keywords associated with the Autism and Anarchism texts.
Additionally, the list of reference adjectives has been obtained using the
Natural Language Toolkit library [18] on these texts. As a result, for each of
these texts, we create two cases: one for keyword extraction (Autism (Keys)
and Anarchism (Keys)) and another for finding adjectives (Autism (POS) and
Anarchism (POS)), as outlined in TABLE. I.

###  V-B Results

In this section, we present the result evaluations of our method across the
specified use cases, assessing its performance using three key metrics:
F1-Score, Precision, and Recall. The results of these evaluations are
presented in TABLE. I. Each block represents a use case, and each line within
the block is characterized by a distinct configuration of the meta-model,
involving variations in sliding window width and stacked models.

All the presented use cases with code can be found at the following links:
Information Retrieval in NLP and Credit Card Fraud.

TABLE I: Performance of Our Method Across Multiple Use Cases Dataset | $width$ | $step$ | $width\\_events$ | Stacked Models | Hyper-parameters | Meta-model | F1-Score | Precision | Recall
---|---|---|---|---|---|---|---|---|---
Credit card fraud | 2 | 1 | 1 | Default | Default | Average | 0.84 | 0.98 | 0.73
| 3 | 1 | 1 | Default | Default | Average | 0.83 | 0.96 | 0.73
| 2 | 1 | 1 | CNN, LSTM | Default | Average | 0.82 | 0.93 | 0.73
| 2 | 1 | 1 | TRANSFORMER | Default | Average | 0.82 | 0.93 | 0.73
| 2 | 1 | 1 | FFN | (1, 20, 20) | Average | 0.84 | 1.0 | 0.73
Autism (Keys) | 2 | 1 | 1 | Default | Default | Average | 0.98 | 1.00 | 0.96
| 3 | 1 | 1 | Default | Default | Average | 0.97 | 0.99 | 0.96
Autism (POS) | 2 | 1 | 1 | Default | Default | Average | 0.80 | 0.85 | 0.75
| 3 | 1 | 1 | Default | Default | Average | 0.80 | 0.85 | 0.75
| 3 | 1 | 1 | GRU | Default | Average | 0.80 | 0.80 | 0.80
Anarchism (Keys) | 2 | 1 | 1 | Default | Default | Average | 0.99 | 1.00 | 0.98
| 2 | 1 | 1 | CONV_LSTM1D | Default | Average | 0.98 | 0.98 | 0.98
Anarchism (POS) | 2 | 1 | 1 | Default | Default | Average | 0.77 | 0.89 | 0.68
| 3 | 1 | 1 | Default | Default | Average | 0.77 | 0.88 | 0.69
| 3 | 1 | 1 | (CNN_RNN, 2) | Default | FFN | 0.79 | 1.00 | 0.65

Figure 2: Training and validation losses of the stacked models (a), as well as
the comparison of predicted and true $op$ (b) associated with the first row
within TABLE. I.

Fig. 2 displays the training and validation losses (MSE) of the stacked models
during the training process for the first row within TABLE. I. The low losses
observed in this case indicate that the meta-model has successfully learned
the underlying patterns behind the $op$ values, justifying the good metrics
obtained. Moreover, the predicted $op$ values exhibit a remarkable alignment
with the true values, showing minimal fluctuations. This underscores the
importance of employing a Gaussian filter to smoothen the predictions [7].
It’s worth noting that occasional additional peaks are observed, emphasizing
the need for employing a peak threshold to filter out false peaks. These steps
ultimately contribute to enhancing the accuracy of the predictions. The
results obtained showcase promising metrics, underscoring the effectiveness of
our method across diverse domains. It is important to emphasize that our
primary objective is not to attain state-of-the-art metrics for each use case
presented here but to demonstrate our method’s versatility and the easy use of
the package in various domains. To achieve state-of-the-art metrics, a deeper
exploration of hyper-parameter optimization for both the stacked models and
the meta-model is necessary. This deeper optimization could lead to further
enhancements in our method’s performance, potentially yielding superior
results. Even when employing the meta-model’s default settings, we
consistently observe robust metrics, as corroborated by a review analysis of
credit card fraud detection performance [22]. The reported F1 scores, ranging
from 0.80 to 0.89, align with our findings and affirm the reliability of our
method.

##  VI Conclusion

We have introduced a novel deep-learning supervised method designed for the
detection of events in multivariate time series data. Our method stands out
due to several unique characteristics when compared to existing deep-learning
supervised approaches. These include a focus on regression rather than binary
classification, the capability to operate with a list of ground truth events
as opposed to fully labeled datasets, the implementation of a stacked ensemble
learning meta-model to enhance robustness, and the provision of a user-
friendly Python package for practical implementations. Through a series of
diverse use cases spanning natural language processing (NLP) tasks such as
keyword extraction and part of speech tagging, as well as credit card fraud
detection for financial security domains, we have underscored the universality
of our method with a primary objective is not to attain state-of-the-art
metrics rather than affirming its adaptability across various domains. The
extensive and user-friendly API provided by our package simplifies the process
of event detection for real-time data and other applications. It also allows
for in-depth exploration of hyperparameter optimization for both the stacked
models and the meta-model, offering the potential to achieve even more
remarkable results with our method. However, it is essential to acknowledge
that our method and the accompanying package have certain limitations.
Notably, multi-class event detection may not be straightforward. In scenarios
where multiple classes of events need to be detected, it becomes necessary to
train separate meta-models to learn the $op$ associated with each individual
class. While this approach adds complexity to the implementation, it also
highlights an area for potential improvement in future iterations of our
method. In addition, we may also want to test our approach on a variety of
different datasets from different fields, with a focus on obtaining state-of-
the-art metrics on each dataset compared to other methods. This would allow us
to highlight the benefits of our method, such as the small number of
parameters needed to train FFNs, which reduces the computational resources
required and makes it a more sustainable and environmentally friendly
solution.

## Acknowledgment

This project was undertaken as part of the France Relance Program, under the
agreement UT3 - N°0002890, with the support of the French Ministère de
l’Economie des Finances et de la Souveraineté Industrielle et Numérique. We
would like to express our gratitude to Akkodis, Université Paul Sabatier
Toulouse III, CNRS, and IRAP. Their contributions have been invaluable to the
success of this project.

## References

  * [1] Z. Zamanzadeh Darban, G. I. Webb, S. Pan, C. C. Aggarwal, and M. Salehi, “Deep learning for time series anomaly detection: A survey,” 2022.
  * [2] T. K. K. Ho, A. Karami, and N. Armanfard, “Graph-based time-series anomaly detection: A survey,” 2023.
  * [3] S. Aminikhanghahi and D. Cook, “A survey of methods for time series change point detection,” in Knowledge and Information Systems, vol. 51, May 2017. https://doi.org/10.1007/s10115-016-0987-z.
  * [4] S. Han, X. Hu, H. Huang, M. Jiang, and Y. Zhao, “ADBench: Anomaly Detection Benchmark,” in Advances in Neural Information Processing Systems, vol. 35, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds. Curran Associates, Inc., 2022, pp. 32142-32159.
  * [5] Y. Zhao, Z. Nasrullah, and Z. Li, “PyOD: A Python Toolbox for Scalable Outlier Detection,” in Journal of Machine Learning Research (JMLR), vol. 20, no. 96, pp. 1-7, 2019.
  * [6] T. G. Dietterich, “Ensemble methods in machine learning,” in Multiple Classifier Systems, Berlin, Heidelberg, 2000, pp. 1-15. Springer Berlin Heidelberg. ISBN 978-3-540-45014-6.
  * [7] M. Azib, B. Renard, P. Garnier, V. Génot, and N. André, “Universal Event Detection in Time Series,” 2023, [Online]. Available: https://doi.org/10.31219/osf.io/uabjg.
  * [8] A. Dal Pozzolo, O. Caelen, Y. Le Borgne, S. Waterschoot, and G. Bontempi, “Learned lessons in credit card fraud detection from a practitioner perspective,” Expert Systems with Applications, vol. 41, no. 10, pp. 4915-4928, 2014.
  * [9] K. Spärck Jones, “A statistical interpretation of term specificity and its application in retrieval,” J. Documentation, vol. 60, pp. 493-502, 2021.
  * [10] Y. Zhang, E. Milios, and A. Zincir-Heywood, “A Comparative Study on Key Phrase Extraction Methods in Automatic Web Site Summarization,” JDIM, vol. 5, pp. 323-332, 2007.
  * [11] S. Lee and H. Kim, “News Keyword Extraction for Topic Tracking,” pp. 554-559, 2008, doi: 10.1109/NCM.2008.199.
  * [12] Z. Wu and C. L. Giles, “Measuring Term Informativeness in Context,” in Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Atlanta, GA, 2013, pp. 259-269.
  * [13] J. Rennie and T. Jaakkola, “Using term informativeness for named entity detection,” pp. 353-360, 2005, doi: 10.1145/1076034.1076095.
  * [14] C. Florescu and C. Caragea, “A New Scheme for Scoring Phrases in Unsupervised Keyphrase Extraction,” in Advances in Information Retrieval, J. Jose et al., Eds., vol. 10193, Lecture Notes in Computer Science, Cham: Springer International Publishing, 2017, doi: 10.1007/978-3-319-56608-5_37.
  * [15] A. Chiche and B. Yitagesu, “Part of speech tagging: a systematic review of deep learning and machine learning approaches,” Journal of Big Data, vol. 9, no. 10, Jan. 2022.
  * [16] Wikimedia Foundation, “Wikimedia Downloads,” [Online]. Available: https://dumps.wikimedia.org.
  * [17] Hugging Face. ‘Wikipedia Dataset.’ [Online]. Available: https://huggingface.co/datasets/wikipedia/viewer/20220301.en/train.
  * [18] S. Bird, E. Klein, and E. Loper, “Natural Language Processing with Python: Analyzing Text with the Natural Language Toolkit”. O’Reilly Media, Inc., 2009.
  * [19] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient Estimation of Word Representations in Vector Space,” in Proceedings of Workshop at ICLR, 2013, arXiv:1301.3781v1.
  * [20] J. Pennington, R. Socher, and C. D. Manning, “GloVe: Global vectors for word representation,” in Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), 2014, pp. 1532-1543.
  * [21] P. Bojanowski, E. Grave, A. Joulin, and T. Mikolov, “Enriching word vectors with subword information,” Transactions of the Association for Computational Linguistics, vol. 5, pp. 135-146, 2017.
  * [22] I. Sadgali, N. Sael, and F. Benabbou, “Bidirectional gated recurrent unit for improving classification in credit card fraud detection,” Indonesian Journal of Electrical Engineering and Computer Science, vol. 21, pp. 1704-1712, Mar. 2021, doi: 10.11591/ijeecs.v21.i3.pp1704-1712.


# ResMGCN: Residual Message Graph Convolution Network for Fast Biomedical
Interactions Discovering

Zecheng Yin
The Chinese University of Hong Kong (Shenzhen), Shenzhen, China
<EMAIL_ADDRESS>
###### Abstract

Biomedical information graphs are crucial for interaction discovering of
biomedical information in modern age, such as identification of multifarious
molecular interactions and drug discovery, which attracts increasing interests
in biomedicine, bioinformatics, and human healthcare communities. Nowadays,
more and more graph neural networks have been proposed to learn the entities
of biomedical information and precisely reveal biomedical molecule
interactions with state-of-the-art results. These methods remedy the fading of
features from a far distance but suffer from remedying such problem at the
expensive cost of redundant memory and time. In our paper, we propose a novel
Residual Message Graph Convolution Network (ResMGCN) for fast and precise
biomedical interaction prediction in a different idea. Specifically, instead
of enhancing the message from far nodes, ResMGCN aggregates lower-order
information with the next round higher information to guide the node update to
obtain a more meaningful node representation. ResMGCN is able to perceive and
preserve various messages from the previous layer and high-order information
in the current layer with least memory and time cost to obtain informative
representations of biomedical entities. We conduct experiments on four
biomedical interaction network datasets, including protein-protein, drug-drug,
drug-target, and gene-disease interactions, which demonstrates that ResMGCN
outperforms previous state-of-the-art models while achieving superb
effectiveness on both storage and time. Our code and involved datasets are
publicly available at *.

###### Index Terms:

residual message graph convolution, interaction prediction, biomedical
interaction networks.

##  I Introduction

A biological information system is an amazingly sophisticated and interesting
network consisting of various biological molecules such as proteins, genes, as
well as the interaction/reactions between these entities. The bioinformation
between these molecules can be represented as a information graph, with
molecular entities as nodes and interactions as edges between them.
Distinguished from language or image, graph structure representation of the
system offers a conceptual and intuitive precondition for further explore to
understand or discover the direct or indirect interactions between molecular
entities in the biological system[1][2]. Such technology boosted the explore
of biology in system level and made novel discoveries in interactions such as
drug-drug interactions (DDI)[3], drug-target interactions(DTI)[4], gene-
disease associations (GDI)[5], and protein-protein interactions (PPI)[6].

Recently, a great number of deep learning methods are proposed to achieve
promising performance across various domains, such as recommendation
systems[7][8], chemistry[9], citation networks[10][11][12], social
networks[13] and medicine[14]. Most of these works are based on Graph
Convolution Network (GCN)[15]. GCN is a popular work that passes the messages
of neigbhouring nodes to the central node repeatedly by stacking multiple GCN
layers, to learn the predictive representation of the nodes for downstream
tasks. Although GCN-based models show great success in link prediction in
bioinformatics[3][16], there is a fundamental issue existing in GCN, which
might depress the representation ability of biomedical graphs. GCN could not
obtain information from different hierarchy at the same time and use these
information to guide node updates. [17] and HOGCN[18] and SkipGNN[17] deem
that GCN only considers the instant neighbours (also known as 1-hop
neighbours) and message from nodes at a long distance is diminished on the
way. Therefore, they conduct different methods to alleviate this problem.
HOGCN[18] calculates messages from neighbours up to K hops at one time in one
layer to combine information of neighbours from different distances, but it is
computationally expensive and causes slow network propagation and
optimization. SkipGNN[17] leverages a copy of the original graph but with
1-hop neighbour removed and 2-hop neighbour connected to preserve information
of 2-hop neighbours, and shows improvement. However, reconstructing a copy of
the original graph and processing a new 2-hop connected graph itself is
expensive in both storage and time.

Targeting this pain point, inspired by ResNet[19] in computer vision, instead
of handling the messages from nodes far away in expensive computational or
storage cost, we propose Residual Message Graph Convolution Network (ResMGCN),
a simple but effective improvement on GCN, a novel graph convolution that is
able to effectively preserve lower order information and process together with
the instant neighbour message to guide this layer’s node update to obtain
informative representation. We applied ResMGCN on an end2end biomedical entity
representation learning that learns every entity of a biomedical system via an
interaction network $\mathcal{G}$ and its features $X$ and conduct link
prediction on two certain entities to determine whether they have meaningful
interaction or not. Specifically, we first encode the biomedical graph using
ResMGCN that utilizes low-order and high-order information, then define a
simple linear decoder to predict interactions between the nodes.

We demonstrate our ResMGCN’s performance with state-of-the-art heuristic
learning methods[20], network embedding methods [21, 22, 23, 24], and graph
convolution-based methods [17, 15, 18] for biomedical link prediction. We
conduct our experiments on four publicly available datasets that represent
various interaction in biomedical. ResMGCN outperforms the methods above both
in accuracy and computation, demonstrating the superiority of ResNGCN
mechanism.

We conduct case study on the PDI network to show that graph neural network
using ResMGCN is able to learn meaningful informative entity representation of
biomedical molecules.

In conclusion, our paper proposed residual graph convolution for predicting
links between entities from the biomedical system, a novel graph convolution
with leveraging low and high-order information in node representation
learning, simple, fast, and effective. Our code and datasets are publicly
available at *.

##  II Related work

By utilizing molecular biomedical graphs, the goal of biomedical network
prediction is to predict whether it has biomedical information correlation for
two given entity nodes such as drug-drug, protein-protein, drug-gene, etc.
There are three main flows of graph-based methods to achieve such goal: (1)
Heuristic learning comes with the idea that it may exist a link if a pair of
unconnected nodes are similar or close in the network. Methods such as [25,
26], computes a similarity score by a certain expert-designed algorithm to
represent how close the two nodes are. They are often limited to give strong
constraints on the network and idealize the graph heavily to satisfy certain
properties, which requires expert knowledge and departures from real-world
scenarios. (2) Direct graph embedding such as [24, 22, 21] generates
embeddings for nodes in the graph by absorbing the topology information. Even
though these methods is intuitive and simple, they are limited to only model
the topology information and lose the rich information of the nodes. (3)
Neural network based representation learning utilizes graph convolution and
learns graph entity informative representations and predicts node interactions
by downstream predictor. In concrete, they learn node representation by
aggregating the information from neighbour nodes (a.k.a. message passing[27])
and optimize the process by downstream task loss like link prediction in a
convenient end2end manner. In GCN layer, spatially speaking, the node can only
obtain its own first-order neighbor information in message passing process and
then update its own representation. It’s the same with its neighbour nodes. In
this case, the higher-order information from the far end can be indirectly
obtained by stacking multiple graph convolutional layers, because its first-
order neighbor also has obtained neighbor information of theirs. Details of
this process are discussed in section III-B.

##  III Preliminaries

The graph in a biomedical system is defined as
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{X})$, where $\mathcal{V}$ is
the set of nodes in biomedical entities such as gene, protein, drug, and
$\mathcal{E}$ is the set of edges information denoting the interactions
between the entities in biomedical system, and $\mathcal{X}\in
R^{|\mathcal{V}|\times F}$ is the node feature representing the information of
each entity and can help graph convolution with additional information other
than topology information, where $F$ is feature dimension.

Our goal in constructing biomedical information graph is to learn a predictor
$P$ which is able to tell whether two arbitrary entities in a biomedical
system interact with each other.

###  III-A Message Passing Framework

(a) Collect messages from the 1-hop neighbour.

(b) Update the node representation accordingly.

Figure 1: Message passing framework illustration. Message step takes
representations of multiple nearby neighbours to calculate the message the
node needed for updating, formulated in Eq.1. Passing step updates the node
representation according to the message provided by the first step and its own
original representation, formulated in Eq.2.

In recent days, spatial graph convolution theory attracts more and more
attentions after GCN is proposed. In message passing framework[28], as shown
in Figure 1, to learn an informative representation requires nodes
interaction, and the interaction operation is divided into 2 steps: message
and passing, where message is the various information to guide node
representation learning and passing is an update process that utilizes the
message into new representation.

In most graph convolutions, the message $m_{i}$ in message step is calculated
from nearby node representation, formulated as a function $f_{m}$ that takes
representations of neighbouring nodes (1-hop neighbour) and calculates the
message the central node $v_{i}$ needs:

$m_{i}=f_{m}(\\{x_{j}\\}),j\in\mathcal{N}_{i}$ (1)

where $\mathcal{N}_{i}$ is the index set of neighbourhood of node $v_{i}$. In
passing step, the node $v_{i}$ takes the message mi obtained in last step and
its own representation $x_{i}$ to update the representation of node $v_{i}$,
formulated as a update function $f_{u}$:

$x_{i}^{\prime}=f_{u}(m_{i},x_{i})$ (2)

Various of recently proposed graph convolutions apply different $f_{m}$ and
$f_{u}$ as all kinds of variants of message passing framework.

Figure 2: Illustration of multiplayer of message passing. Node $v_{i}$ is able
to capture messages from node $v_{j}$ via node $v_{k}$ by stacking two layers
of graph convolution.

As an interesting case to note, nodes is able to capture k-hop (k $>$ 1)
neighbours’ message by stacking multiple graph convolution layers, in an
indirect manner. As shown in Figure 2, we take 2-layer message passing as an
example, the first layer node only receives 1-hop messages of node $v_{i}$,
while in the second layer node, however, node $v_{i}$ will be able to sense
its 2-hop messages through the update of its 1-hop neighbour node $v_{k}$
indirectly, as the neighbour nodes $v_{k}$ is also updated with messages from
its 1-hop neighbour such as node $v_{j}$, which is the 2-hop neighbour for
node $v_{i}$.

###  III-B Graph Convolution(GCN)

Graph Convolution Network[15] is a popular implement version of graph
convolutions. Derived from spectral graph signal processing[29][30], it
extends the convolution operation in computer vision or natural language
processing to graph-structured data. In graph spectral space, the GCN is
actually an ideal simplified version of ChebyNet[29] series, but in recent
days people care more about what GCN processes the message in spatial space,
as spatial space is much more intuitive, and thus developed a message passing
system to describe different implementations of graph convolution. Concretely,
GCN layer takes edge information as the adjacency matrix of graph $A$ and node
feature matrix $X$ to update, where the element of adjacency matrix $A$ is
defined as:

$A_{ij}=\begin{cases}1&if\ v_{i}\ connects\ v_{j}\\\ 0&else\end{cases}$ (3)

In spectral space, GCN layer is denoted as:

$X^{\prime}={f}(X,A)=\sigma\left(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}XW\right)$
(4)

where $D\in\mathbb{R}^{n\times n}$ is the degree matrix of the graph, a
diagonal matrix with each degree of nodes on the diagonal, $n$ is the number
of nodes, and $d$ is the feature dimension, and $\hat{A}\in\mathbb{R}^{n\times
n}=A+I$ is the adjacency matrix with self-loops, and $X\in\mathbb{R}^{n\times
d}$ is node feature matrix, $W\in\mathbb{R}^{d\times o}$ is a learnable linear
transformation matrix of GCN to strengthen learning capability[15], $o$ is
output dimension of this layer.

##  IV Proposed Residual GCN

###  IV-A Message Passing in GCN

In the paper, GCN is proposed in a spectral form, on the other side, however,
in spatial space, in an equivalent wayA, we can also interpret GCN as follows:

$x_{i}^{\prime}=\sigma(\frac{1}{\sqrt{d_{i}}}(\frac{1}{\sqrt{d_{i}}}x_{i}+\sum_{j\in\mathcal{N}_{i}}\frac{1}{\sqrt{d_{j}}}x_{j})W)$
(5)

where $x_{i}\in\mathbb{R}^{1\times d}$ is the node representation of single
node $v_{i}$. To fit into the message passing framework, we separate the
operation as follows. GCN sums up linear projected 1-hop neighbour
representation as message function, and updates the node by taking the mean
value of the neighbouring and its own linear projected representation. GCN
layer’s operations are formulated as:

$m_{i}=f_{m}(\\{x_{j}\\})=\sum_{j\in\mathcal{N}_{i}}\frac{1}{\sqrt{d_{j}}}x_{j}W$
(6)
$x_{i}^{\prime}=f_{u}(m_{i},x_{i})=\frac{1}{\sqrt{d_{i}}}({m_{i}+\frac{1}{\sqrt{d_{i}}}x_{i}W})$
(7)

The illustration of this process is illustrated in Figure 3.

###  IV-B Residual Message GCN (ResMGCN)

In biomedical data graphs, hierarchical connection correlations are crucial
because new reactions or new drug molecular effects are often based on the
progression of previous reaction information, which means information or
message from recent lower order is extremely crucial, thus requires advanced
information processing for messages from both last layer and current layer.

To address this problem, inspired by ResNet[19], we propose Residual Message
GCN (ResMGCN), a simple but effective improvement for message fusion
processing.

In the section IV-A, the message $m_{i}$ denotes different information in the
different layer. For example, with $l$ denotes the layer index, for a 2-layer
GCN, in the first layer $m^{1}$ is the message from 1-hop, while in the second
layer, $m^{2}$ is the message from 2-hop neighbour via 1-hop neighbour, and so
on. In order to jointly obtain hierarchical information and current
information to guide node updates at the same time, we add a shortcut for
message passing framework in different layers. Let $l$ the denote ResMGCN
layer index, ResMGCN is formulated as:

$m_{i}^{l}=f_{m}(\\{x_{j}\\}),j\in\mathcal{N}_{i}$ (8)
$c_{i}^{l}=\Phi(m_{i}^{l},m_{i}^{(l-1)})$ (9)
$x_{i}^{l}=f_{u}(c_{i}^{l},x_{i}^{(l-1)})$ (10)

where $\Phi$ is a message fusion function to handle message from the current
layer and last layer, to provide both lower and current information, and $l$
denotes layer index of ResMGCN, and $m_{i}^{l}$ denotes indirect distant
message of $l$th layer, and $c_{i}^{l}$ denotes combined information from the
different layer. The message from the previous layer flows into the current
layer as message residue. The residual message and current message are fused
by the fusion function $\Phi$ to guide node representation learning together.

Figure 3: Illustration of message passing. The layer outputs the updated node
representation $X$ for the next layer. The messages are left within the
current layer. Figure 4: Illustration of ResMGCN. Besides of the updated
representations, layer keeps the messages of current layer and pass the
hierarchy information for next layer. Each layer has a information fusion
function $\Phi$ to manage the information received for calculating the guided
information $C$ for node updating.

In Figure 3 and Figure 4, $M$ is the total messages of all nodes, and $C$ is
the total fused messages of all nodes, and $l$ indicates the layer index, and
$X$ denotes the node representation matrix. In the Figures, message or
information from the lower hierarchy could flow better compared to the
original, which provide fundamental interaction information for the current
layer from the previous layer.

##  V ResMGCN for biomedical interaction prediction

###  V-A Graph ResMGCN Feature Encoder

We develop ResMGCN to fuse information from the different hierarchy of
biomedical graphs. We conduct ResMGCN as graph feature encoder as a component
in an end2end model and learn link prediction by linear predictor from
biomedical graph representation. Specifically, the ResMGCN in end2end model
is:

$m_{i}^{l}=f_{m}(\\{x_{j}^{(l-1)}\\})=\sum_{j\in\mathcal{N}_{i}}\frac{1}{\sqrt{d_{j}}}x_{j}^{(l-1)}W$
(11)
$c_{i}^{l}=\Phi(m_{i}^{l},m_{i}^{(l-1)})=\frac{1}{2}(m_{i}^{l}+m_{i}^{(l-1)})$
(12)
$x_{i}^{l}=f_{u}(c_{i}^{l},x_{i}^{l})=\sigma(\frac{1}{\sqrt{d_{i}}}({c_{i}^{l}+\frac{1}{\sqrt{d_{i}}}x_{i}^{(l-1)}}W))$
(13)

###  V-B Graph Predictor

After feature encoding of the biomedical interaction graph, we introduce a
simple linear predictor that takes the combination of feature from two
entities and predicts the probability of interaction. For two embedded node
representation $h_{i}$ and $h_{j}$, the predictor is formulated as:

$p_{ij}=\sigma(\Psi(h_{i},h_{j})W_{p}+b)$

where $p_{ij}$ is the probability of interaction between nodes $v_{i}$ and
$v_{j}$, $W_{p}\in\mathbb{R}^{2d\times 1}$ is a learnable weight matrix of the
predictor,$h_{i}\in\mathbb{R}^{1\times d}$ and $h_{j}\in\mathbb{R}^{1\times
d}$ are node representation vectors of two arbitrary node $v_{i}$ and $v_{j}$,
$d$ is feature dimension, $b$ is the bias of the predictor, $\sigma$ is a non-
linear activation function, and $\Psi$ is a combination function that combines
node feature $h_{i}$ and $h_{j}$ such as concatenation. We use vector
concatenation as $\Psi$ function (same as SkipGNN) for a fair comparison with
many baselines.

###  V-C Model Training and Optimization

We apply binary cross entropy loss to optimize the model parameters:

$\mathcal{L}(v_{i},v_{j})=-((1-A_{ij})log(1-p_{ij})+A_{ij}log(p_{ij}))$ (14)

where $p_{ij}$ is the predicted interaction or reaction probability between
node $v_{i}$ and $v_{j}$, and $A_{ij}$ denotes the label interaction (also the
adjacency information) among nodes. Cross entropy loss could guide the model
to predict a higher probability for ground truth interactions than that for
non-interactions. For all nodes in training set, $\mathcal{L}$ is:

$\mathcal{L}=\sum_{(i,j)\in\mathcal{E}}\mathcal{L}(v_{i},v_{j})$ (15)

As an end2end model, the training information flows back from cross entropy
loss to predictor and to feature encoder ResMGCN in the end during
backpropagation.

##  VI Experiment

The biomedical interaction prediction problem is solved by a link prediction
task on the interaction network. We conduct experiments on various interaction
datasets and compare our ResMGCN with state-of-the-art models.

####  VI-1 Datasets

We conduct link prediction experiments on four datasets in wide fields of
bioinformatics, and all of them are publicly available. Details of the
datasets are summarized in Table I.

  * •

BioSNAP-DTI[4]: DTI network contains 15,139 drug-target interactions between
5,018 drugs and 2,325 proteins.

  * •

BioSNAP-DDI[3]: DDI network contains 48,514 drug-drug interactions between
1,514 drugs extracted from drug labels and biomedical literature.

  * •

HuRI-PPI[6]: HI-III human PPI network contains 5,604 proteins and 23,322
interactions generated by multiple orthogonal high-throughput yeast two-hybrid
screens.

  * •

DisGeNET-GDI [5]: GDI network consists of 81,746 interactions between 9,413
genes and 10,370 diseases curated from GWAS studies, animal models and
scientific literature.

TABLE I: Summary of the Datasets Dataset | # Nodes | # Edges train | # Edges validate | # Edges test | Edges Total | Avg. degree
---|---|---|---|---|---|---
DTI | 5,018 drugs, 2,325 proteins | 10,597 | 1,514 | 3,028 | 15,139 | 4.12
DDI | 1,514 drugs | 33,960 | 4,852 | 9,702 | 48,514 | 64.09
PPI | 5,604 proteins | 16,326 | 2,332 | 4,664 | 23,322 | 8.32
GDI | 9,413 genes, 10,370 diseases | 57,222 | 8,175 | 16,349 | 81,746 | 8.26

###  VI-A Baselines

We compare ResMGCN with seven powerful predictors of molecular interactions
from network science and graph machine-learning fields. For direct embedding
models, we use three direct network embedding methods: DeepWalk[21],
node2vec[22], and we also include struct2vec[23]. struct2vec and node2vec are
conceptually distinct by leveraging local network structural information,
while Deepwalk uses random walks to learn embeddings for nodes in the network.
Moreover, we compare with five graph neural networks:
VGAE[31],GCN[15],GAT[32], GIN[33],JK-Net[34], MixHop[35] and HOGCN[18]. These
methods utilize graph convolution to extract the informative representations
of biomedical entities, with the same input as ResMGCN. For heuristic
learning, we consider Spectral Clustering[36] and L3[20] heuristic.

###  VI-B Metrics

We use the same evaluations for all baselines. Datasets are divided into
training, validation, and test sets in the ratio of 7:1:2. We use AUROC, which
is the area under the receiver operating characteristic curve, and AUPRC,
which is the area under the Precision-Recall Curve as two evaluation
indicators.

###  VI-C Experimental Settings

For a fair comparison, we provide node initial representation as one hot
initialization and linear link predictor for SkipGNN, HOGCN, and ResMGCN.
SkipGNN implemented by the paper author used one hot initialization, and HOGCN
implemented by the paper author used node2vec representation initialization to
offer informative embedding in the beginning and did not provide the initial
embedding in the Github project. According to the variable-controlling method,
we initialize the node representation with one hot and only change the graph
feature encoder in these three methods to reveal the true comparison of these
methods.

###  VI-D Results

In this section, we demonstrate the performance of baselines and ResMGCN, and
analysis details about the results. The summary of performance is in Table II.
We referred to the statistics from the previous paper[18, 17] and conduct a
fair implementation of HOGCN experiment.

ResMGCN shows very competitive performance compared with all baselines
including state-of-the-art methods both on AUPRC and AUROC on all four
biomedical datasets. ResMGCN outperformed all baselines on DDI and GDI
datasets. In DDI dataset, ResMGCN achieved around 7% higher and 5% higher than
previous sota SkipGNN in AUPRC and AUROC respectively. In GDI dataset, ResMGCN
achieved around 1% higher and 0.4% higher than previous sota HOGCN in AUPRC
and AUROC respectively. In these four datasets, DDI has the highest node
average degree 64.09, whereas other datasets have only less than 10 average
degree. ResMGCN has the best performance in DDI dataset, proving that ResMGCN
is good at handling different hierarchies and dense topology information.
ResMGCN has huge advantages on both data scale and training cost, even though
this is not so revealed in rather in datasets on smaller scales. Dataset GDI
has the greatest amount of nodes and edges (around 20,000), and ResMGCN
outperformed the baselines, together with later
discussionLABEL:sec:trainingcost on training cost analysis, demonstrating the
ResMGCN has good capability of dealing with large dataset.

TABLE II: Average AUPRC and AUROC With One Standard Deviation on Biomedical Interaction Prediction Dataset | Method | AUPRC | AUROC | Rank
---|---|---|---|---
DTI | DeepWalk | 0.753 ± 0.008 | 0.735 ± 0.009 |
| node2vec | 0.771 ± 0.005 | 0.720 ± 0.010 |
| struct2vec | 0.677 ± 0.007 | 0.656 ± 0.010 |
| SC | 0.818 ± 0.007 | 0.743 ± 0.008 |
| L3 | 0.891 ± 0.004 | 0.793 ± 0.006 |
| VGAE | 0.853 ± 0.010 | 0.800 ± 0.010 |
| GCN | 0.904 ± 0.011 | 0.899 ± 0.010 |
| GIN | 0.922 ± 0.004 | 0.907 ± 0.006 | 4
| JK-Net | 0.921 ± 0.006 | 0.907 ± 0.008 |
| MixHop | 0.921 ± 0.006 | 0.920 ± 0.004 | 2
| SkipGNN | 0.928 ± 0.006 | 0.922 ± 0.004 | 1
| HOGCN | 0.929 ± 0.001 | 0.919 ± 0.001 | 3
| ResMGCN | 0.918 ± 0.001 | 0.901 ± 0.010 | 5
DDI | DeepWalk | 0.698 ± 0.012 | 0.712 ± 0.009 |
| node2vec | 0.801 ± 0.004 | 0.809 ± 0.002 |
| struct2vec | 0.643 ± 0.012 | 0.654 ± 0.007 |
| SC | 0.749 ± 0.009 | 0.816 ± 0.006 |
| L3 | 0.860 ± 0.004 | 0.869 ± 0.003 |
| VGAE | 0.844 ± 0.076 | 0.878 ± 0.008 |
| GCN | 0.856 ± 0.005 | 0.875 ± 0.004 |
| GIN | 0.856 ± 0.005 | 0.876 ± 0.003 |
| JK-Net | 0.870 ± 0.009 | 0.885 ± 0.005 | 3
| MixHop | 0.861 ± 0.006 | 0.879 ± 0.004 | 4
| SkipGNN | 0.866 ± 0.006 | 0.886 ± 0.003 | 2
| HOGCN | 0.8501 ± 0.003 | 0.8620 ± 0.002 |
| ResMGCN | 0.9317 ± 0.001 | 0.9360 ± 0.001 | 1
PPI | DeepWalk | 0.715 ± 0.008 | 0.706 ± 0.005 |
| node2vec | 0.773 ± 0.010 | 0.766 ± 0.005 |
| struct2vec | 0.875 ± 0.004 | 0.868 ± 0.006 |
| SC | 0.897 ± 0.003 | 0.859 ± 0.003 |
| L3 | 0.899 ± 0.003 | 0.861 ± 0.003 |
| VGAE | 0.875 ± 0.004 | 0.844 ± 0.006 |
| GCN | 0.909 ± 0.002 | 0.907 ± 0.006 |
| GIN | 0.907 ± 0.004 | 0.897 ± 0.006 |
| JK-Net | 0.912 ± 0.003 | 0.901 ± 0.005 | 3
| MixHop | 0.909 ± 0.004 | 0.913 ± 0.003 |
| SkipGNN | 0.921 ± 0.003 | 0.917 ± 0.004 | 1
| HOGCN | 0.9155 ± 0.002 | 0.9104 ± 0.001 | 2
| ResMGCN | 0.9104 ± 0.001 | 0.8940 ± 0.001 | 4
GDI | DeepWalk | 0.827 ± 0.007 | 0.832 ± 0.003 |
| node2vec | 0.828 ± 0.006 | 0.834 ± 0.003 |
| struct2vec | 0.910 ± 0.006 | 0.909 ± 0.005 |
| SC | 0.905 ± 0.002 | 0.863 ± 0.003 |
| L3 | 0.899 ± 0.001 | 0.832 ± 0.001 |
| VGAE | 0.902 ± 0.006 | 0.873 ± 0.009 |
| GCN | 0.909 ± 0.002 | 0.906 ± 0.006 |
| GIN | 0.916 ± 0.004 | 0.900 ± 0.005 |
| JK-Net | 0.891 ± 0.049 | 0.898 ± 0.002 |
| MixHop | 0.912 ± 0.005 | 0.916 ± 0.004 | 3
| SkipGNN | 0.915 ± 0.003 | 0.912 ± 0.004 | 4
| HOGCN | 0.924 ± 0.001 | 0.921 ± 0.001 | 2
| ResMGCN | 0.935 ± 0.001 | 0.925 ± 0.001 | 1

###  VI-E ResMGCN is simple and much more effective

In this section, we compare ResMGCN effectiveness with state-of-the-art
methods in recent years. We conduct model training on the same server
executing one single task at a time with RTX 3090s. The time cost of hhe
average epoch and training process with their best epoch number, which is the
epoch round that would give the model the best performance on biomedical
indicators, are listed below in Table III. As time cost is also related to
implementation acceleration, we clarify that these methods are all based on
basic matrix multiplication provided by Pytorch.

TABLE III: Summary of the effectiveness of related methods Dataset | Method | Epoch | Training
---|---|---|---
DTI | SkipGNN | 14.8 | 241.8
| HOGCN | 4.70 | 119.6
| ResMGCN | 2.6 | 105.7
DDI | SkipGNN | 55.04 | 749.4
| HOGCN | 12.5 | 503.1
| ResMGCN | 6.3 | 81.7
PPI | SkipGNN | 20.6 | 310.2
| HOGCN | 6.2 | 161.1
| ResMGCN | 3.5 | 55.5
GDI | SkipGNN | 180.9 | 903.6
| HOGCN | 20.3 | 320.0
| ResMGCN | 9.8 | 50.2

We obviously see our proposed ResMGCN reached state-of-the-art effectiveness
compared with all related methods. (1) SkipGNN reconstructed a copy of the
original graph with 1-hop edges removed and 2-hop edges connected to obtain
higher-order information and then aggregates features from the two graphs,
which requires large computation for graph preprocessing and doubled the
memory and time cost. It is too expensive to conduct such operation in a real
large scale scenario. Despite of the performance superiority of ResMGCN, the
time cost of ResMGCN is significantly lower than SkipGNN, nearly one-tenth of
SkipGNN in terms of single epoch cost and up to one eighteenth
($\frac{1}{18}$) of that in terms of single epoch cost. ResMGCN converges in a
significantly fast and effective manner with a superb performance in many of
the datasets. (2) HOGCN is a method that stacks neighbour messages from 0-hop
to up to k-hop in one layer as information fusion, where it requires multiple
matrix multiplications in one single layer, which could cost a huge amount of
time. To gain a fair comparison, we implemented experiments on DDI dataset in
the same settings with HOGCN[18] in sparse adjacency matrix and achieved sota
effectiveness, but our model could reach 5.2s per epoch on this dataset if we
use dense adjacency matrix. Despite of the performance superiority of ResMGCN,
ResMGCN could reach nearly half the time of HOGCN in terms of a single epoch
and up to one sixth ($\frac{1}{6}$) the time of HOGCN in terms of whole
training cost. Other than that, HOGCN[18] needs human hyperparameter k to
preprocess information in the beginning, while ResMGCN is a simple and fully
end2end convolution that doesn’t require any intervention.

The larger the dataset scale, the greater advantages of ResMGCN. The advantage
of ResMGCN is more obvious when it is applied in large datasets such as GDI
dataset. We see greater epoch cost margin compared with PPI whose node number
is 1,514 and GDI whose node number is around 20,000.

As mentioned before, we conduct a fair comparison, we did not apply bilinear
edge reconstruction as HOGCN did, and did not use any trick for higher
performance, which means this is not the end of ResMGCN’s potential, and
further exploration works are expected.

##  VII Conclusion

In this paper, we proposed a novel graph convolution ResMGCN, a new message
passing scheme to fuse information from different hierarchies to guide more
meaningful graph node representations. We conduct solid experiments on four
publicly available datasets on interaction prediction and compare ResMGCN with
state-of-the-art baselines. ResMGCN outperforms all baselines with clear
improvement on interaction prediction task on the biomedical information
graph, as ResMGCN learns informative representation through interacted
messages from various orders of neighbour. Moreover, the proposed shortcut
scheme enables ResMGCN to process significantly fast and effective feature
encoding both on computation and storage compared with the methods which try
to alleviate the similar issue. The experiments of biomedical interaction
prediction and effectiveness comparison demonstrates ResMGCN’s superiority and
great potential in other related areas.

##  Appendix A Proof of the Equivalence of spatial and spectral convolution of
GCN

$X^{\prime}={f}(X,A)=\sigma\left(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}XW\right)$
(16)

where $D\in\mathbb{R}^{n\times n}$ is the degree matrix of the graph,
$A\in\mathbb{R}^{n\times n}$ is the adjacency matrix of the graph,
$X\in\mathbb{R}^{n\times d}$ is the representation matrix of all nodes in the
graph. Taking a graph composed of three nodes as an example, we explicitly
demonstrate the every element of $D$,$A$ and $X$ matrices. These matrices are
denoted as:

$\left[\\!\begin{array}[]{c}x^{\prime}_{1}\\\ x^{\prime}_{2}\\\
x^{\prime}_{3}\end{array}\\!\right]\\!=\\!\sigma(\left[\begin{array}[]{ccc}d_{1}^{-\frac{1}{2}}&0&0\\\
0&d_{2}^{-\frac{1}{2}}&0\\\
0&0&d_{3}^{-\frac{1}{2}}\end{array}\\!\right]\left[\begin{array}[]{ccc}a_{11}&a_{12}&a_{13}\\\
a_{21}&a_{22}&a_{23}\\\
a_{31}&a_{32}&a_{33}\end{array}\\!\right]\\!\left[\begin{array}[]{ccc}d_{1}^{-\frac{1}{2}}&0&0\\\
0&d_{2}^{-\frac{1}{2}}&0\\\
0&0&d_{3}^{-\frac{1}{2}}\end{array}\right]\left[\begin{array}[]{c}x_{1}\\\
x_{2}\\\ x_{3}\end{array}\\!\right]W)$

where $d_{i}$ is a scalar, the degree of node $v_{i}$, $a_{ij}$ is a scalar,
the element of adjacency matrix $A$, $x_{i}\in\mathbb{R}^{1\times d}$ is the
representation of single node $v_{i}$, and
$x_{i}^{\prime}\in\mathbb{R}^{1\times d}$ is the updated representation of
node $v_{i}$, the output of this layer.

$\left[\begin{array}[]{c}x^{\prime}_{1}\\\ x^{\prime}_{2}\\\
x^{\prime}_{3}\end{array}\right]=\sigma(\left[\begin{array}[]{ccc}d_{1}^{-\frac{1}{2}}\\!&0&0\\\
0&d_{2}^{-\frac{1}{2}}&0\\\
0&0&d_{3}^{-\frac{1}{2}}\end{array}\right]\left[\begin{array}[]{ccc}a_{11}&a_{12}&a_{13}\\\
a_{21}&a_{22}&a_{23}\\\
a_{31}&a_{32}&a_{33}\end{array}\right]\left[\begin{array}[]{ccc}d_{1}^{-\frac{1}{2}}&0&0\\\
0&d_{2}^{-\frac{1}{2}}&0\\\ 0&0&d_{3}^{-\frac{1}{2}}\end{array}\right]XW)$

To reveal the updating of representation $x_{i}^{\prime}$ of node $v_{i}$, we
let $Z=D^{-{\frac{1}{2}}}AD^{-{\frac{1}{2}}}$. $Z$ is:

$Z=\left[\begin{array}[]{ccc}d_{1}^{-\frac{1}{2}}d_{1}^{-\frac{1}{2}}a_{11}&d_{1}^{-\frac{1}{2}}d_{2}^{-\frac{1}{2}}a_{12}&d_{1}^{-\frac{1}{2}}d_{3}^{-\frac{1}{2}}a_{13}\\\
d_{2}^{-\frac{1}{2}}d_{1}^{-\frac{1}{2}}a_{21}&d_{2}^{-\frac{1}{2}}d_{2}^{-\frac{1}{2}}a_{22}&d_{2}^{-\frac{1}{2}}d_{3}^{-\frac{1}{2}}a_{23}\\\
d_{1}^{-\frac{1}{2}}d_{3}^{-\frac{1}{2}}a_{31}&d_{3}^{-\frac{1}{2}}d_{2}^{-\frac{1}{2}}a_{32}&d_{3}^{-\frac{1}{2}}d_{3}^{-\frac{1}{2}}a_{33}\end{array}\right]$

We multiply Z with the representation matrix in vector format
$X=(x_{1}^{T},x_{2}^{T},x_{3}^{T})$:

$ZX=\left[\begin{array}[]{ccc}d_{1}^{-\frac{1}{2}}d_{1}^{-\frac{1}{2}}a_{11}&d_{1}^{-\frac{1}{2}}d_{2}^{-\frac{1}{2}}a_{12}&d_{1}^{-\frac{1}{2}}d_{3}^{-\frac{1}{2}}a_{13}\\\
d_{2}^{-\frac{1}{2}}d_{1}^{-\frac{1}{2}}a_{21}&d_{2}^{-\frac{1}{2}}d_{2}^{-\frac{1}{2}}a_{22}&d_{2}^{-\frac{1}{2}}d_{3}^{-\frac{1}{2}}a_{23}\\\
d_{1}^{-\frac{1}{2}}d_{3}^{-\frac{1}{2}}a_{31}&d_{3}^{-\frac{1}{2}}d_{2}^{-\frac{1}{2}}a_{32}&d_{3}^{-\frac{1}{2}}d_{3}^{-\frac{1}{2}}a_{33}\end{array}\right]\\!\left[\\!\begin{array}[]{c}x_{1}\\\
x_{2}\\\ x_{3}\end{array}\\!\right]$

$ZX=\left[\begin{array}[]{ccc}d_{1}^{-\frac{1}{2}}(d_{1}^{-\frac{1}{2}}a_{11}x_{1}+d_{2}^{-\frac{1}{2}}a_{12}x_{2}+d_{3}^{-\frac{1}{2}}a_{13}x_{3})\\\
d_{2}^{-\frac{1}{2}}(d_{1}^{-\frac{1}{2}}a_{21}x_{1}+d_{2}^{-\frac{1}{2}}a_{22}x_{2}+d_{3}^{-\frac{1}{2}}a_{23}x_{3})\\\
d_{3}^{-\frac{1}{2}}(d_{1}^{-\frac{1}{2}}a_{31}x_{1}+d_{2}^{-\frac{1}{2}}a_{32}x_{2}+d_{3}^{-\frac{1}{2}}a_{33}x_{3})\end{array}\right]$

As $X^{\prime}=\sigma(ZXW)$, finally, the node updating of nodes $v_{i}$ is:

$\left[\\!\begin{array}[]{c}x^{\prime}_{1}\\\ x^{\prime}_{2}\\\
x^{\prime}_{3}\end{array}\\!\right]=\sigma(\left[\begin{array}[]{ccc}d_{1}^{-\frac{1}{2}}(d_{1}^{-\frac{1}{2}}a_{11}x_{1}+d_{2}^{-\frac{1}{2}}a_{12}x_{2}+d_{3}^{-\frac{1}{2}}a_{13}x_{3})\\\
d_{2}^{-\frac{1}{2}}(d_{1}^{-\frac{1}{2}}a_{21}x_{1}+d_{2}^{-\frac{1}{2}}a_{22}x_{2}+d_{3}^{-\frac{1}{2}}a_{23}x_{3})\\\
d_{3}^{-\frac{1}{2}}(d_{1}^{-\frac{1}{2}}a_{31}x_{1}+d_{2}^{-\frac{1}{2}}a_{32}x_{2}+d_{3}^{-\frac{1}{2}}a_{33}x_{3}\end{array}\right]W)$

Taking $x_{1}^{\prime}$ as an example, the updating process is:

$x_{1}^{\prime}=\sigma(d_{1}^{-\frac{1}{2}}(d_{1}^{-\frac{1}{2}}a_{11}x_{1}+d_{2}^{-\frac{1}{2}}a_{12}x_{2}+d_{3}^{-\frac{1}{2}}a_{13}x_{3})W)$

This equation demonstrates an equivalent spatial manner that every node takes
its 1-hop neighbour in spatial graph and aggregates the messages to updates
its own representation. Thus, in the aspect of spectral domain, we can
formulate the GCN process on one node as:

$x_{i}^{\prime}=\sigma(\frac{1}{\sqrt{d_{i}}}(\frac{1}{\sqrt{d_{i}}}x_{i}+\sum_{j\in\mathcal{N}_{i}}\frac{1}{\sqrt{d_{j}}}x_{j})W)$
(17)

where $\mathcal{N}_{i}$ is the index set of neighbourhood of node $v_{i}$.

## References

  * [1] L. Cowen, T. Ideker, B. J. Raphael, and R. Sharan, “Network propagation: a universal amplifier of genetic associations,” _Nat Rev Genet_ , vol. 18, no. 9, pp. 551–562, 09 2017.
  * [2] S. M. Marinka Zitnik, Rok Sosič and J. Leskovec, “BioSNAP Datasets: Stanford biomedical network dataset collection,” http://snap.stanford.edu/biodata, Aug. 2018.
  * [3] M. Zitnik, M. Agrawal, and J. Leskovec, “Modeling polypharmacy side effects with graph convolutional networks,” _Bioinformatics_ , vol. 34, no. 13, pp. i457–i466, 07 2018.
  * [4] Y. Luo, X. Zhao, J. Zhou, J. Yang, Y. Zhang, W. Kuang, J. Peng, L. Chen, and J. Zeng, “A network integration approach for drug-target interaction prediction and computational drug repositioning from heterogeneous information,” _Nat Commun_ , vol. 8, no. 1, p. 573, 09 2017.
  * [5] M. Agrawal, M. Zitnik, and J. Leskovec, “Large-scale analysis of disease pathways in the human interactome,” _Pac Symp Biocomput_ , vol. 23, pp. 111–122, 2018.
  * [6] K. Luck, D. K. Kim, L. Lambourne, K. Spirohn, B. E. Begg, W. Bian, R. Brignall, T. Cafarelli, F. J. Campos-Laborie, B. Charloteaux, D. Choi, A. G. Coté, M. Daley, S. Deimling, A. Desbuleux, A. Dricot, M. Gebbia, M. F. Hardy, N. Kishore, J. J. Knapp, I. A. Kovács, I. Lemmens, M. W. Mee, J. C. Mellor, C. Pollis, C. Pons, A. D. Richardson, S. Schlabach, B. Teeking, A. Yadav, M. Babor, D. Balcha, O. Basha, C. Bowman-Colin, S. F. Chin, S. G. Choi, C. Colabella, G. Coppin, C. D’Amata, D. De Ridder, S. De Rouck, M. Duran-Frigola, H. Ennajdaoui, F. Goebels, L. Goehring, A. Gopal, G. Haddad, E. Hatchi, M. Helmy, Y. Jacob, Y. Kassa, S. Landini, R. Li, N. van Lieshout, A. MacWilliams, D. Markey, J. N. Paulson, S. Rangarajan, J. Rasla, A. Rayhan, T. Rolland, A. San-Miguel, Y. Shen, D. Sheykhkarimli, G. M. Sheynkman, E. Simonovsky, M. Taşan, A. Tejeda, V. Tropepe, J. C. Twizere, Y. Wang, R. J. Weatheritt, J. Weile, Y. Xia, X. Yang, E. Yeger-Lotem, Q. Zhong, P. Aloy, G. D. Bader, J. De Las Rivas, S. Gaudet, T. Hao, J. Rak, J. Tavernier, D. E. Hill, M. Vidal, F. P. Roth, and M. A. Calderwood, “A reference map of the human binary protein interactome,” _Nature_ , vol. 580, no. 7803, pp. 402–408, 04 2020.
  * [7] Y. Jin, W. Zhang, X. He, X. Wang, and X. Wang, “Syndrome-aware herb recommendation with multi-graph convolution network,” in _ICDE_. IEEE, 2020, pp. 145–156.
  * [8] C. Gao, Y. Zheng, N. Li, Y. Li, Y. Qin, J. Piao, Y. Quan, J. Chang, D. Jin, X. He, and Y. Li, “A survey of graph neural networks for recommender systems: Challenges, methods, and directions,” _ACM Transactions on Recommender Systems (TORS)_ , 2021.
  * [9] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chemistry,” _CoRR_ , vol. abs/1704.01212, 2017\. [Online]. Available: http://arxiv.org/abs/1704.01212
  * [10] C. Park, D. Kim, J. Han, and H. Yu, “Unsupervised attributed multiplex network embedding,” in _AAAI_ , vol. 34, no. 04, 2020, pp. 5371–5378.
  * [11] Y. Ren, B. Liu, C. Huang, P. Dai, L. Bo, and J. Zhang, “Heterogeneous deep graph infomax,” _CoRR_ , vol. abs/1911.08538, 2019. [Online]. Available: http://arxiv.org/abs/1911.08538
  * [12] P. Velickovic, W. Fedus, W. L. Hamilton, P. Liò, Y. Bengio, and R. D. Hjelm, “Deep graph infomax.” in _ICLR (Poster)_ , 2019.
  * [13] J. Qiu, J. Tang, H. Ma, Y. Dong, K. Wang, and J. Tang, “Deepinf: Social influence prediction with deep learning,” in _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery; Data Mining_ , ser. KDD ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 2110–2119. [Online]. Available: https://doi.org/10.1145/3219819.3220077
  * [14] H. Stärk, O. Ganea, L. Pattanaik, R. Barzilay, and T. Jaakkola, “Equibind: Geometric deep learning for drug binding structure prediction,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 20 503–20 521.
  * [15] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _5th ICLR_ , 2017.
  * [16] X. Yue, Z. Wang, J. Huang, S. Parthasarathy, S. Moosavinasab, Y. Huang, S. M. Lin, W. Zhang, P. Zhang, and H. Sun, “Graph embedding on biomedical networks: methods, applications and evaluations,” _Bioinformatics_ , vol. 36, no. 4, pp. 1241–1251, 02 2020.
  * [17] K. Huang, C. Xiao, L. Glass, M. Zitnik, and J. Sun, “Skipgnn: Predicting molecular interactions with skip-graph networks,” _arXiv preprint arXiv:2004.14949_ , 2020.
  * [18] K. Kc, R. Li, F. Cui, and A. Haake, “Predicting biomedical interactions with higher-order graph convolutional networks,” _IEEE/ACM Transactions on Computational Biology and Bioinformatics_ , pp. 1–1, 2021.
  * [19] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” _arXiv preprint arXiv:1512.03385_ , 2015.
  * [20] I. A. Kovács, K. Luck, K. Spirohn, Y. Wang, C. Pollis, S. Schlabach, W. Bian, D.-K. Kim, N. Kishore, T. Hao, M. A. Calderwood, M. Vidal, and A.-L. Barabási, “Network-based prediction of protein interactions,” _Nature Communications_ , vol. 10, no. 1, p. 1240, Mar 2019. [Online]. Available: https://doi.org/10.1038/s41467-019-09177-y
  * [21] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , ser. KDD ’14. New York, NY, USA: ACM, 2014, pp. 701–710. [Online]. Available: http://doi.acm.org/10.1145/2623330.2623732
  * [22] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2016.
  * [23] D. Figueiredo, L. Ribeiro, and P. Saverese, “struc2vec: Learning node representations from structural identity,” 04 2017.
  * [24] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding.” in _WWW_. ACM, 2015.
  * [25] A. L. Barabasi and R. Albert, “Emergence of scaling in random networks,” _Science_ , vol. 286, no. 5439, pp. 509–512, Oct 1999.
  * [26] L. Lü, C. H. Jin, and T. Zhou, “Similarity index based on local paths for link prediction of complex networks,” _Phys Rev E Stat Nonlin Soft Matter Phys_ , vol. 80, no. 4 Pt 2, p. 046122, Oct 2009.
  * [27] C. Shi, Y. Li, J. Zhang, Y. Sun, and S. Y. Philip, “A survey of heterogeneous information network analysis,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 29, no. 1, pp. 17–37, 2016.
  * [28] Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli, “Graph matching networks for learning the similarity of graph structured objects,” _CoRR_ , vol. abs/1904.12787, 2019. [Online]. Available: http://arxiv.org/abs/1904.12787
  * [29] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , ser. NIPS’16. Red Hook, NY, USA: Curran Associates Inc., 2016, p. 3844–3852.
  * [30] J. Bruna, W. Zaremba, A. Szlam, and Y. Lecun, “Spectral networks and locally connected networks on graphs,” in _International Conference on Learning Representations (ICLR2014), CBLS, April 2014_ , 2014.
  * [31] T. N. Kipf and M. Welling, “Variational graph auto-encoders,” _NIPS Workshop on Bayesian Deep Learning_ , 2016.
  * [32] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” _arXiv preprint arXiv:1710.10903_ , 2017.
  * [33] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” _CoRR_ , vol. abs/1810.00826, 2018. [Online]. Available: http://arxiv.org/abs/1810.00826
  * [34] K. Xu, C. Li, Y. Tian, T. Sonobe, K. Kawarabayashi, and S. Jegelka, “Representation learning on graphs with jumping knowledge networks,” _CoRR_ , vol. abs/1806.03536, 2018. [Online]. Available: http://arxiv.org/abs/1806.03536
  * [35] S. Abu-El-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan, G. Ver Steeg, and A. Galstyan, “Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing,” in _international conference on machine learning_. PMLR, 2019, pp. 21–29.
  * [36] L. Tang and H. Liu, “Leveraging social media networks for classification,” _Data Min. Knowl. Discov._ , vol. 23, pp. 447–478, 11 2011.