Aitchison Embeddings for Learning Compositional Graph Representations

1. Enunciato del Problema

L'apprendimento di rappresentazioni di grafi è fondamentale per compiti come la previsione di collegamenti e la classificazione dei nodi. Tuttavia, i metodi esistenti affrontano due limitazioni principali riguardo all'interpretabilità e alla modellazione strutturale:

• Mancanza di Interpretabilità Intrinseca: Gli embedding euclidei standard (ad es. Node2Vec, GNN) codificano la similarità geometricamente ma mancano di significato semantico nelle loro dimensioni latenti. Distanze e direzioni sono spesso arbitrarie e sensibili alle scelte di coordinate, richiedendo analisi post-hoc per la spiegazione.
• Modellazione Inadeguata delle Strutture di Ruolo: Molte reti reali mostrano strutture di mescolanza di ruoli (role-mixture) in cui i nodi non sono entità distinte, ma piuttosto mescolanze di fattori archetipici latenti (ad es. un utente che agisce sia come "ricercatore" che come "studente").
  • I modelli basati sui ruoli tradizionali (ad es. Modelli a Blocchi Stocastici) assumono ruoli discreti e allineati agli assi.
  • I modelli a appartenenza mista permettono sovrapposizioni ma spesso si affidano ad assi discreti e identificabili che falliscono quando i ruoli sono continui, sovrapposti o definiti da compromessi relativi piuttosto che da grandezze assolute.
  • Gli spazi euclidei standard non gestiscono naturalmente i dati composizionali (dati in cui contano solo i rapporti tra i componenti, non la scala assoluta), portando a problemi di invarianza di scala e coerenza subcomposizionale.

2. Metodologia: AICoG

Gli autori propongono gli Embedding Composizionali di Aitchison per Grafi (AICoG), un framework fondato sulla geometria di Aitchison, la geometria canonica per i dati composizionali.

Concetti Chiave

• Rappresentazione Composizionale: Ogni nodo $i$ è rappresentato come una composizione $z_i$ sul simplesso $(K-1)$-dimensionale $\Delta^{K-1}$, dove $K$ è il numero di fattori archetipici latenti. Il vettore $z_i = (z_{i1}, \dots, z_{iK})$ rappresenta il contributo relativo di ogni archetipo al nodo.
• Geometria di Aitchison: Invece della distanza euclidea, la similarità è misurata utilizzando la distanza di Aitchison, che dipende esclusivamente dai log-rapporti tra i componenti. Questo garantisce l'invarianza di scala (i livelli di attività assoluta non influenzano la similarità) e la coerenza subcomposizionale (rimuovere un sottoinsieme di componenti preserva la geometria relativa).
• Trasformazione Log-Rapporto Isometrica (ILR): Per abilitare l'ottimizzazione utilizzando strumenti euclidei standard (come la discesa del gradiente) preservando la geometria di Aitchison, il metodo mappa le composizioni dal simplesso a uno spazio euclideo non vincolato $\mathbb{R}^{K-1}$ tramite la trasformazione ILR:
  $$x_i = \text{ILR}(z_i) = \log(z_i)^\top V$$
  dove $V$ è una base ortonormale per lo spazio di contrasto. Questa trasformazione è un'isometria, il che significa che la distanza euclidea tra $x_i$ e $x_j$ è esattamente uguale alla distanza di Aitchison tra $z_i$ e $z_j$.

Architettura del Modello

1. Parametrizzazione: Le composizioni dei nodi $z_i$ sono parametrizzate tramite logit non vincolati $\tilde{z}_i$ passati attraverso una funzione softmax per garantire che giacciano sul simplesso.
2. Verosimiglianza degli Archi: La probabilità di un arco $(i, j)$ è modellata come una distribuzione Bernoulliana dove i log-odds $\eta_{ij}$ sono una funzione monotona decrescente della distanza ILR:
   $$\eta_{ij} = -\|x_i - x_j\|^2 + \gamma_i + \gamma_j$$
   Qui, $\gamma$ rappresenta bias specifici del nodo (ad es. eterogeneità del grado).
3. Ottimizzazione: Il modello è addestrato massimizzando la log-verosimiglianza Bernoulliana sugli archi osservati.
4. Flessibilità della Base: Il framework supporta sia basi fisse (ad es. base di Helmert) che basi apprendibili (addestrate congiuntamente agli embedding) per ottimizzare l'interpretabilità.

