PaGE-Link: Path-based Graph Neural Network Explanation for Heterogeneous
  Link Prediction
Transparency and accountability have become major concerns for black-box
machine learning (ML) models. Proper explanations for the model behavior
increase model transparency and help researchers develop more accountable
models. Graph neural networks (GNN) have recently shown superior performance in
many graph ML problems than traditional methods, and explaining them has
attracted increased interest. However, GNN explanation for link prediction (LP)
is lacking in the literature. LP is an essential GNN task and corresponds to
web applications like recommendation and sponsored search on web. Given
existing GNN explanation methods only address node/graph-level tasks, we
propose Path-based GNN Explanation for heterogeneous Link prediction
(PaGE-Link) that generates explanations with connection interpretability,
enjoys model scalability, and handles graph heterogeneity. Qualitatively,
PaGE-Link can generate explanations as paths connecting a node pair, which
naturally captures connections between the two nodes and easily transfer to
human-interpretable explanations. Quantitatively, explanations generated by
PaGE-Link improve AUC for recommendation on citation and user-item graphs by 9
- 35% and are chosen as better by 78.79% of responses in human evaluation.
Shichang Zhang, Jiani Zhang, Xiang Song, Soji Adeshina, Da Zheng, Christos Faloutsos, Yizhou Sun
# PaGE-Link: Path-based Graph Neural Network Explanation for Heterogeneous Link Prediction

###### Abstract.

Transparency and accountability have become major concerns for black-box machine learning (ML) models. Proper explanations for the model behavior increase model transparency and help researchers develop more accountable models. Graph neural networks (GNN) have recently shown superior performance in many graph ML problems than traditional methods, and explaining them has attracted increased interest. However, GNN explanation for link prediction (LP) is lacking in the literature. LP is an essential GNN task and corresponds to web applications like recommendation and sponsored search on web. Given existing GNN explanation methods only address node/graph-level tasks, we propose Path-based GNN Explanation for heterogeneous Link prediction (_PaGE-Link_) that generates explanations with _connection interpretability_, enjoys model _scalability_, and handles graph _heterogeneity_. Qualitatively, PaGE-Link can generate explanations as paths connecting a node pair, which naturally captures connections between the two nodes and easily transfer to human-interpretable explanations. Quantitatively, explanations generated by PaGE-Link improve AUC for recommendation on citation and user-item graphs by _9 - 35%_ and are chosen as better by _78.79%_ of responses in human evaluation.

Model Transparency, Model Explanation, Graph Neural Networks, Link Prediction +
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
Footnote †: Journal: Journal: Information Systems

+
Footnote †: journal: Journal: Journal: Information Systems

+
grows from \(m\) to \(\sim\)\(2m\) compared to the node prediction task because neighbors of both the source and the target are involved. Since most existing methods consider all (edge-induced) subgraphs, the increased edges will scale the number of subgraph candidates by a factor of \(O(2^{m})\), which makes finding the optimal subgraph explanation much harder. 3) _Heterogeneity:_ Practical LP is often on heterogeneous graphs with rich node and edge types, e.g., a graph for recommendations can have user->buys->item edges and item->has->attribute edges, but existing methods only work for homogeneous graphs.

In light of the importance and challenges of GNN explanation for LP, we formulate it as a post hoc and instance-level explanation problem and generate explanations for it in the form of important paths connecting the source node and the target node. Paths have played substantial roles in graph ML and are the core of many non-GNNLP methods (Gan et al., 2015; Liu et al., 2016; Wang et al., 2017; Wang et al., 2018). Paths as explanations can solve the connection interpretability and scalability challenges. Firstly, paths connecting two nodes naturally explain connections between them. Figure 1 shows an example on a graph for recommendations. Given a GNN and a predicted link between user \(u_{1}\) and item \(i_{1}\), human-interpretable explanations may be based on the user's preference of attributes (e.g., user \(u_{1}\) bought item \(i2\) that shared the same attribute \(a_{1}\) as item \(i_{1}\)) or collaborative filtering (e.g, user \(u_{1}\) had a similar preference as user \(u_{2}\) because they both bought item \(i_{3}\) and user \(u_{2}\) bought item \(i_{1}\), so that user \(u_{1}\) would like item \(i_{1}\)). Both explanations boil down to paths. Secondly, paths have a considerably smaller search space than general subgraphs. As we will see in Proposition 4.1, compared to the expected number of edge-induced subgraphs, the expected number of paths grows strictly slower and becomes negligible. Therefore, path explanations exclude many less-meaningful subgraph candidates, making the explanation generation much more straightforward and accurate.

To this end, we propose Path-based GNN Explanation for heterogeneous Link prediction (PaGE-Link), which achieves a better explanation AUC and scales linearly in the number of edges (see Figure 2). We first perform _k-core pruning_(Beng et al., 2015) to help find paths and improve scalability. Then we do _heterogeneous path-enforcing_ mask learning to determine important paths, which handles heterogeneity and enforces the explanation edges to form paths connecting source to target. In summary, the contributions of our method are:

* **Connection Interpretability:** PaGE-Link produces more interpretable explanations in path forms and quantitatively improves explanation AUC over baselines.
* **Scalability:** PaGE-Link reduces the explanation search space by magnitudes from subgraph finding to path finding and scales linearly in the number of graph edges.
* **Heterogeneity:** PaGE-Link works on heterogeneous graphs and leverages edge-type information to generate better explanations.

## 2. Related Work

We review relevant research on (a) GNNs (b) GNN explanation (c) recommendation explanation and (d) paths for LP. We summarize the properties of PaGE-Link vs. representative methods in Table 1.

