# Refined Edge Usage of Graph Neural Networks for
Edge Prediction

Jiarui Jin1, Yangkun Wang2, Weinan Zhang1, Quan Gan3, Xiang Song3,
Yong Yu1, Zheng Zhang3, David Wipf3 1Shanghai Jiao Tong University,
2University of California San Diego, 3Amazon Web Service  jinjiarui97,
wnzhang<EMAIL_ADDRESS><EMAIL_ADDRESS>quagan, xiangsx, zhaz,
<EMAIL_ADDRESS>
###### Abstract.

Graph Neural Networks (GNNs), originally proposed for node classification,
have also motivated many recent works on edge prediction (a.k.a., link
prediction). However, existing methods lack of elaborate design regarding the
distinctions between two tasks that have been frequently overlooked: (i) edges
only constitute _the topology_ in the node classification task but can be used
as both _the topology and the supervisions_ (i.e., labels) in the edge
prediction task; (ii) the node classification makes prediction over each
_individual node_ , while the edge prediction is determinated by each _pair of
nodes_. To this end, we propose a novel edge prediction paradigm named Edge-
aware Message PassIng neuRal nEtworks (EMPIRE). Concretely, we first introduce
an edge splitting technique to specify use of each edge where each edge is
solely used as either the topology or the supervision (named as topology edge
or supervision edge). We then develop a new message passing mechanism that
generates the messages to source nodes (through topology edges) being aware of
target nodes (through supervision edges). In order to emphasize the
differences between pairs connected by supervision edges and pairs
unconnected, we further weight the messages to highlight the relative ones
that can reflect the differences. In addition, we design a novel negative
node-pair sampling trick that efficiently samples “hard” negative instances in
the supervision instances, and can significantly improve the performance.
Experimental results verify that the proposed method can significantly
outperform existing state-of-the-art models regarding the edge prediction task
on multiple homogeneous and heterogeneous graph datasets.

Edge-aware Message Passing; Edge Prediction; Edge Usage

††conference: Conference; Date; Location

##  1\. Introduction

Graphs (e.g., social networks) as a common structure for complex relational
data, have been recently involved in various machine learning tasks and
received increasing attention. Among these tasks, node classification is one
of the most prominent examples. Due to the remarkable success of graph
convolution networks (GCNs) (Kipf and Welling, 2016a), many advanced graph
neural networks (GNNs) (e.g., graph attention networks (GAT) (Veličković et
al., 2018), SAGE (so called GraphSAGE) (Hamilton et al., 2017)) designs have
been proposed regarding the node classification problem.

Most of prevailing solutions of the edge prediction task are developed based
on GNNs. These methods usually are directly extended from existing GNN
frameworks by plugging the representation vectors of node pairs into a pre-
defined scoring function. Unfortunately, there are significant differences
between node classification task and edge prediction task, which are
overlooked, or even not aware of, by these methods. Here, we summarize two
main differences:

First, given a graph, for the node classification task, the supervisions
(i.e., labels) are on the nodes, while the topology (i.e., graph structure) is
free of the supervision and thus remains the same (and complete) during both
training and test phrases. In contrast, for the edge prediction task, the
supervisions are on the node pairs, and thus the edges are used both as the
topology and the supervisions. Therefore, if directly applying the GNN models
to the edge prediction task, it would simultaneously use the edges as both the
topology and supervisions (i.e., using the whole graph as input and outputting
the predictions over all the edges in the graph). We argue that this setting
is problematic, as it would allow the model to observe the existence (i.e.,
the ground-truth) of the edges to predict, namely the labels are (indirectly)
fed into the model during training. As a consequence, the GNN models are
likely to _over-fit the training graph_ , resulting in the low
generalizability to the test graph.

Second, the classification of each node is solely determinated by the
properties of the node; while the prediction over each edge depends on the
properties of the node pair. We note that conventional message passing
mechanisms, originally proposed for the node classification, are designed to
aggregate the neighborhood of individual nodes. In this regard, directly
applying them to the edge prediction task would make _the messages passing to
the source nodes invariant to the target nodes_. In other words, the message
generation is invariant to the edges to predict.

In this paper, we propose a novel edge prediction paradigm called Edge-aware
Message PassIng neuRal nEtworks (EMPIRE), which tailors the message passing
mechanism introduced in (Gilmer et al., 2017) regarding the aforementioned
differences to make it a good fit for the edge prediction task.

To achieve this, we first refine the usage of the edges in the graph by
splitting edges into two subsets: topology and supervision edges. The former
and latter ones are used as topology and supervisions respectively at each
split (as illustrated in Figure 1). For each round, we randomly sample the
same number of unconnected node pairs as the negative supervision instances.
Then, given the topology edges, our edge prediction models are trained by
recovering the existences of those supervision edges.

On the basis of the splitted edges, we argue that it is essential to make the
messages to source nodes (through topology edges) being aware of target nodes
(through supervision edges). Take Figure 1 as an example. Suppose Item C is a
fiction movie, then when predicting the edge existence between User C and Item
C, the message from Type C to User C should be highly weighted. In the light
of this, we design to use target nodes to attend the messages to source nodes.

We also notice that after each split, there are three types of node pairs:
ones connected by the topology edges, ones connected by the supervision edges,
and unconnected ones; and obviously the likelihoods of the edge existence over
these three types are different and listed in the descending order. Taking
Figure 1 as an example, User B favors Item A, and is likely to favor Item B,
but is unlikely to favor Item C. Hence, when passing the message from Type A
and Type B to User B, we expect it to highlight the differences between Item B
and Item C. For instance, if Item B is a romantic movie and Item C is a war
movie, then we need to assign more attention on the message from Type A than
Type B. To this end, we propose to highlight the relative messages that can
reflect the differences between node pairs connected by supervision edges and
unconnected node pairs.

Figure 1. An illustrated example of the motivation of our target-aware message
passing mechanism: (i) message from the neighbor node Type C to the source
node User C should be weighted by the target node Item C; (ii) information
that can distinguish node pair connected by supervision edges $\langle$User B,
Item B$\rangle$ and unconnected node pair $\langle$User B, Item C$\rangle$
should be highlighted in the message passing to source node User B.

In addition, we notice that the negative instances in the supervision
instances play an important role in the final edge prediction, as they can
significantly influence our message generation. Inspired by (Zhan et al.,
2021) which reveals that “hard” negative samples would improve the
effectiveness and stability of the information retrieval models, we regard the
unconnected node pairs satisfying the common-neighbor heuristics as “hard”
negative samples in the edge prediction task. The underlying reason is that as
the non-parametric common neighbor method (Adamic and Adar, 2003) is a strong
baseline regarding the edge prediction task, it would be hard to distinguish
unconnected node pairs with the common neighbors and connected node pairs.
However, as discussed in (Singh et al., 2021), finding all these node pairs is
much time-consuming. To address this issue, we propose a new negative node-
pair sampling trick, which allows us to efficiently sample/retrieve these node
pairs as the negative samples.

In summary, the contributions of this paper are three-fold:

  * •

We reveal that edges simultaneously used as topology and supervisions would
encourage GNN models to over-fit the inputted training graph, and thus hold
low generalizability to test graph.

  * •

We develop an edge splitting technique and design a novel target-aware message
passing mechanism based on the splitted edges to make messages conditioned on
the source-target node pairs.

  * •

We present a new negative node-pair sampling trick that efficiently samples
“hard” node pairs satisfying the common-neighbor heuristics to construct the
supervision edges.

Our empirical evaluation demonstrates that EMPIRE can be seamlessly adapted to
multiple GNN architectures and consistently lead to significant improvement in
edge prediction accuracy.

##  2\. Preliminaries

We begin by describing the formation of edge prediction and introducing the
associated notations.

###### Definition 0.

_(GNN-based Edge Prediction Framework)_ Considering a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$,***For simplicity, we omit the
relation (i.e., the type of edges) in this paper, since it is straightforward
to extend our proposed techniques across GNN backbones (e.g., GCN, GAT) into
the corresponding relational GNN backbones (e.g., RGCN (Schlichtkrull et al.,
2018), RGAT (Busbridge et al., 2019)) modelling the relational data. where
$\mathcal{V}=\\{v_{1},\ldots,v_{N}\\}$ is the set of nodes and $\mathcal{E}$
is the set of edges connecting these nodes and assuming that each node $v_{n}$
has a feature vector $\bm{x}_{n}$, the $n$-th row of the feature matrix
$\bm{X}$, we can build an arbitrary GNN model (denoted as
$\mathtt{GNN}(\cdot)$) to encode the embedding vector for each node. In other
words, we have $\bm{H}=\mathtt{GNN}(\mathcal{G},\bm{X})$, where $\bm{H}$
denotes the embedding matrix. We directly plug the learned node embeddings
into a score function (denoted as $\mathtt{S}(\cdot)$) to obtain the final
prediction of the edge existence of each pair nodes $\langle s,t\rangle$
(denoted as $\widehat{y}_{st}$), which can be formulated as

(1)
$\widehat{y}_{st}=\mathtt{S}(\mathtt{GNN}(\mathcal{G},\bm{X})_{s},\mathtt{GNN}(\mathcal{G},\bm{X})_{t}).$

One widely adopted loss is a log loss $L$ defined as

(2) $L=-\sum_{\langle
v_{s},v_{t}\rangle\in\mathcal{V}\times\mathcal{V}}\left(y_{st}\log\widehat{y}_{st}+(1-y_{st})\log(1-\widehat{y}_{st})\right),$

where $y_{st}$ is the label for node pair $\langle v_{s},v_{t}\rangle$.

