ESI Talents

Sujet de Stage N°: 317

Sujet de Stage
Validation

Sujet de stage N° 317

Type*

Specialites*

Organisme*

Coencadrants*

Promoteur*

AMROUCHE K et SEBA H (Université Lyon 1)

Email promoteur*

Tel promoteur

Intitule*

Esquisse de grands graphes

Resume*

Avec l'énorme quantité de données produites par les activités humaines de nos jours, le problème de données massives (Big data) est devenu un enjeu essentiel. Un des outils efficaces pour traiter ces données est l’utilisation de graphes ou réseaux. Les graphes sont des outils de modélisation utilisés dans beaucoup de domaines pour la représentation des données : réseaux sociaux et de communication (entités reliées entre elles par des liens physiques ou communautaires), chimie (relations entre les atomes), biologie (interactions entre protéines par exemple), etc. 
Les graphes d’applications réelles, comme les réseaux sociaux, sont des graphes dynamiques qui ne cessent de changer. Pour certaines applications, ils sont traités en flux (Stream) et la problématique principale est de construire une esquisse (sketch) qui peut être maintenue en mémoire et utiliser pour le traitement. Cette esquisse retient une partie ou toutes les propriétés du graphe initial.
 Dans ce projet, nous nous intéressons à ces méthodes de sketching pour évaluer leur capacité à compresser un grand graphe. 
Remarque: L’étudiant bénéficiera, s’il le souhaite, d’un stage gratifié d’une durée de 5 mois à l’université Lyon 1, France

Objectifs*

Le but de ce travail est d’analyser les méthodes  de sketching et de les comparer entre elles et de proposer de nouvelles méthodes plus adaptées aux grands graphes.

Resultats attendus*

- synthèse bibliographique sur les méthodes de sketching
- proposition d'une ou plusieurs méthodes de sketching
- implémentation des solutions proposées et intégration à la plateforme du projet avec une interface adéquate
-validation et expérimentation sur plusieurs benchmarks

Antecedents

PFE a l'ESI: 2017-2018: Algorithmes de compression de graphes : Étude et implémentation

PFE a l'ESI 2018-2019; Algorithmes de compression de graphes par extraction de motifs et les arbres k2-trees : Étude et implémentation

Moyens informatiques

Echeancier*

Le projet est organisé autour de 4 tâches  :
1 : Etude et compréhension des solutions de graph sketching avec ou sans apprentissage. Nous considérerons les graphes entiers et les flux d’arêtes. (3 mois)
2 : proposition de nouvelles méthodes plus performantes (2 mois)
3 : Implémentation de l’approche proposée et comparaison avec l’existant. L’implémentation se fera en C++ avec la librairie SNAP. (3 mois)
4 : Analyse des méthodes sur la base d’une comparaison des résultats obtenus sur plusieurs benchmarks (1 mois)

Bibliographie

[1] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: Sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’12, pages 5–14, New York, NY, USA, 2012. Association for Computing Machinery.
[2] Takuya Akiba and Yosuke Yano. Compact and scalable graph neighborhood sketching. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pages 685–694, New York, NY, USA, 2016. Association for Computing Machinery.
[3] Bortik Bandyopadhyay, David Fuhry, Aniket Chakrabarti, and Srinivasan Parthasarathy. Topological graph sketching for incremental and scalable analytics. In Proceedings of the 25th ACM International on Conference on Information and Knowl-edge Management, CIKM ’16, pages 1231–1240, New York, NY, USA, 2016. Association for Computing Machinery.
[4] Benjamin W. Priest. Degreesketch: Distributed cardinality sketches on massive graphs with applications, 2020.
[5] Dingqi Yang, Paolo Rosso, Bin Li, and Philippe Cudre-Mauroux. Nodesketch: Highly-efficient graph embeddings via recursive sketching. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’19, pages 1162–1172, New York, NY, USA, 2019. Association for Computing Machinery.

Statut validation*

Reponse aux experts

Nous avons apporté les modifications demandées suite aux réserves soulevées par les experts, a savoir:
- détailler la problématique (voir résumé)
- ajouter dans le sujet la proposition de nouvelles méthodes de sketching
- renseigner les objectifs et les résultats attendus
- pour les références bibliographiques, on avait mis les references vers des articles, neanmoins dans cette nouvelle version nous avons precisee les articles 9le titre, les auteurs, etc.)

Reserve pour*

Projet recherche

Notification

Avis sur le Sujet de Stage

Intitule	Organisme	Debut	Fin	Avis	Commentaire
Esquisse de grands graphes	LIRIS : Laboratoire d'Informatique en Image et Systemes d'Information, INSA de Lyon	09/15/2020	09/30/2020	Avis favorable	—
Esquisse de grands graphes	LIRIS : Laboratoire d'Informatique en Image et Systemes d'Information, INSA de Lyon	09/15/2020	09/23/2020	Avis favorable avec réserves mineures	Détailler plus la problématique
Esquisse de grands graphes	LIRIS : Laboratoire d'Informatique en Image et Systemes d'Information, INSA de Lyon	09/15/2020	09/21/2020	Avis favorable avec réserves majeures	Le sujet est plus orienté recherche. C'est plus une synthèse bibliographique + intégration d'une méthode existante dans une plate forme existante. En tant q'un projet de fin d'étude, une contribution en termes de proposition, conception et implémentation d'une nouvelle solution est primordiale. Comparer les résultats obtenus avec ceux des PFEs antérieurs est appréciable, cependant, il fallait rappeler ce qui a été fait dans ces travaux Il faut renseigner les parties ( champs) : objectifs et résultats attendus Enfin, il faut enrichir la bibliographie par des documents tels que , articles, livres, thèses ( les références actuelles sont toutes des sites web)
Esquisse de grands graphes	LIRIS : Laboratoire d'Informatique en Image et Systemes d'Information, INSA de Lyon	09/23/2020	09/23/2020	Avis favorable	—