**Offre en lien avec l’Action/le Réseau :** – — –/Doctorants

Laboratoire/Entreprise : LITIS

Durée : 36 months

Contact : phd-gan_graphs@litislab.fr

Date limite de publication : 2020-09-01

**Contexte :**

## Position Details

* Location The research will be conducted at LITIS Laboratory (Rouen, France) in Normandy.

The LITIS (EA 4108) is affiliated to Normandie University, University of Rouen and INSA Rouen

Normandie, and founding member of the CNRS Research Federation NormaSTIC.

*Supervisors:

– Benoit Gaüzère, LITIS, INSA Rouen http://pagesperso.litislab.fr/∼bgauzere

– Paul Honeine, LITIS, University of Rouen http://honeine.fr/

* Start date September or October 2020 (or earlier)

* Duration 36 months

**Sujet :**

Graphs are a powerful and versatile data structure useful to encode

many real-world data, such as networks, molecules and

documents. However, their flexibility comes with some drawbacks

including the complexity associated to elementary operations. For

instance, deciding if two graphs are isomorphic (i.e., structurally

equivalent) or computing a distance between two graphs are NP-Complete

problems, and even hard to approximate. Considering this, several

strategies have been proposed to find some workarounds in order to be

able to process graphs and use them in the Machine Learning

pipeline. The simplest strategy is the explicit embedding of graphs to

an Euclidean space [1], at the cost of losing information. To

overcome this drawback, two major strategies have been recently

investigated. The first one is improving the embedding through kernels

defined on graphs [2,3]. The second and more recent strategy is the

definition of Graph Neural Networks (GNNs) operating directly on

graphs [4–8]. Using neural networks on graphs allows to learn a

proper embedding of graphs given a problem to solve, and then

alleviate the drawbacks of defining a priori an ad hoc embedding.

These embedding-based methods have been commonly investigated for

supervised learning tasks, essentially classification and

regression. However, their interpretability is one major

drawback. Moreover, they were not efficient in many unsupervised

learning tasks, such as estimating the data centroid in k-means or

more generally generating a graph prototype (one graph representative

of a set of graphs, e.g. a median graph). The main reason is the curse

of the preimage, since one needs to reconstruct the solution in the

graph-data space. The preimage problem has already been addressed in

various domains, mainly for kernel-based methods [9,10]. However,

solving this problem for structured data remains an open problem and

only very few attempts have been made on strings and some particular

class of graphs [11]. The purpose of this PhD thesis is to alleviate

the bottlenecks associated to the preimage problem on graphs, through

the use of Generative Adversarial Network (GAN) [12, 13]. GANs

consists of two parts. First, the encoder aims to embed graphs to an

Euclidean space of a predefined dimension. This can be implemented

using existing GNNs and kernel-based methods. Second, the decoder

part aims to reconstruct a graph given a vectorial representation. It

may be considered as the inverse function of the encoder part. The

purpose here is to define this decoder part to take Euclidean spaces

as input and graphs as output, i.e., structured data. By investigating

this approach, the PhD candidate will study particularly molecular

generation.

**Profil du candidat :**

Required skills

• Master in Applied Mathematics, Computer Science, Data Science, or equivalent

• Experience in Python programming

• Skills in graph theory, neural networks or graph-based methods constitute an advantage

**Formation et compétences requises :**

Required skills

• Master in Applied Mathematics, Computer Science, Data Science, or equivalent

• Experience in Python programming

• Skills in graph theory, neural networks or graph-based methods constitute an advantage

**Adresse d’emploi :**

LITIS,

avenue de l’université,

76800 St Etienne du Rouvray

**Document attaché : **202004071235_offre.pdf