SCGNN: Semantic Consistency enhanced Graph Neural Network Guided by Granular-ball Computing

Genhao Tian, Taihua Xu, Shuyin Xia, Qinghua Zhang, Jie Yang, Jianjun ChenarXiv 2026 · arXiv

TL;DR

SCGNN introduces a highly scalable alternative to expensive pairwise similarity searches ($k$NN) in Graph Neural Networks by leveraging Granular-Ball Computing (GBC) to capture group-level semantic consistency. By combining an anchor-based graph augmentation strategy with a robust label consistency check, SCGNN consistently boosts the accuracy of various GNN backbones while scaling effortlessly to million-node graphs.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) traditionally rely on message passing over an observed graph structure. However, this structure-driven approach often fails to capture rich semantic relationships hidden entirely within node features.

To bridge this gap, existing methods typically build a feature-similarity graph using Full Search Algorithms (FSA) like $k$-Nearest Neighbors ($k$NN). While effective in theory, $k$NN suffers from a quadratic computational complexity ($\mathcal{O}(n^2)$), causing it to hit severe memory bottlenecks on large datasets. Furthermore, its rigid neighbor selection mechanism often introduces noisy connections. The authors of this paper set out to design a scalable, noise-robust framework that extracts high-quality semantic consistency from node features without breaking the computational bank.

Methods

The authors propose SCGNN (Semantic Consistency enhanced Graph Neural Network), a plug-and-play framework featuring a dual enhancement strategy:

  1. Granular-Ball Computing (GBC) for Semantic Mining: Instead of performing exhaustive node-to-node similarity checks, SCGNN adaptively partitions the feature space into "granular balls" (GBs). This shifts the focus from fine-grained node comparisons to group-level semantics, dropping the preprocessing complexity to near-linear ($\mathcal{O}(ndkt)$).
  2. Structure Enhancement: Using the generated granular balls, the framework constructs an augmented graph ($G^{aug}$). It generates virtual "anchor nodes" representing the mean feature of nodes within each granular ball. It then injects group-level semantics into the graph topology via projection edges (connecting anchors to their constituent nodes) and bridging edges (linking anchors that share similar semantics).
Figure 3: Anchor-based graph structure illustration. For clarity, only the edges associated with blue-labeled nodes is shown. Green edges are bridging edges between anchor nodes, red edges are projection edges.
  1. Supervision Enhancement via Label Consistency Checking (LCC): To provide cleaner training signals, SCGNN cross-references the GBC's local domain predictions with the GNN's model predictions. Only nodes where both distinct paradigms agree are retained to generate high-reliability pseudo-labels, filtering out ambiguous or noisy instances.

During training, the vanilla graph and the augmented graph are jointly encoded in a parallel architecture, and their predictions are dynamically fused using an attention mechanism.

Figure 5: The pipeline of the SCGNN. The augment graph and GBC prediction are guided by granular-ball computing.

Datasets

The framework was evaluated across 11 diverse benchmark datasets spanning different scales and homophily levels:

  • Small/Medium Scale: Cora, CiteSeer, PubMed, Wiki, Cornell, Wisconsin, Texas.
  • Large Scale: Physics, Roman-empire, Amazon-ratings, and the million-scale ogbn-arxiv.

No new datasets were introduced, ensuring direct comparability with existing literature.

Key Insights and Ideas

  • Group-Level Semantics as a Filter: Moving away from exact node-to-node similarity to coarse-grained "granular balls" acts as a natural noise filter. It prevents the model from over-fitting to feature-complex or ambiguous outlier nodes.
  • The Power of Paradigm Disagreement: GNNs are structure-driven, while GBC is feature-driven. By forcing a Label Consistency Check (LCC) between these two fundamentally different learning paradigms, the authors mathematically prove that the pseudo-label noise rate drops quadratically rather than linearly.
Figure 4: Illustration of the noise reduction effect of LCC with 𝑐= 7 classes.
  • True Plug-and-Play: SCGNN doesn't alter the underlying GNN architecture; it simply augments the input graph and adds auxiliary losses during training, making it compatible with GCN, GAT, GIN, GraphSAGE, and more.

Key Results

  • Massive Scalability Gains: On the million-scale ogbn-arxiv dataset, traditional $k$NN fails completely due to Out-Of-Memory (OOM) errors (>92 GB RAM required). In contrast, GBC processes the dataset in just 106 seconds while utilizing a mere 597 MB of memory.
Table 1 Comparison of time and memory overhead of GBC and 𝑘NN on datasets of different scales. We have a total of 92160MB (90GB) of RAM memory.
  • Consistent Accuracy Improvements: SCGNN consistently outperformed state-of-the-art graph augmentation methods (like BORF, ComFy, and AGMixup) across all 7 tested GNN backbones. For example, on the heterophilous Cornell dataset using a standard GCN backbone, SCGNN achieved an accuracy of 67.57%, significantly outperforming ComFy (48.11%) and BORF (38.91%).

Limitations and Future Work

While highly effective, the authors note a couple of areas for improvement:

  • Simplified Noise Assumptions: The theoretical proof for the LCC noise reduction assumes independent noise rates between the GNN and GBC predictors. In practice, their predictions may exhibit minor correlations, which could slightly degrade the ideal quadratic noise reduction.
  • Bridging Edge Overhead on Ultra-Large Graphs: For massive graphs, fully connecting anchors with the same label can become expensive. While the authors suggest a random $k$-edge connection strategy as a workaround, finding an optimal, adaptive bridging topology remains an open direction for future work.

Summary updated

Abstract

Capturing semantic consistency among nodes is crucial for effective graph representation learning. Existing approaches typically rely on $k$-nearest neighbors ($k$NN) or other node-level full search algorithms (FSA) to mine semantic relationships via exhaustive pairwise similarity computation, which suffer from high computational complexity and rigid neighbor selection, limiting scalability and introducing noisy connections. In this paper, we propose the Semantic Consistency enhanced Graph Neural Network (SCGNN), a novel plug-and-play framework that leverages granular-ball computing (GBC) to efficiently capture semantic consistency in a scalable manner. Unlike node-level FSA methods, SCGNN models group-level semantic structure by adaptively partitioning nodes into granular balls, significantly reducing computational cost while improving robustness to noise. To effectively utilize the discovered group-level semantic consistency, we design a dual enhancement strategy. Specifically, (1) a structure enhancement module constructs an anchor-based graph structure, where each anchor is a virtual node representing the group-level semantic carried by a granular ball, then injecting group-level semantic information into the graph structure; and (2) a supervision enhancement module performs label consistency checking (LCC) by combining GBC predictions with model-generated pseudo-labels, thereby producing more reliable supervision signals. SCGNN is compatible with various GNN backbones. During the forward propagation of SCGNN, the vanilla graph and the augment graph are jointly encoded, and their predictions are fused; during the backpropagation, the supervision enhancement module provides enhanced supervision signals to guide parameter updates.
BibTeX
@misc{tian2026scgnn,
  author = {Genhao Tian and Taihua Xu and Shuyin Xia and Qinghua Zhang and Jie Yang and Jianjun Chen},
  title = {{SCGNN: Semantic Consistency enhanced Graph Neural Network Guided by Granular-ball Computing}},
  year = {2026},
  eprint = {2605.02617},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.02617},
}
Figure