Node Role-Guided LLMs for Dynamic Graph Clustering

Dongyuan Li, Ying Zhang, Yaozu Wu, Renhe Jiang

Abstract

Dynamic graph clustering aims to detect and track time-varying clusters in dynamic graphs, revealing how complex real-world systems evolve over time. However, existing methods are predominantly black-box models. They lack interpretability in their clustering decisions and fail to provide semantic explanations of why clusters form or how they evolve, severely limiting their use in safety-critical domains such as healthcare or transportation. To address these limitations, we propose an end-to-end interpretable framework that maps continuous graph embeddings into discrete semantic concepts through learnable prototypes. Specifically, we first decompose node representations into orthogonal role and clustering subspaces, so that nodes with similar roles (e.g., hubs, bridges) but different cluster affiliations can be properly distinguished. We then introduce five node role prototypes (Leader, Contributor, Wanderer, Connector, Newcomer) in the role subspace as semantic anchors, transforming continuous embeddings into discrete concepts to facilitate LLM understanding of node roles within communities. Finally, we design a hierarchical LLM reasoning mechanism to generate both clustering results and natural language explanations, while providing consistency feedback as weak supervision to refine node representations. Experimental results on four synthetic and six real-world benchmarks demonstrate the effectiveness, interpretability, and robustness of DyG-RoLLM.

Introduction

Dynamic graph clustering is essential for tracking the evolution of communities in networks, such as social trends or epidemic spreads. Despite its importance, current state-of-the-art models often function as "black boxes," providing clustering assignments without semantic justification. This lack of transparency is a significant barrier in high-stakes domains like healthcare and transportation. Furthermore, traditional methods struggle to distinguish between a node's functional role (e.g., a "bridge" between groups) and its community affiliation.

To address these challenges, we introduce DyG-RoLLM, a framework designed to provide high-accuracy clustering alongside human-verifiable natural language explanations. By bridging the gap between continuous graph neural network (GNN) embeddings and discrete semantic reasoning, DyG-RoLLM offers a transparent window into community evolution.

The DyG-RoLLM Framework

DyG-RoLLM operates through three primary innovations designed to enhance both performance and interpretability:

  1. Orthogonal Subspace Decomposition: To prevent a node's structural role from being conflated with its community membership, the model splits node representations into two mathematically independent (orthogonal) subspaces. One subspace focuses on modularity for clustering, while the other captures semantic roles.
  2. Node Role Prototypes: The framework defines five "semantic anchors" based on structural graph theory: Leader (high-centrality hubs), Contributor (stable intra-community nodes), Wanderer (weakly connected boundary nodes), Connector (bridges between communities), and Newcomer (recently joined, high-volatility nodes).
  3. Hierarchical LLM Reasoning: Utilizing a Chain-of-Thought (CoT) mechanism, Large Language Models (LLMs) analyze the "supply and demand" of roles within communities and evaluate temporal consistency. This allows the LLM to act as a logical filter, correcting structural misclusterings made by the GNN.
The DyG-RoLLM architecture, showing the pipeline from graph encoding to hierarchical LLM reasoning and output correction.

Crucially, the framework employs Bidirectional Feedback. When the LLM identifies a reasoning-based assignment that differs from the initial structural clustering with high confidence, it provides weak supervision to refine the GNN’s underlying representations.

Experimental Evaluation

We evaluated DyG-RoLLM on a diverse set of benchmarks, including four synthetic datasets simulating evolution events (e.g., Birth-Death, Merge-Split) and six massive real-world datasets like arXiv (28k nodes), Flickr (2.3M nodes), and Youtube (3.2M nodes).

Performance and Accuracy

DyG-RoLLM consistently outperformed state-of-the-art baselines in Normalized Mutual Information (NMI) and F1-score. On the Flickr and Youtube datasets, it achieved NMI improvements of 12.9% and 9.8%, respectively, over standard GNN baselines. The model also demonstrated superior modularity and density across various timestamps.

Performance comparison showing NMI over time for Dublin and arXiv datasets, and modularity/density distributions for Flickr and Youtube.

Interpretability and Robustness

Beyond raw accuracy, the framework excels in explanation fidelity. Using the Explanation Fidelity Score (EFS), we verified that over 89% of the LLM's structural claims were factually supported by the graph data. Additionally, DyG-RoLLM proved highly robust to noise; when subjected to 30% noisy edges, it maintained significantly higher performance stability than traditional matrix factorization methods, as the LLM reasoning successfully rejected logically implausible structural connections.

Conclusion

DyG-RoLLM represents a significant step toward interpretable dynamic graph analysis. By decomposing roles and communities and leveraging the logical reasoning of LLMs, it provides both state-of-the-art performance and transparent explanations. Future work will focus on extending the framework to continuous-time dynamic graphs and integrating multimodal node attributes to further enrich semantic role descriptions.

Summary updated

Abstract

Dynamic graph clustering aims to detect and track time-varying clusters in dynamic graphs, revealing how complex real-world systems evolve over time. However, existing methods are predominantly black-box models. They lack interpretability in their clustering decisions and fail to provide semantic explanations of why clusters form or how they evolve, severely limiting their use in safety-critical domains such as healthcare or transportation. To address these limitations, we propose an end-to-end interpretable framework that maps continuous graph embeddings into discrete semantic concepts through learnable prototypes. Specifically, we first decompose node representations into orthogonal role and clustering subspaces, so that nodes with similar roles (e.g., hubs, bridges) but different cluster affiliations can be properly distinguished. We then introduce five node role prototypes (Leader, Contributor, Wanderer, Connector, Newcomer) in the role subspace as semantic anchors, transforming continuous embeddings into discrete concepts to facilitate LLM understanding of node roles within communities. Finally, we design a hierarchical LLM reasoning mechanism to generate both clustering results and natural language explanations, while providing consistency feedback as weak supervision to refine node representations. Experimental results on four synthetic and six real-world benchmarks demonstrate the effectiveness, interpretability, and robustness of DyG-RoLLM. Code is available at https://github.com/Clearloveyuan/DyG-RoLLM.
BibTeX
@inproceedings{li2026node,
  author = {Dongyuan Li and Ying Zhang and Yaozu Wu and Renhe Jiang},
  title = {{Node Role-Guided LLMs for Dynamic Graph Clustering}},
  booktitle = {The Web Conference},
  year = {2026},
  doi = {10.1145/3774904.3792704},
}
Figure