When a semi-supervised model labels its own unlabeled data and then trains on those guesses, wrong guesses get reinforced. One of the better ways to produce guesses is to spread the few known labels over a nearest-neighbor graph built from the network's features. The weak point is a handful of edges that bridge two classes. Labels flow through these bridges and contaminate whole clusters. Sparse linear algebra has spent decades finding exactly such bridges, for a different reason. To solve a graph system by elimination without creating too many new nonzeros, a solver splits the graph at small "vertex separators": node sets whose removal disconnects it.
This note proposes using those separators as a noise diagnostic. If a pseudo-label is wrong, most of its evidence probably arrived through a narrow separator from a distant labeled seed, rather than from seeds inside its own region. A direct factorization ordered by nested dissection computes this "where did the label come from" split exactly. The split falls out of the same factor used to solve the system, at every level of the separator hierarchy, with no extra solves. We call it separator provenance. We propose to test whether it predicts pseudo-label errors better than the confidence and certainty scores used today, and whether gating training on it reduces confirmation bias.
Core Claim
Fill-in minimization is the problem of ordering variables in Gaussian or Cholesky elimination so the factor stays sparse. Its best-known strategy, nested dissection, recursively finds small separators and eliminates them last. With that ordering, the leading diagonal blocks of the factor are exactly the factorizations of the separated subgraphs, each with the separator held at zero.
Consider the label-diffusion system $(L+\Lambda)F=\Lambda Y$. Here $L$ is the graph Laplacian of the feature $k$-nearest-neighbor graph, $\Lambda$ is a diagonal weight that is nonzero on labeled nodes, $Y$ holds one-hot seed labels, and $F$ holds the diffused class scores. Write $M=L+\Lambda$, and split the nodes into a subgraph $A$ and its separator $S$. The solution on $A$ then decomposes as
$$F_A = \underbrace{M_{AA}^{-1}(\Lambda Y)_A}_{\text{local evidence}} \;-\; \underbrace{M_{AA}^{-1}M_{AS}F_S}_{\text{evidence imported through } S}.$$
Both terms are available from the nested-dissection factor through partial forward and back substitutions, and the decomposition applies recursively down the separator tree. For each unlabeled node $i$, we define its import ratio $r_i$ as the fraction of its winning class score that is attributable to the imported term, taken at the coarsest separator level that dominates it.
Our hypothesis is that high-$r_i$ pseudo-labels are wrong far more often than their diffusion certainty suggests, especially early in training. If so, the ordering a sparse solver already computes to save memory doubles as a structural filter against error propagation.
Relation to Prior Work
Two papers motivate this proposal by showing that graph diffusion is the right source of pseudo-labels, while leaving its failure mode untreated. Label Propagation for Deep Semi-Supervised Learning rebuilds a feature $k$-NN graph every epoch, diffuses labels with power iteration, and weights the resulting pseudo-labels by an entropy-based certainty. Its diffused labels beat the network's own softmax outputs early in training. Entropy, however, cannot tell a confident local label from a confident label that leaked across a bridge, and the method does no reordering or factorization at all. Large-Scale Graph-Based Semi-Supervised Learning via Tree Laplacian Solver avoids fill-in by pruning the graph to a minimum spanning tree and solving in linear time. That pruning removes the cycles that give robustness to a single bad edge, and the paper does not study noise at all. We keep the full graph and use the elimination structure diagnostically, rather than sparsifying it away.
Three papers supply the method. Nested dissection and minimum-degree orderings are classical. ReFill learns elimination orders that reduce fill; we use it only as a possible alternative ordering source. Adaptive Algebraic Reuse of Reordering in Cholesky Factorizations with Dynamic Sparsity Patterns (Parth) reuses orderings when the sparsity pattern changes locally, and we borrow it to amortize reordering across epochs.
Parth's evidence comes only from physics and remeshing workloads, whose changes are spatially coherent. Feature-graph drift during self-training may not be coherent in the same way. Measuring that drift is therefore a secondary question here, not an assumption.
Nested Graph Pseudo-Label Refinement is the closest work in spirit, since it fights confirmation bias using explicit graph structure. It operates on whole-graph classification with kernel and message-passing branches, and it never touches node-level diffusion or elimination orderings. Thresholding methods define the competing noise-control paradigm, which ignores graph structure entirely. FixMatch uses a fixed confidence cutoff, FlexMatch uses per-class curriculum cutoffs, and Tri-net uses dropout-stability checks.
Research Program
We first build the diagnostic. At each epoch we construct the $k$-NN feature graph as Iscen et al. do, compute a nested-dissection ordering, and factor $M$ with a supernodal Cholesky. We then extract the hierarchical local/imported decomposition for all unlabeled nodes. In the second epoch onward, Parth-style reuse recomputes orderings only for subgraphs whose edges changed.
The first study is purely observational and uses ground-truth labels of the unlabeled pool. It asks whether $r_i$ separates correct from incorrect pseudo-labels, and how much information it adds beyond entropy certainty. It also asks how this changes across training.
The second study turns the diagnostic into a training signal. Pseudo-label weights become the product of the existing certainty weight and a decreasing function of $r_i$. This gate plugs into two pipelines: the label-propagation-plus-Mean-Teacher pipeline, and a FixMatch/FlexMatch pipeline in which diffusion supplies or vetoes pseudo-labels.
The third study characterizes when the idea can work at all. We measure separator sizes and factor fill on real feature graphs. High-dimensional $k$-NN graphs can behave like expanders, with large separators, and then the factor becomes expensive and "narrow bridge" stops being meaningful. We also measure what fraction of the ordering Parth can reuse from one epoch to the next, which directly tests the tension the file identifies between Parth's locality assumption and continuously drifting features.
Baselines
The naive reference is diffusion pseudo-labels with uniform weights, together with the purely supervised model. On CIFAR-10 with 500 labels, Iscen et al. report roughly 49% error for supervised training and 32.4% error for label propagation alone. Every gated variant must beat the uniform-weight version under the identical graph, backbone, and schedule.
The strongest graph-based competitor is the entropy-certainty and class-balancing weighting of Label Propagation for Deep Semi-Supervised Learning. Combined with Mean Teacher it reports 24.02% error on CIFAR-10 with 500 labels and 70.29% top-1 error on Mini-ImageNet with 4,000 labels. We rerun it with the same features, $k$, diffusion strength, and number of epochs, and we give it the same hyperparameter search budget as our gate. Beating it means lower final error averaged over at least three labeled-seed draws. It also means higher error-detection AUROC for $r_i$ combined with certainty than for certainty alone.
The strongest threshold-based competitor is FlexMatch, which reports 39.94% error on CIFAR-100 with 400 labels, against 46.42% for FixMatch. FixMatch reports 88.61% accuracy on CIFAR-10 with 40 labels and a 64.28% median with one label per class. We run both in a shared codebase, with identical augmentation and iteration budgets, and add our gate as a veto on their pseudo-labels. A win means improvement over the reproduced numbers, not merely over the cited ones.
Two ablations isolate the key ingredient. The first, the "cluster-has-seed" ablation, uses the same nested-dissection partition but replaces the continuous, multilevel $r_i$ with a binary flag for whether a node's leaf subgraph contains a labeled seed. The second replaces nested-dissection separators with an equally sized random or BFS-based partition. The first tells us whether the exact algebraic decomposition matters. The second tells us whether the fill-minimizing separators matter, as opposed to any partition.
Why not just…?
Why not just use the certainty weights or a lower-entropy cutoff on the diffused labels? Entropy measures how peaked a node's class scores are, not where they came from. A cluster with no seed of its own, fed entirely through one bridge, can receive sharp and wrong scores. Whether this happens often enough to matter is an empirical question. The observational study answers it directly: if $r_i$ adds no detection AUROC over certainty, the proposal fails at its first check.
Why not just partition the graph with any clustering method and distrust clusters without a seed? This is the most serious threat, and we treat it as one. If the cluster-has-seed ablation matches the continuous score, the scientific finding still stands: errors leak through bottlenecks. The factorization machinery, however, would be unnecessary, and we would report it that way. The continuous score should help in two situations. One is mixed nodes, near separators, that receive evidence from both sides. The other is the one-label-per-class regime, where most leaf subgraphs contain no seed and a binary flag discards almost everything.
Why not just compute the same decomposition with iterative solves, avoiding factorization fill-in? The local term for each subgraph can indeed be computed with conjugate gradient or power iteration by clamping the separator to zero. Doing so requires a separate solve per subgraph per hierarchy level, whereas the factor provides all of them through substitutions. We will report wall-clock time for both routes, using warm-started iterative solves as the honest competitor. If iterative solves are cheaper on our graphs, the contribution reduces to the provenance score itself, with nested dissection used only to choose the separators, and we will say so. Zhang et al.'s report of iterative solvers taking hundreds of seconds on 630,000-sample Extended MNIST suggests that the factorization route matters at scale. That evidence, however, comes from a tree solver, not ours.
Why not just use FlexMatch-style curriculum thresholds and skip graphs entirely? Thresholds rely on the model's own confidence, which is exactly what confirmation bias corrupts. FlexMatch also notes that minority classes on imbalanced data such as SVHN never raise their thresholds. Running FlexMatch with and without the provenance veto on SVHN and on CIFAR-100 tests whether structural evidence helps where thresholds are known to be weak.
Proposed Experiments and Decisive Checks
The datasets are CIFAR-10 (40, 250, and 500 labels, plus one label per class), CIFAR-100 (400 labels), Mini-ImageNet (4,000 labels), and SVHN as the imbalance stress test. All use the protocols of the cited papers. For each, we report final error, pseudo-label precision at matched recall, and error-detection AUROC for every score. We also report factor fill, separator size, ordering reuse fraction across epochs, and per-epoch solve time.
The first decisive check is observational. On CIFAR-10 with 500 labels, at epochs where pseudo-label error is still high, $r_i$ must raise error-detection AUROC above entropy certainty, and must beat the random-partition ablation by a clear margin.
The second check concerns training. Gating must reduce final error relative to the reproduced certainty-weighted pipeline, across seed draws, with the largest gains in the one-label-per-class regime, where the file reports the widest spread in outcomes.
The third check concerns feasibility. Separators on CIFAR-scale feature graphs must stay small enough that factor fill fits in memory. If they do not, we fall back to the iterative route and treat separator size itself as a measure of how cluster-structured the representation is. Parth's reuse fraction across epochs will show whether representation drift during self-training is local enough for symbolic reuse. That question is open, and the answer is useful to both communities regardless of how the gating results come out.
References
- Label Propagation for Deep Semi-supervised Learning
- Large-Scale Graph-Based Semi-Supervised Learning via Tree Laplacian Solver
- ReFill: Reinforcement Learning for Fill-In Minimization
- Adaptive Algebraic Reuse of Reordering in Cholesky Factorizations with Dynamic Sparsity Patterns
- Nested Graph Pseudo-Label Refinement for Noisy Label Domain Adaptation Learning
- FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence
- FlexMatch: Boosting Semi-Supervised Learning with Curriculum Pseudo Labeling
- Tri-net for Semi-Supervised Deep Learning