Green's function for the Laplace operator represents the propagation of influence of point sources and is the foundation for solving many physics problems. On a graph of pairwise similarities, the Green's function is the inverse of the combinatorial Laplacian; we resolve the zero-mode difficulty by showing its physical origin as the consequence of the Von Neumann boundary condition. We propose to use Green's function to propagate label information for both semi-supervised and unsupervised learning. We also derive this learning framework from the kernel regularization using Reproducing Kernel Hilbert Space theory at strong regularization limit. Green's function provides a well-defined distance metric on a generic weighted graph, either as the effective distance on the network of electric resistors, or the average commute time in random walks. We show that for unsupervised learning this approach is identical to Ratio Cut and Normalized Cut spectral clustering algorithms. Experiments on newsgroups and six UCI datasets illustrate the effectiveness of this approach. Finally, we propose a novel item-based recommender system using Green's function and show its effectiveness.
['Chris H. Q. Ding', 'Horst D. Simon', 'Rong Jin', 'Tao Li']
A learning framework using Green's function and kernel regularization with application to recommender system