# Evolving Computation Graphs

Andreea Deac
Mila – Québec AI Institute
Université de Montréal
Jian Tang
Mila – Québec AI Institute
HEC Montréal

###### Abstract

Graph neural networks (GNNs) have demonstrated success in modeling relational
data, especially for data that exhibits homophily: when a connection between
nodes tends to imply that they belong to the same class. However, while this
assumption is true in many relevant situations, there are important real-world
scenarios that violate this assumption, and this has spurred research into
improving GNNs for these cases. In this work, we propose Evolving Computation
Graphs (ECGs), a novel method for enhancing GNNs on heterophilic datasets. Our
approach builds on prior theoretical insights linking node degree, high
homophily, and inter vs intra-class embedding similarity by rewiring the GNNs’
computation graph towards adding edges that connect nodes that are likely to
be in the same class. We utilise weaker classifiers to identify these edges,
ultimately improving GNN performance on non-homophilic data as a result. We
evaluate ECGs on a diverse set of recently-proposed heterophilous datasets and
demonstrate improvements over the relevant baselines. ECG presents a simple,
intuitive and elegant approach for improving GNN performance on heterophilic
datasets without requiring prior domain knowledge.

##  1 Introduction

Neural networks applied to graph-structured data have demonstrated success
across various domains, including practical applications like drug discovery
[33], transportation networks [9], chip design [25] and theoretical
advancements [8, 3]. Numerous architectures fall under the category of graph
neural networks [6], with one of the most versatile ones being Message Passing
Neural Networks [12]. The fundamental concept behind these networks is that
nodes communicate with their neighbouring nodes through messages in each
layer. These messages, received from neighbours, are then aggregated in a
permutation-invariant manner to contribute to a new node representation.

It has been observed that the performance of graph neural networks may rely on
the underlying assumption of homophily, which suggests that nodes are
connected by edges if they are similar based on their attributes or belonging
to the same class, as commonly seen in social or citation networks. However,
this assumption often fails to accurately describe real-world data when the
graph contains heterophilic edges, connecting dissimilar nodes. This
observation holds particular significance since graph neural networks tend to
exhibit significantly poorer performance on heterophilic graphs compared to
datasets known to be homophilic. Several studies [46, 45, 41, 15] have
highlighted this issue, using a mixture of strongly homophilous graphs—such as
Cora, Citeseer and Pubmed [31]—as well a standard suite of six heterophilic
datasets—Squirrel, Chameleon, Cornell, Texas, Wisconsin and Actor [30,
35]—first curated jointly by Pei et al. [26].

Figure 1: A simplified illustration of Evolving Computation Graphs. Step 1:
nodes in a graph, $G$, are embedded using a pre-trained weak classifier. Step
2: Based on these embeddings, a nearest-neighbour graph, $G^{\mathrm{EGC}}$,
is generated. This graph is likely to have improved propagation and homophily
properties (illustrated by similar colours between neighbouring nodes). Step
3: Message passing is performed, both in the original and in the ECG graph, to
update node representations.

In the context of this standard suite of heterophilic graphs, it has been
observed that general graph neural network architectures tend to underperform
unless there is high label informativeness [23, 27]. In prior work, this issue
was tackled primarily by proposing modifications to the GNN architecture.
These modifications include changes to the aggregation function, such as
separating self- and neighbour embeddings [46], mixing low- and high-frequency
signals [4, 22], and predicting and utilising the compatibility matrix [47].
Other approaches involve using the Jacobi basis in spectral GNNs [41] or
learning cellular sheaves for neural sheaf diffusion [5] to improve
performance.

However, it was recently remarked [28] that this standard heterophilous suite
has significant drawbacks, such as data originating from only three sources,
two of the datasets having significant numbers of repeated nodes and improper
evaluation regarding class imbalance. To address these shortcomings, a more
recent benchmark suite has been introduced by Platonov et al. [28],
incorporating improvements on all of the above issues. Interestingly, once
such corrections are accounted for, standard GNN models such as graph
convolutional networks [19, GCN], GraphSAGE [14, SAGE], graph attention
networks [38, GAT], and Graph Transformers [32, GT] have demonstrated superior
performance compared to specialized architectures tailored specifically for
heterophily—in spite of the heterophilic properties of the datasets. The
notable exception is -sep [46] which has consistently improved GAT and GT by
modelling self and neighbouring nodes separately.

In light of this surprising discovery, we suggest that there should be
alternate routes to making the most of heterophilic datasets. Rather than
attempting to modify these standard GNNs, we propose modifying their
_computation graph_ : effectively, enforcing messages to be sent across
additional pairs of nodes. These node pairs are chosen according to a
particular measure of _similarity_. If the similarity metric is favourably
chosen, such a computation graph will improve the overall homophily
statistics, thereby creating more favourable conditions for GNNs to perform
well.

We further propose that the _modification_ of the computation graph should be
separate from its _utilisation_ 111We note that [26, 34] also rest on a
similar proposal, however their updated computation graph is fully derived as
a function of the input graph structure (ignoring node features and labels),
and thus it is unavoidably _vulnerable_ to any biases or inconsistencies in
the input graph—and real-world graph inputs are rarely flawless.. That is, we
proceed in two phases: the first phase learns the representations that allow
us to construct new computation graphs, and the second phase utilises those
representations to construct new computation graphs, to be utilised by a GNN
in each layer. This design choice makes our method elegant, performant and
easy to evaluate: the two-phase nature means we are not susceptible to bilevel
optimisation (as in [11, 18]), the graphs we use need to be precomputed
exactly once rather than updated on-the-fly in every layer (as in [42]), and
because the same computation graph is used across all GNN layers, we can more
rigidly evaluate how useful this graph is, all other things kept equal.

Hence, the essence of our method is _Evolving Computation Graphs_ (ECG), which
uses weak classifiers to generate node embeddings. These embeddings are then
used to define a similarity metric between nodes (such as cosine similarity).
We then select edges in a $k$-nearest neighbour fashion: we connect each node
to $k$ nodes most similar to it, according to the metric. The edges selected
in this manner form a complementary graph, which we propose using in parallel
with the input graph to update each node’s representation. For this purpose,
we use standard, off-the-shelf, GNNs. Our method is illustrated in Figure 1.

The nature of the weak classifier employed in ECG is flexible and, for the
purpose of this paper, we used two representative options. The first option is
a point-wise MLP classifier, attempting to cluster together nodes based on the
given training labels, without any graph-based biases. For the second option,
we attempt the converse: utilising the given graph structure and node
features, but not relying on the training labels. This is a suitable setting
for a self-supervised graph representation learning method, such as BGRL [36],
which is designed to cluster together nodes with similar local
neighbourhoods—both in terms of subgraphs and features—through a bootstrapping
objective [13].

To evaluate the effectiveness of ECG, we conduct experiments on the benchmark
suite proposed by Platonov et al. [28]. Our results demonstrate that ECG
models outperform their GNN baselines in 19 out of 20 head-to-head
comparisons. The most significant improvements can be noticed for GCNs—which
are best suited to benefit from improved homophily—where improvements reach up
to $10\%$ in absolute terms. Further, the best performing ECG models
outperform a diverse set of representative heterophily-specialised GNNs.

##  2 Background

In this section, we introduce the generic setup of learning representations on
graphs, along with all of the key components that comprise our ECG method.

#### Graph representation learning setup

We denote graphs by $G=(V,E)$, where $V$ is the set of nodes and $E$ is the
set of edges, and we denote by $e_{uv}\in E$ the edge that connects nodes $u$
and $v$. For the datasets considered here, we can assume that the input graphs
are provided to the GNNs via two inputs: the _node feature matrix_ , ${\bf
X}\in\mathbb{R}^{|V|\times k}$ (such that $\mathbf{x}_{u}\in\mathbb{R}^{k}$
are the input features of node $u\in V$), and the _adjacency matrix_ , ${\bf
A}\in\\{0,1\\}^{|V|\times|V|}$, such that $a_{uv}$ indicates whether nodes $u$
and $v$ are connected by an edge. We further assume the graph is _undirected_
; that is, ${\bf A}={\bf A}^{\top}$. We also use $d_{u}=\sum_{v\in
V}a_{uv}\left(=\sum_{v\in V}a_{vu}\right)$ to denote the degree of node $u$.

We focus on node classification tasks with $C$ representing the set of
possible classes, where for node with input features $\mathbf{x}_{u}$, there
is a label $y_{u}\in C$. Thus we aim to learn a function $f$ that minimises
$\mathbb{E}[\mathcal{L}(y_{u},\hat{y}_{u})]$, where $\hat{y}_{u}$ is the
prediction of $f(\mathbf{x}_{u})=\hat{y}_{u}$, and $\mathcal{L}$ is the cross-
entropy loss function.

#### Graph neural networks

The one-step layer of a GNN can be summarised as follows [6]:

$\mathbf{h}_{u}^{(l)}=\phi^{(l)}\left(\mathbf{h}_{u}^{(l-1)},\bigoplus_{(u,v)\in
E}\psi^{(l)}\left(\mathbf{h}_{u}^{(l-1)},\mathbf{h}_{v}^{(l-1)}\right)\right)$
(1)

where, by definition, we set $\mathbf{h}_{u}^{(0)}=\mathbf{x}_{u}$. Leveraging
different (potentially learnable) functions for
$\phi^{(l)}:\mathbb{R}^{k}\times\mathbb{R}^{m}\rightarrow\mathbb{R}^{k^{\prime}}$,
$\bigoplus:\mathrm{bag}(\mathbb{R}^{m})\rightarrow\mathbb{R}^{m}$ and
$\psi^{(l)}:\mathbb{R}^{k}\times\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ then
recovers well-known GNN architectures. Examples include GCN [20]:
$\psi^{(l)}(\mathbf{x}_{u},\mathbf{x}_{v})=\beta_{uv}\omega^{(l)}(\mathbf{x}_{v})$,
with $\beta_{uv}\in\mathbb{R}$ being a constant based on ${\bf A}$, GAT [39]:
$\psi^{(l)}(\mathbf{x}_{u},\mathbf{x}_{v})=\alpha^{(l)}(\mathbf{x}_{u},\mathbf{x}_{v})\omega^{(l)}(\mathbf{x}_{v})$
with $\alpha^{(l)}:\mathbb{R}^{k}\times\mathbb{R}^{k}\rightarrow\mathbb{R}$
being a (softmax-normalised) self-attention mechanism, and -sep [46]:
$\phi^{(l)}={\bf
W}^{(l)}_{\mathrm{self}}\phi^{(l)}_{1}\left(\mathbf{h}_{u}^{(l-1)}\right)+{\bf
W}^{(l)}_{\mathrm{agg}}\phi^{(l)}_{2}\left(\bigoplus_{(u,v)\in
E}\psi^{(l)}(\mathbf{h}_{u}^{(l-1)},\mathbf{h}_{v}^{(l-1)})\right)$, where we
explicitly decompose $\phi^{(l)}$ into two parts, with one of them
($\phi^{(l)}_{1}$) depending on the receiver node only.

#### Homophily

has been repeatedly mentioned as an important measure of the graph, especially
when it comes to GNN performance. Intuitively, it corresponds to an assumption
that neighbouring nodes tend to share labels: $a_{uv}=1\implies y_{u}=y_{v}$,
which is often the case for many industrially-relevant real world graphs (such
as social networks). Intuitively, a graph with high homophily will make it
easier to exploit neighbourhood structure to derive more accurate node labels.

