# Robustness of shallow graph embedding methods for community detection

arXiv: https://arxiv.org/abs/2405.00636 · HTML: https://mlsanity.com/paper/2405.00636/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 79 references that are in the map.
- First posted on arXiv 1 May 2024.

## Builds on (most cited first, 23 of 23)

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [A Comprehensive Survey on Community Detection with Deep Learning](https://mlsanity.com/paper/2105.12584/) (2021)
- [Understanding graph embedding methods and their applications](https://mlsanity.com/paper/2012.08019/) (2020)
- [Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing](https://mlsanity.com/paper/2002.03421/) (2020)
- [Principled approach to the selection of the embedding dimension of networks](https://mlsanity.com/paper/2004.09928/) (2020)
- [Element-centric clustering comparison unifies overlaps and hierarchy](https://mlsanity.com/paper/1706.06136/) (2017)
- [Graph Neural Network Encoding for Community Detection in Attribute Networks](https://mlsanity.com/paper/2006.03996/) (2020)
- [Neural Embeddings of Scholarly Periodicals Reveal Complex Disciplinary Organizations](https://mlsanity.com/paper/2001.08199/) (2020)
- [Community detection in networks using graph embeddings](https://mlsanity.com/paper/2009.05265/) (2020)
- [Residual2Vec: Debiasing graph embedding with random graphs](https://mlsanity.com/paper/2110.07654/) (2021)
- [Network community detection via neural embeddings](https://mlsanity.com/paper/2306.13400/) (2023)
- [Accelerating Spherical k-Means](https://mlsanity.com/paper/2107.04074/) (2021)
- [Robustness of Community Detection to Random Geometric Perturbations](https://mlsanity.com/paper/2011.04298/) (2020)
- [Embedding-aided network dismantling](https://mlsanity.com/paper/2208.01087/) (2022)
- [Robustness of community structure under edge addition](https://mlsanity.com/paper/2304.07238/) (2023)
- [Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks](https://mlsanity.com/paper/1702.02246/) (2017)

## Built on by (most cited first, 3 of 3)

- [Detecting Masquerade Attacks in Controller Area Networks Using Graph Machine Learning](https://mlsanity.com/paper/2408.05427/) (2024)
- [Community detection robustness of graph neural networks](https://mlsanity.com/paper/2509.24662/) (2025)
- [Community Concealment from Graph Neural Networks](https://mlsanity.com/paper/2602.12250/) (2026)

## Abstract (arXiv)

This study investigates the robustness of shallow graph embedding methods for community detection in the face of network perturbations, specifically node deletions. Graph embedding techniques, which represent nodes as low-dimensional vectors, are widely used for various graph machine learning tasks due to their ability to capture structural properties of networks effectively. However, the impact of perturbations on the performance of these methods remains relatively understudied. The research considers state-of-the-art shallow graph embedding methods from two families: matrix factorization (e.g., LE, LLE, HOPE, M-NMF) and random walk-based (e.g., DeepWalk, LINE, node2vec). Through experiments conducted on both synthetic and real-world networks, the study reveals varying degrees of robustness within each family of shallow graph embedding methods. The robustness is found to be influenced by factors such as network size, initial community partition strength, and the type of perturbation. Notably, node2vec and LLE consistently demonstrate higher robustness for community detection across different scenarios, including networks with degree and community size heterogeneity. These findings highlight the importance of selecting an appropriate shallow graph embedding method based on the specific characteristics of the network and the task at hand, particularly in scenarios where robustness to perturbations is crucial.