An experimental investigation of graph kernels on a collaborative recommendation task

Fouss, François [UCL] Yen, Luh [UCL] Pirotte, Alain [UCL] Saerens, Marco [UCL]

(eng) This work presents a systematic comparison between seven kernels (or similarity matrices) on a graph, on a collaborative recommendation task involving a database. The database is viewed as a graph where elements are represented as nodes and relations as links between nodes. From this graph, seven kernels are computed, leading to a set of meaningful proximity measures between nodes, allowing to answer questions about the structure of the graph under investigation; in particular, recommend items to users. Cross-validation results indicate that a simple nearest-neighbours rule based on the similarity measure provided by the regularized Laplacian, the Markov diffusion and the commute time kernels performs best. We therefore recommend the use of the commute time kernel for computing similarities between elements of a database, for two reasons: (1) it has a nice appealing interpretation in terms of random walks and (2) no parameter needs to be adjusted.