Network community detection via neural embeddings.

Area of Science:

• Machine Learning
• Network Science
• Data Mining

Background:

• Neural graph embedding methods learn low-dimensional vector representations of network data.
• These methods are widely adopted for graph machine learning tasks but lack theoretical explanation.
• Understanding how network structure is encoded in embeddings is crucial.

Purpose of the Study:

• To explain the mechanism behind node2vec's ability to encode network structure.
• To demonstrate the equivalence between node2vec and spectral embedding methods.
• To highlight the features of graph neural networks enabling community separation.

Main Methods:

• Analysis of node2vec-shallow, a linear neural network, for community encoding.
• Comparison with random partitioning and spectral embedding using the normalized Laplacian matrix.
• Numerical simulations on stochastic block models and sparse degree-heterogeneous networks.

Main Results:

• Node2vec-shallow encodes communities into separable clusters beyond random partitioning.
• Equivalence established between node2vec embeddings and spectral embeddings via Laplacian eigenvectors.
• Successful community detection demonstrated on various sparse graph types.

Conclusions:

• The study explains how node2vec encodes community structure through its connection to spectral embedding.
• This provides theoretical insight into the effectiveness of neural graph embedding methods.
• Findings clarify the role of graph neural networks in separating communities in embedding spaces.