Technische Samenvatting: Transductief Verscherpen van Grafen

Probleemstelling

In de transductieve setting voor knopclassificatie wordt de volledige graafstructuur en de knopkenmerken waargenomen tijdens het trainen, maar zijn labels alleen beschikbaar voor een subset van knopen ($V_L$). Hoewel Graph Neural Networks (GNN's) aanzienlijke vooruitgang hebben geboekt door architecturale innovaties (bijvoorbeeld message-passing-schema's, transformers), heeft het ontwerpen van trainingsdoelstellingen relatief minder aandacht gekregen. Standaard supervisie trainen minimaliseert de cross-entropy-verliesfunctie uitsluitend op gelabelde knopen, waarbij de voorspellingen die bij elke trainingsstap worden gegenereerd voor ongelabelde knopen ($V_U$) worden verworpen. Het artikel stelt dat deze voorspellingen voor ongelabelde knopen nuttige trainingsignalen bevatten die momenteel onderbenut worden, omdat standaard doelstellingen deze niet kunnen evalueren zonder grondwaarheid-labels.

Methodologie: Transductief Verscherpen (TS)

De auteurs stellen Transductief Verscherpen (TS) voor, een aanpassing op het niveau van de verliesfunctie die voorspellingen op ongelabelde knopen benut zonder architecturale wijzigingen te vereisen. De methode is gebaseerd op de decompositie van cross-entropy-verlies in een label-afhankelijke alignerterm en een label-onafhankelijke entropieterm.

Kernobjectief

Het TS-objectief breidt de standaard supervisie-verliesfunctie ($L_{sup}$) uit met termen die de onzekerheid (entropie) van voorspellingen over de graaf manipuleren:

$$L_{TS} = L_{sup} + \lambda \cdot \frac{1}{|V_U|} \sum_{v \in V_U} R(p_v) - \lambda \cdot \frac{1}{|V_L|} \sum_{v \in V_L} R(p_v)$$

Waarbij:

• $p_v$ de voorspellende waarschijnlijkheidsverdeling is voor knoop $v$.
• $R(p)$ een functie is die onzekerheid meet.
• $\lambda$ een scalair hyperparameter is die de sterkte van het verscherpen regelt.

Implementatiedetails

• Onzekerheidsfunctie ($R$): De auteurs kiezen voor Tsallis-entropie met $q=2$ (equivalent aan Gini-impureid, $S_2(p) = 1 - \sum p_i^2$) in plaats van Shannon-entropie. Deze keuze wordt gemotiveerd door de kwadratische vorm van Tsallis-entropie, die gradiënten oplevert die lineair zijn in $p$. Dit zorgt voor stabiele trainingsdynamiek en voorkomt te agressieve updates of degenererende one-hot-oplossingen die vaak geassocieerd worden met de logaritmische gradiënten van Shannon-entropie nabij de rand van het waarschijnlijkheidssimplex.
• Symmetrisch Mechanisme:
  • Op Ongelabelde Knopen ($V_U$): De term minimaliseert onzekerheid (maximaliseert vertrouwen), waardoor het model wordt aangemoedigd om zijn eigen betrouwbare voorspellingen als leersignaal te behandelen.
  • Op Gelabelde Knopen ($V_L$): De term maximaliseert onzekerheid (werkt oververtrouwen tegen), en fungeert als regularisator om overfitting op de trainingslabels te voorkomen.
• Hyperparameter: De methode introduceert één scalair hyperparameter, $\lambda$. De auteurs tonen aan dat een conservatieve, universele instelling van $\lambda = 0,25$ concurrerend presteert over diverse datasets en architecturen zonder per-dataset afstemming.

Belangrijkste Bijdragen

