Node Role-Guided LLMs for Dynamic Graph Clustering

Dongyuan Li; Ying Zhang; Yaozu Wu; Renhe Jiang

cs.LGMar 14, 2026

Node Role-Guided LLMs for Dynamic Graph Clustering

Authors: Dongyuan Li, Ying Zhang, Yaozu Wu, Renhe Jiang

Organizations: The University of Tokyo Tokyo, Japan · RIKEN Sendai, Japan

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.

Figures & tables

Figure 1. Overview of DyG-RoLLM. We first learn cluster-aware representation through orthogonal decomposition, then bridge them to semantics via node-roles prototypes, and finally enable hierarchical LLM reasoning for interpretable clustering.

Dynamic Graphs	# of Nodes	# of Edges	# of Snapshots
Birth-Death (BD)	30K & 100K	12M & 24M	10 & 20
Expand-Contract (EC)	30K & 100K	13M & 26M	10 & 20
Disappear-Reappear (DR)	30K & 100K	13M & 28M	10 & 20
Merge-Split (MS)	30K & 100K	14M & 29M	10 & 20
Wikipedia	8,400	162,000	5
Dublin	11,000	415,900	5

Table 1. Detailed statistics of dynamic graph benchmarks.

Methods		BD-30K		EC-30K		BD-100K		DR-100K		MS-100K		Wikipedia		Dublin		arXiv		SO		Flickr		Youtube
Methods		NMI	NF1	NMI	NF1	NMI	NF1	NMI	NF1	NMI	NF1	NMI	NF1	NMI	NF1	NMI	NF1	NMI	NF1	NMI	NF1	NMI	NF1
NN-based	node2vec ( Grover and Leskovec, 2016 )	93.8	85.8	93.2	83.6	90.3	84.2	91.2	85.6	89.0	78.2	33.5	10.2	50.3	23.2	44.3	26.8	40.3	23.3	42.4	25.5	42.8	24.5
	RNNGCN ( Yao and Joe-Wong, 2021 )	96.6	84.5	95.9	85.1	90.8	84.9	92.1	84.3	91.2	80.9	40.3	22.5	52.2	31.6	45.4	26.2	40.8	23.8	48.5	30.2	47.6	32.3
	SepNE ( Li et al., 2019 )	92.5	89.4	92.1	81.8	89.1	82.2	89.0	81.1	89.2	78.6	31.4	9.8	49.2	21.0	42.8	25.8	39.2	22.1	40.3	22.4	39.5	21.0
	ROLAND ( You et al., 2022 )	95.5	83.2	94.1	83.8	92.8	85.1	93.3	85.8	92.8	81.6	42.2	22.3	53.6	31.6	46.8	27.6	44.8	29.2	47.5	31.4	48.4	33.2
	TGC ( Liu et al., 2024a )	95.3	83.0	93.8	83.6	92.0	84.5	92.8	85.4	91.5	81.2	41.3	22.3	52.8	31.3	45.8	26.8	44.6	29.0	47.8	31.6	47.9	32.6

Table 2. Overall performances on dynamic graphs. Bold and Underline indicate the best and second-best performing methods. Symbol

{\dagger}

indicates that DyG-RoLLM significantly surpassed all baselines with a p-value

<0.005

. N/A means that it cannot be executed due to memory and running time constraints.

Figure 2. Performance comparison of (A-B) varying timestamps and (C) modularity and density of selected baselines.

Figure 3. Efficiency comparison on large dynamic graphs.

Method	Wikipedia		Dublin		SO
Method	RCS↑	EFS↑	RCS↑	EFS↑	RCS↑	EFS↑
ComGPT (+CoT)	0.69	0.58	0.64	0.55	0.71	0.60
CommLLM (+CoT)	0.62	0.51	0.58	0.47	0.65	0.53
DyG-RoLLM (w/o Role)	0.75	0.66	0.68	0.68	0.83	0.82
DyG-RoLLM (w/o CoT)	0.85	0.64	0.82	0.66	0.87	0.68
DyG-RoLLM	0.88	0.89	0.88	0.90	0.92	0.91

Table 3. Interpretability on real-world dynamic graphs.

Method	Clarity	Soundness	Complete	Trust	Action
ComGPT (+CoT)	3.2	2.8	2.6	2.9	2.5
CommLLM (+CoT)	2.9	2.5	2.4	2.6	2.3
DyG-RoLLM (w/o Role)	3.5	3.3	3.1	3.4	3.2
DyG-RoLLM (w/o CoT)	3.8	3.6	3.4	3.7	3.5
DyG-RoLLM (full)	4.4	4.5	4.3	4.6	4.2

Table 4. Human evaluation with average scores on 1-5 scale.

Figure 4. Noise Attacks. NMI w.r.t. percentage of noisy edges.

Methods		Wikipedia		arXiv
Methods		NMI↑	NF1↑	NMI↑	NF1↑
Remove	w/o Orthogonal Subspace	42.2	22.4	43.5	15.8
	w/o Clustering loss Eq.( 6 )	50.3	25.6	51.6	30.0
	w/o Temporal loss Eq.( 7 )	51.0	26.3	52.5	31.7
	w/o Contrastive loss Eq.( 11 )	50.6	25.7	51.7	30.1
	w/o Consistent loss Eq.( 16 )	50.0	25.1	51.2	29.7

