Mining the space of graph properties

ABSTRACT

Existing data mining algorithms on graphs look for nodes satisfying specific properties, such as specific notions of structural similarity or specific measures of link-based importance. While such analyses for predetermined properties can be effective in well-understood domains, sometimes identifying an appropriate property for analysis can be a challenge, and focusing on a single property may neglect other important aspects of the data. In this paper, we develop a foundation for mining the properties themselves. We present a theoretical framework defining the space of graph properties, a variety of mining queries enabled by the framework, techniques to handle the enormous size of the query space, and an experimental system called F-Miner that demonstrates the utility and feasibility of property mining.

REFERENCES

• 1: http://dbpubs.stanford.edu.
• 2: http://clubnexus.stanford.edu.
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: 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
• 5: Sergey Brin. Extracting patterns and relations from the World Wide Web. In Proceedings of the WebDB Workshop at the 6th International Conference on Extending Database Technology (EDBT), Valencia, Spain, March 1998.
• 6: Luc Dehaspe and Hannu TT Toivonen. Discovery of Relational Association Rules, pages 189--212. Springer-Verlag Heidelberg, Germany, 2001. http://citeseer.nj.nec.com/486120.html.
• 7: Bart Goethals , Jan Van den Bussche, Relational Association Rules: Getting WARMeR, Proceedings of the ESF Exploratory Workshop on Pattern Detection and Discovery, p.125-139, September 16-19, 2002
• 8: Roy Goldman , Narayanan Shivakumar , Suresh Venkatasubramanian , Hector Garcia-Molina, Proximity Search in Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.26-37, August 24-27, 1998
• 9: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 10: Christoph Helma, Stefan Kramer, and Luc De Raedt. The molecular feature miner MolFea. In Proceedings of the Beilstein-Institut Workshop, Bozen, Italy, May 2002.
• 11: Tomasz Imielinski , Heikki Mannila, A database perspective on knowledge discovery, Communications of the ACM, v.39 n.11, p.58-64, Nov. 1996 [doi>10.1145/240455.240472]
• 12: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 13: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775126]
• 14: Glen Jeh and Jennifer Widom. Mining the space of graph properties. Technical report, Stanford University Database Group, 2003. http://dbpubs.stanford.edu/pub/2003-10.
• 15: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 16: M. M. Kessler. Bibliographic coupling between scientific papers. American Documentation, 14:10--25, 1963.
• 17: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 18: Michihiro Kuramochi and George Karypis. An efficient algorithm for discovering frequent subgraphs. Technical report, Department of Computer Science, University of Minnesota, 2002. http://www.cs.umn.edu/~kuram/papers/fsg-long.pdf.
• 19: Surnjani Djoko Lawrence B. Holder, Diane J. Cook. Substructure discovery in the SUBDUE system. In Proceedings of the AAAI Workshop on Knowledge Discovery in Databases (KDD), Seattle, Washington, USA, July 1994.
• 20: Stephen Muggleton and Luc De Raedt. Inductive logic programming: Theory and methods. Journal of Logic Programming, 19/20:629--679, 1994.
• 21: Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The Page-Rank citation ranking: Bringing order to the Web. Technical report, Stanford University Database Group, 1998. http://citeseer.nj.nec.com/368196.html.
• 22: Henry Small. Co-citation in the scientific literature: A new measure of the relationship between two documents. Journal of the American Society for Information Science, 24:265--269, 1973.
• 23: Neel Sundaresan , Jeonghee Yi, Mining the Web for relations, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.699-711, June 2000, Amsterdam, The Netherlands
• 24: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 25: 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
• 26: Mohammed J. Zaki, Efficiently mining frequent trees in a forest, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775058]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
data mining, graph mining