낮은 랭크 행렬 완성(low rank matrix completion)은 협업 필터링 응용 분야에서 핵심적인 역할을 하며, 핵심 아이디어는 변수들이 환경 공간(ambient space)보다 더 작은 부분공간에 존재한다는 점이다. 일반적으로 변수에 대한 추가 정보가 존재하며, 이러한 정보를 활용할 경우 더 정확한 예측이 가능하다는 가정은 타당하다. 본 연구에서는 변수 간의 쌍별 관계가 그래프(graph) 형태로 알려진 경우의 행렬 완성 문제에 대해 다룬다. 우리는 매우 효율적인 공액 경사법 기반의 대체 최소화(Alternating Minimization) 알고리즘을 제안하고, 이를 통해 5,500만 개 이상의 관측치를 포함하는 최적화 문제를 기존 최첨단(스토캐스틱) 경사 하강법 기반 방법보다 최대 2자리 수(100배) 빠르게 해결한다. 이론적으로는 이러한 방법이 가중 핵노름(weighted nuclear norm) 공식화의 일반화임을 보이며, 통계적 일관성(statistical consistency) 보장을 도출한다. 제안된 방법의 성능은 실제 데이터 및 합성 데이터를 활용한 실험을 통해 검증되었다.