Résumé Technique : GTIN – Un cadre unifié pour la prédiction conjointe d'événements et de temps dans les graphes temporels

1. Définition du Problème

L'article traite du défi de la prédiction des événements futurs dans les systèmes dynamiques modélisés sous forme de graphes temporels. Contrairement aux modèles de graphes statiques traditionnels ou aux approches de graphes temporels existantes qui se concentrent souvent sur des sous-graphes localisés ou des historiques d'arêtes spécifiques, ce travail cible une tâche de prédiction unifiée. L'objectif est d'estimer conjointement trois composantes critiques du prochain événement dans un graphe temporel :

1. La Localisation ($c$) : Quelle arête (paire d'interaction) sera active ensuite ?
2. Le Temps ($t$) : Quand cet événement se produira-t-il ?
3. Les Caractéristiques ($W$) : Quels sont les attributs de cet événement ?

Les auteurs soutiennent que les méthodes existantes, telles que les réseaux de neurones de graphes temporels (TGNN) et les processus ponctuels temporels (TPP), échouent souvent à utiliser le contexte structurel global, s'appuyant plutôt sur des fenêtres temporelles limitées ou des voisinages de nœuds locaux. Cette limitation entrave la capacité à capturer des dépendances temporelles à longue portée complexes et des motifs d'événements irréguliers inhérents aux systèmes du monde réel comme les réseaux sociaux, les transactions financières et les journaux de communication.

2. Méthodologie : Réseau d'Interaction Temporelle Globale (GTIN)

La solution proposée, GTIN, est un cadre mathématique unifié qui traite l'ensemble de la structure du graphe comme une entité unique pour la prédiction, plutôt que d'agréger des prédictions d'arêtes indépendantes.

2.1. Formulation Mathématique

Le problème est formulé à l'aide de Processus Ponctuels Marqués. L'historique du graphe jusqu'au temps $t$, noté $\mathcal{H}(t)$, consiste en une séquence de triplets $(t_i, W_i, c_i)$ représentant le temps, les caractéristiques et l'indice d'arête spécifique. Le but est de maximiser la vraisemblance du prochain triplet d'événements $\mathcal{H}(t, 1)$ étant donné l'historique $\mathcal{H}(t)$.

La vraisemblance est décomposée en trois probabilités conditionnelles :
$$P(\hat{c}, \hat{t}, \hat{W} | \mathcal{H}(t)) = P(\hat{c}|\mathcal{H}(t)) \cdot P(\hat{t}|\hat{c}, \mathcal{H}(t)) \cdot P(\hat{W}|\hat{t}, \hat{c}, \mathcal{H}(t))$$

Cette décomposition permet au modèle de prédire séquentiellement la localisation de l'arête, le temps d'occurrence et les caractéristiques de l'événement.

2.2. Architecture du Modèle

GTIN emploie un Cadre de Passage de Messages où les arêtes du graphe original sont traitées comme des nœuds dans un "graphe de lignes" transformé. Les nœuds-arêtes voisins sont ceux partageant un point commun dans le graphe original.

• Embeddings d'Arêtes : Chaque arête $n$ maintient un embedding $h_n(t)$ qui agrège l'information temporelle de son propre historique et des historiques des arêtes voisines.
  $$h_n(t) = \text{COMB}\left( \text{AGG}\{\Phi(t^j_i, W^j_i) | t^j_i \leq t, j \in \mathcal{N}(n)\}, \Phi(t^n_i, W^n_i) \right)$$
  Ici, $\text{COMB}$ utilise un mécanisme d'auto-attention, et $\text{AGG}$ est une transformation linéaire apprenable.
• Encodage Temporel : Pour gérer le temps continu sans discrétisation, le modèle utilise un encodeur de temps harmonique (similaire à GNPP), projetant les horodatages dans des vecteurs de haute dimension à l'aide de paramètres de fréquence apprenables. Cela capture la récence à court terme, les dépendances à long terme et la périodicité.
• Représentation Globale du Graphe : L'état global du graphe au temps $t$ est calculé comme une somme pondérée de tous les embeddings d'arêtes :
  $$h_G(t) = \sum_{n=1}^{N} w_n h_n(t)$$
  Cet embedding global $h_G(t)$ sert de contexte pour prédire le prochain événement, garantissant que la prédiction considère l'état temporel de l'ensemble du graphe.

2.3. Têtes de Prédiction

Le modèle utilise trois têtes distinctes basées sur les embeddings globaux et locaux :

1. Prédiction d'Arête (Classification) : Utilise un softmax sur toutes les arêtes candidates pour prédire $c_i$.
2. Prédiction de Temps (Régression) : Modélise la distribution temporelle comme une Gaussienne $\mathcal{N}(\mu_t, \sigma_t^2)$, prédisant à la fois la moyenne et la variance pour quantifier l'incertitude.
3. Prédiction de Caractéristiques (Régression) : Modélise les caractéristiques de l'événement comme une distribution normale multivariée, conditionnée par l'arête, le temps et l'historique global prédits.

L'objectif d'entraînement minimise la log-vraisemblance négative, qui est la somme de la perte de classification, de la perte de prédiction de temps et de la perte de prédiction de caractéristiques.

2.4. Extension de Scalabilité (DGI + Clustering)

Pour répondre à la complexité computationnelle sur les grands graphes, les auteurs proposent une extension utilisant le Deep Graph Infomax (DGI) et le Clustering K-means Équilibré :

• DGI : Apprend des embeddings de nœuds non supervisés qui préservent l'information mutuelle entre les patchs locaux et le contexte global du grapme.
• Clustering Équilibré : Partitionne le graphe en sous-graphes de taille approximativement égale.
• Prédiction Hiérarchique : Le pipeline construit un nouveau "super graphe" où chaque sous-graphe est traité comme un super-nœud. Ce super graphe est injecté dans l'algorithme pour détecter dans quel cluster l'événement suivant se produit. Une fois le cluster cible identifié, le sous-graphe correspondant est envoyé dans le module de prédiction d'événement, où le type d'événement et son temps d'occurrence sont prédits conjointement via le modèle temporel. Cela permet un traitement parallèle et réduit considérablement le temps d'entraînement et d'inférence.

3. Principales Contributions

L'article met en avant trois contributions majeures :

1. Cadre de Prédiction Conjointe Événement-Temps Globale : Un modèle qui prédit conjointement la localisation, le moment et les caractéristiques du prochain événement en analysant la structure globale du graphe, dépassant la dépendance aux voisinages locaux.
2. Scalabilité Hiérarchique : Un mécanisme pour partitionner et traiter efficacement des graphes de n'importe quelle taille tout en maintenant les dépendances temporelles, facilitant l'entraînement sur des jeux de données à grande échelle.
3. Prévision d'Événements au Niveau des Caractéristiques : La capacité d'estimer les attributs des événements (caractéristiques) parallèlement aux prédictions structurelles et temporelles, offrant une capacité de prévision plus complète.

4. Résultats Expérimentaux

Les auteurs ont évalué GTIN sur trois jeux de données réels (Wikipedia, Reddit, CollegeMsg) et trois jeux de données synthétiques (Hawkes-negative, Hawkes-positive, Poisson).

• Performance : GTIN a systématiquement surpassé les modèles de référence, y compris TGAT, TGN, DyRep et les modèles de processus ponctuels neuronaux (THP, SAHP, NNPP).
  • Sur le jeu de données Wikipedia, GTIN a obtenu une RMSE de 10,6, nettement inférieure à celle de TGN (23,81) et TGAT (37,66).
  • Sur le jeu de données Reddit, GTIN a obtenu une RMSE de 0,51, soit presque la moitié de l'erreur du modèle suivant (GNPP à 1,08).
  • Sur les jeux de données synthétiques, GTIn a réduit les taux d'erreur de 8 à 70 % par rapport à la meilleure base de référence (GNPP), excellant particulièrement dans les jeux de données présentant de forts comportements auto-excitateurs (Hawkes-positive).
• Prédiction de Localisation : Le modèle a démontré une forte performance pour prédire la bonne arête (Hits@10 et MRR), validant l'efficacité de l'intégration du contexte global.
• Scalabilité : Le pipeline basé sur DGI a réduit le temps d'entraînement de 52 à 68 % et le temps d'inférence de 50 à 66 % sur l'ensemble des jeux de données, avec une augmentation seulement marginale de la RMSE, confirmant un compromis favorable entre précision et efficacité.
• Études d'Ablation : Le retrait du mécanisme d'attention a entraîné des baisses de performance constantes, confirmant que l'attention est cruciale pour pondérer les voisins informatifs. L'analyse de "l'activité des arêtes voisines" a montré que l'avantage de GTIN est plus prononcé pour les événements entourés d'une faible activité locale, prouvant sa capacité à exploiter l'information globale là où l'historique local est clairsemé.

5. Signification et Limites

Signification :
L'article affirme que GTIN fournit une base robuste pour la prédiction d'événements temporels en unifiant la modélisation structurelle et temporelle. Sa capacité à gérer des motifs d'événements irréguliers et des dépendances complexes le rend supérieur aux méthodes restreintes aux fenêtres locales. Le cadre est présenté comme une architecture polyvalente capable de s'adapter à divers environnements dynamiques, des interactions sociales denses aux réseaux de communication clairsemés.

Limites :
Les auteurs reconnaissent explicitement deux limites principales :

1. Hypothèse d'Homogénéité : Le modèle traite toutes les arêtes comme équivalentes, ignorant les types d'arêtes spécifiques ou les relations contextuelles (par exemple, distinguer différents types de transactions financières).
2. Exclusion des Caractéristiques de Nœuds : L'implémentation actuelle n'incorpore pas les attributs spécifiques aux nœuds (par exemple, la démographie des utilisateurs), manquant potentiellement des signaux prédictifs précieux disponibles dans les jeux de données riches en métadonnées.

L'article conclut que bien que GTIN fasse progresser l'état de l'art, les travaux futurs devraient se concenter sur l'incorporation de types d'arêtes hétérogènes, d'attributs de nœuds et de mécanismes de calcul distribués pour améliorer davantage la scalabilité et la précision dans les contextes d'interaction clairsemés.