Thesis of Géraud Le Falher

Characterizing edges in signed and vector-valued graphs

We develop methods to efficiently and accurately characterize edges in complex networks. In simple graphs, nodes are connected by a single semantic. For instance, two users are friends in a social networks. Moreover, those connections are typically driven by node similarity, according to homophily. In the previous example, users become friends because of common features. By contrast, complex networks are graphs where every connection has one semantic among k possible ones. Those connections are moreover based on both partial homophily and heterophily of their endpoints. This additional information enable finer analysis of real world graphs. However, it can be expensive to acquire, or is sometimes not known beforehand. We address the problems of inferring edge semantics in various settings. First, we consider graphs where edges have two opposite semantics, and where we observe the label of some edges. These so-called signed graphs are a common way to represent polarized interactions. We propose two learning biases suited for directed and undirected signed graphs respectively. This leads us to design several algorithms leveraging the graph topology to solve a binary classification problem that we call edge sign prediction. Second, we consider graphs with k > 2 available semantics for edge. In that case of multilayer graphs, we are not provided with any edge label, but instead are given one feature vector for each node. Faced with such an unsupervised problem, we devise a quality criterion expressing how well an edge k-partition and k semantical vectors explains the observed connections. We optimize this goodness of explanation criterion in vectorial and matricial forms.

Jury

- Directeur de thèse : Marc Tommasi - Rapporteurs : Alessandro Provetti, Liva Ralaivola - Examinateurs : Elisa Fromont, Sophie Tison

Thesis of the team MAGNET defended on 16/04/2018