Face au déluge actuel de données principalement non structurées, les graphes ont démontré, dans une variété de domaines scientifiques, leur importance croissante comme language abstrait pour décrire des interactions complexes entre des objets complexes. L’un des principaux défis posés par l’étude de ces réseaux est l’inférence de propriétés macroscopiques à grande échelle, affectant un grand nombre d’objets ou d’agents, sur la seule base des interactions microscopiquesqu’entretiennent leurs constituants élémentaires. La physique statistique, créée précisément dans le but d’obtenir les lois macroscopiques de la thermodynamique à partir d’un modèle idéal de particules en interaction, fournit une intuition décisive dans l’étude des réseaux complexes.Dans cette thèse, nous utilisons des méthodes issues de la physique statistique des systèmes désordonnés pour mettre au point et analyser de nouveaux algorithmes d’inférence sur les graphes. Nous nous concentrons sur les méthodes spectrales, utilisant certains vecteurs propres de matrices bien choisies, et sur les graphes parcimonieux, qui contiennent une faible quantité d’information. Nous développons une théorie originale de l’inférence spectrale, fondée sur une relaxation de l’optimisation de certaines énergies libres en champ moyen. Notre approche est donc entièrement probabiliste, et diffère considérablement des motivations plus classiques fondées sur l’optimisation d’une fonction de coût. Nous illustrons l’efficacité de notre approchesur différents problèmes, dont la détection de communautés, la classification non supervisée à partir de similarités mesurées aléatoirement, et la complétion de matrices. / In an era of unprecedented deluge of (mostly unstructured) data, graphs are proving more and more useful, across the sciences, as a flexible abstraction to capture complex relationships between complex objects. One of the main challenges arising in the study of such networks is the inference of macroscopic, large-scale properties affecting a large number of objects, based solely on he microscopic interactions between their elementary constituents. Statistical physics, precisely created to recover the macroscopic laws of thermodynamics from an idealized model of interacting particles, provides significant insight to tackle such complex networks.In this dissertation, we use methods derived from the statistical physics of disordered systems to design and study new algorithms for inference on graphs. Our focus is on spectral methods, based on certain eigenvectors of carefully chosen matrices, and sparse graphs, containing only a small amount of information. We develop an original theory of spectral inference based on a relaxation of various meanfield free energy optimizations. Our approach is therefore fully probabilistic, and contrasts with more traditional motivations based on the optimization of a cost function. We illustrate the efficiency of our approach on various problems, including community detection, randomized similarity-based clustering, and matrix completion.

