Aitchison Embeddings for Learning Compositional Graph Representations

1. Probleemstelling

Het leren van grafrepresentaties is fundamenteel voor taken zoals linkvoorspelling en knopclassificatie. Echter, bestaande methoden staan voor twee primaire beperkingen wat betreft interpreteerbaarheid en structurele modellering:

• Gebrek aan intrinsieke interpreteerbaarheid: Standaard Euclidische embeddings (zoals Node2Vec, GNN's) coderen gelijkenis geometrisch, maar missen semantische betekenis in hun latente dimensies. Afstanden en richtingen zijn vaak willekeurig en gevoelig voor keuzes in coördinaten, wat post-hoc analyse vereist voor uitleg.
• Ongeschikte modellering van rolstructuren: Veel real-world netwerken vertonen rol-mengsel structuren waarbij knopen geen distincte entiteiten zijn, maar mengsels van latente archetypische factoren (bijvoorbeeld een gebruiker die optreedt als zowel "onderzoeker" als "student").
  • Traditionele rolgebaseerde modellen (zoals Stochastic Block Models) gaan uit van discrete, langs de as uitgelijnde rollen.
  • Modellen met gemengde lidmaatschappen staan overlapping toe, maar vertrouwen vaak op discrete, identificeerbare assen die falen wanneer rollen continu, overlappend zijn, of gedefinieerd door relatieve afwegingen in plaats van absolute groottes.
  • Standaard Euclidische ruimtes handelen compositional data (data waarbij alleen de verhoudingen tussen componenten tellen, niet de absolute schaal) niet op natuurlijke wijze, wat leidt tot problemen met schaal-invariantie en subcompositional coherentie.

2. Methodologie: AICoG

De auteurs stellen Aitchison Compositional Graph embeddings (AICoG) voor, een raamwerk gebaseerd op Aitchison-geometrie, de canonieke geometrie voor compositional data.

Kernconcepten

• Compositional Representatie: Elke knoop $i$ wordt weergegeven als een compositie $z_i$ op de $(K-1)$-dimensionale simplex $\Delta^{K-1}$, waarbij $K$ het aantal latente archetypische factoren is. De vector $z_i = (z_{i1}, \dots, z_{iK})$ vertegenwoordigt de relatieve bijdrage van elk archetype aan de knoop.
• Aitchison-geometrie: In plaats van Euclidische afstand wordt gelijkenis gemeten met de Aitchison-afstand, die uitsluitend afhankelijk is van de log-ratio's tussen componenten. Dit zorgt voor schaal-invariantie (absolute activiteitsniveaus beïnvloeden gelijkenis niet) en subcompositional coherentie (het verwijderen van een subset van componenten behoudt de relatieve geometrie).
• Isometrische Log-Ratio (ILR) Transformatie: Om optimalisatie met standaard Euclidische hulpmiddelen (zoals gradient descent) mogelijk te maken terwijl de Aitchison-geometrie behouden blijft, mapt de methode composities van de simplex naar een onbeperkte Euclidische ruimte $\mathbb{R}^{K-1}$ via de ILR-transformatie:
  $$x_i = \text{ILR}(z_i) = \log(z_i)^\top V$$
  waarbij $V$ een orthonormale basis is voor de contrastruimte. Deze transformatie is een isometrie, wat betekent dat de Euclidische afstand tussen $x_i$ en $x_j$ exact gelijk is aan de Aitchison-afstand tussen $z_i$ en $z_j$.

Modelarchitectuur

1. Parametrisatie: Knoop-composities $z_i$ worden geparametriseerd via onbeperkte logits $\tilde{z}_i$ die door een softmax-functie worden geleid om ervoor te zorgen dat ze op de simplex liggen.
2. Kans op een Knoop: De kans op een verbinding $(i, j)$ wordt gemodelleerd als een Bernoulli-verdeling waarbij de log-odds $\eta_{ij}$ een monotoon afnemende functie zijn van de ILR-afstand:
   $$\eta_{ij} = -\|x_i - x_j\|^2 + \gamma_i + \gamma_j$$
   Hierbij vertegenwoordigt $\gamma$ knoop-specifieke biases (bijvoorbeeld heterogeniteit in graad).
3. Optimalisatie: Het model wordt getraind door de Bernoulli log-likelihood over waargenomen verbindingen te maximaliseren.
4. Basisflexibiliteit: Het raamwerk ondersteunt zowel vaste bases (bijvoorbeeld de Helmert-basis) als leerbare bases (gezamenlijk getraind met embeddings) om interpreteerbaarheid te optimaliseren.

3. Belangrijkste Bijdragen

1. AICoG-raamwerk: Introductie van een graf-embedding raamwerk dat knopen modelleert als composities over latente archetypen en deze vergelijkt met Aitchison-geometrie.
2. Expressieve Equivalentie: Bewijs dat het embedden van composities via ILR-coördinaten een latente afstandmodel oplevert dat expressief equivalent is aan standaard onbeperkte Euclidische latente afstandmodellen. Dit betekent dat AICoG interpreteerbaarheid wint zonder in te leveren op het vermogen om complexe kansen voor verbindingen weer te geven.
3. Geometrische Rollen: Een nieuwe definitie van "rollen" als regio's in een compositional latente ruimte gekenmerkt door stabiele relatieve afwegingen, in plaats van langs de as uitgelijnde dimensies. Dit ondersteunt continue en overlappende rolstructuren.
4. Subcompositional Coherentie: Demonstratie dat het raamwerk principiële componentbeperking toestaat. Het verwijderen en hernormaliseren van een subset van archetypische factoren behoudt een goed gedefinieerde geometrie, waardoor analyse mogelijk is van hoe specifieke archetypegroepen voorspellingen beïnvloeden zonder hertraining.
5. Intrinsieke Verklaarbaarheid: De methode biedt uitleg per constructie. Gelijkenis wordt verklaard via log-ratio balans (afwegingen) tussen archetypen, die invariant zijn voor orthogonale herparametrisaties van het coördinatenstelsel.

4. Experimentele Resultaten

De auteurs hebben AICoG geëvalueerd op diverse datasets (Citation-netwerken: Cora, Citeseer; Co-auteurschap: DBLP, AstroPh, etc.; Sociaal: LastFM) tegen sterke baselines waaronder Node2Vec, Role2Vec, MMSBM en SLIM-RAA.

• Linkvoorspelling: AICoG behaalde concurrerende of superieure AUC-ROC-scores vergeleken met sterke baselines. Opvallend is dat het vervangen van Aitchison-geometrie door Euclidische geometrie op de simplex (SIMPLEX-EUCLIDEAN) leidde tot een significante prestatiedaling, wat bewijst dat de compositional geometrie zelf cruciaal is, niet alleen de simplex-beperking.
• Knopclassificatie: AICoG behaalde gunstige Micro-F1-scores, vergelijkbaar met Euclidische methoden, terwijl het geometrisch interpreteerbare representaties bood.
• Subcompositional Evaluatie: Wanneer componenten werden verwijderd (dimensionaliteitsreductie via subsetselectie), behield AICoG de prestaties aanzienlijk beter dan andere op simplex gebaseerde baselines (zoals MMSBM of HM-LDM). Dit bevestigt de stabiliteit van de representatie onder principiële componentbeperking.
• Analyse van Interpreteerbaarheid: Visualisaties toonden aan dat verschillende ILR-bases (Helmert, Learned, Varimax) consistente labelseparaties opleverden, wat bevestigt dat de structuur invariant is ten opzichte van het coördinatenstelsel. De methode slaagde erin interpreteerbare "afwegingstrajecten" tussen archetypen te identificeren.

5. Betekenis en Impact

• Overbrugging van de Kloof: AICoG overbrugt de kloof tussen hoge voorspellende prestaties (typisch voor Euclidische embeddings) en hoge interpreteerbaarheid (typisch voor probabilistische rolmodellen).
• Nieuw Paradigma voor Rollen: Het verschuift het paradigma van discrete, langs de as uitgelijnde rollen naar continue, relatieve afwegingen, wat beter de aard van veel real-world netwerken weerspiegelt (bijvoorbeeld sociaal, biologisch, economisch).
• Principiële Verklaarbaarheid: In tegenstelling tot post-hoc uitlegmethode (zoals GNNExplainer) zijn de uitleggen van AICoG intrinsiek aan de geometrie van het model. Het stelt onderzoekers in staat om te vragen "hoe beïnvloedt de afweging tussen Archetype A en B de positie van de knoop?" in plaats van "wat is het gewicht van dimensie X?".
• Toekomstige Richtingen: Het paper suggereert dat Aitchison-geometrie kan dienen als fundament voor het uitbreiden van compositional inductieve bias naar andere architecturen, zoals message-passing neurale netwerken die opereren op compositional knoopstaten.

Kortom, AICoG biedt een wiskundig rigoureus en praktisch effectieve aanpak voor het leren van grafrepresentaties waarbij de semantiek van de latente ruimte expliciet is afgestemd op de relatieve, compositional aard van knoprollen.