The graphlet spectrum

ABSTRACT

Current graph kernels suffer from two limitations: graph kernels based on counting particular types of subgraphs ignore the relative position of these subgraphs to each other, while graph kernels based on algebraic methods are limited to graphs without node labels. In this paper we present the graphlet spectrum, a system of graph invariants derived by means of group representation theory that capture information about the number as well as the position of labeled subgraphs in a given graph. In our experimental evaluation the graphlet spectrum outperforms state-of-the-art graph kernels.

REFERENCES

• 1: Francis R. Bach, Graph kernels between point clouds, Proceedings of the 25th international conference on Machine learning, p.25-32, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390160]
• 2: Karsten M. Borgwardt , Hans-Peter Kriegel, Shortest-Path Kernels on Graphs, Proceedings of the Fifth IEEE International Conference on Data Mining, p.74-81, November 27-30, 2005 [doi>10.1109/ICDM.2005.132]
• 3: Karsten M. Borgwardt , Cheng Soon Ong , Stefan Schönauer , S. V. N. Vishwanathan , Alex J. Smola , Hans-Peter Kriegel, Protein function prediction via graph kernels, Bioinformatics, v.21 n.1, p.47-56, January 2005 [doi>10.1093/bioinformatics/bti1007]
• 4: Chang, C.-C., & Lin, C.-J. (2001). LIBSVM: a library for support vector machines. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 5: Michael Clausen, Fast generalized Fourier transforms, Theoretical Computer Science, v.67 n.1, p.55-63, Sept. 1989 [doi>10.1016/0304-3975(89)90021-2]
• 6: Debnath, A. K., Lopez de Compadre, R. L., Debnath, G., Shusterman, A. J., & Hansch, C. (1991). Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. J Med Chem, 34, 786--797.
• 7: Gärtner, T., Flach, P., & Wrobel, S. (2003). On graph kernels: Hardness results and efficient alternatives. Proc. Annual Conf. Computational Learning Theory (pp. 129--143). Springer.
• 8: Kashima, H., Tsuda, K., & Inokuchi, A. (2003). Marginalized kernels between labeled graphs. Proc. Intl. Conf. Machine Learning (pp. 321--328). San Francisco, CA: Morgan Kaufmann.
• 9: Kondor, R. (2006). 𝕊_nob: a C++ library for fast Fourier transforms on the symmetric group. Available at http://www.gatsby.ucl.ac.uk/~risi/Snob/.
• 10: Risi Kondor , Karsten M. Borgwardt, The skew spectrum of graphs, Proceedings of the 25th international conference on Machine learning, p.496-503, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390219]
• 11: David K. Maslen, The efficient computation of Fourier transforms on the symmetric group, Mathematics of Computation, v.67 n.223, p.1121-1147, July 1, 1998 [doi>10.1090/S0025-5718-98-00964-8]
• 12: Mikkonen, T. (2007). The ring of graph invariants -- graphic values. arXiv: 0712/0146.
• 13: Rockmore, D. N. (1997). Some applications of generalized FFTs. Proceedings of the DIMACS workshop on groups and computation.
• 14: Schomburg, I., Chang, A., Ebeling, C., Gremse, M., Heldt, C., Huhn, G., & Schomburg, D. (2004). Brenda, the enzyme database: updates and major new developments. Nucleic Acids Research, 32D, 431--433.
• 15: Serre, J.-P. (1977). Linear representations of finite groups, vol. 42 of Graduate Texts in Mathamatics. Springer-Verlag.
• 16: Shervashidze, N., Vishwanathan, S. V. N., Petri, T., Mehlhorn, K., & Borgwardt, K. (2009). Efficient graphlet kernels for large graph comparison. Proceedings of International Conference on Artificial Intelligence and Statistics.
• 17: Koji Tsuda, Entire regularization paths for graph data, Proceedings of the 24th international conference on Machine learning, p.919-926, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273612]
• 18: Nikil Wale , George Karypis, Comparison of Descriptor Spaces for Chemical Compound Retrieval and Classification, Proceedings of the Sixth International Conference on Data Mining, p.678-689, December 18-22, 2006 [doi>10.1109/ICDM.2006.39]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Design, Theory