TL;DR
This paper introduces SE-SGformer, a novel self-explainable graph transformer designed for link sign prediction in signed graphs. It addresses the critical need for explainability in signed graph neural networks (SGNNs) by not only predicting link signs but also providing interpretable reasons for its predictions, outperforming existing methods in both accuracy and explainability.
What Problem Does This Paper Address?
Signed graphs, where relationships between entities can be positive or negative (like friendships and rivalries, or trust and distrust), are prevalent in real-world scenarios. Signed Graph Neural Networks (SGNNs) are powerful tools for analyzing these graphs, particularly for tasks like predicting the sign of unknown links. However, a major hurdle for SGNN adoption in critical domains (e.g., finance, social networks) is their "black box" nature – they lack explainability. Understanding why a link is predicted as positive or negative is crucial for trust and decision-making. Existing explainability methods for general graph neural networks are often "post-hoc," meaning they analyze a trained model after the fact, which can lead to biased or inaccurate explanations. This paper tackles the problem of creating SGNNs that are inherently explainable, generating predictions and their justifications simultaneously.
Methods
The core of the proposed solution is the SE-SGformer framework, which combines a novel graph transformer encoder with a unique explainable prediction module.
Encoding Module: * Transformer Architecture: The framework leverages a Transformer architecture, adapted for graphs. * Novel Encodings: To capture the rich structure of signed graphs, SE-SGformer introduces three key encodings: * Centrality Encoding: This encoding incorporates node degrees (both positive and negative) to reflect a node's importance. * Adjacency Matrix Encoding: This directly injects information about immediate positive and negative neighbors into the self-attention mechanism. * Signed Random Walk Encoding: This is a key innovation. Unlike shortest path encodings, it uses multiple random walks on the signed graph to capture multi-hop relationships and the relative positions of nodes, theoretically proving to be more expressive than shortest path encoding for signed graphs.
Explainable Prediction Module: * K-Nearest/Farthest Neighbors: Instead of a traditional neural network decoder, SE-SGformer uses an explainable approach. For a link between nodes $v_i$ and $v_j$, it identifies the $K$ nearest positive neighbors and $K$ farthest negative neighbors of $v_i$. * Similarity-Based Prediction: The sign of the edge $(v_i, v_j)$ is predicted by comparing the distance between $v_i$ and $v_j$ to the median distances between $v_i$ and its identified positive/negative neighbors. If $v_i$'s distance to $v_j$ is closer to its positive neighbors' distances, the link is predicted as positive; otherwise, it's predicted as negative. The identified neighbors serve as the explanation. * Diffusion Matrix (SRWR): To address the issue of nodes having few or no negative neighbors, a signed random walk with restart (SRWR) diffusion matrix is used to uncover potential negative relationships.
Datasets
The paper evaluates SE-SGformer on eight real-world signed graph datasets:
- Amazon-music
- Epinions
- KuaiRand
- KuaiRec
- WikiRfa
- WikiElec
- Bitcoin-OTC
- Bitcoin-Alpha
These datasets represent various domains where signed relationships are meaningful.
Key Insights and Ideas
- Self-Explainability is Achievable for SGNNs: The paper demonstrates that it's possible to build SGNNs that inherently provide explanations alongside predictions, moving beyond post-hoc methods.
- Signed Random Walks are Powerful: The theoretical analysis and experimental results highlight that signed random walk encoding is more expressive than traditional shortest path encoding for capturing complex relationships in signed graphs, especially in unbalanced cycles.
- Neighbor-Based Explanations are Intuitive and Effective: Using K-nearest positive and K-farthest negative neighbors as the basis for prediction and explanation provides a clear, human-understandable rationale for the model's decisions.
- Addressing Data Imbalance is Crucial: The paper acknowledges and addresses the common issue of sparse negative links in signed graphs, using techniques like the diffusion matrix to improve model performance and explainability.
Key Results
- Prediction Accuracy: SE-SGformer outperforms several state-of-the-art methods, achieving up to a 2.2% improvement in prediction accuracy on some datasets.
- Explanation Accuracy: The model demonstrates significantly better explainability, with up to a 73.1% improvement in explanation accuracy (measured by precision@K) in the best-case scenario.
- Component Effectiveness: Ablation studies show that removing any of the three proposed encodings (centrality, adjacency matrix, or signed random walk) leads to a consistent decrease in performance, underscoring the importance of each component. The adjacency matrix encoding was found to be particularly crucial.
- Parameter Sensitivity: The model shows relatively stable performance across variations in key hyperparameters like max degree and embedding dimension, with a slight performance decrease when the number of Transformer layers increases beyond one.
Limitations and Future Work
- Limitations:
- The paper notes that while SE-SGformer performs well, the performance can be affected by the scarcity of negative edges in some datasets.
- The current explanation relies on identifying neighbors, which might not capture all nuances of complex relationships.
- Future Work:
- The authors anticipate further research in the area of explainability for link sign prediction.
- Exploring more sophisticated methods for identifying informative neighbors and refining the explanation generation process could be future directions.
- Investigating the application of SE-SGformer to other downstream tasks on signed graphs is also a potential avenue.
Summary updated