[1.5em]1.5em1em

# Incorporating Chinese Characters of Words
for Lexical Sememe Prediction

Huiming Jin1 †, Hao Zhu2 , Zhiyuan Liu2,3 , Ruobing Xie4, Maosong Sun2,3, Fen
Lin4, Leyu Lin4
1 Shenyuan Honors College, Beihang University, Beijing, China
2 Beijing National Research Center for Information Science and Technology,
State Key Laboratory of Intelligent Technology and Systems,
Department of Computer Science and Technology, Tsinghua University, Beijing,
China
3Jiangsu Collaborative Innovation Center for Language Ability,
Jiangsu Normal University, Xuzhou 221009 China
4 Search Product Center, WeChat Search Application Department, Tencent, China
Work done while doing internship at Tsinghua University.Equal contribution.
Huiming Jin proposed the overall idea, designed the first experiment,
conducted both experiments, and
wrote the paper; Hao Zhu made suggestions on ensembling, proposed the second
experiment, and spent a lot of time on
proofreading the paper and making revisions. All authors helped shape the
research, analysis and manuscript.Corresponding author: Z. Liu
<EMAIL_ADDRESS>
###### Abstract

Sememes are minimum semantic units of concepts in human languages, such that
each word sense is composed of one or multiple sememes. Words are usually
manually annotated with their sememes by linguists, and form linguistic
common-sense knowledge bases widely used in various NLP tasks. Recently, the
lexical sememe prediction task has been introduced. It consists of
automatically recommending sememes for words, which is expected to improve
annotation efficiency and consistency. However, existing methods of lexical
sememe prediction typically rely on the external context of words to represent
the meaning, which usually fails to deal with low-frequency and out-of-
vocabulary words. To address this issue for Chinese, we propose a novel
framework to take advantage of both internal character information and
external context information of words. We experiment on HowNet, a Chinese
sememe knowledge base, and demonstrate that our framework outperforms state-
of-the-art baselines by a large margin, and maintains a robust performance
even for low-frequency words. iiiCode is available at
https://github.com/thunlp/Character-enhanced-Sememe-Prediction

##  1 Introduction

A sememe is an indivisible semantic unit for human languages defined by
linguists Bloomfield (1926). The semantic meanings of concepts (e.g., words)
can be composed by a finite number of sememes. However, the sememe set of a
word is not explicit, which is why linguists build knowledge bases (KBs) to
annotate words with sememes manually.

Figure 1: Sememes of the word “铁匠” (ironsmith) in HowNet, where _occupation_ ,
_human_ and _industrial_ can be inferred by both external (contexts) and
internal (characters) information, while _metal_ is well-captured only by the
internal information within the character “ 铁” (iron).

HowNet is a classical widely-used sememe KB Dong and Dong (2006). In HowNet,
linguists manually define approximately $2,000$ sememes, and annotate more
than $100,000$ common words in Chinese and English with their relevant sememes
in hierarchical structures. HowNet is well developed and has a wide range of
applications in many NLP tasks, such as word sense disambiguation Duan et al.
(2007), sentiment analysis Fu et al. (2013); Huang et al. (2014) and cross-
lingual word similarity Xia et al. (2011).

Since new words and phrases are emerging every day and the semantic meanings
of existing concepts keep changing, it is time-consuming and work-intensive
for human experts to annotate new

concepts and maintain consistency for large-scale sememe KBs. To address this
issue, Xie et al. (2017) propose an automatic sememe prediction framework to
assist linguist annotation. They assumed that words which have similar
semantic meanings are likely to share similar sememes. Thus, they propose to
represent word meanings as embeddings Pennington et al. (2014); Mikolov et al.
(2013) learned from a large-scale text corpus, and they adopt collaborative
filtering Sarwar et al. (2001) and matrix factorization Koren et al. (2009)
for sememe prediction, which are concluded as Sememe Prediction with Word
Embeddings (SPWE) and Sememe Prediction with Sememe Embeddings (SPSE)
respectively. However, those methods ignore the internal information within
words (e.g., the characters in Chinese words), which is also significant for
word understanding, especially for words which are of low-frequency or do not
appear in the corpus at all. In this paper, we take Chinese as an example and
explore methods of taking full advantage of both external and internal
information of words for sememe prediction.

In Chinese, words are composed of one or multiple characters, and most
characters have corresponding semantic meanings. As shown by Yin (1984), more
than $90\%$ of Chinese characters in modern Chinese corpora are morphemes.
Chinese words can be divided into single-morpheme words and compound words,
where compound words account for a dominant proportion. The meanings of
compound words are closely related to their internal characters as shown in
Fig. 1. Taking a compound word “铁匠” (ironsmith) for instance, it consists of
two Chinese characters: “铁” (iron) and “匠” (craftsman), and the semantic
meaning of “铁匠” can be inferred from the combination of its two characters
(iron \+ craftsman $\,\to\,$ ironsmith). Even for some single-morpheme words,
their semantic meanings may also be deduced from their characters. For
example, both characters of the single-morpheme word “徘徊” (hover) represent
the meaning of “hover” or “linger”. Therefore, it is intuitive to take the
internal character information into consideration for sememe prediction.

In this paper, we propose a novel framework for Character-enhanced Sememe
Prediction (CSP), which leverages both internal character information and
external context for sememe prediction. CSP predicts the sememe candidates for
a target word from its word embedding and the corresponding character
embeddings. Specifically, we follow SPWE and SPSE as introduced by Xie et al.
(2017) to model external information and propose Sememe Prediction with Word-
to-Character Filtering (SPWCF) and Sememe Prediction with Character and Sememe
Embeddings (SPCSE) to model internal character information. In our
experiments, we evaluate our models on the task of sememe prediction using
HowNet. The results show that CSP achieves state-of-the-art performance and
stays robust for low-frequency words.

To summarize, the key contributions of this work are as follows: (1) To the
best of our knowledge, this work is the first to consider the internal
information of characters for sememe prediction. (2) We propose a sememe
prediction framework considering both external and internal information, and
show the effectiveness and robustness of our models on a real-world dataset.

##  2 Related Work

##### Knowledge Bases.

Knowledge Bases (KBs), aiming to organize human knowledge in structural forms,
are playing an increasingly important role as infrastructural facilities of
artificial intelligence and natural language processing. KBs rely on manual
efforts Bollacker et al. (2008), automatic extraction Auer et al. (2007),
manual evaluation Suchanek et al. (2007), automatic completion and alignment
Bordes et al. (2013); Toutanova et al. (2015); Zhu et al. (2017) to build,
verify and enrich their contents. WordNet Miller (1995) and BabelNet Navigli
and Ponzetto (2012) are the representative of linguist KBs, where words of
similar meanings are grouped to form thesaurus Nastase and Szpakowicz (2001).
Apart from other linguistic KBs, sememe KBs such as HowNet Dong and Dong
(2006) can play a significant role in understanding the semantic meanings of
concepts in human languages and are favorable for various NLP tasks:
information structure annotation Gan and Wong (2000), word sense
disambiguation Gan et al. (2002), word representation learning Niu et al.
(2017); Faruqui et al. (2015), and sentiment analysis Fu et al. (2013) inter
alia. Hence, lexical sememe prediction is an important task to construct
sememe KBs.

##### Automatic Sememe Prediction.

Automatic sememe prediction is proposed by Xie et al. (2017). For this task,
they propose SPWE and SPSE, which are inspired by collaborative filtering
Sarwar et al. (2001) and matrix factorization Koren et al. (2009)
respectively. SPWE recommends the sememes of those words that are close to the
unlabelled word in the embedding space. SPSE learns sememe embeddings by
matrix factorization Koren et al. (2009) within the same embedding space of
words, and it then recommends the most relevant sememes to the unlabelled word
in the embedding space. In these methods, word embeddings are learned based on
external context information Pennington et al. (2014); Mikolov et al. (2013)
on large-scale text corpus. These methods do not exploit internal information
of words, and fail to handle low-frequency words and out-of-vocabulary words.
In this paper, we propose to incorporate internal information for lexical
sememe prediction.

##### Subword and Character Level NLP.

Subword and character level NLP models the internal information of words,
which is especially useful to address the out-of-vocabulary (OOV) problem.
Morphology is a typical research area of subword level NLP. Subword level NLP
has also been widely considered in many NLP applications, such as keyword
spotting Narasimhan et al. (2014), parsing Seeker and Çetinoğlu (2015),
machine translation Dyer et al. (2010), speech recognition Creutz et al.
(2007), and paradigm completion Sutskever et al. (2014); Bahdanau et al.
(2015); Cotterell et al. (2016a); Kann et al. (2017); Jin and Kann (2017).
Incorporating subword information for word embeddings Bojanowski et al.
(2017); Cotterell et al. (2016b); Chen et al. (2015); Wieting et al. (2016);
Yin et al. (2016) facilitates modeling rare words and can improve the
performance of several NLP tasks to which the embeddings are applied. Besides,
people also consider character embeddings which have been utilized in Chinese
word segmentation Sun et al. (2014).

The success of previous work verifies the feasibility of utilizing internal
character information of words. We design our framework for lexical sememe
prediction inspired by these methods.

##  3 Background and Notation

In this section, we first introduce the organization of sememes, senses and
words in HowNet. Then we offer a formal definition of lexical sememe
prediction and develop our notation.

###  3.1 Sememes, Senses and Words in HowNet

HowNet provides sememe annotations for Chinese words, where each word is
represented as a hierarchical tree-like sememe structure. Specifically, a word
in HowNet may have various senses, which respectively represent the semantic
meanings of the word in the real world. Each sense is defined as a
hierarchical structure of sememes. For instance, as shown in the right part of
Fig. 1, the word “铁匠” (ironsmith) has one sense, namely ironsmith. The sense
ironsmith is defined by the sememe “人” (human) which is modified by sememe
“职位” (occupation), “金属” (metal) and “工” (industrial). In HowNet, linguists use
about $2,000$ sememes to describe more than $100,000$ words and phrases in
Chinese with various combinations and hierarchical structures.

###  3.2 Formalization of the Task

In this paper, we focus on the relationships between the words and the
sememes. Following the settings of Xie et al. (2017), we simply ignore the
senses and the hierarchical structure of sememes, and we regard the sememes of
all senses of a word together as the sememe set of the word.

We now introduce the notation used in this paper. Let $G=(W,S,T)$ denotes the
sememe KB, where $W=\\{w_{1},w_{2},\dots,w_{|W|}\\}$ is the set of words, $S$
is the set of sememes, and $T\subseteq W\times S$ is the set of relation pairs
between words and sememes. We denote the Chinese character set as $C$, with
each word $w_{i}\in C^{+}$. Each word $w$ has its sememe set
$S_{w}=\\{s|(w,s)\in T\\}$. Take the word “铁匠” (ironsmith) for example, the
sememe set $S_{\text{\it 铁匠\ (ironsmith)}}$ consists of “人” (human), “职位”
(occupation), “金属” (metal) and “工” (industrial).

Given a word $w\in C^{+}$, the task of lexical sememe prediction aims to
predict the corresponding $P(s|w)$ of sememes in $S$ to recommend them to $w$.

##  4 Methodology