GNNs.GNNs are a family of ML models on graphs (Gan et al., 2015; Wang et al., 2017; Wang et al., 2018). They take graph structure and node/edge features as input and output node representations by transforming and aggregating features of nodes' (multi-hop) neighbors. The node representations can be used for LP and achieved great results on LP applications (Gan et al., 2015; Wang et al., 2017; Wang et al., 2018; Wang et al., 2018; Wang et al., 2018; Wang et al., 2018; Wang et al., 2018). We review GNN-based LP models in Section 3.

GNN explanation.GNN explanation was studied for node and graph classification, where the explanation is defined as an important subgraph. Existing methods majorly differ in their definition of importance and subgraph selection methods. GNNExplainer (GNNExplainer, 2018) selects edge-induced subgraphs by learning fully parameterized masks on graph edges and node features, where the mutual information (MI) between the masked graph and the prediction made with the original graph is maximized. PGEExplainer (GNNExplainer, 2018) adopts the same MI importance but trains a mask predictor to generate a discrete mask instead. Other popular importance measures are game theory values. SubgraphX (Wang et al., 2018) uses the Shapley value (Shapiro et al., 2018) and performs Monte Carlo Tree Search (MCTS) on subgraphs. GStarX (GStarX, 2018) uses a structure-aware HN value (Gan et al., 2015) to measure the importance of nodes and generates the important-node-induced subgraph. There are more studies from other perspectives that are less related to this work, i.e., surrogate models (Gan et al., 2015; Wang et al., 2018), counterfactual explanations (Wang et al., 2018), and causality (Wang et al., 2018; Wang et al., 2018), for which (Wang et al., 2018) provides a good review. While these methods produce subgraphs as explanations, what makes a good explanation is a complex topic, especially how to meet "stakeholders' desiderata" (Gan et al., 2015). Our work differs from all above since we focus on a new task of explaining heterogeneous LP, and we generate paths instead of unrestricted subgraphs as explanations. The interpretability of paths makes our method advantaged especially when stakeholders have less ML background.

Figure 1. Given a GNN model and a predicted link \((u_{1},i_{1})\) (dashed red) on a heterogeneous graph of user \(u\), item \(i\), and attribute \(a\) (left). PaGE-Link generates two path explanations (green arrows). Interpretations illustrated on the right.

Figure 2. (a) PaGE-Link outperforms GNNExplainer and PGExplainer in terms of explanation AUC on the citation graph and the user-item graph. (b) The running time of PaGE-Link scales linearly in the number of graph edges.
_Recommendation explanation._ This line of works explains why a recommendation is made (Sohn et al., 2017). J-RECS (Kang et al., 2018) generates recommendation explanations on product graphs using a justification score that balances item relevance and diversity. PRINCE (Bordes and McAllester, 2016) produces end-user explanations as a set of minimal actions performed by the user on graphs with users, items, reviews, and categories. The set of actions is selected using counterfactual evidence. Typically, recommendations on graphs can be formalized as an LP task. However, the recommendation explanation problem differs from explaining GNNs for LP because the recommendation data may not be graphs, and the models to be explained are primarily not GNN-based (Sohn et al., 2017). GNNs have their unique message passing procedure, and GNN-based LP corresponds to more general applications beyond recommendation, e.g., drug repurposing (Kipf and Welling, 2017), and knowledge graph completion (Bordes and McAllester, 2016; Kang et al., 2018). Thus, recommendation explanation is related to but not directly comparable to GNN explanation.

_Paths._ Paths are important in graph ML, and many LP methods are path-based, such as graph distance (Kang et al., 2018), Katz index (Katz, 1976), SimRank (Katz, 1976), and PathSim (Sohn et al., 2017). Paths have also been used to capture the relationship between a pair of nodes. For example, the "connection subgraphs" (Bordes and McAllester, 2016) find paths between the source and the target based on electricity analogs. In general, although black-box GNNs recently outperform path-based methods in LP accuracy, we embrace paths for their interpretability for LP explanation.

## 3. Notations and preliminary

In this section, we define necessary notations, summarize them in Table 2, and review the GNN-based LP models.

**Definition 3.1**.: A heterogeneous graph is defined as a directed graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) associated with a node type mapping function \(\phi:\mathcal{V}\rightarrow\mathcal{A}\) and an edge type mapping function \(\tau:\mathcal{E}\rightarrow\mathcal{R}\). Each node \(v\in\mathcal{V}\) belongs to one node type \(\phi(v)\in\mathcal{A}\) and each edge \(e\in\mathcal{E}\) belongs to one edge type \(\tau(e)\in\mathcal{R}\).

Let \(\Phi(\cdot,\cdot)\) denote a trained GNN-based model for predicting the missing links in \(\mathcal{G}\), where a prediction \(Y=\Phi(\mathcal{G},(s,t))\) denotes the predicted link between a source node \(s\) and a target node \(t\). The model \(\Phi\) learns a conditional distribution \(P_{\Phi}(Y|\mathcal{G},(s,t))\) of the binary random variable \(Y\). The commonly used GNN-based LP models (Sohn et al., 2017; Sohn et al., 2017; Sohn et al., 2017) involve two steps. The first step is to generate node representations \((\mathbf{h}_{s},\mathbf{h}_{t})\) of \((s,t)\) with an \(L\)-hop GNN encoder. The second step is to apply a prediction head on \((\mathbf{h}_{s},\mathbf{h}_{t})\) to get the prediction of \(Y\). An example prediction head is an inner product.

