Self-Explainable Graph Neural Networks for Link Prediction
Graph Neural Networks (GNNs) have achieved state-of-the-art performance for
link prediction. However, GNNs suffer from poor interpretability, which limits
their adoptions in critical scenarios that require knowing why certain links
are predicted. Despite various methods proposed for the explainability of GNNs,
most of them are post-hoc explainers developed for explaining node
classification. Directly adopting existing post-hoc explainers for explaining
link prediction is sub-optimal because: (i) post-hoc explainers usually adopt
another strategy or model to explain a target model, which could misinterpret
the target model; and (ii) GNN explainers for node classification identify
crucial subgraphs around each node for the explanation; while for link
prediction, one needs to explain the prediction for each pair of nodes based on
graph structure and node attributes. Therefore, in this paper, we study a novel
problem of self-explainable GNNs for link prediction, which can simultaneously
give accurate predictions and explanations. Concretely, we propose a new
framework and it can find various $K$ important neighbors of one node to learn
pair-specific representations for links from this node to other nodes. These
$K$ different neighbors represent important characteristics of the node and
model various factors for links from it. Thus, $K$ neighbors can provide
explanations for the existence of links. Experiments on both synthetic and
real-world datasets verify the effectiveness of the proposed framework for link
prediction and explanation.
Huaisheng Zhu, Dongsheng Luo, Xianfeng Tang, Junjie Xu, Hui Liu, Suhang Wang
# Self-Explainable Graph Neural Networks for Link Prediction

###### Abstract.

Graph Neural Networks (GNNs) have achieved state-of-the-art performance for link prediction. However, GNNs suffer from poor interpretability, which limits their adoptions in critical scenarios that require knowing why certain links are predicted. Despite various methods proposed for the explainability of GNNs, most of them are post-hoc explainers developed for explaining node classification. Directly adopting existing post-hoc explainers for explaining link prediction is sub-optimal because: (i) post-hoc explainers usually adopt another strategy or model to explain a target model, which could misinterpret the target model; and (ii) GNN explainers for node classification identify crucial subgraphs around each node for the explanation; while for link prediction, one needs to explain the prediction for each pair of nodes based on graph structure and node attributes. Therefore, in this paper, we study a novel problem of self-explainable GNNs for link prediction, which can simultaneously give accurate predictions and explanations. Concretely, we propose a new framework and it can find various \(K\) important neighbors of one node to learn pair-specific representations for links from this node to other nodes. These \(K\) different neighbors represent important characteristics of the node and model various factors for links from it. Thus, \(K\) neighbors can provide explanations for the existence of links. Experiments on both synthetic and real-world datasets verify the effectiveness of the proposed framework for link prediction and explanation.

Link Prediction, Explainability, Graph Neural Networks +
Footnote †: 10: 2018 Association for Computing Machinery.
with them. For users \(v_{i}\) and \(v_{j}\) in the figure, they share common interests in music and are likely to be linked. However, it is difficult to predict the link simply based on their node feature similarity as most of their features/interests are different. Also, as \(v_{i}\) and \(v_{j}\) have diverse neighbors, directly applying a GNN by aggregating all neighbors' information to learn representations of \(v_{i}\) and \(v_{j}\) followed by the similarity of node representation will result in a low predicted link probability. Thus, how to effectively capture the common factor/preferences for a pair of nodes remains a question.