In this section, we present our framework for lexical sememe prediction (SP).
For each unlabelled word, our framework aims to recommend the most appropriate
sememes based on the internal and external information. Because of introducing
character information, our framework can work for both high-frequency and low-
frequency words.

Our framework is the ensemble of two parts: sememe prediction with internal
information (i.e., internal models), and sememe prediction with external
information (i.e., external models). Explicitly, we adopt SPWE, SPSE, and
their ensemble Xie et al. (2017) as external models, and we take SPWCF, SPCSE,
and their ensemble as internal models.

In the following sections, we first introduce SPWE and SPSE. Then, we show the
details of SPWCF and SPCSE. Finally, we present the method of model
ensembling.

###  4.1 SP with External Information

SPWE and SPSE are introduced by Xie et al. (2017) as the state of the art for
sememe prediction. These methods represent word meanings with embeddings
learned from external information, and apply the ideas of collaborative
filtering and matrix factorization in recommendation systems for sememe
predication.

SP with Word Embeddings (SPWE) is based on the assumption that similar words
should have similar sememes. In SPWE, the similarity of words are measured by
cosine similarity. The score function $P(s_{j}|w)$ of sememe $s_{j}$ given a
word $w$ is defined as:

$P(s_{j}|w)\sim\sum_{w_{i}\in
W}\cos(\mathbf{w},\mathbf{w_{i}})\cdot\mathbf{M}_{ij}\cdot c^{r_{i}},$ (1)

where $\mathbf{w}$ and $\mathbf{w_{i}}$ are pre-trained word embeddings of
words $w$ and $w_{i}$. $\mathbf{M}_{ij}\in{\\{0,1\\}}$ indicates the
annotation of sememe $s_{j}$ on word $w_{i}$, where $\mathbf{M}_{ij}=1$
indicates the word $s_{j}\in S_{w_{i}}$ and otherwise is not. $r_{i}$ is the
descend cosine word similarity rank between $w$ and $w_{i}$, and $c\in(0,1)$
is a hyper-parameter.

SP with Sememe Embeddings (SPSE) aims to map sememes into the same low-
dimensional space of the word embeddings to predict the semantic correlations
of the sememes and the words. This method learns two embeddings $\mathbf{s}$
and $\mathbf{\bar{s}}$ for each sememe by solving matrix factorization with
the loss function defined as:

$\begin{split}\mathcal{L}&=\sum_{w_{i}\in W,s_{j}\in
S}\left(\mathbf{w}_{i}\cdot\left(\mathbf{s}_{j}+\mathbf{\bar{s}}_{j}\right)+\mathbf{b}_{i}+\mathbf{b}_{j}^{\prime}-\mathbf{M}_{ij}\right)^{2}\\\
&+\lambda\sum_{s_{j},s_{k}\in
S}\left(\mathbf{s}_{j}\cdot\mathbf{\bar{s}}_{k}-\mathbf{C}_{jk}\right)^{2},\end{split}$
(2)

where $\mathbf{M}$ is the same matrix used in SPWE. $\mathbf{C}$ indicates the
correlations between sememes, in which $\mathbf{C}_{jk}$ is defined as the
point-wise mutual information $\text{PMI}(s_{j},s_{k})$. The sememe embeddings
are learned by factorizing the word-sememe matrix $\mathbf{M}$ and the sememe-
sememe matrix $\mathbf{C}$ synchronously with fixed word embeddings.
$\mathbf{b}_{i}$ and $\mathbf{b}_{j}^{\prime}$ denote the bias of $w_{i}$ and
$s_{j}$, and $\lambda$ is a hyper-parameter. Finally, the score of sememe
$s_{j}$ given a word $w$ is defined as:

$P(s_{j}|w)\sim\mathbf{w}\cdot\left(\mathbf{s}_{j}+\mathbf{\bar{s}}_{j}\right).$
(3)

###  4.2 SP with Internal Information

We design two methods for sememe prediction with only internal character
information without considering contexts as well as pre-trained word
embeddings.

####  4.2.1 SP with Word-to-Character Filtering (SPWCF)

Inspired by collaborative filtering Sarwar et al. (2001), we propose to
recommend sememes for an unlabelled word according to its similar words based
on internal information. Instead of using pre-trained word embeddings, we
consider words as similar if they contain the same characters at the same
positions.

In Chinese, the meaning of a character may vary according to its position
within a word Chen et al. (2015). We consider three positions within a word:
Begin, Middle, and End. For example, as shown in Fig. 2, the character at the
Begin position of the word “火车站” (railway station) is “火” (fire), while “车”
(vehicle) and “站” (station) are at the Middle and End position respectively.
The character “站” usually means station when it is at the End position, while
it usually means stand at the Begin position like in “站立” (stand), “站岗哨兵”
(standing guard) and “站起来” (stand up).

Figure 2: An example of the position of characters in a word.

Formally, for a word $w=c_{1}c_{2}...c_{|w|}$, we define
$\pi_{B}(w)=\\{c_{1}\\}$, $\pi_{M}(w)=\\{c_{2},...,c_{|w-1|}\\}$,
$\pi_{E}(w)=\\{c_{|w|}\\}$, and

$P_{p}(s_{j}|c)\sim\frac{\sum_{w_{i}\in W\land
c\in\pi_{p}(w_{i})}\mathbf{M}_{ij}}{\sum_{w_{i}\in W\land
c\in\pi_{p}(w_{i})}|S_{w_{i}}|},$ (4)

that represents the score of a sememe $s_{j}$ given a character $c$ and a
position $p$, where $\pi_{p}$ may be $\pi_{B}$, $\pi_{M}$, or $\pi_{E}$.
$\mathbf{M}$ is the same matrix used in Eq. (1). Finally, we define the score
function $P(s_{j}|w)$ of sememe $s_{j}$ given a word $w$ as:

$P(s_{j}|w)\sim\sum_{p\in\\{B,M,E\\}}\sum_{c\in\pi_{p}(w)}P_{p}(s_{j}|c).$ (5)

SPWCF is a simple and efficient method. It performs well because compositional
semantics are pervasive in Chinese compound words, which makes it
straightforward and effective to find similar words according to common
characters.

####  4.2.2 SP with Character and Sememe Embeddings (SPCSE)

The method Sememe Prediction with Word-to-Character Filtering (SPWCF) can
effectively recommend the sememes that have strong correlations with
characters. However, just like SPWE, it ignores the relations between sememes.
Hence, inspired by SPSE, we propose Sememe Prediction with Character and
Sememe Embeddings (SPCSE) to take the relations between sememes into account.
In SPCSE, we instead learn the sememe embeddings based on internal character
information, then compute the semantic distance between sememes and words for
prediction.

Inspired by GloVe Pennington et al. (2014) and SPSE, we adopt matrix
factorization in SPCSE, by decomposing the word-sememe matrix and the sememe-
sememe matrix simultaneously. Instead of using pre-trained word embeddings in
SPSE, we use pre-trained character embeddings in SPCSE. Since the ambiguity of
characters is stronger than that of words, multiple embeddings are learned for
each character Chen et al. (2015). We select the most representative character
and its embedding to represent the word meaning. Because low-frequency
characters are much rare than those low-frequency words, and even low-
frequency words are usually composed of common characters, it is feasible to
use pre-trained character embeddings to represent rare words. During
factorizing the word-sememe matrix, the character embeddings are fixed.

Figure 3: An example of adopting multiple-prototype character embeddings. The
numbers are the cosine distances. The sememe “金属” (metal) is the closest to
one embedding of “铁” (iron).

We set $N_{e}$ as the number of embeddings for each character, and each
character $c$ has $N_{e}$ embeddings $\mathbf{c}^{1},...,\mathbf{c}^{N_{e}}$.
Given a word $w$ and a sememe $s$, we select the embedding of a character of
$w$ closest to the sememe embedding by cosine distance as the representation
of the word $w$, as shown in Fig. 3. Specifically, given a word
$w=c_{1}...c_{|w|}$ and a sememe $s_{j}$, we define

$\hat{k},\hat{r}=\arg\min_{k,r}\left[1-\cos(\mathbf{c}_{k}^{r},(\mathbf{s}^{\prime}_{j}+\mathbf{\bar{s}}_{j}^{\prime}))\right],$
(6)

where $\hat{k}$ and $\hat{r}$ indicate the indices of the character and its
embedding closest to the sememe $s_{j}$ in the semantic space. With the same
word-sememe matrix $\mathbf{M}$ and sememe-sememe correlation matrix
$\mathbf{C}$ in Eq. (2), we learn the sememe embeddings with the loss
function:

$\begin{split}\mathcal{L}&=\sum_{w_{i}\in W,s_{j}\in
S}\left(\mathbf{c}_{\hat{k}}^{\hat{r}}\cdot\left(\mathbf{s}_{j}^{\prime}+\mathbf{\bar{s}}_{j}^{\prime}\right)+\mathbf{b}_{\hat{k}}^{c}+\mathbf{b}_{j}^{\prime\prime}-\mathbf{M}_{ij}\right)^{2}\\\
&+\lambda^{\prime}\sum_{s_{j},s_{q}\in
S}\left(\mathbf{s}_{j}^{\prime}\cdot\mathbf{\bar{s}}_{q}^{\prime}-\mathbf{C}_{jq}\right)^{2},\end{split}$
(7)

where $\mathbf{s}_{j}^{\prime}$ and $\mathbf{\bar{s}}_{j}^{\prime}$ are the
sememe embeddings for sememe $s_{j}$, and $\mathbf{c}_{\hat{k}}^{\hat{r}}$ is
the embedding of the character that is the closest to sememe $s_{j}$ within
$w_{i}$. Note that, as the characters and the words are not embedded into the
same semantic space, we learn new sememe embeddings instead of using those
learned in SPSE, hence we use different notations for the sake of distinction.
$\mathbf{b}_{k}^{c}$ and $\mathbf{b}_{j}^{\prime\prime}$ denote the biases of
$c_{k}$ and $s_{j}$, and $\lambda^{\prime}$ is the hyper-parameter adjusting
the two parts. Finally, the score function of word $w=c_{1}...c_{|w|}$ is
defined as:

$\begin{split}P(s_{j}|w)\sim\mathbf{c}_{\hat{k}}^{\hat{r}}\cdot\left(\mathbf{s}_{j}^{\prime}+\mathbf{\bar{s}}_{j}^{\prime}\right).\end{split}$
(8)

###  4.3 Model Ensembling

SPWCF / SPCSE and SPWE / SPSE take different sources of information as input,
which means that they have different characteristics: SPWCF / SPCSE only have
access to internal information, while SPWE / SPSE can only make use of
external information. On the other hand, just like the difference between SPWE
and SPSE, SPWCF originates from collaborative filtering, whereas SPCSE uses
matrix factorization. All of those methods have in common that they tend to
recommend the sememes of similar words, but they diverge in their
interpretation of similar.

Figure 4: The illustration of model ensembling.