To be more specific regarding how GNN models work, we briefly review
conventional message passing mechanism (Gilmer et al., 2017). The message
passing runs multiple rounds on graph to update the node embeddings, where the
embedding vector $\bm{h}^{(l+1)}_{s}$ of node $s$ in iteration $l+1$ is
updated by

(3)
$\bm{h}^{(l+1)}_{s}=\mathtt{U}(\bm{h}^{(l)}_{s},\\{\bm{m}^{(l)}_{s\leftarrow
w}|w\in\mathcal{N}_{\mathcal{E}}(s)\\}),$

where $\mathtt{U}(\cdot)$ denotes the node embedding update function,
$\bm{m}^{(l)}_{s\leftarrow w}$ denotes the message passing from $v_{w}$ to
$v_{s}$, generated by a message generation function.
$\mathcal{N}_{\mathcal{E}}(s)$ denotes the set of neighbor nodes connecting to
$v_{s}$ via the edges in $\mathcal{E}$, and the initial embedding is set as
$\bm{h}^{(0)}_{s}=\bm{x}_{s}$. The above framework has derived many popular
variants in terms of different designs of $\mathtt{U}(\cdot)$ and
$\mathtt{M}(\cdot)$ such as GCN (Kipf and Welling, 2016a), SAGE (Hamilton et
al., 2017), GAT (Veličković et al., 2018), GIN (Xu et al., 2018). We encourage
the readers to refer to (Gilmer et al., 2017) for detailed background.

Figure 2. An illustrated example of the proposed framework EMPIRE for the edge
prediction task. Given the original graph, as shown in (a), we can first
remove the test edges to form the training graph, as shown in (b). Then, to
align the training and test processes of the GNN models, we propose to split
the training edges into the topology edges and supervision edges, as shown in
(c), where each edge is used as either topology or supervision. On the basis
of the splitted edges, we develop a novel target-aware passing mechanism to
make the messages to the source nodes being aware of the target nodes, as
shown in (d). We further highlight the relative messages that can reflect the
differences between the node pairs connected by the supervision edges and
those unconnected node pairs, as shown in (e). In addition, we also design a
new negative node-pair sampling trick that can efficiently sample the node
pairs satisfying the common-neighbor heuristics to construct the negative
instances in the supervision edges, as shown in (f).

Based on the above framework, there are several key technical details that are
frequently overlooked, and yet nonetheless can play a vital role in achieving
satisfactory performance:

  * •

_Whether the settings of training and test processes of the edge prediction
task are aligned or not._ Given an original graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, a principle data preprocessing
procedure would first remove the test edges $\mathcal{E}_{\mathtt{te}}$ from
the graph is to construct a training graph
$\mathcal{G}_{\mathtt{tr}}=(\mathcal{V},\mathcal{E}_{\mathtt{tr}})$ (and
$\mathcal{E}=\mathcal{E}_{\mathtt{tr}}\cup\mathcal{E}_{\mathtt{te}}$). Then,
the GNN models are trained to recover $\mathcal{E}_{\mathtt{tr}}$ given
$\mathcal{G}_{\mathtt{tr}}$ (a graph containing the edges in
$\mathcal{E}_{\mathtt{tr}}$); while the GNN models are evaluated to recover
$\mathcal{E}_{\mathtt{te}}$ given $\mathcal{G}_{\mathtt{tr}}$ (a graph NOT
containing the edges in $\mathcal{E}_{\mathtt{te}}$). This misalignment would
encourage the models to over-fit the training graph, since the training graph
has already contained all the information to predict; and thus it would make
the models convey the low generalizability to the test graph.

  * •

_Whether the message passing mechanism and the prediction objective are
aligned or not._ As shown in Eq. (3), the conventional message passing
mechanism passes and aggregates the neighborhood information of each node
$v_{s}$ to update the embedding vector of $v_{s}$; while as Eq. (1) shows, the
prediction objective is each pair of nodes $\langle v_{s},v_{t}\rangle$.
Therefore, previous message passing mechanism focuses on the individual node;
however, the prediction objectives require it to optimize over the node pairs.

##  3\. The EMPIRE Framework

###  3.1. Edge Splitting

To begin with, we note that the main difference between the training and test
processes of the GNN models is that during the test process, each edge is used
as either topology or supervision: edges in $\mathcal{E}_{\mathtt{tr}}$ are
used as topology and edges in $\mathcal{E}_{\mathtt{te}}$ are used as
supervision; while during the training process, each edge (in
$\mathcal{E}_{\mathtt{tr}}$) is simultaneously used as topology and
supervision.

In order to align the settings of training and testing processes, we propose
to specify the use of each training edge by splitting the training edges into
two sets, named topology edges and supervision edges. As illustrated in Figure
2(c), the topology edges (denoted as $\mathcal{E}_{\mathtt{in}}$, colored in
purple) are used as the inputs to build the graph topology (i.e., to run the
message passing), while the supervision edges (denoted as
$\mathcal{E}_{\mathtt{out}}$, colored in green) are used as the outputs to
supervise the GNN models (i.e., to update the parameters). After that, we
would further add several randomly sampled unconnected node pairs into the
supervision instances to balance the positive and negative instances, as shown
in Figure 2(b).

While practice, we typically sample the splits by randomly assigning each edge
to $\mathcal{E}_{\mathtt{out}}$ with some probability $\lambda\in(0,1)$, and
the rest edges are assigned to $\mathcal{E}_{\mathtt{in}}$. We empirically
investigate the impact of $\lambda$ in Section 5.3.

###  3.2. Target-aware Message Passing

As discussed in Section 2, in the context of conventional message passing
mechanism, the representations of source and target nodes are solely
determinated by their previous embedding vectors and neighbor nodes, but not
being aware of each other. We argue that as the labels of the edge prediction
task are on node pairs instead of nodes; and thus independently considering
individual node in the message generation would lead to a sub-optimal
solution.

Formally, for each source node $v_{s}$, if following conventional message
passing mechanism, then the message generated from its neighbor node $v_{w}$
to $v_{s}$ can be formulated as $\bm{m}^{(l)}_{s\leftarrow
w}=\mathtt{M}(\bm{h}^{(l)}_{s},\bm{h}^{(l)}_{w})$.

In order to make the messages to the source node $v_{s}$ being aware of the
target node $v_{t}$, one straightforward approach is to generate the message
following the formulation $\bm{m}^{(l)}_{s\leftarrow
w|t}=\mathtt{M}(\bm{h}^{(l)}_{s},$ $\bm{h}^{(l)}_{w},\bm{h}^{(l)}_{t})$.
However, there are often a large number of target nodes for each source node,
and thus it is computationally consuming or even infeasible to generate the
messages for each node pair $\langle v_{s},v_{t}\rangle$.

To make it scalable, when generating the message from neighbor node $v_{w}$ to
the source node $v_{s}$, we propose to model the influence of all the target
nodes (i.e., $v_{t}$s) together as

(4) $\bm{m}^{(l)}_{s\leftarrow
w}=\mathtt{M}(\bm{h}^{(l)}_{s},\bm{h}^{(l)}_{w},\\{\bm{h}^{(l)}_{t}|v_{t}\in\mathcal{N}_{\mathcal{E}_{\mathtt{out}}}(s)\\}),$

where $\mathcal{N}_{\mathcal{E}_{\mathtt{out}}}(s)$ represents a set of the
target nodes connecting to $v_{s}$ by the supervision edges. With the
generated message $\bm{m}^{(l)}_{s\leftarrow w}$, we then can update the
representation vector $\bm{h}^{(l+1)}_{s}$ of each source node following

(5)
$\bm{h}^{(l+1)}_{s}=\mathtt{U}(\bm{h}^{(l)}_{s},\\{\bm{m}^{(l)}_{s\leftarrow
w}|v_{w}\in\mathcal{N}_{\mathcal{E}_{\mathtt{in}}}(s)\\}),$

where $\mathcal{N}_{\mathcal{E}_{\mathtt{in}}}(s)$ denotes a set of neighbor
nodes connecting to $v_{s}$ by the topology edges.

Notice that the designs of $\mathtt{M}(\cdot)$ also vary for different GNN
architectures. For clarity, we examplify how to seamlessly adopt our approach
(i.e., Eqs. (4) and (5)) into GNN models in the context of GAT model. In this
case, $\mathtt{M}(\cdot)$ is implemented as

(6) $\bm{m}^{(l)}_{s\leftarrow w}=\alpha^{(l)}_{s\leftarrow
w}\bm{h}^{(l)}_{w},$

where $\alpha^{(l)}_{s\leftarrow w}$ is a learnable attention weight to make
the message dependent on the affinity between nodes $v_{s}$ and $v_{w}$, i.e.,
passing more messages from the neighbor nodes similar to the source node.
$\alpha^{(l)}_{s\leftarrow w}$ is computed as

(7) $\alpha^{(l)}_{s\leftarrow
w}=\frac{\exp\left(\text{LeakyReLU}(\bm{w}^{\top}[\bm{h}^{(l)}_{s}\|\bm{h}^{(l)}_{w}])\right)}{\sum_{v_{o}\in\mathcal{N}_{\mathcal{E}_{\mathtt{in}}}(s)}\exp\left(\text{LeakyReLU}(\bm{w}^{\top}[\bm{h}^{(l)}_{s}\|\bm{h}^{(l)}_{o}])\right)},$

where $\|$ represents the concatenation operation, and $\bm{w}$ is trainable
vector. These messages are later used to refine the representation of the
source node $v_{s}$ by $\mathtt{U}(\cdot)$ (in Eq. (5)) implemented as

