On the properties of von Neumann kernels for link analysis

We study the effectiveness of Kandola et al.’s von Neumann kernels as a link analysis measure. We show that von Neumann kernels subsume Kleinberg’s HITS importance at the limit of their parameter range. Because they reduce to co-citation relatedness at the other end of the parameter, von Neumann kernels give us a spectrum of link analysis measures between the two established measures of importance and relatedness. Hence the relative merit of a vertex can be evaluated in terms of varying trade-offs between the global importance and the local relatedness within a single parametric framework. As a generalization of HITS, von Neumann kernels inherit the problem of topic drift. When a graph consists of multiple communities each representing a different topic, HITS is known to rank vertices in the most dominant community higher regardless of the query term. This problem persists in von Neumann kernels; when the parameter is biased towards the direction of global importance, they tend to rank vertices in the dominant community uniformly higher irrespective of the community of the seed vertex relative to which the ranking is computed. To alleviate topic drift, we propose to use of a PLSI-based technique in combination with von Neumann kernels. Experimental results on a citation network of scientific papers demonstrate the characteristics and effectiveness of von Neumann kernels. This work was carried out while T. Ito was a Ph.D. student at Nara Institute of Science and Technology.