ESTIM: Efficient and Scalable Tensorial Incomplete Multi-view Semi-supervised Classification

Due to hardware limitations, the dual missing problem with absent views and scarce labels often occurs in multi-view semi-supervised learning (MvSSL), challenging their real-world applications. To solve it, traditional tensor-based methods introduced a third-order tensor to recover the local structures of missing data and existing MvSSL methods have adopted label propagation to enhance the label information of unlabeled data. However, the computational complexity of these methods is cubically dependent on the scale of instances, which severely hampers the scalability to large-scale data. To address these issues, we propose an Efficient and Scalable Tensorial Incomplete Multi-view semi-supervised classification named ESTIM. Specifically, we first replace sample-level graphs with compact bipartite graphs, and then design tensorial graph imputation to explore high-order cross-view information and recover the missing values. Besides, a consensus bipartite graph fusion scheme is designed to align bipartite graphs across views and learn a robust consensus graph against the distorted local structure in label propagation. Moreover, to solve the formulated objective, we derive an efficient optimization algorithm with theoretically proved convergence, whose time complexity is sublinear to the sample sizes. Finally, experimental results across diverse datasets demonstrate the superiority of our ESTIM.