Introduction
Graph Neural Networks (GNNs) have become the state-of-the-art for link prediction (LP) tasks, powering critical applications like recommendation engines and knowledge graph completion. However, the "black box" nature of these models poses significant challenges for transparency and accountability. While several tools exist for explaining GNN predictions in node or graph classification, they often fall short when applied to link prediction.
We present PaGE-Link (Path-based GNN Explanation for heterogeneous Link prediction), a novel framework designed to explain GNN link predictions by identifying the most influential paths between nodes. Unlike traditional methods that produce arbitrary subgraphs, PaGE-Link focuses on paths, offering a more interpretable and scalable approach for complex heterogeneous graphs.
The Challenge of Link Prediction Explanation
Explaining link prediction is inherently more difficult than explaining node classification for three primary reasons:
- Connection Interpretability: Existing explainers often generate subgraphs that are disconnected from the source or target nodes, failing to provide a clear "bridge" that explains the relationship.
- Scalability: The search space for subgraphs in link prediction is exponentially larger, as it involves the neighborhoods of two nodes rather than one.
- Heterogeneity: Real-world graphs are often heterogeneous, containing multiple types of nodes and edges. Standard explainers are typically designed for homogeneous graphs and struggle with this complexity.
Methodology
PaGE-Link addresses these challenges through a three-stage pipeline:
1. k-core Pruning
To manage the computational complexity of large-scale graphs, PaGE-Link first prunes the computation graph—the local neighborhood surrounding the two nodes of interest. By removing peripheral nodes unlikely to contribute to a meaningful connection, the algorithm significantly reduces the search space while preserving critical structural information.
2. Path-Enforcing Mask Learning
The core of PaGE-Link is a mask learning process that assigns importance weights to edges. The model optimizes a dual-objective loss function. One component ensures that the selected edges are influential to the GNN's prediction via perturbation. The second, "path-enforcing" component, encourages the mask to form concise, connected paths between the source and target nodes.
3. Informativeness Scoring
To ensure explanations are meaningful, PaGE-Link incorporates an informativeness scoring function. This function penalizes paths that pass through high-degree "generic" nodes (e.g., broad categories like "Electronics"), favoring more specific and informative connections (e.g., a specific brand or niche attribute) that provide better insight into the model's reasoning.
Experimental Evaluation
Due to the lack of standard benchmarks for link prediction explanation, the authors introduced two new datasets:
- AugCitation: An augmented version of the AMiner citation network where ground-truth explanations are defined by known path patterns, such as shared co-authors.
- UserItemAttr: A synthetic dataset mimicking recommendation systems, where links are generated based on clear, pre-defined attribute-based reasons.
Results and Discussion
PaGE-Link demonstrates significant improvements over adapted baselines like GNNExplainer and PGExplainer across several dimensions:
- Accuracy: PaGE-Link achieved an explanation AUC improvement of 9% to 35% over existing methods, indicating a much higher fidelity in identifying ground-truth influential edges.
- Human Interpretability: In a user study involving 340 evaluations, 78.79% of participants preferred PaGE-Link's path-based explanations, citing them as more helpful and easier to understand than subgraph-based alternatives.
- Scalability: The framework exhibits linear scalability with respect to the number of edges in the graph, making it suitable for real-world, large-scale production environments.
Conclusion
PaGE-Link represents a significant step forward in making GNN-based link prediction models more transparent. By prioritizing paths as the "natural language" of links, it provides explanations that are not only more accurate but also more aligned with human intuition. While currently focused on explaining positive predictions, future work will explore explaining negative predictions and handling dynamic or temporal graph structures.
Summary updated