To explain \(\Phi(\mathcal{G},(s,t))\) with an \(L\)-Layer GNN encoder, we restrict to the _computation graph_\(\mathcal{G}_{c}=(\mathcal{V}_{c},\mathcal{E}_{c})\). \(\mathcal{G}_{c}\) is the \(L\)-hop ego-graph of the predicted pair \((s,t)\), i.e., the subgraph with node set \(\mathcal{V}_{c}=\{v\in V|dist(v,s)\leq L\text{ or }dist(v,t)\leq L\}\). It is called a computation graph because the \(L\)-layer GNN only collects messages from the \(L\)-hop neighbors of \(s\) and \(t\) to compute \(\mathbf{h}_{s}\) and \(\mathbf{h}_{t}\). The LP result is thus fully determined by \(\mathcal{G}_{c}\), i.e., \(\Phi(\mathcal{G},(s,t))\equiv\Phi(\mathcal{G}_{c},(s,t))\). Figure 2(b) shows a 2-hop ego-graph of \(u_{1}\) and \(i_{1}\), where \(u_{3}\) and \(a_{3}^{3}\) are excluded since they are more than 2 hops away from either \(u_{1}\) or \(i_{1}\).

## 4. Proposed problem formulation: link-prediction explanation

In this work, we address a _post hoc_ and _instance-level_ GNN explanation problem. The post hoc means the model \(\Phi(\cdot,\cdot)\) has been trained. To generate explanations, we won't change its architecture or parameters. The instance level means we generate an explanation for the prediction of each instance \((s,t)\). Specifically, the explanation method answers the question of why a missing link is predicted by \(\Phi(\cdot,\cdot)\). In a practical web recommendation system, this question can be "_why an item is recommended to a user by the model_".

An explanation for a GNN prediction should be some substructure in \(\mathcal{G}_{c}\), and it should also be concise, i.e., limited by a size budget \(B\). This is because an explanation with a large size is often neither informative nor interpretable, for example, an extreme case is that \(\mathcal{G}_{c}\) could be a non-informative explanation for itself. Also, a fair comparison between different explanations should consume the same budget. In the following, we define budget \(B\) as the maximum number of edges included in the explanation.

We list three desirable properties for a GNN explanation method on heterogeneous LP: capturing the connection between the source node and the target node, scalable to large graphs, and addressing graph heterogeneity. Using a path-based method inherently possesses all the properties. Paths capture the connection between a pair of nodes and can be transferred to human-interpretable explanations. Besides, the search space of paths with the fixed source node and the target node is greatly reduced compared to edge-induced subgraphs. Given the ego-graph \(\mathcal{G}_{c}\) of \(s\) and \(t\), the number of paths between \(s\) and \(t\) and the number of edge-induced subgraphs in \(\mathcal{G}_{c}\) both rely on the structure of \(\mathcal{G}_{c}\). However, they can

\begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline \multirow{2}{*}{Methods} & \multirow{2}{*}{\(\mathcal{G}=(\mathcal{V},\mathcal{E})\)} & \multirow{2}{*}{a heterogeneous graph \(\mathcal{G}\), node set \(\mathcal{V}\), and edge set \(\mathcal{E}\)} \\  & & & & & & & & \\ \hline On Graphs & ✓ & ✓ & ✓ & ✓ & ✓ &? & ✓ \\ Explains GNN & ✓ & ✓ & ✓ & ✓ & & & \\ Explains LP &? &? &? &? & ✓ & ✓ & ✓ \\ Connection & & & &? &? &? &? & ✓ \\ Scalability & ✓ & ✓ & & &? &? &? & ✓ \\ Heterogeneity & & & & ✓ & ✓ & ✓ &? & ✓ \\ \hline \hline \end{tabular}
\end{table}
Table 1. Methods and desired explanation properties. A question mark (?) means “unclear”, or “maybe, after non-trivial extensions”. “Rec. Exp.” stands for the general recommendation explanation methods.

\begin{table}
\begin{tabular}{l|l} \hline \hline Notation & Definition and description \\ \hline \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) & a heterogeneous graph \(\mathcal{G}\), node set \(\mathcal{V}\), and edge set \(\mathcal{E}\) \\ \(\phi:\mathcal{V}\rightarrow\mathcal{A}\) & a node type mapping function \\ \(\tau:\mathcal{E}\rightarrow\mathcal{R}\) & an edge type mapping function \\ \(D_{u}\) & the degree of node \(v\in\mathcal{V}\) \\ \(\mathcal{E}^{r}\) & edges with type \(r\in\mathcal{R}\), i.e., \(\mathcal{E}^{r}=\{e\in\mathcal{E}|\tau(e)=r\}\) \\ \((\Phi,\cdot,\cdot)\) & the GNN-based LP model to explain \\ \((s,t)\) & the source and target node for the predicted link \\ \(\mathbf{h}_{s}\triangleq\mathbf{h}_{t}\) & the node representations for \(s\triangleq t\) \\ \(Y=\Phi(\mathcal{G},(s,t))\) & the link prediction of the node pair \((s,t)\) \\ \(\mathcal{G}_{c}=(\mathcal{V}_{c},\mathcal{E}_{c})\) & the computation graph, i.e., L-hop ego-graph of \((s,t)\) \\ \hline \hline \end{tabular}
\end{table}
Table 2. Notation table
be estimated using random graph approximations. The next proposition on random graphs shows that the expected number of paths grows strictly slower than the expected number of edge-induced subgraphs as the random graph grows. Also, the expected number of paths becomes insignificant for large graphs.

**Proposition 4.1**.: _Let \(\mathcal{G}(n,d)\) be a random graph with \(n\) nodes and density \(d\), i.e., there are \(m=dbinom{n}{2}\) edges chosen uniformly randomly from all node pairs. Let \(Z_{n,d}\) be the expected number of paths between any pair of nodes. Let \(S_{n,d}\) be the expected number of edge-induced subgraphs. Then \(Z_{n,d}=o(S_{n,d})\), i.e., \(\lim_{n\to\infty}\frac{Z_{n,d}}{S_{n,d}}=0\)._

Proof.: In Appendix A.