Hence, to obtain better prediction performance, it is necessary to combine
these models. We denote the ensemble of SPWCF and SPCSE as the internal model,
and we denote the ensemble of SPWE and SPSE as the external model. The
ensemble of the internal and the external models is our novel framework CSP.
In practice, for words with reliable word embeddings, i.e., high-frequency
words, we can use the integration of the internal and the external models; for
words with extremely low frequencies (e.g., having no reliable word
embeddings), we can just use the internal model and ignore the external model,
because the external information is noise in this case. Fig. 4 shows model
ensembling in different scenarios. For the sake of comparison, we use the
integration of SPWCF, SPCSE, SPWE, and SPSE as CSP in our all experiments. In
this paper, two models are integrated by simple weighted addition.

##  5 Experiments

In this section, we evaluate our models on the task of sememe prediction.
Additionally, we analyze the performance of different methods for various word
frequencies. We also execute an elaborate case study to demonstrate the
mechanism of our methods and the advantages of using internal information.

###  5.1 Dataset

We use the human-annotated sememe KB HowNet for sememe prediction. In HowNet,
$103,843$ words are annotated with $212,539$ senses, and each sense is defined
as a hierarchical structure of sememes. There are about $2,000$ sememes in
HowNet. However, the frequencies of some sememes in HowNet are very low, such
that we consider them unimportant and remove them. Our final dataset contains
$1,400$ sememes. For learning the word and character embeddings, we use the
Sogou-T corpusiiiiiiSogou-T corpus is provided by Sogou Inc., a Chinese
commercial search engine company. https://www.sogou.com/labs/resource/t.php
Liu et al. (2012), which contains $2.7$ billion words.

###  5.2 Experimental Settings

In our experiments, we evaluate SPWCF, SPCSE, and SPWCF + SPCSE which only use
internal information, and the ensemble framework CSP which uses both internal
and external information for sememe prediction. We use the state-of-the-art
models from Xie et al. (2017) as our baselines. Additionally, we use the SPWE
model with word embeddings learned by fastText Bojanowski et al. (2017) that
considers both internal and external information as a baseline.

For the convenience of comparison, we select $60,000$ high-frequency words in
Sogou-T corpus from HowNet. We divide the $60,000$ words into train, dev, and
test sets of size $48,000$, $6,000$, and $6,000$, respectively, and we keep
them fixed throughout all experiments except for Section 5.4. In Section 5.4,
we utilize the same train and dev sets, but use other words from HowNet as the
test set to analyze the performance of our methods for different word
frequency scenarios. We select the hyper-parameters on the dev set for all
models including the baselines and report the evaluation results on the test
set.

We set the dimensions of the word, sememe, and character embeddings to be
$200$. The word embeddings are learned by GloVe Pennington et al. (2014). For
the baselines, in SPWE, the hyper-parameter $c$ is set to $0.8$, and the model
considers no more than $K=100$ nearest words. We set the probability of
decomposing zero elements in the word-sememe matrix in SPSE to be $0.5\%$.
$\lambda$ in Eq. (2) is $0.5$. The model is trained for $20$ epochs, and the
initial learning rate is $0.01$, which decreases through iterations. For
fastText, we use skip-gram with hierarchical softmax to learn word embeddings,
and we set the minimum length of character n-grams to be 1 and the maximum
length of character n-grams to be 2. For model ensembling, we use
$\frac{\lambda_{\text{\it SPWE}}}{\lambda_{\text{\it SPSE}}}=2.1$ as the
addition weight.

For SPCSE, we use Cluster-based Character Embeddings Chen et al. (2015) to
learn pre-trained character embeddings, and we set $N_{e}$ to be $3$. We set
$\lambda^{\prime}$ in Eq. (7) to be $0.1$, and the model is trained for $20$
epochs. The initial learning rate is $0.01$ and decreases during training as
well. Since generally each character can relate to about $15$ \- $20$ sememes,
we set the probability of decomposing zero elements in the word-sememe matrix
in SPCSE to be $2.5\%$. The ensemble weight of SPWCF and SPCSE
$\frac{\lambda_{\text{\it SPWCF}}}{\lambda_{\text{\it SPCSE}}}=4.0$. For
better performance of the final ensemble model CSP, we set $\lambda=0.1$ and
$\frac{\lambda_{\text{\it SPWE}}}{\lambda_{\text{\it SPSE}}}=0.3125$, though
$0.5$ and $2.1$ are the best for SPSE and SPWE + SPSE. Finally, we choose
$\frac{\lambda_{\text{\it internal}}}{\lambda_{\text{\it external}}}=1.0$ to
integrate the internal and external models.

###  5.3 Sememe Prediction

####  5.3.1 Evaluation Protocol

The task of sememe prediction aims to recommend appropriate sememes for
unlabelled words. We cast this as a multi-label classification task, and adopt
mean average precision (MAP) as the evaluation metric. For each unlabelled
word in the test set, we rank all sememe candidates with the scores given by
our models as well as baselines, and we report the MAP results. The results
are reported on the test set, and the hyper-parameters are tuned on the dev
set.

####  5.3.2 Experiment Results

The evaluation results are shown in Table 1. We can observe that:

| Method |  | MAP |
---|---|---|---|---
| SPSE |  | 0.411 |
| SPWE |  | 0.565 |
| SPWE+SPSE |  | 0.577 |
| SPWCF |  | 0.467 |
| SPCSE |  | 0.331 |
| SPWCF + SPCSE |  | 0.483 |
| SPWE + fastText |  | 0.531 |
| CSP |  | 0.654 |

Table 1:  Evaluation results on sememe prediction. The result of SPWCF + SPCSE is bold for comparing with other methods (SPWCF and SPCSE) which use only internal information. word frequency |  $\leqslant$ 50 | 51– 100 | 101 – 1,000 | 1,001 – 5,000 | 5,001 – 10,000 | 10,001 – 30,000 |  $>$30,000
---|---|---|---|---|---|---|---
occurrences | 8537 | 4868 | 3236 | 2036 | 663 | 753 | 686
SPWE | 0.312 | 0.437 | 0.481 | 0.558 | 0.549 | 0.556 | 0.509
SPSE | 0.187 | 0.273 | 0.339 | 0.409 | 0.407 | 0.424 | 0.386
SPWE + SPSE | 0.284 | 0.414 | 0.478 | 0.556 | 0.548 | 0.554 | 0.511
SPWCF | 0.456 | 0.414 | 0.400 | 0.443 | 0.462 | 0.463 | 0.479
SPCSE | 0.309 | 0.291 | 0.286 | 0.312 | 0.339 | 0.353 | 0.342
SPWCF + SPCSE | 0.467 | 0.437 | 0.418 | 0.456 | 0.477 | 0.477 | 0.494
SPWE + fastText | 0.495 | 0.472 | 0.462 | 0.520 | 0.508 | 0.499 | 0.490
CSP | 0.527 | 0.555 | 0.555 | 0.626 | 0.632 | 0.641 | 0.624
Table 2:  MAP scores on sememe prediction with different word frequencies.

(1) Considerable improvements are obtained via model ensembling, and the CSP
model achieves state-of-the-art performance. CSP combines the internal
character information with the external context information, which
significantly and consistently improves performance on sememe prediction. Our
results confirm the effectiveness of a combination of internal and external
information for sememe prediction; since different models focus on different
features of the inputs, the ensemble model can absorb the advantages of both
methods.

(2) The performance of SPWCF + SPCSE is better than that of SPSE, which means
using only internal information could already give good results for sememe
prediction as well. Moreover, in internal models, SPWCF performs much better
than SPCSE, which also implies the strong power of collaborative filtering.

(3) The performance of SPWCF + SPCSE is worse than SPWE + SPSE. This indicates
that it is still difficult to figure out the semantic meanings of a word
without contextual information, due to the ambiguity and meaning vagueness of
internal characters. Moreover, some words are not compound words (e.g.,
single-morpheme words or transliterated words), whose meanings can hardly be
inferred directly by their characters. In Chinese, internal character
information is just partial knowledge. We present the results of SPWCF and
SPCSE merely to show the capability to use the internal information in
isolation. In our case study, we will demonstrate that internal models are
powerful for low-frequency words, and can be used to predict senses that do
not appear in the corpus.

###  5.4 Analysis on Different Word Frequencies

To verify the effectiveness of our models on different word frequencies, we
incorporate the remaining words in HowNetiiiiiiiiiIn detail, we do not use the
numeral words, punctuations, single-character words, the words do not appear
in Sogou-T corpus (because they need to appear at least for one time to get
the word embeddings), and foreign abbreviations. into the test set. Since the
remaining words are low-frequency, we mainly focus on words with long-tail
distribution. We count the number of occurrences in the corpus for each word
in the test set and group them into eight categories by their frequency. The
evaluation results are shown in Table 2, from which we can observe that:

words | models | Top 5 sememes
---|---|---
钟表匠 (clockmaker) | internal |  人(human), 职位(occupation), 部件(part), 时间(time), 告诉(tell)
external |  人(human), 专(ProperName), 地方(place), 欧洲(Europe), 政(politics)
ensemble |  人(human), 职位(occupation), 告诉(tell), 时间(time), 用具(tool)
奥斯卡 (Oscar) | internal |  专(ProperName), 地方(place), 市(city), 人(human), 国都(capital)
external |  奖励(reward), 艺(entertainment), 专(ProperName), 用具(tool), 事情(fact)
ensemble |  专(ProperName), 奖励(reward), 艺(entertainment), 著名(famous), 地方(place)

Table 3: Examples of sememe prediction. For each word, we present the top $5$
sememes predicted by the internal model, external model and the final ensemble
model (CSP). Bold sememes are correct.

(1) The performances of SPSE, SPWE, and SPWE + SPSE decrease dramatically with
low-frequency words compared to those with high-frequency words. On the
contrary, the performances of SPWCF, SPCSE, and SPWCF + SPCSE, though weaker
than that on high-frequency words, is not strongly influenced in the long-tail
scenario. The performance of CSP also drops since CSP also uses external
information, which is not sufficient with low-frequency words. These results
show that the word frequencies and the quality of word embeddings can
influence the performance of sememe prediction methods, especially for
external models which mainly concentrate on the word itself. However, the
internal models are more robust when encountering long-tail distributions.
Although words do not need to appear too many times for learning good word
embeddings, it is still hard for external models to recommend sememes for low-
frequency words. While since internal models do not use external word
embeddings, they can still work in such scenario. As for the performance on
high-frequency words, since these words are used widely, the ambiguity of
high-frequency words is thus much stronger, while the internal models are
still stable for high-frequency words.

(2) The results also indicate that even low-frequency words in Chinese are
mostly composed of common characters, and thus it is possible to utilize
internal character information for sememe prediction on words with long-tail
distribution (even on those new words that never appear in the corpus).
Moreover, the stability of the MAP scores given by our methods on various word
frequencies also reflects the reliability and universality of our models in
real-world sememe annotations in HowNet. We will give detailed analysis in our
case study.

###  5.5 Case Study

The results of our main experiments already show the effectiveness of our
models. In this case study, we further investigate the outputs of our models
to confirm that character-level knowledge is truly incorporated into sememe
prediction.

In Table 3, we demonstrate the top $5$ sememes for “钟表匠” (clockmaker) and
“奥斯卡” (Oscar, i.e., the Academy Awards). “钟表匠” (clockmaker) is a typical
compound word, while “奥斯卡” (Oscar) is a transliterated word. For each word,
the top $5$ results generated by the internal model (SPWCF + SPCSE), the
external model (SPWE + SPSE) and the ensemble model (CSP) are listed.

