Fractional Heat Kernel for Semi-Supervised Graph Learning with Small Training Sample Size

Farid Bozorgnia; Vyacheslav Kungurtsev; Shirali Kadyrov; Mohsen Yousefnezhad

cs.LGOct 6, 2025

Fractional Heat Kernel for Semi-Supervised Graph Learning with Small Training Sample Size

Authors: Farid Bozorgnia, Vyacheslav Kungurtsev, Shirali Kadyrov, Mohsen Yousefnezhad

Abstract

We develop a source-driven fractional heat-kernel framework for semi-super-vised graph learning that combines nonlocal propagation with sustained label information. A fixed nonzero label source compatible with the Laplacian null space prevents asymptotic collapse into that space, providing a mechanism for mitigating oversmoothing at long diffusion times. The fractional order controls the relative modal attenuation and the spectral weighting of the sustained response, while the diffusion time sets the propagation horizon. We characterize conservation laws and equilibria on normalized and disconnected graphs, develop a null-space deflation, and analyze the approximation of the propagators. On Two-Moon, fractional orders improve source-free propagation, while compatible source-driven diffusion exceeds $96\%$ mean accuracy with one training label per class at orders $0.8$ and $1$ . On Cora and CiteSeer, the source-driven pipeline improves mean accuracy over GAT by $9.2$ and $8.0$ percentage points at one training label per class, with model selection on $500$ labeled validation nodes and closely comparable classical and fractional pipeline configurations; it matches GAT on PubMed and trails it at ten and twenty labels per class on Cora. Within GraphHeat, validation-based exponent selection at a common diffusion time yields a paired gain of $1.45$ percentage points at one label per class.

Figures & tables

$s$	$g_{s}(\lambda_{2})$	$g_{s}(1)$	$g_{s}(\lambda_{\max})$
0.30	0.089	0.0067	0.0040
0.50	0.226	0.0067	0.0027
0.75	0.444	0.0067	0.0016
1.00	0.642	0.0067	0.0009
1.50	0.876	0.0067	0.0003

Table 1 . Spectral filter

g_{s}(\lambda)=e^{-t\lambda^{s}}

t=5

on the symmetric normalized Laplacian of a two-block stochastic block model (

\lambda_{2}=0.089

\lambda_{\max}=1.40

). The fixed point

g_{s}(1)=e^{-5}

is independent of

s

Figure 1 . Spectral damping validation on Cora. Panel (a) plots the relative damping ratio $R(\lambda_{k})=e^{-T\lambda_{k}^{0.5}}/e^{-T\lambda_{k}}$ , with sampled eigenvalues overlaid on the analytic curve. Panel (b) compares damped low-frequency spectral amplitudes for $s=1$ and $s=0.5$ . The transition at $\lambda_{k}=1$ verifies that fractional diffusion damps modes below one more strongly and modes above one more weakly than classical heat diffusion.

$m$	$s=0.5$	$s=0.75$	$s=1.0$
4	$3.7\times 10^{-1}$	$1.3\times 10^{-1}$	$1.8\times 10^{-2}$
8	$2.1\times 10^{-1}$	$4.3\times 10^{-2}$	$4.2\times 10^{-5}$
12	$1.5\times 10^{-1}$	$2.2\times 10^{-2}$	$2.0\times 10^{-8}$
16	$1.1\times 10^{-1}$	$1.4\times 10^{-2}$	$3.0\times 10^{-12}$
20	$9.1\times 10^{-2}$	$1.0\times 10^{-2}$	$2.1\times 10^{-15}$
24	$7.7\times 10^{-2}$	$7.7\times 10^{-3}$	$2.3\times 10^{-15}$

Table 2 . Operator-norm Chebyshev error

\|e^{-tL^{s}}-p_{m}(L)\|_{2}

t=5

, where

p_{m}

approximates

x\mapsto e^{-tx^{s}}

on the spectrum of

L

. Convergence is geometric at

s=1

and only algebraic for non-integer

s<1

