Fast best-effort pattern matching in large attributed graphs

ABSTRACT

We focus on large graphs where nodes have attributes, such as a social network where the nodes are labelled with each person's job title. In such a setting, we want to find subgraphs that match a user query pattern. For example, a "star" query would be, "find a CEO who has strong interactions with a Manager, a Lawyer,and an Accountant, or another structure as close to that as possible". Similarly, a "loop" query could help spot a money laundering ring.

Traditional SQL-based methods, as well as more recent graph indexing methods, will return no answer when an exact match does not exist. This is the first main feature of our method. It can find exact-, as well as near-matches, and it will present them to the user in our proposed "goodness" order. For example, our method tolerates indirect paths between, say, the "CEO" and the "Accountant" of the above sample query, when direct paths don't exist. Its second feature is scalability. In general, if the query has n_q nodes and the data graph has n nodes, the problem needs polynomial time complexity O(n ^{n q}), which is prohibitive. Our G-Ray ("Graph X-Ray") method finds high-quality subgraphs in time linear on the size of the data graph.

Experimental results on the DLBP author-publication graph (with 356K nodes and 1.9M edges) illustrate both the effectiveness and scalability of our approach. The results agree with our intuition, and the speed is excellent. It takes 4 seconds on average fora 4-node query on the DBLP graph.

REFERENCES

• 1: B. Aleman-Meza, C. Halaschek-Wiener, S. Sahoo, A. Sheth, and I. Arpinar. Lecture Notes in Computer Science, volume 3495, chapter Template Based Semantic Similarity for Security Applications, pages 621-622. Springer, 2005.
• 2: Arvind Hulgeri , Charuta Nakhe, Keyword Searching and Browsing in Databases using BANKS, Proceedings of the 18th International Conference on Data Engineering, p.431, February 26-March 01, 2002
• 3: H. Blau, N. Immerman, and D. Jensen. A visual language for querying and updating graphs. Technical Report 2002-037, Department of Computer Science, University of Massacheusetts, Amherst, 2002.
• 4: Soumen Chakrabarti, Mining the Web: Discovering Knowledge from HyperText Data, Science & Technology Books, 2002
• 5: Thayne Coffman , Seth Greenblatt , Sherry Marcus, Graph-based technologies for intelligence analysis, Communications of the ACM, v.47 n.3, March 2004 [doi>10.1145/971617.971643]
• 6: D. J. Cook and L. B. Holder. Substructure discovery using minimum description length and background knowledge. Journal of Artificial Intelligence Research (JAIR), 1:231--255, 1994.
• 7: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, 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.1014068]
• 8: D. Fogaras and B. Racz. Towards scaling fully personalized pagerank. In Proc. WAW, pages 105--117, 2004.
• 9: B. Gallagher. Matching structure and semantics: A survey on graph-based pattern matching. In AAAI FS '06: Papers from the 2006 AAAI Fall Symposium on Capturing and Using Patterns for Evidence Detection, pages 45--53, 2006.
• 10: Nicola Guarino , Claudio Masolo , Guido Vetere, OntoSeek: Content-Based Access to the Web, IEEE Intelligent Systems, v.14 n.3, p.70-80, May 1999 [doi>10.1109/5254.769887]
• 11: R. Jin , C. Wang , D. Polshakov , S. Parthasarathy , G. Agrawal, Discovering frequent topological structures from graph datasets, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081944]
• 12: S. Kamvar, T. Haveliwala, C. Manning, and G. Golub. Exploiting the block structure of the web for computing pagerank. In Stanford University Technical Report, 2003.
• 13: Yehuda Koren , Stephen C. North , Chris Volinsky, Measuring and extracting proximity in networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150432]
• 14: Nick Koudas , Chen Li , Anthony K. H. Tung , Rares Vernica, Relaxing join and selection queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 15: Michihiro Kuramochi , George Karypis, Finding Frequent Patterns in a Large Sparse Graph*, Data Mining and Knowledge Discovery, v.11 n.3, p.243-271, November 2005 [doi>10.1007/s10618-005-0003-9]
• 16: Jia-Yu Pan , Hyung-Jeong Yang , Christos Faloutsos , Pinar Duygulu, Automatic multimedia cross-modal correlation discovery, 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.1014135]
• 17: Jian Pei , Daxin Jiang , Aidong Zhang, On mining cross-graph quasi-cliques, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081898]
• 18: L. Shapiro and R. Haralick. Structural descriptions and inexact matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3:504--519, 1981.
• 19: Hanghang Tong , Christos Faloutsos, Center-piece subgraphs: problem definition and fast solutions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150448]
• 20: Hanghang Tong , Christos Faloutsos , Jia-Yu Pan, Fast Random Walk with Restart and Its Applications, Proceedings of the Sixth International Conference on Data Mining, p.613-622, December 18-22, 2006 [doi>10.1109/ICDM.2006.70]
• 21: W.-H. Tsai and K.-S. Fu. Error-correcting isomorphisms of attributed relational graphs for pattern analysis. IEEE Transactions on Systems, Man and Cybernetics, 9:757--768, 1979.
• 22: M. Wolverton, P. Berry, I. W. Harrison, J. D. Lowrance, D. Morley, A. C. Rodriguez, E. H. Ruspini, and J. Thoméré. LAW: A workbench for approximate pattern matching in relational data. In IAAI '03: Proceedings of the Fifteenth Conference on Innovative Applications of Artificial Intelligence, pages 143--150, 2003.
• 23: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 24: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing: a frequent structure-based approach, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007607]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

Additional Classification:
  E. Data
  E.m MISCELLANEOUS

General Terms:
Experimentation

Keywords:
attributed graph, pattern match, random walk