Résumé Technique : Le Rang N'est Pas la Capacité : Occupation Spectrale pour les Modèles de Graphes Latents

Énoncé du Problème

En apprentissage de représentations de graphes, la dimension de l'espace latent est un choix de conception critique qui régit le comportement du modèle. Cependant, cette dimension est traditionnellement traitée comme un hyperparamètre fragile : elle est fixée avant l'entraînement et ajustée via des performances sur un ensemble de validation. Cette approche souffre de deux problèmes fondamentaux :

1. Identifiabilité : Les facteurs latents appris sont identifiables uniquement à une rotation et un redimensionnement global près. Par conséquent, le rang nominal (la dimension déclarée) coïncite rarement avec la quantité qui régit réellement le comportement du modèle.
2. Manque de Contrôle : Les procédures de sélection existantes (par exemple, coudes de vraisemblance profilée, sélection bayésienne, validation croisée) sélectionnent généralement une seule dimension soit avant, soit après l'ajustement. Elles échouent à exposer la « capacité représentative » — le nombre de modes latents effectivement utilisés par le modèle ajusté — en tant que quantité mesurable, contrôlable ou auditable au sein du modèle lui-même.

Dans les régimes surparamétrés, la quantité opératoire n'est pas le rang déclaré, mais la façon dont la masse représentative est distribuée à travers les modes latents.

Méthodologie : SPECTRA

Les auteurs proposent l'Extraction de Préfixe Spectral et l'Analyse de Représentation Ciblée par la Capacité (SPECTRA), un cadre qui remplace le rang nominal par le spectre d'un noyau défini positif semi-défini (PSD) appris comme unité d'analyse.

Composants Principaux

1. Noyau Normalisé par la Trace :
   Au lieu de fixer le rang $r$ comme dimension, SPECTRA paramétrise un noyau d'affinité latent $K \in \mathbb{R}^{N \times N}$ via un facteur limité en rang $L \in \mathbb{R}^{N \times r}$. Crucialement, le noyau est normalisé par la trace :
   $$K(L) = \frac{N \cdot LL^\top}{\text{tr}(LL^\top)}$$
   Cette normalisation fixe la masse spectrale totale à $N$, garantissant que les différences dans la distribution des valeurs propres reflètent la façon dont la représentation alloue son budget spectral fixe à travers les modes latents, plutôt que des différences d'amplitude globale. Cela rend les spectres comparables entre différents ajustements et limites de rang.

2. Occupation Spectrale et Dimension Effective :
   Les valeurs propres normalisées $\lambda_i(K)$ définissent une distribution de probabilité $p_i(K) = \lambda_i(K)/N$ sur les modes spectraux, appelée distribution d'occupation spectrale. Les auteurs définissent la dimension spectrale effective ($d_{\text{spec}}$) comme l'exponentielle de l'entropie de Shannon de cette distribution :
   $$d_{\text{spec}}(K) := \exp\left( -\sum_{i: p_i > 0} p_i \log p_i \right)$$
   Contrairement au rang dur, $d_{\text{spec}}$ est une mesure lisse et continue de la capacité réalisée. Elle vaut 1 si toute la masse est dans un seul mode et vaut $s$ si la masse est uniformément répartie sur $s$ modes.

3. Objectif de Contrôle de Capacité :
   Pour contrôler la dimension réalisée pendant l'entraînement, SPECTRA introduit un objectif régularisé par l'entropie :
   $$F_\eta(L, a, \beta) = \ell(L, a, \beta) - \eta \log d_{\text{spec}}(K(L)) + R(L, a, \beta)$$
   Ici, $\ell$ est la perte de prédiction de liens, $R$ est une régularisation quadratique, et $\eta$ est un poids scalaire d'entropie.

   • $\eta > 0$ encourage un spectre diffus (plus grande $d_{\text{spec}}$).
   • $\eta < 0$ encourage un spectre concentré (plus petite $d_{\text{spec}}$).
   • $\eta = 0$ correspond à l'ajustement de vraisemblance maximale standard sans biais d'entropie spectrale.

4. Ciblage et Calibration :
   Les auteurs établissent que, sous des conditions de régularité locale (spectre actif simple et hessienne non dégénérée), la dimension réalisée $d_{\text{spec}}(\eta)$ est localement $C^1$ et monotone non décroissante par rapport à $\eta$. Cela permet l'utilisation de la dichotomie pour trouver un $\eta^*$ qui cible une dimension effective désirée $d^*_{\text{spec}}$ dans une tolérance spécifiée.

5. Préfixes Spectraux :
   Un noyau ajusté unique produit une famille imbriquée de représentations alignées de dimension inférieure. En tronquant le noyau à ses $k$ premiers modes propres ($K_k$), on obtient l'approximation PSD de rang $k$ optimale (selon le théorème d'Eckart–Young–Mirsky). Ces préfixes spectraux fournissent des vues alignées de capacité inférieure du même modèle ajusté sans réentraînement.

Contributions Clés

