Harmonic Extension

Zuoqiang Shi, Jian Sun, Minghao Tian

Abstract

In this paper, we consider the harmonic extension problem, which is widely used in many applications of machine learning. We find that the traditional 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 traditional 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 compute a harmonic function with convergence guarantees, and practically, they are both simple, amounting to solving a linear system. Our experiments show the PIM performs the best in semi-supervised learning tasks.

Introduction

Semi-supervised learning often relies on the smooth propagation of labels from a small set of known points to a larger unlabeled dataset. This process, known as harmonic extension, seeks the smoothest possible function that honors the boundary conditions (the known labels). Mathematically, this is modeled as solving the Laplace equation on a manifold.

While the Graph Laplacian Method (GLM) has been the standard tool for this task, it suffers from significant inaccuracies near labeled points, which act as boundaries. This paper identifies the mathematical roots of this failure and proposes two robust alternatives: the Point Integral Method (PIM) and the Volume Constraint Method (VCM).

The Failure of the Standard Graph Laplacian

The core issue with the standard discrete Graph Laplacian is its behavior at the boundaries. In continuous theory, the Laplace-Beltrami operator requires specific boundary conditions to be well-defined. However, the discrete graph model often ignores the normal derivative at the boundary, leading to solutions that are jagged or discontinuous.

Comparison of harmonic extension methods on a 1D point cloud. (a) GLM shows significant noise and failure to reach the peak. (b) PIM and (c) VCM provide much smoother approximations of the (d) ground truth FEM solution.

As shown in the 1D toy example above, the standard GLM (a) fails to capture the smooth "tent" shape of the classical harmonic function (d). Instead, it produces a jagged result that does not accurately reach the target label values at the peak. In contrast, PIM (b) and VCM (c) closely approximate the ideal solution.

Proposed Methods: PIM and VCM

To address these shortcomings, we introduce two methods rooted in integral equations rather than pure differential operators:

  1. Point Integral Method (PIM): PIM replaces the differential equation with an integral equation. By incorporating a Robin boundary condition—which relates the function's value to its derivative—PIM creates a modified linear system. This approach is naturally robust to the irregular sampling common in real-world point clouds.
  2. Volume Constraint Method (VCM): VCM addresses the boundary problem by "thickening" the labeled points. Instead of enforcing a label at a single point, it enforces the label over a small local volume. This allows the graph Laplacian to better "see" the boundary, resulting in a smoother extension.

Both methods are computationally efficient, as they reduce to solving a linear system of the form $Ax = b$.

Empirical Evaluation

We compared PIM and VCM against GLM and other state-of-the-art methods on two benchmark datasets: MNIST (handwritten digits) and 20 Newsgroups (text classification).

Key Findings

  • Superior Accuracy: PIM consistently achieved the lowest test error rates across both datasets.
  • Label Efficiency: The performance gap was most pronounced when labels were extremely scarce (e.g., only 2–10 labels per class). PIM's ability to maintain smoothness with minimal data makes it ideal for low-resource scenarios.
  • Theoretical Rigor: Unlike heuristic adjustments, PIM and VCM are backed by convergence proofs, ensuring they approach the true classical harmonic function as data density increases.

Conclusion

The Point Integral Method (PIM) provides a robust and theoretically sound alternative to standard graph Laplacian techniques for harmonic extension. By shifting from differential to integral approximations, we overcome the boundary artifacts that plague traditional semi-supervised learning algorithms, leading to more accurate label propagation in high-dimensional data.

Summary updated

Abstract

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.
BibTeX
@misc{shi2015harmonic,
  author = {Zuoqiang Shi and Jian Sun and Minghao Tian},
  title = {{Harmonic Extension}},
  year = {2015},
  eprint = {1509.06458},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1509.06458},
}
Figure