Résumé Technique : Signatures de Motifs Temporels pour les Réseaux de Neurones sur Graphes Temporels

Énoncé du Problème

Les flux d'interactions temporelles du monde réel (ex. : communications sociales, transferts financiers, avis en ligne) contiennent une structure prédictive au sein de motifs de motifs à horizon court, tels que la répétition, la réciprocité, la diversité stellaire et le flux triadiques. Bien que les réseaux de neurones sur graphes temporels (TGNN) modernes soient des modèles de séquences expressifs capables d'extraire théoriquement n'importe quelle fonction d'un flux temporel, leurs biais inductifs et leurs budgets d'entraînement limités les empêchent souvent de capturer des régularités structurelles spécifiques à horizon court. Ces régularités sont fréquemment simples à calculer de manière analytique mais sont critiques pour les tâches en aval. L'article traite l'écart entre ce que les TGNN standards apprennent et les statistiques explicites à horizon court qui caractérisent les flux temporels, en se demandant si une augmentation principled et agnostique à l'architecture peut combler cet écart résiduel.

Méthodologie

1. Diagnostics Empiriques et Identification de Signatures

Les auteurs analysent d'abord les comptes de motifs par candidat, sur la fenêtre passée, à travers un ensemble diversifié de 13 jeux de données temporels réels et synthétiques (incluant MOOC, Bitcoin Alpha/OTC et les benchmarks TGB). Ils identifient que l'activité des motifs s'organise de manière cohérente selon trois axes stables à l'échelle :

