Balance as a Free Auditor for LLM-Labeled Signed Networks

Large language models are increasingly used as cheap annotators. They read text and emit labels that later train a small model. When the labels are relations between pairs of entities, such as whether one editor supports or opposes another, or whether two users trust or distrust each other, the cost problem is quadratic: there are far more pairs than items, and each pair needs a model call. Text pipelines control label noise with expensive extra checks: a second model filter in DISCO, round-trip retrieval in Promptagator, and multi-agent debate in BARRED. Each of these multiplies the number of model calls per accepted label.

Relational labels have a property that text labels lack. They must be mutually consistent. Structural balance theory, a social-science regularity, says that "the enemy of my enemy is my friend." A network obeying it can be split into factions with friendly ties inside each faction and hostile ties between them. Chiang et al. showed that such a network's signed adjacency matrix has rank at most the number of factions. That makes balance a global constraint that can be checked in seconds rather than through hours of cycle counting. We propose to use this constraint as an almost-free auditor of LLM-generated edge signs. Fit a low-rank balanced model to the teacher's labels. Treat the edges the model contradicts as suspects. Spend expensive verification, meaning a stronger teacher or a debate round, only on those suspects. The question is how much of the verification budget can be removed without losing label quality or downstream accuracy.

Core Claim

Under a fixed budget of teacher calls, routing re-verification to the edges that most violate a low-rank balanced fit will reach the label accuracy of verifying every edge, at a small fraction of the calls. It will also beat routing by the teacher's own confidence. The second half of the claim is what makes this more than matrix completion. BARRED reports that single-model self-critique ("Self-Refine") did worse than no verification at all, and that removing debate cost 27% accuracy on human-annotated data. Those results suggest a model's own signals are poor at locating its own errors. Balance is an external signal: it comes from the other edges, not from the model that produced this one. We predict it locates teacher errors that teacher confidence misses, especially errors correlated with surface cues in the text.

The constraint also shapes the scope. Directed networks governed by hierarchy (status theory) rather than alliance break the balance assumption. In those networks the auditor should flag true edges, and the claim should fail. We treat this as a falsifiable boundary, not an embarrassment.

Research Program

The pipeline has three stages. First, a teacher LLM labels the sign of an initial random sample of candidate pairs from their associated text. Second, we fit a signed low-rank model to these noisy labels. We use the squared-hinge factorization of Chiang et al. and, as an alternative, cluster assignments from the regularized generalized eigenproblem of SPONGE. For each labeled edge we compute a frustration score:

$$s_{ij} = \max\left(0,\, 1 - y_{ij}\,\langle u_i, v_j\rangle\right),$$

where $y_{ij}\in\{-1,+1\}$ is the teacher's label for pair $(i,j)$ and $u_i, v_j$ are the fitted low-rank factors. A high $s_{ij}$ means the label disagrees with the balanced structure implied by everything else. To avoid an edge vouching for itself, the factors are refit with folds of edges held out. Third, the remaining budget goes to re-verifying the highest-scoring edges with a stronger teacher or a two-agent advocate-and-judge exchange in the style of BARRED, and the loop repeats. The final labels train a compact signed graph student. We use a dual-channel attention model such as SNEA or SiGAT, which keep positive and negative messages in separate channels. This matters because Xu et al. found that mixing the two signs in a single channel collapses node representations.

We account for cost in teacher calls and tokens, plus wall-clock time for the auditor. The cost of the low-rank fit matters here. Chiang et al. report about 20 seconds on Slashdot against over 3 hours for 5-cycle counting, which is why we use the global fit rather than triangle enumeration. For larger graphs we will test the linear-time balancing approximation of Dinesh et al. as a still cheaper auditor. SPONGE argues that greedy local heuristics degrade on sparse, noisy graphs. Comparing the two auditors on the same budget therefore directly tests that tension.

Two data regimes are used. The controlled regime uses Epinions and Slashdot, whose human signs serve as ground truth. We inject teacher-like noise that is structured rather than uniform: negatives flip to positive more often than the reverse, mirroring the strong positive skew of real signed graphs, and flips concentrate on low-degree nodes. This goes beyond the uniform 20% sign noise SPONGE was tested against. The real-teacher regime uses Wikipedia Requests for Adminship, where an LLM labels votes from their written justifications and the recorded votes are ground truth. This depends on obtaining the vote texts, which the file does not document. If they are unavailable, we fall back to the controlled regime only and state the limitation.

Baselines

The naive reference point labels a random subset of pairs with the teacher, using the whole budget, and trains the student on those labels unaltered. It shows how much any verification buys.

The strongest existing structural method is plain low-rank completion on teacher labels, the LR-SIG approach of Chiang et al., with no re-query. Completion already denoises, so it is the most likely to match us. The relevant reported figure is LR-SIG at 94.65% sign-prediction accuracy on Epinions with human labels, against 55.39% for the triangle-based MOI-3. We treat 94.65% as the ceiling a fully human-labeled graph reaches. For any LLM-labeled signed graph, there is no reported result found on Lacuna. This baseline gets the same initial labels, the same rank and regularization search, and spends its remaining budget labeling more random pairs.

The strongest verification method borrowed from text pipelines is confidence-guided re-query. The remaining budget goes to the edges where the teacher was least confident, measured by token probability or disagreement across several samples. It receives the same total calls and the same stronger verifier, so the only difference from our method is which edges get rechecked.

An upper reference sends every labeled edge to the stronger verifier. It measures the accuracy we aim to approach at lower cost.

The ablation isolating the key ingredient replaces frustration-ranked re-query with random re-query under the identical budget and fit. If random re-query matches it, the gain came from extra labels, not from balance.

Beating the baselines means two things. Our method must reach label accuracy within one point of the verify-everything reference while using under half its verifier calls. It must also beat both completion-only and confidence-guided re-query on held-out human signs at equal budget, across at least three random seeds.

Why not just…?

Why not just run matrix completion on the teacher's labels and stop? This is the real threat. If teacher errors were roughly random, low-rank completion would absorb them and re-query would add little. We expect teacher errors to be systematic, for example sarcastic opposition read as support. Systematic errors bias the fit rather than averaging out, and only fresh evidence on the suspected edges corrects them. The completion-only baseline settles this directly. If it matches our method on Requests for Adminship, the honest conclusion is that balance helps as a denoiser but not as a router, and we report it that way.

Why not just re-query where the teacher is unsure? It needs no graph and is cheap. But BARRED's finding that self-critique performs worse than no verification suggests a model's own uncertainty is a poor guide to its own errors. We test this as a detection problem. We measure the area under the ROC curve of the frustration score versus teacher confidence for predicting which labels are wrong, and we also report a combination of the two. If confidence wins outright, the proposal reduces to a cheap combination and we say so.

Why not just generate synthetic signed graphs from a signed stochastic block model and skip the LLM? Block-model graphs are free. SPONGE uses them to show near-perfect cluster recovery, with adjusted Rand index near 1. But they have uniform within-block probabilities and none of the text-linked, heavy-tailed structure of real platforms. A student trained on them would never see the actual relations in a target network. We include a block-model-pretrained student as an extra reference on Epinions to show the gap rather than assert it.

Proposed Experiments

The first decisive check is error detection. On every dataset and noise model, we ask whether the held-out frustration score predicts wrong teacher labels better than teacher confidence. A detection AUROC that is not clearly above confidence ends the main claim.

The second check is the budget curve. We plot held-out sign accuracy and student link-prediction accuracy against total teacher calls for all baselines, and read off the calls needed to reach the verify-everything accuracy. We will also compare the Dinesh et al. linear-time auditor against SPONGE and the factorization auditor along the same curve. This shows whether the cheap approximation's lower precision costs downstream accuracy.

The third check is the boundary test. We restrict Epinions and Slashdot to directed edges whose triads fit status theory better than balance, and expect the advantage over random re-query to vanish or reverse. We also report the fraction of frustrated triads in the ground-truth graphs. This shows how much real frustration the auditor must tolerate, and guards against an auditor that simply erases genuine dissent.

Finally, the student is evaluated on human-labeled held-out edges. Negative-edge recall is reported separately, since class imbalance is where signed models usually fail and where a balance auditor should matter most.