1. Occupation Spectrale comme Capacité Réalisée : L'article remplace le rang nominal par le spectre normalisé par la trace du noyau PSD appris, utilisant le rang effectif de Shannon ($d_{\text{spec}}$) comme mesure lisse de la dimension latente réalisée.
2. Contrôle de Capacité pendant l'Entraînement : Il introduit un objectif régularisé par l'entropie où un scalaire $\eta$ façonne la dimension spectrale réalisée, permettant le ciblage de valeurs spécifiques de $d_{\text{spec}}$ via dichotomie.
3. Garanties Théoriques : Les auteurs vérifient l'identifiabilité des modes spectraux actifs sous des conditions de spectre simple et établissent un comportement local $C^1$ et la monotonie du profil de dimension réalisée. Ils prouvent également que les préfixes spectraux sont des résumés PSD de rang optimal.
4. Frontières Empiriques de Capacité : Des expériences sur huit réseaux de référence (collaboration, social, biologique, infrastructure) révèlent que la performance prédictive (AUC) s'aligne sur la $d_{\text{spec}}$ atteinte plutôt que sur le rang nominal. Cela distingue les ensembles de données « saturés » (où la performance culmine en dessous de la limite de rang) des ensembles de données « liés à la limite de rang » (où la performance s'améliore à mesure que la limite augmente).
5. Familles de Préfixes à Ajustement Unique : Un noyau ajusté fournit une famille imbriquée de préfixes spectraux alignés, offrant des vues de capacité inférieure de la même représentation sans réentraînement.
6. Surparamétrisation Contrôlée Spectralement : Dans des expériences appariées, les ajustements surparamétrés ciblés par $\eta$ (où $r > d_{\text{spec}}$) améliorent la vraisemblance logarithmique de test et réduisent l'écart entraînement-test par rapport aux bases de référence basées uniquement sur la limite de rang, même lorsqu'ils sont appariés pour une capacité effective.

Résultats Expérimentaux

• Ensembles de Données : La méthode a été évaluée sur huit graphes non orientés, incluant des réseaux de citations (ca-GrQc, ca-HepTh), des réseaux sociaux (socfb-American75, socfb-Amherst41), des réseaux biologiques (bio-grid-human, bio-grid-worm) et des réseaux d'infrastructure (inf-power, inf-openflights).
• Bases de Référence : SPECTRA a été comparé à des plongements euclidiens (Node2Vec, Role2Vec), à une factorisation de matrices (NetMF, GRAREP), à des modèles à membership mixte (MNMF) et à des modèles de simplexe de distance latente (HM-LDM).
• Performance :
  • À nombre de paramètres égal, SPECTRA ($\eta=0$) a obtenu le meilleur ou le deuxième meilleur AUC sur 7/8 ensembles de données à diverses dimensions.
  • SPECTRA Ciblé par Capacité est resté compétitif à des dimensions réalisées substantiellement plus petites. Par exemple, cibler le rang effectif médian des bases de référence a souvent produit des performances comparables avec une $d_{\text{spec}}$ significativement plus faible.
  • Analyse de Frontière : Lors du tracé de l'AUC par rapport à la $d_{\text{spec}}$ atteinte, les courbes provenant de différentes limites de rang ($r=64, 128, 256$) se sont effondrées sur une frontière commune. Cela confirme que la performance est organisée par la capacité spectrale réalisée, et non par le rang nominal.
  • Surparamétrisation : Le ciblage d'une $d^*_{\text{spec}}$ spécifique en utilisant une limite de rang plus grande $r$ a abouti à des modèles mieux calibrés (écart de généralisation plus faible et vraisemblance logarithmique de test plus élevée) par rapport à un entraînement avec une limite de rang égale à $d^*_{\text{spec}}$.

Importance et Revendications

L'article soutient que la capacité doit être traitée comme une propriété du modèle ajusté plutôt que comme un hyperparamètre du processus d'entraînement. En déplaçant l'accent du rang nominal vers l'occupation spectrale, SPECTRA rend visible et contrôlable le compromis entre la précision prédictive et la dimension réalisée.

Les auteurs affirment que cette approche :

• Fournit une prise de capacité principielle dans le régime surparamétré.
• Permet l'extraction de vues alignées de capacité inférieure d'un modèle (préfixes spectraux) sans réentraînement.
• Distingue les ensembles de données où la structure latente est entièrement capturée par un petit nombre de modes (saturés) de ceux où le modèle est contraint par la limite de rang.
• Offre une coordonnée continue ($d_{\text{spec}}$) pour comparer la complexité structurelle de différents réseaux, potentiellement applicable à l'étude de la variation de la complexité des réseaux à travers différents contextes (par exemple, social, biologique, infrastructure).

Le travail est modeste quant à ses limites, notant qu'il opère actuellement dans des espaces latents euclidiens. L'extension de ces concepts à des géométries non euclidiennes (par exemple, plongements à valeurs simplexe ou hyperboliques) et le développement de protocoles de prétraitement communs pour les comparaisons inter-réseaux sont laissés pour des travaux futurs.