Despite their versatility, graph data have specific characteristics that make their analysis often challenging. Of particular interest in graph data are the relationships between nodes captured by the edges of the graph. These relationships should be analyzed with respect to attribute values available at the nodes and edges. For example, a data scientist may want to investigate how users of a social network, depending on their gender, relate to other users based on their nationality. This inquiry can be accommodated by aggregating existing relationships (edges) in the data graph based on the attributes of their constituent nodes. This process forms a graph cuboid, as is depicted in Figure 1.
The graph cube contains all such possible cuboids that can be generated given the raw graph data [6,10,15,22,35]. As in 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 cuboids. Moreover, each of these cuboids is not a flat relation, but a complex property graph filled with intrinsic structural information based on the formed relationships and annotated with computed summary statistics over the attributes of the graph nodes and edges. A data explorer, familiar with the simpler multidimensional framework of data cubes, may be overwhelmed when she tries to navigate this data deluge.
In this work, we model the relationships between the graph cuboids as a graph cube lattice produced by taking the Cartesian product of simpler data cubes on the attributes of the nodes and edges of the data graph. Using this model, we propose a graph cube analysis workflow that can be used to explore interesting associations hidden within very large graph cubes. Our suggested workflow utilizes two intuitive entropy measures, introduced in [5], in order to reveal associations that deviate from the expected behavior. The first measure termed as external entropy permit us to suggest certain drill-down navigations that reveal associations that deviate from what has already been observed at the higher-level aggregations of the graph cube. As demonstrated by our experiments, from the exponential possible navigations in the graph cube, only a very small percentage of them leads to interesting observations. The external entropy helps the data explorer navigates towards interesting cuboids in the graph cube lattice and may be used to prune a significant portion of the lattice from consideration.
In a second step of the workflow, we utilize entropy calculations in order to elevate particular data associations that deviate 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 are the result of skew in the data graph. These interactions become prominent when the raw data is aggregated at the levels denoted by the cuboid under investigation.
In our experimental section we present results of utilizing our techniques while processing real social datasets of realistic sizes. We compare our techniques against an alternative method that prunes parts of the graph cube based on a minimum support threshold, as in association rule mining. We observe that our framework maintains the most varied parts of the data distribution independently of their frequencies. Thus, many interesting trends revealed by our technique that focuses on data skew within and across cuboids, would be missed by methods that merely seek frequent patterns. We also discuss prominent trends reveled by our techniques on the real datasets used.
We consider a social network which depicts relationships between different users. Each user can be represented as a node in a graph. Each user profile has three attributes: gender (male, female), nation (Greece, Spain, France) and profession (doctor, professor, musician). For brevity, we refer to these attributes values by their initial letter. Each edge in the data graph is associated with a numeric value that indicates the number of interactions between the respective users.
A possible inquiry on this network is to examine how users depending on their gender, relate to other users based on their nationality. To accommodate this query we need to perform three different aggregations. First, starting nodes (i.e. nodes with outgoing edges) are grouped into two aggregate nodes corresponding to gender values male and female, respectively. Similarly, three aggregate nodes corresponding to nations Greece, Spain and France are formed. Finally, each edge of the network, depending on the gender attribute value of its starting node and the nation attribute value of its ending node, is aggregated into an edge between the corresponding aggregate nodes created at the previous steps. At this time, a desired aggregate function can be computed. In this example, we assume that this function is SUM(). The resulting aggregate graph is depicted in the middle of Figure 1. Based on its construction we refer to it as the (gender -nation) cuboid. Continuing with the running example, the cuboid on the left part of the figure depicts the outcome of drilling-down from (gender -nation) to the (gender, profession -nation) cuboid. The intuition is that we would like to explore whether the profession of the source node, in addition to its gender, affects the number of observed relationships. In this contrived example, the aggregated edges from cuboid (gender -nation) are split almost evenly when drilling down to the (gender, profession -nation) cuboid. Thus, this particular navigation step does not seem to reveal interesting correlations for this data, conditioned on what is already observed in the (gender -nation) cuboid.
On the right part of Figure 1, we depict another possible drilldown, this time to the (gender, nation -nation) cuboid. In this new context, some interesting irregularities are revealed. First, while female users are linked evenly to users from Greece and Spain, when these links are conditioned based on her nationality we can see that females from Spain are mainly linked to users from the same country. Similarly, French males are mostly linked to users from Spain. Thus, while cuboid (gender -nation) suggest a uniform relationship based on the nationality of the target node, cuboid (gender, nation -nation) reveals that this is not true for certain members of the user community. It is worth noting that the majority of the links in the (gender, nation -nation) cuboid still follow the same uniform pattern suggested by the (gendernation) cuboid, since most links emanate from female users in Greece and male users in Spain. Thus, the examples discussed above are exceptions to what is suggested by the (gender -nation) cuboid. These are depicted in red color inside the (gender, nation -nation) cuboid.
In our running example, each user profile has three attributes, namely gender (G), nation (N) and profession (P). If we treat these attributes as dimensions in OLAP analysis, the resulting data cube has 2 3 =8 possible cuboids. The work of [35] extended the data cube framework to work on graph data by considering also the relationships between aggregated graph nodes. In particular, consider a data cube for the data attributes of the starting nodes in the graph and another one for the ending nodes. These data cubes share the same dimensions and are, thus, identical in structure (i.e. contain the same set of cuboids). The graph cube can be considered as the Cartesian product of these two data cubes: of the starting-and the ending-cube. In this running example, a graph cuboid can be ((gender, nation, *) -(*,nation, *)) or, for brevity, (gender, nation -nation). The starting nodes on this cuboid are aggregated graph nodes based on their gender, nation attribute values. Similarly, the ending nodes are aggregations of raw graph nodes based on the nation attribute values. Starting and ending nodes in this cuboid are interconnected according to the raw graph edges. These raw data edges are consolidated producing a graph cube edge along with a measure. The user may choose any combination of functions based on attributes on the constituent nodes and edges.
In many applications, edges of the data graph may have attributes that can also be treated during exploratory analysis as dimensions. Attributes on the edges of the data graph can be aggregated creating yet another set of cuboids in an edge-cube lattice. For example, in a social network a connection can have several attributes like the typeT of the relationship (family, friend, sibling etc.) and the date D that this connection was established. Naturally the analyst may want to include those attributes and observe their interaction with the node attributes. As an example, let us consider the case where the data graph edges have a Type (T) and a Date (D) dimension (the latter being rolled-up in a suitable level, e.g. day, year or month). The edge-cube lattice in this example contains four cuboids, namely (*), (T), (D), and (T,D). These cuboids can also participate in the Cartesian product of the graph cube computation adding another dimension in the final cube. A cuboid in this extended cube is denoted as (starting nodeaggregation -edge-aggregation -ending-node-aggregation). In what follows, for simplicity, we will only refer to examples where attributes on the nodes are being used when forming the graph cube. However, our techniques also work when attributes on the edges take also part in the analysis.
In this work, we present techniques that help the analyst identify irregularities when navigating different aggregations of the original data graph. Because of the exponential number of cuboids in the graph cube, it is extremely difficult to manually explore all possible cuboids and all navigation steps among them (roll-up, drill-down) in search for interesting patterns. This realization provides the motivation for our framework. We seek to provide the analyst with solid mathematical tools derived from information theory and in particular the information entropy, that will help her reveal interesting irregularities.
In [5] we introduced two types of entropy calculations. The first one measures the significance of a whole cuboid and it is called external entropy. This type of entropy is used to detect whether a drill-down process during exploratory analysis to a more detailed cuboid provides additional insights or not. In our running example, external entropy calculations on the (gender, profession -nation) and (gender -nation) cuboid will suggest that no apparent irregularities are revealed by this drill-down and it can, thus, be omitted. In contrast, the external entropy metric will suggest that the drill down to the (gender, nation -nation) cuboid reveals certain skew in the calculated relationships that deviate from what is expected by observing the relationships in the (gender -nation) cuboid. The second type is the internal entropy that evaluates the relationships inside a cuboid. Internal entropy can help steer the user towards surprising, skewed relationships (such as those depicted in red in the figure) within a large cuboid, eliminating relationships that do not reveal trends that deviate from the expected behavior.
In what follows, we first introduce the suggested entropy calculations used in our navigation framework. More details on these metrics can be found in [5]. We discuss a graph cube analysis workflow that can be used for processing very large graph cubes.
The edges from a cuboid C i can be represented as a virtual relation. Each record in this virtual relation is associated with (i) a set of attribute values s 1 , . . . s t derived from the starting nodes of the corresponding edge, (ii) a set of values e 1 , . . . e w derived from 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 be mapped to a single row (female, Spain, 310) in the virtual table. Each such record r j =(s 1 , . . . s t , e 1 , . . . e w , a) can be viewed as a discrete probability distribution P(s 1 , . . . s t , e 1 , . . . e w ) by normalizing the aggregate a value on each record by the sum of all aggregate values in the instance of the relation. Thus, record r j is associated with a probability value p(a j ) = a j m i =1 (a i ) . In our example, the probability value for the record that maps to edge (female,Spain) will be 310 301+310+711+720 . The external entropy (eH) of a cuboid is defined as the negative of the logarithm of the probability distribution of the records in the virtual relation (m in the formula bellow refers to the number of edges in the cuboid that also equals the number of records in the virtual table ).
A drill-down process in the graph cube lattice is triggered by adding another attribute (starting or ending) in cuboid C i . This leads the analyst to another more detailed cuboid C k an the next level of the lattice. We refer to cuboid C k as the "child" of C i , while C i is the "parent" of C k . While drilling down from the parent C i to the child C k we can calculate the delta-entropy, i.e. the difference between the two external entropies as:
The delta entropy is a non-negative number. This is because the external entropy of the child cuboid C k is greater or equal to the external entropy of its parent C i . The maximum external entropy of the child is obtained when the aggregate a of each edge is distributed evenly among the more detailed edges in C k and their number is maximized. Let d max denote the number of possible values of the attribute on which the drill down process was performed. In order to maximize the entropy of a child cuboid, an edge with aggregate value a i j in C i is replaced during the drilldown with d max more detailed edges in C k with aggregate values
. Thus, the maximum possible external entropy value of the child cuboid given its parent is
The external entropy rate quantifies how informative, the process of drilling down from parent C i to its child C k is:
This rate takes values between 0 and 1. A value that is close to 1 implies that the drill-down process doesn't change significantly 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 interesting 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.
With similar arguments we can introduce an internal entropy rate threshold in order to select subgraphs within a cuboid that differ significantly from the rest of the cuboid data. Since we consider directed data graphs, we distinguish between two kinds of internal entropy, namely starting internal entropy and ending internal entropy.
Consider cuboid C i with l distinct combinations of starting attribute values of the form (s Let z q y be sum of their aggregate values as well. We calculate the starting internal entropy as the conditional entropy of the ending attributes' values conditioned from each starting attribute combination of values.
The ending internal entropy eiH is defined in an analogous manner. As in the case of external entropy, we introduce the internal entropy rate (for the starting or ending internal entropy, respectively) as the fraction between the (starting/ending) internal entropy and the maximum possible value of internal entropy. The value of the internal entropy rate is between 0 and 1 and can be used to select the most prominent trends within a cuboid, as will be explained in the next Section.
• Weigh all possible navigations within a graph cube lattice and suggest drill-down operations that reveal surprising trends, conditioned on what is observed in the more abstract cuboids contained in the cube. This process eliminates a significant portion of the graph cube, steering the user towards cuboids that reveal skew that is hidden when focusing in more abstract aggregations.
• Evaluate the relationships within the cuboids suggested from the previous step in order to reveal parts of data that contain skewed relationships.
In Figure 3 we depict the distinct steps involved in using our for analyzing massive graph data cubes. After the graph cube is computed, we first utilize an external entropy rate threshold in order to prune edges of the lattice and, consequently, cuboids that do not provide significant insights with respect to their ancestors and descendants. For those cuboids that are connected by edges suggested by this process, we compute the internal entropy rates (for starting and ending attributes aggregated at the level denoted by the corresponding cuboid). We can then use a user-provided internal entropy rate threshold to only return relationships in these cuboids that do not exceed the threshold or, we can sort them and return the top-k selections in increasing order of internal entropy rate.
In this section, we provide preliminary results from applying our suggested framework on three real social network datasets. The focus on this exposition is to first highlight the pruning power of using entropy to navigate very large graph cubes and then to discuss some of the main trends observed in the social datasets used.
The datasets used are summarized in Table 1. The Twitter dataset was crawled by our team and contains 3 attributes: gender, location and language, used in each user profile. We also crawled the VK dataset from VKontakte, the largest European online social networking service. The sample contains 5 attributes: birthyear, country, city, gender and education level of the user. Finally, the Pokec dataset, available from [20] is a social-network from Slovakia and uses 6 node attributes: age, region, gender, registration year, public profile and completion percentage of the profile.
In order to compute the graph cubes of these datasets, we set up a small cluster of 4 PCs equipped with Intel i7-3770 CPUs clocked at 3.40GHz, 4GB of memory and 1TB 7200rpm HDDs. We used the popular Apache Spark [34] framework on 8 VMs (one being the master) running on this cluster. The graph cube for each dataset was computed using an extension of the BUC algorithm discussed in [5].
In first experiment, we utilize the suggested data analysis workflow and evaluate the pruning power of the external and the 4a,4b and 4c illustrate how the starting internal and external rates reduce the number of records of the graph cube, in each dataset. Plots for the using the ending internal entropy are similar and are omitted due to lack of space. The plots suggest a steep reduction in the sizes of the graph cubes for all datasets, as the respective entropy rate thresholds are increased. We observe that using thresholds in the ranges from 5% to 20% helps trim the million or billions (in the case of the Pokec dataset) records in the corresponding graph cubes to manageable sizes. This suggests that indeed, in these real data, there is a needle in the haystack that begs to be revealed. This is more evident in the largest graph cube from the Pokec dataset that contains 4096 cuboids and more than 66 billion records. In that dataset, a 10% external entropy threshold leads the analyst to focus on less than 0.002% of the aggregated graph cube records that contain 9 out of the 10 more prominent associations (when ranked in decreasing order of their internal entropy).
In Figures 5a, 5b and 5c we depict the filtered sub-lattices (sets of cuboids) selected when using an external rate threshold of 3.5% 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 postprocessing. Based on the characteristics of the datasets shown in Table 1 we observe that the external entropy helps prune more cuboids when the number of node attributes is increased, as this results in larger lattices for the full graph cube.
These filtered cuboids are used as input for the final stage of our workflow that further selects parts of these cuboids based in their internal entropy. For that step we used a rate threshold of 20% and present in Table 2 some characteristic results for each shown with their first letter. Thus, N stands for nation, L for language, G for gender, A for age and E for education level.
In the Twitter dataset, we find that users from all countries follow mostly users from the USA. Exceptions include users from Portugal, Romania, Latvia, Venezuela, Taiwan, Chile, Brunei, Brazil and Norway. Users of these countries seek to follow mainly other users from the same country. From the cuboid (nationgender) the entropy reveals that users from Monaco and Nauru follow males 2.2 times more often than females. Similarly, users from Thailand follow men 1.7 times more often than women. On the contrary, Mongolia users follow women 2.1 times more often than men.
From the VK dataset, we mine some other trends. Most connections are towards 35-year-old users from Russia and after that from Ukraine. Most connected users are born between 1986 and 1990. Users from USA are connected mostly with women, the same appears for users from Kazkhstan. Users connected with Turkish profiles are 70% men. Women are related uniformly with both genders while men are connected 60% with other men and 40% with women. Most users are connected to other profiles without a university degree and after that with users that got their diploma between 2008-2012.
Using the entropy-based techniques in the Pokec dataset we see other interesting trends. First, we observe that most relationships are towards women. Specifically, users between 19 and 22 years old have mainly connections to women. On the other hand, 19-year-old females are more frequently connected with other females. With respect to location, connections between the same cities dominate. Also, the most connections are with users from the Presovsky kraj and Presov regions. Users from most of the regions are connected with female users except for those from Nitriansky kraj and Nitra that are associated with more men. 19-year-old users from Presovsky kraj, Bardejov are connected mainly with male peers. Users between 32 and 37 years old from Banskobystricky kraj, Banska are connected mainly with females that are 22 years old.
The rightmost column of Table 2 depicts the support of the corresponding trend. The numbers validate our intuition that skewed trends are quite often hidden within valleys of uniform behavior. Indeed, most trends have small support values and would be, thus, missed by a frequent itemset counting algorithm.
The work in [35] introduced the graph cube that takes into account both attribute aggregation and structure summarization of the underlying graphs. This work is mainly focused on cuboids entropy to measure the diversity within and across graph cuboids. The works of [3,4] consider the case of analyzing very large collections of smaller data graphs, while in this work we consider a singe massive graph that is under investigation.
Our techniques can be used in conjunction with existing systems for parallel graph processing [30] and tools like Perseus [19] that summarizes an input graph using statistics such as PageRank, radius, degree and flags outlier nodes [31], graph visualization tools [18], or with systems that recommend promising visualizations on aggregated datasets like SEEDB [32]. Our techniques may also be combined with the work of [13] that seeks intuitive drill-down operations from aggregated views of data.
Application of graph mining techniques [1,8,17,21,23,26] is also orthogonal to our framework and can be used in conjunction. For instance, the work of [23] looks for structural patterns (or motifs) in the k-hop neighborhood of a node. The work of [21] suggests aggregation of graph nodes scores on vertices that contain some attribute of interest. Unlike conventional iceberg queries, the authors propose an aggregation method that is based on random walks and demonstrate their effectiveness and scalability. The authors of [7] explore data mining techniques to analyze tagging behavior on social graphs. The authors of [9] introduce graph-pattern association rules (GPAR). These rules extend traditional association rules with graph patterns that specify association between entities in a social graph.
There is recent work on systems that permit interactive exploration of very large data cubes. For example DICE [14] is a distributed system that utilizes faceted exploration in order to limit the number of possible queries in an interactive session. Extending this technique for graph cubes is an interesting research direction. Our entropy-based cube navigation framework can be combined with the idea of faceted exploration, either as a pre-processing step that limits the set of possible aggregations (cuboids) that need to be considered, or during interactive exploration by using the external/internal entropy rates in order to steer the user towards skewed correlations.
Graph data is becoming popular due to emerging applications that need to process and analyze interconnected datasets. In this work we proposed a graph data analysis framework based on the graph cube operator. Similar to the data cube, graph cubes contain an exponential number of aggregations of the raw data graph. Moreover, these aggregations are not simple flat records but rather complex graph structures that make their exploration cumbersome.
To overcome these obstacles our framework utilizes two novel entropy metrics that help locate unusual patterns hidden within billions of graph data aggregations. We put our framework to the test using three real social datasets of realistic sizes. Our preliminary results demonstrate that indeed entropy-guided exploration can help prune lots of uniform correlations enabling the analyst to focus on skewed parts of the data that often reveal interesting trends.
: Main trends derived from the three social datasets that aggregate the starting and ending nodes on the same dimensions, e.g. (nation -nation). More general aggregations that differentiate between the starting and ending nodes of the graph are not specifically mentioned but can be addressed under a crosscuboid computation that is mentioned as an extension. In our work, we elevate such cuboids as first-class-citizens in the graph cube framework. As our experiments with real datasets indicate, such cuboids often hold significant insights for the underlying interconnections. Another distinction is that the work of [35] considers all records in the proposed graph cube. As we show in our work, only a small part of a complex graph cube carries interesting information when analyzed under the lens of our entropy-based navigation framework.
A recent work [33] considers aggregate attributed graphs. The authors name their model as a hyper graph cube and show how to compute it using MapReduce batches. The hyper graph cubes aggregate separately attributes at vertices and edges and then calculate the Cartesian product between them. Thus, they do not exploit and analyze the existing relationships under different levels of aggregation on the starting and ending nodes of the graph. OLAP-style summarization in the context of RDF graphs has been recently studied in [2]. The most significant difference from the previous works in graph cubes, is that our techniques address the vast size and complexity of the produced cuboids. To the best of our knowledge we are the first that utilize the entropy in order to filter the information of a graph cube.
The authors of [24] propose a novel framework for reconstructing multidimensional data from stored aggregates using the maximum entropy principle. In a nutshell, the proposed technique finds the model with the least information (maximum entropy) given a set of constraints that can be the 2 n − 2 different aggregations in the cube (excluding the raw data and the grand total aggregate). The method uses a multi-pass algorithm called Iterative Proportional Filtering (IPF) that converges to the maximum entropy solution.
The information entropy was first introduced in [29] as a measure of unpredictability of information content. It measures how much information there is in an event. Entropy is frequently used for splitting decisions when computing Decision Trees [27] The information gain measures the change in information entropy from a prior state to new state after a split. Our external entropy rate measure utilizes the information gain metric in the nominator of its respective formula but differs in that it also takes into consideration the maximum possible increase in the entropy of a child cuboid in a drill down step. By conditioning the information gain over this quantity we are able to obtain the bounds that our selection algorithm utilizes.
Recently, an entropy-based model has been proposed [25] in order to estimate the strength of social connections by analyzing users' occurrences in space and time. This work considers triplets of (user, location, time) data and utilizes entropy to measure the diversity of user co-occurrences. In our work, we utilize