• A1 (Récence Dyadique/Réciprocité) : Capture le timing et la fréquence des interactions directes entre une paire de candidats $(u, v)$.
• A2 (Diversité Stellaire) : Mesure la diversité des voisins interagissant avec $u$ ou $v$ dans une fenêtre temporelle (ex. : le nombre d'éléments distincts avec lesquels un étudiant a interagi).
• A3 (Flux Triadique) : Capture le flux d'interactions à travers des tiers faisant le pont entre $u$ et $v$ (ex. : voisins communs).

2. La Carte de Caractéristiques de Motif $h(u, v, t)$

Sur la base de ces axes, les auteurs conçoivent une carte de caractéristiques de motif compacte, à 13 coordonnées, locale au candidat, $h(u, v, t) \in \mathbb{R}^{13}$. Les contraintes de conception clés incluent :

• Sécurité contre la fuite (Leakage Safety) : Les caractéristiques sont calculées strictement à partir de la fenêtre passée $W_{t}^{past}(\Delta) = \{i : t - \Delta \le t_i < t\}$, garantissant qu'aucune information future ne fuit dans la représentation du candidat.
• Dimension Fixe : Les 13 caractéristiques sont concaténées via une matrice d'embedding linéaire apprenable $M$ dans n'importe quel encodeur statique ou temporel sans changement architectural.
• Sous-familles : Les 13 coordonnées correspondent aux trois axes :
  • A1 (5 caractéristiques) : Comptes d'événements $u \to v$ et $v \to u$, événements appariés, burstiness (caractère explosif), et temps normalisé depuis le dernier événement réciproque.
  • A2 (4 caractéristiques) : Tailles des ensembles de voisins distincts ($N_{u}^{out}, N_{u}^{in}, N_{v}^{out}, N_{v}^{in}$) dans la fenêtre, plafonnées pour gérer les hubs.
  • A3 (4 caractéristiques) : Tailles des intersections de types cross-wedge et bi-wedge dirigées entre les ensembles de voisins de $u$ et $v$.
• Normalisation : Les coordonnées de comptes à distribution lourde subissent une transformation $\log_{10}(1+x)$ pour assurer la comparabilité.

3. Placement Théorique (Weisfeiler-Leman Temporel)

L'article établit une borne théorique pour les MP-GNN temporels standards (GNN de passage de messages). Sous une abstraction commune de score d'arête, ces modèles sont limités par le premier niveau d'une hiérarchie Weisfeiler-Leman ancrée au candidat (temporal-1-WL).

• Les auteurs prouvent qu'il existe des flux ancrés (ex. : un cycle $C_6$ versus deux triangles disjoints $2K_3$) que le temporal-1-WL ne peut distinguer (les réduisant à la même couleur), alors que la carte de caractéristiques de motif $h$ les distingue parfaitement.
• Cela place l'augmentation par motifs strictement au-dessus de la puissance d'expression des MP-GNN temporels standards, agissant comme un "témoin" qui brise le goulot d'étranglement WL.

Contributions Clés

1. Diagnostics (Section 4) : L'article articule que les comptes de motifs par candidat organisent les flux temporels le long de trois axes dominants et stables à l'échelle (A1, A2, A3). Ces signatures par jeu de données prédisent où l'augmentation par motifs produira les gains de performance les plus importants.
2. Expressivité Temporelle (Section 6) : Les auteurs fournissent un placement théorique des MP-GNN temporels standards dans une hiérarchie temporal-WL ancrée au candidat. Ils présentent une paire spécifique de flux où les caractéristiques de motifs distinguent des candidats que le temporal-1-WL réduit, démontrant que l'augmentation élève le modèle au-delà du premier niveau de cette hiérarchie.
3. Performance Empirique (Section 7) : L'article démontre que l'augmentation par motifs élève systématiquement la performance à travers des tâches hétérogènes (prédiction de propriétés de liens TGB, classification d'arêtes et classification au niveau du graphe) par rapport à de solides bases de comparaison TGNN. Le gain est interprétable : il est maximal là où la base échoue à capturer la structure à horizon court (ex. : MOOC) et négligeable là où la base capture déjà la structure pertinente.

Résultats Expérimentaux

Le cadre a été évalué sur :

• Prédiction de Propriétés de Liens TGB : À travers cinq bases de comparaison (TPNet, HyperEvent, DyGFormer, TNCN, TGN) et trois jeux de données (Wiki, Review, Coin).
  • Résultat : L'augmentation par motifs a amélioré la performance sur tous les couples base-jeu de données évalués. Le gain le plus significatif a été observé sur DyGFormer pour le jeu de données tgbl-review-v2, où le Mean Reciprocal Rank (MRR) est passé de 0,224 à 0,413.
  • Observation : Les gains étaient compris dans un écart-type de zéro pour des bases comme TPNet sur tgbl-coin-v2, ce qui est cohérent avec ces bases qui capturent déjà la structure pertinente à horizon court pour ce jeu de données spécifique.
• Classification d'Arêtes :
  • MOOC : Une tâche de classification binaire prédisant l'abandon des étudiants. Un encodeur GraphSAGE vanilla a obtenu un PR-AUC de 0,0164. L'ajout du sous-ensemble de comptage stellaire à 4 caractéristiques (A2) a élevé cela à 0,1430, et la carte complète de 13 caractéristiques a atteint 0,1659.
  • Bitcoin Alpha/OTC : Les tâches de classification de confiance ont montré des améliorations modestes mais constantes (ex. : SAGE PR-AUC de 0,9282 à 0,9667 sur Alpha).
• Classification au Niveau du Graphe : Sur des générateurs temporels synthétiques, l'augmentation par motifs a amélioré l'exactitude de manière significative, élevant notamment GAT d'un niveau de collapse de 16,7 % (prédiction de la classe majoritaire) à 94,0 % sans changement architectural.

Ablations et Contrôles :

• Une analyse "leave-one-out" a confirmé qu'aucune coordonnée n'est uniformément redondante ; différents jeux de données dépendent de différents axes (ex. : MOOC repose fortement sur la diversité stellaire A2, tandis que Bitcoin Alpha repose sur la réciprocité A1).
• Les contrôles ont écarté l'idée que les gains proviennent d'une "capacité supplémentaire" (des caractéristiques aléatoires n'ont pas reproduit l'élévation) et ont confirmé que le gain n'est pas simplement un proxy pour de simples comptes d'activité des nœuds.

Signification et Revendications

L'article affirme que les signatures de motifs temporels constituent une méthode compacte, interprétable et agnostique à l'architecture pour injecter des régularités structurelles à horizon court dans les TGNN.

• Pouvoir Prédictif : La signature par jeu de données le long des axes A1/A2/A3 sert d'outil de diagnostic pour prédire où l'augmentation sera la plus bénéfique.
• Fondement Théorique : En plaçant l'augmentation par rapport à la hiérarchie temporal-WL, l'article clarifie pourquoi les TGNN standards échouent sur certaines tâches (ils sont limités par le temporal-1-WL) et comment l'augmentation surmonte cela.
• Utilité Pratique : La méthode ne nécessite aucun changement dans l'architecture de l'encodeur sous-jacent, seulement la concaténation d'un vecteur de caractéristiques pré-calculé, ce qui la rend facilement déployable sur les pipelines existants.

Les auteurs maintiennent une position modeste, notant que le rayon de la fenêtre $\Delta$ est un hyperparamètre sensible et que dans les flux creux où le flux triadique est négligeable, l'augmentation se réduit à un sous-espace de dimension inférieure avec des gains proportionnellement moindres. Le cadre est présenté comme un moyen rigoureux d'exposer des signaux structurels spécifiques que les fonctions de score d'arêtes des TGNN vanilla échouent souvent à exposer.