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

Hogun Park, Jennifer Neville

Introduction

Unsupervised node embedding techniques like DeepWalk, node2vec, and LINE have become standard for transforming complex networks into low-dimensional vector representations. Despite their utility, these models remain "black boxes." Unlike supervised Graph Neural Networks (GNNs), which benefit from tools like GNNExplainer, unsupervised embeddings lack robust post-hoc explanation methods. This paper addresses the challenge of identifying which nodes are most influential in shaping the global structure of a learned embedding space.

The Bridgeness Hypothesis

The authors propose that a node's global importance is theoretically tied to its "bridgeness"—its role in connecting disparate clusters within a network. By viewing Skip-gram-based models as implicit matrix factorizations of graph Laplacians, they prove that perturbing high-bridgeness nodes causes the most significant shifts in the resulting embedding space.

GRAPH-wGD: A Scalable Explanation Tool

To identify these influential nodes efficiently, the authors introduce GRAPH-wGD (Weighted Gradient Descent). Traditional methods for calculating spectral bridgeness are computationally prohibitive for large graphs ($O(V^{2.367})$). GRAPH-wGD uses a gradient-based approach to estimate sensitivity.

The GRAPH-wGD pipeline: from input graph to latent space, identifying global explanations like key political figures in a social network.

The core innovation is the "weighted sensitivity" function. By using cosine similarity to identify "support nodes" (neighbors that reinforce a node's bridging role), GRAPH-wGD filters out local noise and focuses on signals that define the graph's global topology.

Key Insight: Degree is Not Importance

A common intuition is that high-degree "hub" nodes are the most important. However, the authors demonstrate that a hub buried within a single cluster has less impact on the global embedding than a lower-degree "bridge" node connecting multiple clusters.

Comparison of perturbations: rewiring a high-degree node (blue) vs. a high-bridgeness node (red). The latter causes a much more significant disruption to the embedding clusters.

As shown in the figure above, perturbing the red bridge node significantly alters the separation of clusters in the latent space, whereas perturbing the blue hub node has a localized effect. This confirms that strategic position (bridgeness) outweighs simple connectivity (degree) in defining global representation.

Results and Efficiency

The researchers validated GRAPH-wGD across five real-world datasets, including BlogCatalog and the Enron email network. Key findings include:

  • Accuracy: GRAPH-wGD scores correlate strongly with true mathematical bridgeness, outperforming baselines like PageRank and LIME.
  • Impact: Perturbing nodes identified by GRAPH-wGD leads to the largest changes in downstream classification performance, proving their influence.
  • Scalability: On the BlogCatalog dataset, GRAPH-wGD generated explanations in just 141 seconds, compared to the hundreds of hours or days required by traditional perturbation or LIME-based methods.

Conclusion

By linking network topology to embedding theory, this work provides a theoretically grounded and computationally efficient way to interpret unsupervised graph models. Identifying bridge nodes not only explains how embeddings are formed but also offers a path toward building more transparent and robust machine learning systems for complex networks.

Summary updated

BibTeX
@article{park2023generating,
  author = {Hogun Park and Jennifer Neville},
  title = {{Generating post-hoc explanations for Skip-gram-based node embeddings by identifying important nodes with bridgeness}},
  journal = {Neural Networks},
  year = {2023},
  doi = {10.1016/j.neunet.2023.04.029},
}
Figure