PaperlayerView exact revision on arXiv

Source-linked AI summary

Propagate, Then Sharpen: Post-Hoc Refinement of Frozen Node Classifiers

Preben Johnsen Bentdal, Nello Blaser, Xue-Cheng Tai

arXiv:2609.35080v1cs.LGstat.ML

TL;DR

Post-hoc refinement asks whether a frozen node classifier’s accuracy can be improved using only its class distributions and the graph. PtS alternates probability propagation with mass-preserving sharpening, and improves mean test accuracy over independently tuned APPNP across nine homophilic graphs with an MLP backbone.

  • Problem

    Can accuracy be recovered from frozen class distributions Q and graph G without access to node features, model parameters, gradients, or training data?

    Source: §1 · p. 1

  • Method

    PtS alternates graph propagation of class probabilities with node-wise, mass-preserving sharpening motivated by the Dirichlet–Gini decomposition of the Potts interaction.

    Source: §1 · p. 2

  • Results

    Across nine homophilic graphs with an MLP backbone, PtS improves mean test accuracy over independently tuned APPNP by 3.90 points under severe Gaussian corruption and 1.71 on clean inputs.

    Source: §5 · p. 9

  • Takeaways & Limitations

    PtS removes most of the accuracy drop of deep propagation, while gains over APPNP are smaller with graph-aware backbones and negligible on heterophilic graphs.

    Source: §5 · p. 9

    The main results select hyperparameters at the evaluated corruption severity, assuming validation nodes reflect test-time conditions; evaluation covers Gaussian feature corruption, not missing features or graph perturbations.

    Source: §5 · p. 9

Abstract

from arXiv · show

We study post-hoc refinement of frozen node classifiers: given only the graph $G$ and class distributions $Q$ predicted by a frozen model, can we improve accuracy without access to node features, model parameters, or gradients? APPNP answers this by propagating logits with a restart towards the initial predictions, minimizing the anchored Dirichlet energy. Instead, we consider the Potts energy, and decompose it into a Dirichlet term, which penalizes disagreement between neighbouring nodes, and a Gini term, which penalizes indecision within each node. This decomposition motivates Propagate, Then Sharpen (PtS), which alternates between propagation of class probabilities and node-wise, mass-preserving sharpening, with only one additional hyperparameter selected using labelled validation nodes. Across nine homophilic graphs, with a frozen MLP backbone, PtS improves mean test accuracy over independently tuned APPNP by $1.71$ percentage points on clean inputs and $3.90$ under severe Gaussian feature corruption. Gains over APPNP become smaller, but remain positive with frozen GCN and GraphSAGE backbones. Sharpening also removes most of the accuracy loss of deep propagation: on clean inputs without restart, accuracy falls by $2.2$ points between $2$ and $100$ propagation steps under PtS, compared with $33.8$ for APPNP.

1 Introduction

This section introduces post-hoc refinement using only a frozen classifier’s predictions and the graph, then motivates PtS as a way to balance neighbour agreement with within-node decisiveness. PtS alternates probability propagation and mass-preserving sharpening; its reported gains over APPNP persist across the evaluated corruption settings.

Motivation

  • The refinement question is whether accuracy can be recovered from frozen class distributions Q and graph G without features, model parameters, gradients, or training data.The motivation includes fragile or unavailable features and settings where retraining or access to model internals may be restricted.Source: §1 · p. 1
  • APPNP propagates logits with restart toward initial predictions, but corrupted references can be repeatedly reinjected and errors spread through the graph.Without restart it collapses at large depth; with restart it is sensitive to depth and restart hyperparameters.Source: §1 · p. 1
  • The relaxed Potts interaction decomposes into a Dirichlet term penalizing neighbour disagreement and a Gini term penalizing within-node indecision.This motivates pairing graph smoothing with local sharpening; probability propagation also bounds initial scores in [0, 1], limiting extreme-logit influence while averaging can weaken preferences when neighbours disagree.Source: §1 · p. 2

