An Unsupervised Framework for Comparing Graph Embeddings
arXiv:1906.04562 · doi:10.1093/comnet/cnz043
Abstract
Graph embedding is a transformation of vertices of a graph into set of vectors. Good embeddings should capture the graph topology, vertex-to-vertex relationship, and other relevant information about graphs, subgraphs, and vertices. If these objectives are achieved, they are meaningful, understandable, and compressed representations of networks. They also provide more options and tools for data scientists as machine learning on graphs is still quite limited. Finally, vector operations are simpler and faster than comparable operations on graphs. The main challenge is that one needs to make sure that embeddings well describe the properties of the graphs. In particular, the decision has to be made on the embedding dimensionality which highly impacts the quality of an embedding. As a result, selecting the best embedding is a challenging task and very often requires domain experts. In this paper, we propose a ``divergence score'' that can be assign to various embeddings to distinguish good ones from bad ones. This general framework provides a tool for an unsupervised graph embedding comparison. In order to achieve it, we needed to generalize the well-known Chung-Lu model to incorporate geometry which is interesting on its own rights. In order to test our framework, we did a number of experiments with synthetic networks as well as real-world networks, and various embedding algorithms.
References in corpus (20)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
- Cooperative Game Theory Approaches for Network Partitioning
- LINE: Large-scale Information Network Embedding
- Maps of random walks on complex networks reveal community structure
- Benchmark graphs for testing community detection algorithms
- Hyperbolic Geometry of Complex Networks
- The spatial structure of networks
- Uncovering space-independent communities in spatial networks
- VERSE: Versatile Graph Embeddings from Similarity Measures
- Community structure and scale-free collections of Erdös-Rényi graphs
- A Scalable Generative Graph Model with Community Structure
- Interdisciplinary and physics challenges of Network Theory
- Emergence of Soft Communities from Geometric Preferential Attachment
- Structural properties of spatially embedded networks
- Clustering via Hypergraph Modularity
- Ensemble Clustering for Graphs
- Similarities on Graphs: Kernels versus Proximity Measures
- Ensemble Clustering for Graphs: Comparisons and Applications