Paths are also a natural choice for LP explanations on heterogeneous graphs. On homogeneous graphs, features are important for prediction and explanation. A \(s\)-\(t\) link may be predicted because of the feature similarity of node \(s\) and node \(t\). However, the heterogeneous graphs we focus on, as defined in Definition 3.1, often do not store feature information but explicitly model it using new node and edge types. For example, for the heterogeneous graph in Figure 2(a), instead of making it a user-item graph and assigning each item node a two-dimensional feature with attributes \(a^{1}\) and \(a^{2}\), the attribute nodes are explicitly created and connected to the item nodes. Then an explanation like "\(i_{1}\) and \(i_{2}\) share node feature \(a_{1}^{1_{*}}\) on a homogeneous graph is transferred to "\(i_{1}\) and \(i_{2}\) are connected through the attribute node \(a_{1}^{1_{*}}\) on a heterogeneous graph.

Given the advantages of paths over general subgraphs on connection interpretability, scalability, and their capability to capture feature similarity on heterogeneous graphs, we use paths to explain GNNs for heterogeneous LP. Our design principle is that a good explanation should be concise and informative, so we define the explanation to contain only _short_ paths _without high-degree_ nodes. Long paths are less desirable since they could correspond to unnecessarily complicated connections, making the explanation neither concise nor convincing. For example, in Figure 2(c), the long path \((u_{1},i_{3},a_{2}^{1},i_{2},a_{1}^{1},i_{1})\) is not ideal since it takes four hops to go from item \(i_{3}\) to the item \(i_{1}\), making it less persuasive to be interpreted as "item1 and item3 are similar so item1 should be recommended". Paths containing high-degree nodes are also less desirable because high-degree nodes are often generic, and a path going through them is not as informative. In the same figure, all paths containing node \(a_{2}^{1}\) are less desirable because \(a_{2}^{1}\) has a high degree and connects to all the items in the graph. A real example of a generic attribute is the attribute "grocery" connecting to both "vanilla ice cream" and "vanilla cookie". When "vanilla ice cream" is recommended to a person who bought "vanilla cookie", explaining this recommendation with a path going through "grocery" is not very informative since "grocery" connects many items. In contrast, a good informative path explanation should go through the attribute "vanilla", which only connects to vanilla-flavored items and has a much lower degree.

We formalize the GNN explanation for heterogeneous LP as:

**Problem 4.2**.: Generating path-based explanations for a predicted link between node \(s\) and \(t\):

* a trained GNN-based LP model \(\Phi(\cdot,\cdot)\),
* a heterogeneous computation graph \(\mathcal{G}_{c}\) of \(s\) and \(t\),
* a budget \(B\) of the maximum number of edges in the explanation,
* **Find** an explanation \(\mathcal{P}=\{p|p\) is a \(s\)-\(t\) path with maximum length \(l_{max}\) and degree of each node less than \(D_{max}\}\), \(|\mathcal{P}|l_{max}\leq B\),
* **By optimizing \(p\in\mathcal{P}\)** to be influential to the prediction, concise, and informative.

## 5. Proposed Method: Page-Link

This section details PaGE-Link. PaGE-Link has two modules: (i) a \(k\)-core pruning module to eliminate spurious neighbors and improve speed, and (ii) a heterogeneous path-enforcing mask learning module to identify important paths. An illustration is in Figure 3.

### The k-core Pruning

The _\(k\)-core pruning_ module of PaGE-Link reduces the complexity of \(\mathcal{G}_{c}\). The \(k\)-core of a graph is defined as the unique maximal subgraph with a minimum node degree \(k\)((k)\)(Barb et al., 2016). We use the superscript \(k\) to denote the \(k\)-core, i.e., \(\mathcal{G}_{c}^{k}=(\mathcal{G}_{c}^{k},\mathcal{V}_{c}^{k})\) for the \(k\)-core of \(\mathcal{G}_{c}\). The \(k\)-core pruning is a recursive algorithm that removes nodes \(v\in\mathcal{V}\) such that their degrees \(D_{v}<k\), until the remaining subgraph only has nodes with \(D_{v}\geq k\), which gives the \(k\)-core. The difference in nodes between a (\(k+1\))-core and a \(k\)-core is called the \(k\)-shell. The nodes in the orange box of Figure 2(b) is an example of a \(2\)-core pruned from the \(2\)-hop ego-graph, where node \(a_{1}^{2}\) and \(a_{2}^{2}\) are pruned in the first iteration because they are degree one. Node \(i\)s is recursively pruned because it becomes degree one after node

Figure 3. PaGE-Link on a graph with user nodes \(u\), item nodes \(i\), and two attribute types \(a^{1}\) and \(a^{2}\). (Best viewed in color.)
is pruned. All those three nodes belong to the 1-shell. We perform \(k\)-core pruning to help path finding because the pruned \(k\)-shell nodes are unlikely to be part of meaningful paths when \(k\) is small. For example, the 1-shell nodes are either leaf nodes or will become leaf nodes during the recursive pruning, which will never be part of a path unless \(s\) or \(t\) are one of these 1-shell nodes. The \(k\)-core pruning module in PaGE-Link is modified from the standard \(k\)-core pruning by adding a condition of never pruning \(s\) and \(t\).

The following theorem shows that for a random graph \(\mathcal{G}(n,d)\), \(k\)-core will reduce the expected number of nodes by a factor of \(\delta_{\mathcal{V}}(n,d,k)\) and reduce the expected number of edges by a factor of \(\delta_{\mathcal{E}}(n,d,k)\). Both factors are functions of \(n\), \(d\), and \(k\). We defer the exact expressions of these two factors in Appendix B, since they are only implicitly defined based on Poisson distribution. Numerically, for a random \(\mathcal{G}(n,d)\) with average node degree \(d(n-1)=7\), its 5-core has \(\delta_{\mathcal{V}}(n,d,5)\) and \(\delta_{\mathcal{E}}(n,d,5)\) both \(\approx 0.69\).