The word “钟表匠” (clockmaker) is composed of three characters: “钟” (bell,
clock), “表” (clock, watch) and “匠” (craftsman). Humans can intuitively
conclude that clock $+$ craftsman $\,\to\,$ clockmaker. However, the external
model does not perform well for this example. If we investigate the word
embedding of “钟表匠” (clockmaker), we can know why this method recommends these
unreasonable sememes. The closest $5$ words in the train set to “钟表匠”
(clockmaker) by cosine similarity of their embeddings are: “瑞士” (Switzerland),
“卢梭” (Jean-Jacques Rousseau), “鞋匠” (cobbler), “发明家” (inventor) and “奥地利人”
(Austrian). Note that none of these words are directly relevant to bells,
clocks or watches. Hence, the sememes “时间” (time), “告诉” (tell), and “用具”
(tool) cannot be inferred by those words, even though the correlations between
sememes are introduced by SPSE. In fact, those words are related to clocks in
an indirect way: Switzerland is famous for watch industry; Rousseau was born
into a family that had a tradition of watchmaking; cobbler and inventor are
two kinds of occupations as well. With the above reasons, those words usually
co-occur with “钟表匠” (clockmaker), or usually appear in similar contexts as
“钟表匠” (clockmaker). It indicates that related word embeddings as used in an
external model do not always recommend related sememes.

The word “奥斯卡” (Oscar) is created by the pronunciation of Oscar. Therefore,
the meaning of each character in “奥斯卡” (Oscar) is unrelated to the meaning of
the word. Moreover, the characters “奥”, “斯”, and “卡” are common among
transliterated words, thus the internal method recommends “专” (ProperName) and
“地方” (place), etc., since many transliterated words are proper nouns or place
names.

##  6 Conclusion and Future Work

In this paper, we introduced character-level internal information for lexical
sememe prediction in Chinese, in order to alleviate the problems caused by the
exclusive use of external information. We proposed a Character-enhanced Sememe
Prediction (CSP) framework which integrates both internal and external
information for lexical sememe prediction and proposed two methods for
utilizing internal information. We evaluated our CSP framework on the
classical manually annotated sememe KB HowNet. In our experiments, our methods
achieved promising results and outperformed the state of the art on sememe
prediction, especially for low-frequency words.

We will explore the following research directions in the future: (1) Concepts
in HowNet are annotated with hierarchical structures of senses and sememes,
but those are not considered in this paper. In the future, we will take
structured annotations into account. (2) It would be meaningful to take more
information into account for blending external and internal information and
design more sophisticated methods. (3) Besides Chinese, many other languages
have rich subword-level information. In the future, we will explore methods of
exploiting internal information in other languages. (4) We believe that
sememes are universal for all human languages. We will explore a general
framework to recommend and utilize sememes for other NLP tasks.

## Acknowledgments

This research is part of the NExT++ project, supported by the National
Research Foundation, Prime Minister’s Office, Singapore under its
IRC@Singapore Funding Initiative. This work is also supported by the National
Natural Science Foundation of China (NSFC No. 61661146007 and 61572273) and
the research fund of Tsinghua University-Tencent Joint Laboratory for Internet
Innovation Technology. Hao Zhu is supported by Tsinghua University Initiative
Scientific Research Program. We would like to thank Katharina Kann, Shen Jin,
and the anonymous reviewers for their helpful comments.

## References

  * Auer et al. (2007) Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. 2007.  Dbpedia: A nucleus for a web of open data.  In _Proceedings of ISWC_ , pages 722–735.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015.  Neural machine translation by jointly learning to align and translate.  In _Proceedings of ICLR_.
  * Bloomfield (1926) Leonard Bloomfield. 1926.  A set of postulates for the science of language.  _Language_ , 2(3):153–164.
  * Bojanowski et al. (2017) Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017.  Enriching word vectors with subword information.  _TACL_ , 5:135–146.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008\.  Freebase: A collaboratively created graph database for structuring human knowledge.  In _Proceedings of SIGMOD_ , pages 1247–1250.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  In _Proceedings of NIPS_ , pages 2787–2795.
  * Chen et al. (2015) Xinxiong Chen, Lei Xu, Zhiyuan Liu, Maosong Sun, and Huan-Bo Luan. 2015.  Joint learning of character and word embeddings.  In _Proceedings of IJCAI_ , pages 1236–1242.
  * Cotterell et al. (2016a) Ryan Cotterell, Christo Kirov, John Sylak-Glassman, David Yarowsky, Jason Eisner, and Mans Hulden. 2016a.  The SIGMORPHON 2016 shared task—morphological reinflection.  In _Proceedings of SIGMORPHON_ , pages 10–22.
  * Cotterell et al. (2016b) Ryan Cotterell, Hinrich Schütze, and Jason Eisner. 2016b.  Morphological smoothing and extrapolation of word embeddings.  In _Proceedings of ACL_ , pages 1651–1660.
  * Creutz et al. (2007) Mathias Creutz, Teemu Hirsimäki, Mikko Kurimo, Antti Puurula, Janne Pylkkönen, Vesa Siivola, Matti Varjokallio, Ebru Arisoy, Murat Saraçlar, and Andreas Stolcke. 2007.  Analysis of morph-based speech recognition and the modeling of out-of-vocabulary words across languages.  In _Processings of HLT-NAACL_ , pages 380–387.
  * Dong and Dong (2006) Zhendong Dong and Qiang Dong. 2006.  _HowNet and the computation of meaning_.  World Scientific.
  * Duan et al. (2007) Xiangyu Duan, Jun Zhao, and Bo Xu. 2007.  Word sense disambiguation through sememe labeling.  In _Proceedings of IJCAI_ , pages 1594–1599.
  * Dyer et al. (2010) Chris Dyer, Jonathan Weese, Hendra Setiawan, Adam Lopez, Ferhan Ture, Vladimir Eidelman, Juri Ganitkevitch, Phil Blunsom, and Philip Resnik. 2010.  cdec: A decoder, alignment, and learning framework for finite-state and context-free translation models.  In _Proceedings of the ACL 2010 System Demonstrations_ , pages 7–12.
  * Faruqui et al. (2015) Manaal Faruqui, Jesse Dodge, Sujay Kumar Jauhar, Chris Dyer, Eduard Hovy, and Noah A. Smith. 2015.  Retrofitting word vectors to semantic lexicons.  In _Proceedings of HLT-NAACL_ , pages 1606–1615.
  * Fu et al. (2013) Xianghua Fu, Liu Guo, Guo Yanyan, and Wang Zhiqiang. 2013.  Multi-aspect sentiment analysis for Chinese online social reviews based on topic modeling and HowNet lexicon.  _Knowledge-Based Systems_ , 37:186–195.
  * Gan et al. (2002) Kok-Wee Gan, Chi-Yung Wang, and Brian Mak. 2002.  Knowledge-based sense pruning using the HowNet: an alternative to word sense disambiguation.  In _Proceedings of ISCSLP_.
  * Gan and Wong (2000) Kok Wee Gan and Ping Wai Wong. 2000.  Annotating information structures in Chinese texts using HowNet.  In _Proceedings of The Second Chinese Language Processing Workshop_ , pages 85–92.
  * Huang et al. (2014) Minlie Huang, Borui Ye, Yichen Wang, Haiqiang Chen, Junjun Cheng, and Xiaoyan Zhu. 2014.  New word detection for sentiment analysis.  In _Proceedings of ACL_ , pages 531–541.
  * Jin and Kann (2017) Huiming Jin and Katharina Kann. 2017.  Exploring cross-lingual transfer of morphological knowledge in sequence-to-sequence models.  In _Proceedings of SCLeM_ , pages 70–75.
  * Kann et al. (2017) Katharina Kann, Ryan Cotterell, and Hinrich Schütze. 2017.  One-shot neural cross-lingual transfer for paradigm completion.  In _Proceedings of ACL_ , pages 1993–2003.
  * Koren et al. (2009) Yehuda Koren, Robert Bell, and Chris Volinsky. 2009.  Matrix factorization techniques for recommender systems.  _Computer_ , 42(8).
  * Liu et al. (2012) Yiqun Liu, Fei Chen, Weize Kong, Huijia Yu, Min Zhang, Shaoping Ma, and Liyun Ru. 2012.  Identifying web spam with the wisdom of the crowds.  _ACM Transactions on the Web_ , 6(1):2:1–2:30.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013.  Distributed representations of words and phrases and their compositionality.  In _Proceedings of NIPS_ , pages 3111–3119.
  * Miller (1995) George A Miller. 1995.  WordNet: A lexical database for English.  _Communications of the ACM_ , 38(11):39–41.
  * Narasimhan et al. (2014) Karthik Narasimhan, Damianos Karakos, Richard Schwartz, Stavros Tsakalidis, and Regina Barzilay. 2014.  Morphological segmentation for keyword spotting.  In _Proceedings of EMNLP_ , pages 880–885.
  * Nastase and Szpakowicz (2001) Vivi Nastase and Stan Szpakowicz. 2001.  Word sense disambiguation in Roget’s thesaurus using WordNet.  In _Proceedings of the Workshop on WordNet and Other Lexical Resources: Applications, Extensions and Customizations_.
  * Navigli and Ponzetto (2012) Roberto Navigli and Simone Paolo Ponzetto. 2012.  BabelNet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network.  _Artificial Intelligence_ , 193:217–250.
  * Niu et al. (2017) Yilin Niu, Ruobing Xie, Zhiyuan Liu, and Maosong Sun. 2017.  Improved word representation learning with sememes.  In _Proceedings of ACL_ , pages 2049–2058.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  Glove: Global vectors for word representation.  In _Proceedings of EMNLP_ , pages 1532–1543.
  * Sarwar et al. (2001) Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2001.  Item-based collaborative filtering recommendation algorithms.  In _Proceedings of WWW_ , pages 285–295.
  * Seeker and Çetinoğlu (2015) Wolfgang Seeker and Özlem Çetinoğlu. 2015.  A graph-based lattice dependency parser for joint morphological segmentation and syntactic analysis.  _TACL_ , 3:359–373.
  * Suchanek et al. (2007) Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007.  Yago: A core of semantic knowledge.  In _Proceedings of WWW_ , pages 697–706.
  * Sun et al. (2014) Yaming Sun, Lei Lin, Nan Yang, Zhenzhou Ji, and Xiaolong Wang. 2014.  Radical-enhanced Chinese character embedding.  In _Proceedings of ICONIP_ , pages 279–286.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014.  Sequence to sequence learning with neural networks.  In _Proceedings of NIPS_ , pages 3104–3112.
  * Toutanova et al. (2015) Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. 2015.  Representing text for joint embedding of text and knowledge bases.  In _Proceedings of EMNLP_ , pages 1499–1509.
  * Wieting et al. (2016) John Wieting, Mohit Bansal, Kevin Gimpel, and Karen Livescu. 2016.  Charagram: Embedding words and sentences via character n-grams.  In _Proceedings of EMNLP_ , pages 1504–1515.
  * Xia et al. (2011) Yunqing Xia, Taotao Zhao, Jianmin Yao, and Peng Jin. 2011.  Measuring Chinese-English cross-lingual word similarity with HowNet and parallel corpus.  In _Proceedings of CICLing_ , pages 221–233. Springer.
  * Xie et al. (2017) Ruobing Xie, Xingchi Yuan, Zhiyuan Liu, and Maosong Sun. 2017.  Lexical sememe prediction via word embeddings and matrix factorization.  In _Proceedings of IJCAI_ , pages 4200–4206.
  * Yin (1984) Binyong Yin. 1984.  Quantitative research on Chinese morphemes.  _Studies of the Chinese Language_ , 5:338–347.
  * Yin et al. (2016) Rongchao Yin, Quan Wang, Peng Li, Rui Li, and Bin Wang. 2016.  Multi-granularity Chinese word embedding.  In _Proceedings of EMNLP_ , pages 981–986.
  * Zhu et al. (2017) Hao Zhu, Ruobing Xie, Zhiyuan Liu, and Maosong Sun. 2017.  Iterative entity alignment via joint knowledge embeddings.  In _Proceedings of IJCAI_ , pages 4258–4264.


