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
Résumé
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 une information pertinente de ces réseaux, on a souvent recours à des méthodes de classification qui regroupent entre eux les nœuds ayant un profil de connectivité similaire. Durant les vingt dernières années, de nombreux algorithmes de classification ont été proposés et analysés lorsque le graphe est généré par un modèle à blocs stochastiques (SBM). Mais en pratique, on a souvent accès à de l'information auxiliaire. Il n'est toutefois pas bien compris comment cette information auxiliaire peut-être incorporée par les méthodes existantes, et dans quelle mesure elle peut aider à améliorer les résultats de la classification.Dans un premier temps nous allons résoudre ce problème en s'appuyant sur un modèle génératif simple - le modèle à blocs stochastiques contextuel (CSBM) - qui ajoute à chaque nœud d'un graphe généré par un SBM des covariables gaussiennes. Nous proposons une méthode itérative rapide qui atteint le seuil théorique d'information pour le recouvrement exact des communautés latentes. Notre méthode s'inspire de la méthode de la puissance généralisée (GPM) ainsi que des algorithmes de type EM.Nous étendons ensuite la méthode à des graphes ayant des nœuds avec des degrés hétérogènes ou appartenant à plusieurs communautés, ainsi qu'à des covariables de différentes natures, comme par exemple des réseaux multicouches avec des valeurs manquantes ou des graphes bipartites en grande dimension.Enfin, nous considérons le problème d'appariement de graphes dans lequel le graphe additionnel peut être considéré comme de l'information auxiliaire corrélée. Nous montrons que l'on peut également utiliser une stratégie basée sur GPM pour améliorer de manière significative un appariement initial imparfait. Nous établissons des garanties de consistance de l'algorithme sous le modèle de Wigner corrélé (CoWM).
Origine : Version validée par le jury (STAR)