Contributions

  • 3.90 points under severe Gaussian corruption and 1.71 on clean inputs: PtS improves mean test accuracy over independently tuned APPNP across nine homophilic graphs.The section also reports that PtS improves on average over graph-adapted LAME and a post-hoc Graph-TV baseline.Source: §1 · p. 2
  • PtS alternates probability-space graph propagation with mass-preserving sharpening, adding one parameter η while preserving each node’s predicted class.At η = 0 it reduces exactly to propagation without sharpening; labels are used only for hyperparameter selection, and any backbone outputting class probabilities can be used.Source: §1 · p. 2

Related Work

  • PtS transfers Potts-based splitting to graphs, unlike methods that refine learned representations inside trained GNNs, and acts on frozen model outputs without learnable parameters.Its local sharpening is a soft, mass-preserving counterpart to hard thresholding as η → ∞ when the largest class probability is unique.Source: §1 · p. 2

2 Method

The method starts from frozen class distributions on a graph and alternates restart-based probability propagation with node-wise sharpening. Its propagation and sharpening steps are connected to separate energy terms, without establishing descent of the joint Potts objective.

2 Method

  • The method represents the graph with symmetrized edges, removes duplicate edges and existing self-loops, then adds self-loops; the frozen classifier supplies class distributions Q.The graph operator is a symmetrically normalized adjacency, and each row of Q lies on the probability simplex.Source: §2 · p. 3

2.1 Propagate

  • PPR-Prob applies personalized PageRank recursion to class distributions rather than logits, retaining unnormalized states during propagation and row-normalizing the final state.The recursion uses restart probability α and K steps; APPNP instead propagates logits and applies softmax at the end.Source: §2.1 · p. 3

2.3 Energy interpretation and local descent

  • Propagation descends an anchored, degree-normalized Dirichlet objective and sharpening decreases a local KL–Gini energy, but this does not establish descent of the joint Potts objective.Without restart or sharpening, predictions collapse on a connected graph; in a two-community example, APPNP and PPR-Prob misclassify one community at every K ≥ 3, while PtS with η = 4 keeps all nodes correct.Source: §2.3 · pp. 4–5, §2.2 · p. 4

2.2 Propagate, Then Sharpen

  • PtS alternates propagation and node-wise categorical sharpening; sharpening redistributes class probability while preserving each propagated row’s mass and ranking of classes.It changes a node’s predicted class only through later propagation; η = 0 recovers PPR-Prob exactly.Source: §2.2 · pp. 3–4, §2.3 · p. 5

3 Experimental protocol

The experiments evaluate post-hoc refinement on nine homophilic graphs, using frozen predictions from graph-blind MLPs and additional graph-aware backbones. They compare independently tuned methods on clean inputs and a nested ladder of Gaussian feature-corruption severities.

Datasets and splits

  • The protocol uses nine homophilic graphs and reports two heterophilic graphs separately as controls.The graphs use supplied, official, or random splits as specified, and runs include three backbone seeds per split.Source: §3 · p. 5

Backbones and predictions

  • For each unit, a graph-blind MLP is trained on clean features and frozen; GCN and GraphSAGE backbones follow the same training and corruption protocol.The frozen predictions are computed once per corruption and reused across methods and experiments.Source: §3 · p. 5

Feature corruption

  • Inference adds Gaussian feature noise at σ ∈ {0, 0.5, 1, 1.5, 2}, with three shared noise fields per graph and split reused across severities.The severity ladder is nested, and the feature scale uses each feature’s standard deviation over training nodes.Source: §3 · p. 5

Tuning and baselines

  • APPNP, PPR-Prob, and PtS are independently tuned with 250 Optuna trials per unit, severity, and noise draw using validation accuracy.LAME-Graph and Graph-TV are external post-hoc baselines; Graph-TV is evaluated only at σ ∈ {0, 2} and excludes ogbn-products for memory reasons.Source: §3 · pp. 5–6

4 Results

Across the nine main graphs, PtS improves mean test accuracy over APPNP and reduces the accuracy loss from deep propagation. Its gains persist under corruption and with graph-aware backbones, alongside a calibration trade-off.

