Application of kernels to link analysis

ABSTRACT

The application of kernel methods to link analysis is explored. In particular, Kandola et al.'s Neumann kernels are shown to subsume not only the co-citation and bibliographic coupling relatedness but also Kleinberg's HITS importance. These popular measures of relatedness and importance correspond to the Neumann kernels at the extremes of their parameter range, and hence these kernels can be interpreted as defining a spectrum of link analysis measures intermediate between co-citation/bibliographic coupling and HITS. We also show that the kernels based on the graph Laplacian, including the regularized Laplacian and diffusion kernels, provide relatedness measures that overcome some limitations of co-citation relatedness. The property of these kernel-based link analysis measures is examined with a network of bibliographic citations. Practical issues in applying these methods to real data are discussed, and possible solutions are proposed.

REFERENCES

• 1: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 2: F. R. K. Chung. Spectral Graph Theory. Am. Math. Soc., Providence, RI, USA, 1997.
• 3: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing Top k Lists, SIAM Journal on Discrete Mathematics, v.17 n.1, p.134-160, 2003 [doi>10.1137/S0895480102412856]
• 4: G. H. Golub and C. F. Van Loan. Matrix Computation. Johns Hopkins Univ. Press, 3rd edition, 1996.
• 5: J. Kandola, J. Shawe-Taylor, and N. Cristianini. Learning semantic similarity. In NIPS 15, pages 673--680, 2003.
• 6: M. M. Kessler. Bibliographic coupling between scientific papers. Am. Documentation, 14(1):10--25, 1963.
• 7: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 8: Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
• 9: B. Schölkopf and A. J. Smola. Learning with Kernels. MIT Press, Cambridge, MA, USA, 2002.
• 10: M. Shimbo and T. Ito. Application of kernels to link analysis: proofs and additional experimental results. Technical report, Grad. School of Inform. Science, Nara Institute of Science and Technology, 2005. In preparation.
• 11: H. Small. Co-citation in the scientific literature: a new measure of the relationship between two documents. J. Am. Soc. for Inform. Science, 24:265--269, 1973.
• 12: A. J. Smola and R. Kondor. Kernels and regularization of graphs. In Proc. COLT'03, pages 144--158, 2003.
• 13: Scott White , Padhraic Smyth, Algorithms for estimating relative importance in networks, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956782]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms

Keywords:
HITS, co-citation coupling, graph kernel, link analysis