ESI Talents

Sujet de Stage N°: 319

Sujet de Stage
Validation

Sujet de stage N° 319

Type*

Specialites*

Organisme*

Coencadrants*

Promoteur*

H SEBA et S LAGRAA

Email promoteur*

Tel promoteur

Intitule*

Détection d’anomalies dans un flux de graphes

Resume*

La détection d’anomalies est un domaine de recherche très actif traité par plusieurs
communautés scientifiques telles que : la sécurité informatique, la médecine, l’industrie et la
finance. De façon générale, ce problème consiste à détecter les données qui sont
significativement différentes des données bénignes ou normales. Cependant, de nos jours les
données sont de plus en plus représentées par les graphes, car ces derniers ont la faculté de
modéliser les interactions complexes de façon simple et intuitive. Le problème de la détection
dans ce cas revient à repérer les graphes qui sont différents des graphes correspondants aux
objets normaux observés par le système.
Dans ce travail, nous nous intéressons au problème de la détection d’anomalies dans un flux
de graphes (Graph Stream) (McGregor, 2014, KIOUCHE et al.,2019).
Le problème de la détection d’anomalies dans les graphes a fait l’objet de plusieurs travaux
(Akoglu et al., 2015). Cependant, la plupart des approches existantes concernent les graphes
statiques. Dans le cas des graphes dynamiques ou en flux (Streaming), des exemples de
méthodes existantes sont : détection de sous-structures aberrantes (Outliers) de Aggarwal et
al. (2011), la méthode Classy de Kostakis (2014) pour la détection de programmes malicieux
tels que les malwares. La méthode SpotLight de Eswaran et al. (2018) qui a pour but la
détection d’apparition ou de disparation soudaine d’un grand sous-graphe dans un flux de
graphes dynamiques et la méthode de Hollocou et al. (2017) pour la détection. La méthode
StreamSpot (Manzoor et al., 2016) qui détecte des graphes anormaux dans un flux d’arêtes
hétérogènes.
Des méthodes basées sur l’apprentissage dans le cas dynamique sont plus rares. On peut citer
netwalk (Yu et al., 2018).

Objectifs*

L’objectif de ce projet est d’étudier ces méthodes, de les classifier et d’étudier et évaluer de
nouvelles méthodes basées en particulier sur l’apprentissage de représentations de graphes
qui prennent en compte l’aspect dynamique des flux.

Resultats attendus*

1. Synthèse bibliographique sur les algorithmes de détection d’anomalies dans un flux
d’arêtes
2. Conception et implémentation d’une nouvelle approche de détection d'anomalies
3. Evaluation des algorithmes sur des benchmarks, et validation de la méthode proposée par les tests

Antecedents

Moyens informatiques

Echeancier*

1. Etude et compréhension des algorithmes de détection d’anomalies dans un flux
d’arêtes (3 mois)
2. Conception et implémentation d’une nouvelle approche (2 mois)
3. Implémentation de méthodes existantes  (2 mois)
3. Tests et évaluation des algorithmes sur des benchmarks (2 mois)

Bibliographie

Aggarwal, C. C., P. S. Yu, et Y. Zhao (2011). Outlier detection in graph streams. In 2011
IEEE 27th International Conference on Data Engineering(ICDE), Volume 00, pp. 399–
409.
Akoglu, L., H. Tong, et D. Koutra (2015). Graph based anomaly detection and
description : A survey. Data Min. Knowl. Discov. 29(3), 626–688.
Eswaran, D., C. Faloutsos, S. Guha, et N. Mishra (2018). Spotlight : Detecting anomalies
in streaming graphs. In Proceedings of the 24th ACM SIGKDD International Conference
on Knowledge Discovery &#38; Data Mining, KDD ’18, New York, NY, USA, pp. 1378–
1386.
Hollocou, A., J. Maudet, T. Bonald, et M. Lelarge (2017). A streaming algorithm for
graph clustering. CoRR abs/1712.04337.
KIOUCHE, Abd Errahmane, AMROUCHE, Karima, SEBA, Hamida, et LAGRAA, Sofiane.
Une nouvelle approche pour la détection d’anomalies dans les flux de graphes
hétérogènes. In : Extraction et Gestion des Connaissances : Actes de la conférence
EGC'2019. BoD-Books on Demand, 2019.
Kostakis, O. (2014). Classy : fast clustering streams of call-graphs. Data Mining and
Knowledge Discovery 28(5), 1554–1585.
Manzoor, E., S. M. Milajerdi, et L. Akoglu (2016). Fast memory-efficient anomaly
detection in streaming heterogeneous graphs. In Proceedings of the 22Nd ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining, pp. 1035–1044.
McGregor, A. (2014). Graph stream algorithms : A survey. SIGMOD Rec. 43(1), 9–20.
Perozzi, B., L. Akoglu, P. Iglesias Sánchez, et E. Müller (2014). Focused clustering and
outlier detection in large attributed graphs. In Proceedings of the 20th ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining, pp. 1346–1355.
W. Yu, W. Cheng, C. C. Aggarwal, K. Zhang, H. Chen, W. Wang, Netwalk: A flexible deep
embedding approach for anomaly detection in dynamic networks, in: Proceedings of
the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining, KDD’18, Associa555 tion for Computing Machinery, New York, NY, USA, 2018,
p. 26722681. doi:10.1145/3219819.3220024.

Statut validation*

Reponse aux experts

Nous avons spécifier l'échéancier du PFE sur 9 mois tel que demandé

Reserve pour*

Projet recherche

Notification

Avis sur le Sujet de Stage

Intitule	Organisme	Debut	Fin	Avis	Commentaire
Détection d’anomalies dans un flux de graphes	LCSI : Laboratoire de la Communication dans les Systèmes Informatiques	09/15/2020	09/30/2020	Avis favorable	—
Détection d’anomalies dans un flux de graphes	LCSI : Laboratoire de la Communication dans les Systèmes Informatiques	09/15/2020	09/23/2020	Avis favorable	—
Détection d’anomalies dans un flux de graphes	LCSI : Laboratoire de la Communication dans les Systèmes Informatiques	10/07/2020	10/07/2020	Avis favorable	—
Détection d’anomalies dans un flux de graphes	LCSI : Laboratoire de la Communication dans les Systèmes Informatiques	10/01/2020	10/01/2020	Avis favorable avec réserves mineures	Merci de renseigner l'échéancier détaillé sur au moins 9 mois.