Finding the Needle in a Haystack: Entropy Guided Exploration of Very Large Graph Cubes∗ Dritan Bleco Yannis Kotidis Athens University of Economics and Business Athens University of Economics and Business Athens, Greece Athens, Greece dritanbleco@aueb.gr kotidis@aueb.gr ABSTRACT In this work, we model the relationships between the graph Graphs provide an elegant and versatile solution for modeling cuboids as a graph cube lattice produced by taking the Cartesian complex datasets, especially when the focus of the analysis is on product of simpler data cubes on the attributes of the nodes and highlighting interesting associations between data entities. Graph edges of the data graph. Using this model, we propose a graph cubes permit analysis of the resulting data graphs at various cube analysis workflow that can be used to explore interesting as- levels of granularity based on their node and edge attributes. In sociations hidden within very large graph cubes. Our suggested this work, we utilize information entropy measures in order to workflow utilizes two intuitive entropy measures, introduced help the analyst navigate within the rich information contained in [5], in order to reveal associations that deviate from the ex- in a graph cube. Our metrics suggest navigations (drill-downs) pected behavior. The first measure termed as external entropy towards more detailed data descriptions, conditioned on what permit us to suggest certain drill-down navigations that reveal has been observed at a coarser resolution. We propose a graph associations that deviate from what has already been observed at analysis workflow that first suggests interesting cuboids from the higher-level aggregations of the graph cube. As demonstrated the exponential collection of aggregations that exist in the graph by our experiments, from the exponential possible navigations cube. At a latter step, this workflow handpicks sub-graphs out in the graph cube, only a very small percentage of them leads of these aggregations that deviate significantly from the rest to interesting observations. The external entropy helps the data of the data. We experimentally validate our techniques using explorer navigates towards interesting cuboids in the graph cube real datasets and demonstrate that the proposed entropy-based lattice and may be used to prune a significant portion of the exploration can help eliminate large portions of the respective lattice from consideration. graph cubes from consideration. Our techniques help locate the In a second step of the workflow, we utilize entropy calcula- "needle in the haystack" and steer the user towards data skew tions in order to elevate particular data associations that deviate hidden within vast valleys of near-uniform interactions. from the rest of the relationships within the cuboids selected from the first step. This is achieved by using an internal entropy metric that helps the analyst elevate aggregate interactions that 1 INTRODUCTION are the result of skew in the data graph. These interactions be- Despite their versatility, graph data have specific characteristics come prominent when the raw data is aggregated at the levels that make their analysis often challenging. Of particular interest denoted by the cuboid under investigation. in graph data are the relationships between nodes captured by the In our experimental section we present results of utilizing our edges of the graph. These relationships should be analyzed with techniques while processing real social datasets of realistic sizes. respect to attribute values available at the nodes and edges. For We compare our techniques against an alternative method that example, a data scientist may want to investigate how users of a prunes parts of the graph cube based on a minimum support social network, depending on their gender, relate to other users threshold, as in association rule mining. We observe that our based on their nationality. This inquiry can be accommodated framework maintains the most varied parts of the data distribu- by aggregating existing relationships (edges) in the data graph tion independently of their frequencies. Thus, many interesting based on the attributes of their constituent nodes. This process trends revealed by our technique that focuses on data skew within forms a graph cuboid, as is depicted in Figure 1. and across cuboids, would be missed by methods that merely The graph cube contains all such possible cuboids that can seek frequent patterns. We also discuss prominent trends reveled be generated given the raw graph data [6, 10, 15, 22, 35]. As in by our techniques on the real datasets used. the case of the data cube [11, 12, 16, 28], there is an exponential number of aggregations that define the space of all possible such 2 MOTIVATING EXAMPLE cuboids. Moreover, each of these cuboids is not a flat relation, We consider a social network which depicts relationships be- but a complex property graph filled with intrinsic structural tween different users. Each user can be represented as a node information based on the formed relationships and annotated in a graph. Each user profile has three attributes: gender (male, with computed summary statistics over the attributes of the female), nation (Greece, Spain, France) and profession (doctor, graph nodes and edges. A data explorer, familiar with the simpler professor, musician). For brevity, we refer to these attributes val- multidimensional framework of data cubes, may be overwhelmed ues by their initial letter. Each edge in the data graph is associated when she tries to navigate this data deluge. with a numeric value that indicates the number of interactions ∗ This research is financed by the Research Centre of Athens University of Eco- between the respective users. nomics and Business, in the framework of the project entitled ’Original Scientific Publications A possible inquiry on this network is to examine how users depending on their gender, relate to other users based on their © 2018 Copyright held by the owner/author(s). Published in the Workshop nationality. To accommodate this query we need to perform three Proceedings of the EDBT/ICDT 2018 Joint Conference (March 26, 2018, Vienna, Austria) on CEUR-WS.org (ISSN 1613-0073). Distribution of this paper is permitted different aggregations. First, starting nodes (i.e. nodes with outgo- under the terms of the Creative Commons license CC-by-nc-nd 4.0. ing edges) are grouped into two aggregate nodes corresponding 84 Figure 1: Three possible cuboids: (gender, profession - nation), (gender - nation) and (gender, nation - nation). Notice that the drill-down to the more fine-grained cuboid on the right reveals irregular associations, conditioned to what has been revealed by the cuboid in the middle. In contrast, the relationships contained on the (gender, profession-nation) cuboid seem to follow the same patterns as the original top-level cuboid. to gender values male and female, respectively. Similarly, three 3 THE GRAPH CUBE aggregate nodes corresponding to nations Greece, Spain and In our running example, each user profile has three attributes, France are formed. Finally, each edge of the network, depend- namely gender (G), nation (N) and profession (P). If we treat these ing on the gender attribute value of its starting node and the attributes as dimensions in OLAP analysis, the resulting data nation attribute value of its ending node, is aggregated into an cube has 23 =8 possible cuboids. The work of [35] extended the edge between the corresponding aggregate nodes created at the data cube framework to work on graph data by considering also previous steps. At this time, a desired aggregate function can the relationships between aggregated graph nodes. In particular, be computed. In this example, we assume that this function is consider a data cube for the data attributes of the starting nodes in SUM(). The resulting aggregate graph is depicted in the middle the graph and another one for the ending nodes. These data cubes of Figure 1. Based on its construction we refer to it as the (gender share the same dimensions and are, thus, identical in structure - nation) cuboid. (i.e. contain the same set of cuboids). The graph cube can be Continuing with the running example, the cuboid on the left considered as the Cartesian product of these two data cubes: of part of the figure depicts the outcome of drilling-down from the starting- and the ending-cube. In this running example, a (gender - nation) to the (gender, profession - nation) cuboid. The graph cuboid can be ((gender, nation,*) - (*,nation,*)) or, for brevity, intuition is that we would like to explore whether the profession (gender, nation - nation). The starting nodes on this cuboid are of the source node, in addition to its gender, affects the number of aggregated graph nodes based on their gender, nation attribute observed relationships. In this contrived example, the aggregated values. Similarly, the ending nodes are aggregations of raw graph edges from cuboid (gender - nation) are split almost evenly when nodes based on the nation attribute values. Starting and ending drilling down to the (gender, profession - nation) cuboid. Thus, nodes in this cuboid are interconnected according to the raw this particular navigation step does not seem to reveal interesting graph edges. These raw data edges are consolidated producing a correlations for this data, conditioned on what is already observed graph cube edge along with a measure. The user may choose any in the (gender - nation) cuboid. combination of functions based on attributes on the constituent On the right part of Figure 1, we depict another possible drill- nodes and edges. down, this time to the (gender, nation - nation) cuboid. In this In many applications, edges of the data graph may have at- new context, some interesting irregularities are revealed. First, tributes that can also be treated during exploratory analysis as while female users are linked evenly to users from Greece and dimensions. Attributes on the edges of the data graph can be Spain, when these links are conditioned based on her nationality aggregated creating yet another set of cuboids in an edge-cube we can see that females from Spain are mainly linked to users lattice. For example, in a social network a connection can have from the same country. Similarly, French males are mostly linked several attributes like the typeT of the relationship (family, friend, to users from Spain. Thus, while cuboid (gender - nation) suggest sibling etc.) and the date D that this connection was established. a uniform relationship based on the nationality of the target node, Naturally the analyst may want to include those attributes and cuboid (gender, nation - nation) reveals that this is not true for observe their interaction with the node attributes. As an exam- certain members of the user community. It is worth noting that ple, let us consider the case where the data graph edges have a the majority of the links in the (gender, nation - nation) cuboid Type (T) and a Date (D) dimension (the latter being rolled-up in still follow the same uniform pattern suggested by the (gender - a suitable level, e.g. day, year or month). The edge-cube lattice in nation) cuboid, since most links emanate from female users in this example contains four cuboids, namely (*), (T), (D), and (T,D). Greece and male users in Spain. Thus, the examples discussed These cuboids can also participate in the Cartesian product of the above are exceptions to what is suggested by the (gender - nation) graph cube computation adding another dimension in the final cuboid. These are depicted in red color inside the (gender, nation cube. A cuboid in this extended cube is denoted as (starting node- - nation) cuboid. aggregation - edge-aggregation - ending-node-aggregation). 85 Figure 2: The graph cube when both node attributes (side data cubes) and edge attributes (middle data cube) are being used. The graph cube lattice is produced by taking the Cartesian product of the three data cube lattices that form the constituent data cubes. Figure 2 depicts the graph cube lattice in this extended example 4.2 External Entropy Metric where both node and edge attribute values are being used in the The edges from a cuboid Ci can be represented as a virtual rela- analysis. In what follows, for simplicity, we will only refer to tion. Each record in this virtual relation is associated with (i) a examples where attributes on the nodes are being used when set of attribute values s 1 , . . . st derived from the starting nodes of forming the graph cube. However, our techniques also work the corresponding edge, (ii) a set of values e 1 , . . . ew derived from when attributes on the edges take also part in the analysis. the ending nodes and (iii) an aggregate value a that denotes the result of the selected aggregate function applied over the selected measures from these constituent nodes and edges. In the example of Figure 1, edge (female, Spain) of cuboid (gender - nation) will 4 USING ENTROPY TO NAVIGATE THE be mapped to a single row (female, Spain, 310) in the virtual ta- GRAPH CUBE ble. Each such record r j =(s 1 , . . . st , e 1 , . . . ew , a) can be viewed as 4.1 Main concepts a discrete probability distribution P(s 1 , . . . st , e 1 , . . . ew ) by nor- In this work, we present techniques that help the analyst identify malizing the aggregate a value on each record by the sum of all irregularities when navigating different aggregations of the orig- aggregate values in the instance of the relation. Thus, record r j is associated with a probability value p(a j ) = Ím j(a ) . In our a inal data graph. Because of the exponential number of cuboids i =1 i in the graph cube, it is extremely difficult to manually explore all example, the probability value for the record that maps to edge 310 (female,Spain) will be 301+310+711+720 . The external entropy (eH) possible cuboids and all navigation steps among them (roll-up, drill-down) in search for interesting patterns. This realization of a cuboid is defined as the negative of the logarithm of the provides the motivation for our framework. We seek to provide probability distribution of the records in the virtual relation (m the analyst with solid mathematical tools derived from informa- in the formula bellow refers to the number of edges in the cuboid tion theory and in particular the information entropy, that will that also equals the number of records in the virtual table). help her reveal interesting irregularities. In [5] we introduced two types of entropy calculations. The Õ m first one measures the significance of a whole cuboid and it is eH (Ci ) = − p(a j ) ∗ log2 p(a j ) (1) j=1 called external entropy. This type of entropy is used to detect whether a drill-down process during exploratory analysis to a A drill-down process in the graph cube lattice is triggered more detailed cuboid provides additional insights or not. In our by adding another attribute (starting or ending) in cuboid Ci . running example, external entropy calculations on the (gender, This leads the analyst to another more detailed cuboid Ck an the profession - nation) and (gender - nation) cuboid will suggest that next level of the lattice. We refer to cuboid Ck as the "child" of no apparent irregularities are revealed by this drill-down and it Ci , while Ci is the "parent" of Ck . While drilling down from the can, thus, be omitted. In contrast, the external entropy metric parent Ci to the child Ck we can calculate the delta-entropy, i.e. will suggest that the drill down to the (gender, nation - nation) the difference between the two external entropies as: cuboid reveals certain skew in the calculated relationships that deviate from what is expected by observing the relationships δ ..(Ck ,Ci ) = eH (Ck ) − eH (Ci ) (2) in the (gender - nation) cuboid. The second type is the internal The delta entropy is a non-negative number. This is because entropy that evaluates the relationships inside a cuboid. Internal the external entropy of the child cuboid Ck is greater or equal entropy can help steer the user towards surprising, skewed rela- to the external entropy of its parent Ci . The maximum external tionships (such as those depicted in red in the figure) within a entropy of the child is obtained when the aggregate a of each large cuboid, eliminating relationships that do not reveal trends edge is distributed evenly among the more detailed edges in Ck that deviate from the expected behavior. and their number is maximized. Let dmax denote the number of In what follows, we first introduce the suggested entropy possible values of the attribute on which the drill down process calculations used in our navigation framework. More details was performed. In order to maximize the entropy of a child cuboid, on these metrics can be found in [5]. We discuss a graph cube an edge with aggregate value aij in Ci is replaced during the drill- analysis workflow that can be used for processing very large down with dmax more detailed edges in Ck with aggregate values graph cubes. ai aok = d j . Thus, the maximum possible external entropy value max 86 of the child cuboid given its parent is Õ m p(aij ) i eHmax (Ck ) = − p(aij ) ∗ log2 (3) j=1 dmax The external entropy rate quantifies how informative, the pro- cess of drilling down from parent Ci to its child Ck is: eH (Ck ) − eH (Ci ) eHr at e (Ck , Ci ) = i (4) eHmax (Ck ) − eH (Ci ) This rate takes values between 0 and 1. A value that is close to 1 implies that the drill-down process doesn’t change signifi- cantly the distribution of the records and, thus, no new insights are given to the analyst. The exact opposite happens when the value is close to, or zero. We can therefore exclude less interest- ing navigations in the lattice by defining a maximum external entropy rate threshold value between zero and one. When the external entropy rate of a drill down navigation step surpasses the threshold, then this drill down is omitted from consideration. Figure 3: Graph Cube Analysis Workflow 4.3 Internal Entropy Metric With similar arguments we can introduce an internal entropy rate threshold in order to select subgraphs within a cuboid that In Figure 3 we depict the distinct steps involved in using our differ significantly from the rest of the cuboid data. Since we techniques for analyzing massive graph data cubes. After the consider directed data graphs, we distinguish between two kinds graph cube is computed, we first utilize an external entropy rate of internal entropy, namely starting internal entropy and ending threshold in order to prune edges of the lattice and, consequently, internal entropy. cuboids that do not provide significant insights with respect Consider cuboid Ci with l distinct combinations of starting to their ancestors and descendants. For those cuboids that are y y y attribute values of the form (s 1 , s 2 , . . . , ss ). Let my is the sum connected by edges suggested by this process, we compute the of the aggregate values of all such edges, where y ∈ [1, l]. For internal entropy rates (for starting and ending attributes aggre- each such combination (indicated by parameter y) there are fy gated at the level denoted by the corresponding cuboid). We edges with different combinations of ending attribute values. can then use a user-provided internal entropy rate threshold to Let zqy be sum of their aggregate values as well. We calculate only return relationships in these cuboids that do not exceed the the starting internal entropy as the conditional entropy of the threshold or, we can sort them and return the top-k selections in ending attributes’ values conditioned from each starting attribute increasing order of internal entropy rate. combination of values. 6 EXPERIMENTS Õ fy z qy y siH (Ci ) = − y y p(q j ) ∗ log2 p(q j ) y where p(q j ) = (5) In this section, we provide preliminary results from applying our j=1 my suggested framework on three real social network datasets. The focus on this exposition is to first highlight the pruning power The ending internal entropy eiH is defined in an analogous of using entropy to navigate very large graph cubes and then to manner. As in the case of external entropy, we introduce the discuss some of the main trends observed in the social datasets internal entropy rate (for the starting or ending internal entropy, used. respectively) as the fraction between the (starting/ending) inter- The datasets used are summarized in Table 1. The Twitter nal entropy and the maximum possible value of internal entropy. dataset was crawled by our team and contains 3 attributes: gen- The value of the internal entropy rate is between 0 and 1 and can der, location and language, used in each user profile. We also be used to select the most prominent trends within a cuboid, as crawled the VK dataset from VKontakte, the largest European on- will be explained in the next Section. line social networking service. The sample contains 5 attributes: birthyear, country, city, gender and education level of the user. 5 GRAPH CUBE ANALYSIS WORKFLOW Finally, the Pokec dataset, available from [20] is a social-network Motivated by the examples of the previous subsections, in this from Slovakia and uses 6 node attributes: age, region, gender, work we present techniques that registration year, public profile and completion percentage of the • Weigh all possible navigations within a graph cube lattice profile. and suggest drill-down operations that reveal surprising In order to compute the graph cubes of these datasets, we set trends, conditioned on what is observed in the more ab- up a small cluster of 4 PCs equipped with Intel i7-3770 CPUs stract cuboids contained in the cube. This process elimi- clocked at 3.40GHz, 4GB of memory and 1TB 7200rpm HDDs. nates a significant portion of the graph cube, steering the We used the popular Apache Spark [34] framework on 8 VMs user towards cuboids that reveal skew that is hidden when (one being the master) running on this cluster. The graph cube focusing in more abstract aggregations. for each dataset was computed using an extension of the BUC • Evaluate the relationships within the cuboids suggested algorithm discussed in [5]. from the previous step in order to reveal parts of data that In first experiment, we utilize the suggested data analysis contain skewed relationships. workflow and evaluate the pruning power of the external and the 87 (a) Twitter dataset (b) VK dataset (c) Pokec dataset Figure 4: Number of records in the graph cube, scaling both internal and external entropy rates Twitter VK Pokec manageable sizes. This suggests that indeed, in these real data, Profiles (nodes) 34M 3,9M 1,6M there is a needle in the haystack that begs to be revealed. This is Relations (edges) 910M 493M 31M more evident in the largest graph cube from the Pokec dataset Number of Attributes 3 5 6 that contains 4096 cuboids and more than 66 billion records. In Number of Cuboids 64 1024 4096 that dataset, a 10% external entropy threshold leads the analyst Graph Cube Records 4M 362M 66,3B to focus on less than 0.002% of the aggregated graph cube records Graph Cube Size 143MB 235GB 1.58TB that contain 9 out of the 10 more prominent associations (when ranked in decreasing order of their internal entropy). Cluster CPUs 4 × 4 Cores In Figures 5a, 5b and 5c we depict the filtered sub-lattices (sets Cluster RAM 4 × 4 GB of cuboids) selected when using an external rate threshold of 3.5% Table 1: Description of datasets and hardware used in the graph cube analysis workflow of Figure 3. For the Twitter dataset 17 out of the 64 cuboids of the graph cube are chosen. For the VK dataset 9 out of 1024 cuboids are retained. Finally, for the Pokec dataset only 10 from the 4096 cuboids are kept for post- internal entropy metrics. Figures 4a,4b and 4c illustrate how the processing. Based on the characteristics of the datasets shown in starting internal and external rates reduce the number of records Table 1 we observe that the external entropy helps prune more of the graph cube, in each dataset. Plots for the using the ending cuboids when the number of node attributes is increased, as this internal entropy are similar and are omitted due to lack of space. results in larger lattices for the full graph cube. The plots suggest a steep reduction in the sizes of the graph These filtered cuboids are used as input for the final stage of cubes for all datasets, as the respective entropy rate thresholds our workflow that further selects parts of these cuboids based in are increased. We observe that using thresholds in the ranges their internal entropy. For that step we used a rate threshold of from 5% to 20% helps trim the million or billions (in the case of 20% and present in Table 2 some characteristic results for each the Pokec dataset) records in the corresponding graph cubes to 88 *-* G-* N-* G,L-* G-G G-N N-G N-N N-L G,L-G G,L-N N-G,L N-N,L N,L-L N,L-G,L N-G,N,L N,L-N,L N,L-G,N,L (a) Twitter dataset *-* *-* *-A G-* *-E L-* *-R A-* *-G *-A,N G-N G-G L-L A-G G-G R-G G-A,N G-G,A L-L,A A,R-G G,E-A,N A,R-G,A (b) VK dataset (c) Pokec dataset Figure 5: Selected sub-lattices for a 3.5% external entropy rate threshold dataset. Due to space limitations the attributes in the table are Using the entropy-based techniques in the Pokec dataset we shown with their first letter. Thus, N stands for nation, L for see other interesting trends. First, we observe that most relation- language, G for gender, A for age and E for education level. ships are towards women. Specifically, users between 19 and 22 In the Twitter dataset, we find that users from all countries years old have mainly connections to women. On the other hand, follow mostly users from the USA. Exceptions include users from 19-year-old females are more frequently connected with other Portugal, Romania, Latvia, Venezuela, Taiwan, Chile, Brunei, females. With respect to location, connections between the same Brazil and Norway. Users of these countries seek to follow mainly cities dominate. Also, the most connections are with users from other users from the same country. From the cuboid (nation - the Presovsky kraj and Presov regions. Users from most of the gender) the entropy reveals that users from Monaco and Nauru regions are connected with female users except for those from follow males 2.2 times more often than females. Similarly, users Nitriansky kraj and Nitra that are associated with more men. from Thailand follow men 1.7 times more often than women. On 19-year-old users from Presovsky kraj, Bardejov are connected the contrary, Mongolia users follow women 2.1 times more often mainly with male peers. Users between 32 and 37 years old from than men. Banskobystricky kraj, Banska are connected mainly with females From the VK dataset, we mine some other trends. Most con- that are 22 years old. nections are towards 35-year-old users from Russia and after The rightmost column of Table 2 depicts the support of the that from Ukraine. Most connected users are born between 1986 corresponding trend. The numbers validate our intuition that and 1990. Users from USA are connected mostly with women, skewed trends are quite often hidden within valleys of uniform the same appears for users from Kazkhstan. Users connected behavior. Indeed, most trends have small support values and with Turkish profiles are 70% men. Women are related uniformly would be, thus, missed by a frequent itemset counting algorithm. with both genders while men are connected 60% with other men and 40% with women. Most users are connected to other profiles 7 RELATED WORK without a university degree and after that with users that got The work in [35] introduced the graph cube that takes into ac- their diploma between 2008-2012. count both attribute aggregation and structure summarization of the underlying graphs. This work is mainly focused on cuboids 89 Dataset Trend Cuboid min(siHr at e ,eiHr at e ) Support Twitter * - En N-L 11.05% 87.12% Twitter * - USA N-N 12.15% 36.07% Twitter Portugal - Portugal N-N 12.21% 0.054% Twitter Romania - Romania N-N 15.01% 0.025% Twitter Latvia - Latvia N-N 15.23% 0.006% Twitter Venezuela - Venezuela N-N 15.73% 0.009% Twitter Taiwan - Taiwan N-N 16.10% 0.006% Twitter Chile - Chile N-N 16.39% 0.029% Twitter Brunei - Brunei N-N 16.88% 0.001% Twitter Brazil - Brazil N-N 16.89% 0.564% Twitter Norway - Norway N-N 17.03% 0.061% Twitter Monaco - Male N-G 17.31% 0.002% Twitter Nauru - Male N-G 17.71% 0.00004% Twitter Thailand - Male N-G 17.93% 0.021% Twitter Mongolia - Female N-G 18.06% 0.001% VK * - 35, Russia|Ukraine * - A, N 13.23% 0.963% VK * - [1986..1990] *-A 14.11% 2.388% VK Female - Usa|Kazakhstan G-N 15.53% 0.478% VK Male - Turkey G-N 16.42% 0.082% VK Male - Male G-G 16.51% 37.74% VK * - No Diploma|Diploma 2008-2012 *-E 17.01% 13.42% Pokec age:[19..22] - Female A-G 12.97% 0.098% Pokec age:19, Female - Female A-G 13.05% 0.001% Pokec Cityx - Cityx (same city connection) L-L 15.66% 9.908% Pokec Female - Male , Male - Female G-G 15.98% 65.34% Pokec * - Presovsky kraj|Presov region *-R 16.18% 0.032% Pokec Nitrianskykraj, Nitra - Man R-G 16.47% 0.001% Pokec age:19, Presovsky kraj|Bardejov - Male A, R - G 17.02% 0.712% Pokec age:[32..37], Branska - Female,22 A, R - G, A 17.11% 0.012% Table 2: Main trends derived from the three social datasets that aggregate the starting and ending nodes on the same di- The authors of [24] propose a novel framework for recon- mensions, e.g. (nation - nation). More general aggregations that structing multidimensional data from stored aggregates using differentiate between the starting and ending nodes of the graph the maximum entropy principle. In a nutshell, the proposed tech- are not specifically mentioned but can be addressed under a cross- nique finds the model with the least information (maximum cuboid computation that is mentioned as an extension. In our entropy) given a set of constraints that can be the 2n − 2 differ- work, we elevate such cuboids as first-class-citizens in the graph ent aggregations in the cube (excluding the raw data and the cube framework. As our experiments with real datasets indicate, grand total aggregate). The method uses a multi-pass algorithm such cuboids often hold significant insights for the underlying called Iterative Proportional Filtering (IPF) that converges to the interconnections. Another distinction is that the work of [35] maximum entropy solution. considers all records in the proposed graph cube. As we show The information entropy was first introduced in [29] as a mea- in our work, only a small part of a complex graph cube carries sure of unpredictability of information content. It measures how interesting information when analyzed under the lens of our much information there is in an event. Entropy is frequently used entropy-based navigation framework. for splitting decisions when computing Decision Trees [27] The A recent work [33] considers aggregate attributed graphs. The information gain measures the change in information entropy authors name their model as a hyper graph cube and show how from a prior state to new state after a split. Our external entropy to compute it using MapReduce batches. The hyper graph cubes rate measure utilizes the information gain metric in the nomina- aggregate separately attributes at vertices and edges and then tor of its respective formula but differs in that it also takes into calculate the Cartesian product between them. Thus, they do consideration the maximum possible increase in the entropy of a not exploit and analyze the existing relationships under different child cuboid in a drill down step. By conditioning the information levels of aggregation on the starting and ending nodes of the gain over this quantity we are able to obtain the bounds that our graph. OLAP-style summarization in the context of RDF graphs selection algorithm utilizes. has been recently studied in [2]. The most significant difference Recently, an entropy-based model has been proposed [25] in from the previous works in graph cubes, is that our techniques order to estimate the strength of social connections by analyzing address the vast size and complexity of the produced cuboids. To users’ occurrences in space and time. This work considers triplets the best of our knowledge we are the first that utilize the entropy of (user, location, time) data and utilizes entropy to measure in order to filter the information of a graph cube. the diversity of user co-occurrences. In our work, we utilize 90 entropy to measure the diversity within and across graph cuboids. [4] Dritan Bleco and Yannis Kotidis. 2014. Graph Analytics on Massive Collections The works of [3, 4] consider the case of analyzing very large of Small Graphs. In Proceedings of the EDBT, Athens, Greece. 523–534. [5] Dritan Bleco and Yannis Kotidis. 2017. Entropy-based Selection of Graph collections of smaller data graphs, while in this work we consider Cuboids. In Proceedings of the 5th International Workshop on Graph Data a singe massive graph that is under investigation. Management Experiences and Systems (GRADES). [6] C. Chen, X. Yan, F. Zhu, J. Han, and P. S. Yu. 2008. Graph OLAP: Towards Our techniques can be used in conjunction with existing sys- Online Analytical Processing on Graphs. In ICDM. 103–112. tems for parallel graph processing [30] and tools like Perseus [19] [7] M. Das, S. Thirumuruganathan, S. Amer-Yahia, G. Das, and C. Yu. 2014. An Ex- that summarizes an input graph using statistics such as PageRank, pressive Framework and Efficient Algorithms for the Analysis of Collaborative Tagging. VLDB J. 23, 2 (2014), 201–226. radius, degree and flags outlier nodes [31], graph visualization [8] Mohammed Elseidy, Ehab Abdelhamid, Spiros Skiadopoulos, and Panos Kalnis. tools [18], or with systems that recommend promising visualiza- 2014. GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph. tions on aggregated datasets like SEEDB [32]. Our techniques PVLDB 7, 7 (2014), 517–528. [9] W. Fan, X. Wang, Y. Wu, and J. Xu. 2015. Association Rules with Graph may also be combined with the work of [13] that seeks intuitive Patterns. PVLDB 8, 12 (2015), 1502–1513. drill-down operations from aggregated views of data. [10] A. Ghrab, O. Romero, S. Skhiri, A. A. Vaisman, and E. Zimányi. 2015. A Framework for Building OLAP Cubes on Graphs. In Proceedings of ADBIS. Application of graph mining techniques [1, 8, 17, 21, 23, 26] [11] J. Gray, A. Bosworth, A. Layman, and H. Pirahesh. 1996. Data Cube: A Re- is also orthogonal to our framework and can be used in con- lational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub- junction. For instance, the work of [23] looks for structural pat- Total. In ICDE. 152–159. [12] W. H. Inmon. 1992. Building the Data Warehouse. QED Information Sciences, terns (or motifs) in the k-hop neighborhood of a node. The work Inc., Wellesley, MA, USA. of [21] suggests aggregation of graph nodes scores on vertices [13] M. Joglekar, H. Garcia-Molina, and A. G. Parameswaran. 2016. Interactive that contain some attribute of interest. Unlike conventional ice- Data Exploration with Smart Drill-down. In Proceedings of ICDE. [14] Niranjan Kamat, Prasanth Jayachandran, Karthik Tunga, and Arnab Nandi. berg queries, the authors propose an aggregation method that is 2014. Distributed and Interactive Cube Exploration. In IEEE 30th International based on random walks and demonstrate their effectiveness and Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31 - April 4, 2014. 472–483. scalability. The authors of [7] explore data mining techniques to [15] Kifayat-Ullah Khan, Kamran Najeebullah, Waqas Nawaz, and Young-Koo Lee. analyze tagging behavior on social graphs. The authors of [9] 2014. OLAP on Structurally Significant Data in Graphs. CoRR abs/1401.6887 introduce graph-pattern association rules (GPAR). These rules ex- (2014). [16] Ralph Kimball and Margy Ross. 2002. The Data Warehouse Toolkit: The Complete tend traditional association rules with graph patterns that specify Guide to Dimensional Modeling (2nd ed.). John Wiley & Sons, Inc., New York, association between entities in a social graph. NY, USA. There is recent work on systems that permit interactive ex- [17] Benny Kimelfeld and Phokion G. Kolaitis. 2014. The Complexity of Mining Maximal Frequent Subgraphs. ACM Trans. Database Syst. 39, 4 (2014), 32:1– ploration of very large data cubes. For example DICE [14] is a 32:33. distributed system that utilizes faceted exploration in order to [18] D. Koop, J. Freire, and C. T. Silva. 2013. Visual Summaries for Graph Collections. In IEEE Pacific Visualization Symposium, PacificVis 2013, February 27 2013- limit the number of possible queries in an interactive session. March 1, 2013, Sydney, NSW, Australia. 57–64. Extending this technique for graph cubes is an interesting re- [19] D. Koutra, D. Jin, Y. Ning, and C. Faloutsos. 2015. Perseus: An Interactive search direction. Our entropy-based cube navigation framework Large-Scale Graph Mining and Visualization Tool. PVLDB 8, 12 (2015). [20] Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network can be combined with the idea of faceted exploration, either as a Dataset Collection. http://snap.stanford.edu/data. (June 2014). pre-processing step that limits the set of possible aggregations [21] N. Li, Z. Guan, L. Ren, J. Wu, J. Han, and X. Yan. 2013. gIceberg: Towards (cuboids) that need to be considered, or during interactive explo- Iceberg Analysis in Large Graphs. In 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013. 1021–1032. ration by using the external/internal entropy rates in order to [22] Xiaolei Li, Jiawei Han, and Hector Gonzalez. 2004. High-Dimensional OLAP: steer the user towards skewed correlations. A Minimal Cubing Approach. In (e)Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, August 31 - September 3 2004. 528–539. 8 CONCLUSIONS [23] W. E. Moustafa, A. Deshpande, and L. Getoor. 2012. Ego-centric Graph Pattern Census. In Proceedings of ICDE. 234–245. Graph data is becoming popular due to emerging applications [24] T. Palpanas and N. Koudas. 2001. Entropy Based Approximate Querying and that need to process and analyze interconnected datasets. In this Exploration of Datacubes. In Proceedings of SSDM. 81–90. work we proposed a graph data analysis framework based on [25] H. Pham, C. Shahabi, and Y. Liu. 2013. EBM: An Entropy-Based Model to Infer Social Strength from Spatiotemporal Data. In Proc. of SIGMOD. the graph cube operator. Similar to the data cube, graph cubes [26] G. Qi, C. C. Aggarwal, and T. S. Huang. 2012. Community Detection with contain an exponential number of aggregations of the raw data Edge Content in Social Media Networks. In IEEE 28th International Conference graph. Moreover, these aggregations are not simple flat records on Data Engineering (ICDE 2012), Washington, DC, USA (Arlington, Virginia), 1-5 April, 2012. 534–545. but rather complex graph structures that make their exploration [27] J. R. Quinlan. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (March cumbersome. 1986), 81–106. [28] N. Roussopoulos, Y. Kotidis, and M. Roussopoulos. 1997. Cubetree: Organi- To overcome these obstacles our framework utilizes two novel zation of and Bulk Incremental Updates on the Data Cube. In Proceedings of entropy metrics that help locate unusual patterns hidden within ACM SIGMOD, Tucson, Arizona. 89–99. billions of graph data aggregations. We put our framework to the [29] C. E. Shannon. 2001. A Mathematical Theory of Communication. SIGMOBILE Mob. Comput. Commun. Rev. 5, 1 (Jan. 2001), 3–55. test using three real social datasets of realistic sizes. Our prelimi- [30] V. Spyropoulos and Y. Kotidis. 2017. Digree: Building A Distributed Graph nary results demonstrate that indeed entropy-guided exploration Processing Engine out of Single-node Graph Database Installations. SIGMOD can help prune lots of uniform correlations enabling the analyst Record 46, 4 (December 2017), 22–27. [31] J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos. 2005. Neighborhood Formation to focus on skewed parts of the data that often reveal interesting and Anomaly Detection in Bipartite Graphs. In Proceedings of ICDM. trends. [32] M. Vartak, S. Rahman, S. Madden, A. G. Parameswaran, and N. Polyzotis. 2015. SEEDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics. PVLDB 8, 13 (2015), 2182–2193. REFERENCES [33] Zhengkui Wang, Qi Fan, Huiju Wang, Kian-Lee Tan, Divyakant Agrawal, and [1] A. Arora, M. Sachan, and A. Bhattacharya. 2014. Mining Statistically Sig- Amr El Abbadi. 2014. Pagrol: Parallel graph olap over large-scale attributed nificant Connected Subgraphs in Vertex Labeled Graphs. In International graphs. In ICDE. Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June [34] Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and 22-27, 2014. 1003–1014. Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. In Proceedings [2] E. Akbari Azirani, F. Goasdoué, I. Manolescu, and A. Roatis. 2015. Efficient of HotCloud. OLAP operations for RDF analytics. In ICDE Workshops. 71–76. [35] Peixiang Zhao, Xiaolei Li, Dong Xin, and Jiawei Han. 2011. Graph Cube: On [3] D. Bleco and Y. Kotidis. 2012. Business Intelligence on Complex Graph Data. In Warehousing and OLAP Multidimensional Networks. In Proceedings of ACM Proceedings of the 2012 Joint EDBT/ICDT Workshops, Berlin, Germany. 13–20. SIGMOD. 91