Conditional Distribution Learning for Graph Classification

Deze paper introduceert Conditional Distribution Learning (CDL), een end-to-end methode voor semigekleurd grafiekclassificatie die intrinsieke semantische informatie behoudt door de conditionele verdelingen van zwak en sterk versterkte grafieken te aligneren, terwijl het het conflict tussen het berichtdoorgeefmechanisme van GNN's en contrastief leren van negatieve paren oplost door alleen positieve paren te gebruiken.

De kern

De Kunst van het Leren van Grafen: Een Verhaal over CDL

Stel je voor dat je een enorme verzameling sociale netwerken, moleculaire structuren of verkeerskaarten hebt. In de wereld van kunstmatige intelligentie noemen we deze "grafieken". Het probleem is: we hebben maar heel weinig mensen die kunnen vertellen wat deze kaarten betekenen (bijvoorbeeld: "dit is een gevaarlijk molecuul" of "dit is een spam-netwerk"). We hebben duizenden ongemerkte kaarten, maar slechts een handvol met labels.

Hoe leer je een computer om deze kaarten te begrijpen zonder dat je duizenden experts nodig hebt? Dat is waar dit paper over gaat. De auteurs, Chen, Mao, Liu, Wang en Peng, hebben een nieuwe methode bedacht die ze SSCDL noemen (Self-Supervised Conditional Distribution Learning).

Laten we dit uitleggen met een paar alledaagse analogieën.

1. Het Probleem: De "Verwarde" Leraar en de "Vervormde" Foto's

Om een computer slim te maken, gebruiken we vaak een soort digitale leraar die heet een GNN (Graph Neural Network). Deze leraar leert door informatie uit de buurt van een punt te halen (zoals een buurman die je vertelt wat er in de straat gebeurt).

Maar er zijn twee grote struikelblokken:

• Het Conflict van de Leraar: De digitale leraar is zo goed in het samenvoegen van informatie dat hij op het einde van de les alle leerlingen (de punten in de grafiek) precies hetzelfde laat klinken. Ze worden allemaal "grijze muisjes". Maar om slim te zijn, wil de computer juist leren wat het verschil is tussen een goed en een slecht voorbeeld. Het is alsof je een leraar vraagt om leerlingen te leren onderscheiden, maar de leraar zorgt er per ongeluk voor dat ze er allemaal hetzelfde uitzien.
• De Gevaarlijke Foto's: Om de computer beter te maken, geven we hem "oefeningen" met verstoorde foto's (data-augmentatie). We maken een foto een beetje wazig of veranderen de kleur.
  • Zachte verstoring: Een beetje ruis. De computer leert hier goed van.
  • Harde verstoring: We knippen de foto in stukken of vegen de helft weg. Hierdoor verdwijnt de betekenis van de foto. De computer leert dan iets dat helemaal niet klopt.

De oude methoden probeerden dit op te lossen door de computer te dwingen om te zeggen: "Deze twee foto's zijn hetzelfde" (positieve paren) en "Deze twee zijn verschillend" (negatieve paren). Maar door de "grijze muisjes"-probleem van de leraar, raakte de computer in de war.

2. De Oplossing: De "Twee-Oogjes" Methode (CDL)

De auteurs hebben een slimme oplossing bedacht, alsof je een detective bent die twee soorten sporen volgt:

Stap 1: De "Zachte" en "Harde" Oefeningen
Ze maken twee versies van elke grafiek:

1. Een zacht aangepaste versie (een beetje ruis, alsof je een foto een beetje verwazigt).
2. Een hard aangepaste versie (veel ruis, alsof je de foto flink beschadigt).

Stap 2: De "Voorwaartse" Leerling (Conditional Distribution)
In plaats van de computer te dwingen om te zeggen "deze twee zijn verschillend" (wat de leraar in de war brengt), zeggen ze:
"Als je de originele foto ziet, wat is de kans dat je deze zachte versie ziet? En wat is de kans dat je deze harde versie ziet?"

Ze dwingen de computer om te leren dat de harde versie (die veel ruis heeft) nog steeds dezelfde essentie moet hebben als de zachte versie, zolang ze maar beide zijn gebaseerd op de originele foto.

