Technische Samenvatting: Een Gegeneraliseerde Tikhonov-laag voor naar Ontwerp Interpreteerbare Graph Neural Networks

Probleemstelling

Graph Neural Networks (GNN's) hebben aanzienlijk succes behaald in graf- en knoopclassificatietaken door te leren kenmerken te aggregeren over graf-topologie. Hun interpreteerbaarheid blijft echter een kritieke uitdaging. In tegenstelling tot klassieke neurale netwerken moeten GNN's niet alleen uitleggen hoe invoerkenmerken worden getransformeerd, maar ook hoe de graf-topologie zelf wordt benut. Bestaande methoden voor interpreteerbaarheid vertrouwen vaak op post-hoc benaderingen (bijvoorbeeld GNNExplainer, gradient saliency) die geen garanties voor trouw bieden, of op twee-module architecturen waarbij een verklaringsextractor losgekoppeld is van de classifier, waardoor de classifier de verklaring kan negeren terwijl de verliesfunctie wordt geminimaliseerd. Bovendien lijden diepe GNN's aan pathologieën zoals oversmoothing (instorten van knooprepresentaties) en oversquashing (exponentiële afname van gevoeligheid voor lange afstanden).

Methodologie

De auteurs stellen de Tikhonov-laag voor, een graph neural network-laag die naar ontwerp interpreteerbaar is. De kerninnovatie ligt in het beperken van de graf-propagatiematrix $R$ tot een specifieke oplossing in gesloten vorm, afgeleid van een gegeneraliseerd graf-Tikhonov-regularisatieprobleem.

De Propagatie-operator

Voor een graf met genormaliseerde Laplaciaan $L$ wordt de laagoutput voor invoerkenmerken $X$ gegeven door:
$$X^{(k+1)} = \sigma \left( R X^{(k)} W \right)$$
waarbij de propagatiematrix $R$ wordt gedefinieerd als:
$$R = (p(L) + Q)^{-1} Q$$
Hierbij:

• $L$ is de genormaliseerde graf-Laplaciaan.
• $Q = \text{diag}(q_1, \dots, q_n)$ is een leerbare diagonaalmatrix van strikt positieve scores voor knoopbelang.
• $p(\cdot)$ is een leerbare polynoom die voldoet aan $0 < p(\lambda) < 1$ voor $\lambda \in [0, 2]$.
• $\sigma$ is een puntsgewijze niet-lineariteit en $W$ is een gewichtsmatrix.

Variationale Interpretatie

De operator $R$ is de unieke oplossing in gesloten vorm die het gegeneraliseerde Tikhonov-probleem minimaliseert:
$$R x = \arg \min_{z \in \mathbb{R}^n} \sum_{i \in V} q_i (x_i - z_i)^2 + z^\top p(L) z$$
Deze formulering wisselt expliciet knoopniveau-datafideliteit (gewogen met $q_i$) in tegen topologie-gedreven regularisatie (geleid door $p(L)$).

• Grote $q_i$: De knoop $i$ vertrouwt sterk op zijn eigen kenmerken; de output $z_i$ blijft dicht bij $x_i$.
• Kleine $q_i$: De knoop $i$ verwierpt zijn eigen kenmerken ten gunste van een oplossing die wordt gedreven door de graf-topologie (gladheid of specifieke spectrale eigenschappen zoals gedefinieerd door $p$).
• Vorm van $p(\lambda)$: Bepaalt de aard van de topologische invloed. Een toenemende $p$ straft hoge frequenties af (bevoordeelt homofylie/gladheid), terwijl een afnemende $p$ lage frequenties straft (bevoordeelt heterofylie).

Architectuur en Expressiviteit

Om hoge expressiviteit te behouden zonder interpreteerbaarheid op te offeren, hanteert de architectuur een scheiding van verantwoordelijkheden:

1. Het Q-Netwerk: Een dedicated, mogelijk diep GNN (bijvoorbeeld ChebNet of ARMA) dat de graf $(G, X)$ als invoer neemt en de knoopbelang-scores $Q$ output. Dit onderdeel behandelt complexe representatieve leerprocessen en past $q_i$ aan aan lokale grafstructuren en kenmerken.
2. De Tikhonov-laag: Een enkele, transparante laag die de propagatie $R$ toepast. Deze bevat geen verborgen niet-lineariteiten of complexe berichtuitwisselingsstappen; haar parameters zijn de polynoomcoëfficiënten van $p$ en de output van het Q-netwerk.
3. Kop: Een globale pooling-operatie gevolgd door een MLP voor de uiteindelijke voorspelling.

Het model ondersteunt meerkanaalsuitbreidingen waarbij meerdere onafhankelijke Q-netwerken en polynomen worden gebruikt, hoewel de experimenten zich richten op het enkelaalsgeval ($J=1$).

Implementatiedetails

• Berekening: Het berekenen van $(p(L) + Q)^{-1}QX$ houdt het oplossen van lineaire systemen in. De auteurs gebruiken Preconditioned Conjugate Gradient (PCG) met een diagonale (Jacobi) preconditioner om de $O(n^3)$-kosten van dichte inversie te vermijden, waardoor schaalbaarheid $O(dTKm)$ wordt bereikt, waarbij $T$ het aantal iteraties is.
• Differentiatie: Om het opslaan van het computationele graf van de solver te vermijden, gebruiken de auteurs impliciete differentiatie, waarbij slechts één extra PCG-oplossing in de terugwaartse pass nodig is om gradienten te berekenen met betrekking tot $Q$ en $p$.
• Beperkingen: De polynoom $p(\lambda)$ wordt geparametriseerd met Bernstein-polynomen met sigmoid-activaties om strikt $0 < p(\lambda) < 1$ af te dwingen. De scores $q_i$ worden via een log-ruimte clamping-functie gemapt naar strikt positieve waarden.

Belangrijkste Bijdragen en Theoretische Eigenschappen

1. Ingebouwde Interpreteerbaarheid: Het paar $\{ \{q_i\}_{i \in V}, p(\cdot) \}$ vormt een directe, trouwe verklaring. Grote $q_i$ duidt op afhankelijkheid van kenmerken; kleine $q_i$ duidt op afhankelijkheid van topologie. De vorm van $p$ onthult de spectrale bias (homofylie, heterofylie, band-pass).
2. Structurele Koppeling: De auteurs bewijzen (Propositie 3.6) dat de afbeelding $Q \mapsto R$ injectief is. In tegenstelling tot post-hoc methoden verandert het wijzigen van de verklaring ($Q$) noodzakelijkerwijs de propagatie-operator ($R$), waardoor wordt gegarandeerd dat de verklaring trouw is aan de berekening.
3. Expressiviteit: De laag blijkt dicht te zijn in de ruimte van continue spectrale filters in het homogene geval. Met heterogene $Q$ breidt hij de expressiviteit strikt uit boven traditionele spectrale filters door stationariteit te doorbreken (Propositie 3.3).
4. Mitigatie van GNN-pathologieën:
   • Oversmoothing: Wordt vermeden door het gebruik van één enkele laag en de omkeerbaarheid van $p(L) + Q$. Knoopinstorting treedt alleen op als het model bewust alle $q_i \to 0$ drijft.
   • Oversquashing: De vervalrate van gevoeligheid voor lange afstanden $|R_{ij}|$ wordt bepaald door de conditienummer $\kappa$ van het systeem, die afhangt van de geleerde $Q$. Het model kan leren $\kappa$ te verlagen (door specifieke $q_i$ te verlagen) om de gevoeligheid voor lange afstanden te verhogen waar nodig, effectief lokale precisie inruilend voor globaal bereik.

Experimentele Resultaten

Het model werd geëvalueerd op synthetische en standaard benchmarks, waarbij zowel prestaties als interpreteerbaarheid werden aangetoond:

• Gereguleerde Synthetische Taken:
  • Colors-3: De taak vertrouwt uitsluitend op knoopkenmerken. Het model leerde overal grote $q_i$, waardoor het de topologie effectief negeerde en zich gedroeg als een MLP, en correct identificeerde dat kenmerken de voorspelling drijven.
  • Clique Distance: Een puur structurele taak. Het model leerde kleine $q_i$ voor pad-knooppunten (vertrouwend op topologie om afstand te voelen) en grote $q_i$ voor clique-knooppunten (ankers), en behaalde 100% nauwkeurigheid.
  • Triangles: Een structurele taak voor het detecteren van driehoeken. Het model kende over het algemeen kleine $q_i$ toe, maar grotere $q_i$ aan driehoekse hoekpunten, en pinpointte het motief zonder toezicht.
• CSBM (Contextual Stochastic Block Model): Het model slaagde erin de theoretische fase-overgangsdrempel voor herstel nauwkeurig te volgen. De geleerde $q_i$-waarden gingen soepel over van kenmerk-gedomineerde (grote $q_i$) naar topologie-gedomineerde (kleine $q_i$) regimes, en identificeerden correct de bron van het signaal in gemengde regimes.
• ECHO-diam (Lange-afstandspropagatie): Op een graf-diameter-regressietaak behaalde het model een Mean Absolute Error (MAE) van 1,17, wat beter was dan diepe GNN-baselines (~1,6) en dicht bij de prestaties van Transformers kwam (1,05). De verklaring onthulde dat het model grote $q_i$ toekende aan perifere knopen (eindpunten) en kleine $q_i$ aan binnenste knopen, waarbij het gebruik maakte van het contrast tussen verankerde eindpunten en gegladde binnenkanten om de diameter te schatten.

Betekenis en Claims

Het artikel beweert dat de Tikhonov-laag een nieuwe aanpak biedt voor GNN-interpreteerbaarheid door de laag te ontwerpen om zelf-verklarend te zijn in plaats van verklaringen post-hoc te herstellen.

• Trouw: De verklaring is het model zelf; er is geen losgekoppeld subgraf of benadering.
• Granulariteit: Het biedt een continu, ruimtelijk opgelost antwoord (gegradeerde $q_i$-waarden) in plaats van een binaire subgraf-selectie.
• Prestaties: Het model komt overeen met of overtreft ondoorzichtige baselines (zoals GIN, GAT en Transformers) op diverse taken, terwijl het inzicht biedt in hoe de taak wordt opgelost (bijvoorbeeld het onderscheiden van op kenmerken gebaseerd versus op topologie gebaseerd redeneren).
• Beperkingen: De auteurs erkennen dat sommige verklaringen complex kunnen zijn voor mensen om te interpreteren en dat de rekenkosten van PCG hoog kunnen zijn voor taken die lange-afstandsinteracties vereisen (hoewel ze random numerieke lineaire algebra als toekomstige richting voor benadering suggereren).

Het werk stelt vast dat het mogelijk is om GNN-lagen te beperken tot specifieke variatievormen om interpreteerbaarheid te verkrijgen zonder het vermogen op te offeren om complexe, niet-stationaire graf-filters te leren.