Technische Samenvatting: Contrastive FUSE

Probleemstelling

Het artikel behandelt de uitdaging om betekenisvolle knooprepresentaties te leren in grafen waar expliciete knoopkenmerken niet beschikbaar, onbetrouwbaar of niet-overdraagbaar zijn (kenmerkloze of kenmerk-sparse grafen). In tegenstelling tot standaard onbewaakte graf-embeddingsmethoden die uitsluitend vertrouwen op grafstructuur, of zelfbewaakte contrastieve leermethoden die afhankelijk zijn van dataversterkingen, richt dit werk zich op een setting waar supervisie alleen beschikbaar is in de vorm van partiele paarsgewijze constraints. Deze constraints geven aan of twee knopen vergelijkbaar moeten zijn (must-link) of verschillend (cannot-link), een scenario dat veel voorkomt in domeinen zoals computationele biologie (bijv. voorspelling van synthetische lethaliteit), aanbevelingssystemen (impliciete feedback) en privacygevoelige netwerken waar knoopattributen ontoegankelijk zijn.

Het doel is om een snel, schaalbaar kader te ontwikkelen dat discriminatieve knoopembeddings leert door gezamenlijke optimalisatie voor:

1. Structurele Coherentie: Behoud van de globale gemeenschapsstructuur van de graf.
2. Paarsgewijze Consistentie: Het naleven van de verstrekte getekende paarsgewijze constraints (het aantrekken van vergelijkbare paren, het afstoten van verschillende paren).

Methodologie: Contrastive FUSE

De auteurs stellen Contrastive FUSE voor, een unificerend kader dat structureel leren op basis van modulariteit integreert met contrastieve supervisie via een spectrale formulering.

1. Doelfunctie

De kern-doelfunctie $J(S)$ combineert een structurele term en een contrastieve term:
$$J(S) = \text{Tr}(S^\top \tilde{B}S) - \lambda \text{Tr}(S^\top L_c S)$$

• Structurele Term (Modulariteit): De eerste term maximaliseert modulariteit, waardoor knopen binnen dezelfde gemeenschap vergelijkbare embeddings krijgen. De auteurs gebruiken een gewijzigde modulariteitsmatrix $\tilde{B} = A - \frac{d\mathbf{1}^\top}{2m}$, waarbij $A$ de adjacentiematrix is, $d$ de gradenvector is, en $m$ het totale aantal randen.
• Contrastieve Term: De tweede term maakt gebruik van een getekende, genormaliseerde contrastieve Laplaciaan ($L_c$) die is opgebouwd uit de paarsgewijze supervisiematrix $Y$ (waarbij $Y_{ij} \in \{+1, -1, 0\}$). Deze term fungeert als een regularisator die positieve paren dichter bij elkaar trekt en negatieve paren uit elkaar duwt in de embeddruimte, genormaliseerd per de contrastieve graad van elke knoop om dominantie door sterk geconstraineerde knopen te voorkomen.

2. Efficiënte Optimalisatie via Gradientbenadering

Een belangrijke innovatie is de behandeling van de modulariteitsgradient. De exacte gradient van de modulariteitsdoelstelling bevat een correctieterm voor graad-graad ($d(d^\top S)$), wat computationeel duur en numeriek instabiel is voor grote, dichte grafen.

• Benadering: De auteurs stellen een lichtgewicht benadering voor door de gewogen graadaggregatie $d^\top S$ te vervangen door de ongewogen globale som $\mathbf{1}^\top S$.
• Theoretische Rechtvaardiging: Het artikel bewijst (Stelling 2) dat onder milde aannames met betrekking tot de verdeling van embeddings en de graadstructuur van de graf, de stijgingsrichting van de voorgestelde benaderde gradient nauw blijft aansluiten bij de exacte gradient (gebonden cosinus-similariteit). Dit zorgt voor aanzienlijke computationele besparingen terwijl het structuurzoekend gedrag van modulariteit behouden blijft.

3. Optimalisatie-algoritme

Het kader maakt gebruik van geprojecteerde gradientstijging:

