A Theoretical Analysis of DeepWalk and Node2vec for Exact Recovery of Community Structures in Stochastic Blockmodels

Area of Science:

• Graph theory
• Machine learning
• Network analysis

Background:

• Random-walk-based network embedding algorithms like DeepWalk and node2vec are prevalent for node representation in networks.
• Existing methods lack theoretical explanations for their large-sample behavior.
• Community detection is a key downstream task in network analysis.

Purpose of the Study:

• To provide theoretical analysis for DeepWalk and node2vec algorithms using a matrix factorization perspective.
• To derive error bounds for node embeddings generated by these algorithms.
• To establish theoretical guarantees for community detection using these embeddings.

Main Methods:

• Matrix factorization approach to analyze DeepWalk and node2vec.
• Analysis within the context of stochastic blockmodel graphs and their degree-corrected variants.
• Exploitation of row-wise uniform perturbation bounds for singular vectors.
• Derivation of high-probability error bounds for node embeddings.
• Application of K-means/medians for community recovery.

Main Results:

• High-probability error bounds derived for matrix factorization-based node2vec/DeepWalk embeddings.
• Demonstrated perfect membership recovery using node2vec/DeepWalk with K-means/medians.
• Guaranteed accurate community recovery in sparse stochastic blockmodel graphs with sufficient parameters.
• Theoretical findings are supported by numerical experiments and real-world data.

Conclusions:

• The matrix factorization perspective provides a theoretical foundation for understanding DeepWalk and node2vec.
• These algorithms, particularly node2vec, can reliably recover community structures in various network types.
• The study bridges the gap between empirical success and theoretical understanding of network embedding techniques.