Graph Homomorphism Distortion: A Metric to Distinguish Them All and in the Latent Space Bind Them

Dit artikel introduceert de 'graph homomorphism distortion', een nieuwe metrische maatstaf die zowel grafestructuur als knoopkenmerken combineert om de expressiviteit van graf-neurale netwerken te verbeteren en de vergelijkbaarheid van grafen nauwkeuriger te beoordelen.

De kern

Titel: De "Vergelijkings-Regel" voor Netwerken: Hoe je twee lijnen kunt meten die er anders uitzien

Stel je voor dat je twee enorme, ingewikkelde netwerken hebt. Denk aan een stadsplaat met wegen en gebouwen, of aan een sociaal netwerk met vrienden en hun interesses. In de wereld van kunstmatige intelligentie (AI) proberen computers deze netwerken te begrijpen. Maar hier zit een groot probleem: hoe vertel je een computer of twee netwerken "hetzelfde" zijn, of juist heel verschillend?

Tot nu toe gebruikten computers een heel strakke, maar breekbare regel: "Zijn ze exact hetzelfde?"
Als je één weg verplaatst of één gebouw verandert, zeggen de oude regels: "Nee, dit is een heel ander netwerk!" Dit is als het vergelijken van twee mensen op basis van hun vingerafdrukken: als er één lijntje anders is, zijn het twee verschillende mensen. Maar in de echte wereld zijn netwerken vaak bijna hetzelfde, met kleine verschillen die misschien niet zo belangrijk zijn.

De auteurs van dit paper hebben een nieuwe manier bedacht om netwerken te vergelijken. Ze noemen het "Graph Homomorphism Distortion" (een lange naam voor een slim idee). Laten we het uitleggen met een paar creatieve analogieën.

1. Het oude probleem: De "Perfecte Spiegel"

Stel je voor dat je twee spiegels hebt. De oude methode (die ze Weisfeiler-Leman noemen) kijkt alleen of de spiegels exact hetzelfde beeld geven.

• Als je in de ene spiegel een rode bal ziet en in de andere een blauwe bal, zegt de computer: "Verschil!"
• Als je in de ene spiegel een bal hebt en in de andere twee ballen, zegt de computer: "Verschil!"
• Het probleem: Het kan geen kleine verschillen meten. Het zegt alleen "Ja" of "Nee". Het is alsof je probeert te meten hoe ver twee mensen van elkaar vandaan staan, maar je mag alleen zeggen "Ze staan op dezelfde plek" of "Ze staan niet op dezelfde plek".

2. De nieuwe oplossing: De "Reis met een Buigzame Regel"

De auteurs introduceren een nieuwe maatstaf. Stel je voor dat je twee netwerken hebt, Netwerk A en Netwerk B.
Je probeert nu niet om ze exact op elkaar te laten lijken. In plaats daarvan vraag je je af: "Hoeveel moet ik rekken, buigen of veranderen aan de eigenschappen van Netwerk A om het op Netwerk B te laten lijken?"

Dit is de Distortion (vervorming).

• De Analogie van de Klei:
  Stel je hebt een sculptuur van klei (Netwerk A) en een andere sculptuur (Netwerk B).
  • De oude methode zegt: "Zijn ze identiek?" Nee? Dan zijn ze totaal verschillend.
  • De nieuwe methode zegt: "Hoeveel moet ik de klei van A rekken en duwen om hem op B te laten lijken?"
  • Als je maar een klein beetje hoeft te rekken, zijn ze zeer vergelijkbaar.
  • Als je de hele sculptuur uit elkaar moet halen en opnieuw moet vormen, zijn ze heel verschillend.

Deze "rekking" wordt gemeten aan de hand van de eigenschappen van de punten in het netwerk (bijvoorbeeld: hoe populair is een persoon in een sociaal netwerk, of hoe groot is een stad in een stadsplaat).

3. Waarom is dit zo slim?

A. Het ziet de "kleine" verschillen
Stel je twee vriendengroepen voor. In groep A heeft iedereen 5 vrienden. In groep B heeft iedereen ook 5 vrienden, maar één persoon heeft er 6.

• De oude methode ziet dit als een totaal ander verhaal.
• De nieuwe methode zegt: "Oh, ze zijn bijna hetzelfde, alleen dat ene puntje is ietsje 'vervormd'." Dit helpt computers om netwerken te begrijpen die in de echte wereld vaak niet 100% perfect zijn.

B. Het werkt als een "Richtingwijzer" voor AI
De auteurs tonen aan dat je deze "vervormings-maatstaf" kunt gebruiken om AI-modellen slimmer te maken.