**Theorem 5.1** (Pittel, Spencer and Wormald (Pittel, Spencer and Wormald, 2015)).: _Let \(\mathcal{G}(n,d)\) be a random graph with \(m\) edges as in Proposition 4.1. Let \(\mathcal{G}^{k}(n,d)=(\mathcal{V}^{k}(n,d),\mathcal{E}^{k}(n,d))\) be the nonempty \(k\)-core of \(\mathcal{G}(n,d)\). Then \(\mathcal{G}^{k}(n,d)\) contain \(\delta_{\mathcal{V}}(n,d,k)n\) nodes and \(\delta_{\mathcal{E}}(n,d,k)m\) edges with high probability for large \(n\), i.e., \(|\mathcal{V}^{k}(n,d)|/n\stackrel{{ p}}{{\rightarrow}}\delta_{ \mathcal{V}}(n,d,k)\) and \(|\mathcal{E}^{k}(n,d)|/m\stackrel{{ p}}{{\rightarrow}}\delta_{ \mathcal{E}}(n,d,k)\) (\(\stackrel{{ p}}{{\rightarrow}}\) stands for convergence in probability)._

Proof.: Please refer to Appendix B and (Pittel, Spencer and Wormald, 2015). 

The \(k\)-core pruning helps reduce the graph complexity and accelerates path finding. One concern is whether it prunes too much and disconnects \(s\) and \(t\). We found that such a situation is very unlikely to happen in practice. To be specific, we focus on explaining positively predicted links, e.g. why an item is recommended to a user by the model. Negative predictions, e.g., why an arbitrary item is not recommended to a user by the model, are less useful in practice and thus not in the scope of our explanation. \((s,t)\) node pairs are usually connected by many paths in a practical \(\mathcal{G}\)(Kolmogorov, 2008), and positive link predictions are rarely made between disconnected or weakly-connected \((s,t)\). Empirically, we observe that there are usually too many paths connecting a positively predicted \((s,t)\) instead of no paths, even in the \(k\)-core. Therefore, an optional step to enhance pruning is to remove nodes with super-high degrees. As we discussed in Section 4, high-degree nodes are often generic and less informative. Removing them can be a complement to k-core to further reduce complexity and improve path quality.

### Heterogeneous Path-Enforcing Mask Learning

The second module of PaGE-Link learns heterogeneous masks to find important path-forming edges. We perform mask learning to select edges from the \(k\)-core-pruned computation graph. For notation simplicity in this section, we use \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) to denote the graph for mask learning to save superscripts and subscripts, and \(\mathcal{G}^{k}_{\mathcal{E}}\) is the actual graph in the complete version of our algorithm.

The idea is to learn a mask over all edges of all edge types to select the important edges. Let \(\mathcal{E}^{r}=\{e\in\mathcal{E}|\tau(e)=r\}\) be edges with type \(r\in\mathcal{R}\). Let \(\mathcal{M}=\{\mathcal{M}^{r}\}_{r=1}^{|\mathcal{R}|}\) be learnable masks of all edge types, with \(\mathcal{M}^{r}\in\mathbb{R}^{|\mathcal{E}^{r}|}\) corresponds type \(r\). We denote applying \(\mathcal{M}^{r}\) on its corresponding edge type by \(\mathcal{E}^{r}\odot\sigma(\mathcal{M}^{r})\), where \(\sigma\) is the sigmoid function, and \(\odot\) is the element-wise product. Similarly, we also overload the notation \(\odot\) to indicate applying the set of masks on all types of edges, i.e., \(\mathcal{E}\odot\sigma(\mathcal{M})=\cup_{r\in\mathcal{R}}\{\mathcal{E}^{r} \odot\sigma(\mathcal{M}^{r})\}\). We call the graph with the edge set \(\mathcal{E}\odot\sigma(\mathcal{M})\) a _masked graph_. Applying a mask on graph edges will change the edge weights, which makes GNNs pass more information between nodes connected by highly-weighted edges and less on others. The general idea of mask learning is to learn an \(\mathcal{M}\) that produces high weights for important edges and low weights for others. To learn an \(\mathcal{M}\) that better fits the LP explanation, we measure edge importance from two perspectives: important edges should be both influential for the model prediction and form meaningful paths. Below, we introduce two loss terms \(\mathcal{L}_{pred}\) and \(\mathcal{L}_{path}\) for achieving these two measurements.

\(\mathcal{L}_{pred}\) is to learn to select influential edges for model prediction. The idea is to do a perturbation-based explanation, where parts of the input are considered important if perturbing them changes the model prediction significantly. In the graph sense, if removing an edge \(e\) significantly influences the prediction, then \(e\) is a critical counterfactual edge that should be part of the explanation. This idea can be formalized as maximizing the mutual information between the masked graph and the original graph prediction \(Y\), which is equivalent to minimizing the prediction loss

\[\mathcal{L}_{pred}(\mathcal{M})=-\log P_{\Phi}(Y=1|\mathcal{G}=(\mathcal{V}, \mathcal{E}\odot\sigma(\mathcal{M})),(s,t)). \tag{1}\]

\(\mathcal{L}_{pred}(\mathcal{M})\) has a straightforward meaning, which says the masked subgraph should provide enough information for predicting the missing link \((s,t)\) as the whole graph. Since the original prediction is a constant, \(\mathcal{L}_{pred}(\mathcal{M})\) can also be interpreted as the performance drop after the mask is applied to the graph. A well-masked graph should give a minimum performance drop. Regularizations of the mask entropy and mask norm are often included in \(\mathcal{L}_{pred}(\mathcal{M})\) to encourage the mask to be discrete and sparse.

\(\mathcal{L}_{path}\) is the loss term for \(\mathcal{M}\) to learn to select path-forming edges. The idea is to first identify a set of candidate edges denoted by \(\mathcal{E}_{path}\) (specified below), where these edges can form concise and informative paths, and then optimize \(\mathcal{L}_{path}(\mathcal{M})\) to enforce the mask weights for \(e\in\mathcal{E}_{path}\) to increase and mask weights for \(e\notin\mathcal{E}_{path}\) to decrease. We considered a weighted average of these two forces balanced by hyperparameters \(\alpha\) and \(\beta\),