Symbol	Definition
$\mathcal{L}_{k}$	Set of currently labeled nodes at iteration $k$
$\mathcal{U}_{k}$	Set of unlabeled nodes at iteration $k$ , $\mathcal{U}_{k}=V\setminus\mathcal{L}_{k}$
$\mathcal{E}_{0}$	Fixed pool of nodes eligible for pseudo-label promotion
$\mathcal{E}_{k}$	Remaining eligible nodes, $\mathcal{E}_{k}=\mathcal{E}_{0}\setminus\mathcal{L}_{k}$
$\mathcal{C}_{k}$	Set of high-confidence nodes selected for pseudo-labeling at iteration $k$
$Y_{k}$	Current label matrix, including original and pseudo-labels

Table 3 . Quantities referred to in the algorithms of this section.

Figure 2 . Two-Moon with one labeled point per class: true classes, initial labels, and propagated labels for the trial of median test accuracy among the $50$ trials of Table 4 for Scheme 2 at $s=1$ . The validation-selected time is the long-time limit $t=\infty$ ; the test accuracy is $0.980$ , and $23$ of the $1000$ points are misclassified (circled), all in the overlap of the two moons.

$s$	Labels per class	Scheme 1	Scheme 2	Scheme 3
0.2	1	0.886 $\pm$ 0.016	0.928 $\pm$ 0.014	0.928 $\pm$ 0.014
0.2	2	0.938 $\pm$ 0.009	0.966 $\pm$ 0.004	0.966 $\pm$ 0.004
0.2	3	0.960 $\pm$ 0.008	0.971 $\pm$ 0.004	0.971 $\pm$ 0.004
0.2	4	0.965 $\pm$ 0.006	0.977 $\pm$ 0.003	0.977 $\pm$ 0.003
0.2	5	0.978 $\pm$ 0.002	0.979 $\pm$ 0.002	0.979 $\pm$ 0.002
0.2	6	0.982 $\pm$ 0.003	0.982 $\pm$ 0.002	0.982 $\pm$ 0.002

Table 4 . Two-Moon: mean accuracy on the

400

test nodes

\pm

standard error over

50

trials for the three diffusion schemes. Within a trial the schemes share the point set, the label draw and the validation and test nodes. Schemes 2 and 3 coincide at

s=0.2

, where no node crosses the promotion threshold in any trial.

Setting	Values	Status
Random splits	$10$ ; $k$ labels per class, $500$ validation, $1000$ test nodes	fixed
Laplacian	$L_{\mathrm{sym}}$ of $A+I$ ; componentwise source $\mathcal{C}_{\phi}$ , $\phi=\widetilde{D}^{1/2}\mathbf{1}$	fixed
Fractional order $s$	$0.75$ (Tables 6 , 7 ); grid $\{0.30,0.50,0.75,1.00,1.25\}$ (Table 14 , Section 6.3 )	fixed / selected
Diffusion time $t$	$\{0.5,1,2,4,8,16,32\}\cup\{\infty\}$ with the exact eigendecomposition (Cora, CiteSeer); $\{0.5,1,2,4,8,16,32\}$ with the Chebyshev expansion (PubMed)	selected per split and order
Chebyshev degree $M$	$64$ ; relative error below $2\times 10^{-3}$ at $s=0.75$ , $t\leq 32$	fixed
Refined graph	cosine $10$ -NN of the GAT embeddings, clipped at $0$ , symmetrized by the maximum; $A^{\prime}=\tfrac{1}{2}W_{k}+\tfrac{1}{2}A$	fixed

Table 5. Settings of the citation-network experiments (Tables 6 , 7 and 14 ). “Selected” means chosen on the validation nodes of each split; “fixed” means set in advance. Two-Moon settings are given in Section 6.1 . The Neural FHK++ rows apply to Tables 16 and 17 .

per class	GAT	$s{=}1$	tuned $s$	$s{=}1$	$s{=}0.75$	Holm $p$	$\Delta$ vs. $s{=}1$
Labels		GraphHeat		Pipeline
1	$48.1\pm 5.4$	$54.3\pm 6.6$	$55.0\pm 6.6$	$57.5\pm 6.6$	$57.3\pm 6.3$	$0.001$	$-0.3\pm 0.7$
2	$57.2\pm 7.8$	$61.4\pm 5.9$	$61.8\pm 5.5$	$62.5\pm 5.4$	$62.2\pm 5.5$	$0.134$	$-0.3\pm 0.5$
3	$65.4\pm 4.8$	$68.7\pm 3.5$	$68.4\pm 3.4$	$67.9\pm 4.3$	$67.9\pm 4.3$	$0.097$	$-0.0\pm 0.2$
4	$69.5\pm 4.2$	$71.4\pm 3.1$	$71.0\pm 3.2$	$72.0\pm 2.9$	$71.8\pm 3.0$	$0.097$	$-0.2\pm 0.2$
5	$70.9\pm 3.3$	$72.4\pm 2.9$	$72.5\pm 2.9$	$72.3\pm 3.0$	$72.2\pm 3.0$	$0.134$	$-0.1\pm 0.5$