4.1 Accuracy on clean and corrupted inputs

  • PtS improves mean test accuracy over independently tuned APPNP by 1.71 percentage points on clean inputs and 3.90 at σ = 2.At σ = 2, mean accuracy is 41.95% for unrefined Q, 56.34% for APPNP, and 60.24% for PtS; PtS also beats APPNP on all nine graphs when clean and eight of nine at σ = 2.Source: §4.1 · p. 6, Table 1 · p. 6

4.2 Sharpening and propagation depth

  • Without restart, increasing propagation depth from 2 to 100 reduces clean accuracy by 2.2 points for PtS with η = 200, versus 33.8 for APPNP.At K = 100, PtS remains above APPNP and PPR-Prob in every shown restart and corruption condition; Figure 2 varies restart by column and corruption severity by row.Source: §4.2 · p. 7, Figure 2 · p. 7

4.3 Corruption severity

  • PtS gains over APPNP remain positive across tested corruption severities, including when both methods are selected on clean validation data.At σ = 2, the advantage is 2.28 points with clean-only selection, compared with 3.90 under severity-matched selection; Figure 3 compares PtS with APPNP and PPR-Prob.Source: §4.3 · pp. 7–8, Figure 3 · p. 8

4.4 Backbone

  • With frozen GCN and GraphSAGE backbones, PtS gains over APPNP at σ = 2 are 0.88 and 1.23 points, respectively.Gains are positive on all nine graphs at σ = 2 for both backbones, but are smaller than with MLPs.Source: §4.4 · p. 8, Table 3 · p. 8, Figure 4 · p. 8

4.5 Calibration and runtime

  • At σ = 2, PtS has higher raw NLL and ECE than APPNP, while temperature scaling lowers its mean NLL below APPNP without changing accuracy.Its ECE remains higher after scaling, and PtS costs 1.3–54 ms per propagation step.Source: §4.5 · p. 8

5 Discussion

The discussion reports that refinement recovers some corruption-related accuracy loss, while its gains depend on validation conditions and graph setting. The appendices derive the Potts-based graph energy and document the method’s supporting analyses.

5 Discussion

  • 25.5 points of frozen-MLP accuracy loss from σ = 0 to σ = 2 falls to 16.4 points with PtS, a 36% reduction versus 27% for APPNP.Graph-aware backbones lose less initially (8 and 14 points) and refinement recovers 25% and 22% of those losses.Source: §5 · p. 9
  • Main results tune hyperparameters at each evaluation severity, assuming validation nodes reflect test-time conditions; clean-only validation preserves but shrinks the gain.The study evaluates Gaussian feature corruption, not missing features or graph perturbations; sharpening worsens raw calibration, mitigated by temperature scaling.Source: §5 · p. 9
  • Similar constraints could extend to graphs carrying exploitable geometric or topological information.The discussion points to image-segmentation work incorporating convexity, connectivity, and volume constraints.Source: §5 · p. 9

Reproducibility statement

  • The reproducibility statement points to the protocol, dataset statistics, model sizes, search spaces, selected hyperparameters, baseline settings, and code.These materials are identified across the paper’s sections, tables, appendices, and repository.Source: Reproducibility statement · p. 10

Appendix overview

  • The appendices cover energy derivations, experimental details, external baselines, stronger backbones, mechanism ablations, calibration, and computational cost.They include comparisons with LAME-Graph and Graph-TV, plus analyses of propagation depth and local homophily, degree, and confidence.Source: Appendix overview · p. 13

A From the continuous Potts energy to the graph energy

  • The graph energy is obtained by transferring the continuous Potts formulation to nodes, replacing positions and integrals with graph nodes and sums.The frozen classifier supplies the assignment cost, anchoring the graph energy to its predictions.Source: A From the continuous Potts energy to… · p. 13, §A.1 · p. 14

A.1 Graph analogue

  • The graph Potts interaction decomposes into Dirichlet disagreement between connected nodes and Gini indecision within node distributions.Identical but uncertain neighbouring distributions incur no Dirichlet penalty, yet still contribute to Gini.Source: §A.1 · p. 14

B Derivation of the sharpening step

The sharpening derivation uses a local KL–Gini energy to motivate a mass-preserving reaction after propagation. The related analysis distinguishes PtS from a coupled Potts/LAME update and characterizes collapse under propagation without restart.

B Derivation of the sharpening step

  • One fixed-point sharpening step follows from a local energy combining distance to the propagated distribution with a Gini penalty; η = 0 makes the reaction an identity.The implementation uses one iteration and restores row mass, which determines each row’s contribution to the next propagation step.Source: B Derivation of the sharpening step · pp. 14–15

C Relation to Potts and LAME

  • The coupled Potts/LAME update keeps the original predictions as its reference, whereas PtS propagates first and sharpens using the propagated distribution.The Potts decomposition motivates PtS but does not imply that its iteration reduces the global energy.Source: C Relation to Potts and LAME · pp. 15–16

D Properties of sharpening

  • Sharpening preserves class ordering and decreases local Gini, while the analysis shows restart alone may not preserve correct predictions at every depth.The constructed example shows restart alone can fail, whereas PtS keeps every node correct at every depth.Source: D Properties of sharpening · p. 17, §D.1 · p. 17

D.1 Pure propagation collapses

  • Without restart, pure probability propagation converges to the same normalized weighted average of initial predictions at every node.For APPNP at α = 0, node distributions need not coincide, but all predicted labels collapse onto a single class.Source: §D.1 · p. 17

D.2 Restart alone does not preserve a minority community

On a two-community graph, APPNP and PPR-Prob misclassify the minority community from depth 3, while PtS keeps every node correct; sharpening preserves class ordering and decreases local Gini energy.

D.2 Restart alone does not preserve a minority community

  • For every depth K ≥ 3, APPNP and PPR-Prob misclassify every node in B, while PtS with η = 4 classifies every node correctly.The figure tracks correct-class probability in B using the same graph, initial predictions, and α = 0.1 for all methods.Source: §D.2 · p. 18, Figure 5 · p. 18

D.3 Sharpening preserves the class ordering

  • Sharpening preserves each node’s class ordering, so it reinforces existing preferences without changing the predicted class.A sufficiently large η can restore confidence when the leading class survives propagation, but the same η also sharpens nodes whose leading class is wrong.Source: §D.3 · p. 19

D.4 Proof of Proposition 1

  • Every inner sharpening iteration decreases the local KL–Gini energy, and for η > 0 the Gini impurity strictly decreases unless the distribution is unchanged.This descent follows from the majorization argument for the sharpening update.Source: §D.4 · p. 20

E Datasets

The dataset suite spans graphs with varied sizes, edge counts, homophily, and class counts, and reports heterophilic controls separately.

E Datasets

  • The datasets vary in node and edge counts, homophily, and number of classes.Edges are reported as undirected-pair counts, and h denotes edge homophily.Source: E Datasets · p. 21, Table 4 · p. 21
  • Heterophilic control datasets are reported separately to show method behavior when neighbouring nodes often belong to different classes.Source: E Datasets · p. 21
  • Table 4 summarizes the dataset statistics for the nine graphs in the main board and the heterophilic controls.Source: E Datasets · p. 21, Table 4 · p. 21

F Frozen backbones

The study applies PtS after training frozen MLP, GCN, and GraphSAGE backbones, then tunes propagation and sharpening settings with validation accuracy.

F Frozen backbones

  • PtS is applied after the frozen base models are trained and adds no trainable parameters to them.The MLP uses node features alone, whereas GCN and GraphSAGE also use graph structure.Source: F Frozen backbones · p. 21, Table 5 · p. 21

G Hyperparameter search spaces

H Selected hyperparameters (MLP)

  • PtS tuning selected more propagation steps than PPR-Prob across multiple graphs, while sharpening strength varied by dataset and noise level and was sometimes turned off.The selected depths should be interpreted alongside restart weight α.Source: Table 7 · p. 24, H Selected hyperparameters (MLP) · p. 25

I External post-hoc baselines

The external post-hoc baselines refine the same frozen predictions on the same graph and evaluation units as PtS, with validation labels used only for hyperparameter selection. PtS has higher average accuracy in the reported comparisons, though it does not lead on every dataset.