(8)
$\bm{h}^{(l+1)}_{s}=\sigma\left(\bm{W}^{(l)}\bm{h}^{(l)}_{s}+\sum_{v_{w}\in\mathcal{N}_{\mathcal{E}_{\mathtt{in}}}(s)}\bm{m}^{(l)}_{s\leftarrow
w}\right),$

where $\sigma$ is an activation function, and $\bm{W}$ is the trainable
matrix.

Based on the layer-wise propagation rule of GAT introduced above, to empower
the GAT with the proposed technique, we modify its $\mathtt{M}(\cdot)$ (i.e.,
Eq. (6)) following Eq. (4) as

(9) $\bm{m}^{(l)}_{s\leftarrow w}=\alpha^{(l)}_{s\leftarrow
w}\left(\bm{h}^{(l)}_{w}+\sum_{v_{t}\in\mathcal{N}_{\mathcal{E}_{\mathtt{out}}}(s)}\beta^{(l)}_{w|t}\bm{h}^{(l)}_{w}\right),$

where $\beta^{(l)}_{w|t}$ is another learnable attention weight to mke the
message aware of the target node $v_{t}$, e.g., passing more messages from the
neighbor nodes related to $v_{t}$. $\beta^{(l)}_{w|t}$ is calculated as

(10)
$\beta^{(l)}_{w|t}=\frac{\exp\left(\text{LeakyReLU}(\bm{w}^{\top}[\bm{h}^{(l)}_{t}\|\bm{h}^{(l)}_{w}])\right)}{\sum_{v_{o}\in\mathcal{N}_{\mathcal{E}_{\mathtt{out}}}(s)}\exp\left(\text{LeakyReLU}(\bm{w}^{\top}[\bm{h}^{(l)}_{w}\|\bm{h}^{(l)}_{o}])\right)}.$

We then feed $\bm{m}^{(l)}_{s\leftarrow w}$ computed by Eq. (9) into Eq. (8)
to complete the calculation of the representation vector of $v_{s}$ in
iteration $l+1$.

0: training graph
$\mathcal{G}_{\mathtt{tr}}=(\mathcal{V},\mathcal{E}_{\mathtt{tr}})$, node
feature $\bm{X}$

1: repeat

2: Obtain $\mathcal{E}_{\mathtt{in}},\mathcal{E}_{\mathtt{out}}$ by randomly
splitting $\mathcal{E}_{\mathtt{tr}}$

3: Construct $\mathcal{D}_{\mathtt{out}}$ using Algorithm 3

4: Modify message passing function $\mathtt{M}(\cdot)$ using Eq. (9)

5: Modify update function $\mathtt{U}(\cdot)$ using Eq. (13)

6: Produce $\\{\widehat{y}_{st}|\langle
v_{s},v_{t}\rangle\in\mathcal{D}_{\mathtt{out}}\\}$ using Eq. (1)

7: Update parameters by minimizing $L$ over $\mathcal{D}_{\mathtt{out}}$ in
Eq. (2)

8: until convergence

Algorithm 1 EMPIRE

###  3.3. Relative Message Highlighting

The above subsection describes the modification on the message generation
function to let the messages be aware of the target nodes. We notice that
after each split, there are three types of node pairs with different
likelihoods of the edge existence: ones connected by the topology edges, ones
connected by the supervision edges, and unconnected ones. Inspired by recent
success of contrastive learning (Velickovic et al., 2019; Zhu et al., 2021;
Qiu et al., 2020) on graphs, we consider the unconnected node pairs as the
baseline node pairs. In this regard, the relative messages that can reflect
the differences between the node pairs connected by the supervision edges and
baseline node pairs is super informative, as it is the basis of the prediction
of the edge existence.

To achieve this, we modify the update function (i.e., Eq. (5)) as

(11)
$\bm{h}^{(l+1)}_{s}=\mathtt{U}(\bm{h}^{(l)}_{s},\\{\bm{m}^{(l)}_{s\leftarrow
w},\gamma^{(l)}_{s\leftarrow
w}|v_{w}\in\mathcal{N}_{\mathcal{E}_{\mathtt{in}}}(s)\\}),$

where $\gamma^{(l)}_{s\leftarrow w}$ is a learnable attention weight to
measure the relative information in message $\bm{m}^{(l)}_{s\leftarrow w}$.
$\gamma^{(l)}_{s\leftarrow w}$ is computed as

(12) $\gamma^{(l)}_{s\leftarrow
w}=\frac{\sum_{t\in\mathcal{N}_{\mathcal{E}_{\mathtt{out}}}(s)}\exp\left(\text{LeakyReLU}(\bm{w}^{\top}[\bm{h}^{(l)}_{t}\|\bm{m}^{(l)}_{s\leftarrow
w}])\right)}{\sum_{t^{\prime}\in\mathcal{B}(s)}\exp\left(\text{LeakyReLU}(\bm{w}^{\top}[\bm{h}^{(l)}_{t^{\prime}}\|\bm{m}^{(l)}_{s\leftarrow
w}])\right)},$

where
$\mathcal{B}(s)\subseteq\mathcal{V}/\mathcal{N}_{\mathcal{E}_{\mathtt{in}}\cup\mathcal{E}_{\mathtt{out}}}(s)$
is a set of randomly sampled nodes that are unconnected to the source node
$v_{s}$, and $|\mathcal{B}(s)|=|\mathcal{N}_{\mathcal{E}_{\mathtt{out}}}(s)|$.
From Eq. (12), when the message is “close” to the representation vectors of
the target node and “distant” to the representation vectors of unconnected
nodes, it will receive high attention.

While taking Eq. (11) into practice, we can modify Eq. (8) as

(13)
$\bm{h}^{(l+1)}_{s}=\sigma\left(\bm{W}^{(l)}\bm{h}^{(l)}_{s}+\sum_{v_{w}\in\mathcal{N}_{\mathcal{E}_{\mathtt{in}}}(s)}\gamma^{(l)}_{s\leftarrow
w}\bm{m}^{(l)}_{s\leftarrow w}\right).$

###  3.4. Efficient Negative Node-Pair Sampling

As stated in Section 3.1, as Figure 2(b) depicts, EMPIRE organizes the
training graph into three sets, where the topology instances and positive
supervision instances are obtained from the random split; while the negative
supervision instances are built by random sampling. In this subsection, we
develop a new negative sampling trick regarding the generation of these
negative instances.

Many recent studies especially those in the information retrieval fields such
as (Ying et al., 2018; Zhan et al., 2021) reveal that introducing “hard”
negative instances can improve the stability and performance of the model.
There are two questions to answer for EMPIRE such that it can benefit from the
“hard” negative instances: (i) what are the hard negative instances? (ii) how
to efficiently sample these instances?

Regarding the edge prediction task, we define the hard negative instances as
node pairs that are somewhat likely to be connected, but not connected in the
training graph. Hence, a direct approach is to apply an edge prediction model
over all unconnected node pairs, and select several node pairs with the high
prediction scores as the hard negative instances. However, one obvious
drawback of this approach is unacceptable computation costs.

To address this issue, we propose to generate the hard negative instances by
using the non-parametric common-neighbor heuristic (Adamic and Adar, 2003). As
shown in the edge prediction
leaderboard†††https://ogb.stanford.edu/docs/leader_linkprop/ on Open Graph
Benchmark (OGB), the common-neighbor heuristic can be regarded as a strong
edge prediction model. We further develop a new retrieval algorithm to find
all the node pairs containing the common neighbors with $O(|\mathcal{V}|^{2})$
computations. Considering that it might be unacceptable in some real-world
cases, we present an uniform sampling version to sample $n_{\mathtt{cn}}$ node
pairs with $O(|\mathcal{V}|+|\mathcal{E}_{\mathtt{in}}|+n_{\mathtt{cn}})$
computations. Refer to Appendix A for the pseudo-code and analysis of these
algorithms.

###  3.5. Model Analysis

We summarize the proposed EMPIRE paradigm in Algorithm 1, and provide the
analysis of time complexity and extensions to heterogeneous graphs as follows.

Time Complexity. From Algorithm 1, we can see that there are four operations
brought by EMPIRE: randomly splitting edges in line 1 costs
$O(|\mathcal{E}_{\mathtt{tr}}|)$ computations, and building the supervision
instances using efficient negative node-pair sampling costs
$O(|\mathcal{V}|+(1+\lambda)|\mathcal{E}_{\mathtt{tr}}|)$. Let
$C_{\mathtt{GNN}}$ denote the time complexity of $\mathtt{GNN}(\cdot)$. As
stated in (Veličković et al., 2018), GAT is computationally efficient, where
the time complexity of a single GAT over $F^{\prime}$ features would be
expressed as
$C_{\mathtt{GNN}}=O(|\mathcal{V}|F^{\prime}F+|\mathcal{E}_{\mathtt{tr}}|F^{\prime})$
where $F$ is the number of input features. Therefore, the time complexity of
the target-aware message passing mechanism in line 3 is
$O(|\mathcal{E}_{\mathtt{in}}||\mathcal{E}_{\mathtt{out}}|F^{\prime})$, and
the time complexity of the relative message highlighting in line 4 is
$O(|\mathcal{V}|F^{\prime}F+|\mathcal{E}_{\mathtt{out}}|F^{\prime})$. The
overall complexity is
$O(|\mathcal{V}|F^{\prime}F+|\mathcal{E}_{\mathtt{in}}||\mathcal{E}_{\mathtt{out}}|F^{\prime})$.