Table 6 . Cora, the same

10

splits throughout: GAT, GraphHeat with matched sparsity at the classical and at the validation-tuned exponent, and label-space diffusion on the GAT-refined graph at the classical (

s{=}1

) and the fractional (

s{=}0.75

) kernel; mean

\pm

95\%

t

-interval. Holm

p

is the Holm-adjusted paired

t

-test of the fractional pipeline against GAT across the seven budgets, and

\Delta

the matched per-split difference between the two kernels of the pipeline. The GraphHeat arms were run at one to five labels per class.

Dataset	Labels/class	GAT	Classical ( $s{=}1$ )	Fractional ( $s{=}0.75$ )	$\Delta$ vs. $s{=}1$
CiteSeer	1	$37.6\pm 6.5$	$45.7\pm 6.5$	$45.6\pm 6.7$	$-0.1\pm 0.5$
CiteSeer	2	$41.8\pm 5.7$	$48.6\pm 6.7$	$48.4\pm 6.7$	$-0.1\pm 0.4$
CiteSeer	3	$49.7\pm 5.5$	$54.8\pm 3.9$	$54.8\pm 4.0$	$-0.0\pm 0.3$
CiteSeer	4	$53.4\pm 2.7$	$58.7\pm 3.4$	$58.9\pm 3.3$	$+0.3\pm 0.4$
CiteSeer	5	$58.9\pm 3.2$	$62.1\pm 2.3$	$61.8\pm 2.3$	$-0.3\pm 0.2$
PubMed	1	$56.4\pm 5.3$	$56.1\pm 4.5$	$56.3\pm 4.6$	$+0.1\pm 0.2$

Table 7. CiteSeer and PubMed, one to five labels per class: GAT baseline and label-space diffusion on the GAT-refined graph with the classical and the fractional kernel, mean

\pm

95\%

t

-interval over

10

splits, and the matched per-split difference between the kernels. PubMed propagators are applied by a Chebyshev expansion of degree

64

Dataset	$t$	$\epsilon$	Published	Our reproduction	Difference
Cora	$3.5$	$10^{-4}$	$83.7$	$83.58\pm 0.16$	$-0.12$
CiteSeer	$4.5$	$10^{-5}$	$72.5$	$72.81\pm 0.29$	$+0.31$

Table 8. Reproduction of GraphHeat on the standard public split with the diffusion time

t

and threshold

\epsilon

of [ 17 ] ; mean

\pm

95% CI over 10 initialization seeds, on the two graphs for which the exact kernel fits in memory.

$s$	Retained fraction of $n^{2}$	Mean neighbours	Median	Maximum
$1.00$	$0.099$	$269$	$254$	$1353$
$0.75$	$0.216$	$586$	$575$	$2333$
$0.50$	$0.544$	$1472$	$1656$	$2485$
$0.30$	$0.781$	$2114$	$2446$	$2485$

Table 9. Sparsity of

\mathcal{T}_{\epsilon}(e^{-tL^{s}})

on Cora at

t=3.5

and

\epsilon=10^{-4}

, the tuned GraphHeat setting, with

L=I-D^{-1/2}AD^{-1/2}

formed without self-loops.

Labels/class	GraphHeat ( $s{=}1$ )	Tuned exponent	$\Delta$ (95% CI)	Holm $p$
1	$49.13$	$50.58$	$+1.45\pm 0.84$	$0.007$
2	$60.42$	$61.07$	$+0.65\pm 0.63$	$0.174$
3	$68.04$	$68.32$	$+0.28\pm 0.61$	$1.000$
4	$69.41$	$69.49$	$+0.08\pm 0.23$	$1.000$
5	$73.76$	$73.87$	$+0.11\pm 0.30$	$1.000$

