Breaking Structural Isolation: Scalable Graph Clustering via Community-Aware Sampling and Structural Entropy

# Breaking Structural Isolation: Scalable Graph Clustering via Community-Aware Sampling and Structural Entropy
Source: [https://arxiv.org/html/2607.05469](https://arxiv.org/html/2607.05469)
###### Abstract\.

Unsupervised graph clustering is a fundamental technique for uncovering underlying semantic patterns in large\-scale networks\. Although Graph Contrastive Learning has demonstrated promising performance, existing methods often suffer from the ”structural isolation” issue during mini\-batch training, making it challenging to capture cohesive community structures that characterize the global topological distribution\. To address these challenges, we proposeSCISE, aScalable unsupervised graphClustering framework that preserves structuralIntegrity by synergizing community\-aware sampling with constrainedStructuralEntropy\. Specifically, we first introduce the Structural Entropy Community Constraint operator \(SECC\), which optimizes structural information within a constrained solution space to mitigate community fragmentation and enhance partition cohesion\. Second, to prevent global information loss during batch training, we design a Community\-Aware Sampling Expansion \(CSampE\) mechanism that incorporates the community context of target nodes into sampling batches, effectively breaking structural barriers and preserving topological integrity\. Finally, we devise a Structural Contrastive Learning \(StructCL\) module that refines edge weights based on intra\-batch structural similarity, guiding the encoder to learn representations in a higher\-order structural space\. Extensive experiments on six mainstream benchmark datasets demonstrate thatSCISEsignificantly outperforms state\-of\-the\-art algorithms, with ablation studies and robustness analyses further validating its effectiveness and reliability for real\-world large\-scale graphs\.

PVLDB Reference Format: PVLDB, 19\(1\): XXX\-XXX, 2026\. [doi:XX\.XX/XXX\.XX](https://doi.org/XX.XX/XXX.XX)††This work is licensed under the Creative Commons BY\-NC\-ND 4\.0 International License\. Visit[https://creativecommons\.org/licenses/by\-nc\-nd/4\.0/](https://creativecommons.org/licenses/by-nc-nd/4.0/)to view a copy of this license\. For any use beyond those covered by this license, obtain permission by emailing[info@vldb\.org](https://arxiv.org/html/2607.05469v1/mailto:[email protected])\. Copyright is held by the owner/author\(s\)\. Publication rights licensed to the VLDB Endowment\. Proceedings of the VLDB Endowment, Vol\. 19, No\. 1 ISSN 2150\-8097\. [doi:XX\.XX/XXX\.XX](https://doi.org/XX.XX/XXX.XX)

PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at[https://github\.com/SELGroup/SCISE](https://github.com/SELGroup/SCISE)\.

## 1\.Introduction

Graph\-structured data has become pervasive in representing complex relational information across diverse domains, such as social media, citation networks, and biological systems\(Hamiltonet al\.,[2017](https://arxiv.org/html/2607.05469#bib.bib13); Kipf and Welling,[2017](https://arxiv.org/html/2607.05469#bib.bib30)\)\. As a fundamental task in network analysis, unsupervised graph clustering aims to partition nodes with high topological and attribute affinities into communities without reliance on manual labeling, thereby revealing the underlying semantic patterns and structural motifs within complex networks\(Fortunato,[2010](https://arxiv.org/html/2607.05469#bib.bib31); Xieet al\.,[2016](https://arxiv.org/html/2607.05469#bib.bib32)\)\. This capability is critical for numerous downstream applications, including community detection, targeted recommendation, and anomaly discovery\(Yinget al\.,[2018](https://arxiv.org/html/2607.05469#bib.bib33); Akogluet al\.,[2015](https://arxiv.org/html/2607.05469#bib.bib34)\)\. Given the exponential growth of graph data and the prohibitive cost of human annotation, developing effective and scalable unsupervised clustering frameworks is of paramount importance for extracting meaningful structural insights from unlabeled, large\-scale relational data\(Wuet al\.,[2020](https://arxiv.org/html/2607.05469#bib.bib35); Veličkovićet al\.,[2018](https://arxiv.org/html/2607.05469#bib.bib36)\)\.

![Refer to caption](https://arxiv.org/html/2607.05469v1/x1.png)Figure 1\.Comparison of sampling strategies\. \(a\) Random: fragments communities into batches\. \(b\) Local: limited to neighborhood context\. \(c\)SCISE\(Ours\): incorporates global community context to preserve structural integrity within mini\-batches\.The prevailing paradigm for unsupervised graph clustering has shifted towards integrating Graph Neural Networks \(GNNs\) with Graph Contrastive Learning \(GCL\) to learn discriminative semantic embeddings\(Boet al\.,[2020](https://arxiv.org/html/2607.05469#bib.bib38); Liet al\.,[2025](https://arxiv.org/html/2607.05469#bib.bib39)\)\. Typically, these methods leverage message\-passing mechanisms and consistency regularization to reinforce feature similarity among intra\-cluster nodes\(Zhuet al\.,[2021](https://arxiv.org/html/2607.05469#bib.bib40)\)\. However, as the scale of real\-world networks grows exponentially, these frameworks encounter a formidable bottleneck: the trade\-off between computational scalability and structural integrity\(Gaoet al\.,[2018](https://arxiv.org/html/2607.05469#bib.bib41); Hamiltonet al\.,[2017](https://arxiv.org/html/2607.05469#bib.bib13)\)\.

To handle massive graphs, existing methods predominantly adopt mini\-batch training via various stochastic sampling strategies\(Zenget al\.,[2019](https://arxiv.org/html/2607.05469#bib.bib52)\)\. Although GCL has demonstrated remarkable performance in representation learning, its efficacy on large\-scale data is severely hampered by the ”structural isolation” issue induced by batch\-wise operations\(Shiet al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib42)\)\. Since traditional samplers primarily focus on local neighborhood reachability, they inevitably sever the global community context, sequestering nodes of the same semantic cluster into disparate batches\. Such limitations are visually depicted in Figure[1](https://arxiv.org/html/2607.05469#S1.F1), where conventional random sampling \(a\) and local neighborhood sampling \(b\) fail to maintain community coherence within mini\-batches\. This structural isolation inherently erodes global topological awareness, a problem further exacerbated by the inherent limitations of current technological paths: contrastive\-based frameworks\(Liuet al\.,[2022a](https://arxiv.org/html/2607.05469#bib.bib2); Kulatillekeet al\.,[2025](https://arxiv.org/html/2607.05469#bib.bib37); Yanget al\.,[2023b](https://arxiv.org/html/2607.05469#bib.bib3); Shenet al\.,[2023](https://arxiv.org/html/2607.05469#bib.bib43)\)typically lack mechanisms to compensate for such sampling\-induced fragmentation, while structure\-aware methods\(Sunet al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib6); Liuet al\.,[2023b](https://arxiv.org/html/2607.05469#bib.bib4); Tsitsulinet al\.,[2023](https://arxiv.org/html/2607.05469#bib.bib5)\)often rely on noisy, unrefined graph statistics\. Consequently, the absence of global topological awareness makes it challenging for models to capture cohesive community structures, leading to fragmented representations that fail to reflect the underlying semantic organization\.

To address the aforementioned challenges, we proposeSCISE, aScalable unsupervised graphClustering framework designed to preserve structuralIntegrity through the synergy of community\-aware sampling and constrainedStructuralEntropy\.SCISEreconciles the inherent conflict between computational scalability and community cohesion through three synergistic components\. First, we introduce the Structural Entropy Community Constraint \(SECC\) operator to explicitly quantify and reinforce community compactness\. Unlike traditional structural entropy metrics that often lead to excessive partitioning in unlabeled scenarios, SECC optimizes structural information within a bounded solution space constrained by the target community number\. This allows the model to maintain minimal entropy while effectively mitigating community fragmentation\. Second, to counteract the information loss inherent in mini\-batch training, we design a Community\-Aware Sampling Expansion \(CSampE\) mechanism\. By identifying and incorporating the global community context of target nodes into each sampling batch, CSampE dismantles structural barriers between batches and restores the topological continuity required for stable optimization\. Finally, we devise a Structural Contrastive Learning \(StructCL\) method to guide the encoder toward a more discriminative representation space\. Diverging from conventional paradigms that rely on noisy raw topology, StructCL refines higher\-order edge weights based on latent structural similarities among intra\-batch nodes\. These refined affinities serve as structural guidance to maximize consistency among similar nodes, ultimately yielding high\-quality embeddings that are partitioned into final clusters\.

To evaluate the effectiveness of the proposedSCISE, we conduct extensive experiments on three medium\-scale datasets \(Photo, Computer, Pubmed\) and three large\-scale datasets \(Ogbn\-arxiv, Reddit, Ogbn\-products\)\. Quantitative results yield several critical insights: First, comprehensive performance analysis demonstrates thatSCISEachieves overall superior performance compared to ten state\-of\-the\-art baselines, confirming its consistent efficacy across both medium and large\-scale scenarios\. Second, rigorous ablation studies dissect the synergistic effects of our modules, validating that SECC, CSampE, and StructCL are each indispensable for preserving structural integrity\. Finally, the stability analysis assesses the model’s invariance to hyper\-parameter variations, underscoring its robustness and deployment in real\-world, large\-scale systems\. The main contributions of this work are summarized as follows\.

∙\\bulletScalable Framework \(SCISE\):We proposeSCISE, an unsupervised graph clustering framework that effectively harmonizes the conflict between computational scalability and structural integrity through the synergy of community\-aware sampling and constrained structural entropy\.

∙\\bulletCommunity\-Aware Sampling Expansion \(CSampE\):We develop the CSampE mechanism to bridge ”structural isolation” by adaptively incorporating global community contexts into mini\-batches, thereby restoring topological continuity in mini\-batch training\.

∙\\bulletStructural Entropy Community Constraint \(SECC\):We introduce the SECC operator to explicitly quantify community compactness within a constrained space, significantly mitigating partition fragmentation and ensuring global community integrity\.

∙\\bulletExtensive Validation and Insights:Through extensive evaluations on six benchmark datasets, we demonstrate the overall superior performance and robustness of SCISE, while identifying the synergistic and complementary effects of its core components\.

![Refer to caption](https://arxiv.org/html/2607.05469v1/x2.png)Figure 2\.Overall framework ofSCISE\.
## 2\.Related Work

### 2\.1\.Unsupervised Graph Clustering

Unsupervised graph clustering evolves from traditional statistical methods to sophisticated deep learning paradigms\. Systematic surveys\(Liuet al\.,[2022b](https://arxiv.org/html/2607.05469#bib.bib44); Renet al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib45)\)establish comprehensive taxonomies, categorizing the field into GNN\-based and contrastive learning\-based approaches while analyzing the trade\-offs between generative and discriminative models\. Within the GNN paradigm, DMoN\(Tsitsulinet al\.,[2023](https://arxiv.org/html/2607.05469#bib.bib5)\)achieves end\-to\-end community detection via modularity maximization, while DeepCut\(Aflaloet al\.,[2023](https://arxiv.org/html/2607.05469#bib.bib46)\)and RGC\(Liuet al\.,[2023a](https://arxiv.org/html/2607.05469#bib.bib47)\)extend these techniques to unsupervised image segmentation and reinforcement learning\-based automated cluster number determination, respectively\. Recently, contrastive learning has emerged as a dominant trend to enhance discriminative power; for instance, SCGC\(Kulatillekeet al\.,[2025](https://arxiv.org/html/2607.05469#bib.bib37)\)simplifies contrastive architectures through neighbor\-oriented loss, while CCGC\(Yanget al\.,[2023a](https://arxiv.org/html/2607.05469#bib.bib48)\)and DCGL\(Chenet al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib49)\)leverage clustering\-oriented guidance to refine representation learning\. Parallel to these algorithmic advancements, structural entropy introduces a robust information\-theoretic perspective for capturing graph hierarchies, with methods like USER\(Wanget al\.,[2023](https://arxiv.org/html/2607.05469#bib.bib19)\)and the Lorentz\-based LSEnet\(Sunet al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib6)\)pushing the boundaries of accuracy and parameter\-free clustering\. Furthermore, applying structural entropy to unsupervised graph clustering\(Zhanget al\.,[2025a](https://arxiv.org/html/2607.05469#bib.bib8)\)opens new avenues for synergizing structural information theory with neural networks\.

### 2\.2\.Structural Information Theory

Structural Information Theory has been validated in many applications\. Introducing structural entropy in neural networks captures the underlying topological connectivity and reduces random interference\(Wanget al\.,[2023](https://arxiv.org/html/2607.05469#bib.bib19); Zhanget al\.,[2025a](https://arxiv.org/html/2607.05469#bib.bib8)\)\. The hierarchical nature of the structure entropy encoding tree provides new methods for hierarchical structure pooling in graph neural network\(Wuet al\.,[2022](https://arxiv.org/html/2607.05469#bib.bib20)\), unsupervised image segmentation\(Xieet al\.,[2025](https://arxiv.org/html/2607.05469#bib.bib60); Huanget al\.,[2026](https://arxiv.org/html/2607.05469#bib.bib57)\), dimension estimation\(Yanget al\.,[2023c](https://arxiv.org/html/2607.05469#bib.bib22)\), state abstraction\(Zenget al\.,[2023](https://arxiv.org/html/2607.05469#bib.bib23),[2026b](https://arxiv.org/html/2607.05469#bib.bib59)\)in reinforcement learning, social bot detection\(Penget al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib26); Zenget al\.,[2025](https://arxiv.org/html/2607.05469#bib.bib58)\), unsupervised social event detection\(Caoet al\.,[2024b](https://arxiv.org/html/2607.05469#bib.bib24)\), and recommendation systems\(Zhanget al\.,[2025b](https://arxiv.org/html/2607.05469#bib.bib29)\)\. Additionally, reconstructing the graph structure on the hierarchical encoding tree suppresses edge noise and enhances the learning ability of the graph structure\(Zouet al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib61)\)\. Furthermore, modifying the network structure based on minimizing structural entropy achieves maximum deception of community structure\(Liuet al\.,[2019](https://arxiv.org/html/2607.05469#bib.bib28)\)\. Similarly, SEGA\(Wuet al\.,[2023a](https://arxiv.org/html/2607.05469#bib.bib17)\)and SEPC\(Huanget al\.,[2025](https://arxiv.org/html/2607.05469#bib.bib62)\)improve the performance of graph contrastive learning, guided by the principle of structural entropy minimization\. Based on the homogeneous graph structure entropy, studys of multi\-relational graph SE\(Caoet al\.,[2024a](https://arxiv.org/html/2607.05469#bib.bib16)\)and hypergraph further SE\(Zhanget al\.,[2025b](https://arxiv.org/html/2607.05469#bib.bib29); Zenget al\.,[2026a](https://arxiv.org/html/2607.05469#bib.bib63)\)extend the structural information theory, making it suitable for more complex scenarios\.

### 2\.3\.Large Graph Learning

Large\-scale graph learning has evolved to address the scalability bottlenecks of traditional Graph Neural Networks \(GNNs\)\. As foundational works, GraphSAGE\(Hamiltonet al\.,[2017](https://arxiv.org/html/2607.05469#bib.bib13)\)introduces neighbor sampling for inductive representation learning, while VR\-GCN\(Chenet al\.,[2018](https://arxiv.org/html/2607.05469#bib.bib50)\)adopts variance reduction to stabilize stochastic training\. To overcome the memory explosion in deep GNNs, Cluster\-GCN\(Chianget al\.,[2019](https://arxiv.org/html/2607.05469#bib.bib51)\)leverages graph clustering to restrict neighborhood search within dense subgraphs\. Further refinements in sampling strategies, such as GraphSAINT\(Zenget al\.,[2019](https://arxiv.org/html/2607.05469#bib.bib52)\), utilize subgraph sampling to decouple the number of layers from sampling complexity\. Parallel to these developments, model simplification has become a key trend; SGC\(Wuet al\.,[2019](https://arxiv.org/html/2607.05469#bib.bib53)\)removes non\-linearities to fold GCN into a linear filter\. Recently, the research frontier has shifted toward scaling Graph Transformers to large graphs\. GraphGPS\(Rampášeket al\.,[2022](https://arxiv.org/html/2607.05469#bib.bib54)\)decouples local and global mechanisms, while SGFormer\(Wuet al\.,[2023b](https://arxiv.org/html/2607.05469#bib.bib55)\)and Exphormer\(Shirzadet al\.,[2023](https://arxiv.org/html/2607.05469#bib.bib56)\)employ simplified global attention or sparse frameworks to mitigate quadratic complexity\.

## 3\.Preliminary

###### Definition 3\.1 \(Unsupervised Graph Clustering\)\.

The primary objective of unsupervised graph clustering is to partition nodes into cohesive groups by exclusively exploiting intrinsic topological structures and nodal attributes, in the absence of any ground\-truth labels\. Formally, letG=\(V,E,𝐗\)G=\(V,E,\\mathbf\{X\}\)denote an undirected homogeneous graph, whereV=\{v1,v2,…,vN\}V=\\\{v\_\{1\},v\_\{2\},\\dots,v\_\{N\}\\\}is the set ofNNnodes andE⊆V×VE\\subseteq V\\times Vrepresents the set ofMMedges\. The nodal properties are encapsulated in a feature matrix𝐗∈ℝN×f\\mathbf\{X\}\\in\\mathbb\{R\}^\{N\\times f\}, whereffdenotes the dimensionality of the attribute space\. The connectivity patterns withinGGare characterized by a symmetric adjacency matrix𝐀∈\{0,1\}N×N\\mathbf\{A\}\\in\\\{0,1\\\}^\{N\\times N\}, where𝐀i​j=1\\mathbf\{A\}\_\{ij\}=1indicates the existence of an edge between nodesviv\_\{i\}andvjv\_\{j\}\. Given the graphGG, the objective is to learn a mapping functionf:\{V,𝐀,𝐗\}→𝐘f:\\\{V,\\mathbf\{A\},\\mathbf\{X\}\\\}\\to\\mathbf\{Y\}that assigns each node to one ofKKdisjoint clusters𝐘∈\{1,…,K\}N\\mathbf\{Y\}\\in\\\{1,\\dots,K\\\}^\{N\}, whereKKis a pre\-defined or inferred number of clusters\.

###### Definition 3\.2 \(Structural Entropy\)\.

Structural information theory\(Li and Pan,[2016](https://arxiv.org/html/2607.05469#bib.bib15)\)is originally proposed for measuring the structural information contained within a graph\. Specifically, this theory aims to calculate the structural entropy of the homogeneous graphG=\(V,E\)G=\(V,E\), which reflects its uncertainty when undergoing hierarchical division\. The structural information of the homogeneous graphGGdetermined by the encoding tree𝒯\\mathcal\{T\}is defined as:

\(1\)H𝒯​\(G\)=−∑α∈𝒯,α≠λgαv​o​l​\(G\)​log⁡v​o​l​\(α\)v​o​l​\(α−\),\\displaystyle H^\{\\mathcal\{T\}\}\(G\)=\-\\sum\_\{\\alpha\\in\\mathcal\{T\},\\alpha\\neq\\lambda\}\\frac\{g\_\{\\alpha\}\}\{vol\(G\)\}\\log\\frac\{vol\(\\alpha\)\}\{vol\(\\alpha^\{\-\}\)\},wherev​o​l​\(G\)vol\(G\)is the sum of the degrees of all nodes in the graphGG\. Each vertex in the encoding tree𝒯\\mathcal\{T\}corresponds to a node subsetTαT\_\{\\alpha\}in the graphGG\.v​o​l​\(α\)vol\(\\alpha\)is the volume ofTαT\_\{\\alpha\}and is the sum of the degrees of all nodes in the subsetTαT\_\{\\alpha\}\.α−\\alpha^\{\-\}is the parent vertex of vertexα\\alphain the encoding tree\.gαg\_\{\\alpha\}is the sum of weights of all edges from node subsetTαT\_\{\\alpha\}to node subsetV/TαV/T\_\{\\alpha\}, which can be understood as the total weight of the edges from the nodes outside the node subsetTαT\_\{\\alpha\}to the nodes insideTαT\_\{\\alpha\}, or the total weight of the cut edges\.gαv​o​l​\(G\)\\frac\{g\_\{\\alpha\}\}\{vol\(G\)\}represents the probability that the random walk entersTαT\_\{\\alpha\}\. The structural entropyH​\(G\)H\(G\)of graphGGis the minimumH𝒯​\(G\)H^\{\\mathcal\{T\}\}\(G\)\. Let𝒯h\\mathcal\{T\}\_\{h\}be encoding trees whose height is not greater thanhh, then thehh\-dimensional structural entropy ofGGis defined asHh​\(G\)=m​i​n​\{H𝒯h​\(G\)\}H\_\{h\}\(G\)=min\\\{H^\{\\mathcal\{T\}\_\{h\}\}\(G\)\\\}\.

## 4\.Methodology

This section presents a detailed formalization of the proposed scalable unsupervised graph clustering framework,SCISE\. As illustrated in Figure[2](https://arxiv.org/html/2607.05469#S1.F2),SCISEcomprises three strategic components: Structural Entropy Community Constraint \(SECC\), which optimizes structural entropy minimization under community\-cardinality constraints to generate cohesive partitions; Community\-aware Sampling Extension \(CSampE\), which mitigates the ”structural isolation” of mini\-batches by performing community\-aware context expansion; and Structural Contrastive Learning \(StructCL\), which executes contrastive alignment on a higher\-order topology reconstructed via structural similarity\. Specifically, the pipeline begins with SECC \(Section[4\.1](https://arxiv.org/html/2607.05469#S4.SS1)\) as a preprocessing stage, leveraging a constrained structural entropy operator to partition the raw graph into dense community anchors\. During the representation learning stage, CSampE \(Section[4\.2](https://arxiv.org/html/2607.05469#S4.SS2)\) augments sampled nodes with their corresponding intra\-community neighbors to restore topological integrity\. Subsequently, StructCL \(Section[4\.3](https://arxiv.org/html/2607.05469#S4.SS3)\) refines the batch\-wise subgraph by re\-weighting edges based on structural similarities approximated through random walks\. Finally, the Overall Optimization \(Section[4\.4](https://arxiv.org/html/2607.05469#S4.SS4)\) integrates these modules into a unified objective to refine latent embeddings, followed by K\-means clustering to produce the final partitions\. A detailed complexity analysis ofSCISEis provided in Section[4\.5](https://arxiv.org/html/2607.05469#S4.SS5)\.

### 4\.1\.Structural Entropy Community Constraint \(SECC\)

Applying structural information theory to graph structure learning has demonstrated substantial advantages across various downstream tasks, primarily due to its capacity to reveal the hierarchical topological semantics of nodes\. However, current optimization paradigms for structural entropy predominantly rely on a greedy merge operator—iteratively merging node pairs until no further reduction in structural entropy is possible\. This unconstrained, locally greedy approach is highly susceptible to over\-segmentation and frequently traps the model in local optima\. As illustrated in the case study in Section[5\.7](https://arxiv.org/html/2607.05469#S5.SS7), conventional methods often yield a plethora of fragmented, micro\-communities \(e\.g\., sizes of 2, 3, or 4\)\. In ideal real\-world scenarios, however, community partitions are expected to be cohesive, characterized by an abundance of medium\-sized communities and a minimal presence of extreme\-sized \(excessively large or small\) communities\.

Input:Graph

G=\(V,E\)G=\(V,E\), target community count

NcommN\_\{\\text\{comm\}\}, merge speed

p∈\(0,1\]p\\in\(0,1\]\.

1

Output:Community partition

𝒞=\{c1,c2,…,cNcomm\}\\mathcal\{C\}=\\\{c\_\{1\},c\_\{2\},\\dots,c\_\{N\_\{\\text\{comm\}\}\}\\\}\.

2

3Initialize

𝒞=\{\{v1\},\{v2\},…,\{vN\}\}\\mathcal\{C\}=\\\{\\\{v\_\{1\}\\\},\\\{v\_\{2\}\\\},\\dots,\\\{v\_\{N\}\\\}\\\};

4

5Calculate

vol​\(G\)=∑v∈Vdv\\text\{vol\}\(G\)=\\sum\_\{v\\in V\}d\_\{v\};

6

7while*\|𝒞\|\>N*comm*\|\\mathcal\{C\}\|\>N\_\{\\text\{comm\}\}*do

8

ℰc​a​n​d=\{\(ci,cj\)∣ci,cj∈𝒞,i<j,∃eu,w∈E​s\.t\.​vu∈ci,vw∈cj\}\\mathcal\{E\}\_\{cand\}=\\\{\(c\_\{i\},c\_\{j\}\)\\mid c\_\{i\},c\_\{j\}\\in\\mathcal\{C\},i<j,\\exists e\_\{u,w\}\\in E\\text\{ s\.t\. \}v\_\{u\}\\in c\_\{i\},v\_\{w\}\\in c\_\{j\}\\\};

9

10foreach*\(ci,cj\)∈ℰc​a​n​d\(c\_\{i\},c\_\{j\}\)\\in\\mathcal\{E\}\_\{cand\}*do

11Calculate

Δ​H​\(ci,cj\)\\Delta H\(c\_\{i\},c\_\{j\}\)via Eq\. \([2](https://arxiv.org/html/2607.05469#S4.E2)\);

12

13end foreach

14

15Sort

ℰc​a​n​d\\mathcal\{E\}\_\{cand\}in descending order of

Δ​H\\Delta H;

16

17

Pp​o​s=\{\(ci,cj\)∈ℰc​a​n​d∣Δ​H​\(ci,cj\)<0\}P\_\{pos\}=\\\{\(c\_\{i\},c\_\{j\}\)\\in\\mathcal\{E\}\_\{cand\}\\mid\\Delta H\(c\_\{i\},c\_\{j\}\)<0\\\};

18

//Forced Convergence

19if*Pp​o​sP\_\{pos\}is empty*then

20

Pp​o​s=ℰc​a​n​dP\_\{pos\}=\\mathcal\{E\}\_\{cand\};

21

22end if

23

O​P=\|Pp​o​s\|OP=\|P\_\{pos\}\|;

24

25

k=min⁡\(p⋅O​P,\|𝒞\|−Ncomm\)k=\\min\\left\(p\\cdot OP,\|\\mathcal\{C\}\|\-N\_\{\\text\{comm\}\}\\right\);

26

27Select top

kkpairs from

Pp​o​sP\_\{pos\}and merge them;

28Update

𝒞\\mathcal\{C\}and

\|𝒞\|=\|𝒞\|−k\|\\mathcal\{C\}\|=\|\\mathcal\{C\}\|\-k;

29

30end while

31return

𝒞\\mathcal\{C\}

Algorithm 1Structural Entropy Community ConstraintTo address this bottleneck, we impose a community cardinality constraint, denoted asNcommN\_\{\\text\{comm\}\}, on the greedy structural entropy minimization process\. Consequently, the termination criterion for the merge operator shifts from ”the absence of entropy\-decreasing node pairs” to ”convergence to the target community countNcommN\_\{\\text\{comm\}\}”\. Specifically, the process initializes with allNNnodes forming individual singleton communities, denoted as𝒞=\{c1,c2,…,cN\}\\mathcal\{C\}=\\\{c\_\{1\},c\_\{2\},\\dots,c\_\{N\}\\\}, where inter\-community connections correspond to the original edge setEE\. For each edgeei,j∈Ee\_\{i,j\}\\in E, we calculate the change in structure entropy,Δ​SE​\(i,j\)\\Delta\\text\{SE\}\(i,j\), resulting from the merger ofcic\_\{i\}andcjc\_\{j\}:

\(2\)Δ​H​\(ci,cj\)=\\displaystyle\\Delta H\(c\_\{i\},c\_\{j\}\)=−gci∪cjv​o​l​\(G\)​log⁡v​o​l​\(ci∪cj\)v​o​l​\(G\)\+∑vt∈ci∪cj\(−dvtv​o​l​\(G\)​log⁡dvtvol​\(ci∪cj\)\)\\displaystyle\-\\frac\{g\_\{c\_\{i\}\\cup c\_\{j\}\}\}\{vol\(G\)\}\\log\\frac\{vol\(c\_\{i\}\\cup c\_\{j\}\)\}\{vol\(G\)\}\+\\sum\_\{v\_\{t\}\\in c\_\{i\}\\cup c\_\{j\}\}\\left\(\-\\frac\{d\_\{v\_\{t\}\}\}\{vol\(G\)\}\\log\\frac\{d\_\{v\_\{t\}\}\}\{\\text\{vol\}\(c\_\{i\}\\cup c\_\{j\}\)\}\\right\)−\(−gcivol​\(G\)​log⁡vol​\(ci\)vol​\(G\)\+∑vt∈ci\(−dvtvol​\(G\)​log⁡dvtvol​\(ci\)\)\)\\displaystyle\-\\left\(\-\\frac\{g\_\{c\_\{i\}\}\}\{\\text\{vol\}\(G\)\}\\log\\frac\{\\text\{vol\}\(c\_\{i\}\)\}\{\\text\{vol\}\(G\)\}\+\\sum\_\{v\_\{t\}\\in c\_\{i\}\}\\left\(\-\\frac\{d\_\{v\_\{t\}\}\}\{\\text\{vol\}\(G\)\}\\log\\frac\{d\_\{v\_\{t\}\}\}\{\\text\{vol\}\(c\_\{i\}\)\}\\right\)\\right\)−\(−gcjvol​\(G\)​log⁡vol​\(cj\)vol​\(G\)\+∑vt∈cj\(−dvtvol​\(G\)​log⁡dvtvol​\(cj\)\)\),\\displaystyle\-\\left\(\-\\frac\{g\_\{c\_\{j\}\}\}\{\\text\{vol\}\(G\)\}\\log\\frac\{\\text\{vol\}\(c\_\{j\}\)\}\{\\text\{vol\}\(G\)\}\+\\sum\_\{v\_\{t\}\\in c\_\{j\}\}\\left\(\-\\frac\{d\_\{v\_\{t\}\}\}\{\\text\{vol\}\(G\)\}\\log\\frac\{d\_\{v\_\{t\}\}\}\{\\text\{vol\}\(c\_\{j\}\)\}\\right\)\\right\),wherev​o​l​\(⋅\)vol\(\\cdot\)denotes the volume of the community,g​\(⋅\)g\(\\cdot\)represents the cut edges, anddvtd\_\{v\_\{t\}\}signifies the node degree\. Subsequently, we sort the entropy variations of all candidate edges in increasing order, retainingO​POPpairs whereΔ​H​\(ci,cj\)<0\\Delta H\(c\_\{i\},c\_\{j\}\)<0\. To control the pace and efficiency of the agglomeration, we introduce a hyperparameterpp\(0<p≤10<p\\leq 1\), executing the merge operation only on the topppproportion of these candidate pairs\. Following one iteration, a new community set𝒞′=\{c1,c2,…,cN′\}\\mathcal\{C\}^\{\\prime\}=\\\{c\_\{1\},c\_\{2\},\\dots,c\_\{N^\{\\prime\}\}\\\}is formed, whereN′=N−p×O​PN^\{\\prime\}=N\-p\\times OP\. The core innovation of the constraint lies in its ability to circumvent premature convergence\. So, before termination, if no node pairs satisfyΔ​H​\(ci,cj\)<0\\Delta H\(c\_\{i\},c\_\{j\}\)<0, yet the current number of communities has not reachedNcommN\_\{\\text\{comm\}\}, the algorithm relaxes the strict entropy\-descent condition\. It forces further merges—regardless of temporary structural entropy increases—until the total number of communities is strictly limited toNcommN\_\{\\text\{comm\}\}\(detailed in Algorithm[1](https://arxiv.org/html/2607.05469#algorithm1)\)\. This mechanism effectively breaks out of local optima and yields highly compact partitions by compelling nodes into exactlyNcommN\_\{\\text\{comm\}\}cohesive groups, while ensuring global structural integrity\. The unconstrained minimization algorithm can be used to estimate a feasible upper bound for the community range\. As demonstrated in Section[5\.4](https://arxiv.org/html/2607.05469#S5.SS4),SCISEis highly insensitive to the precise value ofNc​o​m​mN\_\{comm\}, and therefore no exhaustive search for an optimal community number is required in practice\.

### 4\.2\.Community\-aware Sampling Extension \(CSampE\)

To maintain computational efficiency on large\-scale graphs, models typically rely on stochastic node sampling to construct mini\-batches\. However, this inherent randomness frequently severs deep\-seated community ties\. Nodes belonging to the same cohesive cluster may be partitioned into disparate batches, preventing the model from capturing the full topological evolution of a community within a single gradient update—a phenomenon we define as Structural Isolation\. Conventional node\-centric paradigms \(e\.g\., neighbor sampling\) often neglect long\-range community constraints, leading to fragmented subgraphs where intra\-batch nodes are topologically isolated\. This fragmentation hinders the model from learning the cohesive hierarchical semantics intrinsic to the data\.

CSampE bridges this gap by adaptively expanding the initial batch𝒱b​a​t​c​h\\mathcal\{V\}\_\{batch\}into structurally dense collectives based on underlying community memberships\. By shifting the sampling paradigm from ”node expansion” to ”community alignment,” CSampE identifies the corresponding communityc​\(v\)∈𝒞c\(v\)\\in\\mathcal\{C\}for each seed nodev∈𝒱b​a​t​c​hv\\in\\mathcal\{V\}\_\{batch\}via the partitions generated by SECC\. This mechanism pulls nodes from the same community and their critical topological structures into a unified sampling space, forcing the model to observe complete community semantics in each training step\. Specifically, for each nodev∈𝒱b​a​t​c​hv\\in\\mathcal\{V\}\_\{batch\}associated with communityc​\(v\)c\(v\), we introduce a cardinality thresholdθ\\thetato govern the expansion strategy:

Case I: Structural Restoration for Small Communities \(\|c​\(v\)\|≤θ\|c\(v\)\|\\leq\\theta\)\. For small\-scale communities, we execute a full\-community expansion to ensure the local topology is entirely restored within a single training step\. The expanded set𝒱e​x​t\\mathcal\{V\}\_\{ext\}is defined as:

\(3\)𝒱e​x​t=\{u∣∃v∈𝒱b​a​t​c​h,u∈c​\(v\)\},\\mathcal\{V\}\_\{ext\}=\\\{u\\mid\\exists v\\in\\mathcal\{V\}\_\{batch\},u\\in c\(v\)\\\},
Case II: Backbone Extraction for Large Communities \(\|c​\(v\)\|\>θ\|c\(v\)\|\>\\theta\)\. In expansive communities, full inclusion would trigger ”batch explosion” and excessive memory overhead\. To distill the most representative features, we executewlw\_\{l\}random walks of lengthwtw\_\{t\}starting from nodevvwithinc​\(v\)c\(v\)\. Letf​\(u;v\)f\(u;v\)denote the frequency of nodeuubeing visited by nodevvwithinc​\(v\)c\(v\)\. We identify the structural backbone by filtering nodes that exceed the mean visitation frequency:

\(4\)𝒱e​x​t=\{u∣∃v∈𝒱b​a​t​c​h​s\.t\.​u∈c​\(v\)​and​f​\(u;v\)\>f¯v\},\\mathcal\{V\}\_\{ext\}=\\\{u\\mid\\exists v\\in\\mathcal\{V\}\_\{batch\}\\text\{ s\.t\. \}u\\in c\(v\)\\text\{ and \}f\(u;v\)\>\\bar\{f\}\_\{v\}\\\},wheref¯v=1\|ℛv\|​∑w∈ℛvf​\(w;v\)\\bar\{f\}\_\{v\}=\\frac\{1\}\{\|\\mathcal\{R\}\_\{v\}\|\}\\sum\_\{w\\in\\mathcal\{R\}\_\{v\}\}f\(w;v\)denotes the mean visitation frequency associated with seedvv, andℛv\\mathcal\{R\}\_\{v\}represents the set of all nodes reachable from seedvvwithin the community via random walks\. The final expanded batch,𝒱b​a​t​c​h∗=𝒱b​a​t​c​h∪𝒱e​x​t\\mathcal\{V\}^\{\*\}\_\{batch\}=\\mathcal\{V\}\_\{batch\}\\cup\\mathcal\{V\}\_\{ext\}, transforms a collection of isolated points into a coherent structural field\. This dual\-track strategy enables the model to leverage dense community\-aware signals while maintaining an effectively managed batch size, thereby enhancing the stability of gradient updates and the robustness of learned hierarchical representations\.

### 4\.3\.Structural Contrastive Learning \(StructCL\)

While the CSampE module successfully assembles structurally dense mini\-batches, efficiently translating these multi\-hop topological patterns into the representation space remains a significant challenge\. A naive approach would be to treat all node pairs within the same community as positive anchors\. However, for large\-scale graphs, even with the reduced scale of a mini\-batch, this would lead to a quadratic explosion \(𝒪​\(\|𝒱b​a​t​c​h∗\|2\)\\mathcal\{O\}\(\|\\mathcal\{V\}^\{\*\}\_\{batch\}\|^\{2\}\)\) in the number of positive pairs, incurring prohibitive computational overhead\. To quantify community\-level structural relations without inflating complexity, we propose Structural Contrastive Learning \(StructCL\)\.

To efficiently capture community\-level structural relations, we construct a structural affinity matrix𝐀∗\\mathbf\{A\}^\{\*\}based on the visitation counts of localized random walks\. For each nodevi∈𝒱b​a​t​c​h∗v\_\{i\}\\in\\mathcal\{V\}^\{\*\}\_\{batch\}, we executewtw\_\{t\}random walks of lengthwlw\_\{l\}within the graph\. LetC​o​u​n​t​\(vj;vi\)Count\(v\_\{j\};v\_\{i\}\)denote the total frequency of nodevjv\_\{j\}being visited in walks originating fromviv\_\{i\}\. The structural affinity matrix𝐀∗∈ℝB×B\\mathbf\{A\}^\{\*\}\\in\\mathbb\{R\}^\{B\\times B\}\(whereB=\|𝒱b​a​t​c​h∗\|B=\|\\mathcal\{V\}^\{\*\}\_\{batch\}\|\) is defined as:

\(5\)𝐀i​j∗=\{C​o​u​n​t​\(vj;vi\),if​i≠j​and​vj∈RW​\(vi\)0,otherwise,\\mathbf\{A\}^\{\*\}\_\{ij\}=\\begin\{cases\}Count\(v\_\{j\};v\_\{i\}\),&\\text\{if \}i\\neq j\\text\{ and \}v\_\{j\}\\in\\text\{RW\}\(v\_\{i\}\)\\\\ 0,&\\text\{otherwise\}\\end\{cases\},This sparse matrix effectively transforms the batch into a weighted structural subgraph\. Within this subgraph, the weights𝐀i​j∗\\mathbf\{A\}^\{\*\}\_\{ij\}serve as confidence scores for topological co\-occurrence: a higher frequency indicates a more stable structural bond\. By selectively focusing on these frequently visited ”structural anchors,” StructCL effectively captures the core community semantics while avoiding the computational redundancy of all\-to\-all community matching\.

To align the neural similarity of embeddings with the distilled structural affinities, for any node pair\(vi,vj\)\(v\_\{i\},v\_\{j\}\)with𝐀i​j∗\>0\\mathbf\{A\}^\{\*\}\_\{ij\}\>0, we define the consistency loss as a multi\-positive InfoNCE objective:

\(6\)ℒs​t​r​u​c​t=−1B​∑vi∈𝒱b​a​t​c​h∗1\|𝒫i\|​∑vj∈𝒫ilog⁡exp⁡\(sim​\(𝐳i,𝐳j\)/τ\)∑vk≠viexp⁡\(sim​\(𝐳i,𝐳k\)/τ\),\\mathcal\{L\}\_\{struct\}=\-\\frac\{1\}\{B\}\\sum\_\{v\_\{i\}\\in\\mathcal\{V\}^\{\*\}\_\{batch\}\}\\frac\{1\}\{\|\\mathcal\{P\}\_\{i\}\|\}\\sum\_\{v\_\{j\}\\in\\mathcal\{P\}\_\{i\}\}\\log\\frac\{\\exp\(\\text\{sim\}\(\\mathbf\{z\}\_\{i\},\\mathbf\{z\}\_\{j\}\)/\\tau\)\}\{\\sum\_\{v\_\{k\}\\neq v\_\{i\}\}\\exp\(\\text\{sim\}\(\\mathbf\{z\}\_\{i\},\\mathbf\{z\}\_\{k\}\)/\\tau\)\},where𝒫i=\{vj∣𝐀i​j∗\>0\}\\mathcal\{P\}\_\{i\}=\\\{v\_\{j\}\\mid\\mathbf\{A\}^\{\*\}\_\{ij\}\>0\\\}is the sparse set of structural neighbors for nodeviv\_\{i\}\. By minimizingℒs​t​r​u​c​t\\mathcal\{L\}\_\{struct\}, the model adaptively encodes dense intra\-community signals into the representation space\. This self\-supervised mechanism ensures that the learned embeddings are inherently endowed with community\-topology awareness, effectively bridging the ”structural isolation” gap while maintaining a bounded computational complexity suitable for large\-scale graph analysis\.

Input:Graph with feature

G=\(V,E\)G=\(V,E\), features

𝒳\\mathcal\{X\}, adjacency matrix

AA, target community count

NcommN\_\{\\text\{comm\}\}, merge speed

p∈\(0,1\]p\\in\(0,1\], expansion threshold

θ\\theta, random walk params

\(wl,wt\)\(w\_\{l\},w\_\{t\}\), batch size

BB, target clusters

KK\.

Output:Cluster assignments

𝒴\\mathcal\{Y\}\.

1

//Stage 1: Preprocessing community division

2

𝒞←SECC​\(G,Ncomm,p\)\\mathcal\{C\}\\leftarrow\\text\{SECC\}\(G,N\_\{\\text\{comm\}\},p\)via Algorithm[1](https://arxiv.org/html/2607.05469#algorithm1);

3

4Construct community lookup mapping

c​\(v\)c\(v\)for each

v∈Vv\\in Vfrom

𝒞\\mathcal\{C\};

5

//Stage 2: Structure\-Aware Representation Learning

6

7for*epoch = 1, 2, 3,…*do

8

9foreach*mini\-batch𝒱b​a​t​c​h⊂V\\mathcal\{V\}\_\{batch\}\\subset V*do

10

11Initialize

𝒱e​x​t←∅\\mathcal\{V\}\_\{ext\}\\leftarrow\\emptyset;

12

13foreach*v∈𝒱b​a​t​c​hv\\in\\mathcal\{V\}\_\{batch\}*do

14if*\|c​\(v\)\|≤θ\|c\(v\)\|\\leq\\theta*then

//Case I: Full Expansion

15

𝒱e​x​t←𝒱e​x​t∪\{u∣u∈c​\(v\)\}\\mathcal\{V\}\_\{ext\}\\leftarrow\\mathcal\{V\}\_\{ext\}\\cup\\\{u\\mid u\\in c\(v\)\\\}via Eq\.[3](https://arxiv.org/html/2607.05469#S4.E3);

16

17end if

18else

//Case II: Backbone Extraction

19Perform

wtw\_\{t\}random walks of length

wlw\_\{l\}within

c​\(v\)c\(v\);

20

21Update

𝒱e​x​t\\mathcal\{V\}\_\{ext\}via Eq\.[4](https://arxiv.org/html/2607.05469#S4.E4);

22

23end if

24

25end foreach

26

27

𝒱b​a​t​c​h∗=𝒱b​a​t​c​h∪𝒱e​x​t\\mathcal\{V\}^\{\*\}\_\{batch\}=\\mathcal\{V\}\_\{batch\}\\cup\\mathcal\{V\}\_\{ext\};

28

//StructCL Optimization

29Compute structural affinity

𝐀∗\\mathbf\{A\}^\{\*\}via Eq\.[5](https://arxiv.org/html/2607.05469#S4.E5);

30

31

𝐙b​a​t​c​h=GCN​\(𝒳​\[𝒱b​a​t​c​h∗\],A\)\\mathbf\{Z\}\_\{batch\}=\\text\{GCN\}\(\\mathcal\{X\}\[\\mathcal\{V\}^\{\*\}\_\{batch\}\],A\);

32

33calculate

ℒs​t​r​u​c​t\\mathcal\{L\}\_\{struct\}via Eq\.[6](https://arxiv.org/html/2607.05469#S4.E6);

34

35

ℒs​t​r​u​c​t\\mathcal\{L\}\_\{struct\}backward;

36

37end foreach

38

39end for

40

41

𝐙g​l​o​b​a​l=∅\\mathbf\{Z\}\_\{global\}=\\emptyset;

42

43foreach*mini\-batch𝒱b​a​t​c​h⊂V\\mathcal\{V\}\_\{batch\}\\subset V*do

44

45

𝐙b​a​t​c​h=GCN​\(𝒳​\[𝒱b​a​t​c​h\],A\)\\mathbf\{Z\}\_\{batch\}=\\text\{GCN\}\(\\mathcal\{X\}\[\\mathcal\{V\}\_\{batch\}\],A\);

46

47

𝐙g​l​o​b​a​l=𝐙g​l​o​b​a​l∪𝐙b​a​t​c​h\\mathbf\{Z\}\_\{global\}=\\mathbf\{Z\}\_\{global\}\\cup\\mathbf\{Z\}\_\{batch\};

48

49end foreach

50

51

𝒴=K\-means​\(𝐙g​l​o​b​a​l,K\)\\mathcal\{Y\}=\\text\{K\-means\}\(\\mathbf\{Z\}\_\{global\},K\);

52

return

𝒴\\mathcal\{Y\}

Algorithm 2Overall execution procedure ofSCISE\.
### 4\.4\.Overall Optimization

The overall execution procedure ofSCISEis summarized in Algorithm[2](https://arxiv.org/html/2607.05469#algorithm2)\. Our framework adopts a two\-stage paradigm consisting of community division preprocessing and structure\-aware representation learning\. Specifically, the SECC module is first invoked to obtain a stable community structure mapping𝒞\\mathcal\{C\}, which circumvents the high computational overhead of recalculating communities at each training step\. During the training phase, for each mini\-batch𝒱b​a​t​c​h\\mathcal\{V\}\_\{batch\}, the CSampE module adaptively expands the batch with community nodes𝒱e​x​t​e​n​d\\mathcal\{V\}\_\{extend\}based on the pre\-acquired community scales\. This enables the subsequent StructCL objective to distill community\-level semantic signals into the GCN encoder without incurring the ”neighbor explosion” problem\. Subsequently, the node features are processed through aG​C​NGCNbackbone to learn the node embeddings𝐙b​a​t​c​h\\mathbf\{Z\}\_\{batch\}\. Finally, a single\-pass K\-means clustering is performed on the consolidated global embeddings𝐙g​l​o​b​a​l\\mathbf\{Z\}\_\{global\}to obtain the final partitions𝒴p​r​e​d\\mathcal\{Y\}\_\{pred\}\.

### 4\.5\.Complexity Analysis

To demonstrate the scalability ofSCISE, we analyze its computational complexity across two primary stages: offline structural prior acquisition and structure\-aware representation learning\. First, the complexity of the SECC module is governed by the construction of the structural entropy encoding tree\. Given a graphGGwithNNnodes andMMedges, when the parallel merge rate ispp, the maximum number of rounds required for hierarchical merging islog1−p⁡1−pN−1\\log\_\{1\-p\}\\frac\{1\-p\}\{N\-1\}\. Consequently, the time complexity for constructing the structural prior isO​\(M⋅log1−p⁡1−pN−1\)O\(M\\cdot\\log\_\{1\-p\}\\frac\{1\-p\}\{N\-1\}\), which can be simplified toO​\(M​log⁡N\)O\(M\\log N\)\. Since SECC is performed as a one\-time preprocessing step, it does not add to the iterative overhead of the training phase\.

In the online training phase, the complexity for each mini\-batch𝒱b​a​t​c​h\\mathcal\{V\}\_\{batch\}consists of three components: CSampE expansion, neural encoding, and StructCL optimization\. For each batch, the adaptive expansion via either full community retrieval or localized random walks incurs a complexity ofO​\(B⋅wl⋅wt\)O\(B\\cdot w\_\{l\}\\cdot w\_\{t\}\), whereBBis the initial batch size, and\(wl,wt\)\(w\_\{l\},w\_\{t\}\)are the random walk parameters\. The forward pass through the GCN has a complexity ofO​\(\|𝒱b​a​t​c​h∗\|⋅f⋅d\)O\(\|\\mathcal\{V\}^\{\*\}\_\{batch\}\|\\cdot f\\cdot d\), whereffanddddenote the input and embedding dimensions, respectively\. Calculating the structural contrastive loss involves pairwise similarity computations within the expanded batch, resulting inO​\(\|𝒱b​a​t​c​h∗\|⋅wl⋅wt\)O\(\|\\mathcal\{V\}^\{\*\}\_\{batch\}\|\\cdot w\_\{l\}\\cdot w\_\{t\}\)\. Given that\|𝒱b​a​t​c​h∗\|\|\\mathcal\{V\}^\{\*\}\_\{batch\}\|is bounded within a small constant multiple ofBB, the total time complexity per iteration during the representation learning stage isO​\(B⋅\(wl​wt\+f​d\)\)O\(B\\cdot\(w\_\{l\}w\_\{t\}\+fd\)\)\. Extending this to a full training epoch, the overall complexity remainsO​\(N⋅\(wl​wt\+f​d\)\)O\(N\\cdot\(w\_\{l\}w\_\{t\}\+fd\)\)\.

Table 1\.Statistics of datasets\.Dataset\#Node\#Edge\#Feature\#ClusterDegreePhoto7,650119,081745831\.13Computers13,752245,8617671035\.76Pubmed19,71744,32450034\.50Ogbn\-arxiv169,3431,166,2431284013\.77Reddit232,965114,615,89260241491\.98Ogbn\-products2,449,02961,859,1401004750\.52

## 5\.Experiments

In this section, we conduct empirical experiments to demonstrate the effectiveness of the proposed frameworkSCISE\. We aim to answer five research questions as follows:Q1: Effectiveness\.How doesSCISEperform in unsupervised graph clustering tasks compared with state\-of\-the\-art baselines \(Section[5\.2](https://arxiv.org/html/2607.05469#S5.SS2)\)?Q2: Ablation Study\.How do the SECC, CSampE, and StructCL modules influence the performance ofSCISE, and how do they interact with each other \(Section[5\.3](https://arxiv.org/html/2607.05469#S5.SS3)\)?Q3: Stability Analysis\.How do key hyperparameters impact the performance ofSCISE, and what is the degree of model sensitivity to these parameters \(Section[5\.4](https://arxiv.org/html/2607.05469#S5.SS4)\)?Q4: Robustness Against Noise\.How robust isSCISEto noisy community priors \(Section[5\.5](https://arxiv.org/html/2607.05469#S5.SS5)\)?Q5: Robustness Against Sparsity\.CanSCISEeffectively alleviate structural isolation and maintain clustering performance when graph connectivity is severely degraded \(Section[5\.6](https://arxiv.org/html/2607.05469#S5.SS6)\)?Q6: Case Study\.How do the community number \(Nc​o​m​mN\_\{comm\}\) constraints and merge speed \(pp\) balance structural entropy and community cohesion \(Section[5\.7](https://arxiv.org/html/2607.05469#S5.SS7)\)?Q7: Visualization\.CanSCISElearn discriminative node representations that produce well\-separated cluster distributions in a low\-dimensional space \(Section[5\.8](https://arxiv.org/html/2607.05469#S5.SS8)\)?

Table 2\.Comparison of the NMI, ARI, ACC, and F1 across different methods on six datasets\. The best results are bolded, and the second\-best results are underlined\.MethodPhotoComputersPubmedNMIARIACCF1NMIARIACCF1NMIARIACCF1DGI33\.70±0\.8522\.10±0\.5543\.00±1\.1035\.20±0\.9042\.00±1\.0530\.60±0\.8547\.90±1\.2039\.00±1\.0032\.20±0\.8029\.20±0\.7565\.70±1\.6565\.40±1\.60S3GC59\.80±0\.4756\.10±0\.7375\.20±0\.5872\.90±0\.6956\.00±0\.6243\.80±0\.4158\.80±0\.7647\.50±0\.5533\.30±0\.7934\.50±0\.6471\.30±0\.4870\.30±0\.71SUBLIME56\.91±0\.4345\.11±0\.9864\.95±0\.6161\.24±0\.2545\.55±0\.7324\.89±0\.1540\.94±0\.8834\.64±0\.4918\.68±0\.3216\.16±0\.6758\.33±0\.5958\.69±0\.91CONVERT63\.04±0\.3455\.20±1\.1874\.24±0\.6769\.13±1\.0548\.44±1\.4234\.25±0\.5351\.30±0\.9142\.17±0\.2828\.19±0\.7926\.59±1\.3663\.29±0\.4562\.29±1\.12SCGC54\.96±3\.4945\.66±3\.5864\.90±3\.3352\.02±5\.2647\.41±1\.1846\.06±2\.9161\.16±2\.2238\.07±3\.2426\.05±2\.2125\.27±3\.5165\.12±2\.2161\.49±3\.40DMoN63\.38±0\.4652\.41±0\.7373\.83±0\.5871\.05±0\.7949\.30±0\.6431\.82±0\.4149\.13±0\.7739\.29±0\.5229\.80±0\.7124\.52±0\.5561\.99±0\.6962\.17±0\.44Dink\-Net74\.36±0\.3568\.40±0\.9881\.71±0\.6173\.92±1\.1442\.10±0\.7824\.85±1\.6445\.17±1\.1240\.38±1\.9329\.93±1\.4729\.29±0\.5667\.29±1\.8966\.96±1\.03LSEnet58\.94±0\.6347\.80±0\.8865\.46±0\.5445\.80±0\.9155\.03±0\.7942\.15±1\.0253\.27±0\.4722\.41±0\.6829\.67±0\.4227\.90±0\.3658\.98±0\.5859\.00±0\.61MAGI71\.60±0\.7661\.50±0\.3379\.00±1\.0772\.90±0\.8859\.20±1\.1946\.20±0\.5462\.00±0\.9057\.40±0\.3729\.37±0\.2529\.25±0\.4066\.23±0\.2365\.11±0\.20DeSE68\.94±0\.2862\.49±0\.1280\.54±0\.1273\.67±0\.0352\.10±0\.1545\.64±0\.1658\.78±0\.3143\.17±0\.2330\.82±0\.1729\.47±0\.1567\.47±0\.2167\.36±0\.19\\rowcolorgray\!20SCISE74\.53±0\.1464\.51±0\.2979\.71±0\.1576\.22±0\.1258\.46±0\.2451\.78±0\.8067\.32±0\.3659\.48±0\.8435\.77±0\.0236\.33±0\.0272\.38±0\.0171\.83±0\.01Improv\.\(%\)↑\\uparrow0\.23%\-\-↑\\uparrow3\.11%\-↑\\uparrow12\.07%↑\\uparrow8\.58%↑\\uparrow3\.63%↑\\uparrow7\.42%↑\\uparrow5\.31%↑\\uparrow1\.52%↑\\uparrow2\.18%MethodOgbn\-arxivRedditOgbn\-productsNMIARIACCF1NMIARIACCF1NMIARIACCF1DGI41\.20±1\.2022\.30±0\.8031\.40±0\.9523\.00±0\.7030\.60±0\.9017\.00±0\.6022\.40±0\.7518\.30±0\.5546\.70±1\.4017\.40±0\.6532\.00±1\.0019\.20±0\.60S3GC46\.30±0\.5827\.00±1\.4235\.00±0\.9123\.00±1\.1680\.70±1\.2774\.50±0\.6373\.60±1\.0856\.00±0\.7553\.60±0\.8423\.00±0\.3540\.20±0\.5625\.00±0\.92SUBLIMEOOMOOMOOMCONVERTOOMOOMOOMSCGCOOMOOMOOMDMoN35\.60±0\.2612\.70±0\.9725\.00±0\.5819\.00±1\.1462\.80±1\.0850\.20±0\.3452\.90±0\.8626\.00±0\.4142\.80±0\.7213\.90±1\.1930\.40±0\.2921\.00±0\.95Dink\-Net43\.73±0\.2335\.22±0\.4143\.68±0\.3526\.92±0\.4878\.91±0\.3971\.34±0\.2676\.03±0\.4467\.95±0\.3150\.78±0\.5021\.08±0\.3441\.09±0\.2825\.15±0\.42LSEnetOOMOOMOOMMAGI46\.90±0\.2931\.00±1\.1238\.80±0\.6826\.60±1\.3487\.50±1\.4690\.70±0\.5791\.10±0\.9185\.30±0\.2455\.10±0\.8321\.50±1\.2742\.50±0\.4227\.60±1\.05DeSEOOMOOMOOM\\rowcolorgray\!20SCISE48\.42±0\.0837\.66±0\.4744\.13±0\.5931\.52±0\.4187\.92±0\.1290\.97±0\.0891\.75±0\.2486\.48±0\.4155\.61±0\.0225\.65±0\.6743\.88±0\.3927\.82±0\.10Improv\.\(%\)↑\\uparrow3\.25%↑\\uparrow6\.92%↑\\uparrow1\.04%↑\\uparrow17\.08%↑\\uparrow0\.48%↑\\uparrow0\.30%↑\\uparrow0\.71%↑\\uparrow1\.39%↑\\uparrow0\.93%↑\\uparrow11\.50%↑\\uparrow3\.24%↑\\uparrow0\.78%![Refer to caption](https://arxiv.org/html/2607.05469v1/x3.png)Figure 3\.Runtime comparison betweenSCISEand MAGI\.### 5\.1\.Experiment Setup

Datasets\.We conduct experiments on six benchmark datasets: Photo\(Shchuret al\.,[2018](https://arxiv.org/html/2607.05469#bib.bib11)\), Computers\(Shchuret al\.,[2018](https://arxiv.org/html/2607.05469#bib.bib11)\), Pubmed\(Senet al\.,[2008](https://arxiv.org/html/2607.05469#bib.bib14)\), Ogbn\-arxiv\(Huet al\.,[2020](https://arxiv.org/html/2607.05469#bib.bib12)\), Reddit\(Hamiltonet al\.,[2017](https://arxiv.org/html/2607.05469#bib.bib13)\), and Ogbn\-products\(Huet al\.,[2020](https://arxiv.org/html/2607.05469#bib.bib12)\)\. Details of datasets are summarized in Table[1](https://arxiv.org/html/2607.05469#S4.T1)\.

Baselines\.For graph clustering, we mainly compareSCISEwith ten state\-of\-the\-art baselines, including DGI\(Veličkovićet al\.,[2018](https://arxiv.org/html/2607.05469#bib.bib36)\), S3GC\(Devvritet al\.,[2022](https://arxiv.org/html/2607.05469#bib.bib1)\), SUBLIME\(Liuet al\.,[2022a](https://arxiv.org/html/2607.05469#bib.bib2)\), CONVERT\(Yanget al\.,[2023b](https://arxiv.org/html/2607.05469#bib.bib3)\), DMoN\(Tsitsulinet al\.,[2023](https://arxiv.org/html/2607.05469#bib.bib5)\), Dink\-Net\(Liuet al\.,[2023b](https://arxiv.org/html/2607.05469#bib.bib4)\), LSEnet\(Sunet al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib6)\), MAGI\(Liuet al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib7)\), DeSE\(Zhanget al\.,[2025a](https://arxiv.org/html/2607.05469#bib.bib8)\), and SCGC\(Kulatillekeet al\.,[2025](https://arxiv.org/html/2607.05469#bib.bib37)\)\.

Evaluation Metrics\.We evaluate the accuracy and consistency of graph clustering with four metrics\. NMI \(Normalized Mutual Information\) evaluates how well the predicted clusters match the true clusters in terms of information shared\. ARI \(Adjusted Rand Index\) assesses the similarity between the predicted and true cluster assignments, adjusting for random chance\. ACC \(Accuracy\) measures the proportion of nodes correctly assigned to their true clusters\. F1 Score evaluates the balance between precision and recall in cluster assignments\.

### 5\.2\.Overall Performance

Table 3\.Ablation study on six datasets\.Red cellsindicate a significant performance degradation compared to the full model\.VariationPhotoComputersPubmedNMIARIACCF1NMIARIACCF1NMIARIACCF1\\rowcolorgray\!20SCISE74\.53±0\.1464\.51±0\.2979\.71±0\.1576\.22±0\.1258\.46±0\.2451\.78±0\.8067\.32±0\.3659\.48±0\.8435\.77±0\.0236\.33±0\.0272\.38±0\.0171\.83±0\.01w/o SECC74\.41±0\.1464\.51±0\.1079\.74±0\.0776\.16±0\.2958\.11±0\.2351\.07±0\.3867\.05±0\.2658\.97±0\.1335\.59±0\.0136\.20±0\.0272\.31±0\.0171\.72±0\.01w/o CSampE73\.62±0\.7163\.79±0\.4379\.48±0\.1475\.44±0\.93\\cellcolorred\!2049\.00±0\.04\\cellcolorred\!2045\.12±0\.0864\.67±0\.1658\.41±0\.0635\.87±0\.0236\.12±0\.0172\.19±0\.0171\.68±0\.02w/o StructCL74\.79±0\.1364\.72±0\.0979\.82±0\.0576\.31±0\.0655\.69±0\.06\\cellcolorred\!2039\.12±0\.10\\cellcolorred\!2055\.72±0\.06\\cellcolorred\!2052\.03±0\.02\\cellcolorred\!2028\.59±0\.02\\cellcolorred\!2030\.32±0\.03\\cellcolorred\!2068\.73±0\.02\\cellcolorred\!2067\.48±0\.04w/o SECC & StructCL74\.77±0\.1364\.79±0\.1479\.88±0\.0976\.37±0\.0656\.45±0\.01\\cellcolorred\!2040\.61±0\.02\\cellcolorred\!2057\.14±0\.01\\cellcolorred\!2049\.75±0\.01\\cellcolorred\!2025\.62±0\.01\\cellcolorred\!2024\.89±0\.01\\cellcolorred\!2065\.90±0\.02\\cellcolorred\!2066\.96±0\.02w/o CSampE & StructCL\\cellcolorred\!2070\.39±0\.60\\cellcolorred\!2062\.66±0\.6079\.45±0\.3777\.10±0\.42\\cellcolorred\!2050\.24±0\.59\\cellcolorred\!2035\.18±0\.76\\cellcolorred\!2054\.57±0\.22\\cellcolorred\!2055\.82±0\.82\\cellcolorred\!2031\.07±0\.0236\.76±0\.0172\.34±0\.0170\.57±0\.01VariationOgbn\-arxivRedditOgbn\-productsNMIARIACCF1NMIARIACCF1NMIARIACCF1\\rowcolorgray\!20SCISE48\.42±0\.0837\.66±0\.4744\.13±0\.5931\.52±0\.4187\.92±0\.1290\.97±0\.0891\.75±0\.2486\.48±0\.4155\.61±0\.0225\.65±0\.6743\.88±0\.3927\.82±0\.10w/o SECC48\.15±0\.0736\.95±0\.3744\.09±0\.2131\.14±0\.3787\.45±0\.0490\.72±0\.1191\.14±0\.1884\.51±0\.5255\.33±0\.0124\.27±0\.0142\.89±0\.0127\.63±0\.01w/o CSampE\\cellcolorred\!2045\.31±0\.33\\cellcolorred\!2021\.15±1\.11\\cellcolorred\!2032\.73±0\.95\\cellcolorred\!2026\.10±0\.6185\.97±0\.16\\cellcolorred\!2080\.19±1\.37\\cellcolorred\!2085\.66±1\.10\\cellcolorred\!2083\.40±0\.5753\.21±0\.67\\cellcolorred\!2021\.76±1\.17\\cellcolorred\!2039\.40±1\.0626\.13±0\.45w/o StructCL47\.55±0\.17\\cellcolorred\!2032\.97±0\.3141\.42±0\.4530\.34±0\.7388\.20±0\.0391\.27±0\.0891\.57±0\.1385\.82±0\.1954\.78±0\.24\\cellcolorred\!2022\.59±0\.26\\cellcolorred\!2040\.62±0\.1826\.71±0\.11w/o SECC & StructCL46\.91±0\.21\\cellcolorred\!2028\.08±1\.77\\cellcolorred\!2038\.35±0\.6529\.82±1\.0187\.46±0\.1190\.36±0\.2790\.69±0\.28\\cellcolorred\!2083\.42±0\.9054\.80±0\.01\\cellcolorred\!2022\.35±0\.01\\cellcolorred\!2040\.51±0\.0126\.73±0\.02w/o CSampE & StructCL\\cellcolorred\!2041\.49±0\.37\\cellcolorred\!2015\.57±0\.10\\cellcolorred\!2028\.25±0\.77\\cellcolorred\!2022\.95±0\.5885\.44±0\.04\\cellcolorred\!2080\.09±0\.54\\cellcolorred\!2085\.71±0\.84\\cellcolorred\!2082\.61±0\.50\\cellcolorred\!2048\.53±0\.22\\cellcolorred\!2015\.83±1\.65\\cellcolorred\!2033\.92±1\.74\\cellcolorred\!2023\.07±0\.26Table 4\.End\-to\-end runtime analysis ofSCISE\.DatasetSECCepochclusteringtotalPhoto0\.30 s1\.37 s3\.34 s14\.58 minComputers0\.33 s4\.92 s3\.48 s5\.10 minPubmed0\.35 s2\.73 s3\.55 s2\.87 minOgbn\-arxiv1\.24 s73\.73 s73\.26 s1\.64 hReddit2\.58 s40\.97 s96\.59 s1\.80 hOgbn\-products10\.75 s1028\.96 s245\.21 s7\.54 hTable[2](https://arxiv.org/html/2607.05469#S5.T2)presents the comprehensive performance evaluation, whereSCISEdominates across all benchmarks, achieving state\-of\-the\-art \(SOTA\) results in 21 out of 24 metrics\. On the Ogbn\-arxiv dataset, our framework significantly outperforms the strongest baselines by 3\.25% in NMI and a remarkable 17\.08% in F1\-score\. We attribute this localized and global success to three synergistic strengths:First, Countering Structural Drifting and Fragmentation: Unlike existing structural methods \(e\.g\., DMoN, DeSE\) that often suffer from uncontrolled cluster merging or excessive fragmentation,SCISEemploys the SECC operator to enforce explicit community\-cardinality constraints\. This yields partitions that are not only cohesive but also strictly aligned with the network’s inherent semantic distribution\.Second, Bridging Structural Isolation: While conventional self\-supervised methods \(e\.g\., DGI, SUBLIME\) rely on node\-local consistency, they frequently lose global community context during batching\.SCISEmitigates this via CSampE, which proactively restores community\-level connectivity, and StructCL, which recalibrates higher\-order dependencies\. This combination ensures that the encoder captures holistic topological patterns rather than isolated neighborhood signals\.Third, Robust Scalability on Massive Graphs: On large\-scale benchmarks like Reddit and Ogbn\-products, many high\-performance competitors encounter Out\-of\-Memory \(OOM\) errors due to dense graph operations\. In contrast,SCISEscales efficiently to millions of nodes by decoupling the community\-aware expansion from the backpropagation pipeline\. This allows our framework to maintain global topological awareness even under strict memory constraints—a critical advantage for real\-world deployment\. Notably, this demonstrates that our framework preserves global topological awareness under memory constraints—a capability lacking in existing scalable methods\. Collectively, these results demonstrate that the synergy between structural entropy constraints and community\-aware sampling is fundamental for high\-performance graph clustering at scale\.

Furthermore, Figure[3](https://arxiv.org/html/2607.05469#S5.F3)reports the average per\-epoch runtime ofSCISEand MAGI\. As the graph size increases from thousands to millions of nodes, the runtime ofSCISEexhibits a near\-linear growth trend, demonstrating good scalability on large\-scale graphs\. AlthoughSCISEincurs a moderate overhead on small datasets due to community\-aware batch expansion, it becomes increasingly competitive on larger graphs and achieves lower per\-epoch runtime than MAGI on Reddit and Ogbn\-products\. To provide a complete end\-to\-end efficiency analysis, Table[4](https://arxiv.org/html/2607.05469#S5.T4)further reports the preprocessing \(SECC\), training, clustering, and total runtime costs\. The results show that SECC introduces only a negligible one\-time overhead, requiring less than 3 seconds on all datasets except Ogbn\-products \(10\.75 s\), which is insignificant compared with the overall training time\. Even on Ogbn\-products with 2\.45 million nodes, the entire pipeline can be completed within 7\.54 hours\. Table[5](https://arxiv.org/html/2607.05469#S5.T5)reports the memory consumption of both SECC and the training stage\. Despite operating on large\-scale graphs, the memory footprint of SECC remains substantially lower than that of representation learning, confirming that the proposed community discovery step is not the computational bottleneck of the framework\. These results demonstrate thatSCISEachieves strong clustering performance while maintaining practical end\-to\-end efficiency and scalability for million\-scale graph clustering\.

Table 5\.Memory usage breakdown ofSCISE\(GPU A and GPU R denote allocated and reserved GPU memory, respectively\)\.DatasetSECCTrainGPU AGPU RCPUGPU AGPU RCPUPhoto41\.77 MB78\.00 MB1\.07 MB4\.30 GB14\.62 GB62\.46 MBComputers87\.88 MB136\.00 MB1\.30 MB3\.43 GB13\.00 GB30\.34MBPubmed18\.24 MB36\.00 MB1\.50 MB5\.79 GB16\.29 GB23\.28 MBOgbn\-arxiv424\.40 MB591\.99 MB17\.19 MB19\.01 GB46\.84 GB356\.35 MBReddit11\.30 GB11\.90 GB2\.46 MB11\.03 GB31\.17 GB475\.02 MBOgbn\-products18\.71 GB24\.66 GB113\.06 MB39\.43 GB46\.79 GB316\.83 MB
### 5\.3\.Ablation Study: Dissecting the Synergistic and Complementary Effects

![Refer to caption](https://arxiv.org/html/2607.05469v1/x4.png)\(a\)Photo\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x5.png)\(b\)Computers\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x6.png)\(c\)Ogbn\-arxiv\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x7.png)\(d\)Reddit\.

Figure 4\.Sensitivity analysis of merge speedppon Photo, Computers, Ogbn\-arxiv, and Reddit datasets\.![Refer to caption](https://arxiv.org/html/2607.05469v1/x8.png)\(a\)Photo\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x9.png)\(b\)Computers\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x10.png)\(c\)Ogbn\-arxiv\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x11.png)\(d\)Reddit\.

Figure 5\.Sensitivity analysis of community numberNc​o​m​mN\_\{comm\}on Photo, Computers, Ogbn\-arxiv, and Reddit datasets\.To evaluate the contribution of each component, we construct three primary variants \(”w/o SECC”, ”w/o CSampE”, and ”w/o StructCL”\) and two joint variants \(”w/o SECC & StructCL” and ”w/o CSampE & StructCL”\)\. Specifically, ”w/o SECC” replaces community\-constrained structural entropy minimization with unconstrained optimization, while ”w/o StructCL” computes contrastive loss directly on the raw adjacency matrix\. The results in Table[3](https://arxiv.org/html/2607.05469#S5.T3)show that all components contribute positively to the final performance\. \(1\) Effect of CSampE\. Removing CSampE leads to the largest degradation on large\-scale graphs\. For example, the ARI on Ogbn\-arxiv drops from 37\.66% to 21\.15%, indicating that community\-aware batch expansion is crucial for alleviating structural isolation and preserving long\-range topology during mini\-batch training\. \(2\) Effect of StructCL\. StructCL consistently improves clustering quality, particularly on medium\-scale datasets\. On Pubmed, removing StructCL decreases ARI from 36\.33% to 30\.32%, demonstrating the benefit of incorporating refined structural affinities into contrastive learning\. \(3\) Effect of SECC\. Although the impact of SECC is generally smaller than that of CSampE, it provides a stable structural prior for downstream learning\. Comparing ”w/o StructCL” and ”w/o SECC & StructCL”, the additional removal of SECC further reduces Pubmed NMI from 28\.59% to 25\.62%, suggesting that community\-constrained structural entropy helps maintain globally consistent partitions\.

Table 6\.Sensitivity analysis of learning ratel​rlrwith NMI\.l​rlr0\.050\.010\.0050\.0010\.00050\.0001Photo71\.6574\.3174\.4472\.6972\.3872\.50Computers57\.5858\.0256\.3458\.6258\.4057\.89Pubmed23\.7534\.8635\.6227\.9727\.3528\.61Ogbn\-arxiv48\.4048\.3548\.1848\.4048\.2447\.77Reddit88\.3188\.3488\.0688\.2688\.3687\.91Ogbn\-products55\.3355\.1955\.6255\.3555\.4955\.85
### 5\.4\.Stability Analysis: Assessing the Invariance to Hyper\-parameter Variations

To further evaluate the robustness ofSCISE, we analyze the sensitivity of seven key hyperparameters, including the merge speedpp, community numberNc​o​m​mN\_\{comm\}, learning ratel​rlr, random walk parameters \(wtw\_\{t\},wlw\_\{l\}\), expansion thresholdθ\\theta, and initial batch sizeBB\. Overall,SCISEexhibits stable performance across a wide range of settings, indicating low hyperparameter sensitivity and minimal tuning effort\.

Merge speedpp:Figure[4](https://arxiv.org/html/2607.05469#S5.F4)shows that the performance remains stable acrossp∈\{0\.001,0\.01,0\.05,0\.1,0\.5,1\}p\\in\\\{0\.001,0\.01,0\.05,0\.1,0\.5,1\\\}\. Only extreme values lead to noticeable fluctuations on a few datasets, while most settings consistently outperform the strongest baseline\.

Table 7\.Sensitivity analysis of hyperwtw\_\{t\}with NMI\.wtw\_\{t\}10203040506080100Photo73\.8774\.0074\.2174\.1274\.4074\.4274\.1874\.15Computers56\.5758\.4057\.8256\.5056\.5456\.6056\.4256\.50Pubmed35\.3635\.5835\.6235\.5435\.7335\.2135\.7335\.35Arxiv48\.2848\.3448\.3548\.5047\.9848\.5348\.3548\.27Reddit86\.3187\.4688\.3588\.1388\.1588\.0887\.7587\.72Products54\.6355\.3455\.52OOMOOMOOMOOMOOMTable 8\.Sensitivity analysis of hyperwlw\_\{l\}with NMI\.wlw\_\{l\}234567810Photo74\.4974\.0173\.4372\.5771\.9571\.2870\.8869\.94Computers56\.2056\.8157\.1357\.2659\.0258\.0358\.5258\.24Pubmed35\.6233\.6731\.3430\.8733\.2533\.1033\.5433\.99Ogbn\-arxiv48\.6048\.4048\.4648\.0147\.9347\.9748\.0247\.98Reddit87\.5688\.2588\.2887\.9987\.7287\.3487\.0486\.58products54\.1855\.2455\.2755\.6055\.7755\.96OOMOOMCommunity numberNc​o​m​mN\_\{comm\}:As shown in Figure[5](https://arxiv.org/html/2607.05469#S5.F5), the performance curves remain relatively flat across a broad range of community numbers\. Except for a localized drop on Ogbn\-arxiv, the model maintains stable clustering quality, suggesting thatSCISEis largely insensitive to the exact choice ofNc​o​m​mN\_\{comm\}\.

Table 9\.Performance comparison under varying community noise ratios \(NMI\+ARI\+ACC\+F1\)\.Dataset\\columncolorgray\!25SCISE\\columncolorgray\!10MAGIrandom noiseneighbor noiseRate\\columncolorgray\!250%\\columncolorgray\!100%1%2%4%6%8%10%20%100%1%2%4%6%8%10%20%Photo\\columncolorgray\!25294\.96\\columncolorgray\!10285\.00290\.44289\.06290\.61294\.60293\.80288\.44292\.33291\.29289\.94290\.39292\.08294\.73294\.03290\.84288\.12Computers\\columncolorgray\!25237\.03\\columncolorgray\!10224\.80236\.71244\.05234\.89234\.47236\.23231\.30227\.53209\.67235\.22236\.31236\.47234\.46239\.82237\.28231\.89Pubmed\\columncolorgray\!25216\.32\\columncolorgray\!10189\.96186\.69182\.17195\.14188\.09195\.83198\.05189\.93208\.10196\.47181\.42196\.02183\.79204\.18195\.00208\.01Ogbn\-arxiv\\columncolorgray\!25161\.73\\columncolorgray\!10143\.30160\.24160\.91159\.38159\.05158\.88159\.27159\.76143\.42159\.18161\.59157\.73158\.21161\.54158\.12158\.30Reddit\\columncolorgray\!25357\.12\\columncolorgray\!10354\.60359\.11358\.43357\.86357\.38357\.58357\.04357\.00330\.97356\.96357\.73358\.21357\.64357\.84356\.84356\.63Ogbn\-products\\columncolorgray\!25152\.95\\columncolorgray\!10146\.70151\.82150\.50152\.31152\.06151\.27150\.23151\.81136\.34148\.87151\.62149\.11149\.82148\.34150\.03151\.27![Refer to caption](https://arxiv.org/html/2607.05469v1/x12.png)Figure 6\.Sensitivity analysis of thresholdθ\\thetawith NMI\.Learning ratel​rlr:As shown in Table[6](https://arxiv.org/html/2607.05469#S5.T6),SCISEdemonstrates stable convergence across typical learning rate intervals, which further confirms that the framework is not prone to overfitting specific parameter combinations\.

Random walkerwtw\_\{t\}andwlw\_\{l\}:Tables[7](https://arxiv.org/html/2607.05469#S5.T7)and[8](https://arxiv.org/html/2607.05469#S5.T8)show only minor performance variations when changing the number and length of random walks, suggesting that the structural affinity construction is robust to different walk configurations\.

Community size thresholdθ\\theta:Figure[6](https://arxiv.org/html/2607.05469#S5.F6)shows thatSCISEmaintains stable performance forθ∈\[10,100\]\\theta\\in\[10,100\]on most datasets\. Only Pubmed exhibits a modest improvement with larger thresholds, while the overall trend remains consistent\.

Initial Batch sizeBB:Figure[7](https://arxiv.org/html/2607.05469#S5.F7)indicates thatSCISEconsistently outperforms the strongest baseline under different batch sizes\. This suggests that the framework is not strongly dependent on a specific batch configuration and can adapt to diverse hardware constraints\.

Overall,SCISEachieves consistently strong performance across a wide range of hyperparameter settings\. These results indicate that the framework requires little parameter tuning in practice, making it suitable for large\-scale graph clustering scenarios where prior knowledge is limited\.

### 5\.5\.Robustness against Noisy Community Priors

SinceSCISErelies on the community partitions generated by SECC, we further evaluate its robustness under imperfect community priors\. Specifically, we inject two types of perturbations:random noise, which randomly reassigns a fraction of nodes to different communities, andneighbor noise, which reassigns nodes according to the communities of their neighbors\. Table[9](https://arxiv.org/html/2607.05469#S5.T9)reports the results under varying noise ratios using the aggregated score \(NMI\+ARI\+ACC\+F1\)\. Overall,SCISEexhibits strong robustness to both perturbation strategies\. Even when 20% of the nodes are assigned to incorrect communities, the performance degradation remains marginal on most datasets\. In particular, the three large\-scale benchmarks \(Ogbn\-arxiv, Reddit, and Ogbn\-products\) remain highly stable under both random and neighbor noise, indicating that moderate inaccuracies in community assignments have little impact on the learned representations\.

We further consider an extreme setting with completely random community assignments \(100% random noise\)\. Although performance decreases on all datasets,SCISEremains competitive and still achieves performance comparable to or better than MAGI on several benchmarks\. This observation suggests that community priors serve as beneficial structural guidance rather than a strict prerequisite for effective clustering\. The relatively small degradation on Photo can be attributed to its limited graph size, where the expanded batches already cover a substantial portion of the graph and therefore preserve sufficient structural context even under random community assignments\. Overall, these results demonstrate thatSCISEbenefits from community\-aware priors but does not critically depend on highly accurate SECC outputs\. Combined with the hyperparameter sensitivity analysis in Figures[4](https://arxiv.org/html/2607.05469#S5.F4)and[5](https://arxiv.org/html/2607.05469#S5.F5), which shows thatSCISEremains stable across a wide range of SECC configurations, we conclude that the effectiveness ofSCISEis robust to both imperfect community partitions and variations in the SECC preprocessing stage\.

![Refer to caption](https://arxiv.org/html/2607.05469v1/x13.png)Figure 7\.Sensitivity analysis of initial batch sizeBBwith NMI\.
### 5\.6\.Robustness against Sparsity

Table 10\.Performance comparison \(NMI and ACC\) under varying edge deletion ratios\.NMIACCRate0%10%20%30%40%50%60%70%80%0%10%20%30%40%50%60%70%80%PhotoSCISE74\.5374\.4274\.2973\.9074\.0974\.3374\.1473\.8772\.8279\.7179\.7879\.7779\.6779\.6179\.6979\.7379\.5478\.62w/o SECC74\.4174\.0374\.1574\.2774\.1474\.2474\.1273\.9372\.8379\.7479\.7679\.6779\.6779\.7479\.7279\.5779\.5778\.76MAGI71\.6070\.0670\.0368\.7669\.6768\.6868\.8670\.1768\.2279\.0079\.0678\.8077\.9378\.4677\.9778\.0779\.1477\.98ComputersSCISE58\.4658\.2457\.8458\.2257\.9757\.6757\.0856\.9556\.7267\.3266\.7966\.9866\.9966\.8466\.3765\.9866\.0665\.10w/o SECC58\.1158\.3758\.1158\.2757\.6657\.4657\.1356\.1956\.2467\.0567\.2666\.9667\.1666\.7166\.0566\.0965\.4164\.95MAGI59\.2059\.0159\.4059\.5059\.6058\.7158\.7959\.3659\.9162\.0062\.0261\.7361\.4462\.6261\.5261\.9361\.6761\.08PubmedSCISE35\.7732\.9132\.3632\.0232\.3532\.3231\.6630\.7424\.2972\.3870\.6270\.0470\.2270\.3070\.0369\.8769\.2463\.34w/o SECC35\.5932\.0032\.4832\.7132\.4732\.2531\.1831\.6131\.5972\.3169\.9670\.6670\.5770\.2770\.3769\.6169\.7069\.15MAGI29\.3728\.9828\.9729\.1428\.6926\.1723\.4720\.004\.3666\.2365\.9466\.1465\.9065\.5962\.1457\.5351\.6143\.96arxivSCISE48\.4248\.1148\.0946\.1245\.5245\.1544\.2443\.3442\.1644\.1343\.4343\.3338\.2134\.7034\.9933\.6933\.5434\.14w/o SECC48\.1547\.8747\.5547\.4246\.2845\.9945\.1343\.3041\.4644\.0943\.8243\.1943\.1241\.1539\.6737\.5134\.4630\.57MAGI46\.9045\.8646\.3546\.1745\.6644\.9343\.8042\.7240\.6938\.8037\.6237\.0937\.0135\.5934\.2233\.0031\.9029\.74RedditSCISE87\.9287\.6287\.4787\.5187\.4587\.4187\.2986\.9886\.8291\.7591\.4191\.2991\.4691\.2091\.0090\.7790\.8690\.78w/o SECC87\.4585\.3384\.9484\.6485\.5885\.4084\.4384\.5484\.3591\.1483\.3882\.7081\.1484\.6482\.2082\.3582\.1482\.35MAGI87\.5087\.8487\.3487\.2987\.0987\.4486\.8187\.1587\.1291\.1091\.7990\.4089\.4489\.9790\.3188\.8090\.1490\.45productsSCISE55\.6155\.8855\.7555\.4855\.3355\.9555\.6955\.1155\.4343\.8843\.7742\.9644\.2142\.0742\.8442\.9042\.6441\.96w/o SECC55\.3356\.4955\.6455\.5955\.5155\.7655\.1255\.5255\.2042\.8944\.0542\.8643\.8642\.4242\.5742\.2642\.2142\.86MAGI55\.1055\.6655\.5256\.0554\.6455\.1254\.6854\.9454\.4342\.5041\.0840\.5941\.6239\.6340\.5441\.5440\.5938\.65Table 11\.Statistics of the batch before and after CSampE\.DatasetAVG\. NodeAVG\. EdgeAVG\. DegreePhoto2,048→\\to6,60919,475→\\to226,0009\.51→\\to34\.20Computers2,048→\\to9,71312,868→\\to374,2816\.28→\\to8\.53Pubmed2,048→\\to14,8633,002→\\to72,2801\.47→\\to4\.86Ogbn\-arxiv2,048→\\to28,5492,384→\\to204,6331\.16→\\to7\.17Reddit2,048→\\to12,12710,906→\\to1,442,9505\.33→\\to118\.99Ogbn\-products2,048→\\to22,7882,135→\\to284,6611\.04→\\to12\.49To further evaluate whetherSCISEcan alleviate structural isolation under sparse graph conditions, we progressively remove 10%–80% of the edges from the original graph and report the results in Table[10](https://arxiv.org/html/2607.05469#S5.T10)\. In addition, Table[11](https://arxiv.org/html/2607.05469#S5.T11)summarizes the statistics of mini\-batches before and after CSampE expansion\. The results reveal two important observations\.First, CSampE substantially enriches the structural context available to each mini\-batch\.Across all datasets, the expanded batches contain significantly more nodes and edges than the original sampled batches\. For example, on Ogbn\-arxiv and Ogbn\-products, the average batch size increases from 2,048 nodes to 28,549 and 22,788 nodes, respectively, while the average degree increases by more than 6×\\timesand 12×\\times\. This demonstrates that CSampE effectively reconnects fragmented local neighborhoods and recovers structural information that would otherwise be lost during mini\-batch sampling\.Second,SCISEexhibits strong robustness under severe graph sparsification\.Even after removing up to 80% of the edges, the performance degradation remains relatively moderate on most datasets\. Compared with MAGI,SCISEconsistently maintains higher NMI and ACC scores, with the advantage becoming particularly evident on sparse graphs such as Pubmed, where MAGI suffers a dramatic collapse whileSCISEpreserves substantially better clustering quality\. These results indicate that the community\-aware structural expansion introduced bySCISEeffectively mitigates the loss of connectivity caused by both mini\-batch sampling and graph sparsification, thereby improving resilience against structural fragmentation\. Interestingly,SCISEalso remains consistently more stable than its w/o SECC variant on several sparse graphs \(e\.g\., Reddit and Ogbn\-arxiv\), suggesting that the structural prior provided by SECC further improves resilience against graph fragmentation\.

### 5\.7\.Case Study: Balancing SE Minimization and Community Cohesion

To intuitively understand how SECC minimizes structural entropy while enforcing global constraints, we conduct a comprehensive case study on the Ogbn\-arxiv dataset\. Figure[8](https://arxiv.org/html/2607.05469#S5.F8)illustrates the structural entropy landscapes \(Figure[8\(a\)](https://arxiv.org/html/2607.05469#S5.F8.sf1)\) alongside the corresponding community size distributions \(Figure[8\(b\)](https://arxiv.org/html/2607.05469#S5.F8.sf2)\) under varyingNc​o​m​mN\_\{comm\}and merge speedspp\. Specifically, for Ogbn\-arxiv,Nc​o​m​mN\_\{comm\}ranges from 500 to 8,000, including a ”w/ow/o” setting representing the unconstrained scenario\. As shown in Figure[8\(b\)](https://arxiv.org/html/2607.05469#S5.F8.sf2), without SECC constraints, the number of formed communities can skyrocket to 14,335, 11,148, or 3,834 for differentppvalues\. Notably, the minimum constraint of 136 is dictated by the 115 inherent isolated nodes in the dataset and the connectivity between communities, which define the lower bound of partitionable structures\.

![Refer to caption](https://arxiv.org/html/2607.05469v1/x14.png)\(a\)Heatmap of Structural Entropy on Ogbn\-arxiv\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x15.png)\(b\)Histogram of community size on Ogbn\-arxiv\.

Figure 8\.Evolution of structural entropy and community distribution on Ogbn\-arxiv\.The heatmaps visualize the structural entropy values, where deeper shades represent lower entropy, indicating a more stable and cohesive partition\. A key observation is that structural entropy remains remarkably low and stable across a wide range ofNc​o​m​mN\_\{comm\}when modulated bypp\. Specifically, on the Ogbn\-arxiv dataset, whenppis tuned between0\.030\.03and0\.070\.07,Nc​o​m​m\>3,000N\_\{comm\}\>3,000consistently maintains the structural entropy below10\.910\.9\. This quantitative evidence proves that by executing the SECC module,SCISEsacrifices a negligible amount of structural entropy precision to secure substantial community\-level cohesion\. By constraining the solution space, SECC guides the optimization process toward partitions that are both structurally stable and semantically meaningful\. The grid of histograms further reveals how community boundaries are formed under different configurations\.\(1\) Over\-fragmentation without Constraints: As depicted in the bottom rows of Figure[8](https://arxiv.org/html/2607.05469#S5.F8)\(b\), unconstrained optimization continuously favors local entropy reduction, producing a large number of tiny communities \(size<5<5\)\. In this case, community boundaries are excessively fragmented and fail to reflect meaningful mesoscopic structures\.\(2\) Community Collapse under Excessive Constraint: Conversely, overly strict constraints \(top rows\) force many structurally distinct regions to be merged together\. The resulting boundaries become overly coarse, yielding a few dominant communities that obscure the intrinsic organization of the graph\.\(3\) Balanced Boundary Formation: In contrast, the partitions generated bySCISE\(middle rows\) exhibit a much healthier community size distribution, with few fragmented micro\-communities and few oversized giant clusters\. This indicates that the resulting boundaries emerge near structural bottlenecks where further merging provides little entropy reduction, while preserving sufficient intra\-community connectivity\. Consequently, SECC achieves a balance between entropy minimization and community cohesion, producing partitions that better align with the underlying graph structure\.

![Refer to caption](https://arxiv.org/html/2607.05469v1/x16.png)\(a\)SCISE\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x17.png)\(b\)MAGI\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x18.png)\(c\)LSEnet\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x19.png)\(d\)SCGC\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x20.png)\(e\)DeSE\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x21.png)\(f\)DinkNet\.

Figure 9\.Visualization on Pubmed\.
### 5\.8\.Visualization

To qualitatively evaluate the learned representations, we apply t\-SNE to project node embeddings into a two\-dimensional space\. Figure[9](https://arxiv.org/html/2607.05469#S5.F9)presents the visualization results on PubMed\. Compared with existing methods, the embeddings generated bySCISEexhibit more compact intra\-cluster distributions and clearer inter\-cluster boundaries\. While several baselines produce elongated or overlapping manifolds,SCISEforms well\-separated clusters with substantially reduced boundary ambiguity\. This observation suggests that the proposed community\-aware structural expansion and contrastive learning strategy effectively capture global structural semantics, resulting in more discriminative representations for graph clustering\.

## 6\.Conclusion

In this paper, we proposeSCISE, a scalable unsupervised graph clustering framework designed to alleviate structural isolation in large\-scale graph learning\. By incorporating the Structural Entropy Community Constraint \(SECC\), Community\-Aware Sampling Expansion \(CSampE\), and Structured Contrastive Learning \(StructCL\),SCISEeffectively preserves both community cohesion and global topological information during mini\-batch training\. Extensive experiments on six benchmark datasets demonstrate thatSCISEconsistently achieves state\-of\-the\-art clustering performance while maintaining strong scalability on graphs containing millions of nodes\. Beyond accuracy improvements, our analyses show thatSCISEis highly robust to noisy community priors, graph sparsification, and hyperparameter variations\. Furthermore, the additional time and memory evaluations confirm that the proposed SECC preprocessing introduces only a negligible overhead relative to the overall training pipeline, makingSCISEpractical for real\-world large\-scale deployments\. Overall, our findings highlight the importance of integrating community\-level structural information into scalable graph clustering and demonstrate that reliable structural priors can effectively mitigate sampling\-induced information loss without sacrificing efficiency or robustness\. As future work, we plan to investigate more scalable structural entropy optimization techniques and extend the proposed framework to emerging ultra\-large graph benchmarks, such as Ogbn\-papers100M\. Another promising direction is to develop adaptive community\-aware sampling strategies that automatically adjust random\-walk length and sampling budgets according to graph structural characteristics\.

###### Acknowledgements\.

This work is supported by the NSFC through grants U25B2029, 62322202, and 62432006, Beijing Natural Science Foundation through grant L253021, the Pioneer and Leading Goose R&D Program of Zhejiang through grant 2025C02044, Local Science and Technology Development Fund of Hebei Province Guided by the Central Government of China through grant 254Z9902G, Science Research Project of Hebei Higher Education Institutions under grant CYZD2026005, Shijiazhuang Science and Technology Plan Project through grant 2511301807A, Maior Science and Technology Special Projects of Yunnan Province through grants 202502AD080012 and 202502AD080006, and the Academic Excellence Foundation of BUAA for PhD Students\.

## References

- A\. Aflalo, S\. Bagon, T\. Kashti, and Y\. Eldar \(2023\)Deepcut: unsupervised segmentation using graph neural networks clustering\.InProceedings of the IEEE/CVF International Conference on Computer Vision,pp\. 32–41\.Cited by:[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1)\.
- L\. Akoglu, H\. Tong, and D\. Koutra \(2015\)Graph based anomaly detection and description: a survey\.Data mining and knowledge discovery29\(3\),pp\. 626–688\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p1.1)\.
- D\. Bo, X\. Wang, C\. Shi, M\. Zhu, E\. Lu, and P\. Cui \(2020\)Structural deep clustering network\.InProceedings of the web conference 2020,pp\. 1400–1410\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p2.1)\.
- Y\. Cao, H\. Peng, A\. Li, C\. You, Z\. Hao, and P\. S\. Yu \(2024a\)Multi\-relational structural entropy\.InProceedings of the Conference on Uncertainty in Artificial Intelligence,pp\. 1–15\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- Y\. Cao, H\. Peng, Z\. Yu, and P\. S\. Yu \(2024b\)Hierarchical and incremental structural entropy minimization for unsupervised social event detection\.InProceedings of the AAAI conference on artificial intelligence,pp\. 1–13\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- J\. Chen, J\. Zhu, and L\. Song \(2018\)Stochastic training of graph convolutional networks with variance reduction\.InInternational Conference on Machine Learning,pp\. 942–950\.Cited by:[§2\.3](https://arxiv.org/html/2607.05469#S2.SS3.p1.1)\.
- M\. Chen, B\. Wang, and X\. Li \(2024\)Deep contrastive graph learning with clustering\-oriented guidance\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 11364–11372\.Cited by:[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1)\.
- W\. Chiang, X\. Liu, S\. Si, Y\. Li, S\. Bengio, and C\. Hsieh \(2019\)Cluster\-gcn: an efficient algorithm for training deep and large graph convolutional networks\.InProceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining,pp\. 257–266\.Cited by:[§2\.3](https://arxiv.org/html/2607.05469#S2.SS3.p1.1)\.
- F\. Devvrit, A\. Sinha, I\. Dhillon, and P\. Jain \(2022\)S3GC: scalable self\-supervised graph clustering\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 3248–3261\.Cited by:[Appendix C](https://arxiv.org/html/2607.05469#A3.p3.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p2.1)\.
- S\. Fortunato \(2010\)Community detection in graphs\.Physics reports486\(3\-5\),pp\. 75–174\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p1.1)\.
- H\. Gao, Z\. Wang, and S\. Ji \(2018\)Large\-scale learnable graph convolutional networks\.InProceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining,pp\. 1416–1424\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p2.1)\.
- W\. Hamilton, Z\. Ying, and J\. Leskovec \(2017\)Inductive representation learning on large graphs\.Advances in neural information processing systems30\.Cited by:[Appendix B](https://arxiv.org/html/2607.05469#A2.p6.1),[§1](https://arxiv.org/html/2607.05469#S1.p1.1),[§1](https://arxiv.org/html/2607.05469#S1.p2.1),[§2\.3](https://arxiv.org/html/2607.05469#S2.SS3.p1.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p1.1)\.
- W\. Hu, M\. Fey, M\. Zitnik, Y\. Dong, H\. Ren, B\. Liu, M\. Catasta, and J\. Leskovec \(2020\)Open graph benchmark: datasets for machine learning on graphs\.Advances in neural information processing systems33,pp\. 22118–22133\.Cited by:[Appendix B](https://arxiv.org/html/2607.05469#A2.p5.1),[Appendix B](https://arxiv.org/html/2607.05469#A2.p7.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p1.1)\.
- L\. Huang, J\. Zhang, W\. Gong, G\. Zeng, H\. Peng, and D\. Chen \(2026\)SECTOR: structural entropy\-based learning of spatiotemporal organisation in spatial transcriptomics\.Bioinformatics42\(6\),pp\. btag367\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- X\. Huang, H\. Peng, L\. Sun, H\. Lin, C\. Liu, J\. Cao, and P\. S\. Yu \(2025\)Structural entropy guided probabilistic coding\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.39,pp\. 17467–17475\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- T\. N\. Kipf and M\. Welling \(2017\)Semi\-supervised classification with graph convolutional networks\.In5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24\-26, 2017, Conference Track Proceedings,External Links:[Link](https://openreview.net/forum?id=SJU4ayYgl)Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p1.1)\.
- G\. K\. Kulatilleke, M\. Portmann, and S\. S\. Chandra \(2025\)SCGC: self\-supervised contrastive graph clustering\.Neurocomputing611,pp\. 128629\.Cited by:[Appendix C](https://arxiv.org/html/2607.05469#A3.p11.1),[§1](https://arxiv.org/html/2607.05469#S1.p3.1),[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p2.1)\.
- A\. Li and Y\. Pan \(2016\)Structural information and dynamical complexity of networks\.IEEE TIT62\(6\),pp\. 3290–3339\.Cited by:[Definition 3\.2](https://arxiv.org/html/2607.05469#S3.Thmtheorem2.p1.3)\.
- M\. Li, Z\. Yang, X\. Zhou, Y\. Fang, K\. Li, and K\. Li \(2025\)Clustering on attributed graphs: from single\-view to multi\-view\.ACM Computing Surveys57\(7\),pp\. 1–36\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p2.1)\.
- Y\. Liu, J\. Liu, Z\. Zhang, L\. Zhu, and A\. Li \(2019\)REM: from structural entropy to community structure deception\.Proceedings of the Advances in Neural Information Processing Systems32,pp\. 1–11\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- Y\. Liu, Y\. Zheng, D\. Zhang, H\. Chen, H\. Peng, and S\. Pan \(2022a\)Towards unsupervised deep graph structure learning\.InProceedings of the ACM Web Conference 2022,pp\. 1392–1403\.Cited by:[Appendix C](https://arxiv.org/html/2607.05469#A3.p4.1),[§1](https://arxiv.org/html/2607.05469#S1.p3.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p2.1)\.
- Y\. Liu, K\. Liang, J\. Xia, X\. Yang, S\. Zhou, M\. Liu, X\. Liu, and S\. Z\. Li \(2023a\)Reinforcement graph clustering with unknown cluster number\.InProceedings of the 31st ACM international conference on multimedia,pp\. 3528–3537\.Cited by:[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1)\.
- Y\. Liu, K\. Liang, J\. Xia, S\. Zhou, X\. Yang, X\. Liu, and S\. Z\. Li \(2023b\)Dink\-net: neural clustering on large graphs\.InInternational conference on machine learning,pp\. 21794–21812\.Cited by:[Appendix C](https://arxiv.org/html/2607.05469#A3.p7.1),[§1](https://arxiv.org/html/2607.05469#S1.p3.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p2.1)\.
- Y\. Liu, J\. Xia, S\. Zhou, X\. Yang, K\. Liang, C\. Fan, Y\. Zhuang, S\. Z\. Li, X\. Liu, and K\. He \(2022b\)A survey of deep graph clustering: taxonomy, challenge, application, and open resource\.arXiv preprint arXiv:2211\.12875\.Cited by:[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1)\.
- Y\. Liu, J\. Li, Y\. Chen, R\. Wu, E\. Wang, J\. Zhou, S\. Tian, S\. Shen, X\. Fu, C\. Meng,et al\.\(2024\)Revisiting modularity maximization for graph clustering: a contrastive learning perspective\.InProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,pp\. 1968–1979\.Cited by:[Appendix C](https://arxiv.org/html/2607.05469#A3.p9.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p2.1)\.
- H\. Peng, J\. Zhang, X\. Huang, Z\. Hao, A\. Li, Z\. Yu, and P\. S\. Yu \(2024\)Unsupervised social bot detection via structural information theory\.ACM Transactions on Information Systems42\(6\),pp\. 42\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- L\. Rampášek, M\. Galkin, V\. P\. Dwivedi, A\. T\. Luu, G\. Wolf, and D\. Beaini \(2022\)Recipe for a general, powerful, scalable graph transformer\.Advances in Neural Information Processing Systems35,pp\. 14501–14515\.Cited by:[§2\.3](https://arxiv.org/html/2607.05469#S2.SS3.p1.1)\.
- Y\. Ren, J\. Pu, Z\. Yang, J\. Xu, G\. Li, X\. Pu, P\. S\. Yu, and L\. He \(2024\)Deep clustering: a comprehensive survey\.IEEE transactions on neural networks and learning systems36\(4\),pp\. 5858–5878\.Cited by:[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1)\.
- P\. Sen, G\. Namata, M\. Bilgic, L\. Getoor, B\. Galligher, and T\. Eliassi\-Rad \(2008\)Collective classification in network data\.AI magazine29\(3\),pp\. 93–93\.Cited by:[Appendix B](https://arxiv.org/html/2607.05469#A2.p4.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p1.1)\.
- O\. Shchur, M\. Mumme, A\. Bojchevski, and S\. Günnemann \(2018\)Pitfalls of graph neural network evaluation\.arXiv preprint arXiv:1811\.05868\.Cited by:[Appendix B](https://arxiv.org/html/2607.05469#A2.p2.1),[Appendix B](https://arxiv.org/html/2607.05469#A2.p3.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p1.1)\.
- X\. Shen, D\. Sun, S\. Pan, X\. Zhou, and L\. T\. Yang \(2023\)Neighbor contrastive learning on learnable graph augmentation\.InProceedings of the AAAI conference on artificial intelligence,Vol\.37,pp\. 9782–9791\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p3.1)\.
- Z\. Shi, J\. Wang, F\. Lu, H\. Chen, D\. Lian, Z\. Wang, J\. Ye, and F\. Wu \(2024\)Label deconvolution for node representation learning on large\-scale attributed graphs against learning bias\.IEEE Transactions on Pattern Analysis and Machine Intelligence46\(12\),pp\. 11273–11286\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p3.1)\.
- H\. Shirzad, A\. Velingker, B\. Venkatachalam, D\. J\. Sutherland, and A\. K\. Sinop \(2023\)Exphormer: sparse transformers for graphs\.InInternational Conference on Machine Learning,pp\. 31613–31632\.Cited by:[§2\.3](https://arxiv.org/html/2607.05469#S2.SS3.p1.1)\.
- L\. Sun, Z\. Huang, H\. Peng, Y\. Wang, C\. Liu, and P\. S\. Yu \(2024\)LSEnet: lorentz structural entropy neural network for deep graph clustering\.InInternational Conference on Machine Learning,pp\. 47078–47104\.Cited by:[Appendix C](https://arxiv.org/html/2607.05469#A3.p8.1),[§1](https://arxiv.org/html/2607.05469#S1.p3.1),[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p2.1)\.
- A\. Tsitsulin, J\. Palowitch, B\. Perozzi, and E\. Müller \(2023\)Graph clustering with graph neural networks\.Journal of Machine Learning Research24\(127\),pp\. 1–21\.Cited by:[Appendix C](https://arxiv.org/html/2607.05469#A3.p6.1),[§1](https://arxiv.org/html/2607.05469#S1.p3.1),[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p2.1)\.
- P\. Veličković, W\. Fedus, W\. L\. Hamilton, P\. Liò, Y\. Bengio, and R\. D\. Hjelm \(2018\)Deep graph infomax\.InInternational Conference on Learning Representations,Cited by:[Appendix C](https://arxiv.org/html/2607.05469#A3.p2.1),[§1](https://arxiv.org/html/2607.05469#S1.p1.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p2.1)\.
- Y\. Wang, Y\. Wang, Z\. Zhang, S\. Yang, K\. Zhao, and J\. Liu \(2023\)User: unsupervised structural entropy\-based robust graph neural network\.InProceedings of the AAAI Conference on Artificial Intelligence,pp\. 10235–10243\.Cited by:[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1),[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- F\. Wu, A\. Souza, T\. Zhang, C\. Fifty, T\. Yu, and K\. Weinberger \(2019\)Simplifying graph convolutional networks\.InInternational conference on machine learning,pp\. 6861–6871\.Cited by:[§2\.3](https://arxiv.org/html/2607.05469#S2.SS3.p1.1)\.
- J\. Wu, X\. Chen, B\. Shi, S\. Li, and K\. Xu \(2023a\)SEGA: structural entropy guided anchor view for graph contrastive learning\.InProceedings of the ICML,pp\. 1–20\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- J\. Wu, X\. Chen, K\. Xu, and S\. Li \(2022\)Structural entropy guided graph hierarchical pooling\.InProceedings of the International Conference on Machine Learning,pp\. 24017–24030\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- Q\. Wu, W\. Zhao, C\. Yang, H\. Zhang, F\. Nie, H\. Jiang, Y\. Bian, and J\. Yan \(2023b\)Sgformer: simplifying and empowering transformers for large\-graph representations\.Advances in neural information processing systems36,pp\. 64753–64773\.Cited by:[§2\.3](https://arxiv.org/html/2607.05469#S2.SS3.p1.1)\.
- Z\. Wu, S\. Pan, F\. Chen, G\. Long, C\. Zhang, and P\. S\. Yu \(2020\)A comprehensive survey on graph neural networks\.IEEE transactions on neural networks and learning systems32\(1\),pp\. 4–24\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p1.1)\.
- J\. Xie, R\. Girshick, and A\. Farhadi \(2016\)Unsupervised deep embedding for clustering analysis\.InInternational conference on machine learning,pp\. 478–487\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p1.1)\.
- M\. Xie, H\. Peng, P\. Li, G\. Zeng, S\. Wang, J\. Wu, P\. Li, and P\. S\. Yu \(2025\)Hierarchical superpixel segmentation via structural information theory\.InProceedings of the 2025 SIAM International Conference on Data Mining \(SDM\),pp\. 242–251\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- X\. Yang, Y\. Liu, S\. Zhou, S\. Wang, W\. Tu, Q\. Zheng, X\. Liu, L\. Fang, and E\. Zhu \(2023a\)Cluster\-guided contrastive graph clustering network\.InProceedings of the AAAI conference on artificial intelligence,Vol\.37,pp\. 10834–10842\.Cited by:[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1)\.
- X\. Yang, C\. Tan, Y\. Liu, K\. Liang, S\. Wang, S\. Zhou, J\. Xia, S\. Z\. Li, X\. Liu, and E\. Zhu \(2023b\)Convert: contrastive graph clustering with reliable augmentation\.InProceedings of the 31st ACM international conference on multimedia,pp\. 319–327\.Cited by:[Appendix C](https://arxiv.org/html/2607.05469#A3.p5.1),[§1](https://arxiv.org/html/2607.05469#S1.p3.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p2.1)\.
- Z\. Yang, G\. Zhang, J\. Wu, J\. Yang, Q\. Z\. Sheng, H\. Peng, A\. Li, S\. Xue, and J\. Su \(2023c\)Minimum entropy principle guided graph neural networks\.InProceedings of the Sixteenth ACM International Conference on Web Search and Data Mining,pp\. 114–122\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- R\. Ying, R\. He, K\. Chen, P\. Eksombatchai, W\. L\. Hamilton, and J\. Leskovec \(2018\)Graph convolutional neural networks for web\-scale recommender systems\.InProceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining,pp\. 974–983\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p1.1)\.
- G\. Zeng, H\. Peng, A\. Li, L\. Sun, C\. Liu, S\. Li, Y\. Pan, and P\. S\. Yu \(2026a\)Hyperbolic continuous structural entropy for hierarchical clustering\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.40,pp\. 28094–28102\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- H\. Zeng, H\. Zhou, A\. Srivastava, R\. Kannan, and V\. Prasanna \(2019\)GraphSAINT: graph sampling based inductive learning method\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p3.1),[§2\.3](https://arxiv.org/html/2607.05469#S2.SS3.p1.1)\.
- X\. Zeng, H\. Peng, A\. Li, C\. Liu, L\. He, and P\. S\. Yu \(2023\)Hierarchical state abstraction based on structural information principles\.InProceedings of the Thirty\-Second International Joint Conference on Artificial Intelligence, IJCAI\-23,E\. Elkind \(Ed\.\),pp\. 4549–4557\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- X\. Zeng, H\. Peng, and A\. Li \(2025\)Proactive bot detection based on structural information principles\.IEEE Transactions on Pattern Analysis and Machine Intelligence\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- X\. Zeng, H\. Peng, Y\. Pan, A\. Li, and G\. Wu \(2026b\)Structural information\-based hierarchical diffusion for offline reinforcement learning\.Advances in Neural Information Processing Systems38,pp\. 109539–109567\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- J\. Zhang, H\. Peng, L\. Sun, G\. Wu, C\. Liu, and Z\. Yu \(2025a\)Unsupervised graph clustering with deep structural entropy\.InProceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\. 2,pp\. 3752–3763\.Cited by:[Appendix C](https://arxiv.org/html/2607.05469#A3.p10.1),[§2\.1](https://arxiv.org/html/2607.05469#S2.SS1.p1.1),[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1),[§5\.1](https://arxiv.org/html/2607.05469#S5.SS1.p2.1)\.
- J\. Zhang, H\. Peng, M\. Yang, and P\. S\. Yu \(2025b\)Enhanced pre\-training for recommendation via hypergraph structural entropy\.ACM Transactions on Information Systems44\(2\),pp\. 1–48\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.
- Y\. Zhu, Y\. Xu, F\. Yu, Q\. Liu, S\. Wu, and L\. Wang \(2021\)Graph contrastive learning with adaptive augmentation\.InProceedings of the web conference 2021,pp\. 2069–2080\.Cited by:[§1](https://arxiv.org/html/2607.05469#S1.p2.1)\.
- D\. Zou, H\. Peng, and C\. Liu \(2024\)A structural information guided hierarchical reconstruction for graph anomaly detection\.InProceedings of the 33rd ACM International Conference on Information and Knowledge Management,pp\. 4318–4323\.Cited by:[§2\.2](https://arxiv.org/html/2607.05469#S2.SS2.p1.1)\.

## 7\.Appendix

## Appendix ANotations

The comprehensive list of the primary symbols used throughout this paper is presented in Table[12](https://arxiv.org/html/2607.05469#A1.T12)\.

Table 12\.Forms and interpretations of notations\.SymbolDefinitionG=\(V,E,X\)G=\(V,E,X\)The original graph\.VV,EE,XXThe node set , the edge set, the node feature matrix\.NN,MMThe number of nodes, the number of edges\.A∈\{0,1\}N×NA\\in\{\\\{0,1\\\}\}^\{N\\times N\}The adjacency matrix of the original graph\.ff,ddThe dimension of feature/embedding\.𝒴∈\{1,…,K\}n\\mathcal\{Y\}\\in\\\{1,\\dots,K\\\}^\{n\}Clustering assignments for all nodes\.KKNumber of clusters\.𝒯\\mathcal\{T\};λ\\lambdaEncoding tree; The root vertice of the encoding tree\.λ\\lambdaRoot node of the encoding tree𝒯\\mathcal\{T\}\.α\\alpha;α−\\alpha^\{\-\}Vertice on encoding tree\. Parent vertice of verticeα\\alpha\.TαT\_\{\\alpha\}Subset of graph nodes corresponding to tree nodeα\\alpha\.gαg\_\{\\alpha\}Total weight of cut edges betweenTαT\_\{\\alpha\}andV∖TαV\\setminus T\_\{\\alpha\}\.dvd\_\{v\}Degree of nodevv\.v​o​l​\(G\);v​o​l​\(α\)vol\(G\);vol\(\\alpha\)Volume of GraphGG; Volume of verticeα\\alpha\.H𝒯​\(G\)H^\{\\mathcal\{T\}\}\(G\)Structural entropy of graphGGinduced by encoding tree𝒯\\mathcal\{T\}\.hhThe height of the encoding tree\.𝒞=\{c1,…,cN\}\\mathcal\{C\}=\\\{c\_\{1\},\\dots,c\_\{N\}\\\}Set of communities produced by SECC\.c​\(v\)c\(v\)Community assignment of nodevv\.NcommN\_\{\\text\{comm\}\}Target number of communities in SECC\.ppParallel merge ratio controlling agglomeration rate\.Δ​H​\(ci,cj\)\\Delta H\(c\_\{i\},c\_\{j\}\)Change in SE when merging communitiescic\_\{i\}andcjc\_\{j\}\.O​POPNumber of candidate community pairs that could merge\.𝒱b​a​t​c​h\\mathcal\{V\}\_\{batch\}Initial set of sampled nodes in a mini\-batch\.𝒱e​x​t\\mathcal\{V\}\_\{ext\}Community\-guided expansion node set in CSampE\.𝒱b​a​t​c​h∗\\mathcal\{V\}^\{\*\}\_\{batch\}Final expanded batch after CSampE\.θ\\thetaCommunity size threshold for batch expansion strategy\.wl,wtw\_\{l\},w\_\{t\}Length and number of random walks, respectively\.f​\(u;v\)f\(u;v\)Random walk visitation frequency fromvvtouu\.ℛv\\mathcal\{R\}\_\{v\}Reachable node set ofvvvia intra\-community walks\.𝐀∗∈ℝB×B\\mathbf\{A\}^\{\*\}\\in\\mathbb\{R\}^\{B\\times B\}Structural affinity matrix constructed within a mini\-batch\.𝐳i\\mathbf\{z\}\_\{i\}Latent embedding of nodeviv\_\{i\}\.𝐙b​a​t​c​h\\mathbf\{Z\}\_\{batch\}embeddings of nodes in a mini\-batch\.𝐙g​l​o​b​a​l\\mathbf\{Z\}\_\{global\}consolidated global node embeddings\.𝒫i\\mathcal\{P\}\_\{i\}Structural positive set of nodeviv\_\{i\}\.ℒs​t​r​u​c​t\\mathcal\{L\}\_\{struct\}Structural contrastive learning objective\.

## Appendix BDataset

Detailed descriptions of 6 datasets are provided below:

∙\\bulletPhoto\(Shchuret al\.,[2018](https://arxiv.org/html/2607.05469#bib.bib11)\)is a segment of the Amazon co\-purchase graph specifically focusing on the photography category\. Nodes represent products \(e\.g\., cameras and lenses\), and edges indicate that two items are frequently bought together\. Each node is associated with a 745\-dimensional feature vector derived from product reviews in a bag\-of\-words format, reflecting the fine\-grained attributes of photography equipment\.

∙\\bulletComputers\(Shchuret al\.,[2018](https://arxiv.org/html/2607.05469#bib.bib11)\)is also a part of the Amazon co\-purchase network, where nodes correspond to computer\-related products and edges represent frequent co\-purchase relationships\. Similar to the Photo dataset, the node features are encoded as bag\-of\-words vectors based on product descriptions and customer reviews, capturing the semantic similarities between electronic components and peripherals\.

∙\\bulletPubmed\(Senet al\.,[2008](https://arxiv.org/html/2607.05469#bib.bib14)\)is a citation network consisting of scientific publications related to diabetes from the PubMed database\. Nodes represent documents, and edges denote citation links between them\. Each node is characterized by a feature vector represented by weighted TF\-IDF scores of unique words from the document’s abstract\.

∙\\bulletOgbn\-arxiv\(Huet al\.,[2020](https://arxiv.org/html/2607.05469#bib.bib12)\)is a directed graph representing the citation network between all Computer Science \(CS\) arXiv papers indexed by MAG\. Each node is an arXiv paper, and each directed edge indicates that one paper cites another\. The node features are derived by averaging the word embeddings of the paper’s title and abstract, and the task is to classify papers into 40 subject areas\.

∙\\bulletReddit\(Hamiltonet al\.,[2017](https://arxiv.org/html/2607.05469#bib.bib13)\)is a large\-scale social network dataset constructed from Reddit posts made in September 2014\. Nodes represent posts, and an edge exists between two nodes if the same user commented on both posts\. The node features are calculated based on GloVe word vectors, and the communities are defined by the subreddits to which the posts belong\.

∙\\bulletOgbn\-products\(Huet al\.,[2020](https://arxiv.org/html/2607.05469#bib.bib12)\)is an undirected and unweighted graph representing an Amazon product co\-purchasing network\. Nodes represent products sold on Amazon, and edges indicate that the products are purchased together\. Node features are generated by performing Principal Component Analysis \(PCA\) on the product descriptions, making it a benchmark for large\-scale graph clustering and classification\.

## Appendix CBaselines

Detailed descriptions of 10 baselines compared to our work are introduced as follows:

∙\\bulletDGI\(Veličkovićet al\.,[2018](https://arxiv.org/html/2607.05469#bib.bib36)\)is a self\-supervised node representation learning approach that maximizes the mutual information between local patch representations and high\-level graph summaries to capture global structural context\.

∙\\bulletS3GC\(Devvritet al\.,[2022](https://arxiv.org/html/2607.05469#bib.bib1)\)is a scalable self\-supervised graph clustering framework that employs contrastive learning to integrate node features with topological structures, effectively learning cluster\-friendly representations\.

∙\\bulletSUBLIME\(Liuet al\.,[2022a](https://arxiv.org/html/2607.05469#bib.bib2)\)is a structure bootstrapping contrastive Learning framework with the aid of self\-supervised contrastive learning, where the learned graph topology is optimized by data itself\.

∙\\bulletCONVERT\(Yanget al\.,[2023b](https://arxiv.org/html/2607.05469#bib.bib3)\)is a contrastive graph clustering network with reliable augmentation and distills reliable semantic information by recovering the perturbed latent embeddings\.

∙\\bulletDMoN\(Tsitsulinet al\.,[2023](https://arxiv.org/html/2607.05469#bib.bib5)\)introduces a modularity measure of clustering quality to optimize cluster assignment in an end\-to\-end manner and proposes Deep Modularity Networks\.

∙\\bulletDink\-Net\(Liuet al\.,[2023b](https://arxiv.org/html/2607.05469#bib.bib4)\)is an end\-to\-end scalable deep graph clustering method that optimizes clustering distributions through adversarial dilation and shrink losses to guide the network in learning discriminative features\.

∙\\bulletLSEnet\(Sunet al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib6)\)is a hyperbolic graph clustering network that formulates a differentiable structural information \(DSI\) objective, enabling the model to reveal hierarchical cluster structures and determine cluster numbers in a self\-supervised manner\.

![Refer to caption](https://arxiv.org/html/2607.05469v1/x22.png)\(a\)Pubmed\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x23.png)\(b\)Ogbn\-products\.

Figure 10\.Analysis of hyperNc​o​m​mN\_\{comm\}on Pubmed and Ogbn\-products datasets\.![Refer to caption](https://arxiv.org/html/2607.05469v1/x24.png)\(a\)Pubmed\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x25.png)\(b\)Ogbn\-products\.

Figure 11\.Analysis of hyperppon Pubmed and Ogbn\-products datasets\.![Refer to caption](https://arxiv.org/html/2607.05469v1/x26.png)Figure 12\.Analysis of hyperBBwith ACC\.![Refer to caption](https://arxiv.org/html/2607.05469v1/x27.png)Figure 13\.Analysis of hyperθ\\thetawith ACC\.∙\\bulletMAGI\(Liuet al\.,[2024](https://arxiv.org/html/2607.05469#bib.bib7)\)is a graph clustering framework that utilizes modularity maximization as a contrastive pretext task to define positive and negative samples, capturing structural information without manual data augmentations\.

Table 13\.Hyperparameter settings\.DatasetNc​o​m​mN\_\{comm\}ppθ\\thetabatchsizelrwtw\_\{t\}wlw\_\{l\}Photo3000\.12520480\.0051202Computers4500\.11010240\.00053010Pubmed6000\.17040960\.005302Ogbn\-arxiv35000\.048020480\.01303Reddit100017020480\.01304Ogbn\-products590000\.12040960\.005305∙\\bulletDeSE\(Zhanget al\.,[2025a](https://arxiv.org/html/2607.05469#bib.bib8)\)is an unsupervised graph clustering framework that incorporates differentiable structural entropy with soft assignment, utilizing a structural learning layer and a GNN\-based assignment module to optimize clustering on an enhanced graph\.

∙\\bulletSCGC\(Kulatillekeet al\.,[2025](https://arxiv.org/html/2607.05469#bib.bib37)\)is a scalable graph clustering framework that eliminates traditional GNN convolutions in favor of simple linear units and dynamic soft structure fusion via an augmentation\-less edge\-contrastive loss\.

## Appendix DSensitivity Analysis

This section provides supplementary results for the hyperparameter sensitivity analysis discussed in Section[5\.4](https://arxiv.org/html/2607.05469#S5.SS4)\.

∙\\bulletImpact of community numberNc​o​m​mN\_\{comm\}: Figure[10](https://arxiv.org/html/2607.05469#A3.F10)illustrates the stability ofSCISEon the Pubmed and Ogbn\-products datasets as the target community numberNc​o​m​mN\_\{comm\}varies\. The flat curves across wide intervals confirm that the SECC operator effectively anchors the partition regardless of the specificNc​o​m​mN\_\{comm\}value\.

∙\\bulletImpact of merge speedpp: Figure[11](https://arxiv.org/html/2607.05469#A3.F11)shows the distribution of performance across different merge speedsppon the Pubmed and Ogbn\-products datasets\. Box plots show that, at different structure entropy minimization granularities, as long as extreme values are not taken, the model performance is always better than the optimal baseline\.

∙\\bulletImpact of initial batch sizeBB: Figure[12](https://arxiv.org/html/2607.05469#A3.F12)shows that the model’s accuracy is higher than the baseline for most small batch sizes and remains relatively stable, further demonstrating its scalability and decoupling from hardware limitations\.

∙\\bulletImpact of community size thresholdθ\\theta: In Figure[13](https://arxiv.org/html/2607.05469#A3.F13), we present the ACC scores across different expansion thresholdsθ\\theta\. Similar to the NMI results, the model remains stable for most benchmarks\. Only on the Ogbn\-arxiv dataset does it exhibit a slight trend with increasingθ\\theta\.

Table 14\.Comparison between random\-walk affinity and PPR\-based alternatives\.VariationPhotoComputersPubmedNMIARIACCF1NMIARIACCF1NMIARIACCF1\\rowcolorgray\!20SCISE74\.53±0\.1464\.51±0\.2979\.71±0\.1576\.22±0\.1258\.46±0\.2451\.78±0\.8067\.32±0\.3659\.48±0\.8435\.77±0\.0236\.33±0\.0272\.38±0\.0171\.83±0\.01batch PPR51\.69±0\.7137\.93±2\.1262\.96±0\.9865\.25±1\.1350\.75±0\.3335\.12±2\.8752\.43±0\.6246\.43±2\.9925\.95±1\.2824\.57±0\.8863\.87±0\.8564\.17±1\.47global PPR74\.26±0\.1964\.10±0\.2979\.44±0\.2076\.15±0\.1456\.81±1\.1340\.29±2\.7956\.34±1\.5951\.37±2\.2631\.52±2\.4330\.57±3\.2768\.56±2\.8068\.16±2\.52VariationOgbn\-arxivRedditOgbn\-productsNMIARIACCF1NMIARIACCF1NMIARIACCF1\\rowcolorgray\!20SCISE48\.42±0\.0837\.66±0\.4744\.13±0\.5931\.52±0\.4187\.92±0\.1290\.97±0\.0891\.75±0\.2486\.48±0\.4155\.61±0\.0225\.65±0\.6743\.88±0\.3927\.82±0\.10batch PPR30\.23±0\.7210\.47±0\.5320\.96±0\.2217\.13±0\.1154\.95±1\.0135\.52±0\.6251\.08±1\.1244\.57±1\.2027\.80±0\.987\.38±0\.5420\.14±1\.0713\.57±0\.89global PPR45\.67±0\.1820\.33±0\.1232\.77±0\.1827\.73±0\.75OOMOOMTable 15\.Comparison ofSCISEand MAGI on Directed and Undirected Versions of Ogbn\-arxiv\.NMIARIACCF1ALLSCISE\-direct42\.9427\.1837\.3727\.40134\.90MAGI\-direct42\.2421\.9731\.0722\.35117\.63SCISE\-undirect48\.4237\.6644\.1331\.52161\.73MAGI\-undirect46\.9031\.0038\.8026\.60143\.30
## Appendix EHyperparameter Configurations

For the purpose of reproducibility and experimental transparency, we provide the specific hyperparameter settings forSCISEacross six datasets\. These configurations are consistent with the experimental results reported in Section[5\.2](https://arxiv.org/html/2607.05469#S5.SS2)\. The detailed parameter assignments are summarized in Table[13](https://arxiv.org/html/2607.05469#A3.T13)\.

## Appendix FTest on Direct Graph

Although the main paper focuses on undirected homogeneous graphs,SCISEis not inherently restricted to such settings\. To further evaluate its applicability on directed networks, we conduct an additional experiment on Ogbn\-arxiv, which is originally a directed citation graph\. Specifically, we compareSCISEand the strongest baseline MAGI under two settings: \(1\) the original directed graph and \(2\) the commonly used undirected graph obtained by symmetrizing the adjacency matrix\. The results are reported in Table[15](https://arxiv.org/html/2607.05469#A4.T15)\. Several observations can be made\. First,SCISEconsistently outperforms MAGI under both directed and undirected settings, demonstrating that the proposed framework remains effective even when edge directions are preserved\. Second, bothSCISEand MAGI achieve better performance on the undirected graph\. This suggests that bidirectional neighborhood information provides more complete structural signals for community discovery and representation learning\. Third, despite the performance reduction caused by preserving edge directions,SCISEstill maintains a clear advantage over MAGI across all evaluation metrics\. Overall, these results indicate thatSCISEis not limited to undirected graphs and can be directly applied to directed networks\. Nevertheless, the current work mainly targets homogeneous graph clustering, while extending the structural entropy constrained community framework to heterogeneous and more complex graph settings remains an important direction for future research\.

## Appendix GTest on Personalized PageRank

To further validate our technical design regarding the affinity matrix computation, we conducted an ablation study replacing our random walk mechanism with Personalized PageRank \(PPR\), a well\-established metric in the graph clustering literature\. We introduced two variants for comparison: \(1\)global PPR, which computes the exact Personalized PageRank over the entire original graph, and \(2\)batch PPR, which computes the Personalized PageRank restricted strictly within the sampled mini\-batch\. The quantitative results across six datasets are presented in Table[14](https://arxiv.org/html/2607.05469#A4.T14)\. The empirical findings strongly support our choice of a restricted random walk over PPR due to two critical limitations of the latter:The Scalability Bottleneck of Global PPR:While global PPR maintains relatively competitive performance on smaller datasets \(e\.g\., Photo\), it fundamentally lacks scalability\. On massive datasets such as Reddit and Ogbn\-products, calculating and storing the dense global affinity matrix for millions of nodes immediately triggers Out\-of\-Memory \(OOM\) errors\. This extreme memory consumption violates the core scalability requirements of our framework, making global PPR completely infeasible for large\-scale graph clustering\.The Performance Degradation of Batch PPR:To circumvent the OOM issue, batch PPR limits the computation to the local subgraphs within the batch\. However, as demonstrated in Table[14](https://arxiv.org/html/2607.05469#A4.T14), this localized approach leads to a severe degradation in clustering effectiveness across all datasets\. For instance, on the Ogbn\-arxiv dataset, the NMI score drops dramatically from 48\.42 \(SCISE\) to 30\.23 \(batch PPR\)\. Similarly, on the Reddit dataset, the NMI plummets from 87\.92 to 54\.95\. This sharp decline occurs because calculating PPR within a strictly truncated batch suffers from severe boundary effects, isolating nodes from their broader topological environment and losing the crucial global structural context necessary for accurate affinity estimation\. In contrast, our proposed random walk mechanism dynamically captures structural affinity without requiring dense global matrix computations\. It effectively circumvents OOM errors while preserving the global structural context, thereby achieving an optimal balance between state\-of\-the\-art clustering effectiveness and strict scalability\.

![Refer to caption](https://arxiv.org/html/2607.05469v1/x28.png)\(a\)Heatmap of Structural Entropy on Photo\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x29.png)\(b\)Histogram of community size on Photo\.

Figure 14\.Evolution of structural entropy and community distribution on Photo\.![Refer to caption](https://arxiv.org/html/2607.05469v1/x30.png)\(a\)Heatmap of Structural Entropy on Ogbn\-products\.
![Refer to caption](https://arxiv.org/html/2607.05469v1/x31.png)\(b\)Histogram of community size on Ogbn\-products\.

Figure 15\.Evolution of structural entropy and community distribution on Ogbn\-products\.