Generally, the preferences of users are reflected in their neighbors. For example, both \(v_{i}\) and \(v_{j}\) have many neighbors interested in music. By identifying and aggregating these neighbors, we can better learn _pair-specific_ node representations that reflect common interests to predict the link between them. Pair-specific means that the representation of \(v_{i}\) for \((v_{i},v_{j})\) should reflect the common interest with \(v_{j}\), and for \((v_{i},v_{k})\) should reflect the comment interest with \(v_{k}\). Based on this intuitive principle, for each node pair \((v_{i},v_{j})\), one way for self-explainable link prediction is to find dominating \(K\) neighbors of \(v_{j}\) that share the highest \(K\) similarities with \(v_{i}\), which reflects the common interest of \((v_{i},v_{j})\) and vice versa. Then, the explanation for whether there is a link for \((v_{i},v_{j})\) can be: (\(i\)) "We suggest \(v_{j}\) to \(v_{i}\) because these \(K\) neighbors of \(v_{i}\) have common features with \(v_{j}\). \(v_{i}\) will most likely establish a new link with \(v_{j}\) for \(v_{j}\) is similar to current neighbors of \(v_{i}\); and (\(ii\)) "We suggest no link predicted for \((v_{i},v_{j})\) because even top \(K\) similar neighbors of \(v_{i}\) w.r.t \(v_{j}\) don't share common feature with \(v_{j}\), which represent \(v_{j}\) is different from neighbors of \(v_{i}\). Therefore, it's hard for \(v_{i}\) to add \(v_{j}\) (different from \(v_{i}\)'s current neighbors) as a new neighbor of it." Though promising, the work on exploring \(K\) relevant neighbors for self-explainable GNNs on link prediction is rather limited.

Therefore, in this paper, we investigate a novel problem of self-explainable GNN for link prediction. Specifically, for a pair of nodes \((v_{i},v_{j})\), we want to identify \(K\) most important neighbors of \(v_{j}\) and \(v_{i}\), respectively, for link prediction. In essence, there are two main challenges: (\(i\)) How to take both graph structure and node attributes into consideration when measuring node similarity for identifying important neighbors for link prediction?

and (\(ii\)) how to give both accurate predictions and correct corresponding explanations given that we lack the supervision of groundtruth explanations? In an attempt to solve the challenges, we propose a novel framework named Interpretable Link Prediction based on Graph Neural Networks (ILP-GNN). For each node pair \((v_{i},v_{j})\), ILP-GNN adopts a novel mechanism that can explicitly evaluate the node similarity and high-order structure similarity to find \(K\) interpretable neighbors of \(v_{i}\) similar to \(v_{j}\). These neighbors can represent common interests or features between \(v_{i}\) and \(v_{j}\). For high-order structure similarity, graph diffusion is utilized to calculate the closeness of nodes by modeling their local and high-order neighbors' information (Gan et al., 2017). Then, these \(K\) neighbors are aggregated to learn pair-specific representation, which represents common features of node pairs and various factors of links for different node pairs. Furthermore, since explanation based on selecting \(K\) important neighbors should preserve factors resulting in the existence of links, we propose a novel loss function to encourage explanation of our model and improve the performance of link prediction. The main contributions are:

* We study a novel problem of self-explainable GNN for link prediction by finding \(K\) neighbors which are relevant to the links.
* We develop a novel framework ILP-GNN, which adopts an interpretable neighbor aggregation method, and a novel loss function to identify \(K\) relevant neighbors for explainable link prediction;
* We conduct extensive experiments to demonstrate the effectiveness of our model on both predictions and explanations. We also construct a synthetic dataset that can quantitatively evaluate the link prediction explanation.

## 2. Related Works

**Graph Neural Networks.** Graph Neural Networks (GNNs) have shown great ability in representation learning on graphs. Generally, GNNs can be split into two categories, i.e., spectral-based (Beng et al., 2015; Goyal et al., 2016; Goyal et al., 2016; Goyal et al., 2016) and spatial-based (Goyal et al., 2016; Goyal et al., 2016; Goyal et al., 2016; Goyal et al., 2016). Spectral-based approaches are defined according to graph signal processing. Bruna et al. (2016) firstly proposes convolution operation to graph data from the spectral domain. Then, a first-order approximation is utilized to simplify the graph convolution via GCN (Goyal et al., 2016). Spatial-based GNN models aggregate information of the neighbor nodes (Goyal et al., 2016; Goyal et al., 2016). For example, the attention mechanism is utilized in Graph Attention Network (GAT) to update the node representation from the neighbors with different weights (Goyal et al., 2016). Moreover, various spatial methods are proposed for further improvements (Goyal et al., 2016; Goyal et al., 2016; Goyal et al., 2016). For instance, DisGNN models latent factors of edges to facilitate node classification (Goyal et al., 2016).

**Link Prediction.** Link prediction has been widely applied in social networks (Beng et al., 2015) and knowledge graph (Goyal et al., 2016). Existing methods for link prediction can be generally split into two categories, i.e., heuristic-based approaches (Beng et al., 2015; Goyal et al., 2016; Goyal et al., 2016; Goyal et al., 2016) and representation learning based approaches (Goyal et al., 2016; Goyal et al., 2016; Goyal et al., 2016). Heuristics-based approaches mainly compute the pairwise similarity scores based on graph structure or node properties (Goyal et al., 2016). For example, the common-neighbor index (CN) scores a pair of nodes by the number of shared neighbors (Goyal et al., 2016); CN and some methods, i.e. Adamic Adar (AA) (Beng et al., 2015), are calculated from up to two-hop neighbors of the target nodes. Other approaches also explore high-order neighbors, including Katz, rooted PageRank (PR) (Beng et al., 2015) and SimRank (SR) (Goyal et al., 2016). But these heuristic-based methods make strong assumptions and can't be generalized to different graph data. Representation learning based approaches firstly learn the representation of nodes and then apply dot product between two node representations to predict the likelihood of the link between two nodes. GNNs are applied to learn node-level representations that capture both the topology structure together with node feature information and achieve state-of-the-art performance on link prediction (Goyal et al., 2016; Goyal et al., 2016; Goyal et al., 2016) in recent years. For example, VGAE (Goyal et al., 2016) adopts GNNs to encode graph structure with features into node representations followed by a simple inner product decoder to get

Figure 1. Example of factors for the link between \(v_{i}\) and \(v_{j}\).
the link prediction result. SEAL (Srivastava et al., 2017) extracts subgraphs to predict links between nodes. However, these approaches are also not interpretable and will limit their ability in applications which may require why the model predicts links between nodes.

**Explainability of Graph Neural Networks**. To address the problem of lacking interpretability in GNNs, extensive works have been proposed (Kang et al., 2017; Wang et al., 2018; Wang et al., 2019). For example, GNNExplainer (Wang et al., 2018) learns soft masks for edges and node features to find the crucial subgraphs and features to explain the predictions. PGExplainer (Wang et al., 2019) generates the edge masks with parameterized explainer to find the significant subgraphs. However, previous methods are post-hoc explanations that learn an explainer to explain the outputs of a trained GNN with fixed parameters. Post-hoc explanations might result in unstable interpretation as generated explanations are not directly from the model. To fill this gap, self-explainable GNNs are proposed to make predictions and explanations simultaneously (Chen et al., 2017; Wang et al., 2019). For example, SE-GNN finds interpretable labeled neighbors which have the same labels as target nodes (Chen et al., 2017). But self-explainable GNN models on the link prediction task are rather limited. CONPI (Wang et al., 2019) models similarity between neighbors set of node pairs to determine the probability of the existence of links and provide explanations based on similar neighbors. Their explanations are based on local topology similarity which ignores high-order graph structure information. Other relevant papers are about explainable link prediction for knowledge graphs (Wang et al., 2019; Wang et al., 2019). They are designed for knowledge graphs and their explanations are based on reasoning paths or (head, relation, tail) data format. Therefore, it's hard for them to be generalized to all link prediction tasks.

Our work is inherently different from the aforementioned explainable GNN methods: (i) we focus on learning a self-explainable GNN on link prediction which can simultaneously give predictions and explanations while most of the previous methods are designed for node classification; (ii) we study a novel self-explainable method to find factors which determine links between nodes by considering both node and high-order structure information.

## 3. Problem Definition

We use \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})\) to denote an attributed graph, where \(\mathcal{V}=\{v_{1},\ldots,v_{N}\}\) is the set of \(N\) nodes, \(\mathcal{E}\) is the set of edges and \(\mathbf{X}\) is the attribute matrix for nodes in \(\mathcal{G}\). The \(i\)-th row of \(\mathbf{X}\), i.e., \(\mathbf{x}_{i}\in\mathbb{R}^{1\times d_{0}}\), is the \(d_{0}\) dimensional features of node \(v_{i}\). \(\mathbf{A}\in\mathbb{R}^{N\times N}\) is the adjacency matrix. \(A_{ij}=1\) if node \(v_{i}\) and node \(v_{j}\) are connected; otherwise \(A_{ij}=0\). \(\mathcal{N}_{i}\) represents the neighborhood set of \(v_{i}\). The goal of link prediction is to determine whether there exists an edge \(e_{ij}\) between two given nodes \(\{v_{i},v_{j}\}\). It can be formulated as a classification problem on a set of node pairs \(\mathcal{E}_{U}\) given observed edges \(\mathcal{E}_{L}\) and node attributes, where \(e_{ij}=1\) represents a link between node \(v_{i}\) and \(v_{j}\), and \(e_{ij}=0\) means no link between \(v_{i}\) and \(v_{j}\). Due to the great node representation learning ability, GNNs are usually adopted as an encoder: \(f:\mathcal{V}\rightarrow\mathbb{R}^{d}\) to map a node \(v_{i}\) to a \(d\)-dimensional vector \(\mathbf{h}_{i}\) for link prediction. \(f\) should preserve the similarity between nodes based on the observed edge set \(\mathcal{E}_{L}\)(Chen et al., 2017), and give large probability (large \((f(v_{i})^{T}f(v_{j}))\)) for \(e_{ij}=1\) but small probability (small \((f(v_{i})^{T}f(v_{j}))\)) for \(e_{ij}=0\). However, GNN usually lacks interpretability on why they give such predictions (Kang et al., 2017; Wang et al., 2019). There are few attempts of explainers on the node classification task (Chen et al., 2017; Wang et al., 2019; Wang et al., 2019; Wang et al., 2019), while the work on interpretable link prediction based on GNNs is rather limited (Wang et al., 2019). Thus, it's crucial to develop interpretable GNNs for link prediction.

