Multiple graph regularized graph transduction via greedy gradient Max-Cut

Graph transduction methods have been widely adopted for label prediction under semi-supervised settings. To alleviate the relevant sensitivity to initial labels and graph construction processes, recent studies have been aiming at developing robust graph transduction techniques. In particular, the graph transduction method via greedy gradient Max-Cut (GGMC) that minimizes a cost function over a continuous classification function and a binary label variable has been successfully applied to a wide range of applications. However, this method predominately relies on the choice of a high-quality single graph representation, often leading to unstable performance due to selection bias. To tackle this major drawback, we leverage an ensemble learning framework into the GGMC method for exploiting the advantage of constructing and combining multiple graphs. As opposed to performing constrained Max-Cut on a single graph, the proposed multiple graph greedy gradient Max-Cut method (MG-GGMC) simultaneously solves the label prediction and the true graph estimation problems. Specifically, the true graph is approximated by a linear combination of a set of constructed graphs. The coefficients of the linear combination are learned automatically by alternately minimizing a unified objective function in an iterative manner. Comparison studies with representative methods across various real-world benchmarks conspicuously demonstrate the efficaciousness and the superiority of the proposed algorithm in standard evaluation metrics.