Die Low-Rank-Matrix-Vervollständigung spielt eine zentrale Rolle in Anwendungen des kolaborativen Filterns; das zentrale Prinzip besteht darin, dass die Variablen in einem kleineren Unterraum liegen als der umgebende Raum. Häufig ist zusätzliche Information über die Variablen bekannt, und es ist sinnvoll anzunehmen, dass die Einbeziehung dieser Information zu besseren Vorhersagen führt. Wir behandeln das Problem der Matrix-Vervollständigung, wenn paarweise Beziehungen zwischen den Variablen über einen Graphen bekannt sind. Wir formulieren und leiten ein äußerst effizientes, auf dem konjugierten Gradienten basierendes alternierendes Minimierungsverfahren ab, das Optimierungsprobleme mit über 55 Millionen Beobachtungen bis zu zwei Größenordnungen schneller löst als aktuell beste (stochastische) Gradientenabstieg-basierte Methoden. Theoretisch zeigen wir, dass solche Ansätze verallgemeinerte Formulierungen der gewichteten Nuklearnorm umfassen, und leiten statistische Konsistenzgarantien ab. Unsere Ergebnisse werden sowohl an realen als auch an synthetischen Datensätzen validiert.