Technische Samenvatting: Onzekerheidsschatting voor Heterofiele Grafen door de Lens van Informatietheorie

Probleemstelling

Onzekerheidsschatting voor Graph Neural Networks (GNN's) heeft aanzienlijke aandacht getrokken, maar de meeste bestaande methoden vertrouwen sterk op de aanname van homofiele connecties—de neiging van knopen om verbinding te maken met andere knopen van dezelfde klasse. Deze methoden maken vaak gebruik van grafdiffusie of gladmakende kernen om onzekerheid te propageren, wat effectief is wanneer semantisch vergelijkbare knopen met elkaar verbonden zijn. Echter, in heterofiele situaties, waarbij knopen voornamelijk verbinding maken met buren van verschillende klassen, verslechteren deze benaderingen. De afhankelijkheid van gladmaking om (on)zekerheid te propageren is minder gerechtvaardigd in heterofiele grafen, wat leidt tot slechte prestaties bij detectie van out-of-distribution (O.O.D.) en kwantificering van onzekerheid. Bovendien is er in eerdere werken geen systematisch onderzoek gedaan naar hoe onzekerheidsschatters zich gedragen wanneer homofiele-aannames worden geschonden, noch is er een specifieke aanpak voor heterofiele grafen die expliciete exploitatie van homofiele vermijdt.

Methodologie

De auteurs benaderen het probleem vanuit een informatietheoretisch perspectief, waarbij ze Message Passing Neural Networks (MPNN's) analyseren om te begrijpen hoe latente knooprepresentaties evolueren door de lagen heen.

1. Informatietheoretische Analyse van MPNN's

Geïnspireerd door het Information Bottleneck-principe (Tishby & Zaslavsky, 2015), modelleren de auteurs de informatiestroom in MPNN's. In tegenstelling tot standaard neurale netwerken voor onafhankelijke en identiek verdeelde (i.i.d.) data, waarbij de Data Processing Inequality (DPI) voorschrijft dat informatie over een doelvariabele alleen kan afnemen of constant kan blijven door de lagen heen, leiden de auteurs een Data Processing Equality (DPE) af voor MPNN's.

Belangrijke theoretische inzichten zijn:

• Informatieherstel en -winst: In MPNN's is informatie over de label $Y$ van een knoop niet uitsluitend bevat in de eigen kenmerken van de knoop, maar is deze verdeeld over de ego-graf. De auteurs definiëren een ego-graf $G_v$ die is opgedeeld in disjuncte verzamelingen $G_v^{(i)}$ op basis van hop-afstand.
• De Gelijkheid: De wederzijdse informatie $I(Y; Z^{(i+1)})$ die wordt vastgehouden door een representatie op laag $i+1$, decomposeert additief:
  $$I(Y; Z^{(i+1)}) = I(Y; Z^{(i)}) - \Delta_{(-)}^{(0:i)} + \Delta_{(+)}^{(i+1)}$$
  Hier vertegenwoordigt $\Delta_{(-)}^{(0:i)}$ informatieverlies (of -herstel) met betrekking tot de bestaande ego-graf, en vertegenwoordigt $\Delta_{(+)}^{(i+1)}$ de informatiewinst van de nieuwe $i+1$-hop buren.
• Heterofiele versus Homofiele:
  • In homofiele grafen delen aangrenzende knopen vergelijkbare semantiek. Bijgevolg neemt de informatiewinst $\Delta_{(+)}^{(i+1)}$ af naarmate de diepte toeneemt, omdat diepere lagen geen nieuwe semantische informatie over het doel bieden.
  • In heterofiele grafen vertonen aangrenzende knopen verschillende semantiek. De informatiewinst $\Delta_{(+)}^{(i+1)}$ kan groot en positief zijn, wat betekent dat diepere latente embeddings unieke en onderscheidende informatie bevatten over de data-distributie die vlakkere embeddings missen.

2. Gezamenlijke Latente Dichtheidsschatting (JLDE)

Gebaseerd op de bevinding dat heterofiele grafen vereisen dat alle knooprepresentaties gezamenlijk worden beschouwd om de volledige data-distributie te vangen, stellen de auteurs Joint Latent Density Estimation (JLDE) voor.

• Mechanisme: In plaats van dichtheid te schatten vanuit een enkele laatste laag (zoals gebruikelijk is in i.i.d. situaties) of grafdiffusie te gebruiken, concateneert JLDE de latente embeddings van alle lagen van de MPNN ($Z^{(0)}, Z^{(1)}, \dots, Z^{(L)}$).
• Implementatie: Een eenvoudige post-hoc K-Nearest Neighbors (KNN) dichtheidsschatter wordt toegepast op deze geconcateneerde gezamenlijke embeddingsruimte. De epistemische onzekerheid $u_{epi}(v)$ wordt berekend als de negatieve log-likelihood van de gezamenlijke representatie van de knoop binnen de trainingsdistributie.
• Ontwerpprincipe: Deze aanpak exploiteert homofiele niet expliciet via post-processing (bijvoorbeeld gladmaking) en is toepasbaar op elke MPNN-backbone.

Belangrijkste Bijdragen

1. Theoretisch Kader: Het artikel leidt een nieuw analogon van de Data Processing Inequality af voor MPNN's, en bewijst dat informatie kan toenemen met de modeldiepte in heterofiele situaties vanwege de unieke semantische informatie die buren op verschillende afstanden bieden.
2. Informatie-gebaseerde Homofiele Definitie: De auteurs introduceren een definitie van homofiele die is geworteld in wederzijdse informatie, en onderscheid maken tussen gedeelde informatie die relevant is voor het doellabel en irrelevante ruis.
3. JLDE-methode: Zij stellen Joint Latent Density Estimation voor, een eenvoudig post-hoc ontwerpprincipe dat alle latente representaties gezamenlijk modelleert. Deze methode is de eerste die expliciet gericht is op kwantificering van onzekerheid in heterofiele grafen zonder te vertrouwen op homofiele-aannames.
4. Empirische Validatie: De methode wordt geëvalueerd over meerdere datasets, distributieverplaatsingen en backbone-architecturen, waarbij state-of-the-art prestaties worden aangetoond.

Experimentele Resultaten

De auteurs evalueren JLDE op zes datasets (vier heterofiele: Amazon Ratings, Roman Empire, Chameleon, Squirrel; twee homofiele: CoraML, PubMed) onder drie soorten distributieverplaatsingen: Leave-Out-Class (LoC), Near Feature Perturbations en Far Feature Perturbations.

• Heterofiele Prestaties: Op heterofiele datasets behaalt JLDE consistent state-of-the-art epistemische onzekerheid (gemeten door O.O.D. detectie AUC-ROC en AUC-PR). Het presteert significant beter dan methoden die vertrouwen op grafdiffusie (bijvoorbeeld GPN, GEBM) of standaard ensemble-methoden, vooral in scenario's waar informatie uit diepere lagen cruciaal is.
• Homofiele Prestaties: Op homofiele datasets presteert JLDE concurrerend met andere model-agnostische schatters en komt het overeen met de prestaties van methoden die expliciet zijn ontworpen voor homofiele, ondanks het niet gebruiken van homofiele-exploiterende post-processing.
• Ablatiestudies: Experimenten bevestigen dat voor heterofiele grafen het gebruik van alleen de laatste laag of het middelen van dichtheden per laag inferieure resultaten oplevert in vergelijking met de gezamenlijke concatenatie van alle lagen. Omgekeerd presteert de gezamenlijke aanpak op homofiele grafen even goed als het gebruik van alleen de laatste laag, wat de theorie valideert dat diepere lagen in die situaties geen nieuwe informatie toevoegen.
• Backbone-agnostisch: De methode wordt post-hoc toegepast op diverse backbones (Res-GCN, Res-GAT-Sep, Res-GATE, GPRGNN), en scoort consequent als de beste of tweede beste schatter over verschillende architecturen.

Betekenis en Claims

Het artikel claimt de theoretische onderbouwing te bieden voor de vooruitgang van onzekerheidsschatting op grafen voorbij de homofiele-aanname. Door te onthullen dat in heterofiele grafen elke embeddingslaag unieke informatie biedt over de data-distributie, stellen de auteurs een belangrijk ontwerpprincipe vast: onzekerheidsschatting moet alle knooprepresentaties gezamenlijk beschouwen.

De auteurs benadrukken dat hun werk:

• Een gat in de literatuur adresseert waar geen eerdere werken heterofiele grafen expliciet targetten voor kwantificering van onzekerheid.
• Aantoont dat bestaande schatters vaak falen wanneer homofiele-aannames worden geschonden.
• Een eenvoudige, effectieve en model-agnostische oplossing (JLDE) biedt die state-of-the-art resultaten behaalt zonder complexe architecturale wijzigingen of expliciete homofiele-exploitatie te vereisen.
• Bijdraagt aan de ontwikkeling van betrouwbare en vertrouwenswaardige AI, met name in hoog-risico domeinen waar het begrijpen van modelonzekerheid in niet-homofiele data cruciaal is.

De auteurs blijven bescheiden wat betreft de reikwijdte, en merken op dat hoewel JLDE de epistemische onzekerheid verbetert, het inherent geen verbetering biedt voor aleatorische onzekerheid of modelkalibratie, wat orthogonale richtingen blijven voor toekomstig werk. Zij veronderstellen ook dat geavanceerdere dichtheidsmodellen hun eenvoudige KNN-gebaseerde realisatie verder kunnen verbeteren.