Generating post-hoc explanations for Skip-gram-based node embeddings by identifying important nodes with bridgeness.

Area of Science:

• Machine Learning
• Network Science
• Data Mining

Background:

• Node representation learning encodes network structure into vector spaces.
• Unsupervised methods like DeepWalk and LINE excel at downstream tasks but lack explainability.
• Explaining unsupervised embeddings is challenging due to limited methods and theoretical studies.

Purpose of the Study:

• To develop effective methods for post-hoc explanations of unsupervised node embeddings.
• To propose a novel gradient-based explanation technique for graph embeddings.
• To evaluate the efficiency and effectiveness of the proposed explanation method.

Main Methods:

• Global explanations derived from spectral cluster-aware local perturbation and bridgeness computation.
• A novel gradient-based explanation method, GRAPH-wGD, for efficient top-q global explanations.
• Experimental validation on five real-world graphs comparing GRAPH-wGD with existing methods.

Main Results:

• GRAPH-wGD efficiently provides top-q global explanations for learned graph embedding vectors.
• Node rankings by GRAPH-wGD scores correlate highly with true bridgeness scores.
• Top-q explanations from GRAPH-wGD show higher importance and impact on class label prediction compared to alternatives.

Conclusions:

• Global explanations for Skip-gram-based embeddings are achievable via bridgeness computation.
• GRAPH-wGD offers an efficient and effective gradient-based approach for explaining node embeddings.
• The proposed method enhances the interpretability of unsupervised graph representation learning.