TACENR: Task-Agnostic Contrastive Explanations for Node Representations

Probleemstelling

Graph Representation Learning (GRL) heeft aanzienlijke successen geboekt door graf-structuren te coderen in latente vectorruimtes voor taken zoals knoopclassificatie en linkpredictie. Echter, deze knooprepresentaties blijven vaak een "black box": ze zijn moeilijk te interpreteren.
Bestaande uitlegmethoden (Explainable AI) hebben twee belangrijke beperkingen:

1. Taak-specifiek: Ze focussen voornamelijk op het verklaren van voorspellingen voor specifieke downstream-taken (bijv. waarom werd deze knoop als 'spam' geclassificeerd?), in plaats van de representatie zelf te verklaren.
2. Dimensie-specifiek: Bestaande methoden voor het interpreteren van representaties focussen vaak op individuele dimensies van de vector, in plaats van de representatie als geheel te analyseren.

Knooprepresentaties coderen echter drie soorten informatie:

• Proximiteit: Naburige knopen hebben vergelijkbare representaties.
• Structurele gelijkenis: Knoopjes met vergelijkbare structurele rollen delen representaties.
• Attribuut-gelijkenis: Knoopjes met vergelijkbare eigenschappen staan dicht bij elkaar.
  Bestaande methoden slagen er vaak niet in om al deze drie aspecten gelijktijdig te vangen.

Methodologie: TACENR

De auteurs stellen TACENR (Task-Agnostic Contrastive Explanations for Node Representations) voor. Dit is een lokale uitlegmethode die de gehele knooprepresentatie verklaart door bij te dragen aan de positie van de knoop in de representatieruimte.

Kerncomponenten:

1. Kenmerkverrijking: Voor elke knoop $v$ worden drie soorten kenmerken geïntegreerd:

   • Attributen: De oorspronkelijke input-kenmerken ($x_v$).
   • Structurele kenmerken: Functies die de rol in de graf beschrijven (bijv. graad, gemiddelde graad van buren, clusteringcoëfficiënt, driehoekentelling).
   • Proximitietskenmerken: Maatstaven voor connectiviteit (bijv. kortste padafstand, Personalized PageRank).
     Deze worden samengevoegd tot een vector $h_{v,u}$ voor een paar knopen $(v, u)$.

2. Contrastief Leren:
   TACENR leert een uitlegmodel $g$ dat de gelijkenis in de representatieruimte voorspelt op basis van de input-kenmerken.

   • Voor een doelknoop $v$ worden twee sets gedefinieerd:
     • Affiniteitsset ($S^+_v$): De $k$ knopen met de meest vergelijkbare representaties.
     • Divergentieset ($S^-_v$): De $k$ knopen met de minst vergelijkbare representaties.
   • Het doel is om een model te trainen dat de werkelijke gelijkenis $\text{sim}(z_v, z_u)$ zo goed mogelijk voorspelt op basis van de kenmerken $h_{v,u}$. Dit gebeurt door de fout (bijv. MSE) te minimaliseren tussen de voorspelde en werkelijke gelijkenis.

3. Gewogen Gelijkheidsmaatstaf:
   Om de interpretatie te verbeteren, wordt een gewogen variant van de cosinusgelijkheid gebruikt. De gewichten $w_j$ worden aangepast aan het type representatie:

   • Supervised (Bewaakt): Gewichten worden bepaald door de gradienten van de voorspelde klasse (gradient-based weighting). Dimensies die sterk correleren met de voorspelling krijgen meer gewicht.
   • Unsupervised (Onbewaakt): Gewichten worden gebaseerd op de globale variantie van elke dimensie. Dimensies met hoge variantie (meer onderscheidend vermogen) krijgen meer gewicht.

4. Interpretable Surrogaatmodel:
   Het model $g$ dat de gelijkenis voorspelt, is een interpretable model (standaard Lineaire Regressie). De coëfficiënten van dit model geven direct aan welke kenmerken (proximiteit, structuur, attributen) het meest bijdragen aan de representatie van de knoop.

