UiT the Arctic University of Norway · & CNRS, France · & NORCE Norwegian Research Centre
We propose the Tikhonov layer, a graph neural network layer that is interpretable by design: once trained, its learned parameters directly reveal which node features and which aspects of the graph topology were leveraged for prediction. In practice, the layer's propagation matrix takes the closed-form
R=(p(L)+Q)−1Q, where
L is the normalized graph Laplacian,
Q=diag(q1,...,qn) a learnable diagonal matrix of positive node-importance scores, and
p(⋅) a learnable polynomial. For any input feature
x, the layer output
Rx is the exact minimizer of a generalized graph Tikhonov problem that trades off node-level data fidelity against a topology-driven regularization penalty. The learned pair
{{qi},p} constitutes a built-in explanation: large
qi indicates that node
i's own features drive the prediction, while small
qi signals reliance on the local graph topology; the shape of
p reveals whether homophily, heterophily, or a band-pass response is exploited. Expressivity is preserved by routing complexity through a dedicated, arbitrarily deep Q-network that produces the importance scores, while the Tikhonov layer itself remains transparent. We prove that distinct node-importance matrices yield distinct propagation operators, structurally coupling the explanation to the computation. Additionally, the Tikhonov layer provides, in a single layer, a global receptive field, mitigating both oversmoothing and oversquashing. Experiments on standard graph classification benchmarks confirm that the model matches (and sometimes outperforms) opaque baselines while producing interpretable and faithful explanations.