1. Introductie van Transductief Verscherpen (TS): Een eenvoudige, architectuur-onafhankelijke aanpassing van de verliesfunctie die voorspellingen op ongelabelde knopen omzet in directe trainingsignalen voor transductieve knopclassificatie.
2. Prestatie-Complexiteit Trade-off: TS verbetert standaard GNN (GCN, GraphSAGE, GAT) en MLP-baselines over 13 knopclassificatie-benchmarks, terwijl er slechts één hyperparameter wordt toegevoegd en geen wijzigingen in de backbone-architectuur nodig zijn.
3. Analyse van de Verscherpingscoëfficiënt ($\lambda$): De auteurs tonen aan dat TS effectief is over een reeks positieve $\lambda$-waarden. Zij identificeren dat matig verscherpen (bijvoorbeeld $\lambda \in [0, 0,5]$) de meest betrouwbare verbeteringen oplevert, terwijl excessief verscherpen het model kan dwingen zich te sterk te committeren aan onjuiste voorspellingen.
4. Mechanistisch Inzicht: Empirische analyse toont aan dat TS succesvol voorspellend vertrouwen herverdeelt naar ongelabelde knopen, waardoor een grotere entropiegap ontstaat tussen gelabelde en ongelabelde knopen in vergelijking met de supervisie-baseline.

Experimentele Resultaten

Het artikel evalueert TS over 13 datasets (waaronder Cora, CiteSeer, PubMed en diverse heterofiele grafen) met behulp van GCN, GraphSAGE, GAT en MLP backbones.

• Consistente Verbeteringen: TS verbetert consistent de prestaties van supervisie-baselines of komt deze gelijk. Bijvoorbeeld, op de Cora-dataset verbeterde de GCN-nauwkeurigheid van 84,54% naar 85,74% (+1,20), en de MLP-nauwkeurigheid verbeterde van 60,96% naar 64,48% (+3,52).
• MLP versus GNN: Hoewel TS MLP's verbetert (wat aantoont dat het signaal niet specifiek is voor grafische message passing), blijft de prestatie van MLP+TS onder die van GNN's, wat bevestigt dat TS de voordelen van message passing niet vervangt.
• Universele Hyperparameter: Een vaste $\lambda = 0,25$ toegepast over alle datasets en architecturen behoudt een groot deel van het voordeel van per-dataset afstemming en veroorzaakt zelden significante prestatieachteruitgang.
• Ablatiestudies:
  • Het verwijderen van de correctieterm voor gelabelde knopen (entropiemaximalisatie op $V_L$) verslechtert over het algemeen de prestaties, wat het belang benadrukt van het balanceren van verscherping op ongelabelde knopen met regularisatie op gelabelde knopen.
  • Asymmetrische configuraties (het verschuiven van $\lambda$) leveren geen systematische verbeteringen op ten opzichte van de symmetrische formulering.
  • Het dynamisch meta-leren van $\lambda$ tijdens het trainen presteert slechter dan het gebruik van een vaste, via validatie geselecteerde constante, wat suggereert dat de toegevoegde complexiteit instabiliteit introduceert.

Betekenis en Claims

Het artikel beweert dat Transductief Verscherpen een sterke prestatie-complexiteit trade-off biedt. Door het trainingsdoel te herzien in plaats van de architectuur, tonen de auteurs aan dat voorspellingen die doorgaans worden verworpen tijdens transductief leren (vanwege het ontbreken van labels) een nuttig en onderbenut signaal bieden.

De betekenis ligt in de eenvoud en generaliteit van de aanpak:

• Het vereist geen architecturale wijzigingen aan bestaande GNN-pijplijnen.
• Het voegt verwaarloosbare rekenkosten toe.
• Het biedt een algemene weg om leeralgoritmen in transductieve settings te verbeteren zonder de modelcomplexiteit te verhogen.

De auteurs concluderen dat hoewel hun werk zich richt op transductieve knopclassificatie, het principe van het benutten van ongelabelde voorspellingen via op vertrouwen gebaseerde doelstellingen kan worden uitgebreid naar andere settings, zoals linkpredictie of temporele knopclassificatie, en zo een lichtgewicht methode biedt om waarde te halen uit de volledige graafstructuur tijdens het trainen.