I External post-hoc baselines

  • Both baselines refine the same frozen predictions Q on the same observed graph and evaluation units as PtS, using validation labels only for hyperparameter selection.Source: I External post-hoc baselines · p. 26
  • LAME-Graph replaces LAME’s pretrained-feature affinities with the self-looped graph operator, keeping original predictions as the reference while graph interaction enters inside the softmax.Its interaction strength and fixed iteration count are selected by validation accuracy.Source: I External post-hoc baselines · p. 26
  • Graph-TV keeps predictions close to Q with a KL term and penalizes disagreement across the graph with classwise neighbourhood total variation.Its λ is selected by validation accuracy from a grid of candidates.Source: I External post-hoc baselines · p. 26
  • PtS has higher average accuracy than the external baselines in the reported comparisons, but is not best on every dataset.On clean data, LAME-Graph performs better on ogbn-arxiv, TAPE-Arxiv23, and Books-History; the Graph-TV comparison covers eight graphs, excluding ogbn-products for memory requirements.Source: Table 8 · p. 26, I External post-hoc baselines · p. 27, Table 9 · p. 27

J Full decomposition

Under severe corruption, probability-space propagation and sharpening each contribute to gains over APPNP, and PtS also outperforms APPNP with frozen GCN and GraphSAGE backbones.

J Full decomposition

  • At σ = 2, probability-space propagation accounts for 2.81 percentage points of mean gain, and adding sharpening contributes a further 1.09 over APPNP.The contributions vary by graph: WikiCS gains +1.01 and +3.17, while ogbn-arxiv gains +6.57 and +0.18, respectively.Source: J Full decomposition · p. 27, Table 10 · p. 27
  • With PtS-selected (α, K) held fixed, setting η to zero lowers mean accuracy to 54.93%, below APPNP.The propagation configurations selected for PtS are therefore viable only in combination with sharpening; PtS generally selects deeper propagation than PPR-Prob.Source: J Full decomposition · p. 27
  • With hyperparameters selected on clean data and evaluated at σ = 2, PtS gains 2.28 percentage points over APPNP across the nine main graphs.Source: J Full decomposition · p. 27

K.1 GCN Backbone

The analyses find gains across backbone and pipeline variants, while also identifying conditions and trade-offs: sharpening helps at depth, benefits vary by node and dataset, and calibration worsens before temperature scaling.

K.1 GCN Backbone

  • With a frozen GCN, PtS exceeds APPNP on all nine main graphs at σ = 2 and on seven of nine graphs with clean inputs.Source: §K.1 · p. 28, Table 11 · p. 28

K.2 GraphSAGE backbone

  • With GraphSAGE, PtS achieves higher accuracy than APPNP on the nine main homophilic graphs at selected noise levels, with gains that vary across backbones and increase with noise.Improvements are more prominent on ogbn-arxiv and Ele-Computers, and smaller on ogbn-products.Source: §K.2 · p. 28, Table 12 · p. 28

L Correct and Smooth comparison

N Preserving mass

  • Preserving propagated row mass gives larger improvements under noise, especially on WikiCS and Ele-Computers, but row normalization is better on ogbn-arxiv in both settings.Mass preservation affects results but does not guarantee higher accuracy.Source: N Preserving mass · p. 32, Table 16 · p. 32

O Depth sensitivity

  • At greater depths, strong sharpening substantially reduces the accuracy loss of pure diffusion without restart; η = 200 works best at large depth without restart, while η = 16 is better with restart at σ = 2.Restart dampens the decrease, but PtS retains its advantage at greater depths in this analysis.Source: O Depth sensitivity · p. 32, Table 17 · p. 33

P Dirichlet and Gini

  • Propagation reduces Dirichlet energy and increases Gini energy, while sharpening reverses those changes; Proposition 1 guarantees local energy descent under sharpening.Because sharpening preserves each node’s predicted class, its effect on validation accuracy at greater depth occurs through subsequent propagation steps.Source: P Dirichlet and Gini · pp. 33–34, Figure 6 · p. 34

Q Per-node performance

R Runtime and overhead; S Calibration

Related papers

Loading 2609.35080v1…