Projection with mixed-size anchor graphs

The graph-based projection method projects the raw high-dimensional data into a more compact low-dimensional subspace involving two sequential steps of constructing similarity matrices and solving the eigenvalue decomposition problems, which are time-consuming and memory-intensive. In addition, it is worth attention that a single similarity graph may inevitably capture inadequate data structures for comprehensive knowledge exploration. To this end, we propose an efficient unsupervised method termed Projection with Mixed-size Anchor Graphs (PMAG), which adopts a multi-granularity number of anchors in the task of projection. Mixed-size anchor graphs are used to improve projection learning, which helps to explore the intrinsic data structure and extract knowledge more deeply and comprehensively. An automatic mechanism is introduced to evaluate the diverse contributions of anchor graphs in hybrid sizes and integrate them to stimulate the projection. Furthermore, an efficient optimization algorithm with computational complexity scales linearly with the size and dimensionality of the dataset is presented to solve the resulting problem. Extensive experimental results reveal that PMAG is 6.73 times faster than the best comparative method, achieving more than 20% accuracy improvement on the largest dataset. The code is available at https://github.com/caccode/PMAG.