As mentioned in the introduction, generally, the preferences of a node are reflected in its neighbors. For node pairs, only some of the neighbors with common features are important for their link prediction. Therefore, to learn pair-specific representation for each node pair \((v_{i},v_{j})\), we propose to find the top \(K\) neighbors of node \(v_{i}\) which are similar to \(v_{j}\). Specifically, for a node pair \((v_{i},v_{j})\), we can learn pair-specific representations \(\mathbf{h}_{i}\) and \(\mathbf{h}_{j}\) by aggregating selected top \(K\) neighbors. Thus, \(\mathbf{h}_{i}^{T}\mathbf{h}_{j}\) will be large when neighbors of \(v_{i}\) are similar to \(v_{j}\) and dissimilar neighbors will result in lower \(\mathbf{h}_{i}^{T}\mathbf{h}_{j}\). Due to the undirected property of graphs, it also holds true for node \(v_{j}\). _Explanations of link prediction can be: (i)_ "for a node pair \(v_{i}\) and \(v_{j}\) with a link, take node \(v_{i}\) as an example, \(v_{i}\)'s neighbors \(v_{c}\in\mathcal{N}_{i}\) have higher similarity score with regard to \(v_{j}\) and \(v_{j}\) in the graph. This explanation also holds for node \(v_{j}\); (ii) "for a node pair \(v_{i}\) and \(v_{j}\) without a link, neighbors of \(v_{i}\) are dissimilar to \(v_{j}\) and also neighbors of \(v_{j}\) are dissimilar to \(v_{i}\).

With the notations above, the problem is formally defined as: _Given an attributed graph \(\mathcal{G}=(\mathcal{V},\mathcal{E}_{L},\mathbf{X})\) with observed edge set \(\mathcal{E}_{L}\) and unobserved edge set \(\mathcal{E}_{U}\), learn an interpretable link predictor \(g_{\theta}:\mathcal{V}\times\mathcal{V}\rightarrow\{True,False\}\) which can accurately predict links in \(\mathcal{E}_{U}\) and simultaneously generate explanation by identifying two sets of important \(K\) neighbors for link between each node pair \((v_{i},v_{j})\)._

## 4. Methodology

In this section, we introduce the details of the proposed framework ILP-GNN. The basic idea of ILP-GNN is: for each node pair \((v_{i},v_{j})\), it identifies \(K\) neighbors of node \(v_{i}\) and \(v_{j}\), respectively, aiming to capture the common interests of the two nodes. Then, it aggregates these \(K\) neighbors' information to obtain their pair-specific representation vectors and calculate the similarity based on their representations. Meanwhile, the \(K\) most relevant neighbors of \(v_{i}\) and \(v_{j}\) provide the explanation on why there is or isn't a link between this node pair. There are mainly two challenges: (i) how to obtain the \(K\) most relevant neighbors of \(v_{i}\) and \(v_{j}\) for the prediction of links between them; (ii) how to simultaneously give accurate predictions and correct corresponding explanations. To address these challenges, for each node pair \((v_{i},v_{j})\), ILP-GNN explicitly models both node and high-order structure similarity between \(v_{i}\) and neighbors of \(v_{j}\) to identify the \(K\) important nodes of \(v_{j}\) for explainable link prediction. Similarly, it explicitly models both node and high-order structure similarity between \(v_{j}\) and neighbors of \(v_{i}\) to identify \(K\) important nodes of \(v_{i}\).

An illustration of the proposed framework is shown in Figure 2. It is mainly composed of an Interpretable Neighbors Aggregation module and an Explanation Enhancement module. With the Interpretable Neighbors Aggregation, for each node pair \((v_{i},v_{j})\), the \(K\) most important neighbors, which represent factors for the existence of links, are found based on both node and high-order structure information. Then, the prediction of links between nodes can be given based on the identified \(K\) neighbors. Finally, the Explanation Enhancement module is designed to further benefit the accurate explanation generation, and also encourage the model to improve link prediction via aggregating \(K\) important neighbors.
### Interpretable Neighbors Aggregation

For GNN-based link prediction on a pair of nodes \((v_{i},v_{j})\), we firstly aggregate their neighbors' information to obtain their representation vectors \((\mathbf{h}_{i},\mathbf{h}_{j})\). Then, the similarity will be calculated between \((\mathbf{h}_{i},\mathbf{h}_{j})\) via \(\mathbf{h}_{i}^{T}\mathbf{h}_{j}\) to indicate whether there is a link between them and pair-specific representation is required to predict links.

However, links are generated due to multiple factors. For different links from \(v_{i}\), it's necessary for us to learn pair-specific representations for \(v_{i}\) to predict links between them. In graph data, the neighborhood of \(v_{i}\) can represent important characteristics but not all neighbors have relevant factors w.r.t different connected nodes of \(v_{i}\). Based on this observation, ILP-GNN selects \(K\) neighbors of \(v_{i}\) which are similar to \(v_{j}\) to learn pair-specific representation of \(v_{i}\). Similarly, through the same way, we learn a pair-specific representation of \(v_{j}\) with \(K\) interpretable neighbors. ILP-GNN relies on interpretable \(K\) neighbors that reveal the common interest of \(v_{i}\) and \(v_{j}\) for link prediction and explanation. We need to design a similarity measurement to measure the similarity between neighbors of node \(v_{i}\) and another connected or unconnected node \(v_{j}\). Unlike i.i data, which only needs to measure the similarity from the feature perspective, for graph-structure data, both node attributes and graph structures of nodes contain crucial information for link prediction. In the following part, for a node pair \((v_{i},v_{j})\), we use \(v_{i}\) as an example to demonstrate the process of finding \(K\) interpretable neighbors. And we will do the same operations for node \(v_{j}\).

#### 4.1.1. High-order Structure Similarity

In the graph, for a pair of nodes \((v_{i},v_{j})\), the distance between neighbors of \(v_{i}\) and \(v_{j}\) can be used to measure their similarity. For instance, one-hop neighbors of the node \(v_{i}\) may have higher similarity scores with \(v_{i}\), while high-order neighbors will have lower similarity scores. And the one-hop relation is represented as the adjacency matrix \(\mathbf{A}\) and high-order relations can be represented as \(\mathbf{A}^{2},\mathbf{A}^{3}\), etc. Since original edge relations are often sparse and missed in real-world graphs, only using one-hop neighbors to measure the distance between nodes may result in unreliable similarity, i.e., the similarity between \(v_{i}\) and \(v_{j}\) equals \(A_{ij}\). Therefore, it's necessary to model both one-hop and high-order relations to measure the similarity between nodes based on graph structure. To measure this high-order similarity, we propose to use a Graph Diffusion matrix which calculates the closeness of nodes in the graph structure by repeatedly passing the weighting coefficients to the neighboring nodes and represents the high-order similarity between nodes based on graph structure(Kirsh and Kirsh, 2015):

\[\mathbf{S}=\sum_{k=0}^{\infty}\theta_{k}\mathbf{T}^{k}, \tag{1}\]

