Abstract
Embedding a web-scale information network into a low-dimensional vector space facilitates tasks such as link prediction, classification, and visualization. Past research has addressed the problem of extracting such embeddings by adopting methods from words to graphs, without defining a clearly comprehensible graph-related objective. Yet, as we show, the objectives used in past works implicitly utilize similarity measures among graph nodes. In this paper, we carry the similarity orientation of previous works to its logical conclusion; we propose VERtex Similarity Embeddings (VERSE), a simple, versatile, and memory-efficient method that derives graph embeddings explicitly calibrated to preserve the distributions of a selected vertex-to-vertex similarity measure. VERSE learns such embeddings by training a single-layer neural network. While its default, scalable version does so via sampling similarity information, we also develop a variant using the full information per vertex. Our experimental study on standard benchmarks and real-world datasets demonstrates that VERSE, instantiated with diverse similarity measures, outperforms state-of-the-art methods in terms of precision and recall in major data mining tasks and supersedes them in time and space efficiency, while the scalable sampling-based variant achieves equally good results as the non-scalable full variant.
Introduction
Graph embedding—the process of mapping nodes into a low-dimensional vector space—is essential for tasks like link prediction and community detection. However, existing methods often suffer from rigidity. Popular approaches like DeepWalk and Node2vec rely on implicit notions of "neighborhoods" based on random walks, which can make them inflexible. For instance, a model tuned for community detection might fail to capture structural roles, such as identifying that two "hubs" in different parts of a graph are functionally similar.
VERSE (VERtex Similarity Embeddings) addresses this by making the embedding objective explicit: the learned vectors should minimize the difference between a target graph similarity distribution (such as Personalized PageRank or SimRank) and the reconstructed distribution in the embedding space. This allows the model to be tailored to the specific structural properties of interest.
Methodology
The core of VERSE is a single-layer neural network designed to minimize the Kullback-Leibler (KL) divergence between two distributions:
- $sim_G$: The "ground truth" similarity distribution from the graph (e.g., Personalized PageRank).
- $sim_E$: The similarity distribution in the learned embedding space, calculated via the dot product of vertex vectors.
To ensure scalability for massive networks, VERSE utilizes Noise Contrastive Estimation (NCE). Instead of a costly softmax over all nodes, NCE treats the problem as a binary classification task: distinguishing between "real" similar nodes sampled from the graph and "noise" nodes sampled randomly. This approach achieves linear time and space complexity relative to the number of nodes.
Key Results and Performance
The authors evaluated VERSE on six real-world datasets, including massive networks like Orkut (3.1M nodes). VERSE consistently outperformed or matched state-of-the-art methods like Node2vec and LINE across link prediction and node classification tasks while remaining significantly more efficient.
Efficiency and Robustness
- Speed: VERSE processed the Orkut dataset in about 3 hours, whereas competitors took between 6 and 15 hours.
- Memory: The memory footprint is minimal, scaling linearly with the number of nodes.
- Hyperparameters: Unlike Node2vec, which requires extensive grid searches for its parameters, VERSE is robust to its primary hyperparameter (the damping factor $\alpha$ when using PPR), making it easier to deploy in practice.
Conclusion
VERSE demonstrates that vertex similarity is the fundamental "hidden variable" in graph embeddings. By making this objective explicit and utilizing efficient sampling techniques like NCE, VERSE provides a versatile framework that is both more accurate and more scalable than previous heuristic-based methods. Future work includes adapting the framework for dynamic graphs and exploring more complex asymmetric similarity measures.
Summary updated