• Voorbeeld: Stel je voor dat je een AI traint om medicijnen te vinden (die vaak worden voorgesteld als netwerken van atomen).
• Als je de AI vertelt: "Kijk niet alleen of de atomen precies op dezelfde plek zitten, maar meet ook hoe 'vervormd' de structuur is als je ze vergelijkt," dan leert de AI veel sneller en beter. Het wordt een betere "inductieve bias" (een slimme aanname die de AI helpt).

4. Wat hebben ze bewezen?

De auteurs hebben wiskundig bewezen dat:

1. Het werkt: Je kunt hiermee netwerken die niet exact hetzelfde zijn, toch goed van elkaar onderscheiden.
2. Het completer is: Het doet alles wat de oude methoden deden, maar dan veel fijner en gedetailleerder.
3. Het praktisch is: Ze hebben een manier bedacht om dit snel te berekenen, zelfs voor grote netwerken, door te "kijken" naar kleinere, bekende netwerken (als referentiepunten).

Samenvatting in één zin

In plaats van te vragen "Zijn deze twee netwerken exact hetzelfde?", vraagt deze nieuwe methode: "Hoeveel moeite kost het om het ene netwerk in het andere te veranderen?" Hierdoor kunnen computers netwerken veel menselijker en nauwkeuriger begrijpen, zelfs als ze niet 100% identiek zijn.

Het is alsof je van een "ja/nee"-vraag overgaat naar een "hoeveel?"-vraag, waardoor de AI veel meer nuance kan zien in de complexe wereld van netwerken.

Technische samenvatting

Probleemstelling

