Abstract. Benchmarking graph-oriented database workloads and graph-oriented database systems is increasingly becoming relevant in analytical Big Data tasks, such as social network analysis. In graph data, structure is not mainly found inside the nodes, but especially in the way nodes happen to be connected, i.e. structural correlations. Because such structural correlations determine join fan-outs experienced by graph analysis algorithms and graph query executors, they are an essential, yet typically neglected, ingredient of synthetic graph generators. To address this, we present S3G2: a Scalable Structure-correlated Social Graph Generator. This graph generator creates a synthetic social graph, containing non-uniform value distributions and structural correlations, which is intended as test data for scalable graph analysis algorithms and graph database systems. We generalize the problem to decompose correlated graph generation in multiple passes that each focus on one so-called correlation dimension; each of which can be mapped to a MapReduce task. We show that S3G2 can generate social graphs that (i) share well-known graph connectivity characteristics typically found in real social graphs (ii) contain certain plausible structural correlations that influence the performance of graph analysis algorithms and queries, and (iii) can be quickly generated at huge sizes on common cluster hardware. Data in real life is correlated; e.g. people living in Germany have a different distribution in names than people in Italy (location), and people who went to the same university in the same period have a much higher probability to be friends in a social network. Such correlations can strongly influence the intermediate result sizes of query plans, the effectiveness of indexing strategies, and cause absence or presence of locality in data access patterns. Regarding intermediate result sizes of selections, consider: SELECT personID FROM person WHERE firstName = 'Joachim' AND addressCountry = 'Germany' Query optimizers commonly use the independence assumption for estimating the result size of conjunctive predicates, by multiplying the estimates for the individual predicates. This would underestimate this result size, since Joachim is more common in Germany than in most other countries; similar would happen e.g. when querying for firstName 'Cesare' from 'Italy'. Overestimation can also easily happen, if we would query for 'Cesare' from 'Germany' or 'Joachim' from 'Italy ' (i.e. anti-correlation). This correlation problem has been recognized in relational database systems as relevant, and some work exists to detect correlated properties inside the same table (e.g., see [13] ). Still, employing techniques for the detection of correlation is hardly mainstream in relational database management, and this is even more so when we start considering correlations between predicates that are separated by joins. Consider for instance the DBLP example of co-authorship of papers that counts the number of authors that have published both in TODS and in the VLDB Journal: SELECT COUNT( * ) FROM paper pa1 JOIN journal jn1 ON pa1.journal = jn1.ID paper pa2 JOIN journal jn2 ON pa2.journal = jn2.ID WHERE pa1.author = pa2.author AND jn1.name = 'TODS' AND jn2.name = 'VLDB Journal' The above query is likely to have a larger result size than a query that substitutes 'TODS' for 'Bioinformatics', even though Bioinformatics is a much larger publication than TODS. The underlying observation is that database researchers are likely to co-publish in TODS and The VLDB Journal, but are much less likely to do crossdisciplinary work. For database technology, this example poses (i) a challenge to the optimizer to adjust the estimated join hit ratio of pa1.author = pa2.author downwards or upwards depending on other (selection or join) predicates in the query (ii) provide indexing support that can accelerate this query: the anti-correlated query (Bioinformatics and The VLDB Journal) has a very small result size and thus could theoretically be answered very quickly. However, just employing standard join indices will generate a large intermediate result for the Bioinformatics sub-plan containing all Bioinformatics authors, of which only a minute fraction is actually useful for the final answer. Summarizing, correlated predicates are still a frontier area in database research, and such queries are generally not well-supported yet in mature relational systems. This holds still more strongly in the emerging class of graph database systems, where we argue the need for correlation-awareness in query processing is even higher. In the particular case of RDF, its graph data model is expressly chosen to work without need for an explicit schema, such that graph datasets get stored as one big pile of edges (in particular, subject-property-object "triples"). Here we see a dualism between structure and correlation: in the relational model, certain structure is explicit in the schema, whereas in RDF such structure only re-surfaces as structural correlation. That is, it will turn out a journal paper (subject) always happens to have one title property, one issue property, one journalName, etc; and that these properties exclusively occur in connection to journal issues. The extreme flexibility of RDF systems in the data they can store, thus poses a significant challenge to SPARQL query optimizers, as they need to understand such correlations to get the planning of even basic queries right. Other graph database systems which use a richer data model, where nodes have a declared structure, suffer less from this problem. Still, when considering that graph analysis queries often involve a combination of (property) value constraints and structural constraints (pattern matching), it is likely that correlations between the structure of the graph and the values in them will strongly affect the performance of systems and algorithms. Yet, systems are not sufficiently aware of this, and existing graph benchmarks do not specifically test for this; and synthetic graphs used for benchmarking do not have such structure correlations. As such, we argue that for benchmarking graph data analysis systems and algorithms, it would be very worthwhile if a data generator could generate synthetic graphs which such correlated structure. To our knowledge, there exists no solution for generating a scalable random graph with value and structure correlations. Existing literature on random graph generation [4, 10, 6, 8] either does not consider node properties at all or ignores correlations between them. In this paper, we describe the Scalable Structure-correlated Social Graph Generator (S3G2), and its underlying generic conceptual correlated graph generation framework. This framework organizes data generation in multiple phases that each center around a correlation dimension. In the case of our social graph use case, these dimensions are (i) education and (ii) personal interests. The data generation workflow is constrained by correlation dependencies, where certain already generated data influences the generation of additional data. A graph generator generates new nodes (with property values), and edges between these nodes and existing nodes. The probability to choose a certain value from a dictionary, or the probability to connect two nodes with an edge are thus influenced by existing data values. For instance, the birth location of a person influences probability distribution of the firstName and university dictionaries. As another example, the probability to create a friendship edge is influenced by (dis)agreement on gender, birthYear and university properties of two person nodes. A practical challenge in S3G2 is that a naive approach to correlated graph generation would continuously access possibly any node and any edge in order to make decisions regarding the generation of a next node or edge. For generating graphs of a size that exceeds RAM, such a naive algorithm would grind down due to expensive random I/O. To address this challenge, we designed a S3G2 graph generation algorithm following the MapReduce paradigm. Each pass along one correlation dimension is a Map phase in which data is generated, followed by a Reduce phase that sorts the data along the correlation dimension that steers the next pass. We show that this algorithm achieves good parallel scale-out, allowing it e.g. to generate 1.2TB of correlated graph data in half an hour on a Hadoop cluster of 16 machines. Contributions of our work are the following: (1) we propose a novel framework for specifying the generation of correlated graphs, (2) we show the usefulness of this framework in its ability to specify the generation of a social network with certain plausible correlations between values and structure, and (3) we devise a scalable algorithm that implements this generator as a series of MapReduce tasks, and verify both quality of its result as well as its scalability. In our vision, this data generator is a key ingredient for new benchmarks for graph query processing. Outline. In Section 1, we present our framework for the generation of correlated graphs, and describe how such it maps on a MapReduce implementation. In Section 2 we use our framework to generate a synthetic social network graph. In Section 3 we evaluate our approach, confirming that the generated data has typical social network characteristics, and showing the scalability of our generator. Finally, in Section ??, we review related work before concluding in Section 4. We first formally define the end product of S3G2 which is essentially a directed graph of objects, and introduce the main ingredients of the S3G2 framework. Then, we describe the MapReduce-based generation algorithm that follows from these ingredients. S3G2 generates a directed labeled graph, where the nodes are objects with property values, and their structure is determined by the class a node belongs to. Such a data model is commonly provided by graph database systems, and is more structured than RDF (though it can of course be represented in RDF, and our S3G2 implementation in fact generates RDF output). Definition 1. S3G2 produces a graph G(V , E, P , C) where V is a set of nodes, E is a set of edges, P is a set of properties and C is a set of classes. is set of literal properties of class x in C; P E(x,y) is the set of properties representing relationship edges that go from instances of class x to class y. We now discuss the conceptual framework behind S3G2, which are (i) property dictionaries, (ii) simple subgraph generation, and (iii) edge generation along correlation dimensions. L(x) are generated following a property dictionary specification P D l (D, R, F ), consisting of a dictionary D, a ranking function R and a probability function F (if the context is unclear, we can also write D l , R l and F l ). A dictionary D is simply a fixed set of values: D = {v 1 , .., v |D| }. The ranking function R is a bijection R : D → {1, .., |D|} which gives each value in a dictionary a unique rank between 1 and |D|. The probability density function F : {1, .., |D|} →[0, 1] steers how the generator chooses values; i.e. by having it draw random numbers 0 ≤ p ≤ 1, it chooses the largest rank r such that It finally emits the value v pos from dictionary D from position pos = R(r). Thus, our framework can generate data corresponding to any discrete probability distribution. The idea to have a separate ranking and probability function comes from generating correlated values. In particular, the ranking function R[z](c) is typically parametrized by some parameters z; which means that depending on the parameter z, the value ranking is different. For instance, in case of a dictionary of firstName we could have R [g, c, y]; e.g. the popularity of first names, depending on gender g, country c and the year y from the birthDate property (let's call this birthYear). Thus, the fact that the popularity of first names in different countries and times is different, is reflected by the different ranks produced by function R() over the full dictionary of names. Name frequency distributions do tend to be similar in shape, which is guaranteed by the fact that we use the same probability distribution F () for all data of a property. Thus, the S3G2 data generator must contain property dictionaries D l for all literal properties in l ∈ L(x), and it also must contain the ranking functions R l , for all literal properties defined in all classes x ∈ C. When designing correlation parameters for a ordering function R l , one should ensure that the amount of parameter combinations such as (g, c, y) stays limited, in order to keep the representation of such functions compact. We want the generator to be a relatively small program and not depend needlessly on huge data files with dictionaries and ranking functions. Figure 2 shows how S3G2 compactly represents R [g, c, y], by keeping for each combination of (g, c, y) a small table with only the top-N dictionary values (here N =10 for presentation purposes, but it is typically larger). Rather than storing an ordering of all values, a table like R [male, Germany, 2010] is just an array of N integers. A value j here simply identifies value v j in dictionary D. This table thus only stores the top-N ranked values. In order to avoid storing more information, the values ranked lower than N get their ranks assigned randomly. Given that in a monotonically decreasing probability function like the geometric distribution used here, the probabilities below that rank are very small anyway, this approximation only slightly decreases the plausibility of the generated values. In Figure 2 we see on the left that for (male,Germany,2010) we keep the 10 most popular boys names, which get mapped on the geometric distribution. All other dictionary values (among which Italian names) get some random ranks > 10. On the right, we see that for (male,Italy,2010) these Italian names are actually the most popular, and the German names get arbitrary (and low) probabilities. Simple Graph Generation. Edges are often generated in one go together with new nodes, essentially starting with an existing node n, and creating new nodes to which it gets connected. This process is guided by a degree distribution function N (n) that first determines how many such new children (or descendants) to generate. In many social networks, the amount of neighbour edges h is distributed following a power law distribution (N (h) ∼ γ.h −λ ). In the S3G2 framework, it is possible to make the function N (n i ) that determines the degree of a node n i correlated with its properties, e.g. by having these properties influence λ or γ. For instance, people with many friends in a social network will typically post more pictures than people with few friends (hence, the amount of friend nodes in our use case influences the amount of posted comment and picture nodes). Generating new nodes and connecting them on the fly among mostly themselves and to an existing node n i leads to isolated subgraphs that are dangling off the main graph connected to it by n i . Typically, such subgraphs are small or have the shape of shallow trees if they are larger. Correlation Dimensions. To generate correlated and highly connected graph data, we need a different approach that generates edges after generating many nodes. This is computationally harder than generating edges towards new nodes. The reason is that if node properties influence their connectivity, a naive implementation would have to compare the properties of all existing nodes with all nodes, which could lead to quadratic computational cost and a random access pattern, so the generation algorithm would only be fast as long as the data fits in RAM. Data correlation actually alleviates this problem. We observe that the probability that two nodes are connected is typically skewed with respect to some similarity between the nodes. Given node n i , for a small set of nodes that are somehow similar to it, there is a high connectivity probability, whereas for most other nodes, this probability is quite low. This observation can be exploited by a graph data generator by identifying correlation dimensions. For a certain edge label e ∈ P E(x,y)  , so a single metric function would typically be used. For simplicity of discussion we will assume M = M x = M y in the sequel. We can compute the similarity metric by invoking M (n i ) on all nodes n i , and sort all nodes on this score. This means that similar nodes are brought near each other, and we observe that the larger the distance between two nodes, their similarity difference monotonically increases. Again, we use a geometric probability distribution for F () that provides a probability for picking nodes to connect with that are between 1 and W.t positions apart in this similarity ranking. To fully comply with a geometric distribution, we should not cut short at W.t positions apart, but consider even further apart nodes. However we observe that for a skewed distribution like geometric, the probability many positions away will be minute, i.e. ≤ ϵ (F (W.t) = ϵ). The advantage of this window shortcut is that after sorting the data, it allows S3G2 to generate edges using a fully sequential access pattern that needs little RAM resources (it only buffers W.t nodes). An example of a similarity function M () could be location. Location, i.e., a place name, can be mapped to (longitude,latitude) coordinates, yet for M () we need a singledimensional metric that can be sorted on. In this case, one can keep (longitude,latitude) at 16-bits integer resolution and mix these by bit-interleaving into one 32-bits integer. This creates a two-dimensional space filling curve called Z-ordering, also known in geographic query processing as QuadTiles 3 . Such a space filling curve "roughly" provides the property that points which are near each other in the Euclidean space have a small z-order difference. Note that the use of similarity functions and probability distribution functions over ranked distance drive what kind of nodes get connected with an edge, not how many. The decision on the degree of a node is made prior to generating the edges, using the previously mentioned degree function N (n i ), which in social networks would typically be a power-law function. During data generation, this degree of node n i is fulfilled by randomly picking the required number of edges according to the correlated probability distributions as described before in the example with person who have many friends generating more discussion posts. In case of multiple correlations, and thus multiple passes along correlation dimensions, we determine for each pass the number of edges to generate for a certain node. The overall degree function N (n) = ∑ N CD (n) is the sum of the degree distribution functions over all correlation dimensions CD. Random Dimension. The idea that we only generate edges between the W.t most similar nodes in all correlation dimensions is too restrictive: unlikely connections in a social network that the data model would not explain or make plausible, will occur in practice. Such random noise can be modeled by partly falling back onto uniformly random data generation. In the S3G2 framework this can be modeled as a special case of a correlation dimension, by using a purely random function as rough metric, and a uniform probability function. Hence, data distributions can be made more noisy by making a pass in random order over the data and generating (a few) additional random edges. In the previous discussion we have introduced the main concepts of the S3G2 framework: (i) correlated data dictionaries (ii) simple graph generation (iii) edge generation according to correlation dimensions. We now describe how a MapReduce algorithm is built using these ingredients. 3 See http://wiki.openstreetmap.org/wiki/QuadTiles Tile being filled Window of W most recent tiles Tile of t nodes node for which edges are being generated Fig. 3 . Sliding window of W tiles along the graph.
The Social Intelligence BenchMark (SIB) REF is an RDF benchmark that introduces the S3G2 (Scalable Structure-correlated Social Graph Generator) for generating social graphs that contain certain structural correlations.
S3G2: A Scalable Structure-Correlated Social Graph Generator
Lecture Notes in Computer Science
Lecture Notes in Computer Science
Computer Science