months on graph sketching for anomaly detection in graph streams.
The student can start on march.
*****************************
*Contact :Hamida SEBA (hamida.seba@univ-lyon1.fr)*
*Location: University Lyon 1, Lyon France*
*Description:*
Dynamic graphs, and graph streams, represent one of the most widely used
solutions in modeling data produced by systems that change over time. It
is generally a large and interconnected data that can be found in
several applications including: cyber-security, finance, social
networks, computer systems etc. A dynamic graph is a graph whose
structure changes over time (i.e., at an instant $t$, we will only have
a partial view of the graph). At each instant $t$, an event of deletion
or addition of an element (node, edge, label or weight) of the graph
could take place.
In this project, we are interested in the study of anomaly detectors in
graph streams. Typically, an anomaly detector identifies parts of the
system that are significantly different from other parts. The existence
of these elements may be due to an abnormal activity such as a cyber-
attack, as it may simply represent an event of interest to the system
under study. In a graph stream, an anomaly can have several forms: an
edge which should not exist between two nodes, a node different from the
other nodes, a subgraph denser than the rest of the graph, etc.
In this problem, the main task is to build a sketch of the graph or part
of it that can be kept in memory and used for processing. This sketch
retains some or all of the properties of the initial graph.
In this project, we are interested in these sketching methods to
evaluate their ability to represent a graph stream in the context of
anomaly detection.
References related to the project :__
[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.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
