When Is Reweighting Not Enough? A Hodge Certificate for Rewiring Noisy and Incomplete Graphs

Graph repair methods change an edge in one of two ways. They change how much it counts, which we call reweighting, or whether it exists, which we call rewiring. Structure learners mix the two moves and rarely ask which one a graph needs. We give an exact answer to one form of this question. The predictions of a frozen node classifier, compared across each edge, form a flow on the graph. Hodge decomposition splits the flow into a gradient part, which one score per node explains, and a cycle part, which no such score explains. We prove that no positive reweighting of a fixed edge set lets one score per node explain the cycle part, and that weights of spread γ move its share of the flow by at most a factor γ. A nonzero cycle part therefore certifies that an exact fit requires rewiring. We turn the certificate into the Hodge Router. It rewires an instance only when the cycle fraction is large relative to its chance level, ranks the edits by their share of the cycle part, and sends the edits on which the structural signals disagree to a language model under a fixed query budget. The bound holds on every weighting we draw. Corruption raises the diagnostic to about 1.6 times its clean value, and the diagnostic predicts which operation helps better than seven competing statistics, with a partial Spearman correlation of 0.38. Under random corruption the router matches or exceeds the better fixed operation on every dataset. Under Metattack it rewires nearly every instance, and under PRBCD it reweights the graphs on which reweighting wins, so it follows the operation each attack favors. It has the best average accuracy of all compared methods under both attacks, ahead of the joint structure learners JDR and Pro-GNN.