Source-linked AI summary
VERSE: Versatile Graph Embeddings from Similarity Measures
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Emmanuel Müller
TL;DR
Graph embeddings lacked a clearly defined, flexible objective for preserving the diverse similarities relevant to graph-mining tasks. VERSE explicitly reconstructs distributions of a selected node similarity with a single-layer neural network, and experiments report stronger quality and efficiency than state-of-the-art methods.
Problem
Existing graph-embedding methods lack a universal, tractable objective that flexibly captures diverse node similarities across graph tasks.
Method
VERSE learns graph embeddings by reconstructing each node’s distribution under any selected vertex-to-vertex similarity measure with a single-layer neural network.
Results
VERSE consistently outperforms state-of-the-art graph-embedding approaches across many graph tasks in quality while also improving efficiency.
Takeaways & Limitations
Explicitly grounding embeddings in vertex similarity provides a versatile representation framework that can use task-appropriate measures such as PPR, SimRank, and adjacency similarity.
Takeaways & Limitations
SimRank has computational complexity O(n4) with the straightforward method, and naïve training requires materializing or normalizing similarity information over all nodes.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Graph embeddings need expressive node features, but existing approaches struggle to provide a universal, tractable, and flexible objective. VERSE explicitly learns selected vertex similarities with an efficient neural model intended to support diverse graph tasks.
- Graph mining tasks require expressive features, but manually engineered features are tedious and transfer poorly across tasks.
- Existing embedding approaches face scalability, quality, or flexibility limitations, including dense similarity matrices and rigid local-neighborhood objectives.
- Community structure, node roles, and structural equivalence represent distinct similarities that real-world tasks may require a single embedding method to capture.
- VERSE explicitly learns any chosen node similarity by reconstructing similarity distributions with a simple single-layer neural network.
- VERSE is reported to outperform previous methods in quality and runtime across varied large real-world networks and tasks.
- VERSE can use Personalized PageRank, SimRank, or adjacency similarity, replacing fixed neighborhood assumptions with task-specific similarity selection.
2 RELATED WORK
Related graph-embedding methods trade off scalability, nonlinear modeling, and the ability to represent diverse node similarities. VERSE is positioned as a local, scalable, nonlinear framework that makes similarity choice explicit.
- Traditional spectral and nonlinear dimensionality-reduction methods operate on dense matrices, limiting their applicability to large graphs.
- HOPE supports diverse similarity measures but requires the entire graph matrix and treats embedding as linear dimensionality reduction.
- Neural graph embeddings were inspired by word embeddings, with DeepWalk learning low-dimensional representations from local node neighborhoods and random walks.
- DeepWalk-based methods use objectives not tailored to graph structures, while LINE and Node2vec remain restricted to local neighborhoods.
- Table 1 compares prior methods by algorithmic properties and by the implicit or explicit node similarities they express.
- The related-work criteria include locality, scalability to graphs exceeding 10^6 nodes, and nonlinear transformations.
3 VERSATILE GRAPH EMBEDDING
VERSE learns low-dimensional node embeddings by explicitly preserving distributions from a chosen similarity measure, using a single-layer neural network and scalable sampling. Its framework supports multiple similarities and combines nonlinear reconstruction with favorable scalability and reconstruction quality.
- Embedding objective: VERSE represents each vertex with a d-dimensional embedding and aims to preserve the distribution of a selected graph similarity measure without materializing the full similarity matrix.The target embedding dimension satisfies d ≪ n, and similarities from each vertex are treated as distributions.
- Embedding objective: The model minimizes KL divergence between the given and embedded similarity distributions, using dot-product scores normalized with softmax.The KL objective is converted to cross-entropy, enabling stochastic optimization.
- Reconstruction quality: In a small matrix reconstruction, VERSE preserves most original similarity information, whereas linear SVD fails to differentiate some nodes.The comparison uses the Karate club graph with d = 4 for both methods.
- VERSE algorithm: Noise Contrastive Estimation avoids full normalization by distinguishing similarity-distribution samples from noise samples, with s = 3 used experimentally.Its derivative converges to the cross-entropy gradient as the number of noise samples increases.
- Similarity instantiations: VERSE can instantiate Personalized PageRank, adjacency similarity, or SimRank, thereby supporting different notions of proximity and structural relatedness.Personalized PageRank uses random walks with restart, whereas adjacency similarity captures immediate neighbors and SimRank captures structural relatedness.
- Reconstruction quality: NCE nearly matches exhaustive fVERSE on the ground-truth top-100 similar nodes, while negative sampling does not deliver the same reconstruction quality.The result concerns ranking performance for reconstructing Personalized PageRank similarity.
- Complexity: VERSE has time linear in n for fast sampling and lies at the low end of graph-embedding complexity, while fVERSE remains comparable to some prior methods.The comparison reports average and worst-case time and space complexity; sampled methods can still have quadratic worst-case space.
- Complexity: A damping factor α = 0.95 corresponds to DeepWalk and Node2vec window size w = 39, whose large value prohibitively increases their computation time.The standard α = 0.85 is close to w = 10.
4 EXPERIMENTS
VERSE is evaluated against graph-embedding methods and task-specific baselines across real datasets, with experiments covering link prediction, node classification, graph reconstruction, parameter sensitivity, scalability, and visualization.
- Experimental setup: VERSE is evaluated against DeepWalk, LINE, GraRep, HOPE, Node2vec, logistic regression, and Louvain using real-network datasets and standardized embedding settings.The experiments use six real datasets, 128-dimensional embeddings, repeated evaluation runs, and reported dataset characteristics.
- 4.1 Link Prediction: VERSE with Hadamard edge representations consistently performs best for link prediction, outperforming the baseline, while hsVERSE surpasses Node2vec on all tested datasets.The authors attribute the edge-representation quality to explicit reconstruction using noise contrastive estimation.
- 4.2 Node Classification: VERSE delivers comparable or superior node-classification predictions and scales to large networks, while hsVERSE remains stronger than unsupervised alternatives on YouTube and Orkut where Node2vec exhausts memory.LINE outperforms VERSE only on VK, where direct neighborhood information better captures user gender.
- 4.4 Graph Reconstruction: hsVERSE achieves the highest graph-reconstruction neighborhood accuracy when instantiated with Adjacency Similarity, while fVERSE also improves on sampled VERSE.The result follows the task alignment between Adjacency Similarity and graph reconstruction.
- 4.5 Parameter Sensitivity: Performance grows approximately linearly with embedding dimensionality up to d = 128, while sampled VERSE is comparatively better at low dimensions and degrades beyond 128.Classification accuracy is robust to the damping factor α except at extreme values; α near 0 emphasizes immediate neighborhoods, whereas α near 1 approaches regular PageRank.
- 4.6 Scalability and 4.7 Visualization: VERSE is the most efficient and scalable method in the runtime comparison, processing 10^6 nodes in about three hours versus six to fifteen hours for DeepWalk and LINE.On CoCit visualization, VERSE produces well-separated, low-noise clusters and distinguishes papers within the same community.
5 CONCLUSIONS
VERSE reframes graph embeddings as reconstructing a chosen vertex-similarity distribution, yielding a scalable method with linear time complexity and graph-sized space requirements. Experiments show that VERSE consistently outperforms state-of-the-art graph-embedding approaches across many graph tasks, with a hyperparameter-supervised variant performing even better.
- VERSE reconstructs the distribution of any chosen similarity measure for each graph node.
- Its global graph view substantially reduces the number of parameters required for training.
- Linear time complexity enables VERSE to scale to large real graphs.
- Graph-sized space requirements limit storage needs to the graph itself.
- VERSE consistently outperforms state-of-the-art graph embeddings across a broad range of graph tasks, while a hyperparameter-supervised variant performs even better.