Change Point Detection in Temporal Graphs

Abstract

Change point detection (CPD) in temporal graphs is a crucial task for identifying structural regime shifts in dynamic networks. However, existing approaches often struggle when communication data are sparse and volatile, as they rely on structural features or global statistics that are not adapted to such settings. They also lack the flexibility to evaluate changes across arbitrary substructures, which limits their applicability. In this thesis, we adapt the Multi-Scale Anomaly Detection (MAD) framework to the problem of CPD in temporal graphs. MAD introduces a probabilistic and multi-scale analysis of subgraphs, producing a scoring function that identifies abrupt structural changes even in highly sparse data. The method is flexible, as it can detect change points at the edge, node, or graph level, and efficient, with linear complexity in both the length of the data and the number of analyzed communications. Extensive experiments on synthetic and real-world datasets demonstrate that MAD produces sharp and consistent change point signals. It successfully recovers regime shifts across networks of varying densities and reveals meaningful structural transitions in real communication and organizational data. These results highlight MAD as a robust and scalable framework for CPD in temporal graphs, particularly effective in sparse and uncertain environments.***

La détection de points de changement (CPD) dans les graphes temporels constitue une tâche essentielle pour identifier les transitions de régime structurel dans les réseaux dynamiques. Cependant, les approches existantes rencontrent souvent des difficultés lorsque les données de communication sont parcimonieuses et volatiles, car elles reposent sur des caractéristiques structurelles ou des statistiques globales qui ne sont pas adaptées à de tels contextes. Elles manquent également de flexibilité pour évaluer les changements à travers des sous-structures arbitraires, ce qui limite leur applicabilité. Dans ce mémoire, nous adaptons l’algorithme Multi-Scale Anomaly Detection (MAD) au problème de la CPD dans les graphes temporels. MAD introduit une analyse probabiliste et multi-échelle des sous-graphes, produisant une fonction de score capable d’identifier des changements structurels brusques même dans des données hautement clairsemées. La méthode est flexible, car elle peut détecter des points de changement au niveau des arêtes, des noeuds ou du graphe global, et efficace, avec une complexité linéaire à la fois dans la longueur des données et dans le nombre de communications analysées. Des expériences approfondies sur des jeux de données synthétiques et réels démontrent que MAD produit des signaux de points de changement nets et cohérents. Il parvient à détecter avec succès les transitions de régime dans des réseaux de densités variées et met en évidence des transitions structurelles significatives dans des données réelles de communication et d’organisation. Ces résultats confirment que MAD constitue un cadre robuste et évolutif pour la CPD dans les graphes temporels, particulièrement efficace dans des environnements clairsemés et incertains.