However, in spite of the importance of quantifying homophily in a graph, there
is no universally-agreed-upon metric for this. One very popular metric, used
by several studies, is edge homophily [1], which measures the proportion of
homophilic edges:

$\texttt{h-edge}=\frac{|(u,v)\in E:y_{u}=y_{v}|}{|E|}$ (2)

while [27] also introduces adjusted homophily to account for number of classes
and their distributions:

$\texttt{h-adj}=\frac{\texttt{h-edge}-\sum_{k=1}^{C}D_{k}^{2}/(2|E|)^{2}}{1-\sum_{k=1}^{C}D_{k}^{2}/(2|E|)^{2}}$
(3)

where $D_{k}=\sum_{u:y_{u}=k}d_{u}$, the sum of degrees for the nodes
belonging to class $k$.

Additionally, the label informativeness (LI) measure proposed in [27] measures
how much information about a node’s label is gained by observing its
neighbour’s label, on average. It is defined as

$\texttt{LI}=I(y_{\xi},y_{\eta})/H(y_{\xi})$ (4)

where $(\xi,\eta)\in E$ is a uniformly-sampled edge, $H$ is the Shannon
entropy and $I$ is mutual information.

#### Weak classifier

In order to derive novel computation graphs which are likely to result in
higher test performance, we likely require “novel” homophilic connections to
emerge—rather than amplifying the homophily already present in ${\bf A}$.
Therefore, for the purposes of building a useful computation graph, our ECG
method aims to first learn representations of nodes governed by a model which
does _not_ have access to inputs (${\bf X}$), graph structure (${\bf A}$) and
training labels (${\bf y}_{\mathrm{tr}}$) simultaneously. We hence call such a
model a “weak classifier”, as it is not exposed to the same kind of inductive
biases as a supervised GNN would (and hence it must obtain useful models which
do not rely on these biases).

#### MLPs

Arguably the simplest way to make a weak classifier, as above, is to withhold
access to the graph structure (${\bf A}$), and force the model to classify the
nodes in pure isolation from one another. This is effectively a standard
multi-layer perceptron (MLP) applied pointwise. Another way of understanding
this model is setting ${\bf A}={\bf I}_{|V|}$, or equivalently, $E=\\{(u,u)\
|\ u\in V\\}$, in Equation 1, which is sometimes referred to as the Deep Sets
model [44]. We train this model by using cross-entropy against the training
nodes’ labels (${\bf y}_{\mathrm{tr}}$) and, once trained, use the final layer
activations, $\mathbf{h}_{u}^{(L)}$—for a model with $L$ layers—as our MLP
embeddings.

#### BGRL

While using the embeddings from an MLP can offer a solid way to improve
homophily metrics, their confidence will degrade for nodes where the model is
less accurate outside of the training set—which are arguably the nodes we
would like to improve predictions on the most. Accordingly, as a converse
approach to obtaining a weak classifier, we may also withhold access to the
training labels ($\mathbf{y}_{\mathrm{tr}}$). Now the model is forced to
arrange the node representations in a way that will be mindful of the input
features and graph structure, but without knowing the task specifics upfront,
and hence not vulnerable to overfitting on the training nodes. Such a weak
classifier naturally lends itself to self-supervised learning on graphs.

Bootstrapped graph latents [36, BGRL] is a state-of-the-art self-supervised
graph representation learning method based on BYOL [13]. BGRL learns two GNN
encoders with identical architecture; an _online_ encoder,
$\mathcal{E}_{\theta}$, and a _target_ encoder, $\mathcal{E}_{\phi}$. BGRL
also contains a _predictor_ network $p_{\theta}$. We offer a “bird’s eye” view
of how BGRL is trained, and defer to [36] for implementation details.

At each step of training, BGRL proceeds as follows. First, two data
augmentations (e.g. random node and edge dropout) are applied to the input
graph, obtaining augmented graphs $({\bf X}_{1},{\bf A}_{1})$ and $({\bf
X}_{2},{\bf A}_{2})$. Then, the two encoders are applied to these
augmentations, recovering a pair of latent node embeddings: ${\bf
H}_{1}=\mathcal{E}_{\theta}({\bf X}_{1},{\bf A}_{1})$, ${\bf
H}_{2}=\mathcal{E}_{\phi}({\bf X}_{2},{\bf A}_{2})$. The first embedding is
additionally passed through the predictor network: ${\bf
Z}_{1}=p_{\theta}({\bf H}_{1})$. At this point, BGRL attempts to preserve the
cosine similarity between all the corresponding nodes in ${\bf Z}_{1}$ and
${\bf H}_{2}$, via the following loss function:

$\mathcal{L}_{\mathrm{BGRL}}=-\frac{{\bf Z}_{1}{\bf H}_{2}^{\top}}{\|{\bf
Z}_{1}\|\|{\bf H}_{2}\|}$ (5)

Lastly, the parameters of the online encoder $\mathcal{E}_{\theta}$ and
predictor $p_{\theta}$ are updated via stochastic gradient descent on
$\mathcal{L}_{\mathrm{BGRL}}$, and the parameters of the target encoder
$\mathcal{E}_{\phi}$ are updated as the exponential moving average of the
online encoder’s parameters.

Once the training procedure concludes, typically only the online network
$\mathcal{E}_{\theta}$ is retained, and hence the embeddings ${\bf
H}=\mathcal{E}_{\theta}({\bf X},{\bf A})$ are the BGRL embeddings of the input
graph given by node features ${\bf X}$ and adjacency matrix ${\bf A}$.

Owing to its bootstrapped objective, BGRL does not require the generation of
negative samples, and is hence computationally efficient compared to
contrastive learning approaches. Further, it is very successful at large
scales; it was shown by Addanki et al. [2] that BGRL’s benefits persist on
industrially relevant graphs of hundreds of millions of nodes, leading to one
of the top-3 winning entries at the OGB-LSC competition [17]. This is why we
employ it as a representative self-supervised embedding method for our ECG
framework.

##  3 Evolving Computation Graphs

Armed with the concepts above, we are now ready to describe the steps of the
ECG methodology. Please refer to Algorithm 1 for a pseudocode summary.

#### Step 1: Embedding extraction

Firstly, we assume that an appropriate weak classifier has already been
trained (as discussed in previous sections), and is capable of producing node
embeddings. We start by invoking this classifier to obtain ECG embeddings
$\mathbf{H}_{\mathrm{ECG}}=\gamma(\mathbf{X},\mathbf{A})$. We study two simple
but potent variants of $\gamma$, as per the previous section:

  * MLP:

In this case, we utilise a simple deep MLP222Note that this MLP only computes
high-dimensional embeddings of each node; while training $\gamma$, an
additional logistic regression layer is attached to this architecture.; that
is,
$\gamma(\mathbf{X},\mathbf{A})=\sigma\left(\sigma\left(\mathbf{X}\mathbf{W}_{1}\right)\mathbf{W}_{2}\right)$,
where $\mathbf{W}_{\cdot}$ are the weights of the MLP, and $\sigma$ is the
GELU activation function [16].

  * BGRL:

In this case, we set $\gamma=\mathcal{E}_{\theta}$, the online encoder of
BGRL. For our experiments, we utilise a publicly available off-the-shelf
implementation of BGRL provided by the Deep Graph
Library333https://github.com/dmlc/dgl/tree/master/examples/pytorch/bgrl [40],
which uses a two-layer GCN [20] as the base encoder.

The parameters of $\gamma$ are kept frozen throughout, and are not to be
further trained on.

#### Step 2: Graph construction

Having obtained $\mathbf{H}_{\mathrm{ECG}}$, we can now use it to compute a
similarity metric between the nodes, such as cosine similarity, as follows:

$\mathbf{S}=\mathbf{H}_{\mathrm{ECG}}\mathbf{H}_{\mathrm{ECG}}^{\top}\qquad\hat{s}_{uv}=\frac{s_{uv}}{\|\mathbf{h}_{\mathrm{ECG}_{u}}\|\|\mathbf{h}_{\mathrm{ECG}_{v}}\|}$
(6)

Based on this similarity metric, for each node $u\in V$ we select its
neighbourhood $\mathcal{N}_{u}^{\mathrm{ECG}}$ to be its $k$ nearest
neighbours in $\mathbf{S}$ (where $k$ is a tunable hyperparameter):

$\mathcal{N}_{u}^{\mathrm{ECG}}=\mathrm{top\text{-}}k_{v\in V}\hat{s}_{uv}$
(7)

Equivalently, we construct a new computation graph,
$G^{\mathrm{ECG}}=(V,E^{\mathrm{ECG}})$, such that its edges are
$E^{\mathrm{ECG}}=\\{(u,v)\ |\ u\in V\wedge v\in\mathcal{N}_{u}\\}$. These
edges are effectively determined by the weak classifier.

#### Step 3: Parallel message passing

Finally, once the ECG graph, $G^{\mathrm{ECG}}$, is available, we can run our
GNN of choice over it. To retain the topological benefits contained in the
input graph structure, we opt to run two GNN layers in parallel—one over the
input graph (as in Equation 1), and one over the ECG graph, as follows:

$\displaystyle\mathbf{h}_{\mathrm{INP}_{u}}^{(l)}$
$\displaystyle=\phi^{(l)}_{\mathrm{INP}}\left(\mathbf{h}_{u}^{(l-1)},\bigoplus_{(u,v)\in
E}\psi_{\mathrm{INP}}^{(l)}\left(\mathbf{h}_{u}^{(l-1)},\mathbf{h}_{v}^{(l-1)}\right)\right)$
(8) $\displaystyle\mathbf{h}_{\mathrm{ECG}_{u}}^{(l)}$
$\displaystyle=\phi^{(l)}_{\mathrm{ECG}}\left(\mathbf{h}_{u}^{(l-1)},\bigoplus_{(u,v)\in
E^{\mathrm{ECG}}}\psi_{\mathrm{ECG}}^{(l)}\left(\mathbf{h}_{u}^{(l-1)},\mathbf{h}_{v}^{(l-1)}\right)\right)$
(9)

Then the representation after $l$ layers is obtained by jointly transforming
these two representations:

$\mathbf{h}_{u}^{(l)}=\mathbf{W}^{(l)}\mathbf{h}_{\mathrm{INP}_{u}}^{(l)}+\mathbf{U}^{(l)}\mathbf{h}_{\mathrm{ECG}_{u}}^{(l)}$
(10)

where $\mathbf{W}^{(l)}$ and $\mathbf{U}^{(l)}$ are learnable parameters.

Equations 8–10 can then be repeatedly iterated, much like is the case for any
standard GNN layer. As it is possible that $G^{\mathrm{ECG}}$ will contain
noisy edges which do not contribute to useful propagation of messages, we
additionally apply DropEdge [29] when propagating over the ECG graph, with
probability $p_{de}=0.5$.

Input: Graph $G=(V,E)$; Node Feature Matrix $\mathbf{X}$; Adjacency Matrix
$\mathbf{A}$.

Hyper-parameters: Value of $k$; Drop edge probability $p_{de}$; Number of
layers $L$;

Output: Predicted labels $\hat{\mathbf{y}}$

begin

/* Step 1: Extract embeddings */

$\mathbf{H}_{\mathrm{ECG}}\leftarrow\gamma(\mathbf{X},\mathbf{A})$ /*
Embeddings stored in matrix */

/* Step 2: Construct ECG graph */

$\mathbf{S}\leftarrow\mathbf{H}_{\mathrm{ECG}}\mathbf{H}_{\mathrm{ECG}}^{\top}$