Belangrijkste Bijdragen

• Task-Agnostic Explainer: TACENR is de eerste methode die de volledige knooprepresentatie verklaart, onafhankelijk van een specifieke downstream-taak.
• Holistische Analyse: Het integreert simultaan attributen, structurele kenmerken en proximitie, in plaats van zich te beperken tot één type relatie.
• Contrastief Framework: Het introduceert een contrastief leerproces met een aangepaste gewogen gelijksheidsfunctie die zowel voor bewaakte als onbewaakte scenario's werkt.
• Uitgebreide Evaluatie: De methode is getest op diverse datasets (Cora, CiteSeer, PubMed, PPI, BA-Shapes) en modellen (node2vec, role2vec, GCN, GAT, GraphSAGE).

Resultaten

De experimenten tonen de volgende inzichten:

1. Invloed van Kenmerken: Proximitie, structurele kenmerken en attributen dragen allemaal bij aan de representaties, maar hun relatieve belangrijkheid varieert per algoritme.
   • Bij node2vec (random walks) is proximiteit (zoals PPR) zeer belangrijk.
   • Bij GNN's (GCN, GAT, GraphSAGE) zijn lokale structurele kenmerken (zoals gemiddelde graad van buren en clusteringcoëfficiënt) dominant, wat overeenkomt met hun aggregatiemechanisme.
2. Synthetische Data (BA-Shapes): TACENR slaagt erin om de fundamentele structurele regels van het model te onthullen. Het onderscheidt duidelijk tussen knopen in "house-motieven" (lokaal gestructureerd) en knopen in de schaalvrije basis (globale rol), waarbij het de juiste kenmerken (bijv. driehoeken voor motieven, PPR voor hubs) identificeert.
3. Vergelijking met State-of-the-Art:
   • In een bewaakte setting presteert de TACENR-variant (met alleen attributen als input) vergelijkbaar met of beter dan bestaande taak-specifieke methoden (zoals GNNExplainer, GraphLIME) op de AOPC-metriek (Area Over the Perturbation Curve).
   • TACENR is beter in het filteren van ruis: het wijst minder vaak onbelangrijke (ruis)kenmerken toe als belangrijk in vergelijking met andere methoden.
4. Ablatie-studie:
   • Het gebruik van gewogen gelijksheid verbetert de kwaliteit van de uitleg aanzienlijk, vooral in bewaakte settings.
   • De samenstelling van de contrastieve sets is cruciaal: voor bewaakte embeddings werkt een set met veel vergelijkbare knopen (80% affiniteit) het beste, terwijl voor onbewaakte embeddings een set met veel verschillende knopen (80% divergentie) nodig is om voldoende contrast te bieden.
   • Simpele Lineaire Regressie bleek vaak even goed of beter dan complexere modellen (Ridge, Lasso, HSIC Lasso), wat de transparantie van de methode ten goede komt.

Betekenis en Conclusie

TACENR vult een kritieke leemte in het veld van Explainable AI voor grafen. Het verschuift de focus van het verklaren van voorspellingen naar het begrijpen van de representaties zelf. Dit stelt onderzoekers en practitioners in staat om te begrijpen waarom een model bepaalde knopen dicht bij elkaar plaatst in de vectorruimte, ongeacht of het model voor classificatie, clustering of linkpredictie wordt gebruikt.

De methode biedt een robuust raamwerk om te analyseren hoe verschillende algoritmen (van traditionele random walks tot moderne GNN's) informatie uit de grafstructuur en attributen integreren. Dit is essentieel voor het vertrouwen in AI-systemen in domeinen zoals bio-informatica (proteïne-interacties) en sociale netwerkanalyse, waar de interpretatie van de onderliggende relaties net zo belangrijk is als de voorspelling zelf.