# RaWaNet: Enriching Graph Neural Network Input via Random Walks on Graphs

Anahita Iravanizad &Edgar Ivan Sanchez Medina &Martin Stoll* Chair of
Scientific Computing, Department of Mathematics, Technische Universität
Chemnitz, 09107 Chemnitz, GermanyChair for Process Systems Engineering, Otto-
von-Guericke University, Universitätsplatz 2, Magdeburg, 39106, Germany

###### Abstract

In recent years, graph neural networks (GNNs) have gained increasing
popularity and have shown very promising results for data that are represented
by graphs. The majority of GNN architectures are designed based on developing
new convolutional and/or pooling layers that better extract the hidden and
deeper representations of the graphs to be used for different prediction
tasks. The inputs to these layers are mainly the three default descriptors of
a graph, node features $(X)$, adjacency matrix $(A)$, and edge features $(W)$
(if available). To provide a more enriched input to the network, we propose a
random walk data processing of the graphs based on three selected lengths.
Namely, (regular) walks of length 1 and 2, and a fractional walk of length
$\gamma\in(0,1)$, in order to capture the different local and global dynamics
on the graphs. We also calculate the stationary distribution of each random
walk, which is then used as a scaling factor for the initial node features
($X$). This way, for each graph, the network receives multiple adjacency
matrices along with their individual weighting for the node features. We test
our method on various molecular datasets by passing the processed node
features to the network in order to perform several classification and
regression tasks. Interestingly, our method, not using edge features which are
heavily exploited in molecular graph learning, let a shallow network
outperform well known deep GNNs.

##  1 Introduction

Machine learning based on Euclidean data, such as images, videos or audio
signals, has enabled a revolution throughout science and engineering (LeCun et
al., 2015). The backbone of many success stories are deep neural networks and
in particular convolutional neural networks. The extension of these techniques
to non-Euclidean domains such as social networks, recommender systems,
chemistry, computer graphics, NLP, and etc., has received a tremendous amount
of attention (Bronstein et al., 2017). In many cases the data are represented
as graphs, which are then embedded into graph neural networks (GNNs)(Gori et
al., 2005; Scarselli et al., 2009).

The main idea behind GNNs is to incorporate the non-Euclidean data into the
network to allow operations such as convolution or pooling. For this the
networks need to encode the graph’s adjacency information and possibly initial
features for the vertices and/or edges. The two main approaches for GNNs are
to design a convolution operator based on either spatial or spectral
information of the graph, in order to reveal a hidden and richer
representation of the input data. Usually to extract more meaningful features
from the graphs multiple spatial/spectral convolutional layers are stack to
each other, which makes the network more complex (Wu et al., 2020).

In order to incorporate the neighborhood information, we propose to process
the input data based on random walks of different lengths defined on the
graph. The use of random walks is motivated to go beyond a uniform
distribution of the nodes and to incorporate a multitude of adjacency
information. This will allow us to explore different dynamics within the
graph. For this purpose, we calculate the stationary distribution for each
walk that scales the node features of the data to serve as further input
information to the network. This would equip the network with an enriched
initial knowledge, such that we do not always require the use of a deep
network or even edge features of the graph.

We examined our method on various small molecular datasets obtained from
MoleculeNet (Wu et al., 2018) and a few molecular combustion-related datasets
(Schweidtmann et al., 2020a). Such choice of datasets allows us to test our
method on multiple chemical property prediction tasks, and to compare our
method with networks that are more complex with respect to the number of
layers and the inclusion of bond feature information.

We observe that using the random walk approach combined with a shallow
network, not relying on edge features, leads to better or on par performance
with the current deep GNN methods for these tasks. Remarkably, this shows just
how much information can be used from the graph properties before entering the
realm of convolutional or other network layers.

Our results highlight that using enriched initial information allows for
simpler and cheaper networks while not sacrificing accuracy. We believe that
this technique can lead to new ideas for other challenging tasks in graph-
based learning.

##  2 Related Works

Special interest has been set on molecular graphs. The models developed for
tasks in this domain are from both categories of classical machine learning
and graph neural networks. We believe our method is suitable to be implemented
in both realms and to offer prominent advancements in the field of graph
neural networks.

###  2.1 Graph Neural Networks

GNNs mainly evolve around designing convolutional layers, which are the
generalization of the convolution operation on grid-structured data to the
data represented by a graph (Wu et al., 2020). Graph convolutional operations
divide into two categories, spectral-based and spatial-based, which then gave
rise to Graph Attention Networks (GANs), Graph Generative Networks (GGNs) and
Graph Auto-encoders (GAEs)(Cao et al., 2020).

##### Spectral-based Methods.

The idea behind these methods is to generalize the spectral convolution from
Euclidean domain to graph domain, which was initially proposed by (Bruna et
al., 2013). The method is to calculate the graph Fourier transform of the
input signal, using the spectral decomposition of the graph Laplacian. Due to
high computational complexity of eigen-decomposition, several simplifications
and approximations of the calculation have been introduced by (Defferrard et
al., 2016; Kipf and Welling, 2016; Levie et al., 2018). Later (Zhuang and Ma,
2018) introduced Dual Graph Convolutional Network (DGCN), which is capable of
encoding both global and local information of the input data in parallel (Wu
et al., 2020).

##### Spatial-based Methods.

As a more straightforward and explicit generalization of CNNs, these methods
use the spatial relations of a node to extract its local features with respect
to a neighborhood. The idea began with Neural Network for Graphs (NN4G)
(Micheli, 2009), which directly adds (sums) up a node’s neighborhood
information at each layer. Similar to the convolution on an image the hidden
representation of a node is extracted through aggregation of the information
from its neighboring nodes, unlike images the neighborhood of each node varies
in size, which is the main challenge to this approach. Many different variants
of this approach have been proposed to tackle this problem, such as the
diffusion convolutional neural network (DCNN) (Atwood and Towsley, 2016), and
GraphSAGE (Hamilton et al., 2017). Later on (Gilmer et al., 2017) introduced
Message Passing Neural Network (MPNN) as a general framework for describing
spatial-based convolutional layers.

In order to get more general features, convolutional layers are usually
followed by a pooling layer. Different pooling layers has been designed to
learn graph representations, e.g. Set2set (Vinyals et al., 2015), which uses
an LSTM-based method and invariant to the order of the elements in the feature
matrix $X$, and also is used as a read out function in MPNN to get the graph-
level embedding (Zhou et al., 2020).

The above introduced convolutional and pooling layers are some of the many
network layers that are designed to read information from the graph input and
are utilized in building up the majority of GNN architectures. The objective
of these layers is to learn from the graph’s topology and/or its node feature
set. The general inputs to graph networks are the set of adjacency
information, node features and (possibly) edge features. In this paper, we
introduce RaWaNet, a technique that proposes additional inputs to GNN layers.
This would enable the network to access further topologies and input feature
sets based on different random walks on the graphs.

###  2.2 Molecular Graphs and Conventional Machine Learning

There are various ways to represent molecular structures, and graph is among
the most popular and intuitive ones. In a molecular graph vertices and edges
are denoting atoms and chemical bonds, respectively. Prior to deep learning
approaches in this domain, such as PotentialNet (Feinberg et al., 2018) and
MolDQN (Zhou et al., 2019), "classical" machine learning approaches were only
used to perform property predictions tasks (Atz et al., 2021).

As a prominent set of techniques, Quantitative Structure-Activity Relationship
(QSAR) are machine learning models to perform regression and classification
tasks for physicochemical, biological and environmental property prediction.
The process is to first extract the relevant information contained in the
chemical structure of the data and encode it as a set of molecular
descriptors, then to construct a model, e.g. Support Vector Machine (SVM),
Decision Tree, and Random Forest, and finally perform various property
prediction tasks using the selected molecular descriptors. 2D
descriptors/representations (also referred to as topological representations)
such as molecular graphs, are among the most popular molecular representations
that are effectively used for QSAR modeling (Cherkasov et al., 2014).

As a part of our experiments we use the graph embedding produced by our
technique to perform a classification task using random forest classifier,
where we outperform the results of all the state of the art GNNs and classical
models on the HIV molecular dataset (Hu et al., 2020) described in the
experiments section.

We perform our experiments with the goal to investigate the strength of these
additional feature sets via simple and shallow network setting.

##  3 Proposed Method

Before explaining our method we need to set up some graph notation and
preliminaries, and recall graphs properties.

###  3.1 Graph Theory Notation and Preliminaries

A (connected undirected) graph, $G=(V,E)$, is defined as a set of nodes
(vertices) $V=\\{v_{1},\ldots,v_{n}\\}$ along with a set of edges
$E=\\{\>(v_{i},v_{j})\>|\>v_{i},v_{j}\in V\mbox{~{}and~{}}i\neq j\\}\subseteq
V\times V$ whose elements denote connected vertex’s pairs. Cardinally of the
node and edge sets are $|V|=n$ and $|E|=m$, respectively. Each two connected
vertices are called adjacent (or neighbor), written $v_{i}\sim v_{j}$, and
that defines the adjacency matrix $A$ such that,

$A_{ij}=\begin{cases}1&\text{if $(v_{i},v_{j})\in E$}\\\
0&\text{elsewhere.}\end{cases}$

Assigning a non-negative weight to each edge defines weighted (undirected)
graph, $G=(V,E,W)$, with the weight matrix $W$ where $W_{ij}=w_{ij}\geq 0$. In
case of a weighted graph we will have a weighted adjacency matrix $A=W$, with
$A_{ij}=w_{ij}$. The degree of a node $v_{i}\in V$ is the number of edges
adjacent to it and denoted by $d(v_{i})\coloneqq d_{i}=\sum_{j:v_{i}\sim
v_{j}}w_{ij}$. The degree matrix $D$ is defined as a diagonal matrix whose
entries are the degrees of the nodes, i.e.
$D=\mathrm{diag}(d_{1},\ldots,d_{n})$.

