SPINE: Structural Identity Preserved Inductive Network Embedding

Junliang Guo, Linli Xu, Jingchang Liu

Introduction

Network embedding has become a cornerstone of graph analysis, enabling tasks like node classification and link prediction by mapping nodes into low-dimensional vector spaces. However, most traditional methods focus primarily on local proximity—the idea that nodes connected in a graph should be close in the embedding space. This approach often overlooks structural identity, where nodes performing similar roles (e.g., "influencers" or "hubs") should be embedded similarly even if they are located in distant parts of the network.

SPINE (Structural Identity Preserved Inductive Network Embedding) addresses this gap by introducing a framework that captures both local neighborhoods and global structural roles. Crucially, SPINE is inductive, allowing it to generate embeddings for new nodes or entirely unseen graphs without the need for costly retraining.

The Challenge: Local Proximity vs. Structural Identity

Standard embedding techniques are often transductive, meaning they learn a fixed lookup table for a specific graph. When the network evolves or a new node is added, the entire model must be re-run. Furthermore, by focusing only on direct connections, these models fail to recognize nodes with identical structural signatures that are not directly connected.

Structural identity vs. local proximity: Nodes with similar roles (yellow) should be embedded closely regardless of network distance.

As illustrated in Figure 1, "opinion leaders" in separate communities may share the same structural role. SPINE aims to map these nodes to similar coordinates, preserving their functional identity across the global network.

The SPINE Framework

The authors propose a three-stage pipeline to integrate structural identity into an inductive framework:

  1. Structural Feature Generation: To capture a node's global position efficiently, SPINE utilizes Rooted PageRank (RPR). The authors prove that RPR is a "complete" structural property, containing sufficient information to identify a node's role. To handle large-scale graphs, they employ a Monte Carlo approximation to identify the top-$k$ most structurally relevant neighbors.
  2. Inductive Embedding Generator: Instead of learning static embeddings, SPINE trains a Multi-Layer Perceptron (MLP) as an embedding generator. This MLP takes a node's content features and its RPR-based structural features as input. Because the model learns a function rather than a lookup table, it can generalize to unseen nodes instantly.
  3. Biased SGNS Optimization: The framework adapts Skip-Gram Negative Sampling (SGNS) with a unique biased positive sampling strategy. This ensures that the optimization process occasionally samples structurally similar nodes that are far away in the network, reinforcing the preservation of structural identity.

Experimental Evaluation

SPINE was evaluated against state-of-the-art methods like node2vec, struc2vec, and GraphSAGE across citation networks (Cora, Citeseer, Pubmed), protein-protein interaction (PPI) networks, and social networks (FB-686).

Inductive Performance

In the inductive setting, where the model is tested on nodes not seen during training, SPINE demonstrated significant improvements. On the PPI dataset, which consists of multiple distinct networks, SPINE outperformed GraphSAGE in both micro-F1 and macro-F1 scores.

Node classification performance on the PPI dataset. SPINE achieves higher micro-F1 and macro-F1 scores compared to GraphSAGE and other baselines.

Efficiency and Robustness

Beyond accuracy, SPINE offers remarkable computational efficiency. Inference on datasets like Cora is orders of magnitude faster than attention-based models like GAT. Additionally, the model shows high robustness; using a "mirrored" network test (FB-686), the authors demonstrated that SPINE consistently maps structurally identical nodes closer together than competitors, even when the network structure is perturbed by edge removal.

Conclusion

SPINE represents a significant step forward in network embedding by bridging the gap between local connectivity and global structural roles. Its inductive nature and computational efficiency make it highly suitable for real-world, dynamic applications such as recommendation systems and biological network analysis, where both node roles and scalability are paramount.

Summary updated

Abstract

Recent advances in the field of network embedding have shown that low-dimensional network representation is playing a critical role in network analysis. Most existing network embedding methods encode the local proximity of a node, such as the first- and second-order proximities. While being efficient, these methods are short of leveraging the global structural information between nodes distant from each other. In addition, most existing methods learn embeddings on one single fixed network, and thus cannot be generalized to unseen nodes or networks without retraining. In this paper we present SPINE, a method that can jointly capture the local proximity and proximities at any distance, while being inductive to efficiently deal with unseen nodes or networks. Extensive experimental results on benchmark datasets demonstrate the superiority of the proposed framework over the state of the art.
BibTeX
@inproceedings{guo2019spine,
  author = {Junliang Guo and Linli Xu and Jingchang Liu},
  title = {{SPINE: Structural Identity Preserved Inductive Network Embedding}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/333},
}
Figure