Table 10. Operator isolation on Cora at the common diffusion time

t=3.5

and a matched sparsity budget of

269

stored entries per node,

30

random splits. The tuned arm selects the exponent on validation data;

\Delta

is the matched per-split difference against the classical exponent.

$s$	$k{=}1$	$k{=}2$	$k{=}3$	$k{=}4$	$k{=}5$
$0.30$	$-23.04$	$-26.23$	$-26.39$	$-27.63$	$-22.97$
$0.50$	$-6.85$	$-10.40$	$-9.71$	$-10.30$	$-8.57$
$0.75$	$-0.56$	$-1.97$	$-1.26$	$-1.66$	$-1.62$
$1.00$	$0$	$0$	$0$	$0$	$0$
$1.25$	$-2.23$	$-0.97$	$-0.54$	$-0.41$	$+0.05$

Table 11. Accuracy of GraphHeat with matched sparsity at each fixed exponent

s

minus its accuracy at

s=1

(the classical column of Table 10 ), matched per split; Cora, common diffusion time

t=3.5

30

splits. Negative entries are losses relative to the classical kernel.

	$k{=}1$	$k{=}4$
$s=0.30$	$-18.54\pm 3.14$	$-29.72\pm 2.19$
$s=0.50$	$-13.81\pm 2.86$	$-22.59\pm 2.00$
$s=0.75$	$-6.42\pm 2.02$	$-7.92\pm 0.99$
$s=1.25$	$+0.73\pm 2.14$	$-1.08\pm 0.91$
Tuned on validation	$+2.42\pm 1.18$	$+0.16\pm 0.41$

Table 12. Matched per-split difference against the classical exponent on Cora when each order receives the diffusion time

t_{s}=t_{1}\lambda_{+}^{1-s}

, with

t_{1}=3.5

and

\lambda_{+}=4.78\times 10^{-3}

the smallest positive eigenvalue of the Laplacian used in this experiment,

30

splits. The last row is the tuned arm, which selects the exponent on validation data.

Dataset	Convention	$\dim\ker$	$\lambda_{\max}$	$\rho_{0}$	$\rho_{(0,1)}$	$\rho_{=1}$	$\rho_{>1}$
Cora	$A$	$78$	$2.000$	$0.216$	$0.646$	$0.021$	$0.118$
Cora	$A+I$	$78$	$1.483$	$0.224$	$0.705$	$0.003$	$0.068$
CiteSeer	$A$	$390$	$2.000$	$0.383$	$0.408$	$0.056$	$0.153$
CiteSeer	$A+I$	$438$	$1.502$	$0.407$	$0.490$	$0.029$	$0.074$
PubMed	$A$	$1$	$1.986$	$0.254$	$0.408$	$0.181$	$0.157$
PubMed	$A+I$	$1$	$1.654$	$0.287$	$0.619$	$0.008$	$0.086$

Table 13. Complete one-hot label energy of

L_{\mathrm{sym}}

relative to the fixed point

\lambda=1

\rho_{0}

is the null-space share, unaffected by

s

, and

\rho_{>1}

the share that an order below one retains more strongly than the classical kernel. Both self-loop conventions are shown since the convention moves

\lambda_{\max}

. The column

\dim\ker

equals the number of components only when every degree is positive: CiteSeer’s

48

isolated vertices contribute the eigenvalue one, not zero, without self-loops. Cora and CiteSeer use the exact eigendecomposition; the PubMed values are approximate polynomial estimates, and its

\rho_{=1}

entries are the transition-band energy around one for the reported half-width

10^{-3}

$s$	Single pass	$\Delta$ vs. $s{=}1$	Self- training	$\Delta$ vs. single pass	Splits with promotion	Promoted nodes	$\mathrm{OSI}_{h}$ / share $t{=}\infty$
$0.30$	$71.1\pm 3.2$	$-0.9\pm 0.5$	$71.1\pm 3.2$	$0$	$0/10$	$0$	$0.01$ / $0.00$
$0.50$	$71.5\pm 3.1$	$-0.5\pm 0.4$	$71.5\pm 3.1$	$0$	$0/10$	$0$	$0.02$ / $0.20$
$0.75$	$71.8\pm 3.0$	$-0.2\pm 0.2$	$71.8\pm 3.0$	$0$	$0/10$	$0$	$0.02$ / $0.50$
$1.00$	$72.0\pm 2.9$	$0$	$72.0\pm 2.9$	$0$	$0/10$	$0$	$0.02$ / $0.60$
$1.25$	$72.0\pm 2.8$	$-0.0\pm 0.4$	$72.1\pm 2.4$	$+0.1\pm 0.6$	$2/10$	$9$	$0.02$ / $0.80$