for  _$u\in V$_ do

for  _$v\in V$_ do

$\hat{s}_{uv}\leftarrow
s_{uv}/(\|\mathbf{h}_{\mathrm{ECG}_{u}}\|\|\mathbf{h}_{\mathrm{ECG}_{v}}\|)$
/* Compute pair-wise cosine similarities */

$\mathcal{N}_{u}^{\mathrm{ECG}}\leftarrow\mathrm{top\text{-}}k_{v\in
V}\hat{s}_{uv}$ /* Compute $k$ nearest neighbours of $u$ */

$E^{\mathrm{ECG}}\leftarrow\\{(u,v)\ |\ u\in V\wedge v\in\mathcal{N}_{u}\\}$
/* Construct the ECG edges */

/* Step 3: Running ECG-GNN with parallel processing of $G$ and
$G^{\mathrm{ECG}}$ */

for  _$u\in V$_ do

$\mathbf{h}^{0}_{u}\leftarrow\mathbf{x}_{u}$ /* Setting initial node features
*/

for  _$l\leftarrow 1$ to $L$_ do

/* Message passing propagation with the two parallel processors on $G$ and
$G^{\mathrm{ECG}}$ respectively */

$E^{\mathrm{ECG}}_{(l)}\leftarrow\mathrm{DropEdge}(E^{\mathrm{ECG}},p_{de})$
/* Randomly drop edges in the ECG graph */

for  _$u\in V$_ do

$\mathbf{h}_{\mathrm{INP}_{u}}^{(l)}\leftarrow\phi^{(l)}_{\mathrm{INP}}\left(\mathbf{h}_{u}^{(l-1)},\bigoplus_{(u,v)\in
E}\psi_{\mathrm{INP}}^{(l)}\left(\mathbf{h}_{u}^{(l-1)},\mathbf{h}_{v}^{(l-1)}\right)\right)$
/* GNN on $G$ */

$\mathbf{h}_{\mathrm{ECG}_{u}}^{(l)}\leftarrow\phi^{(l)}_{\mathrm{ECG}}\left(\mathbf{h}_{u}^{(l-1)},\bigoplus_{(u,v)\in
E_{(l)}^{\mathrm{ECG}}}\psi_{\mathrm{ECG}}^{(l)}\left(\mathbf{h}_{u}^{(l-1)},\mathbf{h}_{v}^{(l-1)}\right)\right)$
/* GNN on $G^{\mathrm{ECG}}$ */

$\mathbf{h}_{u}^{(l)}\leftarrow\mathbf{W}^{(l)}\mathbf{h}_{\mathrm{INP}_{u}}^{(l)}+\mathbf{U}^{(l)}\mathbf{h}_{\mathrm{ECG}_{u}}^{(l)}$
/* Updating the node representation */

/* Predict node labels */

for  _$u\in V$_ do

${p}_{u}\leftarrow\mathrm{softmax}(\mathbf{W}^{(c)}\mathbf{h}^{(L)}_{u})$
$\hat{y}_{u}\leftarrow\arg\max_{c\in C}{p}_{c}$ /* Predicted class label */

return _$\hat{\mathbf{y}}$_

Algorithm 1 Evolving Computation Graph for Graph Neural Networks: ECG-GNN

##  4 Experiments

We evaluate the performance of ECG on five heterophilic datasets, recently-
proposed by Platonov et al. [28]: roman-empire, amazon-ratings, minesweeper,
tolokers and questions. All five datasets are node classification tasks,
testing for varying levels of homophily in the input (roman-empire has the
highest label informativeness), different connectivity profiles (tolokers is
the most dense, questions has the lowest values of clustering coefficients)
and providing both real-world datasets (amazon-ratings), as well as synthetic
examples (minesweeper).

We ran ECG as an extension on standard GNN models, choosing the “-sep” variant
[46] for GAT and GT as it was noted to improve their performance consistently
on these tasks [28]. Thus, our baselines are GCN, GraphSAGE, GAT-sep and GT-
sep, which we extend by modifying their computation graph as presented in
Section 3. For each ECG model, we ran three variants, depending on which weak
classifier was used to select the complementary edges, $E^{\mathrm{ECG}}$: the
MLP, the BGRL, or a concatenation of the output of the two.

