Change Point Detection in Temporal Graphs

Abstract

Temporal graphs provide a natural framework for modeling complex systems where relationships between entities evolve over time. Detecting the moments when these structures undergo significant changes referred to as change points is crucial for understanding regime shifts in domains such as social networks, communication systems, financial markets, and large scale online collaborations. Traditional change detection techniques, developed mainly for time series, are not sufficient to capture the relational and dynamic nature of graphs. This has motivated the development of methods specifically tailored to temporal graphs, where changes correspond to structural modifications in the underlying network. This thesis presents a literature review of representative approaches for change point detection in temporal graphs, focusing specifically on methods that operate on graph snapshot series. This study examines seven methods, spanning different methodological families such as spectral analysis, probabilistic modeling, similarity-based techniques, and neural representation learning. By synthesizing these contributions, this work provides a structured overview of the field and highlights the challenges and perspectives for future research in change point detection for temporal graphs.***

Les graphes temporels offrent un cadre naturel pour modéliser des systèmes complexes où les relations entre entités évoluent au fil du temps. Détecter les moments où ces structures subissent des changements importants appelés points de changement est essentiel pour comprendre les transitions de régime dans des domaines tels que les réseaux sociaux, les systèmes de communication, les marchés financiers et les collaborations en ligne à grande échelle. Les techniques classiques de détection de changements, développées principalement pour les séries temporelles, ne suffisent pas à capturer la nature relationnelle et dynamique des graphes. Cela a motivé le développement de méthodes spécifiquement adaptées aux graphes temporels, où les changements correspondent à des modifications structurelles du réseau sous jacent. Ce mémoire présente une revue de littérature sur des approches représentatives de la détection de points de changement dans les graphes temporels, en se concentrant sur les méthodes qui fonctionnent à partir de séries d’instantanés de graphes. Cette étude examine sept méthodes, couvrant différentes familles méthodologiques telles que l’analyse spectrale, la modélisation probabiliste, les techniques basées sur la similarité et l’apprentissage de représentations neuronales. En synthétisant ces contributions, ce travail propose une vue d’ensemble structurée du domaine et met en évidence les principaux défis ainsi que des perspectives pour les recherches futures en détection de points de changement dans les graphes temporels.