Table 14 . Sensitivity to the order

s

on Cora at

4

labels per class,

10

splits, label-space diffusion on the GAT-refined graph (the pipeline of Table 6 ). Single pass is the fixed compatible source; self-training is Algorithm 1 with the threshold schedule of Section 6.2.1 .

\Delta

are matched per-split differences with

95\%

t

-intervals.

\mathrm{OSI}_{h}

is the over-smoothing index of the homogeneous part

e^{-tL^{s}}Y_{0}

at the selected

t

, bounded by

e^{-t\lambda_{+}^{s}}

(Proposition 5.7 ); the last column is the share of splits in which validation selected

t=\infty

Dataset	Homophily $H$	GAT	Fractional ( $s^{\star}$ )	$s^{\star}$
Chameleon	$0.23$	$37.3\pm 1.5$	$33.1\pm 1.7$	$0.50$
Squirrel	$0.22$	$24.8\pm 1.0$	$23.2\pm 0.8$	$1.00$
Texas	$0.06$	$48.4\pm 4.5$	$32.5\pm 6.4$	$0.30$
Wisconsin	$0.18$	$42.2\pm 4.2$	$33.5\pm 4.0$	$0.30$

Table 15. Heterophily benchmarks at

k=5

labels per class with edge homophily

H

; label-space diffusion on the original graph. Accuracy is the mean

\pm

normal-approximation

95\%

interval over

10

splits with

\min(200,n/4)

validation and

n/3

test nodes (Texas

45/61

, Wisconsin

62/83

, Chameleon

200/759

, Squirrel

200/1733

); the GAT is trained for

150

epochs.

s^{\star}

maximizes mean test accuracy over the tested grid; the displayed intervals are unadjusted for this selection.

Method	0%	5%	10%	20%	40%
GAT baseline	70.6 $\pm$ 2.7	66.9 $\pm$ 3.1	66.9 $\pm$ 2.0	58.1 $\pm$ 2.9	48.3 $\pm$ 4.5
Label-FHK, original graph	60.0 $\pm$ 3.2	53.0 $\pm$ 3.2	46.9 $\pm$ 2.7	37.5 $\pm$ 3.4	25.5 $\pm$ 3.0
Label-FHK, GAT-refined graph	68.3 $\pm$ 2.8	65.4 $\pm$ 2.7	64.1 $\pm$ 2.5	57.2 $\pm$ 2.5	47.2 $\pm$ 3.2
Neural FHK++, original graph	70.1 $\pm$ 1.7	66.1 $\pm$ 3.5	65.1 $\pm$ 2.3	58.1 $\pm$ 2.4	47.9 $\pm$ 3.5
Neural FHK++, GAT-refined graph	69.0 $\pm$ 2.2	67.5 $\pm$ 2.2	65.3 $\pm$ 1.9	58.1 $\pm$ 2.8	49.1 $\pm$ 3.3
Neural FHK++, refined + residual	68.0 $\pm$ 2.5	64.9 $\pm$ 2.8	64.5 $\pm$ 2.0	56.2 $\pm$ 3.2	47.0 $\pm$ 3.8

Table 16 . Robustness to random edge rewiring on Cora at

4

labels per class; mean

\pm

normal-approximation

95\%

interval over

10

random splits. “Refined” is the GAT-refined graph and “Label-FHK, GAT-refined graph” the pipeline of Table 6 ; “residual” applies the decoder to

Z_{T}+Z_{0}

and

\kappa

is the validation-selected source strength (Section 5.7 ). These runs use an earlier version of the protocol, before the componentwise source, the

t=\infty

grid point and the GAT training length of Section 6.2.1 , so the GAT baseline differs slightly from Table 6 .

