In this paper we revisit matrix completion for recommender systems from the point of view of link prediction on graphs. Interaction data such as movie ratings can be represented by a bipartite user-item graph with labeled edges representing observed ratings. Building on recent progress in deep learning on graph-structured data, we propose a graph auto-encoder framework based on differentiable message passing on the bipartite interaction graph. This framework can be viewed as an important first step towards end-to-end learning in settings where the interaction data is integrated into larger graphs such as social networks or knowledge graphs, circumventing the need for multistage frameworks. Our model achieves competitive performance on standard collaborative filtering benchmarks, significantly outperforming related methods in a recommendation task with side information.