Graphs provide an elegant and versatile solution for modeling complex datasets, especially when the focus of the analysis is on highlighting interesting associations between data entities. Graph cubes permit analysis of the resulting data graphs at various levels of granularity based on their node and edge attributes. In this work, we utilize information entropy measures in order to help the analyst navigate within the rich information contained in a graph cube. Our metrics suggest navigations (drill-downs) towards more detailed data descriptions, conditioned on what has been observed at a coarser resolution. We propose a graph analysis workflow that first suggests interesting cuboids from the exponential collection of aggregations that exist in the graph cube. At a latter step, this workflow handpicks sub-graphs out of these aggregations that deviate significantly from the rest of the data. We experimentally validate our techniques using real datasets and demonstrate that the proposed entropy-based exploration can help eliminate large portions of the respective graph cubes from consideration. Our techniques help locate the "needle in the haystack" and steer the user towards data skew hidden within vast valleys of near-uniform interactions.
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 [
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 [
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. 2
We consider a social network which depicts relationships between diferent 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 diferent 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, afects 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 (gender nation) 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 23=8 possible cuboids. The work of [
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 type T 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).
Figure 2 depicts the graph cube lattice in this extended example where both node and edge attribute values are being used in the analysis. 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. 4 4.1
In this work, we present techniques that help the analyst identify irregularities when navigating diferent aggregations of the original data graph. Because of the exponential number of cuboids in the graph cube, it is extremely dificult 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 [
In what follows, we first introduce the suggested entropy
calculations used in our navigation framework. More details
on these metrics can be found in [
The edges from a cuboid Ci can be represented as a virtual relation. Each record in this virtual relation is associated with (i) a set of attribute values s1, . . . st derived from the starting nodes of the corresponding edge, (ii) a set of values e1, . . . ew 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 rj =(s1, . . . st , e1, . . . ew , a) can be viewed as a discrete probability distribution P (s1, . . . st , e1, . . . ew ) by normalizing the aggregate a value on each record by the sum of all aggregate values in the instance of the relation. Thus, record rj is associated with a probability value p(aj ) = Ímaj i=1(ai ) . In our example, the probability value for the record that maps to edge 310 (female,Spain) will be 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).
m eH (Ci ) = − Õ p(aj ) ∗ log2 p(aj )
j=1
A drill-down process in the graph cube lattice is triggered by adding another attribute (starting or ending) in cuboid Ci . This leads the analyst to another more detailed cuboid Ck an the next level of the lattice. We refer to cuboid Ck as the "child" of Ci , while Ci is the "parent" of Ck . While drilling down from the parent Ci to the child Ck we can calculate the delta-entropy, i.e. the diference between the two external entropies as: δ..(Ck,Ci ) = eH (Ck ) − eH (Ci )
The delta entropy is a non-negative number. This is because the external entropy of the child cuboid Ck is greater or equal to the external entropy of its parent Ci . 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 Ck and their number is maximized. Let dmax 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 aij in Ci is replaced during the drilldown with dmax more detailed edges in Ck with aggregate values aij . Thus, the maximum possible external entropy value aok = dmax (1) (2) of the child cuboid given its parent is (3) (4) m p(aij ) eH miax (Ck ) = − Õ p(aij ) ∗ log2 dmax
j=1
The external entropy rate quantifies how informative, the process of drilling down from parent Ci to its child Ck is: eH (Ck ) − eH (Ci ) eHr at e (Ck , Ci ) =
eH miax (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 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. 4.3
With similar arguments we can introduce an internal entropy rate threshold in order to select subgraphs within a cuboid that difer 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 Ci with l distinct combinations of starting attribute values of the form (s1 , s2y , . . . , ssy ). Let my is the sum y of the aggregate values of all such edges, where y ∈ [1, l ]. For each such combination (indicated by parameter y) there are fy edges with diferent combinations of ending attribute values. Let zqy 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.
fy siH (Ciy ) = − Õ p(qyj ) ∗ log2 p(qyj ) j=1 where p(qyj ) = zqy my (5)
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. 5
Motivated by the examples of the previous subsections, in this work we present techniques that • 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 techniques 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. 6
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 [
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 [
In first experiment, we utilize the suggested data analysis workflow and evaluate the pruning power of the external and the (c) Pokec dataset internal entropy metrics. Figures 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 *-A,N
G-A,N G,E-A,N *-* G-* G-N *-E
G-G G-G,A dataset. Due to space limitations the attributes in the table are 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 (nation gender) 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.
G-* G-G *-* G-N
N-* N-G G,L-* N-N
N-L G,L-G
G,L-N
N-G,L
N-N,L N,L-G,L
N-G,N,L
N,L-G,N,L (a) Twitter dataset
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. 7
The work in [
A recent work [
The authors of [
The information entropy was first introduced in [
Recently, an entropy-based model has been proposed [
Our techniques can be used in conjunction with existing
systems for parallel graph processing [
Application of graph mining techniques [
There is recent work on systems that permit interactive
exploration of very large data cubes. For example DICE [
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.