Robustness of shallow graph embedding methods for community detection

Abstract 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. Acknowledgements The work of Zhi-Feng Wei is supported by the U.S. Department of Energy (DOE) Office of Advanced Scientific Computing Research (ASCR) through the ASCR Distinguished Computational Mathematics Postdoctoral Fellowship (Project No. 71268). Pacific Northwest National Laboratory (PNNL) is a multi-program national laboratory operated for the U.S. Department of Energy (DOE) by Battelle Memorial Institute under Contract No. DE-AC05-76RL01830. The research of Zhi-Feng Wei was supported in part by an appointment with the National Science Foundation (NSF) Mathematical Sciences Graduate Internship (MSGI) Program. This program is administered by the Oak Ridge Institute for Science and Education (ORISE) through an interagency agreement between the U.S. Department of Energy (DOE) and NSF. ORISE is managed for DOE by ORAU. All opinions expressed in this paper are the author’s and do not necessarily reflect the policies and views of NSF, ORAU/ORISE, or DOE. The research of Zhi-Feng Wei was supported in part by an appointment to the Oak Ridge National Laboratory GRO Program, sponsored by the U.S. Department of Energy and administered by the Oak Ridge Institute for Science and Education. This paper has been coauthored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The publisher, by accepting the article for publication, acknowledges that the U.S. government retains a nonexclusive, paid up, irrevocable, world-wide license to publish or reproduce the published form of the manuscript, or allow others to do so, for U.S. government purposes. The DOE will provide public access to these results in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan). This research was supported in part by Lilly Endowment, Inc., through its support for the Indiana University Pervasive Technology Institute. Funding The work of Zhi-Feng Wei was supported by the U.S. Department of Energy (DOE) Office of Advanced Scientific Computing Research (ASCR) through the ASCR Distinguished Computational Mathematics Postdoctoral Fellowship (Project No. 71268). The research of Zhi-Feng Wei was also supported in part by the National Science Foundation (NSF) Mathematical Sciences Graduate Internship (MSGI) Program and the Oak Ridge National Laboratory GRO Program. This research was also supported in part by Lilly Endowment, Inc., through its support for the Indiana University Pervasive Technology Institute. Author information Authors and Affiliations Corresponding author Ethics declarations Competing interests The authors declare no competing interests. Additional information Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Appendices Appendix A Remarks on node2vec method Node2vec produces more robust graph community detection results due to its flexible random walk strategy, which employs biased random walks to provide a trade-off between breadth-first search (BFS) and depth-first search (DFS). As mentioned in Goyal and Ferrara (2018), node2vec produces higher-quality and more informative embeddings than DeepWalk, enabling node2vec to preserve community structure as well as structural equivalence between nodes. There has been theoretical evidence supporting the superiority of node2vec over DeepWalk in community detection tasks. As demonstrated in Kojaku et al. (2024, 2021), node2vec is notably robust to degree heterogeneity due to its ability to learn degree-agnostic embeddings. In contrast, DeepWalk tends to encode node degree as a dominant feature in the embedding space. This sensitivity makes DeepWalk more susceptible to structural noise in networks with heterogeneous degree distributions, such as those generated by the LFR benchmark model. These theoretical insights are consistent with our empirical results. As shown in Figs. 10 and 15, when the proportion of removed nodes is small—so the perturbed network retains structural properties close to the original LFR benchmark—the ECS similarity scores achieved by DeepWalk are consistently lower than those by node2vec. A similar pattern is observed in Figs. 11 and 16. In addition, this theoretical insight is reflected in Table 5: the \(y_0\) values for DeepWalk are smaller than those for node2vec in these two tables. Furthermore, Cohen et al. (2000) studied the robustness of networks with power-law degree distributions under random breakdowns using percolation theory. Specifically, they showed that if a network has a degree distribution with probability mass function \(\{P_k\}\), and a fraction p of its nodes break down, the resulting degree distribution has probability mass function This transformation preserves the heavy-tailed nature of the original distribution. Furthermore, applying this calculation in the case of LFR graphs, we can get a stronger assertion: If \(\{P_k\}\) is power-law distributed with exponent \(\gamma \), then \(\{P'_k\}\) is asymptotically power-law distributed and has the same exponent \(\gamma \). To show this, we can first construct a random sum \(S_N = \sum ^{N}_{i=1}B_i\), where N is a power-law random variable with exponent \(\gamma \) and \(\{B_i\}_{i=1}^\infty \) is a sequence of independent Bernoulli random variable whose probability of taking value 1 is \(1-p\). Then the probability mass function of \(S_N\) is exactly \(\{P'_k\}\). According to Theorem 3.1 in Robert and Segers (2008), we have Because N is a power-law random variable with exponent \(\gamma \), it follows that Now that \(\{P'_k\}\) is the probability mass function of \(S_N\), we proved our assertion: if \(\{P_k\}\) is power-law distributed with exponent \(\gamma \), then \(\{P'_k\}\) is asymptotically power-law distributed with the same exponent \(\gamma \). Hence, the type of random perturbation we considered does not eliminate degree heterogeneity. Consequently, DeepWalk remains vulnerable to degree-based noise after such perturbations, while node2vec continues to perform robustly in community detection. As discussed in Kojaku et al. (2024); Qiu et al. (2018), LINE can be regarded as a special case of node2vec with a window size \(w=1\), meaning that it focuses solely on learning dyadic (i.e., direct) relationships between nodes. This limited temporal context restricts LINE’s ability to capture higher-order or indirect structural features. Consequently, LINE exhibits lower robustness than node2vec, particularly in noisy or perturbed networks, because it tends to encode stochastic and noisy pairwise interactions. In contrast, node2vec, by aggregating longer biased random walks, can effectively capture indirect relationships between nodes, making it more resilient in downstream tasks such as community detection. Moreover, as mentioned in Kojaku et al. (2024), node2vec is robust to network sparsity compared to traditional spectral embedding methods. These observations are corroborated in our experiments. In fact, as we remove more nodes, networks are getting sparsified. Therefore, it is understandable that node2vec is more robust in our experiments. Hence, node2vec is more robust against random and targeted perturbations in community detection, outperforming other methods in stability under perturbations. Appendix B M-NMF method with higher embedding dimensions An increase in ECS can be observed in Figs. 9, 17 and 18 for the M-NMF method, where 16-dimensional and 32-dimensional embedding are used. We see some unexpected increasing behaviors in the M-NMF curves in Figs. 9b and 9d for synthetic LFR networks with 10, 000 nodes. Intuitively, these networks are bigger and therefore more complex, which makes it more difficult to detect communities. We thus conducted additional experiments on M-NMF with a 128-dimensional embedding as shown in Fig. 20. We observe that the unexpected increasing behaviors are mitigated compared to 32-dimensional embedding. Specifically, the ECS scores of M-NMF with 128-dimensional embedding are more stable than those with 32-dimensional embedding. This indicates that the choice of embedding dimension can significantly and sensitively impact the performance of M-NMF. Due to the substantial computational cost associated with our additional experiments on synthetic networks with 10, 000 nodes, we reduced the number of realizations per percentage of removed nodes to 10, compared to the 50 used in the original paper, to obtain results within the high-performance computing cluster’s time limit. Standard deviations are still negligible compared to the mean but we do not show them here. Notably, the M-NMF curves in Fig. 17a and 18a for email-EU-core networks are generated using the exact same node removal sequence, with the only difference being the embedding dimension. In Fig. 17a, where the embedding dimension is 16, the M-NMF curve remains almost stable showing slightly unexpected increases. In Fig. 18a, the increasing of ECS is more noticeable. To get more insights into this behavior, we performed additional experiment and analyzed the ECS scores of M-NMF with 128-dimensional embedding. The comparison results are presented in Fig. 21. We can see that the ECS scores of M-NMF with 128-dimensional embedding are more “stable” as more nodes are removed, where unexpected increasing behaviors are much less pronounced. This again suggests that the choice of embedding dimension can significantly impact the performance of M-NMF, as it has been noticed by Tandon et al. (2021) and Zhu et al. (2022). Furthermore, we observe a difference in community structure: our synthetic LFR networks with 1000 nodes exhibit approximately 10 communities; our synthetic LFR networks with 10, 000 nodes exhibit approximately 20 communities. In contrast, the email-EU-core network contains 42. Consequently, employing a higher embedding dimension, such as 128, appears reasonable to effectively separate these more numerous communities in the embedding space for email-EU-core network. In summary, we have observed that the choice of embedding dimension can significantly sensitively impact the performance of M-NMF in community detection, which can lead to pathological behaviors in the ECS scores. This reveals that M-NMF is not as robust compared to other methods, especially node2vec, which is more stable and less sensitive to the choice of embedding dimension. Appendix C Modularity evolution under node removal In this appendix, we examine how the modularity Q of the network evolves under node removal for the LFR benchmark model. We consider networks with 1, 000 nodes and evaluate two attack strategies: random node removal and targeted removal based on betweenness centrality. Node removal is performed under the constraint that the remaining network must remain connected. Therefore, articulation points that would disconnect the graph are not removed during the attack process. To investigate the effect of community strength, we consider two mixing parameters in the LFR benchmark: \(\mu =0.1\) and \(\mu =0.5\). A smaller mixing parameter corresponds to stronger community structure, while larger values indicate weaker separation between communities. Figure 22 shows how modularity evolves as the fraction of removed nodes increases under the two attack strategies. When \(\mu =0.1\), the network exhibits strong community structure. In this case, both random and targeted node removal lead to relatively stable modularity values. Targeted removal may even slightly increase modularity. This effect occurs because nodes with high betweenness centrality often participate in inter-community connections. Removing these nodes can reduce cross-community links while preserving the internal structure of communities, which may increase the modularity of the remaining graph. When \(\mu =0.5\), the community structure becomes significantly weaker and a larger fraction of edges already connect different communities. Under this regime, high-betweenness nodes are not necessarily bridge nodes between well-separated communities. Removing these nodes may instead disrupt the remaining community structure, leading to a gradual decrease in modularity under targeted node removal. These observations highlight that the evolution of modularity depends on the strength of the underlying community structure. While modularity reflects the structural separation between communities in the perturbed network, ECS evaluates how accurately the original community assignments can still be recovered after perturbation. Therefore, modularity and ECS provide complementary perspectives on network robustness. Appendix D Computational complexity of shallow graph embeddings In this appendix, we summarize the asymptotic time complexity (dominant term) of the seven embedding techniques considered in this work. Laplacian Eigenmaps (LE): Laplacian Eigenmaps requires solving a sparse eigenvalue problem associated with the graph Laplacian to obtain the embedding coordinates. The original formulation describes the method as involving “a few local computations and one sparse eigenvalue problem” (Belkin and Niyogi 2003). Under common implementations, the dominant computational cost arises from this sparse eigensolver step, which scales approximately as \(O(|E|\, d^{2})\), where |E| is the number of edges and d is the embedding dimension. Locally Linear Embedding (LLE): Locally Linear Embedding first computes local reconstruction weights based on nearest neighbors and then obtains the embedding by solving an eigenvalue problem (Roweis and Saul 2000). The dominant computational cost arises from the sparse eigenvalue decomposition step, which scales approximately as \(O(|E|\, d^{2})\) under common implementations. HOPE: HOPE (High-Order Proximity preserved Embedding) reduces the high-order proximity preservation problem to a generalized singular value decomposition (GSVD) formulation (Ou et al. 2016). Using iterative eigensolvers, the dominant computational cost scales approximately as \(O(|E|\, d^{2})\), where |E| is the number of edges and d is the embedding dimension. M-NMF: M-NMF jointly models community structure and node embeddings through a modularized nonnegative matrix factorization framework (Wang et al. 2017). The algorithm relies on iterative multiplicative update rules for matrix factors and community indicators. Under common implementations, the dominant computational cost scales approximately as \(O(|V|\,(d+c))\), where |V| is the number of nodes, d is the embedding dimension, and c is the number of communities. DeepWalk: DeepWalk generates truncated random walks from each node and learns embeddings using the Skip-Gram model with negative sampling (Perozzi et al. 2014). When walk parameters are treated as constants, the dominant computational cost scales approximately as \(O(|V|\, d)\), where |V| is the number of nodes and d is the embedding dimension. LINE: LINE learns node embeddings by optimizing first- and second-order proximity objectives using edge sampling and negative sampling (Tang et al. 2015). The optimization process typically performs a number of stochastic gradient updates proportional to the number of edges, leading to an overall computational complexity of approximately \(O(|E|\, d)\). node2vec: node2vec extends DeepWalk by introducing biased second-order random walks to better explore network structure (Grover and Leskovec 2016). After preprocessing transition probabilities for the random walks, the dominant computational cost arises from random walk generation and Skip-Gram training, which scales approximately as \(O(|V|\, d)\) when walk parameters are treated as constants. Rights and permissions Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. About this article Cite this article Wei, ZF., Moriano, P. & Kannan, R. Robustness of shallow graph embedding methods for community detection. Appl Netw Sci (2026). https://doi.org/10.1007/s41109-026-00825-z Received: Accepted: Published: DOI: https://doi.org/10.1007/s41109-026-00825-z