Recently, there has been increasing interest for easy and reliable generation of 3D animated models facilitating several real-time applications. In most of these applications, the reconstruction of soft body animations is based on time-varying point clouds which are irregularly sampled and highly incomplete. To overcome these imperfections, we introduce a novel reconstruction technique, using graph-based matrix completion approaches. The presented method exploits spatio-temporal coherences by implicitly forcing the proximity of the adjacent 3D points in time and space. The proposed constraints are modeled by using the weighted Laplacian graphs and are constructed from the available points. Extensive evaluation studies, carried out using a collection of different highly-incomplete dynamic models, verify that the proposed technique achieves plausible reconstruction output despite the constraints posed by arbitrarily complex and motion scenarios.