A walk is an alternating sequence of nodes and edges, $v(0)e_{1}v(1)\ldots
e_{k}v(k)$, where $e_{t}=(v(t-1),v(t))$ and $v(t)\in V$ is the walker’s
position at the (time) step $t$. A path is a walk with no repeated vertices,
unless it is a closed path, i.e. $v(1)=v(k)$. The length of a walk or a path
equals to the number of edges in the sequence. The distance between two
vertices is the length of the shortest path between them. $G$ is connected if
between each nodes pair there is a path. To find the number of walks of length
$k$ from $v_{i}$ to $v_{j}$ we calculate $A^{k}$ and look at the entry of row
$i$ and column $j$ (or vice versa, as the undirected graphs have symmetric
adjacency matrices).

A random walk on a graph $G=(V,E,W)$ is a process of starting from a node
$v(0)\in V$ and move to one of its adjacent nodes by random, and repeat the
same after landing on the next node until reaching the desired length. This is
equivalent to creating a sequence of random nodes, $(v(t),\>t=1,2,\ldots,k)$,
where each two consecutive nodes in the sequence are connected. At step $t$,
when we are at a node $v(t)=v_{i}$, the probability of arriving at its
neighbor node $v_{j}$ is $\Pr(v(t+1)=v_{j}\>|\>v(t)=v_{i})=p_{ij}$ where

$p_{ij}=\begin{cases}w_{ij}/d_{i}&\text{if $(v_{i},v_{j})\in E$}\\\
0&\text{elsewhere,}\end{cases}$ (1)

and forming the transition matrix $M=(p_{ij})_{i,j\in V}=D^{-1}W$ (Lovász,
1993). The probability distribution of a random node at time (step) $t$ is
vector $P_{t}$ where

$P_{t}(i)=\mathrm{Pr}(v(t)=v_{i}).$ (2)

The random walk is then describing a Markov chain (process), with the
transition matrix $M$. Therefore the distribution of random walker at step $t$
is

$P_{t+1}=M^{T}P_{t}.$ (3)

Starting the walk with the distribution vector $P_{0}$ the distribution vector
at step $t$ will be

$P_{t}=(M^{T})^{t}P_{0}.$ (4)

A distribution (of a Markov process) is called stationary if it won’t change
in time, i.e. $P_{0}$ is a stationary distribution if $P_{t}=P_{0}$ for any
$t$. If the distribution of our random walker is stationary then we call our
walk a stationary walk. In other terms the random walk’s stationary
distribution is the eigenvector of the transition matrix $M$ corresponding to
the eigenvalue $1$, i.e.

$\pi=M^{T}\pi.$ (5)

As a random walk backwards is also considered a random walk our Markov chain
has the time reversibility property, which is equivalent to satisfying the
detailed balance equations

$\pi_{i}p_{ij}=\pi_{j}p_{ji},$ (6)

which is easy to solve. We have

$\pi_{i}\dfrac{w_{ij}}{d_{i}}=\pi_{j}\dfrac{w_{ji}}{d_{j}},$

where, as the graph is undirected, $w_{ij}=w_{ji}$. This means
$\dfrac{\pi_{i}}{d_{i}}=\dfrac{\pi_{j}}{d_{j}}=c$, where $c$ is a constant.
Also we know that

$\sum_{i=1}^{n}\pi_{i}=1\;\>\Rightarrow\;\>c=\dfrac{1}{\sum_{i=1}^{n}d_{i}},$

and hence,

$\pi=\dfrac{\mathrm{diag}(D)}{\sum_{i=1}^{n}d_{i}}.$ (7)

The graph Laplacian of the weighted undirected connected graph $G$ is a
symmetric matrix $L=D-A$, with the spectral decomposition $L=U\Lambda U^{T}$,
where $\Lambda=\mathrm{diag}(\lambda_{1},\ldots,\lambda_{n})$. (Riascos and
Mateos, 2014) introduced the fractional Laplacian as

$\begin{gathered}L^{\gamma}=U\Lambda^{\gamma}U^{T},\\\
\Lambda=\mathrm{diag}(\lambda_{1}^{\gamma},...,\lambda_{n}^{\gamma}),\quad\gamma\in(0,1),\end{gathered}$
(8)

in order to define a random walker who does not tend to revisit the same nodes
and therefore explores the network more efficiently. This gives us the
adjacency matrix

$A_{\gamma}=\mathrm{diag}(L^{\gamma})-L^{\gamma}.$ (9)

Following the same process as before they have also calculated the stationary
distribution of the fractional walk as

$\pi_{\gamma}=\dfrac{\mathrm{diag}(L^{\gamma})}{\sum_{i=1}^{n}(L^{\gamma})_{ii}}.$
(10)

The authors have shown that in the fractional random walk, i.e. $0<\gamma<1$,
the random walker more often explores and navigates new regions with every
step, using long-range navigation from one node to another arbitrarily distant
node and furthermore, the transition probability
$M_{\gamma}=\mathrm{diag}(L^{\gamma})^{-1}A_{\gamma}$ contains a global (non-
local) dynamics in the network as opposed to the regular random walks, i.e.
$k\in\mathbb{N}$.

###  3.2 Random Walk Data Processing: RaWaNet

As graph data carries such an expressive structure compared to other domains,
our suggested model includes more initial information for the input to the
graph network than only the matrix of node features $X\in\mathbb{R}^{n\times
c}$, adjacency information $A$, and if available the edge features
$X^{e}\in\mathbb{R}^{m\times d}$.

Random walks of various lengths, as an approach to navigate on the network,
each construct a new adjacency matrix with the weights
$A_{ij}^{k}=w_{ij}^{(k)}$ being the number of possible walks of length $k$
between the two nodes, or in other words a measure of the strength of their
connection.

For the lengths $k\in\\{1,2\\}$ the walk is also a path between nodes pairs.
As we know, if the walks are of the regular length $k=1$ there would be no
repeated nodes in every walk between two nodes. The same holds for the walks
of length $k=2$, except for the loops, i.e. the diagonal entries of $A^{2}$,
which are closed paths. Since the loops do not help with the navigation on the
graph, and do not add to the information of the nodes (as we already used the
neighborhood of the nodes in $A_{1}$) we remove the loops from the adjacency
matrix.

This gave rise to our idea of creating multiple further sets of adjacency
matrices for the input graphs and learn the data with more enriched initial
information. We calculate the stationary distributions of each random walk to
use as a weighting for the node features.

Figure 1: Illustration of an input graph with its three proposed random walks.
$A_{1}$ and $A_{2}$ for expressing the local dynamics and $A_{\gamma}$, with
$0<\gamma<1$, for a global and more descriptive navigation of the network. The
entries of the adjacency matrix of each graph equals the number of walks
between each two nodes, which is shown via thickness and color of the edges.
$\mathrm{diag}(\pi)$ denotes a diagonal matrix, where the diagonal entries are
the vector $\pi$, the stationary distribution of the random walker. The
colored nodes indicate the weighted node features obtained by multiplication
of the stationary distribution of each random walk with the node features.

To construct both local and non-local dynamics of the graph we selected two
standard random walks, i.e. of the length $k\in\\{1,2\\}$, and a fractional
random walk of length $0<\gamma<1$, respectively. In addition to $(A,X,X^{e})$
our input to the graph (neural) network contains the following information:

$\displaystyle(A_{1},X_{1}),$ (11) $\displaystyle(A_{2},X_{2}),$ (12)
$\displaystyle(A_{\gamma},X_{\gamma}),$ (13)

where

$\displaystyle A_{1}$ $\displaystyle=A,\hskip
75.0001ptX_{1}=\mathrm{diag}{(\pi_{1})}X,$ $\displaystyle A_{2}$
$\displaystyle=A^{2}-\mathrm{diag}{A^{2}},\hskip
28.00006ptX_{2}=\mathrm{diag}{(\pi_{2})}X,$ $\displaystyle A_{\gamma}$
$\displaystyle=\mathrm{diag}(L^{\gamma})-L^{\gamma},\qquad
X_{\gamma}=\mathrm{diag}{(\pi_{\gamma})}X.$

We know that the stationary distribution vector $\pi$ is the eigenvector of
the transition matrix $M$. Therefore,

$\mathrm{diag}{(\pi)}\in\mathbb{R}^{n\times n},$
$\mathrm{diag}{(\pi)}X\in\mathbb{R}^{n\times c}.$

In Figure 1 we give an illustration of the proposed random walks with their
adjacency matrices and modified node features. The proposed additional set of
graph inputs in Equations 11, 12 and 13 can then be used as input to proposed
GNN layers, such as convolutional, pooling, normalization, etc.

There are various ways to select and make use of the additional inputs in
order to enhance learning the data. From using all of them along with the
initial graph inputs, to only using one, e.g. $(A_{2},X_{2})$. This could give
rise to further research on how for different datasets and different network
architectures a different subset of these inputs improve the learning
accuracy.

###  3.3 A Solution for Disconnected Graphs

For this method we need the graphs to be connected, while we know some data
can include disconnected graphs. For example in our experiments, the molecular
graphs might contain ions which causes disconnection in graphs.

To address this problem we tracked the disconnected graph and added an extra
node to it, whose features are zero and is connected to all the nodes in the
graph. In other words, a zero-padding for $X$ from below, and a one-padding
for $A$ from below and right (except for the diagonal entry). This way the
network could yet distinguish graphs that are originally disconnected from the
connected ones.

We also need $A^{2}$ to be a connected graph, therefore the graphs need to
have at least three vertices. For the graphs with two vertices we followed the
above, and fixed the problem with an additional node. There are rare
exceptions of having graphs with a single node due to the approach of
constructing hydrogen depleted graphs, e.g. methane. For these cases we
proposed adding two additional nodes that are connected to the single node and
to each other. This leads to add two rows of zeros to $X$ and two rows and
columns of ones to $A$ (except for the diagonal entries).

There are certainly other approaches to prepare the dataset to be connected
with minimum three nodes, which could be further investigated.

##  4 Experiments

The recent IPCC report (Masson-Delmotte et al., 2021) has highlighted, once
more, the urgent need for a transition to a more sustainable economy. In this
regard, the enormous chemical space has to be explored to find potential
sustainable replacements of many currently used chemical compounds. For
encouraging the contributions towards solving this worldwide-concerning
conundrum, we have used three molecular combustion-related datasets (MON, RON,
DCN) (Schweidtmann et al., 2020a) that reflect the autoignition behavior of
molecules. This might lead to substantial advances in the design/discovery of
renewable fuels. Additionally, we have applied our method to a very small
ecotoxicological dataset (BCF)(Zhao et al., 2008), that meets the official
REACH legislation (REACH, ), in a way to test our model with very small
molecular graph databases (a common situation in most sustainability related
chemical data banks (VEGA, )). This dataset reports the bioacummulation factor
of several chemicals in fish, which is closely related to the accumulation of
pollutants in ecosystems. Moreover, in order to ensure a fair comparison to
other existing learning algorithms, we have also tested our method using
several molecular datasets available from MoleculeNet (Wu et al., 2018) and
splitted by OGB (Hu et al., 2020). This includes biophysical (HIV, BACE),
physico-chemical (ESOL, FreeSolv, Lipophilicity) and physiological (BBBP,
SIDER, ClinTox) properties.