Table 5. Ablation and strategy replacement of DyG-RoLLM.

Figure 5. Hyperparameter tuning results.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Prototype ( $\mathbf{p}_{i}^{n}$ )	Centrality ( $\mathbf{f}^{\mathbf{C}}$ )			Local Structure ( $\mathbf{f}^{\mathbf{L}}$ )		Temporal ( $\mathbf{f}^{\mathbf{T}}$ )
	Degree	Betweenness	Closeness	Clustering Coeff.	Intra-Density	Volatility	Stability
Community Leader ( $\mathbf{p}_{1}^{n}$ )	$\mathbf{1}$	$\mathbf{0}$	$\mathbf{1}$	$\mathbf{1}$	$\mathbf{1}$	$\mathbf{0}$	$\mathbf{1}$
Active Member ( $\mathbf{p}_{2}^{n}$ )	$\mathbf{1}$	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{1}$	$\mathbf{1}$	$\mathbf{0}$	$\mathbf{1}$
Peripheral Member ( $\mathbf{p}_{3}^{n}$ )	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{1}$	$\mathbf{0}$
Bridge Node ( $\mathbf{p}_{4}^{n}$ )	$\mathbf{1}$	$\mathbf{1}$	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{1}$
Newcomer/Evolver ( $\mathbf{p}_{5}^{n}$ )	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{0}$	$\mathbf{1}$	$\mathbf{0}$

Appendix

Table 6. The Node Role Prototype Prior Matrix (

\mathbf{f}^{\text{prior}}

). The matrix encodes the ideal structural and temporal characteristics of the five predefined roles. A value of

\mathbf{1}

indicates a required high intensity for the role, while

\mathbf{0}

indicates a low intensity.

Graph Clustering

Graph clustering groups network nodes by connectivity, attributes, or shared roles to reveal communities and other mesoscale structure.

See all 78 papers

Clustering as Reasoning: A $k$ -Means Interpretation of Chain-of-Thought Graph Learning
May 24, 2026Xuanting Xie, Zhaochen Guo, Bingheng Li +4Graph Representation Learning Text-Attributed Graph Learning
University of Electronic Science and Technology of China, 611731, Chengdu, China · Singapore Management University, 188065, Singapore · Michigan State University, East Lansing, 48824, MI, USA +1
Robust Contrastive Graph Clustering with Adaptive Local-Global Integration
May 27, 2026Lei Zhang, Fubo Sun, Haipeng Yang +2Graph Representation Learning Multi-Scale Feature Fusion
School of Computer Science and Technology, Anhui University · College of Management and Economics, Tianjin University
AdaSTORM: Scaling LLM Reasoning on Dynamic Graphs via Adaptive Spatio-Temporal Multi-Agent Collaboration
Jun 15, 2026Bing Hao, Ruijie Wang, Haodong Qian +5Graph Partitioning LLM Reasoning with Graphs
1Tianjin University, China · 2Beihang University, China

May 24, 2026J/K move · Enter open · S save

Clustering as Reasoning: A $k$ -Means Interpretation of Chain-of-Thought Graph Learning

Xuanting Xie, Zhaochen Guo, Bingheng Li, Xingtong Yu+3

University of Electronic Science and Technology of China, 611731, Chengdu, China · Singapore Management University, 188065, Singapore · Michigan State University, East Lansing, 48824, MI, USA+1

Graph Representation Learning Text-Attributed Graph Learning LLMs for Graph Learning

Open paper AskPDF arXiv

Chain-of-Thought (CoT) prompting has shown promise in enhancing the reasoning capabilities of large language models (LLMs) on text-attributed graphs (TAGs). This work reframes CoT-based graph learning through the principle of clustering as reasoning, offering a

k

-means interpretation of how iterative reasoning operates over graph-structured data. We observe that existing graph CoT methods rely on disjoint architectures and fixed graph representations, limiting step-by-step semantic-topological interaction and interpretability. To overcome this limitation, we propose a unified framework named KCoT that integrates CoT reasoning with graph representation learning. Our key theoretical result reveals a formal mathematical correspondence between a Transformer block and the

k

-means algorithm, allowing reasoning to be interpreted as iterative assignment and update steps. Based on this insight, we introduce a Semantic Discriminating Prompt that explicitly formulates these steps as structured CoT reasoning, together with a structure-grounded alignment strategy to fuse topological priors with evolving thought-conditioned representations. Experiments on standard benchmarks demonstrate consistent improvements over state-of-the-art methods, validating clustering as a principled mechanism for CoT-based graph learning.

Abstract

Graph Clustering

Explore similar work

Clustering as Reasoning: A kkk-Means Interpretation of Chain-of-Thought Graph Learning

Robust Contrastive Graph Clustering with Adaptive Local-Global Integration

AdaSTORM: Scaling LLM Reasoning on Dynamic Graphs via Adaptive Spatio-Temporal Multi-Agent Collaboration

Clustering as Reasoning: A $k$ -Means Interpretation of Chain-of-Thought Graph Learning