Efficient aggregation for graph summarization

ABSTRACT

Graphs are widely used to model real world objects and their relationships, and large graph datasets are common in many application domains. To understand the underlying characteristics of large graphs, graph summarization techniques are critical. However, existing graph summarization methods are mostly statistical (studying statistics such as degree distributions, hop-plots and clustering coefficients). These statistical methods are very useful, but the resolutions of the summaries are hard to control.

In this paper, we introduce two database-style operations to summarize graphs. Like the OLAP-style aggregation methods that allow users to drill-down or roll-up to control the resolution of summarization, our methods provide an analogous functionality for large graph datasets. The first operation, called SNAP, produces a summary graph by grouping nodes based on user-selected node attributes and relationships. The second operation, called k-SNAP, further allows users to control the resolutions of summaries and provides the "drill-down" and "roll-up" abilities to navigate through summaries with different resolutions. We propose an efficient algorithm to evaluate the SNAP operation. In addition, we prove that the k-SNAP computation is NP-complete. We propose two heuristic methods to approximate the k-SNAP results. Through extensive experiments on a variety of real and synthetic datasets, we demonstrate the effectiveness and efficiency of the proposed methods.

REFERENCES

• 1: Lada A. Adamic , Natalie Glance, The political blogosphere and the 2004 U.S. election: divided they blog, Proceedings of the 3rd international workshop on Link discovery, p.36-43, August 21-25, 2005, Chicago, Illinois [doi>10.1145/1134271.1134277]
• 2: D. A. Bader and K. Madduri. GTgraph: A suite of synthetic graph generators. http://www.cc.gatech.edu/~kamesh/GTgraph.
• 3: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 4: Daniel K. Blandford , Guy E. Blelloch , Ian A. Kash, Compact representations of separable graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 6: Deepayan Chakrabarti , Christos Faloutsos, Graph mining: Laws, generators, and algorithms, ACM Computing Surveys (CSUR), v.38 n.1, p.2-es, 2006 [doi>http://doi.acm.org/10.1145/1132952.1132954]
• 7: Deepayan Chakrabarti , Christos Faloutsos , Yiping Zhan, Visualization of large networks with min-cut plots, A-plots and R-MAT, International Journal of Human-Computer Studies, v.65 n.5, p.434-445, May, 2007 [doi>10.1016/j.ijhcs.2006.11.002]
• 8: D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-MAT: A recursive model for graph mining. In Proceedings of 4th SIAM International Conference on Data Mining, 2004.
• 9: D. G. Corneil , C. C. Gotlieb, An Efficient Algorithm for Graph Isomorphism, Journal of the ACM (JACM), v.17 n.1, p.51-64, Jan. 1970 [doi>10.1145/321556.321562]
• 10: Ivan Herman , Guy Melançon , M. Scott Marshall, Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.24-43, January 2000 [doi>10.1109/2945.841119]
• 11: Jun Huan , Wei Wang , Jan Prins , Jiong Yang, SPIN: mining maximal frequent subgraphs from graph databases, 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.1014123]
• 12: M. Ley. DBLP Bibliography. http://www.informatik.uni-trier.de/ ley/db/.
• 13: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 14: M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E, 69:026113, 2004.
• 15: S. Raghavan and H. Garcia-Molina. Representing Web graphs. In Proceedings of ICDE'03, pages 405--416, 2003.
• 16: F. S. Roberts and L. Sheng. How hard is it to determine if a graph has a 2-role assignment? Networks, 37(2):67--73, 2001.
• 17: Jose F. Rodrigues Jr. , Agma J. M. Traina , Christos Faloutsos , Caetano Traina Jr., SuperGraph Visualization, Proceedings of the Eighth IEEE International Symposium on Multimedia, p.227-234, December 11-13, 2006 [doi>10.1109/ISM.2006.143]
• 18: Jimeng Sun , Yinglian Xie , Hui Zhang , Christos Faloutsos, Less is More: Sparse Graph Mining with Compact Matrix Decomposition, Statistical Analysis and Data Mining, v.1 n.1, p.6-22, February 2008 [doi>10.1002/sam.v1:1]
• 19: Wei Wang , Chen Wang , Yongtai Zhu , Baile Shi , Jian Pei , Xifeng Yan , Jiawei Han, GraphMiner: a structural pattern-mining system for large disk-based graph databases and its applications, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066273]
• 20: Takashi Washio , Hiroshi Motoda, State of the art of graph-based data mining, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959249]
• 21: D. R. White and K. P. Reitz. Graph and semigroup homomorphisms on semigroups of relations. Social Networks, 5(2):193--234, 1983.
• 22: Xiaowei Xu , Nurcan Yuruk , Zhidan Feng , Thomas A. J. Schweiger, SCAN: a structural clustering algorithm for networks, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281280]
• 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
aggregation, graphs, social networks, summarization