Many graph networks have been developed in recent years and their performance
has been evaluated for learning molecular datasets. To investigate the
informativity of the proposed additional inputs, i.e. Equations 11, 12 and 13,
we perform our experiments on a shallow network where its configuration is
tuned for each dataset separately. For a more precise comparison with the
results of state of the art methods, we choose the same setting for atom
features. The aim of our experiments is not to outperform the current results,
but to highlight the information contained in the data processing we propose.
As a result we believe that this can be implemented in various current and
future graph network architectures.

Current state of the art methods working on molecular graphs are based on
either neural fingerprints 111Here by neural fingerprints we refer to the
final graph embedding vector obtained from the GNN models. that combined atom
and bond features in an optimized way according to the task at hand or
circular fingerprints (e.g ECFP) that enconde the substructures present in the
molecular graph into a fixed-size vector (Duvenaud et al., 2015). For a fair
comparison, we use the same data splitting and SMILES string transformation to
molecular graphs as the networks we are comparing our results to. We also keep
the same transformation of the initial features $X$ to a higher dimension for
each task as is done in deep methods explained later.

The extended input to all the networks for our experiments is

$(A,X,X^{e},A_{1},X_{1},A_{2},X_{2},A_{\gamma},X_{\gamma}).$

For the fractional walk length we chose $\gamma=0.1$. Also, we did not use the
bond features $X^{e}$ in our experiments because we would like to highlight
the sole contributions from the additional weighted features that results from
our random walk technique.

###  4.1 OGB Classification and Regression Tasks

[ht!]

Table 1: ROC-AUC results for OGB binary classification datasets. Here the
shallow network is a one prediction (linear) layer. The comparison is with the
performance of various models, taken from OGB leaderbord.

---
Dataset |  Model |  Test |  Valid. |  Edge Feat. |  #Tasks
ogbg-molhiv | FingerPrint + GMAN |  82.44% |  83.29% |  ✓ |  1
Neural FingerPrints |  82.32% |  83.31% |  ✓
Graphormer + FPs |  82.25% |  83,96% |  ✓
Graphormer (2021) |  80.51% |  83.10% |  ✓
directional GSN (2020) |  80.39% |  84.73% |  ✓
RaWaNet + Shallow Network |  79.79% |  81.12% |  ✗
DGN (2021) |  79.70% |  84.70% |  ✓
EGC-M (2021) |  78.18% |  83.96% |  ✗
GIN + virtual node (2020) |  77.07% |  84.79% |  ✓
ogbg-molsider | RaWaNet + Shallow Network |  62.58% |  61.22% |  ✗ |  27
GCN + virtual node (2020) |  61.65% |  59.86% |  ✓ |
ogbg-molclintox | RaWaNet + Shallow Network |  92.01% |  96.95% |  ✗ |  2
GCN |  91.30% |  99.24% |  ✓ |
ogbg-molbbbp | RaWaNet + Shallow Network |  70.27% |  96.43% |  ✗ |  1
GIN + virtual node |  69.88% |  94.66% |  ✓ |
ogbg-molbase | RaWaNet + Shallow Network |  83.37% |  76.83% |  ✗ |  1
GCN |  79.15% |  73.74% |  ✓ |

[ht!]

Table 2: RMSE results for OGB regression tasks. Here the shallow network is a
one prediction (linear) layer.

---
Dataset | Model | Test | Valid. | Edge Feat.
ogbg-molesol | RaWaNet + Shallow Network |  0.922 |  0.882 |  ✗
GIN + virtual node |  0.998 |  0.878 |  ✓
ogbg-molfreesolv | RaWaNet + Shallow Network |  1.905 |  2.282 |  ✗
GIN + virtual nod |  2.151 |  2.181 |  ✓
ogbg-mollipophilicity | GIN + virtual node |  0.704 |  0.679 |  ✓
RaWaNet + Shallow Network |  0.813 |  0.800 |  ✗

OGB (Hu et al., 2020) has adopted these datasets (HIV, BACE, ESOL, FreeSolv,
Lipophilicity, BBBP, SIDER, ClinTox) from MoleculeNet and performed a
standardized scaffold splitting procedure on them. As we mentioned before, the
network setting for our experiments is shallow and has a simple setup. For all
datasets we created an initial node embedding using the OGB atom-encoder
class. The dimension of the embedding is tuned for each dataset and is set to
1000 for the ogbg-molhiv dataset and is either 150 or 300 for all other
datasets. A subset of $\\{X,X_{1},X_{2},X_{\gamma}\\}$ is selected for each
task, where $\gamma=0.1$. Each task is using 3 or 4 of theses feature sets
except for the ogbg-molhiv dataset, where we only use $X_{2}$ to learn. For
all datasets but ogbg-molhiv we apply a graph normalization, GraphNorm (Cai et
al., 2021), on each of the feature matrices, followed by an activation
function of either ReLU, tanh, or sigmoid. The results are then passed through
a global pooling layer, which is either the average pooling alone or the
average pooling scaled via max pooling. The output vectors are then
concatenated and fed into a linear layer to perform the according prediction
tasks. We use the Adam optimizer for all the methods and tune the learning
rate for each task. The batch size for train/validation/test is 32 across all
datasets. Regression tasks are trained for 300 epochs, ogbg-molhiv for 50
epochs and all other classification tasks for 100 epochs. We repeat all the
experiments 10 times and report the mean of their respective accuracy measure.

The results for the classification tasks are shown in Table 1. We can see a
higher performance from our learning method compared to the deep graph neural
networks. This highlights once more that our network achieves comparable
performance while being shallow and significantly simpler. For the ogbg-molhiv
dataset, we include the results by some of the selected models from the OGB
leaderbord, including the current top leading models. These provide a variety
of baselines with the models ranging from traditional MPNNs to the most recent
more expressive architectures. We observe that the top 3 models with a
significant jump in their performance are benefiting from combining two shared
factors, the complexity of their models and the use of the extended-
connectivity fingerprints (ECFPs). For instance, Graphormer (Ying et al.,
2021) learns over 47M network parameters compared to the number of parameters
of our model that is at least 2 orders of magnitude less. These results
suggest that a meaningful processing of the input data can contribute
significantly to the performance of the model. We believe that in the future
this can be considered and implemented in a more general way through our
RaWaNet framework along different graph domains.

Regression results are shown in Table 2 where we outperform the state of the
art for two out of three tasks via a shallow network.

####  4.1.1 Classical Machine Learning Approach for ogbg-molhiv

As mentioned above, the top results in the leaderboard (shown in Table 1)
belong to deep networks trained using molecular fingerprints, more precicely
ECFPs, which are vector embeddings encoding the structure of the molecules.

We test our method in a different way and produce a fingerprint for graphs in
ogbg-molhiv dataset in order to fit a classical machine learning classifier.
This time we extract a one-hot encoding of the same node features as above and
use global pooling layers to get the vector embedding.

For this we employ two feature sets, $\\{X,X_{2}\\}$, and use the embedding
vector to fit a random forest classifier. We use max and average global
pooling to output the final feature vector, which then serves as the input to
fit the classifier.

We perform the classification task on two models; the first one only takes our
RaWaNet feature vector as input while the second one uses the concatenation of
both the RaWaNet vector and the the Morgan finger print ((Rogers and Hahn,
2010)). The size of the feature vector in our first model is 513, and in the
second one $(2048+513)$.

The number of the estimators for all models is 1000 and the number of jobs is
set to -1. The min_samples_leaf in our both models is set to 4. The max_depth
when we only have RaWaNet input is set to 10, while it is set to None for the
other models. We show the averaged results over 10 runs.

[h]

Table 3: ROC-AUC results for ogbg-molhiv classification task using classical
machine learning approach. The second result is taken from OGB leaderbord.

---
Model |  Test (%) |  Valid. (%)
RaWaNet + Morgan FP + Rand. Forest | 82.84$\pm$0.22 | 83.17$\pm$0.17
Morgan FP + Rand. Forest (2010) | 80.60$\pm$0.10 | 84.20$\pm$0.30
RaWaNet + Rand. Forest | 80.27$\pm$0.13 | 77.33$\pm$0.36

Our results (Table 3) indicate how expressive is the embedding produced by our
processed data. With a much less deep tree we got on par test accuracy as when
we use the Morgan FP. Also the feature vector from RaWaNet is much smaller in
size, which can be the result of a more compressed feature extraction in this
technique. Finally, combining both vectors results in outperforming all the
existing state of the arts (shown in Tables 1 and 3), while maintaining a much
simpler structure for the network.

####  4.1.2 Going Deep for Lipophilicity Dataset.

To test if going deep with our additional input can improve the performance we
implemented a convolutional message passing network for ogbg-mollipophilicity
dataset. As we did not perform well learning this dataset with our simple
setting, we use a deep network with our proposed RaWaNet inputs. Here, we
again do not use the bond feature information. After encoding the initial
input node features to an embedding of dimension 50, we concatenate $X_{1}$,
$X_{2}$, and $X_{\gamma}$ to obtain one feature tensor $X_{T}$. Then $X_{T}$
is fed into three parallel message passing layers GraphConv (Morris et al.,
2019) with adjacency information corresponding to walks of length 1, 2, and
$0.1$, respectively. We then pass the outputs through a shared GRU layer to
form a message passing network scheme. The resulting features are now the
updated $X_{1}$, $X_{2}$, and $X_{\gamma}$, which are again concatenated and
passed through GraphConv layers followed by another GRU layer as before.
Finally, we apply an average pooling to each updated embedding and sum these
three pooled features to then perform a prediction using a linear layer. We
use the Adam optimizer with a 0.001 learning rate and run the network for 150
epochs. As it is shown in Table 4, we outperform the result from OGB.

Table 4: RMSE results for ogbg-mollipophilicity, learned by a deep network
setting with our random walk processed input. Here the Deep Network is a
message passing scheme using GraphConv + GRU layers.
---
Model |  Test |  Valid. |  Edge Feat.
RaWaNet + Deep Network | 0.684 | 0.695 | ✗
GIN + virtual node | 0.704 | 0.679 | ✓

[ht!]

Table 5: MAE results for RON, MON, DCN and BCF property prediction tasks. Here
the shallow network contains two hidden (linear) layers, for generating
feature embedding and prediction. GNN1 and GNN2 are from (Schweidtmann et al.,
2020a) and (Medina et al., 2021) respectively.

---
Dataset | Model | Avg. MAE | EL MAE | EL $\mathbf{R^{2}}$ | Edge Feat.
MON | RaWaNet + Shallow Network |  5.2 |  4.6 |  90% |  ✗
GNN1 |  5.4 |  - |  - |  ✓
RON | RaWaNet + Shallow Network |  4.6 |  4.0 |  95% |  ✗
GNN1 |  5.2 |  - |  - |  ✓
DCN | RaWaNet + Shallow Network |  6.0 |  5.1 |  92% |  ✗
GNN1 |  6.6 |  - |  - |  ✓
BCF | RaWaNet + Shallow Network |  0.38 |  0.36 |  89% |  ✗
GNN2 |  - |  0.48 |  82% |  ✓
Zhao (QSAR) (2008) |  - |  - |  83% |  ✓

###  4.2 MON, RON, DCN, BCF Property Prediction Tasks

