VERSE: Versatile Graph Embeddings from Similarity Measures

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.

In WWW 2018: The Web Conference. 10 pages, 5 figures

References in corpus (10)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• DeepWalk: Online Learning of Social Representations
• Cooperative Game Theory Approaches for Network Partitioning
• LINE: Large-scale Information Network Embedding
• Link Prediction in Complex Networks: A Survey
• struc2vec: Learning Node Representations from Structural Identity
• A Fast and Simple Algorithm for Training Neural Probabilistic Language Models
• subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs
• Learning Edge Representations via Low-Rank Asymmetric Projections

Cited by in corpus (64)

• Contrastive Multi-View Representation Learning on Graphs
• NetLSD: Hearing the Shape of a Graph
• NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization
• Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts
• GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding
• DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
• A Comparative Study for Unsupervised Network Representation Learning
• MultiVERSE: a multiplex and multiplex-heterogeneous network embedding approach
• Graph Clustering with Graph Neural Networks
• Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems
• Efficient Algorithms for Personalized PageRank Computation: A Survey
• A Broader Picture of Random-walk Based Graph Embedding
• FREDE: Anytime Graph Embeddings
• Overlapping Community Detection with Graph Neural Networks
• Network representation learning systematic review: ancestors and current development state
• Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress?
• PANE: scalable and effective attributed network embedding
• Efficient Representation Learning Using Random Walks for Dynamic Graphs
• Boost then Convolve: Gradient Boosting Meets Graph Neural Networks
• vGraph: A Generative Model for Joint Community Detection and Node Representation Learning
• An Unsupervised Framework for Comparing Graph Embeddings
• Hypergraph Partitioning With Embeddings
• "What's ur type?" Contextualized Classification of User Types in Marijuana-related Communications using Compositional Multiview Embedding
• Deep Graph Similarity Learning: A Survey
• FOBE and HOBE: First- and High-Order Bipartite Embeddings
• SCE: Scalable Network Embedding from Sparsest Cut
• Zoo Guide to Network Embedding
• Network Representation Learning: Consolidation and Renewed Bearing
• Network Embedding via Deep Prediction Model
• Multiple Kernel Representation Learning on Networks
• Higher-Order Ranking and Link Prediction: From Closing Triangles to Closing Higher-Order Motifs
• Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective
• Word Embeddings for Entity-annotated Texts
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• QUINT: Node embedding using network hashing
• Topic-aware latent models for representation learning on networks
• InstantEmbedding: Efficient Local Node Representations
• Towards a Flexible Embedding Learning Framework
• EvalNE: A Framework for Evaluating Network Embeddings on Link Prediction
• Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank
• Spectral Graph Complexity
• Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds
• Boosting Multitask Learning on Graphs through Higher-Order Task Affinities
• Fast and Accurate Network Embeddings via Very Sparse Random Projection
• Adversarial Directed Graph Embedding
• Graph Ordering: Towards the Optimal by Learning
• Representation Learning for Recommender Systems with Application to the Scientific Literature
• A Robust and Generalized Framework for Adversarial Graph Embedding
• HUGE: Huge Unsupervised Graph Embeddings with TPUs
• An Analytical Survey on Recent Trends in High Dimensional Data Visualization
• Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling
• Inductive Graph Embeddings through Locality Encodings
• UniNet: Scalable Network Representation Learning with Metropolis-Hastings Sampling
• Unsupervised Hierarchical Graph Representation Learning by Mutual Information Maximization
• Feature Learning for Meta-Paths in Knowledge Graphs
• Subset Node Representation Learning over Large Dynamic Graphs
• Self-Supervised Graph Learning with Proximity-based Views and Channel Contrast
• Learning Large-scale Network Embedding from Representative Subgraph
• Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push
• Learning Based Proximity Matrix Factorization for Node Embedding
• Constructing Graph Node Embeddings via Discrimination of Similarity Distributions
• COLOGNE: Coordinated Local Graph Neighborhood Sampling
• DeepGD: A Deep Learning Framework for Graph Drawing Using GNN
• Leveraging semantically similar queries for ranking via combining representations