Principled approach to the selection of the embedding dimension of networks

Abstract

Network embedding is a general-purpose machine learning technique that encodes network structure in vector spaces with tunable dimension. Choosing an appropriate embedding dimension -- small enough to be efficient and large enough to be effective -- is challenging but necessary to generate embeddings applicable to a multitude of tasks. Existing strategies for the selection of the embedding dimension rely on performance maximization in downstream tasks. Here, we propose a principled method such that all structural information of a network is parsimoniously encoded. The method is validated on various embedding algorithms and a large corpus of real-world networks. The embedding dimension selected by our method in real-world networks suggest that efficient encoding in low-dimensional spaces is usually possible.

arXiv comment13 pages, 5 figures, Supplementary Information available this http://homes.sice.indiana.edu/filiradi/Mypapers/SI_nc.pdf

References in corpus (26)

• Emergence of scaling in random networks
• Distributed Representations of Words and Phrases and their Compositionality
• Community structure in social and biological networks
• DeepWalk: Online Learning of Social Representations
• Semi-Supervised Classification with Graph Convolutional Networks
• LINE: Large-scale Information Network Embedding
• Maps of random walks on complex networks reveal community structure
• Inductive Representation Learning on Large Graphs
• Comparing community structure identification
• Stochastic blockmodels and community structure in networks
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Word Embeddings Quantify 100 Years of Gender and Ethnic Stereotypes
• Hyperbolic Geometry of Complex Networks
• The Geometry of Culture: Analyzing Meaning through Word Embeddings
• Sustaining the Internet with Hyperbolic Mapping
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Self-similarity of complex networks and hidden metric spaces
• Representation Learning on Graphs: Methods and Applications
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Statistical inference on random dot product graphs: a survey
• On the Dimensionality of Word Embedding
• Principled approach to the selection of the embedding dimension of networks
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• The impossibility of low rank representations for triangle-rich complex networks
• Dimensionality of social networks using motifs and eigenvalues
• Node Embeddings and Exact Low-Rank Representations of Complex Networks

Cited by in corpus (10)

• Principled approach to the selection of the embedding dimension of networks
• Detecting the ultra low dimensionality of real networks
• Random hyperbolic graphs in $d+1$ dimensions
• Zoo Guide to Network Embedding
• Strange Attractors in Complex Networks
• Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
• Detecting Masquerade Attacks in Controller Area Networks Using Graph Machine Learning
• Determinable and interpretable network representation for link prediction
• Systematic comparison of graph embedding methods in practical tasks
• Real-World Networks are Low-Dimensional: Theoretical and Practical Assessment