1. Bereken de structurele gradient ($G_{mod} = \tilde{B}S$) en de contrastieve gradient ($G_{con} = -L_c S$).
2. Combineer gradienten: $G = G_{mod} + \lambda G_{con}$.
3. Update embeddings: $\tilde{S} = S + \eta G$.
4. Projectie: Handhaaf eenheidsnorm-beperkingen via genormaliseerde rijen ($S_i \leftarrow \tilde{S}_i / \|\tilde{S}_i\|_2$) om triviale schaaloplossingen te voorkomen.
5. Downstream Classificatie: De geleerde embeddings worden gebruikt als invoerfeatures voor een op GNN gebaseerde classifier (GCN, GAT of GraphSAGE) gevolgd door een MLP om paarsgewijze relaties te voorspellen.

Belangrijkste Bijdragen

1. Nieuwe Contrastieve Formulering: Introduceert een methode voor het leren van knooprepresentaties onder paarsgewijze supervisie die gelabelde knoop-paar constraints direct integreert in de embeddoelstelling zonder dat knoopkenmerken nodig zijn.
2. Getekende Genormaliseerde Contrastieve Laplaciaan: Stelt een specifieke Laplaciaan-operator voor die modulariteitsgebaseerd leren aanvult door gelijktijdig vergelijkbare paren aan te trekken en verschillende paren af te stoten op een genormaliseerde manier.
3. Schaalbaar Optimalisatieschema: Ontwikkelt een computationeel efficiënte benadering van de modulariteitsgradient die de overhead aanzienlijk verlaagt terwijl de theoretische uitlijning met de exacte doelstelling behouden blijft, waardoor training mogelijk is op grafen met miljoenen randen.

Experimentele Resultaten

De methode werd geëvalueerd op een diverse reeks benchmarks, waaronder citatienetwerken (Cora, CiteSeer, PubMed), co-aankoopgrafiek (Amazon Photo, WikiCS) en grote OGB-datasets (ArXiv, Products).

• Prestaties: Contrastive FUSE behaalde concurrerende of superieure downstream prestaties voor knoopclassificatie (Nauwkeurigheid en Macro-F1) vergeleken met state-of-the-art baselines, waaronder onbewaakte methoden (DeepWalk, Node2Vec), zelfbewaakte contrastieve methoden (DGI, GRACE, SGCL) en spectrale methoden (COLES).
• Schaalbaarheid en Efficiëntie: Het kader toonde aanzienlijke winst in runtime. Op datasets van middelgrote schaal was het aanzienlijk sneller dan contrastieve baselines zoals GRACE en SGCL. Op de grote OGBN-ArXiv-dataset was het ongeveer 13–14 keer sneller dan op random-walk gebaseerde methoden (DeepWalk, Node2Vec) terwijl het concurrerende prestaties behield. Verschillende andere baselines konden niet draaien op ArXiv vanwege geheugenbeperkingen.
• Ablatie: Het verwijderen van de contrastieve term (instellen van $\lambda=0$) resulteerde in consequent lagere prestaties, wat de noodzaak bevestigt van paarsgewijze supervisie voor het leren van discriminatieve representaties in kenmerkloze settings.

Betekenis en Claims

Het artikel stelt dat Contrastive FUSE effectief de kloof overbrugt tussen structurele gemeenschapsdetectie en paarsgewijze geleerd leren. De primaire betekenis ligt in het bieden van een snelle en schaalbare alternatief voor bestaande contrastieve leermethoden die doorgaans vertrouwen op dure diepe encoders, uitgebreide dataversterkingen of berichtdoorgeefarchitecturen.

Door modulariteit-geïnspireerd structureel leren te koppelen aan contrastieve supervisie, maakt het kader efficiënt leren van knoopembeddings mogelijk in scenario's waar knoopkenmerken ontbreken maar paarsgewijze relaties bekend zijn. De auteurs benadrukken dat deze aanpak bijzonder waardevol is voor evoluerende of contextspecifieke grafen waar embeddings efficiënt opnieuw moeten worden berekend, en voor domeinen zoals bio-informatica en privacygevoelige netwerken waar leren uitsluitend op basis van structuur een noodzaak is. De methode bereikt een gunstige afweging tussen voorspellende nauwkeurigheid en computationele efficiëntie, waardoor het geschikt is voor grootschalige real-world toepassingen.