Benchmarks for Graph Embedding Evaluation

Abstract

Graph embedding is the task of representing nodes of a graph in a low-dimensional space and its applications for graph tasks have gained significant traction in academia and industry. The primary difference among the many recently proposed graph embedding methods is the way they preserve the inherent properties of the graphs. However, in practice, comparing these methods is very challenging. The majority of methods report performance boosts on few selected real graphs. Therefore, it is difficult to generalize these performance improvements to other types of graphs. Given a graph, it is currently impossible to quantify the advantages of one approach over another. In this work, we introduce a principled framework to compare graph embedding methods. Our goal is threefold: (i) provide a unifying framework for comparing the performance of various graph embedding methods, (ii) establish a benchmark with real-world graphs that exhibit different structural properties, and (iii) provide users with a tool to identify the best graph embedding method for their data. This paper evaluates 4 of the most influential graph embedding methods and 4 traditional link prediction methods against a corpus of 100 real-world networks with varying properties. We organize the 100 networks in terms of their properties to get a better understanding of the embedding performance of these popular methods. We use the comparisons on our 100 benchmark graphs to define GFS-score, that can be applied to any embedding method to quantify its performance. We rank the state-of-the-art embedding approaches using the GFS-score and show that it can be used to understand and evaluate novel embedding approaches. We envision that the proposed framework (https://www.github.com/palash1992/GEM-Benchmark) will serve the community as a benchmarking platform to test and compare the performance of future graph embedding techniques.

References in corpus (13)

• Emergence of scaling in random networks
• Inductive Representation Learning on Large Graphs
• Benchmark graphs for testing community detection algorithms
• Spectral Networks and Locally Connected Networks on Graphs
• Clustering and preferential attachment in growing networks
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Deep Convolutional Networks on Graph-Structured Data
• Growing Scale-Free Networks with Tunable Clustering
• Hyperbolic Geometry of Complex Networks
• Variational Graph Auto-Encoders
• Kronecker Graphs: An Approach to Modeling Networks
• Gated Graph Sequence Neural Networks
• Duplication-divergence model of protein interaction network

Cited by in corpus (4)

• MultiVERSE: a multiplex and multiplex-heterogeneous network embedding approach
• The Effects of Randomness on the Stability of Node Embeddings
• Benchmarking neural embeddings for link prediction in knowledge graphs under semantic and structural changes
• A Process for the Evaluation of Node Embedding Methods in the Context of Node Classification