where \(\mathbf{T}\) represents the random walk transition matrix as \(\mathbf{T}=\mathbf{A}\mathbf{D}^{-1}\), and the degree matrix \(\mathbf{D}\) is the diagonal matrix of node degrees, i.e. \(D_{ii}=\sum_{j=1}^{N}A_{ij}\). In this paper, we utilize a popular example of graph diffusion, Personalized PageRank (PPR) (Kip
Finally, with node and high-order structure similarity, the importance score of \(v_{i}\) with \(v_{c}\in\mathbf{N}_{i}\) on \((v_{i},v_{j})\) is:

\[s(v_{i},v_{c},v_{j})=\alpha\cdot s_{\text{ST}}(v_{i},v_{c},v_{j})+(1-\alpha) \cdot s_{\text{NO}}(v_{i},v_{c},v_{j}), \tag{5}\]

where \(\alpha\) is the hyperparameter to control the contributions of node and high-order structure similarity.

After getting weights for neighbors of node \(v_{i}\), we will find \(K\) neighbors based on these weights. We will do the same thing for neighbors of \(v_{j}\). In the link prediction task, common neighbors between \(v_{i}\) and \(v_{j}\) may be highly relevant to links between pairs of nodes (K
```
0:\(\mathcal{G}=(\mathcal{V},\mathcal{E}_{L},\mathbf{X})\), \(K\), \(\lambda,\alpha,\delta\)
0: GNN model \(g_{\theta}\) with explanation for link prediction.
1: Randomly initialize the model parameters \(\Theta\).
2: Calculate high-order distance via Eq.(1).
3:repeat
4: For each node pair \((v_{i},v_{j})\), assign weights \(\mathrm{s}_{\mathrm{ST}}(v_{i},v_{c},v_{j})\) to neighbors of \(v_{i}\) by high-order structure similarity in Eq.(2).
5: Learn node feature representation by Eq.(3) and assign weights to neighbors of \(v_{i}\) by node similarity in Eq.(4).
6: Do the same operation on \(v_{j}\) and aggregate top \(K\) neighbors of \(v_{i}\) and \(v_{j}\) with two kinds of weights in Eq.(7).
7: Calculate the probability \(p_{ij}\) of a link between two nodes.
8: Randomly choose neighbors except from top \(K\) neighbors to obtain \(p_{ij}^{\mathrm{rand}}\) and calculate \(\mathcal{L}_{\mathrm{dis}}^{\mathcal{P}}\) in Eq.(11)
9: Calculate \(\mathcal{L}_{\mathrm{dis}}^{\mathcal{P}}\) using negative samples
10: Update \(\Theta\) by minimizing the overall loss function in Eq.(14)
11:until convergence
12:return\(g_{\theta}\)
```

**Algorithm 1** Training Algorithm of ILP-GNN.

### Training Algorithm and Time Complexity

#### 4.4.1. Training Algorithm

The training algorithm of ILP-GNN is given in Algorithm 1. We utilize \(e_{ij}=1\) as positive samples and \(e_{ij}=0\) as negative samples. ILP-GNN assigns weights to neighbors of nodes based on both node and high-order structure similarity. The top \(K\) neighbors with high weights are aggregated to learn representation for self-explainable link predictions. Specifically, in line one, we initialize the parameters of the model with Xavier initialization (Chen et al., 2017). Then, we calculate high-order similarity by Eq.(1). In lines 4 to line 6, for each node pair \((v_{i},v_{j})\) with or without links, we assign weights to neighbors of \(v_{i}\) and \(v_{j}\) by learned node and high-order structure similarity. Then, ILP-GNN aggregates top \(K\) neighbors with high weights to obtain pair-specific representation vectors \(\mathbf{h}_{i},\mathbf{h}_{j}\). Also, these top \(K\) neighbors, which represent common interests between node pairs, can be treated as the explanation for the existence of links. In line 7, the probability of a link is calculated based on node representation vectors in Eq.(8). To guarantee the quality of explanation, in lines 8 and 9, for positive samples, \(\mathcal{L}_{\mathrm{dis}}^{\mathcal{P}}\) is proposed to make the predicted probability from ILP-GNN larger than the probability predicted from representation vectors with randomly selected neighbors. For negative samples, \(\mathcal{L}_{\mathrm{dis}}^{n}\) is applied to make weights of neighbors small which represents neighbors of one node are dissimilar to another node. In this case, the model will give low predicted probabilities for the existence of links. Finally, the model is optimized on the total loss function Eq.(14).

#### 4.4.2. Time Complexity Analysis

The main time complexity of our model comes from calculating the node similarity and high-order structure similarity together with our proposed loss function. For high-order structure similarity, the time complexity of Personalized PageRank (PPR) is denoted as \(\mathcal{O}(k|\mathcal{E}_{L}|)\), where \(k\) is the number of iterations in Eq.(1). Also, high-order structure similarity can be pre-computed which will not influence the training process of the model. For node similarity, the time complexity for links \(e_{ij}\in\mathcal{E}\) is \(\mathcal{O}(\sum_{e_{ij}\in\mathcal{E}}|\mathcal{N}_{i}||\mathcal{N}_{j}|d)\), where \(d\) is the embedding dimension and \(|\mathcal{N}_{i}|\) is the number of neighbors for \(v_{i}\). The time complexity of the proposed loss function is \(\mathcal{O}(K|\mathcal{E}_{L}|d)\). Therefore, the overall time complexity for the training phase in each iteration is \(\mathcal{O}(\sum_{e_{ij}\in\mathcal{E}_{L}}|\mathcal{N}_{i}||\mathcal{N}_{j}|d +K|\mathcal{E}_{L}|d)\). The time complexity of the testing phase is \(\mathcal{O}(\sum_{e_{ij}\in\mathcal{E}_{U}}|\mathcal{N}_{i}||\mathcal{N}_{j}|d)\). A detailed training time comparison is given in Appendix B.

## 5. Experiment

In this section, we conduct experiments on real-world and synthetic datasets to verify the effectiveness of ILP-GNN. In particular, we aim to answer the following research questions: **(RQ1)** Can our proposed method provide accurate predictions for link prediction? **(RQ2)** Can ILP-GNN learn reasonable explanation for the existence of links? **(RQ3)** How do two similarity measurement methods of our ILP-GNN contribute to the link prediction performance?

### Datasets

We conduct experiments on four publicly available real-world datasets and their details are shown below:

* **Cora and Citeseer**(Cota et al., 2017): These two datasets are citation networks where nodes are papers and edges are their citation relations. Each node has a sparse bag-of-words feature vector.
* **Photo**(Zhou et al., 2018): This dataset is a subgraph of the Amazon co-purchase graph (Zhou et al., 2018), where nodes are products and two frequently purchased products are connected via an edge. Each node has a bag-of-word feature vector of reviews.
* **Ogbm-arxiv**(Chen et al., 2017): It is a citation network between all Computer Science arXiv papers indexed by MAG (Mori et al., 2018). Nodes in this dataset represent papers and edges indicate one paper citing another one. Each paper has a 128-dimensional feature vector obtained by averaging the embeddings of words in its title and abstract.
* **Ogbl-collab**(Chen et al., 2017): This dataset is a subset of the collaboration network between authors indexed by MAG (Mori et al., 2018), where nodes are authors and edges indicate the collaboration between authors. All nodes have 128-dimensional feature vectors by averaging the embeddings of words in papers published by authors.

**Synthetic-Data:** Since the publicly available datasets don't have groundtruth explanations, to quantitatively evaluate the explanation of the proposed method, we also construct synthetic datasets that have groundtruth explanation for links. We firstly generate a set of \(N\) nodes, \(\{v_{1},v_{2},...,v_{N}\}\), with their feature information. Then, for the generation of links between the node pair \((v_{i},v_{j})\), the links are determined by \(B\) neighbors of \(v_{i}\) and these \(B\) neighbors share both high structure and node similarity with \(v_{j}\). Similarly, due to the undirected property of the graph, we also consider \(B\) neighbors of \(v_{j}\) similar to \(v_{i}\) for the generation of links. And these \(B\) neighbors of \(v_{i}\) and \(B\) neighbors of \(v_{j}\) can be treated as groundtruth explanation for this link. We fix \(N\) as 1000 and generate three datasets with different number of edges for experiments. The detailed construction process of the synthetic datasets is given in Appendix A.

The statistics of these datasets are summarized in Table 4 in Appendix A. Following (Cota et al., 2017), for Cora, Citeseer and Photo, we randomly split the edges of each dataset into 85%/5%/10% as train/val/test. The random split is conducted 5 times and average performance will be reported. For Ogbm-arxiv, we randomly split the edges into 60%/10%/30% as train/val/test. For Ogbl-collab, follow (Chen et al., 2017), we split
the edges according to time, where the collaboration edges until 2017 are used as training edges, those in 2018 are used as validation edges, and those in 2019 are test edges. For Synthetic datasets, we randomly select 40% edges from edges set with groundtruth explanation as testing set and 10% as validation set. The remaining edges are used as training samples. We maintained consistency across datasets by following VAGE's split proportion and randomly selecting node pairs not in the training set as negative samples following (Kang et al., 2019). Note that this approach differs from WP and SEAL, which selected pairs not present in any of the training, validation, or test sets. The number of negative samples is equal to the number of positive samples. Positive and negative samples are then combined as our training, validation and testing sets (Kang et al., 2019).

### Experimental Setup

**Baselines.** We compare the proposed framework with representative and state-of-the-art methods for link prediction, which include:

* **CN**(Wang et al., 2019): Common-neighbor index counts the number of common neighbors to predict the link for a pair of nodes.
* **AA**(Chen et al., 2019): Adamic-Adar index is a second-order traditional heuristic method. It assumes that a shared neighbor with the large degree is less significant to the measure of a link.
* **VGAE**(Kang et al., 2019): VGAE is a generative model for graph representation. We use a GCN as the encoder where the second layer has two channels for mean and deviations to sample the latent embeddings and a link reconstruction module as the decoder.
* **GCN**(Kang et al., 2019): GCN is one of the most popular spectral GNN models based on graph Laplacian, which has shown great performance for node classification. To adopt it for link prediction, we treat it as the encoders in the Graph Autoencoder manner.
* **GAT**(Wang et al., 2019): Instead of treating each neighbor node equally, GAT utilizes an attention mechanism to assign different weights to nodes in the neighborhood during the aggregation step.
* **SEAL**(Wang et al., 2019): SEAL is a link prediction method that extracts local subgraphs of node pairs and learns link prediction heuristics from them automatically.
* **CONPI**(Wang et al., 2019): CONPI is an interpretable model to compare the similarity between neighbors sets of two nodes for link prediction. It has two variants and we report the best results of them.
* **WP**(Wang et al., 2019): WalkPooling (WP) jointly encodes node representations and graph topology into learned topological features. Then, these features are used to enhance representation of extracted subgraphs which are relevant to links of node pairs.

As the work on explainable GNN for link prediction is rather limited, we also adapt a popular post-hoc explanation model GNNExplainer for post-hoc link prediction.

* **GNNExplainer**(Wang et al., 2019): GNNExplainer takes a trained GNN and the predictions as input to obtain post-hoc explanations. A soft edge mask is learned for each instance to identify the crucial subgraph. We adopt GNNExplainer to find crucial neighbors of node pairs with links for link prediction.

**Configurations.** All experiments are conducted on a 64-bit machine with Nvidia GPU (NVIDIA RTX A6000, 1410MHz, 48 GB memory). For a fair comparison, we utilize a two-layer graph neural network for all methods, and the hidden dimension is set as 128. The learning rate is initialized to 0.001. Besides, all models are trained until converging, with the maximum training epoch as 1000. The implementations of all baselines are based on Pytorch Geometric or their original code. The hyperparameters of all methods are tuned on the validation set. In particular, for the proposed framework, we select \(K\) from 1 to 6 and vary \(\lambda\) as \(\{0.1,0.3,0.5,0.7\}\). The \(\alpha\) which balances the node similarity and high-order structure similarity is fixed as 0.3 for all datasets. The margin \(\delta\) in Eq.(11) is set as 0.5.

### Performance on Link Prediction

In this subsection, we compare the performance of the proposed ILP-GNN with baselines for link prediction on real-world graphs introduced in Sec. 5.1, which aims to answer **RQ1**. Each experiment is conducted 5 times for all datasets and the average link prediction AUC scores with standard deviations are reported in Table 1. From the table, we make the following observations:

* Our method outperforms VGAE, GCN and GAT on various real-world datasets. This is because for each node pair \((u_{i},v_{j})\), our model can select \(K\) neighbors of \(v_{i}\) and \(v_{j}\) separately, which contain common characteristics of \((u_{i},v_{j})\) and are highly relevant to the factors for the existence of the link. By aggregation these \(K\) significant neighbors, our model can learn pair-specific representations of \(v_{i}\) and \(v_{j}\) for the link and predict it accurately.
* ILP-GNN can outperform SEAL and its variant WP which extracts subgraphs to learn link prediction heuristics. The reason is that our model can implicitly find local neighbors which can also explore link prediction heuristics like common neighbors and high-order structure information.
* Though CONPI also compares neighbors of node pairs and finds relevant neighbors for link prediction, our model can outperform CONPI, which shows the effectiveness of our method in selecting neighbors for link prediction and our loss function can guide the model to obtain link prediction relevant neighbors.

### Explanation Quality

In this subsection, we conduct quantitatively experimental comparisons and visualization to answer **RQ2**.

\begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline
**Method** & AA & CN & VGAE & GCN & GAT & SEAL & CONPI-Pair & WP & ILP-GNN \\ \hline Cora & 75.80 \(\pm\) 0.15 & 75.57 \(\pm\) 0.13 & 91.18 \(\pm\) 0.41 & 91.57 \(\pm\) 0.69 & 91.87 \(\pm\) 0.93 & 92.21 \(\pm\) 1.23 & 89.69 \(\pm\) 0.32 & 92.42 \(\pm\) 1.1 & **93.21 \(\pm\) 1.14** \\ Citeseer & 69.80 \(\pm\) 0.22 & 69.70 \(\pm\) 0.23 & 91.42 \(\pm\) 0.96 & 92.51 \(\pm\) 1.00 & 93.57 \(\pm\) 0.64 & 90.52 \(\pm\) 1.29 & 87.47 \(\pm\) 0.10 & 91.37 \(\pm\) 0.98 & **95.23 \(\pm\) 1.33** \\ Photo & 96.59 \(\pm\) 0.22 & 96.21 \(\pm\) 0.04 & 97.03 \(\pm\) 0.15 & 97.08 \(\pm\) 0.13 & 96.47 \(\pm\) 0.19 & 98.04 \(\pm\) 0.70 & 96.45 \(\pm\) 0.42 & 98.12 \(\pm\) 0.14 & **98.23 \(\pm\) 0.04** \\ Ogbn-arxiv & 82.41 \(\pm\) 0.02 & 82.43 \(\pm\) 0.01 & 95.05 \(\pm\) 0.07 & 95.27 \(\pm\) 0.06 & 94.79 \(\pm\) 0.03 & 95.30 \(\pm\) 0.04 & 94.22 \(\pm\) 0.08 & 95.33 \(\pm\) 0.02 & **95.42 \(\pm\) 0.03** \\ Ogbn-collab & 58.09 \(\pm\) 0.09 & 57.88 \(\pm\) 0.02 & 96.27 \(\pm\) 0.07 & 96.73 \(\pm\) 0.02 & 96.64 \(\pm\) 0.05 & 93.57 \(\pm\) 0.04 & 92.31 \(\pm\) 0.03 & 96.81 \(\pm\) 0.02 & **97.17 \(\pm\) 0.01** \\ \hline \hline \end{tabular}
\end{table}
Table 1. Link Prediction performance (AUC(%) \(\pm\) Std.) on all graphs.
#### 5.4.1. Results on Fidelity Scores

We first demonstrate the effectiveness of explanation in terms of fidelity scores. The fidelity score measures the link prediction performance drop for each pair of nodes when important neighbors of the pair of nodes are removed. Intuitively, if a model can capture important neighbors of a pair of nodes for link prediction, the removal of such neighbors would result in a significant performance drop. Specifically, for each node pair \((v_{i},v_{j})\) in the test set, take node \(v_{i}\) as an example, we denote the delete top \(M\) neighbors based on weight scores given by the model as \(\mathcal{N}_{i}^{o}\). We delete will \(\mathcal{N}_{i}^{o}\) and obtain a new neighbor set \(\mathcal{N}_{i}\backslash\mathcal{N}_{i}^{o}\). We then aggregate neighbors \(v_{c}\) of \(v_{i}\) from this new set \(v_{c}\in\mathcal{N}_{i}\backslash\mathcal{N}_{i}^{o}\) to obtain the representation vector \(\mathbf{h}_{i}^{w}\) via different aggregation methods from different models, i.e., GAT, CONPI, ILP-GNN. We do the same operations for node \(v_{j}\) to get the representation \(\mathbf{h}_{j}^{w}\). Note that if \(|\mathcal{N}_{i}|\leq M\) and the new neighbors set is empty, we only use their features. Then, we can obtain the new link prediction score \(\hat{\theta}_{ij}^{w}\) using \(\mathbf{h}_{i}^{w}\) and \(\mathbf{h}_{j}^{w}\) by Eq.(8). The fidelity score \(\Delta AUC\%\) is calculated as \(\Delta AUC\%=\sum_{v_{j}\in\mathcal{E}_{v_{j}}}(AUC\,\hat{\rho}_{ij}-AUC \hat{\rho}_{ij}^{w})\%\), where \(AUC\,\hat{\rho}_{ij}\) and \(AUC\,\hat{\rho}_{ij}^{w}\) are AUC value with regard to different predicted results, and \(\hat{\rho}_{ij}\) is the original predicted result. We compare our model with GAT and CONPI which can also assign weights to neighbors for link prediction. We vary the number of deleted neighbor \(M\) as \(\{1,2,3,4\}\). All experiments are conducted five times with random splits and the results are reported in Figure 3. From the figure, we make the following observations: (i) ILP-GNN consistently outperforms two baselines with different deleted neighbors. Compared with GAT, for different links \((v_{i},v_{j})\) and \((v_{i},v_{k})\), ILP-GNN learns pair specific representation for \(v_{i}\) by selecting different neighbors of \(v_{i}\) relevant to the existence of various links. However, GAT assigns higher weights to the same neighbors and learns one representation of \(v_{i}\) for different links. In real-word graphs, different links may be from different factors, which are relevant to different neighbors of nodes. Therefore, our proposed ILP-GNN can explore the relevant neighbors for links with different factors, which will greatly improve link prediction and lead to higher fidelity scores. (ii) Also, our proposed loss function can help the model select neighbors to give high probabilities to links and low probabilities to no-links. It can help the model find neighbors relevant to links. Thus, our model can achieve the best fidelity score by deleting neighbors.

#### 5.4.2. Results on Synthetic Datasets

Secondly, we evaluate the explanation quality on synthetic datasets with groundtruth explanation. Specifically, in the synthetic datasets, for each node pair \((v_{i},v_{j})\), \(v_{i}\) is similar to \(K\) neighbors of node \(v_{j}\) and \(v_{j}\) are similar to \(K\) neighbors of \(v_{i}\), which lead to the link between them. We treat these \(K\) neighbors of \(v_{i}\) and \(K\) neighbors of \(v_{j}\) as explanation neighbors for the link between them. Therefore, for the task to find explanation neighbors in the synthetic datasets, the model should find the correct \(K\) neighbors of \(v_{i}\) and \(K\) neighbors of \(v_{j}\) for explainable link prediction. Specifically, for each node pair \((v_{i},v_{j})\), we rank neighbors of \(v_{i}\) based on weight scores assigned from the model, i.e., ILP-GNN, GAT and CONPI. We also do the same operations on \(v_{j}\). We then calculate the precision@\(2\) and precision@\(1\) for the ranked neighbors list of \(v_{i}\) and \(v_{j}\) w.r.t groundtruth explanation neighbors set of \(v_{i}\) and \(v_{j}\). Also, we includes the baseline (named Random in Table 2) which randomly select \(K\) neighbors of \(v_{i}\) and \(v_{j}\) and evaluate the explanation performance based on randomly selected \(K\) neighbors list. To further demonstrate the effectiveness of our model on link prediction explanation, we adopt one classical post-hoc explanation method, GNNExplainer, which is originally designed for node classification. For the link between \(v_{i}\) and \(v_{j}\), we adopt GNNExplainer to find the top \(K\) crucial neighbors of them for the link between them. We treat these \(K\) neighbors of \(v_{i}\) and \(v_{j}\) as explanation neighbors of them. The higher the precision@\(1\) or precision@\(2\) is, the closer the explainable neighbors found by the model with the groundtruth. We evaluate explanation performance by precision@\(1\) or precision@\(2\) and link prediction performance by AUC. All experiments are conducted five times and the average results and standard deviations on the three synthetic datasets are reported in Table 2 and Table 3 for explanation and link prediction performance. From the results, we make the following observations: (i) GNNExplainer only has a little improvement compared with the Random method. It demonstrates that current explanation methods designed for node classification can't be easily adopted to link prediction. (ii) ILP-GNN consistently outperforms all baselines on both explanation and link prediction metrics, which indicates that it can retrieve reliable \(K\) neighbor nodes for prediction and explanation simultaneously.
probabilities to no-links. Therefore, it further demonstrates the effectiveness of our model to select relevant neighbors to improve the performance of link prediction.

### Ablation Study

To answer **RQ3**, we conduct an ablation study to explore the effects of both node and structure similarity to find \(K\) interpretable neighbors for the link prediction task. ILP-GNN\(\backslash\)E denotes the variant that we don't use structure similarity measurement to find neighbors, i.e., setting \(\alpha=0\) in Eq.(5). ILP-GNN\(\backslash\)F denotes the variant without node similarity measurement in Eq.(5), i.e., setting \(\alpha=1\). ILP-GNN\(\backslash\)F, E represents the GCN model that aggregates all neighbors without weights. The experimental results on Cora and Photo are reported in Figure 7. We can observe that: (a) two variants of ILP-GNN and ILP-GNN by predicting links with selecting neighbors can greatly outperform ILP-GNN\(\backslash\)F, E. It means that the proposed interpretable neighbor aggregation module can greatly improve the performance of link prediction by finding \(K\) neighbors of one node, which are similar to other linked nodes. (b) ILP-GNN\(\backslash\)F and ILP-GNN\(\backslash\)E, which implies that combining both node and structure similarity is helpful for finding relevant neighbors to improve the link prediction.

### Hyperparameter Sensitivity Analysis

In this section, we explore the sensitivity of the most important hyperparameters \(K\) and \(\lambda\), which control the number of neighbors to select and the contribution of the Explanation Enhancement module, respectively. Specifically, we vary \(K\) as \(\{1,2,4,6\}\) and \(\lambda\) as \(\{0.1,0.3,0.5,0.7\}\). The other settings are the same as the experiment for Table 1. We report the AUC value for link prediction on Cora and Citeseer. The experiment is conducted five times with random splits and the average results are shown in Figure 5. From the figure, we observe that: (i) with the increase of \(K\), the performance firstly increases and then decreases. When \(K\) is small, a small number of relevant neighbors are selected. A small set of neighbors may not reflect the characteristics of nodes to build links with other nodes, which results in poor performance. When \(K\) is large, the large number of selected neighbors may contain bias and will cover important characteristics of nodes building links. Therefore, when \(K\) is in the range of 2 to 4, the performance is generally good. (ii) with the increasing of \(\lambda\), the performance of ILP-GNN tends to firstly increase and then decrease. When \(\lambda\) is small, little supervision is received to select neighbors which may result in a high predicted probability for positive samples and low probabilities for negative samples. Also, large \(\lambda\) will be dominated by enhancing selected neighbors for link prediction, which can also lead to poor performance. For \(\lambda\), a value between 0.3 to 0.5 generally gives a good performance.

### Case Study

We conduct a case study to show the importance of selected neighbors for the decision process of link prediction. Specifically, we apply t-SNE to the learned representation of nodes, i.e. \(\mathbf{h}_{i}\) for node \(u_{i}\) in Eq.(7), with aggregating selected neighbors from our model. Then, we learn another representation \(\mathbf{h}_{i}^{*}\) by aggregating neighbors without these selected neighbors. The relative positions of nodes for these two representations are visualized. Also, we visualize their local 1-hop neighbors to obtain the positions of nodes based on node similarity as shown in Figure 4. We show cases of links between two nodes with and without common neighbors and node pairs without links. As shown in Figure 4 (a), the learned representation with selected neighbors from our model will have higher similarity in the left figure (\(v_{1}\) is near to \(v_{2}\)). However, the learned embedding without these neighbors will result in a lower similarity in the right figure (two nodes are distant). For no-links, our model

Figure 4. Case Study for node pairs with links or without links on Cora.

Figure 5. Hyperparameter Sensitivity Analysis

Figure 6. Visualization of weighted scores.

Figure 7. Ablation Study on Cora and Photo datasets.
will make the learned representation of both \(v_{1}\) and \(v_{2}\) with their neighbors distant. And the model will give lower probabilities for no-links. Therefore, our model can provide both predictions and explanations accurately by finding significant neighbors.

## 6. Conclusion

In this paper, we study a novel problem of self-explainable GNNs for link prediction by exploring \(K\) important neighbors for links. We propose a novel framework, which designs an interpretable aggregation module for finding \(K\) neighbors relevant to factors of links and simultaneously uses these neighbors to give predictions and explanations. Also, a novel loss function is proposed to enhance the generation of explanations and also the performance of the link prediction task. Extensive experiments on real-world and synthetic datasets verify the effectiveness of the proposed ILP-GNN for explainable link prediction. An ablation study and parameter sensitivity analysis are also conducted to understand the contribution of the proposed modules and sensitivity to the hyperparameters. There are several interesting directions that need further investigation. One direction is to extend ILP-GNN for dynamic network link prediction. Another direction is to design more efficient and learnable approaches to explore high-order similarity in graphs.
