Discovering similarities between unstructured data

Networks are a powerful tool to represent systems of interacting data in an enormous range of real-world applications. Complex network theory provides a versatile and adaptative framework to model and analyse various systems from very different fields, making discoveries in this theory potential breakthroughs impacting many applicative areas.

It is often useful to assess the similarity between graphs in order to identify common actors in varied situations. Applications include the prediction of therapeutic effects of a molecule, detecting malware, or finding controversy within Wikipedia. This problem is connected to the very well-studied problem of graph isomorphism (i.e. detecting whether two graphs are topologically identical), for which no polynomial time algorithms exists, leading existing approaches to fail to scale to large networks.

Assessing similarity requires a careful characterisation of the properties that graphs must share to be considered similar. Those common properties generally rely on graph topological features, possibly enriched by other sources of information, e.g. outside expertise. One widely used way of defining a (topological) similarity is to map the graphs node sets so that most of the edges are preserved-a pair of edges whose both end nodes are mapped are preserved.

This is of particular interest because mapping node sets from different networks enables one to infer knowledge from network to network. This Graph Alignment (GA) problem is known to have a complexity that grows exponentially with the size of the graphs. Thus, many heuristics have been proposed to approximatively solve it.

Some use a node's structural role to create embeddings. Others try to find permutations to maximise a measure of similarity using optimisation tools. Both approaches generally have high computational cost and existing algorithms are mainly designed for networks in which interactions are symmetric.

The focus of this PhD is on adapting existing GA methods and developing new approaches so that they can handle large-scale (~1M of node), directed (i.e. nonsymmetric) networks and represents a potential breakthrough for many real-world applications.