For each of these architectures, the hyper-parameters to sweep are the number
of neighbours sampled in the ECG graph, $k$ (selected from $\\{3,10,20\\}$),
the edge dropout rate used on it (selected from $\\{0.,0.5\\}$, the hidden
dimension of the graph neural networks, where the one ran on the original
graph $G$ always matches the one ran on $G^{\mathrm{ECG}}$ (selected from
$\\{256,512\\}$), as well as the standard choice of number of layers (selected
from $\\{2,3,4,5\\}$). In the Appendix, we present additional information on
the experiments, together with the hyper-parameters corresponding to the best
validation results.

In Table 1, we show the test performance corresponding to the highest
validation score among all embedding possibilites for each of the five
datasets and for each of the four baselines. Altogether, there are 20 dataset-
model combinations that ECG is tested on. We find that on 19 out of these 20
combinations (marked with arrow up in the table), using ECG improves the
performance of the corresponding GNN architecture, the only exception being
GraphSAGE on amazon-ratings.

Moreover, we observe the highest gains in performance are achieved by ECG-GCN,
ranging from $1.17\%$ to $10.84\%$ (absolute values) in a manner that is
correlated with the homophily of the dataset. This confirms the hypothesis
that, due to the aggregation function it employs, GCN is also the architecture
most prone to performance changes based on the homophily of the graph.

Additionally, we note that BGRL-based embeddings are consistently preferred
for the roman-empire and questions graphs. These datasets have the lowest
average degree and average local clustering – this emphasises the need for
different methods of obtaining complementary graphs, balancing connectivity
and homophily aspects, as remarked in [43].

Table 1: ECG performance on datasets proposed in [28]. We report accuracy for roman-empire and amazon-ratings and ROC AUC for minesweeper, tolokers, and questions. Model | roman-empire | amazon-ratings | minesweeper | tolokers | questions
---|---|---|---|---|---
MLP | $65.88{\scriptscriptstyle\pm 0.38}$ | $45.90{\scriptscriptstyle\pm 0.52}$ | $50.89{\scriptscriptstyle\pm 1.39}$ | $72.95{\scriptscriptstyle\pm 1.06}$ | $70.34{\scriptscriptstyle\pm 0.76}$
GCN | $73.69{\scriptscriptstyle\pm 0.74}$ | $48.70{\scriptscriptstyle\pm 0.63}$ | $89.75{\scriptscriptstyle\pm 0.52}$ | $83.64{\scriptscriptstyle\pm 0.67}$ | $76.09{\scriptscriptstyle\pm 1.27}$
ECG-GCN |  $84.53{\scriptscriptstyle\pm 0.26}$ ($\uparrow$) |  $51.12{\scriptscriptstyle\pm 0.38}$ ($\uparrow$) |  $92.63{\scriptscriptstyle\pm 0.10}$ ($\uparrow$) |  $\textbf{84.81}{\scriptscriptstyle\pm 0.25}$ ($\uparrow$) |  $77.50{\scriptscriptstyle\pm 0.35}$ ($\uparrow$)
SAGE | $85.74{\scriptscriptstyle\pm 0.67}$ | $53.63{\scriptscriptstyle\pm 0.39}$ | $93.51{\scriptscriptstyle\pm 0.57}$ | $82.43{\scriptscriptstyle\pm 0.44}$ | $76.44{\scriptscriptstyle\pm 0.62}$
ECG-SAGE |  $87.88{\scriptscriptstyle\pm 0.25}$ ($\uparrow$) |  $53.45{\scriptscriptstyle\pm 0.27}$ ($\downarrow$) |  $94.11{\scriptscriptstyle\pm 0.07}$ ($\uparrow$) |  $82.61{\scriptscriptstyle\pm 0.29}$ ($\uparrow$) |  $77.23{\scriptscriptstyle\pm 0.36}$ ($\uparrow$)
GAT-sep | $88.75{\scriptscriptstyle\pm 0.41}$ | $52.70{\scriptscriptstyle\pm 0.62}$ | $93.91{\scriptscriptstyle\pm 0.35}$ | $83.78{\scriptscriptstyle\pm 0.43}$ | $76.79{\scriptscriptstyle\pm 0.71}$
ECG-GAT-sep |  $\textbf{89.62}{\scriptscriptstyle\pm 0.18}$ ($\uparrow$) |  $\textbf{53.65}{\scriptscriptstyle\pm 0.39}$ ($\uparrow$) |  $\textbf{94.52}{\scriptscriptstyle\pm 0.20}$ ($\uparrow$) |  $84.23{\scriptscriptstyle\pm 0.25}$ ($\uparrow$) |  $77.38{\scriptscriptstyle\pm 0.18}$ ($\uparrow$)
GT-sep | $87.32{\scriptscriptstyle\pm 0.39}$ | $52.18{\scriptscriptstyle\pm 0.80}$ | $92.29{\scriptscriptstyle\pm 0.47}$ | $82.52{\scriptscriptstyle\pm 0.92}$ | $78.05{\scriptscriptstyle\pm 0.93}$
ECG-GT-sep |  $89.56{\scriptscriptstyle\pm 0.16}$ ($\uparrow$) |  $53.25{\scriptscriptstyle\pm 0.39}$ ($\uparrow$) |  $93.62{\scriptscriptstyle\pm 0.27}$ ($\uparrow$) |  $84.00{\scriptscriptstyle\pm 0.24}$ ($\uparrow$) |  $78.12{\scriptscriptstyle\pm 0.32}$ ($\uparrow$)
H2GCN | $60.11{\scriptscriptstyle\pm 0.52}$ | $36.47{\scriptscriptstyle\pm 0.23}$ | $89.71{\scriptscriptstyle\pm 0.31}$ | $73.35{\scriptscriptstyle\pm 1.01}$ | $63.59{\scriptscriptstyle\pm 1.46}$
CPGNN | $63.96{\scriptscriptstyle\pm 0.62}$ | $39.79{\scriptscriptstyle\pm 0.77}$ | $52.03{\scriptscriptstyle\pm 5.46}$ | $73.36{\scriptscriptstyle\pm 1.01}$ | $65.96{\scriptscriptstyle\pm 1.95}$
GPR-GNN | $64.85{\scriptscriptstyle\pm 0.27}$ | $44.88{\scriptscriptstyle\pm 0.34}$ | $86.24{\scriptscriptstyle\pm 0.61}$ | $72.94{\scriptscriptstyle\pm 0.97}$ | $55.48{\scriptscriptstyle\pm 0.91}$
FSGNN | $79.92{\scriptscriptstyle\pm 0.56}$ | $52.74{\scriptscriptstyle\pm 0.83}$ | $90.08{\scriptscriptstyle\pm 0.70}$ | $82.76{\scriptscriptstyle\pm 0.61}$ | $\textbf{78.86}{\scriptscriptstyle\pm 0.92}$
GloGNN | $59.63{\scriptscriptstyle\pm 0.69}$ | $36.89{\scriptscriptstyle\pm 0.14}$ | $51.08{\scriptscriptstyle\pm 1.23}$ | $73.39{\scriptscriptstyle\pm 1.17}$ | $65.74{\scriptscriptstyle\pm 1.19}$
FAGCN | $65.22{\scriptscriptstyle\pm 0.56}$ | $44.12{\scriptscriptstyle\pm 0.30}$ | $88.17{\scriptscriptstyle\pm 0.73}$ | $77.75{\scriptscriptstyle\pm 1.05}$ | $77.24{\scriptscriptstyle\pm 1.26}$
GBK-GNN | $74.57{\scriptscriptstyle\pm 0.47}$ | $45.98{\scriptscriptstyle\pm 0.71}$ | $90.85{\scriptscriptstyle\pm 0.58}$ | $81.01{\scriptscriptstyle\pm 0.67}$ | $74.47{\scriptscriptstyle\pm 0.86}$
JacobiConv | $71.14{\scriptscriptstyle\pm 0.42}$ | $43.55{\scriptscriptstyle\pm 0.48}$ | $89.66{\scriptscriptstyle\pm 0.40}$ | $68.66{\scriptscriptstyle\pm 0.65}$ | $73.88{\scriptscriptstyle\pm 1.16}$

Figure 2: For roman-empire, we use a random GCN layer to obtain node
embeddings based on the original graph $G$ (left) or from the complementary
graph $G^{\mathrm{ECG}}$ (right). The colours correspond to the ground-truth
labels of the nodes.

###  4.1 Qualitative studies

In Table 2, we analyse the properties of the complementary graphs
$G^{\mathrm{ECG}}$ with $k=3$ nearest neighbours. We note that this represents
the graph used by ECG-GCN, which preferred lower values of $k$, while the
optimal values of $k$ for SAGE, GAT-sep and GT-sep were on the higher end,
varying between $3$, $10$ and $20$ depending on the dataset.

We observe that MLP-ECG confirms our hypothesis: taking the edges
corresponding to the pairs of nodes marked as most similar by the ResNet
results in a graph $G^{\mathrm{ECG}}$ with high homophily, especially compared
to the original input graph. It is important to note that all of our MLP-ECG
graphs were obtained with a relatively shallow ResNet, which, as it can be
seen in Table 1 lacks in performance compared to the graph-based methods.
However, our method’s success in conjunction with GNNs shows that even a weak
classifier can be used to generate homophilic graphs that can improve
performance when used to complement the information provided by the given
input data.

In Figure 2, we also verify how predictive of the node classes the graph
topology is when obtained from the original data compared to when we build a
complementary graph $G^{\mathrm{ECG}}$. More precisely, we first build the
graph $G^{\mathrm{ECG}}$ as presented in Step 1 of Algorithm 1, using pre-
trained MLP embeddings. Then we use a randomly initialised GCN to compute node
embeddings on the input graph $G$, as well as on $G^{\mathrm{ECG}}$. We
visualise these two sets of node embeddings using t-SNE [37] by projecting to
a 2D space, attributing the colour of each point based on the node’s ground
truth label. We can observe that using the $G^{\mathrm{ECG}}$ topology leads
to more distinguishable clusters corresponding to the classes even without any
training, thus supporting the enhancements in performance when building ECG-
GNN.

Table 2: Statistics of the original heterophilous graphs and of the evolutionary computation graph obtained from MLP and BGRL. | roman-empire | amazon-ratings | minesweeper | tolokers | questions
---|---|---|---|---|---
edges | $32,927$ | $93,050$ | $39,402$ | $519,000$ | $153,540$
edge homophily | $0.05$ | $0.38$ | $0.68$ | $0.59$ | $0.84$
adjusted homophily | $-0.05$ | $0.14$ | $0.01$ | $0.09$ | $0.02$
LI | $0.11$ | $0.04$ | $0.00$ | $0.01$ | $0.00$
ECG($k=3$) edges | $67,986$ | $73,476$ | $30,000$ | $35,274$ | $146,763$
MLP-ECG edge homophily | $0.73$ | $0.66$ | $0.79$ | $0.79$ | $0.97$
MLP-ECG adjusted homophily | $0.7$ | $0.53$ | $0.33$ | $0.4$ | $0.41$
MLP-ECG LI | $0.65$ | $0.33$ | $0.16$ | $0.19$ | $0.28$
BGRL-ECG edge homophily | $0.16$ | $0.3$ | $0.68$ | $0.6$ | $0.93$
BGRL-ECG adjusted homophily | $0.06$ | $0.02$ | $0.12$ | $0.08$ | $0.01$
BGRL-ECG LI | $0.1$ | $0.03$ | $0.05$ | $0.03$ | $0.03$

##  5 Related work

Many specialised architectures have been proposed to tackle GNNs limitations
in modeling heterophilic data. H2GCN [46] proposes separation of ego and
neighbour embeddings, using higher-order neighbourhoods and combining
representations from intermediate layers. CPGNN [45] learns a compatibility
matrix to explicitly integrate information about label correlations and uses
it to modulate messages. Similarly, GGCN [43] modifies GCN through degree
corrections and signed messages, based on an insight linking heterophily and
oversmoothing. FAGCN [4] uses a self-gating mechanism to adaptively integrate
low-frequency signals, high-frequency signals and raw features and ACM-GNN
[22] extends it to enable adaptive channel mixing node-wise. GPRGNN [7] learns
Generalized PageRank weights that adjust to node label patterns. FSGNN [24]
proposes Feature Selection GNN which separates node feature aggregation from
the depth of the GNN through multiplication the node features with different
powers and transformations of the adjacency matrix and uses a softmax to
select the relevant features. GloGNN [21] leverages global nodes to aggreagte
information, while GBK-GNN [10] uses bi-kernel feature transformation.

Most relevant to ECG-GNN could be considered GeomGCN [26] and the work of
Suresh et al. [34]. The former uses network embedding methods to find
neighbouring nodes in the corresponding latent space, to be then aggregated
with the neighbours in the original graph, over which a two-level aggregation
is then performed. Similarly, [34] modifies the computation graph by computing
similarity of degree sequences for different numbers of hops. However, in both
cases, the input node features and labels are not used, making it prone to
inaccuracies in the graph structure.

It was recently pointed [28] that the standard datasets on which these models
were tested, such as Squirrel, Chameleon, Cornell, Texas and Wisconsin, had
considerable drawbacks: high number of duplicated nodes, highly imbalanced
classes and lack of diversity in setups considered. In fact, when evaluated on
their newly proposed heterophilic suite, it was noted that most specialised
architectures are outperformed by their standard counter-parts such as GCN,
SAGE, GAT and GT, with only the separation of ego and neighbour embeddings
from [46] maintaining an advantage.

##  6 Limitations and further work

We observe that our complementary graph is constructed based on two sources of
homophily: a pretrained ResNet model that relies on provided training labels,
and a pretrained self-supervised graph module, BGRL, which depends solely on
the graph structure and node features without any labels. In cases where
neither of these two approaches generates a graph with a satisfactory level of
homophily and advantageous connectivity, the complementary graph may struggle
to enhance the overall model performance, as evidenced by the relatively
smaller gains observed in the amazon-ratings dataset.

In such cases, it may be beneficial to explore additional sources for
obtaining embeddings. Furthermore, there is potential for improvements in
leveraging the complementary information, such as separately using three
distinct graphs: the original graph, the MLP-ECG graph, and the BGRL-ECG
graph. This approach might prove to be more effective in incorporating the
different types of information, rather than relying solely on the projection
of concatenated embeddings.

Finally, it is worth noting that while this method enhances the performance of
standard graph neural networks, it can also be applied to specialised
architectures specifically designed to improve performance on heterophilic
data. These two approaches are independent and can in principle be combined to
further boost a model’s capabilities. By integrating the complementary graph
construction into specialized architectures, we could leverage the benefits of
both techniques and potentially achieve even better results when dealing with
heterogeneous data. As our paper focuses on the effects of modulating the
graph structure using weak classifiers, we apply only commonly-used GNN
layers, and leave explorations of this kind to future work.

##  7 Conclusions

We present Evolving Computation Graphs for graph neural networks, ECG-GNN.
This is a two-phase method focused on improving the performance of standard
GNNs on heterophilous data. Firstly, it builds an evolved computation graph,
formed from the original input and a complementary set of edges determined by
a weak classifier. Then, the two components of this computation graph are
modelled in parallel by two GNNs processors, and projected to the same
embeddings space after each propagation layer. This simple and elegant
extension of existing graph neural networks proves to be very effective – for
four models considered on five diverse heterophilic datasets, the ECG-GNN
enhances the performance in $95\%$ of the cases.

## References

  * Abu-El-Haija et al. [2019] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan.  Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing.  In _international conference on machine learning_ , pages 21–29. PMLR, 2019.
  * Addanki et al. [2021] Ravichandra Addanki, Peter W Battaglia, David Budden, Andreea Deac, Jonathan Godwin, Thomas Keck, Wai Lok Sibon Li, Alvaro Sanchez-Gonzalez, Jacklynn Stott, Shantanu Thakoor, et al.  Large-scale graph representation learning with very deep gnns and self-supervision.  _arXiv preprint arXiv:2107.09422_ , 2021.
  * Blundell et al. [2021] Charles Blundell, Lars Buesing, Alex Davies, Petar Veličković, and Geordie Williamson.  Towards combinatorial invariance for kazhdan-lusztig polynomials.  _arXiv preprint arXiv:2111.15161_ , 2021.
  * Bo et al. [2021] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen.  Beyond low-frequency information in graph convolutional networks.  _arXiv preprint arXiv:2101.00797_ , 2021.
  * Bodnar et al. [2022] Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Liò, and Michael M Bronstein.  Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns.  _arXiv preprint arXiv:2202.04579_ , 2022.
  * Bronstein et al. [2021] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković.  Geometric deep learning: Grids, groups, graphs, geodesics, and gauges.  _arXiv preprint arXiv:2104.13478_ , 2021.
  * Chien et al. [2021] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic.  Adaptive universal generalized pagerank graph neural network.  In _International Conference on Learning Representations. https://openreview. net/forum_ , 2021.
  * Davies et al. [2021] Alex Davies, Petar Veličković, Lars Buesing, Sam Blackwell, Daniel Zheng, Nenad Tomašev, Richard Tanburn, Peter Battaglia, Charles Blundell, András Juhász, et al.  Advancing mathematics by guiding human intuition with ai.  _Nature_ , 600(7887):70–74, 2021.
  * Derrow-Pinion et al. [2021] Austin Derrow-Pinion, Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Marc Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, et al.  Eta prediction with graph neural networks in google maps.  In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, pages 3767–3776, 2021.
  * Du et al. [2022] Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang.  Gbk-gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily.  In _Proceedings of the ACM Web Conference 2022_ , pages 1550–1558, 2022.
  * Franceschi et al. [2019] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He.  Learning discrete structures for graph neural networks.  In _International conference on machine learning_ , pages 1972–1982. PMLR, 2019.
  * 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.
  * Grill et al. [2020] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent-a new approach to self-supervised learning.  _Advances in neural information processing systems_ , 33:21271–21284, 2020.
  * Hamilton et al. [2017] William L. Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  _arXiv_ , abs/1706.02216, 2017.  URL http://arxiv.org/abs/1706.02216.
  * He et al. [2022] Dongxiao He, Chundong Liang, Huixin Liu, Mingxiang Wen, Pengfei Jiao, and Zhiyong Feng.  Block modeling-guided graph convolutional neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 4022–4029, 2022.
  * Hendrycks and Gimpel [2016] Dan Hendrycks and Kevin Gimpel.  Gaussian error linear units (gelus).  _arXiv preprint arXiv:1606.08415_ , 2016.
  * Hu et al. [2021] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec.  Ogb-lsc: A large-scale challenge for machine learning on graphs.  _arXiv preprint arXiv:2103.09430_ , 2021.
  * Kazi et al. [2022] Anees Kazi, Luca Cosmo, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael M Bronstein.  Differentiable graph module (dgm) for graph convolutional networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(2):1606–1617, 2022.
  * Kipf and Welling [2016a] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv_ , abs/1609.02907, 2016a.  URL http://arxiv.org/abs/1609.02907.
  * Kipf and Welling [2016b] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016b.
  * Li et al. [2022] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian.  Finding global homophily in graph neural networks when meeting heterophily.  _arXiv preprint arXiv:2205.07308_ , 2022.
  * Luan et al. [2022] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup.  Revisiting heterophily for graph neural networks.  _arXiv preprint arXiv:2210.07606_ , 2022.
  * Ma et al. [2021] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang.  Is homophily a necessity for graph neural networks?  _arXiv preprint arXiv:2106.06134_ , 2021.
  * Maurya et al. [2022] Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata.  Simplifying approach to node classification in graph neural networks.  _Journal of Computational Science_ , 62:101695, 2022.
  * Mirhoseini et al. [2021] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al.  A graph placement methodology for fast chip design.  _Nature_ , 594(7862):207–212, 2021.
  * Pei et al. [2020] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang.  Geom-gcn: Geometric graph convolutional networks.  _arXiv preprint arXiv:2002.05287_ , 2020.
  * Platonov et al. [2022] Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova.  Characterizing graph datasets for node classification: Beyond homophily-heterophily dichotomy.  _arXiv preprint arXiv:2209.06177_ , 2022.
  * Platonov et al. [2023] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova.  A critical look at the evaluation of gnns under heterophily: are we really making progress?  _arXiv preprint arXiv:2302.11640_ , 2023.
  * Rong et al. [2020] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang.  Dropedge: Towards deep graph convolutional networks on node classification.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=Hkx1qkrKPr.
  * Rozemberczki et al. [2021] Benedek Rozemberczki, Carl Allen, and Rik Sarkar.  Multi-scale attributed node embedding.  _Journal of Complex Networks_ , 9(2):cnab014, 2021\.
  * Sen et al. [2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  _AI magazine_ , 29(3):93–93, 2008.
  * Shi et al. [2020] Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun.  Masked label prediction: Unified message passing model for semi-supervised classification.  _arXiv preprint arXiv:2009.03509_ , 2020.
  * Stokes et al. [2020] Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann, et al.  A deep learning approach to antibiotic discovery.  _Cell_ , 180(4):688–702, 2020.
  * Suresh et al. [2021] Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma.  Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns.  _arXiv preprint arXiv:2106.06586_ , 2021.
  * Tang et al. [2009] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang.  Social influence analysis in large-scale networks.  In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 807–816, 2009.
  * Thakoor et al. [2021] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko.  Large-scale representation learning on graphs via bootstrapping.  In _International Conference on Learning Representations_ , 2021.
  * Van der Maaten and Hinton [2008] Laurens Van der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  _Journal of machine learning research_ , 9(11), 2008.
  * Velickovic et al. [2017] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv_ , abs/1710.10903, 2017.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Wang et al. [2019a] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang.  Deep graph library: A graph-centric, highly-performant package for graph neural networks.  _arXiv preprint arXiv:1909.01315_ , 2019a.
  * Wang and Zhang [2022] Xiyuan Wang and Muhan Zhang.  How powerful are spectral graph neural networks.  In _International Conference on Machine Learning_ , pages 23341–23362. PMLR, 2022.
  * Wang et al. [2019b] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon.  Dynamic graph cnn for learning on point clouds.  _Acm Transactions On Graphics (tog)_ , 38(5):1–12, 2019b.
  * Yan et al. [2021] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra.  Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks.  _arXiv preprint arXiv:2102.06462_ , 2021.
  * Zaheer et al. [2017] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola.  Deep sets.  _Advances in neural information processing systems_ , 30, 2017.
  * Zhu et al. [2020a] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra.  Graph neural networks with heterophily.  _arXiv preprint arXiv:2009.13566_ , 2020a.
  * Zhu et al. [2020b] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra.  Beyond homophily in graph neural networks: Current limitations and effective designs.  _Advances in Neural Information Processing Systems_ , 33, 2020b.
  * Zhu et al. [2020c] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra.  Generalizing graph neural networks beyond homophily.  _arXiv preprint arXiv:2006.11468_ , 2020c.

##  Appendix A Training information

We used the same experimental setup as presented in Platonov et al. [28].
Results are aggregated over ten random splits of the data, with each run
taking $50\%$ of the nodes for training, $25\%$ for validation, and $25\%$ for
testing. The following hyperparameters are tuned for all models and baselines,
using the average validation performance across the splits:

  * •

Number of GNN/ResNet layers, $L\in\\{1,2,3,4,5\\}$.

  * •

The dimensionality of the GNN/ResNet’s latent embeddings,
$d\in\\{256,512,1024\\}$.

Additionally, for the ECG models only, the following hyperparameters were
swept:

  * •

Embeddings used by ECG,
$\tau\in\\{\text{MLP},\text{BGRL},\text{MLPBGRL},\text{MLP}\rightarrow\text{GNN}\\}$,
referring to:

    * MLP:

Using the embeddings from a pre-trained ResNet;

    * BGRL:

Using the embeddings from a pre-trained BGRL model;

    * MLPBGRL:

Using the normalised concatenation of the ResNet and BGRL embeddings;

    * MLP$\rightarrow$GNN:

Using the embeddings from a pre-trained MLP-ECG model of the same type.

Note that, for methods requiring access to labels (such as MLP), a separate
set of embeddings is computed for every dataset split (to avoid test data
contamination). For self-supervised methods like BGRL, no labels are used, and
hence a single set of embeddings is produced for all experiments.

  * •

The number of neighbours sampled per node, $k\in\\{3,10,20\\}$.

  * •

The DropEdge rate, $p_{de}\in\\{0.0,0.5\\}$.

The model configuration with the best-performing average validation
performance is then evaluated on the corresponding test splits, producing the
aggregated performances reported in Table 1.

The best-performing hyperparameters for each model type on each dataset are
given in Table 3. Each individual experiment has been executed on a single
NVIDIA Tesla P100 GPU, and the longest training time allocated to an
individual experiment has been six hours (on the questions dataset).

For convenience, and to assess the relative benefits of various ECG embedding
sources, we provide in Table 4 an expanded version of 1, showing the test
performance obtained by the tuned version of each ECG variant, for every
embedding type.

For additional information, the anonymised code can be found at
https://anonymous.4open.science/r/evolving_computation_graphs-97B7/.

Table 3: The best-performing hyperparameters for each GNN propagation rule in our experiments. The only experiment where the baseline model outperforms ECG is the SAGE propagation layer on amazon-ratings; hence, the hyperparameters $k$ and $p_{de}$ are irrelevant. | roman-empire | amazon-ratings | minesweeper | tolokers | questions
---|---|---|---|---|---
ResNet |  |  |  |  |
$L$ | $2$ | $1$ | $5$ | $5$ | $1$
$d$ | $512$ | $512$ | $512$ | $512$ | $512$
GCN |  |  |  |  |
$L$ | $5$ | $2$ | $4$ | $4$ | $3$
$d$ | $512$ | $512$ | $256$ | $512$ | $256$
$\tau$ | MLPBGRL | MLP$\rightarrow$GNN | MLP | MLP | BGRL
$k$ | $3$ | $3$ | $3$ | $3$ | $3$
$p_{de}$ | $0.5$ | $0.5$ | $0.5$ | $0.5$ | $0.0$
SAGE |  |  |  |  |
$L$ | $5$ | $2$ | $5$ | $4$ | $5$
$d$ | $512$ | $1024$ | $256$ | $256$ | $256$
$\tau$ | BGRL | Baseline | BGRL | BGRL | BGRL
$k$ | $10$ | — | $20$ | $20$ | $10$
$p_{de}$ | $0.5$ | — | $0.5$ | $0.5$ | $0.0$
GAT-sep |  |  |  |  |
$L$ | $5$ | $2$ | $5$ | $5$ | $4$
$d$ | $512$ | $512$ | $256$ | $256$ | $256$
$\tau$ | BGRL | MLP$\rightarrow$GNN | MLP | BGRL | BGRL
$k$ | $10$ | $3$ | $20$ | $20$ | $10$
$p_{de}$ | $0.5$ | $0.5$ | $0.5$ | $0.5$ | $0.5$
GT-sep |  |  |  |  |
$L$ | $5$ | $2$ | $5$ | $5$ | $4$
$d$ | $512$ | $512$ | $256$ | $256$ | $256$
$\tau$ | BGRL | MLP$\rightarrow$GNN | MLP | MLPBGRL | BGRL
$k$ | $20$ | $3$ | $20$ | $20$ | $10$
$p_{de}$ | $0.5$ | $0.5$ | $0.0$ | $0.0$ | $0.5$
Table 4: Detailed breakdown of model performance on the datasets proposed by Platonov et al. [28]. ResNet, GCN, SAGE, GAT-sep and GT-sep are the baselines, while all the other models are variants of ECG. Red marks the best performance on each dataset for each of the considered GNN architectures and the corresponding ECGs. Accuracy is reported for roman-empire and amazon-ratings, and ROC AUC is reported for minesweeper, tolokers, and questions. | roman-empire | amazon-ratings | minesweeper | tolokers | questions
---|---|---|---|---|---
ResNet | $65.88\pm 0.38$ | $45.90\pm 0.52$ | $50.89\pm 1.39$ | $72.95\pm 1.06$ | $70.34\pm 0.76$
GCN | $73.69\pm 0.74$ | $48.70\pm 0.63$ | $89.75\pm 0.52$ | $83.64\pm 0.67$ | $76.09\pm 1.27$
MLP-ECG-GCN | $83.55\pm 0.39$ | $50.99\pm 0.64$ | $92.63\pm 0.10$ | $84.81\pm 0.25$ | $76.25\pm 0.59$
BGRL-ECG-GCN | $80.59\pm 0.48$ | $48.99\pm 0.28$ | $92.35\pm 0.10$ | $84.25\pm 0.22$ | $77.50\pm 0.35$
MLPBGRL-ECG-GCN | $84.53\pm 0.26$ | $50.11\pm 0.60$ | $92.47\pm 0.50$ | $84.73\pm 0.23$ | $77.32\pm 0.31$
MLP->GNN-ECG-GCN | $84.39\pm 0.22$ | $51.12\pm 0.38$ | $92.56\pm 0.23$ | $84.35\pm 0.31$ | $75.16\pm 0.87$
SAGE | $85.74\pm 0.67$ | $53.63\pm 0.39$ | $93.51\pm 0.57$ | $82.43\pm 0.44$ | $76.44\pm 0.62$
MLP-ECG-SAGE | $85.82\pm 0.62$ | $53.32\pm 0.39$ | $94.10\pm 0.08$ | $82.60\pm 0.23$ | $76.13\pm 0.41$
BGRL-ECG-SAGE | $87.88\pm 0.25$ | $53.12\pm 0.32$ | $94.11\pm 0.07$ | $82.61\pm 0.29$ | $77.23\pm 0.36$
MLPBGRL-ECG-SAGE | $86.50\pm 0.34$ | $52.34\pm 0.92$ | $94.01\pm 0.07$ | $82.55\pm 0.18$ | $76.55\pm 0.33$
MLP->GNN-ECG-SAGE | $85.94\pm 0.57$ | $53.45\pm 0.27$ | $93.77\pm 0.12$ | $82.52\pm 0.22$ | $75.53\pm 0.64$
GAT-sep | $88.75\pm 0.41$ | $52.70\pm 0.62$ | $93.91\pm 0.35$ | $83.78\pm 0.43$ | $76.79\pm 0.71$
MLP-ECG-GAT-sep | $88.22\pm 0.36$ | $52.98\pm 0.30$ | $94.52\pm 0.20$ | $83.91\pm 0.32$ | $77.30\pm 0.47$
BGRL-ECG-GAT-sep | $89.62\pm 0.18$ | $52.20\pm 0.57$ | $94.24\pm 0.15$ | $84.23\pm 0.25$ | $77.38\pm 0.18$
MLPBGRL-GAT-sep | $88.73\pm 0.37$ | $51.06\pm 0.73$ | $94.39\pm 0.20$ | $84.11\pm 0.23$ | $76.97\pm 0.45$
MLP->GNN-ECG-GAT-sep | $88.04\pm 0.32$ | $53.65\pm 0.39$ | $93.97\pm 0.19$ | $83.75\pm 0.30$ | $75.61\pm 0.74$
GT-sep | $87.32\pm 0.39$ | $52.18\pm 0.80$ | $92.29\pm 0.47$ | $82.52\pm 0.92$ | $78.05\pm 0.93$
MLP-ECG-GT-sep | $88.56\pm 0.35$ | $52.68\pm 0.65$ | $93.62\pm 0.27$ | $83.65\pm 0.29$ | $77.82\pm 0.43$
BGRL-ECG-GT-sep | $89.56\pm 0.16$ | $52.37\pm 0.30$ | $93.55\pm 0.18$ | $82.97\pm 0.26$ | $78.12\pm 0.32$
MLPBGRL-GT-sep | $88.70\pm 0.30$ | $52.29\pm 0.60$ | $93.52\pm 0.25$ | $84.00\pm 0.24$ | $77.85\pm 0.45$
MLP->GNN-ECG-GT-sep | $88.62\pm 0.46$ | $53.25\pm 0.39$ | $92.69\pm 0.34$ | $83.41\pm 0.44$ | $75.50\pm 1.13$


# Sentence Similarity Learning by Lexical Decomposition and Composition

Zhiguo Wang  Haitao Mi  Abraham Ittycheriah
IBM T.J. Watson Research Center
Yorktown Heights, NY, USA
{zhigwang, hmi<EMAIL_ADDRESS>
###### Abstract

Most conventional sentence similarity methods only focus on similar parts of
two input sentences, and simply ignore the dissimilar parts, which usually
give us some clues and semantic meanings about the sentences. In this work, we
propose a model to take into account both the similarities and dissimilarities
by decomposing and composing lexical semantics over sentences. The model
represents each word as a vector, and calculates a semantic matching vector
for each word based on all words in the other sentence. Then, each word vector
is decomposed into a similar component and a dissimilar component based on the
semantic matching vector. After this, a two-channel CNN model is employed to
capture features by composing the similar and dissimilar components. Finally,
a similarity score is estimated over the composed feature vectors.
Experimental results show that our model gets the state-of-the-art performance
on the answer sentence selection task, and achieves a comparable result on the
paraphrase identification task.

##  1 Introduction

Sentence similarity is a fundamental metric to measure the degree of
likelihood between a pair of sentences. It plays an important role for a
variety of tasks in both NLP and IR communities. For example, in paraphrase
identification task, sentence similarity is used to determine whether two
sentences are paraphrase or not [Yin and Schütze (2015, He et al. (2015]. For
question answering and information retrieval tasks, sentence similarities
between query-answer pairs are used for assessing the relevance and ranking
all the candidate answers [Severyn and Moschitti (2015, Wang and Ittycheriah
(2015].

$E_{1}$ The research is [irrelevant] to sockeye.
---
$E_{2}$ The study is [not related] to salmon.
$E_{3}$ The research is relevant to salmon.
$E_{4}$ The study is relevant to sockeye, $\langle$instead of coho$\rangle$.
$E_{5}$ The study is relevant to sockeye, $\langle$rather than
flounder$\rangle$.
Table 1: Examples for sentence similarity learning. “coho” and “sockeye” are
in the salmon family, while “flounder” is not.

However, sentence similarity learning has following issues:

  1. 1.

there is a lexical gap between semantically equivalent sentences. Take the
$E_{1}$ and $E_{2}$ in Table 1 for example, they have the similar meaning but
with different lexicons.

  2. 2.

semantic similarity should be measured at different levels of granularity
(word-level, phrase-level and syntax-level). E.g., “not related” in $E_{2}$ is
an indivisible phrase when matching with “irrelevant” in $E_{1}$ (shown in
square brackets).

  3. 3.

the dissimilarity (shown in angle brackets) between two sentences is also a
significant clue [Qiu et al. (2006]. For example, by judging the dissimilar
parts, we can easily identify that $E_{3}$ and $E_{5}$ share the similar
meaning “The study is about salmon”, because “sockeye” belongs to the salmon
family, and “flounder” does not. Whereas the meaning of $E_{4}$ is quite
different from $E_{3}$, which emphasizes “The study is about red (a special
kind of) salmon”, because both “sockeye” and “coho” are in the salmon family.
How can we extract and utilize those information becomes another issue.

In order to handle the issues above, researchers have been working on sentence
similarity algorithms for a long time. To bridge the lexical gap (issue 1),
some word similarity metrics were proposed to match different but semantically
related words. Examples include knowledge-based metrics [Resnik (1995] and
corpus-based metrics [Jiang and Conrath (1997, Yin and Schütze (2015, He et
al. (2015]. To measure sentence similarity from various granularities (issue
2), researchers have explored features extracted from $n$-grams, continuous
phrases, discontinuous phrases, and parse trees [Yin and Schütze (2015, He et
al. (2015, Heilman and Smith (2010]. The third issue did not get much
attention in the past, the only related work of ?) explored the dissimilarity
between sentences in a pair for paraphrase identification task, but they
require human annotations in order to train a classifer, and their performance
is still below the state of the art.

In this paper, we propose a novel model to tackle all these challenges jointly
by decomposing and composing lexical semantics over sentences. Given a
sentence pair, the model represents each word as a low-dimensional vector
(issue 1), and calculates a semantic matching vector for each word based on
all words in the other sentence (issue 2). Then based on the semantic matching
vector, each word vector is decomposed into two components: a similar
component and a dissimilar component (issue 3). We use similar components of
all the words to represent the similar parts of the sentence pair, and
dissimilar components of every word to model the dissimilar parts explicitly.
After this, a two-channel CNN operation is performed to compose the similar
and dissimilar components into a feature vector (issues 2 and 3). Finally, the
composed feature vector is utilized to predict the sentence similarity.
Experimental results on two tasks show that our model the state-of-the-art
performance on the answer sentence selection task, and achieves a comparable
result on the paraphrase identification task.

In following parts, we start with a brief overview of our model (Section 2),
followed by the details of our end-to-end implementation (Section 3). Then we
evaluate our model on answer sentence selection and paraphrase identifications
tasks (Section 4).

##  2 Model Overview

Figure 1 shows an overview of our sentence similarity model. Given a pair of
sentences $S$ and $T$, our task is to calculate a similarity score $sim(S,T)$
in following steps:

Figure 1: Model overview.

Word Representation. Word embedding of ?) is an effective way to handle the
lexical gap issue in the sentence similarity task, as it represents each word
with a distributed vector, and words appearing in similar contexts tend to
have similar meanings [Mikolov et al. (2013]. With those pre-trained
embeddings, we transform $S$ and $T$ into sentence matrixes
$S=[s_{1},...,s_{i},...,s_{m}]$ and $T=[t_{1},...,t_{j},...,t_{n}]$, where
$s_{i}$ and $t_{j}$ are _d_ -dimension vectors of the corresponding words, and
$m$ and $n$ are sentence length of $S$ and $T$ respectively.

Semantic Matching. In order to judge the similarity between two sentences, we
need to check whether each semantic unit in one sentence is covered by the
other sentence, or vice versa. For example, in Table 1, to check whether
$E_{2}$ is a paraphrase of $E_{1}$, we need to know the single word
“irrelevant” in $E_{1}$ is matched or covered by the phrase “not related” in
$E_{2}$. In our model, we treat each word as a primitive semantic unit, and
calculate a semantic matching vector $\hat{s_{i}}$ for each word $s_{i}$ by
composing part or full word vectors in the other sentence $T$. In this way, we
can match a word $s_{i}$ to a word or phrase in $T$. Similarly, for the
reverse direction, we also calculate all semantic matching vectors
$\hat{t_{j}}$ in $T$.

$\begin{split}\hat{s_{i}}=f_{match}(s_{i},T)\hskip 28.45274pt\forall s_{i}\in
S\\\ \hat{t_{j}}=f_{match}(t_{j},S)\hskip 28.45274pt\forall t_{j}\in
T\end{split}$ (1)

We explore different $f_{match}$ functions latter in Section 3.

Decomposition. After the semantic matching phase, we have the semantic
matching vectors of $\hat{s_{i}}$ and $\hat{t_{j}}$. We interpret
$\hat{s_{i}}$ (or $\hat{t_{j}}$) as a semantic coverage of word $s_{i}$ (or
$t_{j}$) by the sentence $T$ (or $S$). However, it is not necessary that all
the semantics of $s_{i}$ (or $t_{j}$) are fully covered by $\hat{s_{i}}$ (or
$\hat{t_{j}}$). Take the $E_{1}$ and $E_{2}$ in Table 1 for example, the word
“sockeye” in $E_{1}$ is only partially matched by the word “salmon” (the
similar part) in $E_{2}$, as the full meaning of “sockeye” is “red salmon”
(the semantic meaning of “red” is the dissimilar part). Motivated by this
phenomenon, our model further decomposes word $s_{i}$ (or $t_{j}$), based on
its semantic matching vector $\hat{s_{i}}$ (or $\hat{t_{j}}$), into two
components: similar component $s_{i}^{+}$ (or $t_{j}^{+}$) and dissimilar
component $s_{i}^{-}$ (or $t_{j}^{-}$). Formally, we define the decomposition
function as:

$\begin{split}[s_{i}^{+};s_{i}^{-}]=f_{decomp}(s_{i},\hat{s_{i}})\hskip
28.45274pt\forall s_{i}\in S\\\
[t_{j}^{+};t_{j}^{-}]=f_{decomp}(t_{j},\hat{t_{j}})\hskip 28.45274pt\forall
t_{j}\in T\end{split}$ (2)

Composition. Given a similar component matrix
$S^{+}=[s_{1}^{+},...,s_{m}^{+}]$ (or $T^{+}=[t_{1}^{+},...,t_{n}^{+}]$) and a
dissimilar component matrix $S^{-}=[s_{1}^{-},...,s_{m}^{-}]$ (or
$T^{-}=[t_{1}^{-},...,t_{n}^{-}]$), our goal in this step is how to utilize
those information. Besides the suggestion from ?) that the significance of the
dissimilar parts alone between two sentences has a great effect of their
similarity, we also think that the dissimilar and similar components have
strong connections. For example, in Table 1, if we only look at the dissimilar
or similar part alone, it is hard to judge which one between $E_{4}$ and
$E_{5}$ is more similar to $E_{3}$. We can easily identify that $E_{5}$ is
more similar to $E_{3}$, when we consider both the similar and dissimilar
parts. Therefore, our model composes the similar component matrix and
dissimilar component matrix into a feature vector $\vec{S}$ (or $\vec{T}$)
with the composition function:

$\begin{split}\vec{S}=f_{comp}(S^{+},S^{-})\\\
\vec{T}=f_{comp}(T^{+},T^{-})\end{split}$ (3)

Similarity assessing. In the final stage, we concatenate the two feature
vectors ($\vec{S}$ and $\vec{T}$) and predict the final similarity score:

$sim(S,T)=f_{sim}(\vec{S},\vec{T})$ (4)

##  3 An End-to-End Implementation

Section 2 gives us a glance of our model. In this section, we describe details
of each phase.

###  3.1 Semantic Matching Functions

This subsection describes our specifications for the semantic matching
function $f_{match}$ in Eq. (1). The goal of $f_{match}$ is to generate a
semantic matching vector $\hat{s_{i}}$ for $s_{i}$ by composing the vectors
from $T$.

For a sentence pair $S$ and $T$, we first calculate a similarity matrix
$A_{m\times n}$, where each element $a_{i,j}\in A_{m\times n}$ computes the
cosine similarity between words $s_{i}$ and $t_{j}$ as

$a_{i,j}=\frac{s_{i}^{T}t_{j}}{\|s_{i}\|\cdot\|t_{j}\|}\hskip
28.45274pt\forall s_{i}\in S,\forall t_{j}\in T.$ (5)

Then, we define three different semantic matching functions over $A_{m\times
n}$:

$f_{match}(s_{i},T)=\begin{cases}\frac{\sum_{j=0}^{n}a_{i,j}t_{j}}{\sum_{j=0}^{n}a_{i,j}}&\emph{global}\\\
\frac{\sum_{j=k-w}^{k+w}a_{i,j}t_{j}}{\sum_{j=k-w}^{k+w}a_{i,j}}&\emph{local-w}\\\
t_{k}&\emph{max}\\\ \end{cases}$ (6)

where $k=\operatornamewithlimits{argmax}_{j}a_{i,j}$. The idea of the _global_
function is to consider all word vectors $t_{j}$ in $T$. A semantic matching
vector $\hat{s_{i}}$ is a weighted sum vector of all words $t_{j}$ in $T$,
where each weight is the normalized word similarity $a_{i,j}$. The _max_
function moves to the other extreme. It generates the semantic matching vector
by selecting the most similar word vector $t_{k}$ from $T$. The _local-w_
function takes a compromise between _global_ and _max_ , where $w$ indicates
the size of the window to consider centered at $k$ (the most similar word
position). So the semantic matching vector is a weighted average vector from
$t_{k-w}$ to $t_{k+w}$.

###  3.2 Decomposition Functions

This subsection describes the implementations for the decomposition function
$f_{decomp}$ in Eq. (2). The intention of $f_{decomp}$ is to decompose a word
vector $s_{j}$ based on its semantic matching vector $\hat{s_{j}}$ into a
similar component $s_{i}^{+}$ and a dissimilar component $s_{i}^{-}$, where
$s_{i}^{+}$ indicates the semantics of $s_{i}$ covered by $\hat{s_{i}}$ and
$s_{i}^{-}$ indicates the uncovered part. We implement three types of
decomposition function: _rigid_ , _linear_ and _orthogonal_.

The _rigid_ decomposition only adapts to the _max_ version of $f_{match}$.
First, it detects whether there is an exactly matched word in the other
sentence, or $s_{i}$ equal to $\hat{s_{i}}$. If yes, the vector $s_{i}$ is
dispatched to the similar component $s_{i}^{+}$, and the dissimilar component
is assigned with a zero vector 0. Otherwise, the vector $s_{i}$ is assigned to
the dissimilar component $s_{i}^{-}$. Eq. (7) gives the formal definition:

$\begin{split}[s_{i}^{+}=s_{i};\ s_{i}^{-}=\textbf{0}]\hskip 28.45274pt&if\
s_{i}=\hat{s_{i}}\\\ [s_{i}^{+}=\textbf{0};\ s_{i}^{-}=s_{i}]\hskip
28.45274pt&otherwise\\\ \end{split}$ (7)

The motivation for the _linear_ decomposition is that the more similar between
$s_{i}$ and $\hat{s_{i}}$, the higher proportion of $s_{i}$ should be assigned
to the similar component. First, we calculate the cosine similarity $\alpha$
between $s_{i}$ and $\hat{s_{i}}$. Then, we decompose $s_{i}$ linearly based
on $\alpha$. Eq. (8) gives the corresponding definition:

$\begin{split}&\alpha=\frac{s_{i}^{T}\hat{s_{i}}}{\|s_{i}\|\cdot\|\hat{s_{i}}\|}\\\
&s_{i}^{+}=\alpha s_{i}\\\ &s_{i}^{-}=(1-\alpha)s_{i}\\\ \end{split}$ (8)

The _orthogonal_ decomposition is to decompose a vector in the geometric
space. Based on the semantic matching vector $\hat{s_{i}}$, our model
decomposes $s_{i}$ into a parallel component and a perpendicular component.
Then, the parallel component is viewed as the similar component $s_{i}^{+}$,
and perpendicular component is taken as the dissimilar component $s_{i}^{-}$.
Eq. (9) gives the concrete definitions.

$\begin{split}&s_{i}^{+}=\frac{s_{i}\cdot\hat{s_{i}}}{\hat{s_{i}}\cdot\hat{s_{i}}}\hat{s_{i}}\hskip
28.45274ptparallel\\\ &s_{i}^{-}=s_{i}-s_{i}^{+}\hskip
28.45274ptperpendicular\\\ \end{split}$ (9)

###  3.3 Composition Functions

The aim of the composition function $f_{comp}$ in Eq. (3) is to extract
features from both the similar component matrix and the dissimilar component
matrix. We also want to acquire similarities and dissimilarities of various
granularity during the composition phase. Inspired from ?), we utilize a two-
channel convolutional neural networks (CNN) and design filters based on
various order of $n$-grams, e.g., unigram, bigram and trigram.

The CNN model involves two sequential operations: _convolution_ and _max-
pooling_. For the _convolution_ operation, we define a list of filters
{$w_{o}$}. The shape of each filter is $d\times h$, where $d$ is the dimension
of word vectors and $h$ is the window size. Each filter is applied to two
patches (a window size $h$ of vectors) from both similar and dissimilar
channels, and generates a feature. Eq. (10) expresses this process.

$c_{o,i}=f(w_{o}\ast S^{+}_{[i:i+h]}+w_{o}\ast S^{-}_{[i:i+h]}+b_{o})$ (10)

where the operation $A\ast B$ sums up all elements in $B$ with the
corresponding weights in $A$, $S^{+}_{[i:i+h]}$ and $S^{-}_{[i:i+h]}$ indicate
the patches from $S^{+}$ and $S^{-}$, $b_{o}$ is a bias term and $f$ is a non-
linear function (we use _tanh_ in this work). We apply this filter to all
possible patches, and produce a series of features
$\vec{c_{o}}=[c_{o,1},c_{o,2},...,c_{o,O}]$. The number of features in
$\vec{c_{o}}$ depends on the shape of the filter $w_{o}$ and the length of the
input sentence. To deal with variable feature size, we perform a _max-pooling_
operation over $\vec{c_{o}}$ by selecting the maximum value $c_{o}=max\
\vec{c_{o}}$. Therefore, after these two operations, each filter generates
only one feature. We define several filters by varying the window size and the
initial values. Eventually, a vector of features is captured by composing the
two component matrixes, and the feature dimension is equal to the number of
filters.

###  3.4 Similarity Assessment Function

The similarity assessment function $f_{sim}$ in Eq. (4) predicts a similarity
score by taking two feature vectors as input. We employ a linear function to
sum up all the features and apply a _sigmoid_ function to constrain the
similarity within the range [0, 1].

###  3.5 Training

We train our sentence similariy model by maximizing the likelihood on a
training set. Each training instance in the training set is represented as a
triple ($S_{i}$, $T_{i}$, $L_{i}$), where $S_{i}$ and $T_{i}$ are a pair of
sentences, and $L_{i}\in\\{0,1\\}$ indicates the similarity between them. We
assign $L_{i}=1$ if $T_{i}$ is a paraphrase of $S_{i}$ for the paraphrase
identification task, or $T_{i}$ is a correct answer for $S_{i}$ for the answer
sentence selection task. Otherwise, we assign $L_{i}=0$. We implement the
mathematical expressions with Theano [Bastien et al. (2012] and use Adam
[Kingma and Ba (2014] for optimization.

##  4 Experiment

###  4.1 Experimental Setting

We evaluate our model on two tasks: answer sentence selection and paraphrase
identification. The answer sentence selection task is to rank a list of
candidate answers based on their similarities to a question sentence, and the
performance is measured by mean average precision (MAP) and mean reciprocal
rank (MRR). We experiment on two datasets: _QASent_ and _WikiQA_. Table 2
summarises the statistics of the two datasets, where _QASent_ [Wang et al.
(2007] was created from the TREC QA track, and _WikiQA_ [Yang et al. (2015] is
constructed from real queries of Bing and Wikipedia. The paraphrase
identification task is to detect whether two sentences are paraphrases based
on the similarity between them. The metrics include the accuracy and the
positive class $F_{1}$ score. We experiment on the Microsoft Research
Paraphrase corpus (MSRP) [Dolan et al. (2004], which includes 2753 true and
1323 false instances in the training set, and 1147 true and 578 false
instances in the test set. We build a development set by randomly selecting
100 true and 100 false instances from the training set. In all experiments, we
set the size of word vector dimension as $d=$300, and pre-train the vectors
with the _word2vec_ toolkit [Mikolov et al. (2013] on the English Gigaword
(LDC2011T07).

| Set | Questions | QA Pairs
---|---|---|---
QASent | train | 1,229 | 53,417
dev | 65 | 1,117
test | 68 | 1,442
WikiQA | train | 2,118 | 20,360
dev | 296 | 2,733
test | 633 | 6,165
Table 2: Statistics of answer sentence selection data sets.

###  4.2 Model Properties

There are several alternative options in our model, e.g., the semantic
matching functions, the decomposition operations, and the filter types. The
choice of these options may affect the final performance. In this subsection,
we present some experiments to demonstrate the properties of our model, and
find a good configuration that we use to evaluate our final model. All the
experiments in this subsection were performed on the _QASent_ dataset and
evaluated on the development set.

First, we evaluated the effectiveness of various semantic matching functions.
We switched the semantic matching functions among {_max_ , _global_ , _local-
l_}, where $l\in$ {1, 2, 3, 4}, and fixed the other options as: the _linear_
decomposition, the filter types including {unigram, bigram, trigram}, and 500
filters for each type. Figure 2 presents the results. We found that the _max_
function worked better than the _global_ function on both MAP and MRR. By
increasing the window size, the _local-l_ function acquired progressive
improvements when the window size is smaller than 4. But after we enlarged the
window size to 4, the performance dropped. The _local-3_ function worked
better than the _max_ function in term of the MAP, and also got a comparable
MRR. Therefore, we use the _local-3_ function in the following experiments.

Figure 2: Influence of semantic matching functions.

Second, we studied the effect of various decomposition operations. We varied
the decomposition operation among {_rigid_ , _linear_ , _orthogonal_}, and
kept the other options unchanged. Figure 3 shows the performance. We found
that the _rigid_ operation got the worst result. This is reasonable, because
the _rigid_ operation decomposes word vectors by exactly matching words. The
_orthogonal_ operation got a similar MAP as the _linear_ operation, and it
worked better in term of MRR. Therefore, we choose the _orthogonal_ operation
in the following experiments.

Figure 3: Influence of decomposition functions.

Third, we tested the influence of various filter types. We constructed 5
groups of filters: _win-1_ contains only the unigram filters, _win-2_ contains
both unigram and bigram filters, _win-3_ contains all the filters in _win-2_
plus trigram filters, _win-4_ extends filters in _win-3_ with 4-gram filters,
and _win-5_ adds 5-gram filters into _win-4_. We generate 500 filters for each
filter type (with different initial values). Experimental results are shown in
Figure 4. At the beginning, adding higher-order ngram filters was helpful for
the performance. The performance reached to the peak, when we used the _win-3_
filters. After that, adding more complex filters decreased the performance.
Therefore, the trigram is the best granularity for our model. In the following
experiments, we utilize filter types in _win-3_.

Figure 4: Influence of filter types in the composition function.

###  4.3 Comparing with State-of-the-art Models

In this subsection, we evaluated our model on the test sets of _QASent_ ,
_WikiQA_ and _MSRP_.

_QASent_ dataset. Table 3 presents the performances of the state-of-the-art
systems and our model, where the performances were evaluated with the standard
trec_eval-8.0 script 111http://trec.nist.gov/trec_eval/. Given a pair of
sentences, ?) employed a CNN model to compose each sentence into a vector
separately, and joined the two sentence vectors to compute the sentence
similarity. Because only the sentence-level granularity was used, the
performance is much lower (the second row of Table 3). After adding some word
overlap features between the two sentences, the performance was improved
significantly (the third row of Table 3). Therefore, the lower-level
granularity is an indispensable factor for a good performance. ?) conducted
word alignment for a sentence pair based on word vectors, and measured the
sentence similarity based on a couple of word alignment features. They got a
slightly better performance (the fourth row of Table 3), which indicates that
the vector representation for words is helpful to bridging the lexical gap
problem. Our model makes use of all these useful factors and also considers
the dissimilarities of a sentence pair. We can see that our model got a
significantly better performance than all the other work (the last row).

Models | MAP | MRR
---|---|---
|  ?)
---
(CNN only)
0.6709 | 0.7280
|  ?)
---
(CNN + sparse features)
0.7459 | 0.8078
?) | 0.7460 | 0.8200
This work | 0.7714 | 0.8447
Table 3: Experimental results on the QASent dataset from the state-of-the-art
models and our proposed model.

_WikiQA_ dataset. Table 4 presents the results of our model and several state-
of-the-art models. ?) constructed the dataset and reimplemented several
baseline models. The best performance (shown at the second row of Table 4) was
acquired by a bigram CNN model combining with the word overlap features. ?)
models the sentence similarity by enriching LSTMs with a latent stochastic
attention mechanism. The corresponding performance is given at the third row
of Table 4. ?) introduced the attention mechanism into the CNN model, and
captured the best performance (the fourth row of Table 4). The semantic
matching phase in our model is similar to the attention mechanism. But
different from the previous models, our model utilizes both the similarity and
dissimilarity simultaneously. The last row of Table 4 shows that our model is
more effective than the other models.

Models | MAP | MRR
---|---|---
|  ?)
---
(2-gram CNN)
0.6520 | 0.6652
|  ?)
---
(Attention-based LSTM)
0.6886 | 0.7069
|  ?)
---
(Attention-based CNN)
0.6921 | 0.7108
This work | 0.7058 | 0.7226
Table 4: Experimental results on the WikiQA dataset from the state-of-the-art
models and our proposed model.

_MSRP_ dataset. Table 5 summarized the results from our model and several
state-of-the-art models. ?) employed a CNN model to learn sentence
representations on multiple level of granularity and modeled interaction
features at each level for a pair of sentences. They obtained their best
performance by pretraining the model on a language modeling task (the 3rd row
of Table 5). However, their model heavily depends on the pretraining strategy.
Without pretraining, they got a much worse performance (the second row of
Table 5). ?) proposed a similar model to ?). Similarly, they also used a CNN
model to extract features at multiple levels of granularity. Differently, they
utilized some extra annotated resources, e.g., embeddings from part-of-speech
(POS) tags and PARAGRAM vectors trained from the Paraphrase Database
[Ganitkevitch et al. (2013]. Their model outperformed ?) without the need of
pretraining (the sixth row of Table 5). However, the performance was reduced
after removing the extra resources (the fourth and fifth rows of Table 5). ?)
applied their attention-based CNN model on this dataset. By adding a couple of
sparse features and using a layerwise training strategy, they got a pretty
good performance. Comparing to these neural network based models, our model
obtained a comparable performance (the last row of Table 5) without using any
sparse features, extra annotated resources and specific training strategies.
However, the best performance so far on this dataset is obtained by ?). In
their model, they just utilized several hand-crafted features in a Support
Vector Machine (SVM) model. Therefore, the deep learning methods still have a
long way to go for this task.

Models | Acc | F1
---|---|---
|  ?)
---
(without pretraining)
72.5 | 81.4
|  ?)
---
(with pretraining)
78.4 | 84.6
|  ?)
---
(without POS embeddings)
77.8 | N/A
|  ?)
---
(without Para. embeddings)
77.3 | N/A
|  ?)
---
(POS and Para. embeddings)
78.6 | 84.7
|  ?)
---
(with sparse features)
78.9 | 84.8
?) | 80.4 | 86.0
This work | 78.4 | 84.7
Table 5: Experimental results for paraphrase identification on MSRP corpus.