Extension to Heterogeneous Graphs. Although we introduce EMPIRE in the context
of homogeneous graphs, it is straightforward to extend it to some existing
heterogeneous GNN models such as HAN (Wang et al., 2019b) and RGCN
(Schlichtkrull et al., 2018) on heterogeneous graphs, because all these
methods are developed based on the message passing mechanism. Taking HAN as an
example, we provide the detailed descriptions of how to adopt EMPIRE to it in
Appendix B.

We also provide the discussion on the deployment feasibility in Appendix D.

Table 1.  Results of performance gain from different components of EMPIRE
incorporating with various GNN models on the homogeneous graph datasets in
terms of AUC. * indicates $p<0.001$ in significance tests compared to Origin.

Models | Techniques | USAir | NS | PB | Yeast | C.ele | Power | Router | E.coli | Arxiv | Facebook
---|---|---|---|---|---|---|---|---|---|---|---
GCN | Origin | 0.9065 | 0.9354 | 0.8963 | 0.9142 | 0.8014 | 0.8973 | 0.9034 | 0.9425 | 0.9467 | 0.9348
EMPIRE${}^{-}_{\mathtt{split}}$ | 0.9248∗ | 0.9543∗ | 0.9177∗ | 0.9292∗ | 0.8220∗ | 0.9112∗ | 0.9278∗ | 0.9572∗ | 0.9533∗ | 0.9505∗
EMPIRE${}^{-}_{\mathtt{+message}}$ | 0.9403 | 0.9632 | 0.9244 | .0.9330 | 0.8376 | 0.9283 | 0.9346 | 0.9687 | 0.9689 | 0.9628
EMPIRE${}^{-}_{\mathtt{+relative}}$ | 0.9462 | 0.9705 | 0.9336 | 0.9413 | 0.8654 | 0.9402 | 0.9583 | 0.9781 | 0.9746 | 0.9726
EMPIRE | 0.9506 | 0.9797 | 0.9459 | 0.9542 | 0.8683 | 0.9420 | 0.9714 | 0.9808 | 0.9806 | 0.9747
GIN | Origin | 0.9465 | 0.9385 | 0.8911 | 0.9195 | 0.8227 | 0.9027 | 0.9104 | 0.9456 | 0.9512 | 0.9462
EMPIRE${}^{-}_{\mathtt{split}}$ | 0.9650∗ | 0.9556∗ | 0.9098∗ | 0.9285∗ | 0.8343∗ | 0.9178∗ | 0.9275∗ | 0.9576∗ | 0.9656∗ | 0.9584∗
EMPIRE${}^{-}_{\mathtt{+message}}$ | 0.9716 | 0.9642 | 0.9177 | 0.9274 | 0.8405 | 0.9209 | 0.9306 | 0.9606 | 0.9687 | 0.9613
EMPIRE${}^{-}_{\mathtt{+relative}}$ | 0.9757 | 0.9645 | 0.9173 | 0.9283 | 0.8458 | 0.9207 | 0.9497 | 0.9688 | 0.9697 | 0.9614
EMPIRE | 0.9765 | 0.9708 | 0.9156 | 0.9309 | 0.8467 | 0.9226 | 0.9527 | 0.9721 | 0.9702 | 0.9620
GAT | Origin | 0.9369 | 0.9476 | 0.9254 | 0.9395 | 0.8313 | 0.9103 | 0.9340 | 0.9422 | 0.9544 | 0.9604
EMPIRE${}^{-}_{\mathtt{split}}$ | 0.9463∗ | 0.9568∗ | 0.9371∗ | 0.9462∗ | 0.8420∗ | 0.9164∗ | 0.9475∗ | 0.9587∗ | 0.9668∗ | 0.9666∗
EMPIRE${}^{-}_{\mathtt{+message}}$ | 0.9597 | 0.9645 | 0.9420 | 0.9577 | 0.8482 | 0.9233 | 0.9503 | 0.9605 | 0.9689 | 0.9716
EMPIRE${}^{-}_{\mathtt{+relative}}$ | 0.9576 | 0.9730 | 0.9512 | 0.9671 | 0.8441 | 0.9286 | 0.9587 | 0.9690 | 0.9697 | 0.9755
EMPIRE | 0.9635 | 0.9783 | 0.9560 | 0.9685 | 0.8452 | 0.9325 | 0.9630 | 0.9727 | 0.9698 | 0.9762
SAGE | Origin | 0.9278 | 0.9346 | 0.9178 | 0.9235 | 0.8143 | 0.8943 | 0.9477 | 0.9436 | 0.9465 | 0.9456
EMPIRE${}^{-}_{\mathtt{split}}$ | 0.9349∗ | 0.9423∗ | 0.9211∗ | 0.9378∗ | 0.8288∗ | 0.9024∗ | 0.9520∗ | 0.9488∗ | 0.9573∗ | 0.9502∗
EMPIRE${}^{-}_{\mathtt{+message}}$ | 0.9466 | 0.9478 | 0.9554 | 0.9428 | 0.8345 | 0.9112 | 0.9557 | 0.9601 | 0.9608 | 0.9535
EMPIRE${}^{-}_{\mathtt{+relative}}$ | 0.9487 | 0.9515 | 0.9633 | 0.9478 | 0.8403 | 0.9156 | 0.9638 | 0.9692 | 0.9682 | 0.9626
EMPIRE | 0.9538 | 0.9545 | 0.9678 | 0.9492 | 0.8458 | 0.9185 | 0.9697 | 0.9715 | 0.9697 | 0.9678

##  4\. Related Work

GNN Models for Edge Prediction. As GNN models have become the prevailing tool
to encode the graph structure, there are an influx of works studying applying
GNN models for the edge prediction task, which can be roughly categorized into
two folds. One line of research (Kipf and Welling, 2016b) implicitly assumes
that a GNN model holding a strong expressive power on the node representations
can lead to the good link representations by combining the pair-wise node
representations. For example, RGCN (Schlichtkrull et al., 2018) modifies GCN
(Kipf and Welling, 2016a) to encode the heterogeneity of edges (i.e.,
relations). Based on the assumption, one can adopt various GNN models (Kipf
and Welling, 2016a; Hamilton et al., 2017; Veličković et al., 2018; Xu et al.,
2018; Wang et al., 2021; You et al., 2019) original proposed for the node
classification task to make the predictions of the edge existence by
introducing a scoring function (also known as similarity metrics (Adamic and
Adar, 2003)). The other line of research (Zhang and Chen, 2018; Zhang et al.,
2020) implicitly assumes that subgraphs that include and do not include the
edge are discriminated by the representations learned by GNN models. For
instance, SEAL (Zhang and Chen, 2018) formulates the edge prediction problems
as the graph classification problems, where the models are required to
classify the subgraphs including or not including the edge connecting the
given node pairs. Besides these applications regarding GNN algorithms, there
is an influx of literature (He et al., 2020; Wang et al., 2019a, b; Ying et
al., 2018; Zhang and Chen, 2019; Jin et al., 2020; Zhang et al., 2019; Hu et
al., 2020a) suggesting that mining the graph structure can offer auxiliary
information for recommendations. As most of the relational data (e.g., social
network) in the real-world is heterogeneous, these methods pay much attention
on leveraging the heterogeneity of the nodes and relations by modifying GNN
architectures or introducing metapath (Sun et al., 2011). For example, HAN
(Wang et al., 2019b) adopts a hierarchical attention mechanism to capture
node-level and semantic level information, which might be regarded as a
heterogeneous version of GAT. All the above previous methods focus on
elaborate architectures and algorithms; however, there is limited literature
investigating how to adjust GNN models to make them fit the edge prediction
task. We argue that it is essential, as GNN models especially those following
the message passing neural network framework (Gilmer et al., 2017) are
originally designed for the node classification task instead of the edge
prediction task. In this paper, we propose a novel EMPIRE paradigm to fill the
blank, which can be seamlessly incorporate with the multiple GNN models and
bring significant improvements.

Simple Enhancements for GNN Models. There are several prior works (Wang et
al., 2021; Rong et al., 2019) showing that some simple modifications on GNN
architectures and label usage can significantly improve the node
classification accuracy. However, there are limited literature (Singh et al.,
2021; Zhang et al., 2020) investigating some simple enhances regarding the
edge prediction problem. From this perspective, our paper proposes some easy-
to-implement refinements for apply GNN models regarding the edge prediction
task, which is the first one, to our knowledge.

##  5\. Experiment

###  5.1. Datasets and Experimental Flow

Dataset Description. To evaluate the performance of our proposed techniques,
we conduct experiments on the edge prediction datasets used in (Zhang and
Chen, 2018): USAir (Vladimir Batagelj, 2006) is a network of US Air lines with
332 nodes and 2,126 edges. NS (Newman, 2006) is a collaboration network of
researchers in network science with 1,589 nodes and 2,742 edges. PB (Ackland
et al., 2005) is a network of US political blogs with 1,222 nodes and 16,714
edges. Yeast (Von Mering et al., 2002) is a protein-protein interaction
network in yeast with 2,375 nodes and 11,693 edges. C.ele (Watts and Strogatz,
1998) is a network of C.elegans with 297 nodes and 2,148 edges. Power (Watts
and Strogatz, 1998) is an electrical grid of western US with 4,941 nodes and
6,594 edges. Rounter (Spring et al., 2002) is a router-level Internet with
5,022 nodes and 6,258 edges. E.coli (Zhang et al., 2018) is a pairwise
reaction network of metabolites in E.coli with 1,805 nodes and 14,660 edges.
Arxiv (Leskovec and Krevl, 2015) is an academic network with 18,722 nodes and
198,110 edges. Facebook (Leskovec and Krevl, 2015) is a social network with
4,029 nodes and 88,324 edges.

