Systematic comparison of graph embedding methods in practical tasks
- 22 October 2021
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 104 (4) , 044315
Abstract
Network embedding techniques aim to represent structural properties of graphs in geometric space. Those representations are considered useful in downstream tasks such as link prediction and clustering. However, the number of graph embedding methods available on the market is large, and practitioners face the nontrivial choice of selecting the proper approach for a given application. The present work attempts to close this gap of knowledge through a systematic comparison of 11 different methods for graph embedding. We consider methods for embedding networks in the hyperbolic and Euclidean metric spaces, as well as nonmetric community-based embedding methods. We apply these methods to embed more than 100 real-world and synthetic networks. Three common downstream tasks — mapping accuracy, greedy routing, and link prediction — are considered to evaluate the quality of the various embedding methods. Our results show that some Euclidean embedding methods excel in greedy routing. As for link prediction, community-based and hyperbolic embedding methods yield an overall performance that is superior to that of Euclidean-space-based approaches. We compare the running time for different methods and further analyze the impact of different network characteristics such as degree distribution, modularity, and clustering coefficients on the quality of the embedding results. We release our evaluation framework to provide a standardized benchmark for arbitrary embedding methods.Keywords
All Related Versions
Funding Information
- National Science Foundation (CMMI-1552487)
- Army Research Office (W911NF-21-1-0194)
This publication has 64 references indexed in Scilit:
- Dimension of spatially embedded networksNature Physics, 2011
- What's in a crowd? Analysis of face-to-face behavioral networksJournal of Theoretical Biology, 2011
- Identification of influential spreaders in complex networksNature Physics, 2010
- Benchmark graphs for testing community detection algorithmsPhysical Review E, 2008
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences of the United States of America, 2008
- Graph evolutionACM Transactions on Knowledge Discovery From Data, 2007
- Models of social networks based on social distance attachmentPhysical Review E, 2004
- Network Motifs: Simple Building Blocks of Complex NetworksScience, 2002
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- A Set of Measures of Centrality Based on BetweennessSociometry, 1977