An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification

Area of Science:

• Graph theory
• Machine learning
• Data mining

Background:

• Kernel methods are widely used in machine learning.
• Graph-based kernels offer intuitive ways to measure node similarity.
• A comprehensive comparison of various graph kernels is needed.

Purpose of the Study:

• To survey and empirically compare nine kernels on graphs.
• To evaluate their performance on collaborative recommendation and semi-supervised classification tasks.
• To identify the most effective graph kernels for these applications.

Main Methods:

• Implemented and evaluated seven established graph kernels and two novel ones.
• Applied kernels to link prediction in collaborative recommendation.
• Utilized kernels for semi-supervised classification on multiple datasets.

Main Results:

• The regularized commute-time kernel and Markov diffusion kernel showed the best performance.
• The regularized Laplacian kernel also performed competitively.
• Performance varied across different datasets and tasks.

Conclusions:

• The regularized commute-time and Markov diffusion kernels are highly effective for recommendation and classification.
• Graph kernels provide valuable proximity measures for graph structure analysis.
• Further investigation into these kernels is warranted for graph-based machine learning.