La complétion de matrices à faible rang joue un rôle fondamental dans les applications de filtrage collaboratif, l'idée centrale étant que les variables sont contenues dans un sous-espace de dimension inférieure à celle de l'espace ambiant. Souvent, des informations supplémentaires sur les variables sont disponibles, et il est raisonnable de supposer qu’intégrer ces informations permet d’obtenir des prédictions améliorées. Nous abordons le problème de la complétion de matrices lorsque des relations par paires entre les variables sont connues, via un graphe. Nous formulons et dérivons un schéma d’optimisation très efficace, basé sur la méthode du gradient conjugué et minimisation alternée, capable de résoudre des problèmes d’optimisation comportant plus de 55 millions d’observations, jusqu’à deux ordres de grandeur plus rapidement que les méthodes d’état de l’art basées sur la descente de gradient (stochastique). Du point de vue théorique, nous montrons que ces méthodes généralisent les formulations au noyau nucléaire pondéré, et établissons des garanties de cohérence statistique. Nos résultats sont validés sur des jeux de données réels et synthétiques.