Technical Summary: Where LLM Annotators Fail: Label-Free Learning on Graphs with LLMs

Problem Statement

Node classification on text-attributed graphs (TAGs) traditionally relies on labeled nodes, but obtaining ground-truth labels at scale is expensive. While Large Language Models (LLMs) offer a low-cost alternative by annotating a small subset of nodes based on semantic content (e.g., paper abstracts, product descriptions), these generated labels are inherently noisy. Existing label-free graph learning methods attempt to mitigate this noise by treating LLM reliability as either a global property of the annotator or a class-conditional confusion pattern.

The authors identify a critical failure mode in these existing approaches: LLM annotation errors are not uniform. Instead, reliability varies significantly across feature-space regions (clusters) even within the same true class. For instance, on the DBLP dataset, the "Database" class exhibits an average LLM accuracy of 64.7%, but this masks a sharp disparity where accuracy ranges from 81.0% in one cluster to 21.6% in another. Treating reliability as class-conditional leads to over-trusting unreliable clusters and under-utilizing reliable ones, causing errors to propagate through the graph via message passing and pseudo-label expansion.

Methodology: Cluster-Aware Noise Estimation (CANE)

To address this, the authors propose CANE, a label-free learning framework that estimates cluster-conditional LLM reliability without requiring ground-truth labels. The pipeline consists of five stages:

1. Representative Seed Selection and Annotation:

   • Nodes are embedded using a self-supervised GraphMAE2 encoder and clustered into $K=2C$ regions (where $C$ is the number of classes).
   • The most central nodes in each cluster are selected as seeds to ensure representation of diverse feature-space regions.
   • A subset of these seeds ($\rho = 0.4$) is designated as a probe set and annotated by the LLM first. The remaining seeds are annotated later. This probe set is used to estimate reliability without incurring additional query costs.

2. Cluster-Conditional Noise Estimation:

   • CANE estimates a cluster-conditional transition matrix $T_c$, where $T_c[k, i, j] = P(\hat{y}=j | y=i, \text{cluster}=k)$.
   • Crucially, this is estimated without ground truth. The method uses cross-modality agreement: for a probe node $v$, it calculates the fraction of its neighbors (both graph neighbors and feature-space nearest neighbors) that the LLM labeled identically to $v$.
   • High agreement between independent views (structure and features) serves as a proxy for label correctness. The diagonal entries of $T_c$ are set to the mean agreement for each (cluster, class) pair, with off-diagonal entries distributed uniformly.

3. Pseudo-label Expansion:

   • A GNN is trained on the initial LLM-labeled seeds.
   • During self-training expansion, the acceptance threshold for pseudo-labels is adjusted based on local reliability. For a node in cluster $k$ predicted as class $g$, the threshold $\tau_g$ is raised if the estimated reliability $T_c[k, g, g]$ is low:
     $$\tau_g(k) = \tau_g + \alpha(1 - T_c[k, g, g])$$
   • This ensures that in unreliable regions, only highly confident predictions are accepted, preventing noise propagation.

4. Iterative Label Correction:

   • The framework iteratively retrains the GNN and corrects labels that disagree with the model's current prediction.
   • A label is only overwritten if the GNN prediction is supported by a sufficient number of agreeing neighbors, where the required support threshold is modulated by the local reliability $T_c$. Labels in reliable regions are protected from being overwritten by weak evidence, while labels in noisy regions are corrected more readily.

5. Final Training:

   • A final GNN is trained on the stabilized, refined label set to produce predictions for all nodes.

Key Contributions

1. Identification of Cluster-Conditional Noise: The paper empirically demonstrates that LLM annotation noise in TAGs is not merely class-dependent but region-dependent. Reliability varies sharply across feature-space clusters within the same class, a phenomenon existing methods fail to capture.
2. CANE Framework: The authors propose a label-free framework that estimates a per-cluster transition matrix using self-supervised graph embeddings and LLM annotation statistics (specifically cross-modality agreement), eliminating the need for ground-truth labels during the noise estimation phase.
3. Adaptive Learning Pipeline: CANE integrates these reliability estimates into both pseudo-label expansion (via adaptive thresholds) and iterative label correction (via reliability-gated updates), allowing the system to trust labels more in reliable regions and correct them more aggressively in noisy ones.

Experimental Results

The authors evaluated CANE on five text-attributed graph benchmarks (CITESEER, CORA, PUBMED, WIKICS, DBLP) using GCN and GAT backbones, comparing against strong baselines like LLM-GNN, DMA, and LOCLE.

• Performance: CANE outperformed the strongest label-free baseline (LOCLE) on 8 out of 10 dataset-backbone combinations. It consistently surpassed LLM-GNN and DMA across all settings.
• Correlation with Noise Structure: The performance gains were most significant on datasets exhibiting strong cluster-conditional noise (e.g., DBLP, WIKICS, CITESEER), where the LLM's accuracy fluctuates widely between clusters. On PUBMED, where LLM accuracy was already high and uniform, CANE provided marginal gains, consistent with the method's design.
• Robustness: The method remained effective when the underlying LLM annotator was swapped from GPT-3.5-turbo to GPT-4o-mini, indicating that CANE adapts to the specific error patterns of the annotator rather than relying on a specific model's quirks.
• Ablation Studies: Removing the cluster-conditional noise model (collapsing it to a global matrix) significantly reduced performance, confirming that local noise modeling is the primary driver of improvement. The label-free estimation of $T_c$ performed nearly identically to an oracle estimate using ground truth, validating the efficacy of the agreement-based estimator.
• Budget Sensitivity: CANE showed superior performance in low-budget regimes (scarce labels), degrading more gracefully than baselines as the annotation budget decreased.

Significance and Claims

The paper claims that cluster-conditional noise modeling represents a necessary evolution beyond class-conditional approaches in label-free graph learning. By acknowledging that LLM reliability is a function of local feature-space regions, CANE provides a more precise mechanism for filtering and correcting noisy supervision.

The authors position CANE as a step toward more robust, cost-effective graph learning that leverages the semantic capabilities of LLMs while mitigating their inconsistency. They note that while the method does not modify graph structure (unlike some baselines that use graph rewiring), it offers a complementary approach that can be combined with structural methods. The work highlights that the "failure mode" of LLM annotators is not random but structured, and exploiting this structure allows for significant improvements in node classification without human intervention.