Shallow graph embedding methods vary widely in robustness to node deletion

Shallow graph embedding methods, which compress the structure of a network into low-dimensional vectors assigned to individual nodes, are a standard tool for community detection in graph machine learning. A new study published in Applied Network Science examines how well these methods hold up when the underlying network is perturbed, focusing specifically on the deletion of nodes. According to the authors, the impact of such perturbations on embedding performance has remained relatively understudied, despite the widespread use of these techniques in tasks that depend on capturing structural properties of networks.

The research evaluates state-of-the-art shallow embedding methods drawn from two families. The first is matrix factorization-based approaches, including Laplacian Eigenmaps (LE), Locally Linear Embedding (LLE), HOPE and M-NMF. The second comprises random walk-based methods, including DeepWalk, LINE and node2vec. Experiments were conducted on both synthetic and real-world networks, allowing the authors to compare how each method’s community detection performance degrades as nodes are removed.

Robustness was found to depend on several factors, including the size of the network, the strength of the initial community partition, and the type of perturbation applied. In other words, no single method was uniformly resilient; how well an embedding survived node deletion depended on the characteristics of the network being analyzed and on how its communities were structured before perturbation.

Notably, two methods stood out across the experiments. Node2vec, a random walk-based technique, and LLE, a matrix factorization technique, consistently demonstrated higher robustness for community detection across different scenarios. This held even in networks with degree heterogeneity, where node connectivity varies widely, and in networks with community size heterogeneity, where communities differ substantially in the number of nodes they contain. The fact that the two most robust methods come from different methodological families suggests that robustness is not simply a property of the underlying algorithmic approach.

The authors argue that 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. In applications where robustness to perturbations is crucial, such as networks that evolve over time or lose nodes, the choice of embedding method can materially affect the reliability of detected communities. The study, published as open access on 3 September 2026 by Zhi-Feng Wei, Pablo Moriano and Ramakrishnan Kannan, offers a systematic basis for making that choice rather than relying on default assumptions about which embedding technique performs best.

Subject of Research: Robustness of shallow graph embedding methods for community detection under network perturbations

Article Title: Robustness of shallow graph embedding methods for community detection

Article References: Wei, Z.-F., Moriano, P., & Kannan, R. (2026). Robustness of shallow graph embedding methods for community detection. Applied Network Science. https://doi.org/10.1007/s41109-026-00825-z

Image Credits: AI Generated

DOI: 10.1007/s41109-026-00825-z

Keywords: graph embedding, community detection, network science, node2vec, LLE, DeepWalk, matrix factorization, random walks, network perturbation, robustness, shallow, graph