Accelerated Graph Integration with Approximation of Combining Parameters

Abstract

Graph-based models offer the advantage of handling data that resides on irregular and complex structures. From various models for graph-structured data, graph-based semi-supervised learning (SSL) with label propagation has shown promising results in numerous applications. Meanwhile, with the rapid growth in the availability of data, there exist multiple relations for the same set of data points. Each relation contains complementary information to one another, and it would be beneficial to integrate all the available information. Such integration can be translated to finding an optimal combination of the graphs, and several studies have been conducted. Previous works, however, incur high computation time with a complex design of the learning process. This leads to a low capacity of applicability in multiple cases. To circumvent the difficulty, we propose an SSL-based fast graph integration method that employs approximation in the maximum likelihood estimation process of finding the combination. The proposed approximation utilizes the connection between the co-variance and its Neumann series, which allows us to avoid explicit matrix inversion. Empirically, the proposed method achieves competitive performance with significant improvements in computational time when compared to other integration methods.