3. Contributi Chiave

1. Framework AICoG: Introduzione di un framework di embedding di grafi che modella i nodi come composizioni su archetipi latenti e li confronta utilizzando la geometria di Aitchison.
2. Equivalenza Espressiva: Dimostrazione che l'embedding di composizioni tramite coordinate ILR produce un modello di distanza latente espressivamente equivalente ai modelli di distanza latente euclidei standard non vincolati. Ciò significa che AICoG guadagna interpretabilità senza sacrificare la capacità di rappresentare matrici complesse di probabilità degli archi.
3. Ruoli Geometrici: Una nuova definizione di "ruoli" come regioni in uno spazio latente composizionale caratterizzate da compromessi relativi stabili, piuttosto che da dimensioni allineate agli assi. Questo supporta strutture di ruolo continue e sovrapposte.
4. Coerenza Subcomposizionale: Dimostrazione che il framework permette una restrizione dei componenti principiale. Rimuovere e rinormalizzare un sottoinsieme di fattori archetipici preserva una geometria ben definita, permettendo l'analisi di come gruppi specifici di archetipi influenzino le previsioni senza riaddestramento.
5. Spiegabilità Intrinseca: Il metodo fornisce spiegazioni per costruzione. La similarità è spiegata tramite bilanci log-rapporto (compromessi) tra archetipi, che sono invarianti rispetto a riparametrizzazioni ortogonali del sistema di coordinate.

4. Risultati Sperimentali

Gli autori hanno valutato AICoG su vari dataset (reti di citazione: Cora, Citeseer; co-autorialità: DBLP, AstroPh, ecc.; sociali: LastFM) confrontandolo con baseline robuste tra cui Node2Vec, Role2Vec, MMSBM e SLIM-RAA.

• Previsione di Collegamenti: AICoG ha ottenuto punteggi AUC-ROC competitivi o superiori rispetto alle baseline robuste. Notevolmente, sostituire la geometria di Aitchison con la geometria euclidea sul simplesso (SIMPLEX-EUCLIDEAN) ha causato un calo significativo delle prestazioni, dimostrando che la geometria composizionale stessa è critica, non solo il vincolo del simplesso.
• Classificazione dei Nodi: AICoG ha ottenuto punteggi Micro-F1 favorevoli, comparabili ai metodi euclidei, fornendo al contempo rappresentazioni geometricamente interpretabili.
• Valutazione Subcomposizionale: Quando i componenti sono stati rimossi (riduzione della dimensionalità tramite selezione di sottoinsiemi), AICoG ha mantenuto le prestazioni in modo significativamente migliore rispetto ad altre baseline basate sul simplesso (come MMSBM o HM-LDM). Questo conferma la stabilità della rappresentazione sotto restrizione principiale dei componenti.
• Analisi dell'Interpretabilità: Le visualizzazioni hanno mostrato che diverse basi ILR (Helmert, Appresa, Varimax) hanno prodotto separazioni di etichette coerenti, confermando che la struttura è invariante rispetto al sistema di coordinate. Il metodo ha identificato con successo "traiettorie di compromesso" interpretabili tra gli archetipi.

5. Significato e Impatto

• Colmare il Divario: AICoG colma il divario tra alta prestazione predittiva (tipica degli embedding euclidei) e alta interpretabilità (tipica dei modelli probabilistici di ruolo).
• Nuovo Paradigma per i Ruoli: Sposta il paradigma da ruoli discreti e allineati agli assi a compromessi relativi continui, che riflettono meglio la natura di molte reti reali (ad es. sociali, biologiche, economiche).
• Spiegabilità Principiale: A differenza dei metodi di spiegazione post-hoc (ad es. GNNExplainer), le spiegazioni di AICoG sono intrinseche alla geometria del modello. Permette ai ricercatori di chiedere "come il compromesso tra l'Archetipo A e B influisce sulla posizione del nodo?" piuttosto che "qual è il peso della dimensione X?".
• Direzioni Future: Il paper suggerisce che la geometria di Aitchison può servire come fondamento per estendere i bias induttivi composizionali ad altre architetture, come le reti neurali a passaggio di messaggi che operano su stati di nodi composizionali.

In sintesi, AICoG offre un approccio matematicamente rigoroso e praticamente efficace per l'apprendimento di rappresentazioni di grafi in cui la semantica dello spazio latente è esplicitamente allineata alla natura relativa e composizionale dei ruoli dei nodi.