2023/06/23 by Sadamori Kojaku, Filippo Radicchi, Kojaku, Sadamori +5 · 5 citations
Computer Science · Neuroscience · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Functional Brain Connectivity Studies #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2306.13400
openalex publication_date 2023/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Recent advances in machine learning research have produced powerful neural graph embedding methods, which learn useful, low-dimensional vector representations of network data. These neural methods for graph embedding excel in graph machine learning tasks and are now widely adopted. However, how and why these methods work -- particularly how network structure gets encoded in the embedding -- remain largely unexplained. Here, we show that node2vec -- shallow, linear neural network -- encodes communities into separable clusters better than random partitioning down to the information-theoretic detectability limit for the stochastic block models. We show that this is due to the equivalence between the embedding learned by node2vec and the spectral embedding via the eigenvectors of the symmetric normalized Laplacian matrix. Numerical simulations demonstrate that node2vec is capable of learning communities on sparse graphs generated by the stochastic blockmodel, as well as on sparse degree-heterogeneous networks. Our results highlight the features of graph neural networks that enable them to separate communities in embedding space.