We also employ four large-scale edge prediction benchmark datasets on OGB (Hu
et al., 2020b): ogbl-ppa (Hu et al., 2020b) is a protein-protein association
graph with 576,289 nodes and 42,463,862 edges, where the task is to predict
biologically meaningful associations between proteins. ogbl-collab (Hu et al.,
2020b) is an author collaboration graph with 235,868 nodes and 2,464,517
edges, where the task is to predict future collaborations. ogbl-ddi (Hu et
al., 2020b) is a drug-drug interaction network with 4,267 nodes and 2,402,800
edges, where each edge represents an interaction between drugs. ogbl-citation2
(Hu et al., 2020b) is a paper citation network with 2,927,963 nodes and
30,561,187 edges, where the task is to predict the missing citations.

Table 2. Results of performance gain from different components of EMPIRE on
the large homogeneous graph datasets in terms of AUC, ACC, F1. * in
EMPIRE${}^{-}_{\mathtt{split}}$ indicates $p<0.001$ in significance tests
compared to Origin.

Models | Techniques | ogb-ppa | ogb-collab | ogb-ddi | ogb-citation2
---|---|---|---|---|---
AUC | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1
GCN | Origin | 0.9532 | 0.9325 | 0.9363 | 0.9609 | 0.9422 | 0.9431 | 0.9046 | 0.8887 | 0.8908 | 0.9542 | 0.9360 | 0.9382
EMPIRE${}^{-}_{\mathtt{split}}$ | 0.9586∗ | 0.9387∗ | 0.9398∗ | 0.9634∗ | 0.9446∗ | 0.9557∗ | 0.9178∗ | 0.8904∗ | 0.8934∗ | 0.9591∗ | 0.9473∗ | 0.9494∗
EMPIRE${}^{-}_{\mathtt{+message}}$ | 0.9597 | 0.9459 | 0.9411 | 0.9655 | 0.9469 | 0.9590 | 0.9195 | 0.8927 | 0.8956 | 0.9660 | 0.9579 | 0.9518
EMPIRE${}^{-}_{\mathtt{+relative}}$ | 0.9619 | 0.9550 | 0.9532 | 0.9678 | 0.9497 | 0.9638 | 0.9284 | 0.8986 | 0.8994 | 0.9675 | 0.9635 | 0.9646
EMPIRE | 0.9632 | 0.9564 | 0.9519 | 0.9763 | 0.9525 | 0.9681 | 0.9301 | 0.9004 | 0.9062 | 0.9725 | 0.9755 | 0.9763
GAT | Origin | 0.9213 | 0.8980 | 0.9031 | 0.9532 | 0.9351 | 0.9387 | 0.9246 | 0.9053 | 0.9074 | 0.9478 | 0.9254 | 0.9276
EMPIRE${}^{-}_{\mathtt{split}}$ | 0.9341∗ | 0.9153∗ | 0.9187∗ | 0.9566∗ | 0.9387∗ | 0.9402∗ | 0.9358∗ | 0.9167∗ | 0.9196∗ | 0.9586∗ | 0.9361∗ | 0.9385∗
EMPIRE${}^{-}_{\mathtt{+message}}$ | 0.9394 | 0.9196 | 0.9205 | 0.9592 | 0.9424 | 0.9488 | 0.9426 | 0.9218 | 0.9212 | 0.9619 | 0.9478 | 0.9493
EMPIRE${}^{-}_{\mathtt{+relative}}$ | 0.9428 | 0.9227 | 0.9296 | 0.9617 | 0.9493 | 0.9489 | 0.9472 | 0.9286 | 0.9277 | 0.9623 | 0.9484 | 0.9506
EMPIRE | 0.9477 | 0.9292 | 0.9332 | 0.9626 | 0.9519 | 0.9545 | 0.9501 | 0.9324 | 0.9355 | 0.9712 | 0.9532 | 0.9556
SAGE | Origin | 0.9083 | 0.8843 | 0.8832 | 0.9612 | 0.9453 | 0.9465 | 0.9103 | 0.8943 | 0.8965 | 0.9321 | 0.9134 | 0.9171
EMPIRE${}^{-}_{\mathtt{split}}$ | 0.9224∗ | 0.8927∗ | 0.9001∗ | 0.9665∗ | 0.9477∗ | 0.9489∗ | 0.9242∗ | 0.9075∗ | 0.9092∗ | 0.9444∗ | 0.9256∗ | 0.9290∗
EMPIRE${}^{-}_{\mathtt{+message}}$ | 0.9252 | 0.8961 | 0.9030 | 0.9694 | 0.9498 | 0.9507 | 0.9324 | 0.9113 | 0.9131 | 0.9492 | 0.9283 | 0.9305
EMPIRE${}^{-}_{\mathtt{+relative}}$ | 0.9295 | 0.8980 | 0.9040 | 0.9711 | 0.9601 | 0.9523 | 0.9353 | 0.9196 | 0.9190 | 0.9548 | 0.9359 | 0.9394
EMPIRE | 0.9316 | 0.8987 | 0.9196 | 0.9734 | 0.9624 | 0.9532 | 0.9379 | 0.9214 | 0.9214 | 0.9573 | 0.9385 | 0.9417

Besides the above homogeneous graph datasets, we include four heterogeneous
graph benchmark datasets: LastFM (Hu et al., 2018) is an audio recommendation
network with 2,101 user nodes, 18,746 artist nodes, 12,648 tag nodes, 92,834
user-artist edges, 25,434 user-user edges, 186,479 user-tag edges. Amazon (Ni
et al., 2019) is an e-commerce recommendation network with 6,170 user nodes,
2,753 item nodes, 3,857 view nodes, 334 brand nodes, 146,230 user-item edges,
5,694 item-view edges, 2,753 item-brand edges, 37,958 user-user edges. Yelp
(Hu et al., 2018) is a business-based social network with 16,239 user nodes,
14,284 business nodes, 47 city nodes, 511 genre nodes, 198,397 user-business
edges, 158,590 user-user edges, 76,875 user-city edges, 14,267 business-city
edges, 40,009 business-genre edges. Douban (Zheng et al., 2017) is a book
recommendation network with 13,024 user nodes, 22,347 book nodes, 2,936 group
nodes, 10,805 author nodes, 1,815 publisher nodes, 598,420 user-book edges,
169,150 user-user edges, 1,189,271 user-group edges, 21,907 book-author edges,
21,773 book-publisher edges.

We provide the detailed descriptions of data preprocessing and hyperparameter
settings in Appendix C.2. We evaluate the performance in terms of Area Under
ROC Curve (AUC), Accuracy (ACC), F1 score (F1). The threshold for positive
prediction is set as 0.5.

Baseline Description. We note that EMPIRE can be regarded as plug-in
techniques that can be seamlessly incorporate into various GNN models on both
homogeneous and heterogeneous graph datasets. To be more specific, for
homogeneous GNN models, we introduce the following GNN models as the basic
model: GCN (Kipf and Welling, 2016a), GIN (Xu et al., 2018), GAT (Veličković
et al., 2018), SAGE (Hamilton et al., 2017). For heterogeneous graph datasets,
we use the following GNN models as the basic model: RGCN (Schlichtkrull et
al., 2018), HAN (Wang et al., 2019b). We provide the detailed descriptions of
these baselines in Appendix C.1.

Noting that the edge splitting technique is the basis of other techniques, to
evaluate the performance gain from each component of EMPIRE, we construct
following variants of EMPIRE:

  * •

Origin directly uses the basic GNN models.

  * •

EMPIRE${}^{-}_{\mathtt{split}}$ applies the edge splitting technique
(introduced in Section 3.1) to the basic GNN models.

  * •

EMPIRE${}^{-}_{\mathtt{+message}}$ employs the target-aware message passing
mechanism (introduced in Section 3.2) to EMPIRE${}^{-}_{\mathtt{split}}$.

  * •

EMPIRE${}^{-}_{\mathtt{+relative}}$ combines the relative message highlighting
technique (introduced in Section 3.3) to EMPIRE${}^{-}_{\mathtt{+message}}$.

  * •

EMPIRE applies the efficient negative node-pair sampling trick (introduced in
Section 3.4) to EMPIRE${}^{-}_{\mathtt{+relative}}$, namely it includes all
the proposed techniques.

Figure 3. Comparison of performance of EMPIRE using GAT as the basic GNN model
under different split rate $\lambda$ on Arxiv dataset (depicted in (a)) and
ogb-collab dataset (depicted in (b)) in terms of AUC and ACC. Figure 4.
Comparison of performance of EMPIRE using GAT as the basic GNN model under
different number of GNN layers on Arxiv dataset (depicted in (a)) and ogb-
collab dataset (depicted in (b)) in terms of AUC and ACC. Table 3. Results of
performance gain from different components of EMPIRE on the heterogeneous
graph datasets in terms of AUC, ACC, F1. * in EMPIRE${}^{-}_{\mathtt{split}}$
indicates $p<0.001$ in significance tests compared to Origin.