##  5 Related Work

The semantic matching functions in subsection 3.1 are inspired from the
attention-based neural machine translation [Bahdanau et al. (2014, Luong et
al. (2015]. However, most of the previous work using the attention mechanism
in only LSTM models. Whereas our model introduces the attention mechanism into
the CNN model. A similar work is the attention-based CNN model proposed by ?).
They first build an attention matrix for a sentence pair, and then directly
take the attention matrix as a new channel of the CNN model. Differently, our
model uses the attention matrix (or similarity matrix) to decompose the
original sentence matrix into a similar component matrix and a dissimilar
component matrix, and then feeds these two matrixes into a two-channel CNN
model. The model can then focus much on the interactions between similar and
dissimilar parts of a sentence pair.

##  6 Conclusion

In this work, we proposed a model to assess sentence similarity by decomposing
and composing lexical semantics. To bridge the lexical gap problem, our model
represents each word with its context vector. To extract features from both
the similarity and dissimilarity of a sentence pair, we designed several
methods to decompose the word vector into a similar component and a dissimilar
component. To extract features at multiple levels of granularity, we employed
a two-channel CNN model and equipped it with multiple types of ngram filters.
Experimental results show that our model is quite effective on both the answer
sentence selection task and the paraphrase identification task .

## Acknowledgments

## References

  * [Bahdanau et al. (2014]  Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  2014\.  Neural machine translation by jointly learning to align and translate.  arXiv preprint arXiv:1409.0473.
  * [Bastien et al. (2012]  Frédéric Bastien, Pascal Lamblin, Razvan Pascanu, James Bergstra, Ian J. Goodfellow, Arnaud Bergeron, Nicolas Bouchard, and Yoshua Bengio.  2012\.  Theano: new features and speed improvements.  Deep Learning and Unsupervised Feature Learning NIPS 2012 Workshop.
  * [Dolan et al. (2004]  Bill Dolan, Chris Quirk, and Chris Brockett.  2004\.  Unsupervised construction of large paraphrase corpora: Exploiting massively parallel news sources.  In Proceedings of the 20th international conference on Computational Linguistics, page 350. Association for Computational Linguistics.
  * [Ganitkevitch et al. (2013]  Juri Ganitkevitch, Benjamin Van Durme, and Chris Callison-Burch.  2013\.  Ppdb: The paraphrase database.  In HLT-NAACL, pages 758–764.
  * [He et al. (2015]  Hua He, Kevin Gimpel, and Jimmy Lin.  2015\.  Multi-perspective sentence similarity modeling with convolutional neural networks.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1576–1586.
  * [Heilman and Smith (2010]  Michael Heilman and Noah A Smith.  2010\.  Tree edit models for recognizing textual entailments, paraphrases, and answers to questions.  In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 1011–1019. Association for Computational Linguistics.
  * [Ji and Eisenstein (2013]  Yangfeng Ji and Jacob Eisenstein.  2013\.  Discriminative improvements to distributional sentence similarity.  In EMNLP, pages 891–896.
  * [Jiang and Conrath (1997]  Jay J Jiang and David W Conrath.  1997\.  Semantic similarity based on corpus statistics and lexical taxonomy.  arXiv preprint cmp-lg/9709008.
  * [Kim (2014]  Yoon Kim.  2014\.  Convolutional neural networks for sentence classification.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, pages 1746–1751.
  * [Kingma and Ba (2014]  Diederik Kingma and Jimmy Ba.  2014\.  Adam: A method for stochastic optimization.  In International Conference on Learning Representation (ICLR).
  * [Luong et al. (2015]  Minh-Thang Luong, Hieu Pham, and Christopher D Manning.  2015\.  Effective approaches to attention-based neural machine translation.  arXiv preprint arXiv:1508.04025.
  * [Miao et al. (2015]  Yishu Miao, Lei Yu, and Phil Blunsom.  2015\.  Neural variational inference for text processing.  arXiv preprint arXiv:1511.06038.
  * [Mikolov et al. (2013]  Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  2013\.  Efficient estimation of word representations in vector space.  arXiv preprint arXiv:1301.3781.
  * [Qiu et al. (2006]  Long Qiu, Min-Yen Kan, and Tat-Seng Chua.  2006\.  Paraphrase recognition via dissimilarity significance classification.  In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, pages 18–26. Association for Computational Linguistics.
  * [Resnik (1995]  Philip Resnik.  1995\.  Using information content to evaluate semantic similarity in a taxonomy.  arXiv preprint cmp-lg/9511007.
  * [Severyn and Moschitti (2015]  Aliaksei Severyn and Alessandro Moschitti.  2015\.  Learning to rank short text pairs with convolutional deep neural networks.  In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 373–382. ACM.
  * [Wang and Ittycheriah (2015]  Zhiguo Wang and Abraham Ittycheriah.  2015\.  Faq-based question answering via word alignment.  arXiv preprint arXiv:1507.02628.
  * [Wang et al. (2007]  Mengqiu Wang, Noah A Smith, and Teruko Mitamura.  2007\.  What is the jeopardy model? a quasi-synchronous grammar for qa.  In EMNLP-CoNLL, volume 7, pages 22–32.
  * [Yang et al. (2015]  Yi Yang, Wen-tau Yih, and Christopher Meek.  2015\.  Wikiqa: A challenge dataset for open-domain question answering.  In Proceedings of the Conference on Empirical Methods in Natural Language Processing.
  * [Yin and Schütze (2015]  Wenpeng Yin and Hinrich Schütze.  2015\.  Convolutional neural network for paraphrase identification.  In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 901–911.
  * [Yin et al. (2015]  Wenpeng Yin, Hinrich Schütze, Bing Xiang, and Bowen Zhou.  2015\.  Abcnn: Attention-based convolutional neural network for modeling sentence pairs.