\[\mathcal{L}_{path}(\mathcal{M})=-\sum_{r\in\mathcal{R}}(\alpha\sum_{ \begin{subarray}{c}e\in\mathcal{E}_{path}\\ \tau(e)=r\end{subarray}}\mathcal{M}^{r}_{e}-\beta\sum_{\begin{subarray}{c}e \in\mathcal{E},\mathcal{E}\notin\mathcal{E}_{path}\\ \tau(e)=r\end{subarray}}\mathcal{M}^{r}_{e}). \tag{2}\]

The key question for computing \(\mathcal{L}_{path}(\mathcal{M})\) is to find a good \(\mathcal{E}_{path}\) containing edges of concise and informative paths. As in Section 4, paths with these two desired properties should be short and without high-degree generic nodes. We thus define a score function of a path \(p\) reflecting these two properties as below

\[Score(p) =\log\prod_{\begin{subarray}{c}e\in p\\ \mathbf{e}=(u,\sigma)\end{subarray}}\frac{P(e)}{D_{o}}=\sum_{\begin{subarray}{c}e \in p\\ e=(u,\sigma)\end{subarray}}Score(e), \tag{4}\] \[Score(e) =\log\sigma(\mathcal{M}^{r}_{e}(e))-\log(D_{b}). \tag{3}\]

In this score function, \(\mathcal{M}\) gives the probability of \(e\) to be included in the explanation, i.e., \(P(e)=\sigma(\mathcal{M}^{r}_{e}(e))\). To get the importance of a path, we first use a mean-field approximation for the joint probability by multiplying \(P(e)\) together, and we normalize each
\(P(\epsilon)\) for edge \(e=(u,e)\) by its target node degree \(D_{v}\). Then, we perform log transformation, which improves numerical stability for multiplying many edges with small \(P(e)\) or large \(D_{v}\) and break down a path score to a summation of edge scores \(Score(e)\) that are easier to work with. This path score function captures both desired properties mentioned above. A path score will be high if the edges on it have high probabilities and these edges are linked to nodes with low degrees. Finding paths with the highest \(Score(p)\) can be implemented using Dijkstra's shortest path algorithm (Dijkstra, 2007), where the distance represented by each edge is set to be the negative score of the edge, i.e., \(-Score(e)\). We let \(\mathcal{E}_{path}\) be the set of edges in the top five shortest paths found by Dijkstra's algorithm.

### Mask Optimization and Path Generation

We optimize \(\mathcal{M}\) with both \(\mathcal{L}_{pred}\) and \(\mathcal{L}_{path}\). \(\mathcal{L}_{pred}\) will increase the weights of the prediction-influential edges. \(\mathcal{L}_{path}\) will further increase the weights of the path-forming edges that are also highly weighted by the current \(\mathcal{M}\) and decrease other weights. Finally, after the mask learning converges, we run one more shortest-path algorithm to generate paths from the final \(\mathcal{M}\) and select the top paths according to budget \(B\) to get the explanation \(\mathcal{P}\) defined in Section 4. A pseudo-code of PaGE-Link is shown in Algorithm 1.

```
Input: heterogeneous graph \(\mathcal{G}\), trained GNN-based LP model \(\Phi(\cdot,\cdot)\), predicted link \((s,t)\), size budget \(B\), k for k-core, hyperparameters \(\alpha\) and \(\beta\), learning rate \(\eta\), maximum iterations \(T\). Output: Explanation as a set of paths \(\mathcal{P}\). Extract the computation graph \(\mathcal{G}_{c}\); Prune \(\mathcal{G}_{c}\) for the k-core \(\mathcal{G}_{c}^{k}\); Initialize \(\mathcal{M}^{(0)}\); \(t=0\); while\(\mathcal{M}^{(t)}\) not converge and \(t<T\)do  Compute \(\mathcal{L}_{pred}(\mathcal{M}^{(t)})\); \(\triangleright\) Eq.(1)  Compute \(Score(e)\) for each edge \(e\); \(\triangleright\) Eq.(4)  Construct \(\mathcal{E}_{path}\) by finding shortest paths on \(\mathcal{G}_{c}^{k}\) with edge distance \(-Score(e)\);  Compute \(\mathcal{L}_{path}(\mathcal{M}^{(t)})\) according to \(\mathcal{E}_{path}\); \(\triangleright\) Eq.(2) \(\mathcal{M}^{(t+1)}=\mathcal{M}^{(t)}-\eta\nabla(\mathcal{L}_{pred}(\mathcal{M}^ {(t)})+\mathcal{L}_{path}(\mathcal{M}^{(t)}))\); t \(\leftarrow\) 1; endwhile \(\mathcal{P}\) = Under budget \(B\), the top shortest paths on \(\mathcal{G}_{c}^{k}\) with edge distance \(-Score(e)\); Return:\(\mathcal{P}\).
```

**Algorithm 1** PaGE-Link

### Complexity Analysis