• De Analogie: Stel je voor dat je een recept hebt (de originele grafiek).
  • De zachte versie is het recept met een klein beetje extra peper.
  • De harde versie is het recept waarbij je 50% van de ingrediënten hebt weggelaten.
  • De oude methode zei: "Vergelijk het recept met en zonder peper."
  • De nieuwe methode (CDL) zegt: "Als ik het originele recept zie, moet je kunnen voorspellen dat het recept met 50% ingrediënten er nog steeds op lijkt als het recept met een beetje peper, omdat ze beide van hetzelfde origineel komen."
  • Hierdoor leert de computer de ware betekenis van het recept, zelfs als de helft van de ingrediënten weg is.

Stap 3: Het Oplossen van het Conflict
Door alleen te kijken naar de relatie tussen de originele foto en de zachte versie (en niet de harde versie die te veel ruis heeft), vermijden ze het probleem dat de leraar alle leerlingen gelijk maakt. Ze houden de "positieve paren" (origineel vs. zacht) intact, maar negeren de "negatieve paren" die de computer in de war brengen.

3. De Twee-Fase Training (Pre-training & Fine-tuning)

De methode werkt in twee stappen, net als het leren van een instrument:

1. De Oefenronde (Pre-training): De computer krijgt duizenden ongemerkte grafieken. Hij oefent alleen met de "zachte" en "harde" versies om te leren wat de echte betekenis is, zonder dat iemand hem vertelt wat het juiste antwoord is. Hij bouwt zo een sterke basis op.
2. De Finale (Fine-tuning): Nu krijgen ze een paar grafieken met labels (het antwoord). De computer past zijn kennis aan om de specifieke vragen te beantwoorden. Omdat hij al zo'n sterke basis heeft, heeft hij maar heel weinig voorbeelden nodig om perfect te worden.

Waarom is dit geweldig?

• Het werkt met weinig data: Je hebt niet duizenden experts nodig, want de computer leert zichzelf eerst slim.
• Het is robuust: Zelfs als je de data flink beschadigt (harde augmentatie), blijft de computer de kernboodschap begrijpen.
• Geen conflicten: Het lost het probleem op waarbij de computer alle dingen gelijk maakt in plaats van ze te onderscheiden.

Kortom:
De auteurs hebben een slimme manier bedacht om computers te leren grafieken te begrijpen, zelfs als we maar weinig voorbeelden hebben en de data soms erg beschadigd is. Ze gebruiken een soort "twee-oogjes" strategie: kijken naar wat er overblijft van een beschadigde foto, in vergelijking met een licht beschadigde foto, om de ware betekenis te onthullen. De resultaten tonen aan dat deze methode beter werkt dan de huidige beste methoden op allerlei gebieden, van chemie tot sociale netwerken.

Technische samenvatting

Titel: Conditional Distribution Learning voor Graph Classificatie (SSCDL)

1. Het Probleem

Graph Contrastive Learning (GCL) heeft veelbelovende resultaten geleverd voor semigebaseerde graph-classificatie, maar er zijn twee fundamentele beperkingen die de prestaties beperken:

• Conflict tussen Message-Passing en Contrastive Learning: In Graph Neural Networks (GNN's) hebben opeenvolgende lagen de neiging om node-embeddings steeds meer op elkaar te laten lijken (door het message-passing mechanisme). GCL probeert echter juist de dissimilariteit (ongelijkheid) tussen negatieve paren van node-embeddings te maximaliseren. Dit creëert een inherent conflict: GNN's maken embeddings vergelijkbaar, terwijl contrastive learning ze juist van elkaar moet onderscheiden.
• Behoud van Semantische Informatie bij Data Augmentatie: Het is uitdagend om de diversiteit en hoeveelheid van graph-gebaseerde data-augmentaties (zoals knooppunten verwijderen of attributen maskeren) te benutten zonder de intrinsieke semantische informatie van de graph te verstoren. Sterke augmentaties kunnen de structuur zodanig beschadigen dat het model geen bruikbare features meer leert.

2. Methodologie: SSCDL (Self-Supervised Conditional Distribution Learning)

De auteurs stellen een nieuwe methode voor, genaamd SSCDL, die een end-to-end model gebruikt om graph-representaties te leren. De aanpak bestaat uit de volgende kerncomponenten:

• Framework: Het model bestaat uit drie modules:

  1. Een gedeelde GNN-encoder (bijv. GCN) die graph-level representaties leert van de originele data, een zwak versterkte weergave (weak augmentation) en een sterk versterkte weergave (strong augmentation).
  2. Een projectie-head (MLP) voor contrastive learning.
  3. Een module voor het construeren van conditionele verdelingen.

• Conditionele Verdelingsleer (CDL):

  • In plaats van direct contrastive learning toe te passen op alle paren, aligneren ze de conditionele verdelingen van de zwak en sterk versterkte features over de originele features.
  • De verdeling $p(h^w_i | h_i)$ (zwak versterkt gegeven origineel) wordt gebruikt om $p(h^s_i | h_i)$ (sterk versterkt gegeven origineel) te superviseren.
  • Door de divergentie tussen deze twee verdelingen te minimaliseren (via een verliesfunctie $L_d$), zorgt het model ervoor dat zelfs bij sterke augmentatie de intrinsieke semantische informatie behouden blijft.

• Oplossing voor het GNN-Conflict:

  • Om het conflict tussen message-passing en contrastive learning van negatieve paren op te lossen, worden alleen positieve paren gebruikt voor het meten van gelijkenis tussen de originele features en de zwak versterkte features.
  • Negatieve paren worden niet direct gebruikt in de contrastive loss voor deze specifieke vergelijking, wat voorkomt dat het message-passing mechanisme wordt ondermijnd.

• Semigebaseerd Leerplan (Pretraining & Fine-tuning):

  1. Pretraining-fase: Gebruikt ongelabelde data. Het model traint met een verliesfunctie ($L_s$) die de consistentie tussen originele en zwak versterkte weergaven maximaliseert (via een lower bound van wederzijdse informatie).
  2. Fine-tuning-fase: Gebruikt een klein aantal gelabelde data. Het model combineert de cross-entropy loss voor classificatie ($L_c$) met de conditionele verdelingsloss ($L_d$) en de similarity loss ($L_s$). De totale loss is: $L = L_c + \alpha L_s + \beta L_d$.

3. Belangrijkste Bijdragen

• End-to-End Model: Een nieuw model dat zowel zwakke als sterke augmentaties van graph-data benut voor semigebaseerde classificatie.
• Conditionele Verdelingsleer: Introductie van CDL om de consistentie van conditionele verdelingen van versterkte node-embeddings ten opzichte van de originele embeddings te karakteriseren. Dit lost het probleem op van semantische vervorming bij sterke augmentaties.
• Conflictreductie: Een nieuwe similariteitsverliesfunctie die het potentiële conflict tussen het message-passing mechanisme van GNN's en contrastive learning van negatieve paren vermindert.
• Semigebaseerd Systeem: Een effectief trainingskader met pretraining en fine-tuning dat werkt met beperkte gelabelde data.

4. Resultaten

De auteurs hebben hun methode getest op acht benchmark datasets (o.a. MUTAG, PROTEINS, IMDB-B, COLLAB, GITHUB) met label-ratio's van 30%, 50% en 70%.

• Prestaties: De SSCDL-methode overtreft consistent state-of-the-art methoden zoals GCL, GLIA, G-Mixup, GCMAE en GRDL.
  • Bijvoorbeeld, op de MUTAG dataset met 30% gelabelde data, behaalde SSCDL een nauwkeurigheid van 89.36%, vergeleken met 87.25% voor de tweede beste methode (GLIA).
  • De prestaties blijven superieur bij hogere label-ratio's (50% en 70%).
• Ablatie-studie: Experimenten tonen aan dat zowel de pretraining-fase als de conditionele verdelingscomponent ($L_d$) essentieel zijn voor de hoge prestaties. Zonder pretraining of zonder de conditionele verdeling daalt de nauwkeurigheid aanzienlijk.
• Robuustheid: De methode is robuust tegenover variaties in de maskeringsratio van knooppunten, hoewel te sterke augmentatie (ratio > 0.35) de prestaties doet dalen door verlies van structuurinformatie.

5. Betekenis en Impact

Dit paper biedt een significante doorbraak in het veld van graph representation learning door twee fundamentele problemen in GCL aan te pakken:

1. Het biedt een theoretisch onderbouwde oplossing voor het conflict tussen GNN-message-passing en contrastive learning, wat de stabiliteit van het trainingsproces verbetert.
2. Het introduceert een strategie om data-augmentatie effectiever te maken zonder de semantische integriteit van de graph te verliezen.

Dit maakt SSCDL bijzonder waardevol voor toepassingen waar gelabelde data schaars is (zoals in chemie, sociale netwerken en verkeersstromen), omdat het modellen in staat stelt om beter te generaliseren vanuit een beperkt aantal gelabelde voorbeelden.