(Morris et al., 2019) introduce k-dimensional GNNs (k-GNNs) as a
generalization to GNNs, which is capable of distinguishing non-isomorphism
between graphs. They defined a local and global neighborhood for their
introduced higher dimensional graph, which is based on higher order
Weisfeiler-Leman graph isomorphisms. (Schweidtmann et al., 2020b) designed a
GNN for the prediction of MON, RON, DCN, three fuel-related molecular
properties. They have implemented their networks using the 2-GNN from the
k-GNN package to get higher-order graph structures as part of their message
passing process. (Medina et al., 2021) also implemented a message passing GNN
using two layers of NNConv (Gilmer et al., 2017) followed by a GRU layer.

In our proposed network, as well as the GNNs that we compare our results to,
we obtain an initial node embedding by applying a linear layer to the one-hot
encoded node features. Here we use $X_{1}$, $X_{2}$ and $X_{\gamma}$ and take
them to the dimension 100. We then apply a GraphNorm on outputs, followed by a
ReLU function. After passing through a global add pooling we concatenate the
feature vectors to the get the final embedding of the graph and feed it to a
linear layer for prediction. The optimizer for all datasets is AdamW with a
learning rate of $0.01$. The batch size for train/validation/test is 64/4/4
and the number of training epochs 200. We use StepLR scheduler for BCF dataset
and ReduceLROnPlateau for the other three. All the shown experiments in Table
5 are the average MAE over 40 runs with different random seeds for
train/validation split. EL MAE and EL $R^{2}$ refer to the accuracy results
from ensemble learning. Ensemble learning here means to use all the 40 trained
models for prediction, and average over their results. As it is shown in Table
5 we outperform all the tasks with a much faster and smaller network.

##  5 Conclusion and Future Work

In this paper we showed that a scaled input in combination with a shallow and
simple architecture can show better or a on par performance with state of the
art GNNs. For this, we introduced additional, more descriptive graph
topologies along with their corresponding scaled node features. These are
based on random walks of different lengths on the graph and their resulting
stationary distributions as scaling of the node features. The resulting
architectures are not only able to produce excellent performance but also only
require orders of magnitude fewer parameters than most current GNNs rely on.
Relying on simple networks we outperformed state of the art graph networks on
HIV dataset and many more classification and regression tasks for molecular
datasets.

Our contribution is a data processing technique that enables us to encode more
information through the additional inputs to the network, which grants us a
simplified and efficient way of learning challenging datasets from various
applications. We believe that this idea can be used within many different
graph based architectures and unfold a new chapter of graph neural network
architecture design.

## References

  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  _nature_ , 521(7553):436–444, 2015.
  * Bronstein et al. (2017) Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: going beyond euclidean data.  _IEEE Signal Processing Magazine_ , 34(4):18–42, 2017.
  * Gori et al. (2005) Marco Gori, Gabriele Monfardini, and Franco Scarselli.  A new model for learning in graph domains.  In _Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005._ , volume 2, pages 729–734. IEEE, 2005.
  * Scarselli et al. (2009) F. Scarselli, M. Gori, Ah Chung Tsoi, M. Hagenbuchner, and G. Monfardini.  The Graph Neural Network Model.  _IEEE Transactions on Neural Networks_ , 20(1):61–80, January 2009.  ISSN 1045-9227, 1941-0093.  doi:10.1109/TNN.2008.2005605.  URL http://ieeexplore.ieee.org/document/4700287/.
  * Wu et al. (2020) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  _IEEE transactions on neural networks and learning systems_ , 32(1):4–24, 2020.
  * Wu et al. (2018) Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande.  Moleculenet: a benchmark for molecular machine learning.  _Chemical science_ , 9(2):513–530, 2018.
  * Schweidtmann et al. (2020a) Artur M Schweidtmann, Jan G Rittig, Andrea König, Martin Grohe, Alexander Mitsos, and Manuel Dahmen.  Graph neural networks for prediction of fuel ignition quality.  _Energy & fuels_, 34(9):11395–11407, 2020a.
  * Cao et al. (2020) Wenming Cao, Zhiyue Yan, Zhiquan He, and Zhihai He.  A comprehensive survey on geometric deep learning.  _IEEE Access_ , 8:35929–35949, 2020.
  * Bruna et al. (2013) Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun.  Spectral networks and locally connected networks on graphs.  _arXiv preprint arXiv:1312.6203_ , 2013.
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  _Advances in neural information processing systems_ , 29:3844–3852, 2016.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Levie et al. (2018) Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein.  Cayleynets: Graph convolutional neural networks with complex rational spectral filters.  _IEEE Transactions on Signal Processing_ , 67(1):97–109, 2018.
  * Zhuang and Ma (2018) Chenyi Zhuang and Qiang Ma.  Dual graph convolutional networks for graph-based semi-supervised classification.  In _Proceedings of the 2018 World Wide Web Conference_ , pages 499–508, 2018.
  * Micheli (2009) Alessio Micheli.  Neural network for graphs: A contextual constructive approach.  _IEEE Transactions on Neural Networks_ , 20(3):498–511, 2009.
  * Atwood and Towsley (2016) James Atwood and Don Towsley.  Diffusion-convolutional neural networks.  In _Advances in neural information processing systems_ , pages 1993–2001, 2016.
  * Hamilton et al. (2017) William L Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pages 1025–1035, 2017.
  * Gilmer et al. (2017) Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In _International conference on machine learning_ , pages 1263–1272. PMLR, 2017.
  * Vinyals et al. (2015) Oriol Vinyals, Samy Bengio, and Manjunath Kudlur.  Order matters: Sequence to sequence for sets.  _arXiv preprint arXiv:1511.06391_ , 2015.
  * Zhou et al. (2020) Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun.  Graph neural networks: A review of methods and applications.  _AI Open_ , 1:57–81, 2020.
  * Feinberg et al. (2018) Evan N Feinberg, Debnil Sur, Zhenqin Wu, Brooke E Husic, Huanghao Mai, Yang Li, Saisai Sun, Jianyi Yang, Bharath Ramsundar, and Vijay S Pande.  Potentialnet for molecular property prediction.  _ACS central science_ , 4(11):1520–1530, 2018\.
  * Zhou et al. (2019) Zhenpeng Zhou, Steven Kearnes, Li Li, Richard N Zare, and Patrick Riley.  Optimization of molecules via deep reinforcement learning.  _Scientific reports_ , 9(1):1–10, 2019.
  * Atz et al. (2021) Kenneth Atz, Francesca Grisoni, and Gisbert Schneider.  Geometric deep learning on molecular representations.  _arXiv preprint arXiv:2107.12375_ , 2021.
  * Cherkasov et al. (2014) Artem Cherkasov, Eugene N Muratov, Denis Fourches, Alexandre Varnek, Igor I Baskin, Mark Cronin, John Dearden, Paola Gramatica, Yvonne C Martin, Roberto Todeschini, et al.  Qsar modeling: where have you been? where are you going to?  _Journal of medicinal chemistry_ , 57(12):4977–5010, 2014.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec.  Open graph benchmark: Datasets for machine learning on graphs.  _arXiv preprint arXiv:2005.00687_ , 2020.
  * Lovász (1993) László Lovász.  Random walks on graphs.  _Combinatorics, Paul Erdos is Eighty_ , 2(1-46):4, 1993.
  * Riascos and Mateos (2014) A. P. Riascos and José L. Mateos.  Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights.  _Physical Review E_ , 90(3):032809, September 2014\.  ISSN 1539-3755, 1550-2376.  doi:10.1103/PhysRevE.90.032809.  URL https://link.aps.org/doi/10.1103/PhysRevE.90.032809.
  * Masson-Delmotte et al. (2021) V. Masson-Delmotte, P. Zhai, A. Pirani, S. L. Connors, C. Péan, S. Berger, N. Caud, Y. Chen, L. Goldfarb, M. I. Gomis, M. Huang, K. Leitzell, E. Lonnoy, J. B. R. Matthews, T. K. Maycock, T. Waterfield, O. Yelekçi, R. Yu, and B. Zhou (eds.).  _IPCC, 2021: Climate Change 2021: The Physical Science Basis. Contribution of Working Group I to the Sixth Assessment Report of the Intergovernmental Panel on Climate Change_.  Cambridge University Press, 2021.
  * Zhao et al. (2008) Chunyan Zhao, Elena Boriani, Antonio Chana, Alessandra Roncaglioni, and Emilio Benfenati.  A new hybrid system of qsar models for predicting bioconcentration factors (bcf).  _Chemosphere_ , 73(11):1701–1707, 2008.
  * (29) REACH.  Registration, Evaluation, Authorization and Restriction of Chemicals (REACH) Regulation (EC) No 1907/2006 of the European Parliament and of the Council of 18 December 2006.  https://eur-lex.europa.eu/legal-content/en/TXT/HTML/?uri=CELEX:02006R1907-20210215, 2006\.  Accessed: 2021-08-13.
  * (30) VEGA.  VEGA QSAR platform.  https://www.vegahub.eu/about-qsar/qsar-regulation-and-research/, 2021\.  Accessed: 2021-08-13.
  * Duvenaud et al. (2015) David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraguirre, Rafael Gómez-Bombarelli, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams.  Convolutional networks on graphs for learning molecular fingerprints.  _arXiv preprint arXiv:1509.09292_ , 2015.
  * Ying et al. (2021) Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu.  Do transformers really perform bad for graph representation?  _arXiv preprint arXiv:2106.05234_ , 2021.
  * Bouritsas et al. (2020) Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein.  Improving graph neural network expressivity via subgraph isomorphism counting.  _arXiv preprint arXiv:2006.09252_ , 2020.
  * Beani et al. (2021) Dominique Beani, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò.  Directional graph networks.  In _International Conference on Machine Learning_ , pages 748–758. PMLR, 2021.
  * Tailor et al. (2021) Shyam A. Tailor, Felix L. Opolka, Pietro Liò, and Nicholas D. Lane.  Adaptive filters and aggregator fusion for efficient graph convolutions, 2021.
  * Cai et al. (2021) Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie-yan Liu, and Liwei Wang.  Graphnorm: A principled approach to accelerating graph neural network training.  In _International Conference on Machine Learning_ , pages 1204–1215. PMLR, 2021.
  * Rogers and Hahn (2010) David Rogers and Mathew Hahn.  Extended-connectivity fingerprints.  _Journal of chemical information and modeling_ , 50(5):742–754, 2010.
  * Morris et al. (2019) Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 4602–4609, 2019.
  * Medina et al. (2021) EI Sanchez Medina, Steffen Linke, and Kai Sundmacher.  Prediction of bioconcentration factors (bcf) using graph neural networks.  In _Computer Aided Chemical Engineering_ , volume 50, pages 991–997. Elsevier, 2021.
  * Schweidtmann et al. (2020b) Artur Schweidtmann, Jan Rittig, Andrea König, Martin Grohe, Alexander Mitsos, and Manuel Dahmen.  Graph Neural Networks for Prediction of Fuel Ignition Quality.  May 2020b.  doi:10.26434/chemrxiv.12280325.v1.  URL /articles/preprint/Graph_Neural_Networks_for_Prediction_of_Fuel_Ignition_Quality/12280325/1.  Publisher: ChemRxiv.