La description détaillée des systèmes désordonnés et vitreux représente un défi central en physique statistique et de la matière condensée, puisqu'à ce jour il n'existe pas de théorie unique et établie permettant de comprendre ces systèmes, pourtant omniprésents.Ce travail de recherche est lié en particulier à l'étude des matériaux vitreux à basse température. Plus précisément, si l'on considère des systèmes formés par un ensemble de particules athermiques avec des interactions répulsives de portée finie, en augmentant la densité, on peut observer une transition dite d'encombrement ("jamming"). Celle-ci consiste en un blocage des degrés de liberté accompagné par une augmentation spectaculaire de la rigidité du matériau.Nous étudierons ce problème à l’aide d’une analogie formelle entre des modèles de sphères et le perceptron, un modèle théorique qui développe une transition d'encombrement et des phénomènes de frustration typiques des systèmes désordonnés.En tant que modèle en champ moyen, il permet d'obtenir des résultats analytiques précis et généralisables à des systèmes à haute dimension.L'enjeu majeur de cette étude est de reconstruire le spectre des modes de vibration et toutes les propriétés pertinentes d'une phase spécifique (correspondant au régime dit des sphères dures).Dans ce cadre, nous dériverons le potentiel effectif en fonction des paramètres d'ordre du modèle et nous montrerons qu'il est dominé à proximité du point de jamming par une interaction logarithmique non triviale, qui clarifiera le lien entre les forces de contact et les distances moyennes entre les particules, dans la région critique et au-delà.Comprendre pleinement la transition d'encombrement et les propriétés du perceptron nous permettra de faire des progrès dans plusieurs domaines reliés. En premier lieu, cela peut conduire à une théorie complète des systèmes amorphes, à la fois en dimension infinie et en dimension finie.De plus, le modèle du perceptron semble avoir un lien étroit avec des problèmes dits de Von Neumann. En effet, les systèmes biologiques et écologiques développent souvent des propriétés liées à une condition pseudo-critique en mettant en oeuvre des mécanismes d'optimisation de ressource-consommation.Est-il possible d'identifier un régime caractérisé par une brisure de symétrie? Quel serait le spectre de fluctuations d'énergie dans ces systèmes?Ce ne sont que quelques-unes des questions auxquelles nous essayerons de répondre dans cette thèse.Cependant, l'approximation de champ moyen peut parfois fournir des informationsincorrectes ou trompeuses, en particulier dans l'étude de certaines transitions de phase et la détermination des dimensions critiques inférieure et supérieure.Afin d'avoir une vue d'ensemble et pouvoir manipuler correctement des systèmes en dimension finie, dans la suite de la thèse nous discuterons comment obtenir un développement perturbatif systématique, applicable à tout modèle, à condition que ce dernier soit défini sur un réseau ou un graphe biparti.Notre motivation est en particulier liée à la possibilité d'étudier certaines transitions de phase du second ordre qui existent sur le réseau de Bethe - c'est-à-dire un réseau en arbre sans boucles dont chaque noeud a une connectivité fixe - mais qui sont qualitativement différentes ou absentes dans le modèle entièrement connecté correspondant. / The detailed description of disordered and glassy systems represents an open problem in statistical physics and condensed matter. As yet, there is no single, well-established theory allowing to understand such systems. The research presented in this thesis is related in particular to the study of glassy materials in the low-temperature regime. More precisely, considering systems formed by athermal particles subject to repulsive short-range interactions, upon progressively increasing the density, a so-called jamming transition can be detected. It entails a freezing of the degrees of freedom and hence a huge increase of the material rigidity.We shall study this problem in view of a formal analogy between sphere models and the perceptron, a theoretical model undergoing a jamming transition and frustration phenomena typical of disordered systems. Being a mean-field model, it allows to obtain exact analytical results, which are generalizable to more complex high-dimensional settings.The main aim is to reconstruct the vibrational spectrum and all the relevant properties of a specific phase of the perceptron, corresponding to the hard-sphere regime.In this framework, we will derive the effective potential as a function of the gaps between and forces among the particles, and we will show that it is dominated by a non-trivial logarithmic interaction near the jamming point. This interaction in turn will clarify the relations existing between the relevant variables of the system, in the critical jamming region and beyond.Understanding the jamming transition and the perceptron properties will allow us to make progress in several related fields. First, this study could lay part of the groundwork towards a complete theory of amorphous systems, in both infinite and finite dimensions. Furthermore, the perceptron model seems to a have a close connection with the so-called Von Neumann problems. Indeed, biological and ecological systems often develop pseudo-critical properties and give rise to general mechanisms of resource-consumption optimisation.Is the identification of a broken symmetry regime possible? What would it yield in terms of the spectrum of the energy fluctuations?These are just a few questions we shall attempt to answer in this context.However, the mean-field approximation can sometimes provide wrong or misleading information, especially in studying certain phase transitions and determining the exact lower and upper critical dimensions. To have a broad perspective and correctly deal with finite-dimensional systems, in the second part of the thesis we will discuss obtaining a systematic perturbative expansion which can be applied to any model, as long as defined on a lattice or a bipartite graph.Our motivation is in particular due to the possibility of studying relevant second-order phase transitions which exist on the Bethe lattice — a lattice with a locally tree-like structure and fixed connectivity for each node — but which are qualitatively different or absent in the corresponding fully-connected version.