Models | Techniques | LastFM | Amazon | Yelp | Douban
---|---|---|---|---|---
AUC | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1
RGCN | Origin | 0.8532 | 0.8382 | 0.8354 | 0.8120 | 0.7403 | 0.7322 | 0.8879 | 0.8411 | 0.8330 | 0.9203 | 0.8412 | 0.8267
EMPIRE${}^{-}_{\mathtt{split}}$ | 0.8624∗ | 0.8447∗ | 0.8412∗ | 0.8125∗ | 0.7496∗ | 0.7346∗ | 0.8935∗ | 0.8504∗ | 0.8434∗ | 0.9351∗ | 0.8573∗ | 0.8394∗
EMPIRE${}^{-}_{\mathtt{+message}}$ | 0.8697 | 0.8459 | 0.8511 | 0.8155 | 0.7529 | 0.7490 | 0.9095 | 0.8527 | 0.8456 | 0.9380 | 0.8589 | 0.8428
EMPIRE${}^{-}_{\mathtt{+relative}}$ | 0.8719 | 0.8550 | 0.8552 | 0.8208 | 0.7557 | 0.7512 | 0.9144 | 0.8616 | 0.8494 | 0.9455 | 0.8645 | 0.8496
EMPIRE | 0.8732 | 0.8564 | 0.8591 | 0.8263 | 0.7575 | 0.7581 | 0.9181 | 0.8684 | 0.8562 | 0.9565 | 0.8695 | 0.8533
HAN | Origin | 0.8915 | 0.8336 | 0.8296 | 0.9156 | 0.8488 | 0.8427 | 0.8487 | 0.7682 | 0.7572 | 0.9243 | 0.8500 | 0.8451
EMPIRE${}^{-}_{\mathtt{split}}$ | 0.9086∗ | 0.8417∗ | 0.8358∗ | 0.9234∗ | 0.8525∗ | 0.8496∗ | 0.8527∗ | 0.7753∗ | 0.7625∗ | 0.9286∗ | 0.8586∗ | 0.8488∗
EMPIRE${}^{-}_{\mathtt{+message}}$ | 0.9127 | 0.8464 | 0.8395 | 0.9264 | 0.8587 | 0.8568 | 0.8616 | 0.7812 | 0.7723 | 0.9313 | 0.8603 | 0.8556
EMPIRE${}^{-}_{\mathtt{+relative}}$ | 0.9183 | 0.8523 | 0.8435 | 0.9310 | 0.8621 | 0.8598 | 0.8677 | 0.7865 | 0.7786 | 0.9376 | 0.8665 | 0.8611
EMPIRE | 0.9194 | 0.8535 | 0.8472 | 0.9356 | 0.8654 | 0.8623 | 0.8714 | 0.7935 | 0.7842 | 0.9463 | 0.8732 | 0.8642

###  5.2. Performance Comparison

Tables 1, 2 and 3 summarize all the main results. From tables, we can see that
the performance gains from our techniques vary with different basic GNN
models. We list the major findings as follows.

  * •

Results of comparisons between Origin and EMPIRE${}^{-}_{\mathtt{split}}$
demonstrate the superiority of our proposed edge splitting technique, where
the performance gains can be attributed to specifying use of each edge. We
note that this technique is super simple yet can consistently bring the
significant improvement in various graphs.

  * •

Comparisons between EMPIRE${}^{-}_{\mathtt{+message}}$ and
EMPIRE${}^{-}_{\mathtt{split}}$ show the performance gain brought from our
proposed target-aware message passing mechanism. And, comparisons between
EMPIRE${}^{-}_{\mathtt{+relative}}$ and EMPIRE${}^{-}_{\mathtt{+message}}$
illustrates the performance gain brought from the proposed relative message
highlighting technique. Comparing to other techniques, the performance of this
relative message highlighting technique is less stable. One possible
explanation is that as defined in Eq. (12), it is calculated using randomly
sampled nodes, which might make its performance partly rely on randomness.

  * •

The differences between results of EMPIRE${}^{-}_{\mathtt{sample}}$ and EMPIRE
show the performance gain from the efficient negative node-pair sampling
trick. It performance gain usually might be not as significant as that of
other techniques, but is very stable.

###  5.3. Impact of Split Rate

As our edge splitting technique is the basis of all other techniques, thus it
is essential to investigate the impact of split rate $\lambda$. From the
description in Section 3.1, when $\lambda$ approaches zero, there is no edge
used as the supervisions which is meaningless; while when $\lambda$ tends to
one, it represents the case where there is no input graph topology which also
tells nothing. Hence, we select 0.2, 0.3, 0.4, 0.5 as the values of $\lambda$
to depict the trend in term of AUC and ACC on Arxiv and ogb-collab datasets.
As Figure 3 shows, the best performance often occurs around 0.2 to 0.3,
showing that 70% to 80% edges used as the topology and the rest 30% to 20%
edges used as the supervisions mgiht be the best choice in most best cases.
One possible reason is that a larger $\lambda$ means more edges used as the
supervisions and less edges used for the topology, which would cause the data
sparsity issue on the input graph; while a smaller $\lambda$ would encourage
the model to focus more on the input graph, which might lead to the over-
fitting issue.

###  5.4. Impact of Number of GNN Layers

Another key hyperparameter is the number of layers of GNN models. Normally
speaking, the best choice of the number of GNN layers are among the values
1,2,3,4. Therefore, we evaluate their performance in term of AUC and ACC on
Arxiv and ogb-collab datasets and depict the results in Figure 4, which shows
the performance changes from the number of GNN layers are relatively small,
and among those choices 3 might be the best one in the most cases.

Figure 5. Comparisons of training and inference time of EMPIRE and its
variants using GAT as the basic GNN model on Arxiv dataset.

###  5.5. Time Complexity

We study the time complexity of applying the proposed technique on Arxiv
dataset, and depict the training and inference times for one round of the
whole data in Figure 5. From the figure, our efficient negative node-pair
sampling algorithm still consume much time during training. To solve this, one
possible solution is to pre-compute and store these node pairs into buffer,
and then we can simply sample instances from the buffer during training. We
also note that there is almost no extra cost for inference time.

##  6\. Conclusion and Future Work

In this paper, we first analyze the key differences between the node
classification and edge prediction tasks, and present a novel GNN based edge
prediction framework named EMPIRE to tailor existing GNN models (originally
proposed for the node classification task) to be more fit for the edge
prediction task. Specifically, we first propose to specify the edge usage to
avoid the models over-fitting the training graph, and then develop a novel
target-aware message passing mechanism to make the messages to the source
nodes be aware of the target nodes. In addition, we also show that
highlighting relative message and sampling hard negative instances could
further improve the performance. Our experimental results demonstrate that our
techniques can be applied to various GNN models. Future work could focus on
incorporating them into other graph tasks (e.g., graph classification).

