pith. sign in

arxiv: 2509.24662 · v1 · submitted 2025-09-29 · 💻 cs.SI · cs.AI· physics.soc-ph· stat.ML

Community detection robustness of graph neural networks

Jaidev Goel , Pablo Moriano , Ramakrishnan Kannan , Yulia R. Gel This is my paper

Pith reviewed 2026-05-18 12:45 UTC · model grok-4.3

classification 💻 cs.SI cs.AIphysics.soc-phstat.ML
keywords graph neural networkscommunity detectionrobustnessadversarial attacksnetwork perturbationsunsupervised methodssupervised methodscitation networks
0
0 comments X

The pith

Supervised GNNs start more accurate on community detection but unsupervised models like DMoN hold up better under perturbations and attacks.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tests six graph neural network architectures on the task of recovering communities in networks where node attributes or edges have been altered or attacked. It compares performance on both synthetic graphs with controlled community strength and real citation networks, using element-centric similarity to measure how well the detected groups match the true ones. Supervised models post higher scores when data is clean, yet they lose more ground when faced with targeted changes, while unsupervised methods prove steadier especially when communities are clearly separated. The work matters because GNNs are now common tools for grouping nodes in noisy or contested network data, and knowing which architectures survive real-world distortions helps choose the right one.

Core claim

Supervised GNNs tend to achieve higher baseline accuracy, while unsupervised methods, particularly DMoN, maintain stronger resilience under targeted and adversarial perturbations. Robustness appears to be strongly influenced by community strength, with well-defined communities reducing performance loss. Across all models, node attribute perturbations associated with targeted edge deletions and shift in attribute distributions tend to cause the largest degradation in community recovery.

What carries the argument

Comparative evaluation of six GNN architectures (GCN, GAT, Graph-SAGE, DiffPool, MinCUT, DMoN) across node attribute manipulations, edge topology distortions, and adversarial attacks, scored by element-centric similarity.

If this is right

  • Unsupervised architectures such as DMoN become preferable when networks may contain adversarial tampering or attribute noise.
  • Stronger inherent community structure in the data lowers the performance drop for every tested model.
  • Targeted changes to node attributes combined with edge deletions inflict more damage than random or uniform perturbations.
  • Designers must weigh initial accuracy against sustained performance when deploying GNNs for real-world grouping tasks.
  • Well-separated communities act as a buffer that preserves detection quality even after moderate attacks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Adding explicit robustness objectives during training could narrow the accuracy gap between supervised and unsupervised approaches.
  • The same evaluation pattern may appear in other graph tasks such as link prediction or node classification under attack.
  • Testing on time-varying networks would show whether the observed resilience holds when perturbations accumulate over time.
  • Practitioners facing high-stakes grouping decisions might default to DMoN when data integrity cannot be guaranteed.

Load-bearing premise

The synthetic benchmarks, real citation networks, and three chosen categories of perturbations represent the conditions GNNs face in typical community detection settings.

What would settle it

A controlled experiment on a new set of networks with stronger community mixing or a different attack type that reverses the resilience pattern, showing unsupervised models degrading faster than supervised ones.

Figures

Figures reproduced from arXiv: 2509.24662 by Jaidev Goel, Pablo Moriano, Ramakrishnan Kannan, Yulia R. Gel.

