Harmonic Extension
This addresses a foundational issue in machine learning for applications like semi-supervised learning, but it is incremental as it builds on existing methods with new approaches.
The paper tackled the harmonic extension problem, showing that the traditional graph Laplacian method fails to approximate classical harmonic functions well, and proposed the point integral method (PIM) and volume constraint method (VCM), with experiments on semi-supervised learning datasets indicating PIM performs best.
In this paper, we consider the harmonic extension problem, which is widely used in many applications of machine learning. We find that the transitional method of graph Laplacian fails to produce a good approximation of the classical harmonic function. To tackle this problem, we propose a new method called the point integral method (PIM). We consider the harmonic extension problem from the point of view of solving PDEs on manifolds. The basic idea of the PIM method is to approximate the harmonicity using an integral equation, which is easy to be discretized from points. Based on the integral equation, we explain the reason why the transitional graph Laplacian may fail to approximate the harmonicity in the classical sense and propose a different approach which we call the volume constraint method (VCM). Theoretically, both the PIM and the VCM computes a harmonic function with convergence guarantees, and practically, they are both simple, which amount to solve a linear system. One important application of the harmonic extension in machine learning is semi-supervised learning. We run a popular semi-supervised learning algorithm by Zhu et al. over a couple of well-known datasets and compare the performance of the aforementioned approaches. Our experiments show the PIM performs the best.