## References

  * (1)
  * Ackland et al. (2005) Robert Ackland et al. 2005\.  Mapping the US political blogosphere: Are conservative bloggers more prominent?. In _BlogTalk Downunder 2005 Conference, Sydney_.
  * Adamic and Adar (2003) Lada A Adamic and Eytan Adar. 2003.  Friends and neighbors on the web.  _Social networks_ (2003).
  * Busbridge et al. (2019) Dan Busbridge, Dane Sherburn, Pietro Cavallo, and Nils Y Hammerla. 2019.  Relational graph attention networks.  _Technical report arXiv:1904.05811_ (2019).
  * Gilmer et al. (2017) Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017\.  Neural message passing for quantum chemistry. In _ICML_.
  * Hamilton et al. (2017) William L Hamilton, Rex Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs. In _NIPS_.
  * He et al. (2020) Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. 2020\.  Lightgcn: Simplifying and powering graph convolution network for recommendation. In _SIGIR_.
  * Hu et al. (2018) Binbin Hu, Chuan Shi, Wayne Xin Zhao, and Tianchi Yang. 2018\.  Local and global information fusion for top-n recommendation in heterogeneous information network. In _CIKM_.
  * Hu et al. (2020b) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020b.  Open graph benchmark: Datasets for machine learning on graphs. In _Technical report arXiv:2005.00687_.
  * Hu et al. (2020a) Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. 2020a.  Heterogeneous graph transformer. In _WWW_.
  * Jin et al. (2020) Jiarui Jin, Jiarui Qin, Yuchen Fang, Kounianhua Du, Weinan Zhang, Yong Yu, Zheng Zhang, and Alexander J Smola. 2020\.  An efficient neighborhood-based interaction model for recommendation on heterogeneous graph. In _KDD_.
  * Kipf and Welling (2016a) Thomas N Kipf and Max Welling. 2016a.  Semi-supervised classification with graph convolutional networks. In _ICLR_.
  * Kipf and Welling (2016b) Thomas N Kipf and Max Welling. 2016b.  Variational graph auto-encoders.  _Technical report arXiv:1611.07308_ (2016).
  * Leskovec and Krevl (2015) Jure Leskovec and Andrej Krevl. 2015.  _SNAP Datasets:Stanford large network dataset collection._ (2015).
  * Newman (2006) Mark EJ Newman. 2006\.  Finding community structure in networks using the eigenvectors of matrices.  _Physical review E_ (2006).
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019.  Justifying recommendations using distantly-labeled reviews and fine-grained aspects. In _EMNLP_.
  * Qiu et al. (2020) Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. 2020\.  Gcc: Graph contrastive coding for graph neural network pre-training. In _KDD_.
  * Rong et al. (2019) Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. 2019\.  Dropedge: Towards deep graph convolutional networks on node classification.  _ICLR_ (2019).
  * Schlichtkrull et al. (2018) Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. 2018.  Modeling relational data with graph convolutional networks. In _ESWC_.
  * Singh et al. (2021) Abhay Singh, Qian Huang, Sijia Linda Huang, Omkar Bhalerao, Horace He, Ser-Nam Lim, and Austin R Benson. 2021.  Edge proposal sets for link prediction.  _Technical report arXiv:2106.15810_ (2021).
  * Spring et al. (2002) Neil Spring, Ratul Mahajan, and David Wetherall. 2002\.  Measuring ISP topologies with Rocketfuel.  _ACM SIGCOMM Computer Communication Review_ (2002).
  * Sun et al. (2011) Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S Yu, and Tianyi Wu. 2011.  Pathsim: Meta path-based top-k similarity search in heterogeneous information networks.  _Proceedings of the VLDB Endowment_ (2011).
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018.  Graph attention networks. In _ICLR_.
  * Velickovic et al. (2019) Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. 2019.  Deep Graph Infomax.  _ICLR_ (2019).
  * Vladimir Batagelj (2006) Andrej Mrvar Vladimir Batagelj. 2006\.  _http://vlado.fmf.uni-lj.si/pub/networks/data/_ (2006).
  * Von Mering et al. (2002) Christian Von Mering, Roland Krause, Berend Snel, Michael Cornell, Stephen G Oliver, Stanley Fields, and Peer Bork. 2002\.  Comparative assessment of large-scale data sets of protein–protein interactions.  _Nature_ (2002).
  * Walker (1977) Alastair J Walker. 1977\.  An efficient method for generating discrete random variables with general distributions.  _TOMS_ (1977).
  * Wang et al. (2019c) Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. 2019c.  Deep Graph Library: Towards Efficient and Scalable Deep Learning on Graphs.  _Technical report_ (2019).
  * Wang et al. (2019a) Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019a.  Neural graph collaborative filtering. In _SIGIR_.
  * Wang et al. (2019b) Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. 2019b.  Heterogeneous graph attention network. In _WWW_.
  * Wang et al. (2021) Yangkun Wang, Jiarui Jin, Weinan Zhang, Yong Yu, Zheng Zhang, and David Wipf. 2021\.  Bag of Tricks for Node Classification with Graph Neural Networks.  _DLG-KDD_ (2021).
  * Watts and Strogatz (1998) Duncan J Watts and Steven H Strogatz. 1998.  Collective dynamics of ‘small-world’networks.  _nature_ (1998).
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018\.  How powerful are graph neural networks?  _ICLR_ (2018).
  * Ying et al. (2018) Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. 2018\.  Graph convolutional neural networks for web-scale recommender systems. In _KDD_.
  * You et al. (2019) Jiaxuan You, Rex Ying, and Jure Leskovec. 2019.  Position-aware graph neural networks. In _ICML_.
  * Zhan et al. (2021) Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Jiafeng Guo, Min Zhang, and Shaoping Ma. 2021\.  Optimizing dense retrieval model training with hard negatives. In _SIGIR_.
  * Zhang et al. (2019) Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. 2019.  Heterogeneous graph neural network. In _KDD_.
  * Zhang and Chen (2018) Muhan Zhang and Yixin Chen. 2018.  Link prediction based on graph neural networks.  _NIPS_ (2018).
  * Zhang and Chen (2019) Muhan Zhang and Yixin Chen. 2019.  Inductive matrix completion based on graph neural networks.  _ICLR_ (2019).
  * Zhang et al. (2018) Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. 2018\.  Beyond link prediction: Predicting hyperlinks in adjacency space. In _AAAI_.
  * Zhang et al. (2020) Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. 2020.  Revisiting graph neural networks for link prediction.  _Technical report arXiv:2010.16103_ (2020).
  * Zheng et al. (2017) Jing Zheng, Jian Liu, Chuan Shi, Fuzhen Zhuang, Jingzhi Li, and Bin Wu. 2017\.  Recommendation in heterogeneous information network via dual similarity regularization.  _International Journal of Data Science and Analytics_ (2017).
  * Zhu et al. (2021) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2021.  Graph contrastive learning with adaptive augmentation. In _WWW_.

##  Appendix A Common Neighbor Nodes Retrieval and Sampling algorithms

In this part, we first provide a retrieval algorithm that can search and
retrieve all the node pairs satisfying the common-neighbor heuristics (Adamic
and Adar, 2003) in the training graph $\mathcal{G}_{\mathtt{tr}}$.
Equivalently, we formulate the task as to find all the two-node paths in
$\mathcal{G}_{\mathtt{tr}}$. Formally, our input is
$\mathcal{G}_{\mathtt{tr}}=(\mathcal{V},\mathcal{E}_{\mathtt{tr}})$ and the
output is $\mathcal{B}$ containing all the node pairs.

1 $\mathcal{B}\leftarrow\\{\\}$

2 for  _each $v_{u}\in\mathcal{V}$_ do

3 for  _each $v_{o},v_{w}\in\mathcal{N}_{\mathcal{E}_{\mathtt{tr}}}(u)$_ do

4 if  _$\langle v_{o},v_{w}\rangle\not\in\mathcal{E}_{\mathtt{tr}}$_ then

5 $\mathcal{B}\leftarrow\mathcal{B}\cup\\{(v_{o},v_{w})\\}$

6 end if

7

8 end for

9

10 end for

Algorithm 2 Common Neighbor Nodes Retrieval

1 $\mathcal{B}\leftarrow\\{\\}$

2 for  _each $v_{u}\in\mathcal{V}$_ do

3 $c_{u}\leftarrow d_{u}(d_{u}-1)$ where $d_{u}$ is the degree of node $v_{u}$

4 end for

5$c\leftarrow\sum_{u}c_{u}$

6 for  _each $v_{u}\in\mathcal{V}$_ do

7 $p_{u}\leftarrow c_{u}/c$

8 end for

9for  _$i\leftarrow 1$ to $n_{\mathtt{cn}}$_ do

10 Sample $v_{u}$ with probability $p_{u}$

11 Uniformly sample two different neighbor nodes (i.e., $v_{o}$ and $v_{w}$)
of $v_{u}$

12 if  _$\langle v_{o},v_{w}\rangle\not\in\mathcal{E}_{\mathtt{tr}}$_ then

13 $\mathcal{B}\leftarrow\mathcal{B}\cup\\{(v_{o},v_{w})\\}$

14 end if

15

16 end for

Algorithm 3 Common Neighbor Nodes Sampling

Based on Algorithm 2, we can see all the unconnected node pairs
$(v_{o},v_{w})$ sharing the neighbor node $v_{u}$ are enumerated. As the nodes
$v_{u},v_{o},v_{w}$ can be any nodes in $\mathcal{G}_{\mathtt{tr}}$, the time
complexity of Algorithm 2 is $O(|\mathcal{V}|^{2})$.

However, in the real-world scenarios, there are the many cases with large
graphs, where Algorithm 2 might be not practical due to its high computation
costs. Therefore, we further propose a novel common neighbor nodes sampling
algorithm in Algorithm 3 that can uniformly sample $n_{\mathtt{cn}}$ node
pairs. Its inputs and outputs are identical to Algorithm 2. Let $d_{u}$ denote
the degree of node $v_{u}$.

For the correctness of Algorithm 3, we formulate the sampling the node pairs
into uniformly sampling three-node path, namely $(v_{o},v_{u},v_{w})$. We
first sample the intermediate node of the path (i.e., $v_{u}$) where there are
$d_{u}(d_{u}-1)/2$ three-node paths with $v_{u}$ as its intermediate node.
Next, we sample $v_{u}$ with the probability $p_{u}$ to ensure uniformity,
where $p_{u}=d_{u}(d_{u}-1)/\sum_{u}d_{u}(d_{u}-1)$, and then sample its two
neighbor nodes to form the paths.

For the time complexity, the computation for the degree requires
$O(|\mathcal{E}_{\mathtt{tr}}|)$, the first two loops require
$O(|\mathcal{V}|)$, and the last loop requires $O(n_{\mathtt{cn}})$ if we
sample $(v_{o},v_{w})$ using alias method (Walker, 1977). So, the overall time
complexity of Algorithm 3 is
$O(|\mathcal{V}|+|\mathcal{E}_{\mathtt{tr}}|+n_{\mathtt{cn}})$.

##  Appendix B Extension to Heterogeneous Graphs

Previously, we have introduced EMPIRE in the context of homogeneous graphs,
and exemplify our target-aware message passing and relative message
highlighting techniques by GAT (Veličković et al., 2018).

In this section, we describe how to extend EMPIRE to heterogeneous graphs. We
first introduce the concept of heterogeneous graphs as follows. A
heterogeneous graph, denoted as $\mathcal{G}=(\mathcal{V},\mathcal{E})$,
consists of a node set $\mathcal{V}$ and an edge set $\mathcal{E}$.
$\mathcal{G}$ is also associated with a node type mapping function
$\varphi:\mathcal{V}\rightarrow\mathcal{A}$ and an edge type mapping function
$\psi:\mathcal{E}\rightarrow\mathcal{R}$. $\mathcal{A}$ and $\mathcal{R}$ are
the sets of pre-defined node types and edge types, where
$|\mathcal{A}|+|\mathcal{R}|>2$.

As there are multiple types of edges, two nodes can be connected via different
meta-paths which is defined as follows. A meta-path $\Phi$ is defined as a
path in the form of $A_{1}\stackrel{{\scriptstyle
R_{1}}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle
R_{2}}}{{\longrightarrow}}\cdots\stackrel{{\scriptstyle
R_{l}}}{{\longrightarrow}}A_{l+1}$ that describes a composite relation
$R=R_{1}\odot R_{2}\odot\cdots\odot R_{l}$ between node type $A_{1}$ and
$A_{l}$ and $\odot$ denotes the composition operator on the edge types. Based
on a meta-path $\Phi$, we further present the definition of the meta-path
based neighborhood $\mathcal{N}^{\Phi}_{\mathcal{E}}(s)$ of node $v_{s}$ as:
the set of nodes which connect with node $v_{s}$ via meta-path $\Phi$.