Figure 1
Figure 1. Figure 1: FIG. 1: GNN based community detection approach [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: ECS scores for GCN-based community [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: ECS scores for GAT-based community [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4: ECS scores for SAGE-based community [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5: ECS scores for MinCut-based community [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6: ECS scores for DiffPool-based community [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7: ECS scores for DMoN-based community [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8: ECS scores for Cora dataset. Under node [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9: ECS scores for Citeseer dataset. Under node [PITH_FULL_IMAGE:figures/full_fig_p014_9.png] view at source ↗
Figure 11
Figure 11. Figure 11: FIG. 11: ECS scores for GCN-based community detec [PITH_FULL_IMAGE:figures/full_fig_p019_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: FIG. 12: ECS scores for GAT-based community [PITH_FULL_IMAGE:figures/full_fig_p020_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: FIG. 13: ECS scores for GraphSAGE-based community [PITH_FULL_IMAGE:figures/full_fig_p021_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: FIG. 14: ECS scores for Diffpool-based community [PITH_FULL_IMAGE:figures/full_fig_p022_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: FIG. 15: ECS scores for Mincut-based community [PITH_FULL_IMAGE:figures/full_fig_p023_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: FIG. 16: ECS scores for DMoN-based community [PITH_FULL_IMAGE:figures/full_fig_p024_16.png] view at source ↗
read the original abstract

Graph neural networks (GNNs) are increasingly widely used for community detection in attributed networks. They combine structural topology with node attributes through message passing and pooling. However, their robustness or lack of thereof with respect to different perturbations and targeted attacks in conjunction with community detection tasks is not well understood. To shed light into latent mechanisms behind GNN sensitivity on community detection tasks, we conduct a systematic computational evaluation of six widely adopted GNN architectures: GCN, GAT, Graph-SAGE, DiffPool, MinCUT, and DMoN. The analysis covers three perturbation categories: node attribute manipulations, edge topology distortions, and adversarial attacks. We use element-centric similarity as the evaluation metric on synthetic benchmarks and real-world citation networks. Our findings indicate that supervised GNNs tend to achieve higher baseline accuracy, while unsupervised methods, particularly DMoN, maintain stronger resilience under targeted and adversarial perturbations. Furthermore, robustness appears to be strongly influenced by community strength, with well-defined communities reducing performance loss. Across all models, node attribute perturbations associated with targeted edge deletions and shift in attribute distributions tend to cause the largest degradation in community recovery. These findings highlight important trade-offs between accuracy and robustness in GNN-based community detection and offer new insights into selecting architectures resilient to noise and adversarial attacks.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper evaluates the robustness of six GNN models (GCN, GAT, Graph-SAGE, DiffPool, MinCUT, DMoN) for community detection under node attribute manipulations, edge topology distortions, and adversarial attacks on synthetic and real-world networks. It reports that supervised GNNs have higher baseline accuracy, unsupervised methods like DMoN are more resilient, robustness depends on community strength, and node attribute perturbations with targeted edge deletions cause the most degradation, using element-centric similarity.

Significance. If validated, these empirical findings would be significant for understanding accuracy-robustness trade-offs in GNN community detection, aiding model selection in noisy environments. The multi-perturbation analysis and focus on community strength provide actionable insights beyond single-model studies.

major comments (1)
  1. [Experimental Setup] The central claim contrasting supervised GNNs' higher baseline accuracy with unsupervised methods' stronger resilience under perturbations assumes a uniform evaluation protocol. However, if unsupervised models like DMoN are re-optimized on perturbed graphs while supervised models like GCN are applied with parameters fixed from clean training data, the resilience difference may reflect adaptation rather than robustness. The manuscript must specify this protocol explicitly in the experimental setup to support the claim.
minor comments (1)
  1. [Abstract] The abstract presents qualitative findings without including any quantitative results, error bars, or specific parameter values for perturbations, making it difficult to assess the practical significance of the reported differences.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and constructive feedback on our manuscript. We have carefully considered the major comment regarding the experimental setup and protocol for evaluating robustness. We address this point below and will make the necessary revisions to enhance clarity.

read point-by-point responses

  1. Referee: [Experimental Setup] The central claim contrasting supervised GNNs' higher baseline accuracy with unsupervised methods' stronger resilience under perturbations assumes a uniform evaluation protocol. However, if unsupervised models like DMoN are re-optimized on perturbed graphs while supervised models like GCN are applied with parameters fixed from clean training data, the resilience difference may reflect adaptation rather than robustness. The manuscript must specify this protocol explicitly in the experimental setup to support the claim.

    Authors: We appreciate the referee pointing out the need for explicit clarification on our evaluation protocol. To address this, we confirm that in our experiments, the supervised GNNs (GCN, GAT, Graph-SAGE) are trained exclusively on the clean, unperturbed graphs using their standard training procedures. These trained models are then directly applied to the perturbed graphs for evaluation, without any re-optimization or adaptation to the perturbations. This setup tests the models' robustness to changes in input data. For the unsupervised models (DiffPool, MinCUT, DMoN), which do not involve a separate training phase on clean data, they are optimized or run directly on each perturbed graph as input. This is the natural and standard way to apply unsupervised community detection methods. We believe this protocol fairly compares the robustness, as it reflects real-world usage where supervised models are deployed after training and unsupervised ones process the available (possibly noisy) data. We will add a detailed description of this protocol in the Experimental Setup section of the revised manuscript to support our claims more robustly. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical evaluation of GNN robustness

full rationale

The paper performs a direct computational comparison of six existing GNN architectures on community detection tasks under node, edge, and adversarial perturbations, reporting results via element-centric similarity on synthetic benchmarks and citation networks. No mathematical derivations, first-principles claims, or parameter-fitting steps are present that could reduce to the inputs by construction. All reported findings on accuracy-robustness trade-offs and the influence of community strength follow from the experimental protocol and external benchmarks rather than any self-definitional or self-citation load-bearing steps.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central empirical claims rest on the representativeness of the chosen benchmarks and perturbations plus standard assumptions about GNN message-passing behavior; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Synthetic benchmarks and citation networks constitute a sufficient testbed for generalizing robustness observations.
    The abstract invokes these datasets without discussing their limitations or external validation.
  • domain assumption Element-centric similarity is an appropriate metric for comparing community recovery under perturbation.
    The abstract uses this metric as the sole evaluation criterion without justifying alternatives.

pith-pipeline@v0.9.0 · 5770 in / 1350 out tokens · 53824 ms · 2026-05-18T12:45:44.660190+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

67 extracted references · 67 canonical work pages · 3 internal anchors

  1. [1]

    LFR benchmark The Lancichinetti–Fortunato–Radicchi (LFR) bench- mark has emerged as a popular tool for generating graphs with known community structures [32, 39]. Its primary strength lies in its ability to create networks where both degree and community size distributions follow power- laws, mirroring the characteristics of many real-world networks. Key ...

    work page

  2. [2]

    We vary the mixing parameter µ ranging between 0.1 to 0.5 to investigate the effects of perturbations at different initial community strengths

    to generate undirected, unweighted LFR benchmark graphs with 1,000 nodes. We vary the mixing parameter µ ranging between 0.1 to 0.5 to investigate the effects of perturbations at different initial community strengths

    work page

  3. [3]

    In the SBM, a graph with n vertices is partitioned into K different communities

    Stochastic block model (SBM) The standard (degree-free) SBM is a probabilistic framework for generating random graphs with planted community structure [41]. In the SBM, a graph with n vertices is partitioned into K different communities. Each vertex is assigned to one of these K communi- ties, and the probability of an edge existing between any two vertic...

    work page

  4. [4]

    Node attribute perturbation Here, we perturb node attributes by first, altering the location and then scale of their distribution. We add random Gaussian noise generated by varying location parameter and keeping scale parameter fixed and then varying the scale parameter, but keeping the location parameter fixed, similar to [22]. By doing this, we per- tur...

    work page

  5. [5]

    We follow the procedure outlined by [31]

    Graph topology perturbation We explore how removing edges affects network struc- ture through two approaches, random and targeted edge deletions. We follow the procedure outlined by [31]. In the random approach, which emulates real-world network failures, we randomly select some percentage of nodes ranging between 10% to 70% of the nodes in increments of ...

    work page

  6. [6]

    Adversarial attacks for community detection We also evaluate GNN robustness under more sophis- ticated attacks that target the overall learning process to degrade community detection performance. Specifically, we use Nettack [23] and Metattack [24] schemes, which represent advanced adversarial techniques designed to compromise graph-based machine learning...

    work page

  7. [7]

    They allow the learning of node representations based on both node features and graph structure

    GCN GCNs are a type of GNN designed to work with graph structured data, extending the concept of convolutional neural networks to graphs. They allow the learning of node representations based on both node features and graph structure. The core operation in a GCN is the graph convolution, where for a single GCN layer, the output features H(l+1) are compute...

    work page

  8. [8]

    GAT GAT uses attention mechanism enabling structural learning on networks. In this GNN, the node features are updated as h(l+1) i = σ(P j∈N(i) αijW(l)h(l) j ), with atten- tion coefficients αij = softmax j(eij) = exp(eij)P k∈N (i) exp(eik), where eij = LeakyReLU(aT [W(l)H(l) i ∥W(l)H(l) j ]) and ∥ denotes concatenation. This allows the network to assign d...

    work page

  9. [9]

    The key innovation is the sampling of a fixed-size neighborhood and the combination of the node’s own features with the aggregated neighborhood features

    GraphSAGE GraphSAGE generalizes the neighborhood ag- gregation approach with h(l+1) i = σ(W(l) · CONCAT(h(l) i , AGG({h(l) j , ∀j ∈ N(i)}))), where AGG is a permutation-invariant aggregation function such as mean, max, or LSTM, applied to the neighbor set. The key innovation is the sampling of a fixed-size neighborhood and the combination of the node’s ow...

    work page

  10. [10]

    The key idea is to formulate a continuous relaxation of the normalized MinCut problem and train- ing a GNN to compute optimal cluster assignments

    MinCut MinCutPool is differentiable graph pooling layer that performs hierarchical clustering based on spectral clus- tering [21]. The key idea is to formulate a continuous relaxation of the normalized MinCut problem and train- ing a GNN to compute optimal cluster assignments. The normalized MinCut objective aims to partition a graph’s vertices V into K d...

    work page

  11. [11]

    Given a graph with adjacency matrix A ∈ [0, 1]n×n and node features X ∈ Rn×p

    DiffPool DiffPool introduces hierarchical graph representation learning through differentiable pooling layers that enable end-to-end training of deep GNNs [20]. Given a graph with adjacency matrix A ∈ [0, 1]n×n and node features X ∈ Rn×p. DiffPool learns to cluster nodes at each layer l using two GNNs An embedding GNN generates node representations: Z(l) ...

    work page

  12. [12]

    DMoN DMoN introduces an unsupervised clustering approach that leverages a differentiable modularity objective for graph pooling [22]. The key idea is to encode commu- nity assignments using GNNs and a modularity based objective function to optimize to make a learnable graph clustering function in an end to end unsupervised man- ner. Using a softmax functi...

    work page

  13. [13]

    For average drop acrossµi values for a specific model and perturbation type, we compute: ∆ECSµi = 1 |Mi| X Mi |ECSinitial(µi) − ECSfinal(µi)| ECSinitial(µi) ×100%, where Mi is the set of all perturbations levels for all values µi

    work page

  14. [14]

    ∆ECSpert = 1 |P| X p∈P |ECSinitial(p) − ECSfinal(p)| ECSinitial(p) ×100%, where P is the set of all perturbation types (mean, scale, random edge, targeted edge)

    For average drop across perturbation types for a specific model, we compute. ∆ECSpert = 1 |P| X p∈P |ECSinitial(p) − ECSfinal(p)| ECSinitial(p) ×100%, where P is the set of all perturbation types (mean, scale, random edge, targeted edge). Table IV shows results av- eraged for different levels of community mixing parame- ters µ and Table V reports the aver...

    work page

  15. [15]

    Nettack Network perturbation attacks, specifically Nettack and Metattack, represent sophisticated approaches to com- promising graph-based learning systems through struc- tural perturbations. Nettack operates as a targeted at- tack mechanism that modifies the graph structure around specific nodes by strategically adding or removing edges and manipulating ...

    work page

  16. [16]

    Fortunato, Community detection in graphs, Phys

    S. Fortunato, Community detection in graphs, Phys. Rep 486, 75 (2010)

    work page 2010

  17. [17]

    M. E. Newman, Modularity and community structure in networks, Proc. Natl. Acad. Sci. U. S. A 103, 8577 (2006)

    work page 2006

  18. [18]

    Girvan and M

    M. Girvan and M. E. Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci, U. S. A 99, 7821 (2002)

    work page 2002

  19. [19]

    Wandelt, X

    S. Wandelt, X. Shi, and X. Sun, Estimation and improve- ment of transportation network robustness by exploiting communities, Reliab. Eng. Syst. Saf 206, 107307 (2021)

    work page 2021

  20. [20]

    Lancichinetti and S

    A. Lancichinetti and S. Fortunato, Community detection algorithms: a comparative analysis, Phys. Rev. E 80, 056117 (2009)

    work page 2009

  21. [21]

    Moriano, J

    P. Moriano, J. Finke, and Y.-Y. Ahn, Community-based event detection in temporal networks, Sci. Rep 9, 4358 (2019)

    work page 2019

  22. [22]

    Aref and M

    S. Aref and M. Mostajabdaveh, Analyzing modularity maximization in approximation, heuristic, and graph neural network algorithms for community detection, J. Comput. Sci 78, 102283 (2024)

    work page 2024

  23. [23]

    Schuurman and E

    T. Schuurman and E. Bruner, Modularity and commu- nity detection in human brain morphology, Anat. Rec 307, 345 (2024)

    work page 2024

  24. [24]

    F. R. Khawaja, Z. Zhang, Y. Memon, and A. Ullah, Ex- ploring community detection methods and their diverse applications in complex networks: a comprehensive re- view, Soc. Netw. Anal. Min 14, 115 (2024)

    work page 2024

  25. [25]

    Scarselli, M

    F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, The graph neural network model, IEEE. Trans. Neural. Netw 20, 61 (2008)

    work page 2008

  26. [26]

    Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, A comprhensive survey on graph neural networks, IEEE. Trans. Neural. Netw. Learning. Syst 32, 4 (2020)

    work page 2020

  27. [27]

    K. Xu, W. Hu, J. Leskovec, and S. Jegelka, How powerful are graph neural networks?, arXiv preprint arXiv:1810.00826 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  28. [28]

    Veliˇ ckovi´ c, Everything is connected: Graph neural net- works, Curr

    P. Veliˇ ckovi´ c, Everything is connected: Graph neural net- works, Curr. Opin. Struct. Biol 79, 102538 (2023)

    work page 2023

  29. [29]

    T. N. Kipf and M. Welling, Semi-supervised classifica- tion with graph convolutional networks, arXiv preprint arXiv:1609.02907 (2016)

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  30. [30]

    Graph Attention Networks

    P. Veliˇ ckovi´ c, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, Graph attention networks, arXiv preprint arXiv:1710.10903 (2017)

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  31. [31]

    Hamilton, Z

    W. Hamilton, Z. Ying, and J. Leskovec, Inductive rep- resentation learning on large graphs, Advances in neural information processing systems 30 (2017)

    work page 2017

  32. [32]

    X. Su, S. Xue, F. Liu, J. Wu, J. Yang, C. Zhou, W. Hu, C. Paris, S. Nepal, D. Jin, et al., A comprehensive survey on community detection with deep learning, IEEE Trans. Neural. Netw. Learn. Syst (2022)

    work page 2022

  33. [33]

    Y. Ren, J. Pu, Z. Yang, J. Xu, G. Li, X. Pu, S. Y. Philip, and L. He, Deep clustering: A comprehensive survey, IEEE. Trans. Neural. Netw. Learn. Syst (2024)

    work page 2024

  34. [34]

    Y. Liu, J. Xia, S. Zhou, X. Yang, K. Liang, C. Fan, Y. Zhuang, S. Z. Li, X. Liu, and K. He, A survey of deep graph clustering: Taxonomy, challenge, application, and open resource, arXiv preprint arXiv:2211.12875 (2022)

    work page arXiv 2022

  35. [35]

    Z. Ying, J. You, C. Morris, X. Ren, W. Hamilton, and J. Leskovec, Hierarchical graph representation learning with differentiable pooling, Advances in neural informa- tion processing systems 31 (2018)

    work page 2018

  36. [36]

    F. M. Bianchi, D. Grattarola, and C. Alippi, Spectral clustering with graph neural networks for graph pool- ing, in International Conference on Machine Learning (PMLR, 2020) pp. 874–883

    work page 2020

  37. [37]

    Tsitsulin, J

    A. Tsitsulin, J. Palowitch, B. Perozzi, and E. M¨ uller, Graph clustering with graph neural networks, J. Mach. Learn. Res 24, 1 (2023)

    work page 2023

  38. [38]

    Z¨ ugner, A

    D. Z¨ ugner, A. Akbarnejad, and S. G¨ unnemann, Adver- sarial attacks on neural networks for graph data, in Pro- ceedings of the 24th ACM SIGKDD International Con- ference on Knowledge Discovery & Data Mining (2018) pp. 2847–2856

    work page 2018

  39. [39]

    Z¨ ugner and S

    D. Z¨ ugner and S. G¨ unnemann, Adversarial attacks on graph neural networks via meta learning (2024), arXiv:1902.08412 [cs.LG]

    work page arXiv 2024

  40. [40]

    B. Wang, J. Jia, X. Cao, and N. Z. Gong, Certified ro- bustness of graph neural networks against adversarial structural perturbation, in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (2021) pp. 1645–1653

    work page 2021

  41. [41]

    G¨ unnemann, Graph neural networks: Adversarial ro- bustness, in Graph neural networks: foundations, fron- tiers, and applications (Springer, 2022) pp

    S. G¨ unnemann, Graph neural networks: Adversarial ro- bustness, in Graph neural networks: foundations, fron- tiers, and applications (Springer, 2022) pp. 149–176

    work page 2022

  42. [42]

    Zhang, X

    B. Zhang, X. Guo, Z. Tu, and J. Zhang, Graph alter- nate learning for robust graph neural networks in node classification, Neural. Comput. Appl 34, 8723 (2022)

    work page 2022

  43. [43]

    Zhang, B

    H. Zhang, B. Wu, X. Yuan, S. Pan, H. Tong, and J. Pei, Trustworthy graph neural networks: Aspects, methods, and trends, Proceedings of the IEEE 112, 97 (2024)

    work page 2024

  44. [44]

    L. Sun, Y. Dou, C. Yang, K. Zhang, J. Wang, S. Y. Philip, L. He, and B. Li, Adversarial attack and defense on graph data: A survey, IEEE. Trans. Knowl. Data. Eng 35, 7693 (2022)

    work page 2022

  45. [45]

    Tian and P

    M. Tian and P. Moriano, Robustness of community struc- ture under edge addition, Phys. Rev. E 108, 054302 (2023)

    work page 2023

  46. [46]

    Z.-F. Wei, P. Moriano, and R. Kannan, Robustness of graph embedding methods for community detection, arXiv preprint arXiv:2405.00636 (2024)

    work page arXiv 2024

  47. [47]

    Lancichinetti, S

    A. Lancichinetti, S. Fortunato, and F. Radicchi, Bench- mark graphs for testing community detection algorithms, Phys. Rev. E 78, 046110 (2008)

    work page 2008

  48. [48]

    Karrer and M

    B. Karrer and M. E. Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E 83, 016107 (2011)

    work page 2011

  49. [49]

    A. K. Dey, Y. Tian, and Y. R. Gel, Community detec- tion in complex networks: From statistical foundations to data science applications, Wiley Interdisciplinary Re- views: Computational Statistics 14, e1566 (2022)

    work page 2022

  50. [50]

    Y. Zhao, E. Levina, and J. Zhu, Consistency of com- munity detection in networks under degree-corrected stochastic block models, Ann. Stat 40, 2266–2292 (2012)

    work page 2012

  51. [51]

    Tsitsulin, B

    A. Tsitsulin, B. Rozemberczki, J. Palowitch, and B. Per- ozzi, Synthetic graph generation to benchmark graph learning, arXiv preprint arXiv:2204.01376 (2022)

    work page arXiv 2022

  52. [52]

    A. J. Gates, I. B. Wood, W. P. Hetrick, and Y.-Y. Ahn, Element-centric clustering comparison unifies overlaps and hierarchy, Sci. Rep 9, 8574 (2019). 17

    work page 2019

  53. [53]

    Goel, Robust graph neural networks, https://github.com/jdg-stat/robustgnn (2025), gitHub repository

    J. Goel, Robust graph neural networks, https://github.com/jdg-stat/robustgnn (2025), gitHub repository

    work page 2025

  54. [54]

    Lancichinetti and S

    A. Lancichinetti and S. Fortunato, Benchmarks for test- ing community detection algorithms on directed and weighted graphs with overlapping communities, Phys. Rev. E 80, 016118 (2009)

    work page 2009

  55. [55]

    Hagberg, P

    A. Hagberg, P. J. Swart, and D. A. Schult, Exploring net- work structure, dynamics, and function using NetworkX , Tech. Rep. (Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008)

    work page 2008

  56. [56]

    P. W. Holland, K. B. Laskey, and S. Leinhardt, Stochastic blockmodels: First steps, Social networks 5, 109 (1983)

    work page 1983

  57. [57]

    Z. Yang, W. Cohen, and R. Salakhudinov, Revisiting semi-supervised learning with graph embeddings, in In- ternational Conference on Machine Learning (PMLR,

    work page

  58. [58]

    Y. Xu, M. Lanier, A. Sarkar, and Y. Vorobeychik, At- tacks on node attributes in graph neural networks, arXiv preprint arXiv:2402.12426 (2024)

    work page arXiv 2024

  59. [59]

    Souravlas, S

    S. Souravlas, S. Anastasiadou, and S. Katsavounis, A sur- vey on the recent advances of deep community detection, Appl. Sci 11, 7179 (2021)

    work page 2021

  60. [60]

    Sobolevsky and A

    S. Sobolevsky and A. Belyi, Graph neural network in- spired algorithm for unsupervised network community detection, Appl. Netw. Sci 7, 63 (2022)

    work page 2022

  61. [61]

    Leeney and R

    W. Leeney and R. McConville, Uncertainty in gnn learn- ing evaluations: A comparison between measures for quantifying randomness in gnn community detection, En- tropy 26, 78 (2024)

    work page 2024

  62. [62]

    V. D. Kumar, S. Sreesankar, K. Dinesan, P. B. Nair, and L. Deepthi, Analyzing gnn models for commu- nity detection using graph embeddings: A comparative study, in 2024 15th International Conference on Comput- ing Communication and Networking Technologies (ICC- CNT) (IEEE, 2024) pp. 1–8

    work page 2024

  63. [63]

    Merkwirth and T

    C. Merkwirth and T. Lengauer, Automatic generation of complementary descriptors with molecular graph net- works, J. Chem. Inf. Model 45, 1159 (2005)

    work page 2005

  64. [64]

    X. Su, S. Xue, F. Liu, J. Wu, J. Yang, C. Zhou, W. Hu, C. Paris, S. Nepal, D. Jin, et al. , A comprehensive sur- vey on community detection with deep learning, IEEE. Trans. Neural. Netw. Learning. Syst (2022)

    work page 2022

  65. [65]

    Budel, M

    G. Budel, M. Kitsak, R. Aldecoa, K. Zuev, and D. Kri- oukov, Random hyperbolic graphs in d+1 dimensions, Physical Review E 109, 054131 (2024)

    work page 2024

  66. [66]

    D´ esy, P

    B. D´ esy, P. Desrosiers, and A. Allard, Dimension mat- ters when modeling network communities in hyperbolic spaces, PNAS nexus 2, pgad136 (2023)

    work page 2023

  67. [67]

    M. Yang, M. Zhou, Z. Li, J. Liu, L. Pan, H. Xiong, and I. King, Hyperbolic graph neural networks: A review of methods and applications, arXiv:2202.13852 (2025). 18 APPENDIX A. Theoretical details Cut-based metrics Let {Ci}K i=1 be disjoint partitions of V. We can define a cut as cut(C1, . . . ,CK) = 1 2 KX k=1 |(u, v) ∈ E : u ∈ C k, v ∈ ˆCk|, here ˆCk is ...

    work page arXiv 2025