DS07 - Société de l'information et de la communication

Efficiency and Structure in Graph Mining Applications – ESIGMA

Submission summary

As a general modelling tool, graphs are gaining increasing attention. They capture the interactions of enti- ties in an easily comprehensible way and yet provide a rich model of the underlying structure. As information technology scrapes up ever more data in diverse areas of human activities, it becomes vital to discover mean- ingful information from the massive amounts of available data. Data sets can be naturally depicted as graphs, and characteristic examples include web graphs, internet topologies, social networks, and text corpora. This is the central theme of graph mining, whose applications can be found in many areas such as computer vision, bioinformatics, sociology, and cognitive science.

In the meanwhile, graph theory and algorithm design with provable bounds, as a field of theoretical com- puter science, witnessed considerable advances during the last decades. Most of interesting computational problems are intractable and thus we cannot expect to have algorithms which, ideally, solve such problems both efficiently and exactly. Approximation and parameterized algorithms are prominent frameworks for designing algorithms with (mathematically) provable bounds on running time and performance guarantee. Modern graph theory offers rich results, from which algorithm design has largely benefited as well.

Graph data that arise in real-world applications are often highly structured. Consequently, to learn and analyze this structure is an important issue when dealing with such data sets, especially when the graph data are huge. This project aims to forge a structural viewpoint for handling graph data so that algorithms can be de- signed and analyzed on a structure-aware principle rather than ad-hoc approaches with empirical warrant. The novelty of this project is that, to this aim, we deploy knowledge from graph theory and theoretical algorithm design/analysis frameworks. In particular, we will use graph theory as a guideline to navigate the various structural aspects of graph data, and take advantage of theoretical algorithms analysis in order to implement/discern such structure embedded in algorithm design.

In this project, we shall study diverse facets of structure in graph data, which involve (a) their global structural aspects (b) their structure-aware succinct representation, and (c) structural resemblance between graphs. We will also tackle topics that are requested for concrete applications such as identifying influential nodes in information spreading process and detecting an event on social media stream, and examine structure emerging in the relevant contexts. Such application-driven study of structure can benefit from methodologies as in (a), (b), and (c), but also would extensively require data- and instance-specific knowledge.

This project inherently calls for interdisciplinary collaboration. Our consortium comprises strong expertise in domains pertinent to the goal and methodologies of this project, including machine learning/graph mining, bioinformatics, structural graph theory, algorithms design and analysis.

Project coordination

Michalis VAZIRGIANNIS (Laboratoire d'informatique de l'École polytechnique)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.


CNRS-LIRMM Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier
LAMSADE Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
LIX Laboratoire d'informatique de l'École polytechnique

Help of the ANR 408,191 euros
Beginning and duration of the scientific project: March 2018 - 48 Months

Useful links

Explorez notre base de projets financés



ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter