Efficient iterative methods for clustering and matching problems on graphs ; Méthodes itératives efficientes pour des problèmes de classification et d'appariement de graphes

Graph structured datasets arise naturally in many fields including biology with protein-to-protein interaction networks, ecology with predator-prey networks and economy with financial market networks. In order to extract relevant information from these networks, one often uses clustering methods to gather nodes having similar connectivity patterns into communities. Numerous clustering algorithms have been proposed in the past decade and have been analyzed under the Stochastic Block Model (SBM), a popular random graph model. However, in practice, one often has access to side information, and it is typically unclear how this information can be incorporated in existing methods and to what extent it can help to improve the clustering performance.We will first address this question under the Contextual SBM (CSBM) -- a simple extension of the SBM with independent Gaussian covariates associated to each nodes -- and propose an iterative refinement method that is fast and achieves the information theoretic threshold for exact recovery. Our method is inspired by the Generalized Power Method (GPM) and principles of EM type algorithms.Next, we extend the method in order to be applied to networks with heterogeneous degrees or mixed-membership, but also with different kind of covariates like multilayer graphs with possibly missing values, or high dimensional bipartite graphs, hence showing the flexibility of the approach.Lastly, we consider the graph matching problem where the additional graphs can be considered as correlated side information. We show that we can also use the GPM for this problem to significantly improve the matching obtained by state-of-the art methods, and provide consistency guarantees for the GPM under the Correlated Wigner Model (CoWM). ; Des données structurées sous forme de graphe apparaissent naturellement dans de nombreux domaines comme la biologie avec les réseaux d'interaction protéine-protéine, l'écologie avec les réseaux proie-prédateur ou l'économie avec les réseaux financiers. Afin d'extraire ...