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.
Introduction
In network analysis, "embedding" a node involves mapping it into a low-dimensional vector space. Traditional methods primarily focus on local proximity, ensuring that neighboring nodes have similar vectors. However, this approach often overlooks structural identity—the phenomenon where nodes far apart in a network play identical roles (e.g., "influencers" in different communities). Furthermore, many existing algorithms are transductive, requiring the entire model to be retrained whenever a new node joins the network.
SPINE (Structural Identity Preserved Inductive Network Embedding) addresses these challenges by capturing both local and global structural information while remaining fully inductive, enabling it to generate embeddings for unseen data with high efficiency and accuracy.
Methodology
The SPINE framework is built upon three core pillars:
- Structural Feature Generation: To capture a node's global role, SPINE utilizes Rooted PageRank (RPR), approximated via Monte Carlo random walks. This creates a "structural fingerprint" that describes a node's relationship to the broader graph, regardless of distance.
- Inductive Embedding Generator: Instead of a static lookup table, SPINE employs a Multilayer Perceptron (MLP). This generator maps a node’s content features and its structural fingerprint to an embedding. This functional approach allows for the immediate processing of new nodes or entirely new networks.
- Biased Skip-Gram Negative Sampling (SGNS): The training process incorporates a novel sampling strategy that pairs nodes based on structural similarity (calculated using Dynamic Time Warping), even if they are topologically distant. This forces the embedding space to respect structural roles.
Experimental Results
The authors evaluated SPINE across citation networks (Citeseer, Cora, Pubmed), biological networks (PPI), and social networks (FB-686).
Structural Identity and the Mirror Test
To evaluate the preservation of structural roles, the authors conducted a "mirror test" using a duplicate network. SPINE successfully mapped nodes and their mirror counterparts to nearly identical locations in the embedding space, significantly outperforming local-only methods.
Computational Efficiency
A key advantage of SPINE is its speed. Because the embedding generation relies on a simple MLP rather than complex neighborhood aggregations (as seen in GraphSAGE or GAT), its inference time is significantly lower.
Robustness and Generalization
In transductive classification, SPINE outperformed unsupervised baselines like node2vec. More impressively, in inductive scenarios where 80% of the network was removed during training, SPINE maintained high accuracy, demonstrating its ability to learn the underlying structural logic of the network rather than just memorizing node positions.
Conclusion
SPINE provides a robust framework for learning network embeddings that respect both local connectivity and global structural roles. Its inductive nature and high inference speed make it particularly suitable for dynamic, large-scale networks. Future work may explore its application in social recommendation systems where identifying user roles is as critical as knowing their direct connections.
Summary updated