Het leren van grafen (graph learning) wordt sterk beïnvloed door de wisselwerking tussen de structuur van een graf en de kenmerken (features) van de knopen. Bestaande methoden om de expressiviteit van Graph Neural Networks (GNN's) te analyseren, zoals de Weisfeiler-Leman (WL) hiërarchie, hebben echter twee fundamentele beperkingen:

1. Binair karakter: De WL-test levert een binair resultaat (isomorf of niet-isomorf). Dit maakt het onmogelijk om "kleine verschillen" tussen grafen te meten of te beoordelen in hoeverre twee grafen met vergelijkbare kenmerken als gelijk moeten worden beschouwd.
2. Structuur-gerichtheid: Bestaande maatstaven negeren vaak de knopenkenmerken en focussen uitsluitend op de topologische structuur. Zelfs bij uitbreidingen naar geometrische grafen wordt vaak geen rekening gehouden met benaderende (geometrische) gelijkenis.

Er is behoefte aan een maatstaf die zowel structuur als kenmerken integreert en een continue, fijner opgesplitste maatstaf van gelijkenis biedt, in plaats van een binair ja/nee.

Methodologie: Graph Homomorphism Distortion

De auteurs introduceren een nieuwe (pseudo-)metriek genaamd Graph Homomorphism Distortion (GHD). Deze is geïnspireerd op de Gromov-Hausdorff-afstand uit de metriek-geometrie, maar toegepast op de context van grafen met knopenkenmerken.

Kernconcepten:

• Homomorfisme: Een functie die knopen van graf $G$ naar graf $G'$ afbeeldt zodat de connectiviteit behouden blijft.
• Attribuutvervorming (Attribute Distortion): Voor een homomorfisme $\phi: G \to G'$ wordt de vervorming gedefinieerd als de maximale norm van het verschil tussen de kenmerken van een knoop $v$ en de kenmerken van zijn afbeelding $\phi(v)$ in de andere graf.
  $$\text{dis}(\phi) := \max_{v \in V} \|f(v) - f'(\phi(v))\|$$
• GHD-definitie: De Graph Homomorphism Distortion $d_{HD}(G, G')$ tussen twee grafen is het maximum van de infimum van de vervorming in beide richtingen (van $G$ naar $G'$ en vice versa). Als er geen homomorfismen bestaan, wordt de afstand oneindig.
  $$d_{HD}(G, G') := \max \left( \inf_{\phi \in \text{Hom}(G, G')} \text{dis}(\phi), \inf_{\phi' \in \text{Hom}(G', G)} \text{dis}(\phi') \right)$$

Theoretische Eigenschappen:

• Pseudo-metriek: $d_{HD}$ voldoet aan de eigenschappen van een metriek (niet-negativiteit, symmetrie, driehoeksongelijkheid), maar is een pseudo-metriek omdat $d_{HD}(G, G') = 0$ niet noodzakelijk impliceert dat $G$ en $G'$ identiek zijn (ze kunnen isomorf zijn).
• Volledigheid (Completeness): Onder bepaalde voorwaarden (injectiviteit en permutatie-invariantie van de kenmerkfuncties) is $d_{HD}$ een volledige metriek: $d_{HD}(G, G') = 0$ dan en slechts dan als $G$ en $G'$ isomorf zijn.
• Lipschitz-continuïteit: De metriek is continu ten opzichte van veranderingen in de kenmerkfuncties.

Berekenbaarheid en Encoding:
Omdat het tellen van homomorfismen NP-volledig is, stellen de auteurs een benadering voor. Ze gebruiken een familie van "proxy-grafen" $\mathcal{F}$ (bijv. bomen of cycli met beperkte boombreedte) om de afstand te schatten via een HD-encoding $\Gamma(G)_{\mathcal{F}}$. Dit is een vector van afstanden van $G$ naar elke graf in $\mathcal{F}$. Door stochastisch te bemonsteren (Expectation-Completeness) kunnen ze een efficiënte, complete encoding creëren die in de latent space van GNN's kan worden gebruikt.

Belangrijkste Bijdragen

1. Nieuwe Metriek: Introductie van de Graph Homomorphism Distortion als een maatstaf voor gelijkenis die zowel structuur als knopenkenmerken combineert en een continue afstand biedt.
2. Theoretische Fundamenten: Bewijzen dat de metriek isomorfisme kan onderscheiden, permutatie-invariant is, en completer is dan de WL-test. Ze tonen aan dat de door de GHD geïnduceerde topologie fijner is dan die van de WL-test.
3. Structurale Encoding: Ontwikkeling van een nieuwe inductieve bias voor GNN's gebaseerd op de GHD-encoding. Deze encoding kan worden gecombineerd met bestaande homomorfismetellingen.
4. Efficiënte Benadering: Een praktische methode om de onberekenbare exacte afstand te benaderen via stochastisch bemonsteren van homomorfismen naar een beperkte familie van grafen.

Resultaten

De auteurs valideren hun methode op twee fronten:

1. Discriminatiekracht (Niet-lerende scenario's):

• Dataset: BREC-dataset (Benchmarks for Graph Expressivity), specifiek gericht op het onderscheiden van moeilijk te onderscheiden niet-isomorfe grafen (zoals CFI-grafen en regular graphs).
• Vergelijking: De GHD-methode presteert aanzienlijk beter dan de 1-WL en 3-WL tests.
• Prestaties: De methode bereikte een onderscheidingspercentage van 100% op de moeilijkste klassen (zoals klasse D en 4), terwijl de 3-WL test daar faalde (0% of zeer laag). Zelfs vergeleken met geavanceerde methoden zoals persistente homologie (PH), behaalde GHD de beste of vergelijkbare resultaten.
• Invloed van Kenmerken: De resultaten tonen aan dat de keuze van de knopenkenmerken (bijv. Shortest Path Encodings vs. Random Walk Positional Encodings) en de keuze van de proxy-familie $\mathcal{F}$ (bomen vs. cycli) de discriminatiekracht sterk beïnvloeden.

2. Lerende Scenario's (GNN Prestaties):

• Dataset: ZINC-12K (graf-regressie taak).
• Setup: De GHD-encoding werd gebruikt als extra input (inductieve bias) voor GAT, GCN en GIN modellen.
• Resultaten:
  • Het gebruik van de GHD-encoding alleen verbeterde de prestaties (gemiddelde absolute fout, MAE) ten opzichte van basismodellen en modellen die alleen homomorfismetellingen gebruiken.
  • De beste resultaten werden behaald door de GHD-encoding te combineren met traditionele homomorfismetellingen (Hom) of subgraftellingen (Sub).
  • Bijvoorbeeld, voor het GIN-model daalde de MAE van 0.246 (base) naar 0.138 wanneer de GHD-encoding gecombineerd werd met subgraftellingen.

Betekenis en Impact

Dit werk biedt een paradigmaverschuiving in het analyseren van de expressiviteit van grafen.

• Van Binair naar Continu: Het verlegt de focus van het binair onderscheiden van grafen (isomorf/niet) naar het kwantificeren van de graad van verschil, wat essentieel is voor real-world toepassingen waar grafen zelden exact identiek zijn.
• Integratie van Structuur en Kenmerken: Het lost het probleem op dat bestaande theorieën (zoals WL) kenmerken negeren, door een maatstaf te bieden die inherent afhankelijk is van zowel topologie als knopenattributen.
• Praktische Toepasbaarheid: Door de theorie te vertalen naar een berekenbare encoding, bieden de auteurs een direct bruikbaar hulpmiddel om GNN's krachtiger te maken, zonder de theoretische garanties van volledigheid op te geven.

Kortom, de Graph Homomorphism Distortion is een krachtig nieuw instrument dat de theoretische grenzen van grafvergelijking uitbreidt en direct leidt tot verbeterde prestaties in machine learning taken.