Notice that we summarize the main techniques of EMPIRE as line 1 to line 4 in
Algorithm 1. It is trivial for applying lines 1 and 2 on heterogeneous graphs.
For lines 3 and 4, we further exemplify these operations with HAN (Wang et
al., 2019b), which can be regarded as a heterogeneous version of GAT.
Concretely, we tailor Eq. (9) as

(14) $\bm{m}^{\Phi(l)}_{s\leftarrow w}=\alpha^{\Phi(l)}_{s\leftarrow
w}\left(\bm{h}^{(l)}_{w}+\sum_{v_{t}\in\mathcal{N}^{\Phi}_{\mathcal{E}_{\mathtt{out}}}(s)}\beta^{\Phi(l)}_{w|t}\bm{h}^{(l)}_{w}\right),$

where $\alpha^{\Phi(l)}_{s\leftarrow w}$ and $\beta^{\Phi(l)}_{w|t}$ are
derived by replacing $\mathcal{N}_{\mathcal{E}}$ with
$\mathcal{N}^{\Phi}_{\mathcal{E}}$ in Eqs. (7) and (10). Then, as stated in
(Wang et al., 2019b), these messages will be fed into a semantic-level
attention to aggregate the messages passed through various meta-paths. More
specifically, we tailor Eq. (13) as

(15)
$\bm{h}^{(l+1)}_{s}=\sigma\left(\sum_{\Phi}\zeta^{\Phi(l)}(\bm{W}^{(l)}\bm{h}^{(l)}_{s}+\bm{m}^{\Phi(l)}_{s})\right),$

where $\bm{m}^{\Phi(l)}_{s}$ is the message to node $v_{s}$ through meta-path
$\Phi$ which can be derived as

(16)
$\bm{m}^{\Phi(l)}_{s}=\sum_{v_{w}\in\mathcal{N}^{\Phi}_{\mathcal{E}_{\mathtt{in}}}(s)}\gamma^{\Phi(l)}_{s\leftarrow
w}\bm{m}^{\Phi(l)}_{s\leftarrow w}.$

Here, $\bm{m}^{\Phi(l)}_{s\leftarrow w}$ can be obtained from Eq. (14) and
$\gamma^{\Phi(l)}_{s\leftarrow w}$ is calculated by replacing
$\mathcal{N}_{\mathcal{E}}$ with $\mathcal{N}^{\Phi}_{\mathcal{E}}$ in Eq.
(12). To obtain $\zeta^{\Phi(l)}$ in Eq. (15), we first calculate the
importance of each meta-path following

(17)
$w^{\Phi(l)}=\frac{1}{|\mathcal{V}|}\sum_{v_{s}\in\mathcal{V}}\bm{w}^{(l)\top}\text{tanh}(\bm{W}^{(l)}\bm{m}^{\Phi(l)}_{s}+\bm{b}^{(l)}),$

where $\bm{m}^{\Phi(l)}_{s}$ can be obtained from Eq. (16).

The attention weight of meta-path $\Phi$ denoted as $\zeta^{\Phi(l)}$, can be
computed by normalizing the above importance over all the meta-paths using a
softmax function as

(18) $\zeta^{\Phi}=\frac{\exp(w^{\Phi})}{\sum_{\Phi}\exp(w^{\Phi})}.$

##  Appendix C Experiments

###  C.1. Baseline Description

Our EMPIRE introduced in Section 3 can be regarded as plug-in techniques that
can be seamlessly incorporate into various GNN models on both homogeneous and
heterogeneous graph dataset. To be more specific, for homogeneous GNN models,
we introduce the following GNN models as the basic model:

  * •

GCN (Kipf and Welling, 2016a) is a graph convolutional network particularly
designed for graph structured data.

  * •

GIN (Xu et al., 2018) combines MLP with GCN that is provably as powerful as
the Weisfeiler-Lehman graph isomorphism test.

  * •

GAT (Veličković et al., 2018) combines an attention mechanism with GCN to
model the different contributions from neighbor nodes.

  * •

SAGE (Hamilton et al., 2017) is a graph neural network following a sample-
aggregation paradigm.

For heterogeneous graph datasets, we use the following GNN models as the basic
model:

  * •

RGCN (Schlichtkrull et al., 2018) combines graph neural networks with
factorization models for edge prediction task.

  * •

HAN (Wang et al., 2019b) is a hierarchical attention network designed on
heterogeneous graphs to capture node- and semantic-level information.

###  C.2. Experimental Setting

For the datasets introduced in Section 5.1, we randomly split the edges into
training, testing sets with the ratio of 8:2. We note that we do not directly
use the splitted sets in OGB (Hu et al., 2020b), as some of splits consider
other factors (e.g., date information in ogbl-collab). And, our data
preprocessing is also different from (Zhang and Chen, 2018) where they
randomly select 10% existing edges from each dataset as positive testing data,
and use the remaining 90% existing edges for training, which forms one of
important reasons for inconsistent results between Table 1 and the numbers
reported in (Zhang and Chen, 2018).

For the basic GNN methods, we employ these baseline methods based on Deep
Graph Library (DGL) (Wang et al., 2019c) following their original setting or
directly using their official implementations. We further specify the hyper-
parameter settings as follows. All the models involving GNN layers are set to
have the same three layers. We fix the configurations across all the
experiments, where the dimension size of the embeddings is set to 128, and the
learning rate space is $[0.001,0.0001]$. The dropout rate of input is set to
0.6, of edge is set to 0.3. We use the Adam optimizer for all the models. The
models are trained under the same hardware settings with an Amazon EC2
p3.8$\times$large instance‡‡‡Detailed setting of AWS E2 instance can be found
at https://aws.amazon.com/ec2/instance-types/?nc1=h_ls., where the GPU
processor is NVIDIA Tesla V100 processor and the CPU processor is Intel Xeon
E5-2686 v4 (Broadwell) processor.

##  Appendix D Deployment Feasibility

Here, we discuss the feasibility of industrial deployment of EMPIRE framework.
As graphs (especially heterogeneous graphs) have been leveraged as powerful
data organizing tools to fuse complex information and successfully applied to
many information retrieval scenarios. Among them, one prevailing web-scale
application of GNN models is PinSage (Ying et al., 2018). Hence, we mainly
discuss the deployment feasibility based on Pinsage.

0: current embedding $\bm{h}_{s}$ for node $v_{s}$, set of neighbor embeddings
via topology edges
$\\{\bm{h}_{t}|v_{t}\in\mathcal{N}_{\mathcal{E}_{\mathtt{in}}}(s)\\}$, set of
neighbor embeddings via supervision edges
$\\{\bm{h}_{t}|v_{t}\in\mathcal{N}_{\mathcal{E}_{\mathtt{out}}}(s)\\}$,
symmetric vector function $\mathtt{V}(\cdot)$

0: new embedding $\bm{h}^{\mathtt{new}}_{s}$ for node $v_{s}$

1: $\bm{\alpha}\leftarrow$Eq. (7), $\bm{\beta}\leftarrow$Eq. (10),
$\bm{\gamma}\leftarrow$Eq. (12)

2:
$\bm{n}_{s}\leftarrow\mathtt{V}(\\{\text{ReLU}(\bm{Q}\bm{h}_{s}+\bm{q}|v_{s}\in\mathcal{N}_{\mathcal{E}_{\mathtt{in}}}(s))\\};\bm{\alpha},\bm{\beta})$

3:
$\bm{h}^{\mathtt{new}}_{s}\leftarrow\text{ReLU}(\bm{W}[\bm{h}_{s},\bm{\gamma}^{\top}\bm{n}_{s}]+\bm{w})$

4:
$\bm{h}_{s}^{\mathtt{new}}\leftarrow\bm{h}^{\mathtt{new}}_{s}/\|\bm{h}^{\mathtt{new}}_{s}\|_{2}$

Algorithm 4 Localized EMPIRE Convolution

First, it is not difficult to switch the current model pipeline to EMPIRE. As
stated in (Ying et al., 2018), the core of a PinSage is a localized
convolution, which formulates how to aggregate information from $v_{s}$’s
neighborhood. To apply EMPIRE to PinSage, we modify Algorithm 1 in (Ying et
al., 2018) to get the localized version of EMPIRE convolution. As shown in
Algorithm 4, the main changes brought from EMPIRE are the neighbor and message
weights $\bm{\alpha}$, $\bm{\beta}$, $\bm{\gamma}$ in line 1.

Second, efficiency is another essential concerns in the industrial
applications. The overall complexity of EMPIRE is theoretically analyzed in
Section 3.5 and empirically studied in Section 5.5. To save the computation
costs, we can compute and store the weights in line 1 in an asynchronous
manner. In other words, after assigning initial values to $\bm{\alpha}$,
$\bm{\beta}$, $\bm{\gamma}$, we can run line 2 to line 4 for each step, but
run line 1 for each $T$ step, where $T$ is the update interval for these
weights. Or, we can also simply use the randomized learnable weights (similar
to $\bm{Q}$, $\bm{q},\bm{W},\bm{w}$ in the algorithm) to replace
$\bm{\alpha}$, $\bm{\beta}$, $\bm{\gamma}$ defined in Eqs. (7), (10), (12).

Third, from perspective of the system load, EMPIRE mainly operates the message
passing mechanism during the training procedure; therefore, it is no
additional cost during the inference procedure.