Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling
arXiv:2105.09182
Abstract
A widely established set of unsupervised node embedding methods can be interpreted as consisting of two distinctive steps: i) the definition of a similarity matrix based on the graph of interest followed by ii) an explicit or implicit factorization of such matrix. Inspired by this viewpoint, we propose improvements in both steps of the framework. On the one hand, we propose to encode node similarities based on the free energy distance, which interpolates between the shortest path and the commute time distances, thus, providing an additional degree of flexibility. On the other hand, we propose a matrix factorization method based on a loss function that generalizes that of the skip-gram model with negative sampling to arbitrary similarity matrices. Compared with factorizations based on the widely used loss, the proposed method can better preserve node pairs associated with higher similarity scores. Moreover, it can be easily implemented using advanced automatic differentiation toolkits and computed efficiently by leveraging GPU resources. Node clustering, node classification, and link prediction experiments on real-world datasets demonstrate the effectiveness of incorporating free-energy-based similarities as well as the proposed matrix factorization compared with state-of-the-art alternatives.
References in corpus (15)
- Efficient Estimation of Word Representations in Vector Space
- Distributed Representations of Words and Phrases and their Compositionality
- PyTorch: An Imperative Style, High-Performance Deep Learning Library
- Graph Embedding Techniques, Applications, and Performance: A Survey
- Graph Embedding on Biomedical Networks: Methods, Applications, and Evaluations
- A Fast and Simple Algorithm for Training Neural Probabilistic Language Models
- VERSE: Versatile Graph Embeddings from Similarity Measures
- Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
- Developments in the theory of randomized shortest paths with a comparison of graph node distances
- A Class of Graph-Geodetic Distances Generalizing the Shortest-Path and the Resistance Distances
- A Comparative Study for Unsupervised Network Representation Learning
- A bag-of-paths framework for network data analysis
- Principled Simplicial Neural Networks for Trajectory Prediction
- Deconstructing and reconstructing word embedding algorithms
- Distributed Scheduling using Graph Neural Networks