Forging The Graphs: A Low Rank and Positive Semidefinite Graph Learning Approach
Dijun Luo, Heng Huang, Feiping Nie, Chris H. Q. Ding · 2012
In many graph-based machine learning and data mining approaches, the quality of the graph is critical. However, in real-world applications, especially in semi-supervised learning and unsupervised learning, the evaluation of the quality of a graph is often expensive and sometimes even impossible, due the cost or the un-availability of ground truth. In this paper, we proposed a robust approach with convex optimization to “forge ” a graph: with an input of a graph, to learn a graph with higher quality. Our major concern is that an ideal graph shall satisfy all the following constraints: non-negative, symmetric, low rank, and positive semidef-inite. We develop a graph learning algorithm by solving a convex optimization problem and further develop an efficient optimization to obtain global optimal so-lutions with theoretical guarantees. With only one non-sensitive parameter, our method is shown by experimental results to be robust and achieve higher accuracy in semi-supervised learning and clustering under various settings. As a prepro-cessing of graphs, our method has a wide range of potential applications machine learning and data mining. 1