Summarizing semantic graphs: a survey <s> Statistical and hybrid graph summarization <s> 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. <s> BIB001 </s> Summarizing semantic graphs: a survey <s> Statistical and hybrid graph summarization <s> Graphs are widely used to model real-world objects and their relationships, and large graph data sets are common in many application domains. To understand the underlying characteristics of large graphs, graph summarization techniques are critical. 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 chapter, we introduce database-style operations to summarize graphs. Like the OLAP-style aggregation methods that allow users to interactively drill-down or roll-up to control the resolution of summarization, the methods described in this chapter provide an analogous functionality for large graph data sets. <s> BIB002 </s> Summarizing semantic graphs: a survey <s> Statistical and hybrid graph summarization <s> Large graph datasets are ubiquitous in many domains, including social networking and biology. Graph summarization techniques are crucial in such domains as they can assist in uncovering useful insights about the patterns hidden in the underlying data. One important type of graph summarization is to produce small and informative summaries based on user-selected node attributes and relationships, and allowing users to interactively drill-down or roll-up to navigate through summaries with different resolutions. However, two key components are missing from the previous work in this area that limit the use of this method in practice. First, the previous work only deals with categorical node attributes. Consequently, users have to manually bucketize numerical attributes based on domain knowledge, which is not always possible. Moreover, users often have to manually iterate through many resolutions of summaries to identify the most interesting ones. This paper addresses both these key issues to make the interactive graph summarization approach more useful in practice. We first present a method to automatically categorize numerical attributes values by exploiting the domain knowledge hidden inside the node attributes values and graph link structures. Furthermore, we propose an interestingness measure for graph summaries to point users to the potentially most insightful summaries. Using two real datasets, we demonstrate the effectiveness and efficiency of our techniques. <s> BIB003 </s> Summarizing semantic graphs: a survey <s> Statistical and hybrid graph summarization <s> In the enterprise context, people need to exploit and mainly visualize different types of interactions between heterogeneous objects. Graph model seems to be the most appropriate way to represent those interactions. However, the extracted graphs have in general a huge size which makes it difficult to analyze and visualize. An aggregation step is needed to have more understandable graphs in order to allow users discovering underlying information and hidden relationships between entities. In this work, we propose new measures to evaluate the quality of summaries based on an existing algorithm named k-SNAP that produces a summarized graph according to user-selected node attributes and relationships. <s> BIB004 </s> Summarizing semantic graphs: a survey <s> Statistical and hybrid graph summarization <s> Graph-structured data is ubiquitous and with the advent of social networking platforms has recently seen a significant increase in popularity amongst researchers. However, also many business applications deal with this kind of data and can therefore benefit greatly from graph processing functionality offered directly by the underlying database. This paper summarizes the current state of graph data processing capabilities in the SAP HANA database and describes our efforts to enable large graph analytics in the context of our research project SynopSys. With powerful graph pattern matching support at the core, we envision OLAP-like evaluation functionality exposed to the user in the form of easy-to-apply graph summarization templates. By combining them, the user is able to produce concise summaries of large graph-structured datasets. We also point out open questions and challenges that we plan to tackle in the future developments on our way towards large graph analytics. <s> BIB005
Several follow-ups on the SNAP summarization approach (Sect. 4.1.2) have been proposed in the literature. The k-SNAP summarization approach BIB001 BIB002 is an approximation of the SNAP one. It allows setting the desired number k of summary nodes, so that a whole graph can be visualized at different granularity levels, similarly to roll-up and drill-down OLAP operations. A k-SNAP summary is a graph of k summary nodes which satisfy the above condition (i) of a SNAP summary, but relax condition (ii) so that only some (not every) input graph node represented by some summary node satisfies it. Further, as many such summaries may exist, a k-SNAP summary is defined as one that best satisfy the condition (ii) of SNAP summaries. Finding such a summary is NP-complete BIB001 ; hence, tractable heuristicbased algorithms are proposed to compute approximations of k-SNAP summaries. The k-SNAP summarization approach has been further extended BIB003 to handle numerical attributes, while k-SNAP as well as SNAP before have only considered categorial attributes whose domains are made of a limited number of values. The proposed CANAL approach allows bucketizing the values of some numerical attribute into the desired number of categories, hence reducing the summarization of graphs with categorial and numerical attributes to that of graphs with categorial attributes only. For a given numerical attribute a, each of the obtained categories represent a range of a values that nodes with similar edge structure have. Computing such categories is in O (N log N + k 4 a ), where k a is the number of distinct a values that the input graph contains. Also, to ease the use of k-SNAP to inspect a graph in an rollup and drill-down OLAP fashion, Zhang et al. BIB003 provides a solution to automatically recommend k values for visualizing this graph. It consists in ranking k-SNAP summaries of varying k according to a so-called interestingness measure, defined in terms of conciseness, coverage and diversity criteria. k-SNAP has also strongly inspired the summarization approach in BIB004 , which similarly aims at computing graph summaries w.r.t. user-selected number of summary nodes, attributes and edge types. The summaries are computed using a variant of one above-mentioned tractable k-SNAP heuristics, which keeps the SNAP condition (i) but changes the SNAP condition (ii) that k-SNAP tries to best satisfies, so that a summary best reflects the organization in social com-munities of the input graph nodes w.r.t. the selected attributes and edge types. From a different perspective, BIB005 sketches SAP HANA's approach for large graph analytics through summarization. It consists in defining rules to summarize part of an analyzed graph. Rules are made of two components, one graph pattern to be matched on the graph, and how the matched data should be grouped and aggregated into a result graph.