In Table 3, we summarize the time complexity of PaGE-Link and representative existing methods for explaining a prediction with computation graph \(\mathcal{G}_{c}=(\mathcal{V}_{c},\mathcal{E}_{c})\) on a full graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\). Let \(T\) be the mask learning epochs. GNNExplainer has complexity \(|\mathcal{E}_{c}|T\) as it learns a mask on \(\mathcal{E}_{c}\). PGExplainer has a training stage and an inference stage (separated by \(/\) in the table). The inference stage is linear in \(|\mathcal{E}_{c}|\), but the training stage covers edges in the entire graph and thus scales in \(O(|\mathcal{E}|T)\). SubgraphX has a much higher time complexity exponential in \(|\mathcal{V}_{c}|\), so a size budget of \(B_{node}\) nodes is forced to replace \(|\mathcal{V}_{c}|\), and \(\hat{D}=\max_{q\in\mathcal{V}}D_{q}\) denotes the maximum degree (derivation in Appendix). For PaGE-Link, the k-core pruning step is linear in \(|\mathcal{E}_{c}|\). The mask learning with Dijkstra's algorithm has complexity \(|\mathcal{E}_{c}^{k}|T\). PaGE-Link has a better complexity than existing methods since \(|\mathcal{E}_{c}^{k}|\) is usually smaller than \(|\mathcal{E}_{c}|\) (see Theorem 5.1), and PaGE-Link often converges faster, i.e., has a smaller \(T\), as the space of candidate explanations is smaller (see Proposition 4.1) and noisy nodes are pruned.

## 6. Experiments

In this section, we conduct empirical studies to evaluate explanations generated by PaGE-Link. Evaluation is a general challenge when studying model explainability since standard datasets do not have ground truth explanations. Many works (Zhu et al., 2017; Wang et al., 2018) use synthetic benchmarks, but no benchmarks are available for evaluating GNN explanations for heterogeneous LP. Therefore, we generate an augmented graph and a synthetic graph to evaluate explanations. They allow us to generate ground truth explanation patterns and evaluate explainers quantitatively.

### Datasets

_The augmented graph._AugCitation is constructed by augmenting the AMiner citation network (Zhu et al., 2017). A graph schema is shown in Figure 3(a). The original AMiner graph contains four node types: author, paper, reference (ref), and field of study (fos), and edge types "cites", "writes", and "in". We construct AugCitation by augmenting the original graph with new (author, paper) edges typed "likes" and define a paper recommendation task on AugCitation for predicting the "like" edges. A new edge \((s,t)\) is augmented if there is at least one concise and informative path \(p\) between them. In our augmentation process, we require the paths \(p\) to have lengths shorter than a hyperparameter \(l_{max}\) and with degrees of nodes on \(p\) (excluding \(s\)\(\&\)\(t\)) bounded by a hyperparameter \(D_{max}\). We highlight these two hyperparameters because of the conciseness and informativeness principles discussed in Section 4. The augmented edge \((s,t)\) is used for prediction. The ground truth explanation is the set of paths satisfying the two hyperparameter requirements. We only take the top \(P_{max}\) paths with the smallest degree sums if there are many qualified paths. We train a GNN-based LP model to predict these new "likes" edges and evaluate explainers by comparing their output explanations with these path patterns as ground truth.

_The synthetic graph._UserItemAttr is generated to mimic graphs with users, items, and attributes for recommendations. Figure 3(b) shows the graph schema and illustrates the generation process. We include three node types: "user", "item", and item attributes ("attr") in the synthetic graph, and we build different types of edges step by step. Firstly, the "has" edges are created by randomly connecting items to attrs, and the "hidden prefers" edges are created by randomly connecting users to attrs. These edges represent items having attributes and user preferences for these attributes. Next,

\begin{table}
\begin{tabular}{l c c|c} \hline \hline GNNExp (Zhu et al., 2017) & PGExp (Zhu et al., 2017) & SubgraphX (Wang et al., 2018) & PaGE-Link (ours) \\ \hline \(O(|\mathcal{E}_{c}|T)\) & \(O(|\mathcal{E}|T)\) / \(O(|\mathcal{E}_{c}|)\) & \(\Theta(|\mathcal{V}_{c}|\hat{D}^{B_{node}-e})\) & \(O(|\mathcal{E}_{c}|+|\mathcal{E}_{c}^{k}|T)\) \\ \hline \hline \end{tabular}
\end{table}
Table 3. Time complexity of PaGE-Link and other methods.
we randomly sample a set of items for each user, and we connect a (user, item) pair by a "buys" edge, if the user "hidden prefers" any attr the item "has". The "hidden prefers" edges correspond to an intermediate step for generating the observable "buys" edges. We remove the "hidden prefers" edges after "buys" edges are generated since we cannot observe "hidden prefers" information in reality. An example of the rationale behind this generation step is that items have certain attributes, like the item "ice cream" with the attribute "vanilla". Then given that a user likes the attribute "vanilla" as hidden information, we observe that the user buys "vanilla ice cream". The next step is to generate more 'buys" edges between randomly picked (user, item) pairs if a similar user (two users with many shared item neighbors) buys this item. The idea is like collaborative filtering, which says similar users tend to buy similar items. The final step is generating edges for prediction and their corresponding ground truth explanations, which follows the same augmentation process described above for AugCitation. For UserItemAttr, we have "has" and "buys" as base edges to construct the ground truth, and we create "likes" edges between users and items for prediction.

### Experiment Settings

The GNN-based LP modelAs described in Section 3, the LP model involves a GNN encoder and a prediction head. We use RGCN (Zhu et al., 2017) as the encoder to learn node representations on heterogeneous graphs and the inner product as the prediction head. We train the model using the cross-entropy loss. On each dataset, our prediction task covers one edge type \(r\). We randomly split the observed edges of type \(r\) into train:validation:test = 7:1:2 as positive samples and draw negative samples from the unobserved edges of type \(r\). Edges of other types are used for GNN message passing but not prediction.

Explainer baselinesExisting GNN explanation methods cannot be directly applied to heterogeneous LP. Thus, we extend the popular GNNExplainer (Zhu et al., 2017) and PGExplainer (Zhu et al., 2017) as our baselines. We re-implement a heterogeneous version of their mask matrix and mask predictor similar to the heterogeneous mask learning module in PaGE-Link. For these baselines, we perform mask learning using their original objectives, and we generate edge-induced subgraph explanations from their learned mask. We refer to these two adapted explainers as GNNExp-Link and PGExp-Link below. We do not compare to other search-based explainers like SubgraphX (Zhu et al., 2017) because of their high computational complexity (see Section 5.4). They work well on small graphs as in the original papers, but they are hard to scale to large and dense graphs we consider for LP.

