Unsupervised Graph Representation Learning with Complementary View Alignment

Technische Samenvatting: Unsupervised Graph Representation Learning met Complementary View Alignment (ALIGNGAE)

Probleemstelling
Unsupervised Graph Representation Learning (UGRL) beoogt betekenisvolle node-embeddings af te leiden door zowel structurele als attributieve informatie te vangen zonder gelabelde data. Hoewel bestaande methoden, met name Graph Autoencoders (GAEs) en masked graph autoencoders (bijv. MaskGAE, GraphMAE), effectiviteit hebben getoond, vertrouwen ze doorgaans op message-passing mechanismen die uitgaan van homofilie (verbonden nodes delen vergelijkbare attributen). Deze mechanismen fungeren als low-pass filters in het spectrale domein, waardoor hoogfrequente componenten worden onderdrukt. Als gevolg hiervan lijden deze methoden aan prestatievermindering op heterofiele grafen, waarbij verbonden nodes dissimilaire kenmerken vertonen. Het verlies van hoogfrequente componenten verhindert de effectieve identificatie van heterofiele patronen, wat leidt tot spectrale incompletheid en suboptimale representaties.

Methodologie: ALIGNGAE
Om de spectrale beperkingen van traditionele benaderingen aan te pakken, stellen de auteurs ALIGNGAE (Aligning Graph Autoencoder) voor, een nieuw framework dat MaskGAE uitbreidt via complementary view alignment om het volledige frequentiespectrum te behouden. De methodologie is gebaseerd op spectrale decompositie en de Neighborhood Identity Distribution (NID) theorie.

1. Dual-Encoder Architectuur:

   • Neighborhood View (Structureel): Verwerkt de graaf met behulp van een twee-laagse Graph Convolutional Network (GCN) met leerbare skip-connections op een gemaskeerde adjacency matrix. Deze view fungeert als een low-pass filter, die laagfrequente (homofiele) signalen en structurele afhankelijkheden vastlegt.
   • Node View (Attributief): Verwerkt node-attributen en positionele embeddings met behulp van een niet-convolutionele Multi-Layer Perceptron (MLP). Deze view vermijdt de smoothing-effecten van graph convoluties, waardoor hoogfrequente (heterofiele) signalen en variaties in attributen behouden blijven.
   • Positionele Embeddings: Afgeleid van random walks en getraind via een Skip-gram model, deze embeddings benaderen de NID, vangen de globale topologische context en de inconsistenties in kenmerken die essentieel zijn voor heterofiele grafen.

2. Dual Reconstruction Taken:

   • Edge Reconstruction: Voorspelt gemaskeerde edges met behulp van een decoder die structurele en positionele embeddings integreert om de graaf-topologie te reconstrueren.
   • Node Attribute Reconstruction: Reconstrueert geconcateneerde node-features en positionele embeddings met behulp van de node view embeddings, wat zorgt voor het behoud van hoogfrequente detailinformatie van de attributen.

3. NID Alignment Strategie:

   • Om semantische consistentie tussen de structurele en de attributieve views te waarborgen terwijl hun onderscheidende kenmerken behouden blijven, stemt ALIGNGAE hun Neighborhood Identity Distributions (NIDs) op elkaar af.
   • De NID vertegenwoordigt de waarschijnlijkheidsverdeling van pairwise feature-afstanden binnen de buurt van een node. Homofiele nodes vertonen scherpe NID-pieken nabij nul, terwijl heterofiele nodes bredere, multimodale distributies laten zien.
   • Het framework gebruikt alignment losses (KL Divergentie, Wasserstein Afstand, of Contrastive Alignment) om de discrepantie tussen de NIDs van de twee views te minimaliseren, waardoor wordt gewaarborgd dat de geleerde representaties consistente distributies delen zonder view-specifieke informatie te verliezen.

4. Theoretische Fundering:

   • De auteurs stellen vast dat wanneer de alignment loss convergeert, het model een maximale wederzijdse informatie tussen de views bereikt, identieke NID-distributies heeft en het volledige frequentiespectrum vangt (Theorem 2). Dit garandeert theoretisch de preservatie van zowel laagfrequente als hoogfrequente signalen.

Belangrijkste Bijdragen

• Theoretische Verbinding: Het artikel legt een theoretische link tussen spectrale decompositie en de kwaliteit van representaties, waarbij NID wordt geïdentificeerd als een cruciale brug voor het afstemmen van homofiele en heterofiele representaties.
• Nieuw Framework: Het introduceert ALIGNGAE, dat gemaskeerde graph autoencoders uitbreidt door dual-view spectrale alignment te incorporeren. Dit stelt het model in staat om zowel homofiele als heterofiele patronen simultaan te vangen zonder taakspecifieke aanpassingen.
• Uitgebreide Validatie: Het werk biedt uitgebreide experimentele validatie over diverse graafstructuren, waarbij wordt aangetoond dat het voorgestelde view alignment paradigma de beperkingen van traditionele message-passing methoden overwint.

Experimentele Resultaten
De auteurs evalueerden ALIGNGAE op 12 benchmark datasets, gecategoriseerd in homofiele (bijv. Cora, Citeseer, CS, Physics) en heterofiele (bijv. Cornell, Wisconsin, Texas, Chameleon, Squirrel) grafen.

• Heterofiele Grafen: ALIGNGAE presteert significant beter dan state-of-the-art methoden. Op de Texas dataset verbeterde het de nauwkeurigheid van node-classificatie met maar liefst 18,7% (specifiek genoteerd als een verbetering van 23,52% ten opzichte van MaskGAE in de resultaten sectie). Het overtrof consequent baselines zoals DeepWalk, DGI, GRACE en MaskGAE op alle heterofiele datasets.
• Homofiele Grafen: Het model behield een concurrerend niveau van prestaties op homofiele grafen, met een verbetering van tot wel 1,94% ten opzichte van de beste baselines op datasets zoals Cora en Citeseer.
• Ablatie Studies: Experimenten bevestigden dat het verwijderen van edge reconstructie ($L_{edge}$) de prestaties op heterofiele grafen verslechterde, terwijl het verwijderen van node reconstructie ($L_{node}$) de homofiele prestaties schaadde. De alignment loss ($L_{align}$) bleek essentieel voor de coherentie van de embeddings.
• Vergelijking van Alignment Loss: De studie vond dat de Wasserstein afstand ($L_W$) het beste presteerde op heterofiele grafen met complexe distributionele mismatches, terwijl KL divergentie ($L_{KL}$) uitblonk op homofiele grafen.

Betekenis en Claims
Het artikel claimt dat ALIGNGAE een nieuw paradigma vestigt voor frequency-aware graph representation learning. Door expliciet de "low-pass filter" bias van bestaande message-passing methoden aan te pakken, lost ALIGNGAE het probleem van spectrale incompletheid op. De auteurs stellen dat hun aanpak robuust leren mogelijk maakt over diverse graafstructuren, met name in uitdagende heterofiele settings waar traditionele methoden falen om nodes met dissimilar attributen te onderscheiden. Het werk demonstreert dat het behoud van het volledige frequentiespectrum door middel van complementary view alignment cruciaal is voor het vooruithelpen van unsupervised graph learning voorbij de beperkingen van homofilie-aannames.