Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Many applications in structure matching require the ability to search for graphs that are similar to a query graph, i.e., similarity graph queries. Prior works, especially in chemoinformatics, have used the maximum common edge subgraph (MCEG) to compute the graph similarity. This approach is prohibitively slow for real-time queries. In this work, we propose an algorithm that extracts and indexes subgraph features from a graph dataset. It computes the similarity of graphs using a linear graph kernel based on feature weights learned offline from a training set generated using MCEG. We show empirically that our proposed algorithm of learning to rank graphs can achieve higher normalized discounted cumulative gain compared with existing optimal methods based on MCEG. The running time of our algorithm is orders of magnitude faster than these existing methods.

REFERENCES

• 1: B. Chen, Q. Zhao, B. Sun, and P. Mitra. Temporal and social network based blogging behavior prediction in blogspace. In Proc. ICDM, 2007.
• 2: D. Haussler. Convolution kernels on discrete structures. Technical Report UCS-CRL-99-10, 1999.
• 3: P. Li, C. J. Burges, and Q. Wu. Learning to rank using classification and gradient boosting. In Proc. NIPS, 2007.
• 4: Siegfried Nijssen , Joost N. Kok, A quickstart in frequent structure mining can make a difference, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014134]
• 5: J. W. Raymond, E. J. Gardiner, and P. Willet. Rascal: Calculation of graph similarity using maximum common edge subgraphs. The Computer Journal, 45(6):631--644, 2002.
• 6: Bingjun Sun , Prasenjit Mitra , C. Lee Giles, Mining, indexing, and searching for textual chemical molecule information on the web, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367597]
• 7: Bingjun Sun , Prasenjit Mitra , C. Lee Giles , John Yen , Hongyuan Zha, Topic segmentation with shared topic detection and alignment of multiple documents, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277778]
• 8: Bingjun Sun , Qingzhao Tan , Prasenjit Mitra , C. Lee Giles, Extraction and search of chemical formulae in text documents on the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242607]
• 9: Bingjun Sun , Ding Zhou , Hongyuan Zha , John Yen, Multi-task text segmentation and alignment based on weighted mutual information, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183760]
• 10: Xifeng Yan , Feida Zhu , Philip S. Yu , Jiawei Han, Feature-based similarity search in graph structures, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1418-1453, December 2006 [doi>10.1145/1189769.1189777]
• 11: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to Ad Hoc information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.334-342, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384019]
• 12: Qiankun Zhao , Ling Chen , Sourav S. Bhowmick , Sanjay Madria, XML structural delta mining: issues and challenges, Data & Knowledge Engineering, v.59 n.3, p.627-651, December 2006 [doi>10.1016/J.datak.2005.10.002]
• 13: Zhaohui Zheng , Keke Chen , Gordon Sun , Hongyuan Zha, A regression framework for learning ranking functions using relative relevance judgments, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277792]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Design, Experimentation

Keywords:
graph kernel, learn to rank, similarity graph search