### Evaluation Results

Quantitative evaluationBoth the ground truth and the final explanation output of PaGE-Link are sets of paths. In contrast, the baseline explainers generate edge masks \(\mathcal{M}\). For a fair comparison, we take the intermediate result PaGE-Link learned, also the mask \(\mathcal{M}\), and we follow (Zhu et al., 2017) to compare explainers by their masks. Specifically for each computation graph, edges in the ground truth paths are treated as positive, and other edges are treated as negative. Then weights in \(\mathcal{M}\) are treated as the prediction scores of edges and are evaluated with the ROC-AUC metric. A high ROC-AUC score reflects that edges in ground truth are precisely captured by the mask. The results are shown in Table 4, where PaGE-Link outperforms both baseline explainers.

For scalability, we showed PaGE-Link scales linearly in \(O(|\mathcal{E}_{c}^{k}|)\) in Section 5.4. Here we evaluate its scalability empirically by generating ten synthetic graphs with various sizes from 20 to 5,500 edges in \(\mathcal{G}_{c}\). The results are shown in Figure 1(b), which suggests the computation time scales linearly in the number of edges.

Qualitative evaluationA critical advantage of PaGE-Link is that it generates path explanations, which can capture the connections between node pairs and enjoy better interpretability. In contrast, the top important edges found by baseline methods are often disconnected from the source, the target, or both, which makes their explanations hard for humans to interpret and investigate. We conduct case studies to visualize explanations generated by PaGE-Link on the paper recommendation task on AugCitation.

Figure 5 shows a case in which the model recommends the source author "Vipin Kumar" the recommended target paper titled "Fast

\begin{table}
\begin{tabular}{l c c|c} \hline \hline  & GNNExp-Link & PGExp-Link & PaGE-Link (ours) \\ \hline AugCitation & 0.829 & 0.586 & **0.928** \\ UserItemAttr & 0.608 & 0.578 & **0.954** \\ \hline \hline \end{tabular}
\end{table}
Table 4. ROC-AUC scores on learned masks. PaGE-Link outperforms baselines.

Figure 4. The proposed augmented graph AugCitation and the synthetic graph UserItemAttr.
and exact network trajectory similarity computation: a case-study on bicycle corridor planning". The top path explanation generated by PaGE-Link goes through the coauthor "Shashi Shekhar", which explains the recommendation as Vipin Kumar and Shashi Shekhar coauthored the paper "Correlation analysis of spatial time series datasets: a filter-and-refine approach", and Shashi Shekhar wrote the recommended paper. Given the same budget of three edges, explanations generated by baselines are less interpretable.

Figure 6 shows another example with the source author "Huan Liu" and the recommended target paper titled "Using association rules to solve the cold-start problem in recommender systems". PaGE-Link generates paths going through the common fos of the recommended paper and three other papers written by Huan Liu: _p22646_, _p25160_, and _p35294_. We show the PaGE-Link explanation with the top three paths in green. We also show other unexpected fos shared by the _p22646_, _p25160_, and _p35294_ and the target paper. Note that the explanation paths all have length three, even though there are many paths with length five or longer, e.g., \((a328,p22646,f4,p25260,f4134,p5670)\). Also, the explanation paths go through the fos "Redundancy (engineering)" and "User profile" instead of generic fos like "Artificial intelligence" and "Computer science". This case demonstrates that explanation paths selected by PaGE-Link are more concise and informative.

## 7. Human Evaluation

The ultimate goal of model explanation is to improve model transparency and help human decision-making. Human evaluation is thus the best way to evaluate the effectiveness of an explainer, which has been a standard evaluation approach in previous works (Granter et al., 2017; Wang et al., 2018; Wang et al., 2018). We conduct a human evaluation by randomly picking 100 predicted links from the test set of AugCitation and generate explanations for each link using GNNExp-Link, PGExp-Link, and PaGE-Link. We design a survey with single-choice questions. In each question, we show respondents the predicted link and those three explanations with both the graph structure and the node/edge type information, similarly as in Figure 5 but excluding method names. The survey is sent to people across graduate students, postdocs, engineers, research scientists, and professors, including people with and without background knowledge about GNNs. We ask respondents to "please select the best explanation of '_why the model predicts this author will like the recommended paper?_". At least three answers from different people are collected for each question. In total, 340 evaluations are collected and 78.79% of them selected explanations by PaGE-Link as the best.

## 8. Conclusion

In this work, we study model transparency and accountability on graphs. We investigate a new task: GNN explanation for heterogeneous LP. We identify three challenges for the task and propose a new path-based method, i.e. PaGE-Link, that produces explanations with _interpretable connections_, is _scalable_, and handles graph _heterogeneity_. PaGE-Link explanations quantitatively improve ROC-AUC by 9 - 35% over baselines and are chosen by 78.79% responses as qualitatively more interpretable in human evaluation.

###### Acknowledgements.

 We thank Ziniu Hu for the helpful discussions on this work. This work is partially supported by NSF (2211557, 1937599, 2119643), NASA, SRC, Okawa Foundation Grant, Amazon Research Awards, Cisco Research Grant, Picsart Gifts, and Snapchat Gifts.

Figure 5. Explanations (green arrows) by different explainers for the predicted link (\(a2367,p16200\)) (dashed red). PaGE-Link explanation explains the recommendation by co-authorship, whereas baseline explanations are less interpretable.

Figure 6. Top three paths (green arrows) selected by PaGE-Link for explaining the predicted link (\(a328,p5670\)) (dashed red). The selected paths are short and do not go through a generic field of study like “Computer Science”.