A semi-supervised heat kernel pagerank MBO algorithm for data classification
Ekaterina Merkurjev, Andrea Louise Bertozzi, Fan Chung · Communications in Mathematical Sciences · 2018
We present an accurate and efficient graph-based algorithm for semi-supervised classification that is motivated by recent successful threshold dynamics approaches and derived using heat kernel pagerank.Two different techniques are proposed to compute the pagerank, one of which proceeds by simulating random walks of bounded length.The algorithm produces accurate results even when the number of labeled nodes is very small, and avoids computationally expensive linear algebra routines.Moreover, the accuracy of the procedure is comparable with or better than that of stateof-the-art methods and is demonstrated on benchmark data sets.In addition to the main algorithm, a simple novel procedure that uses heat kernel pagerank directly as a classifier is outlined.We also provide detailed analysis, including information about the time complexity, of all proposed methods.