On the Scalability of Large Graph Methods for Kernel-Based Machine Learning∗

Kernel-based machine learning methods (such as support vector machines and kernel regression) can be viewed as a generalization of group decision-making, based on nearest neighbor labels in the feature space. For this reason, for many machine learning tasks in which data is separable over a known distance topology, kernel-based methods can learn extremely successfully, rivaling and sometimes surpassing that of neural networks. However, for scalability reasons, kernel-based methods are often not considered for very large dataset tasks; e.g. with n training samples, the computational complexity is prohibitive in both training (O(n³)) and inference (O(n²)). We consider a scalable approach to very large kernel SVMs by viewing the kernel values as weights in an undirected graph, and use an approximate method to solve this linear system using bounded memory and complexity costs. This approximates a kernel biased toward using nearest neighbor label information, which is a common approach in inference over very large graphs. Specifically, by leveraging the approximate page-rank method (APPR), we bound the set of nonzeros of the intermediary variables and demonstrate it does not scale with n, the size of the graph. Overall, this new method more gracefully showcases the transition between a graph-based majority vote method (cheap, low performance) and a full kernel SVM method (high performance, unscalable) and illustrates potential use in large-scale applications.