  We consider a Canonical Polyadic (CP) decomposition approach to low-rank
tensor completion (LRTC) by incorporating external pairwise similarity
relations through graph Laplacian regularization on the CP factor matrices. The
usage of graph regularization entails benefits in the learning accuracy of
LRTC, but at the same time, induces coupling graph Laplacian terms that hinder
the optimization of the tensor completion model. In order to solve
graph-regularized LRTC, we propose efficient alternating minimization
algorithms by leveraging the block structure of the underlying CP
decomposition-based model. For the subproblems of alternating minimization, a
linear conjugate gradient subroutine is specifically adapted to
graph-regularized LRTC. Alternatively, we circumvent the complicating coupling
effects of graph Laplacian terms by using an alternating directions method of
multipliers. Based on the Kurdyka-{\L}ojasiewicz property, we show that the
sequence generated by the proposed algorithms globally converges to a critical
point of the objective function. Moreover, the complexity and convergence rate
are also derived. In addition, numerical experiments including synthetic data
and real data show that the graph regularized tensor completion model has
improved recovery results compared to those without graph regularization, and
that the proposed algorithms achieve gains in time efficiency over existing
algorithms.