Classical graph-based methods
Method	Type	Total labels	Reported test accuracy
Label Propagation [ 3 ]	Classical	$140$	$68.0\%$
DeepWalk [ 48 ]	Classical	$140$	$67.2\%$
Manifold Regularization [ 29 ]	Classical	$140$	$59.5\%$
Graph neural networks
GCN [ 26 ]	GNN	$140$	$81.5\%$

Table 17. Representative published results on Cora under the standard

20

-labels-per-class setting, together with the controlled result of the best Neural FHK++ source-driven variant. Literature values are contextual reference points, not controlled comparisons. The values for Label Propagation, DeepWalk and Manifold Regularization are those reported in [ 26 ] , taken in turn from [ 47 ] .

Dataset	$1$ label/class	$2$ labels/class	$5$ labels/class	$10$ labels/class	$20$ labels/class
Cora	$54.94\pm 16.09$	$66.92\pm 10.04$	$77.80\pm 4.46$	$80.86\pm 2.99$	$82.95\pm 1.37$
CiteSeer	$58.95\pm 9.59$	$64.98\pm 8.31$	$70.03\pm 3.63$	$72.34\pm 2.42$	$73.53\pm 3.31$
PubMed	$65.94\pm 4.87$	$69.31\pm 4.87$	$71.99\pm 1.91$	$75.13\pm 3.88$	$79.16\pm 1.37$

Table 18. Published GRAND++ low-label results of Thorpe et al. [ 19 ] , in percent, included as literature references only; they were not obtained under the splits, preprocessing or validation protocol of this paper.

Explore similar work

Apr 22, 2026cs.LG

F\textsuperscript{2}LP-AP: Fast & Flexible Label Propagation with Adaptive Propagation Kernel

Semi-supervised node classification is a foundational task in graph machine learning, yet state-of-the-art Graph Neural Networks (GNNs) are hindered by significant computational overhead and reliance on strong homophily assumptions. Traditional GNNs require expensive iterative training and multi-layer message passing, while existing training-free methods, such as Label Propagation, lack adaptability to heterophilo-us graph structures. This paper presents \textbf{F

^2

LP-AP} (Fast and Flexible Label Propagation with Adaptive Propagation Kernel), a training-free, computationally efficient framework that adapts to local graph topology. Our method constructs robust class prototypes via the geometric median and dynamically adjusts propagation parameters based on the Local Clustering Coefficient (LCC), enabling effective modeling of both homophilous and heterophilous graphs without gradient-based training. Extensive experiments across diverse benchmark datasets demonstrate that \textbf{F

^2

LP-AP} achieves competitive or superior accuracy compared to trained GNNs, while significantly outperforming existing baselines in computational efficiency.

Yutong Shen, Ruizhe Xia, Jingyi Liu +1

Beijing University of Technology

Graph-Based Semi-Supervised Learning Semi-Supervised Learning Node Classification Graph Heterophily

Ask PDF

May 27, 2026cs.LG

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

Node classification on graphs often requires labeled nodes, yet obtaining labels at graph scale is expensive. When node attributes contain semantic content, such as paper abstracts, web pages, or product descriptions, large language models (LLMs) can provide low-cost supervision by annotating a small subset of nodes. However, these LLM-generated labels are noisy, and existing label-free graph learning methods usually treat this noise as either global or class-conditional. We find that LLM annotation errors are not only class-dependent but also region-dependent: within the same class, reliability can vary sharply across feature-space clusters. In light of this, we propose Cluster-Aware Noise Estimation (CANE), a label-free learning framework that estimates cluster-conditional LLM reliability without ground truth labels, and uses this estimate to decide which pseudo-labels to trust, and which labels to correct. Across various graph benchmarks and GNN backbones, CANE improves over the strongest label-free baselines, with the largest gains on datasets exhibiting stronger cluster-conditional noise.

Safal Thapaliya, Jiatan Huang, Chuxu Zhang

University of Connecticut, USA

LLM-Assisted Annotation Text-Attributed Graph Learning Noisy-Label Learning Classification Learning with Noisy Labels Node Classification+1

Ask PDF

Sep 28, 2026cs.LG

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

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.

Preben Johnsen Bentdal, Nello Blaser, Xue-Cheng Tai

Department of Informatics, University of Bergen · Norwegian Research Centre (NORCE)

Graph-Based Semi-Supervised Learning Classification Node Classification Graph Diffusion

Ask PDF