  Graph learning has emerged as a promising technique for multi-view clustering
with its ability to learn a unified and robust graph from multiple views.
However, existing graph learning methods mostly focus on the multi-view
consistency issue, yet often neglect the inconsistency across multiple views,
which makes them vulnerable to possibly low-quality or noisy datasets. To
overcome this limitation, we propose a new multi-view graph learning framework,
which for the first time simultaneously and explicitly models multi-view
consistency and multi-view inconsistency in a unified objective function,
through which the consistent and inconsistent parts of each single-view graph
as well as the unified graph that fuses the consistent parts can be iteratively
learned. Though optimizing the objective function is NP-hard, we design a
highly efficient optimization algorithm which is able to obtain an approximate
solution with linear time complexity in the number of edges in the unified
graph. Furthermore, our multi-view graph learning approach can be applied to
both similarity graphs and dissimilarity graphs, which lead to two graph
fusion-based variants in our framework. Experiments on twelve multi-view
datasets have demonstrated the robustness and efficiency of the proposed
approach.
