Charaterizing RDF graphs through graph-based measures – framework and assessment

3.2.1.Basic graph measures

In the following, we describe measures that can be applied to graphs in general (cf. Definition 3.1).

We report on the total number of vertices n and the total number of edges m for a graph G. Some works in the literature refer to these values as size and volume, respectively. These measures are relevant, as the number of vertices and edges usually varies drastically across knowledge domains.

In multigraphs, parallel edges represent edges that share the same pair of source and target vertices. Therefore, the measure number of parallel edges, denoted as mp, is defined as

3.2.2.Degree-based measures

In a graph G=(V,E), the degree of a vertex v∈V is the total number of edges that are connected to it. With directed graphs, as is the case of RDF graphs, it is common to distinguish between in-degree and out-degree of a vertex v. For a given v∈V, we define the total degree by means of the in- and out-degree.

In social network analyses, vertices with a high out-degree are said to be “influential”, whereas vertices with a high in-degree are called “prestigious”. To identify these vertices in an RDF graph, we compute the maximum total-, in-, and out-degree of the graph’s vertices, denoted as dmax=maxv∈Vd(v), dmax+=maxv∈Vd+(v), dmax−=maxv∈Vd−(v), respectively. In addition, we compute the graph’s mean total-degree z, which is the arithmetic mean of all vertices’ total-degree, and can be computed via the following equation

Another degree-based measure is h-index, known from citation networks [22], where it is widely established to measure author impact based on publications and citations. In a graph G a value of h means that for the number of h vertices in the graph, the degree of these vertices is greater or equal to h. In order to compute the value through the following equation, as a prerequisite, it is required to have a list of all vertex degrees sorted in descending order.

This measure is an indicator of the importance of a vertex, similar to a centrality measure (see Section 3.2.3). Further, a high value of a graph’s h-index could be an indicator for a “dense” graph and that its vertices are more “prestigious”. As citations in a citation network are incoming edges to vertices, in this work, we report on this network measure for the directed graph (using only the in-degree of vertices) denoted as h+. h takes the undirected graph into account (using in- and out-degree of vertices).

3.2.3.Centrality measures

In social network analyses, the concept of point centrality expresses the importance of nodes in a network. There are many interpretations for the term “importance” and so are measures for centrality [29]. A high centrality value of a vertex generally means that it is more “important”, although for different reasons, as indicated by the different measures.

We compute the maximum point centrality of all vertices V, denoted as Cd.66 To indicate that it is a centrality measure, and not just the maximum degree, the literature often normalizes these values by the total number of all vertices, i.e.,

Besides the point centrality, there is also the measure of graph centralization [18], which is known from social network analysis. This measure may also be seen as an indicator of the type of graph. It expresses the degree of inequality and concentration of vertices by means of a perfectly star-shaped graph, which itself is at most centralized and unequal with regard to its degree distribution. The graph centralization value of one graph G regarding the degree is defined as:

Another centrality measure is PageRank [30], which considers all incoming edges to a vertex to estimate its importance. After computing the PageRank value for all vertices v∈V in the graph G, denoted as pr(V), the maximum PageRank value is defined as

3.2.4.Edge-based measures

As the (average) number of vertices and edges vary highly across knowledge domains [36], it is interesting to measure the so-called “density” of a graph, sometimes referred to as “connectance” or “fill”. The density is computed as the ratio of all edges to the total number of all possible edges. The formula is in accordance with the definition of RDF graphs, which are directed and may contain loops. As mentioned earlier, RDF graphs may contain parallel edges, and thus we provide an additional measure, which uses unique edges only. Therefore, fill_overall and fill, denoted as f and fu, respectively, are defined as follows:

These measures may be used to calculate the probability of an edge between two randomly chosen vertices in the graph G. Comparing the measure fill with centrality measures shows that dense graphs show higher centrality values of the vertices, which in turn leads to higher “connectivity” and linkage among them, as mentioned earlier. This also has a positive impact on navigation through the graph.

As RDF graphs are directed and labeled graphs, the aspect of “navigability” through the graph through RDF predicates is of interest. We analyze the fraction of bidirectional connections between vertices in the graph. These are pairs of vertices forward-connected by some edge, which are also backward-connected by some other edge. The value of reciprocity, denoted as y, is expressed as the ratio of the number of bidirectional edges, denoted as mbi, among all edges in the graph G

High values of reciprocity mean there are many links between vertices that are bidirectional. This value is typically high in citation or social networks.

Another critical group of measures that is described by the graph topology is related to paths. A path is a set of edges one can follow along between two vertices. As there can be more than one path, the diameter is defined as the longest shortest path between two vertices of the network [29], denoted as δ.

The diameter is usually a very time-consuming measure to compute since all possible paths have to be considered. Thus, we used the pseudo diameter algorithm77 to estimate the value of the diameter for the studied RDF graphs. In query optimization over RDF data, this measure may be applied to estimate the cardinality of joins (e.g., subject-object joins), which heavily depends on the paths in an RDF graph.

3.2.5.Descriptive statistical measures

Descriptive statistical measures are useful to describe distributions of some set of values. It can be useful to consult the degree of dispersion of the distribution of interest; in our scenario, it is the distribution of vertex degrees in the graphs. Types of dispersion are, for example, the degree variance σ2, and the degree standard deviation σ,

We compute the variance and the standard deviation for the in- and out-degree distributions of vertices in the graphs, denoted as σ2+, σ2−, and σ+, σ−, respectively. They are defined adequately using the appropriate in- and out-degree values for vertex degree and mean degree of all vertices V of a graph.

Comparing different standard deviation values is not very meaningful, since two different distributions most likely will have different means. Coefficient of variation, denoted as cv, may be consulted to have a comparable measure for distributions with different mean values. It is obtained by dividing the standard deviation σ by the corresponding mean value, z.

As cv may also reflect the type of distribution concerning a set of values, we are especially interested in cv+ and cv−, reflecting the in- and out-degree distributions. A low value of cv− means a constant influence of vertices in the graph (homogeneous group). In contrast, a high value of cv+ means high prominence of some vertices in the graph (heterogeneous group).

Further, the type of degree distribution is an often considered measure of graphs. In some knowledge domains, datasets report on degree distributions that follow a power-law function [24], which means that the number of vertices with degree d behaves proportionally to the power of d−α, for some α∈R. Such networks are called scale-free. The literature has found that values in the range of 2 <α< 3 are typical in many real-world networks [29]. The scale-free behavior also applies to some datasets and measures of RDF datasets [14,15]. However, to reason about whether a distribution follows a power-law can be technically challenging [3], and computing the exponent α, that falls into a specific range of values, is not sufficient. In addition to α (reflecting the total-degree distribution) we also compute the exponent for the in-degree distribution of a graph, denoted as α+ [3], as we are interested in the degree distribution of prominent vertices (RDF objects). Also, to support the analysis of power-law distributions, the framework produces plots for both distributions. A power-law distribution is described as a line in a log-log plot.

Determining the function that fits the distribution may be of high value to estimate the selectivity of vertices and attributes in graphs. The structure and size of datasets created by synthetic datasets, for instance, can be controlled with these measures. Also, an explicit power-law distribution allows for high compression rates of RDF datasets [15].

RQ1: What is an efficient and non-redundant set of features for characterizing RDF graphs?

In order to characterize graphs or sets of graphs within domains efficiently, concise graph descriptions have to be based on efficient, non-redundant feature sets where each feature provides significant information gain.

This question aims at finding a concise and finite set M′⊂M of measures that reduce or eliminate redundancy and maximize information gain through correlation analysis. This step will improve the effectiveness of the resulting set of graph measures and improve their applicability, for instance, as part of machine learning models.

RQ2: Which measures describe and characterize individual knowledge domains most/least efficiently?

Datasets within the LOD cloud are categorized into nine distinct knowledge domains so that each dataset is associated with precisely one specific category. In order to understand the representativeness and variability of topological measures within a knowledge domain, we investigate the heterogeneity of feature values within and across distinct domains through basic statistic metrics and discuss observed values representative for distinct LOD domains. We will refer to this feature set as Mk″ with k∈K. Please note that Mk″⊂M′, ∀k∈K.

This will provide insights into the capacity of individual features to represent the nature of particular domains and may contribute to discriminative models and to filtering out noise features when profiling datasets.

RQ3: Which measures show the best performance to discriminate individual knowledge domains?

Datasets from a knowledge domain exhibit distinct characteristics with respect to topological features of the graphs but also with respect to other features, such as vocabulary adoption. A particular question is which (RDF-) graph measures are most descriptive within one particular knowledge domain. In contrast to RQ2, this research question investigates feature importance for each domain. The findings are of interest to synthetic dataset generators, for example. By generating a synthetic dataset, benchmark suites most often target some particular domain of interest. When generating datasets for the Publications knowledge domain, for example, a generator should follow a specific set of measures, range of values, and used vocabularies, in order to be identified with that category of datasets.

4.2.1.Datasets

We have downloaded a large group of datasets from the LOD Cloud 201788 and prepared it with our framework presented in [36].

From the total number of 1,163 potentially available datasets in the LOD Cloud 2017, 280 datasets were selected based on the criteria: (i) RDF media types statements that were correct for the datasets, and (ii) the availability of data dumps provided by the services. To not stress SPARQL endpoints to transfer large amounts of data, in this experiment, only datasets that provide downloadable dumps were considered.

To dereference RDF datasets, we relied on the metadata (so called data-package) available at DataHub, which specifies URLs and media types for the corresponding data provider of one dataset.99 We collected the datapackage metadata for all datasets and manually mapped the obtained media types from the datapackage to their corresponding official media types that are given in the specifications. For instance, rdf, xml_rdf or rdf_xml were mapped to application/rdf+xml and similar.1010 In this way, we obtained the URLs of 890 RDF datasets. After that, we checked whether the dumps are available by performing HTTP HEAD requests on the URLs. At the time of the experiment, this returned 486 potential RDF dataset dumps to download. For the other not available URLs, we verified the status of those datasets with http://stats.lod2.eu. After these manual preparation steps, the data dumps could be downloaded with the framework.

The framework needs to transform all formats into N-Triples. From here, the number of prepared datasets for the analysis further reduced to 280. The reasons were: (1) corrupt downloads, (2) wrong file media type statements, and (3) syntax errors or other formats than these what were expected during the transformation process. This number seems low compared to the total number of available datasets in the LOD Cloud, though it sounds reasonable compared to recent studies on the LOD Cloud [11,12,21]. Table 2 gives some descriptive statistics about the analyzed datasets.

As graph library we used graph-tool,1111 an efficient library for statistical analysis of graphs. In graph-tool, core data structures and algorithms are implemented in C/C++, while the library itself can be used with Python. graph-tool comes with pre-defined implementations for graph analysis, e.g., degree distributions or more advanced implementations on graphs like PageRank or clustering coefficient. Further, some values may be stored as attributes of vertices or edges in the graph structure. The library’s internal graph-structure may be serialized as a compressed binary object for future re-use. It can be reloaded by graph-tool with much higher performance than the original edgelist. We instantiated the graphs from the binary representation (see next section) and operated on the graph objects provided by the graph-tool library.

4.2.2.Graph measures computation

All graph-based measures introduced in Section 3.2 where already part of the framework introduced in [36]. In order to do a more comprehensive evaluation of the effectiveness of graph measures, we include RDF graph measures from Fernández et al. [15], who provides a comprehensive list and formalization of various RDF graph-based measures. Table 3 gives an overview of all RDF graph-measures we implemented as a module extension3 of our framework.

We worked with lists of vertices, edges, and edge labels (predicates), using Python’s build-in operations for lists in the first place. In order to optimize performance on list operations, we used external libraries.1212 That way, the computation of measures, such as the maximum and mean in-/out-degree of all vertices, was straight-forward. A more complex example is the partial out-degree measure, which is “defined as the number of triples of G in which s occurs as subject and p as predicate”. In order to compute this measure from the perspective of a native graph object in memory, one must create an array of all pairs of source vertices (subjects) and their outgoing edge labels (predicates) and count the number of grouped occurrences of these pairs.

We encourage the interested reader to look into the corresponding package of the framework3 to find the implementation for all measures.

4.2.3.Measure efficiency and measure importance

For RQ1, we will first give an overview of all the measures and their relationship among each other by calculating the Spearman correlation coefficients between all measures. To this end, the Spearman correlation test is employed, since most of the distributions of measure values do not follow a normal distribution. To reduce the number of measures, we employ two popular methods: (a) a low variance test, which filters measures which fall below a certain threshold, and (b) popular univariate statistical tests, from which we choose Chi2, and Mutual Information (MI). Since many of the variables are continuous, and MI only works with discrete values, Maximum Information Non-parametric Estimation (MINE) is utilized additionally. Therefore, M′ is defined as follows:

For RQ2, we will show boxplots as aggregated descriptive statistics for some selected measures. This will give insights into the distribution of values. In order to investigate the variability at the category level, we apply some statistical methods. To show the variability per category, we group all datasets by categories and compute the variance per measure and group. By this means, we can analyze noisy and non-noisy features in terms of variance and assign the corresponding Mk″ for all k∈K.

The variability across categories (vac) is computed by taking the mean of a measure for all datasets in a particular category k∈K computing the standard deviation over the obtained means subsequently. More formally, with val denoting all values for measure m∈M′ and datasets in Dk, with k∈K

For the classification tasks in RQ3, we deploy and tune a Random Forest classifier for both tasks. Initial experiments have shown that Random Forest outperforms other established classifiers on our task. Measure efficiency/performance is evaluated in two different experiments. First, we will train a classifier in order to predict one of all six domains. By means of this classification task, we will investigate measure performance, in order to discriminate all domains between each other. Second, in another classification task, we want to find those measures with the best performance to describe one particular knowledge domain. This is done by employing the binary relevance method, which is a one-vs-rest version of the first classification task. It will evaluate measure performance for each individual domain by training one independent classifier per domain. The measures with the best performance will have the ability to characterize datasets within one particular category most effectively.

Please note that our main aim is to understand overall and class-wise feature (i.e., graph measure) importance, rather than finding the best model for predicting category labels of RDF graphs. However, we want to find meaningful results. Thus we are obliged to tune the classifier to some extend. We hyper-tune the parameters via grid-search and five-fold cross-validation.

Since the classes are not balanced (cf. Table 2), we experimented with over- and undersampling strategies. For oversampling, we used the SMOTE-algorithm, for undersampling, a random undersampler. The results are presented by employing the highest scored classifier from the parameter-tuning and sampling strategy.

5.1.1.Correlation coefficients

We first report on observations about correlation coefficients between measures. Figure 1 shows a correlation matrix of all measures with color-encoded values for the Spearman correlation coefficients. Values close to 1.0 indicate strong positive correlation, around 0 no correlation, and close to −1.0 strong negative correlation.

Fig. 2.

Meaningful measures according to different statistical feature selection scoring methods.

In the group of graph measures, the number of edges m and vertices n has an almost perfect correlation with (a) max_degree and (b) max_in_degree. In addition, the two measures have a strong positive mutual correlation. Due to this, other measures which employ these measures are in turn strongly correlated with each other. In particular, this can be observed for measures employing the in-degree. Descriptive statistics on the distribution of in-degrees, like var_in_degree, stddev_in_degree, and coefficient_var_in_degree, grow with the size and volume of the graphs. This does not apply for measures relating to the vertices out-degree: measures using the in-degree differ from measures using the out-degree. Most of the measures employing the out-degree do not correlate with almost any of the other measures, which makes them more descriptive. A negative correlation value implies that while values for a measure x increase, values for another measure y decrease. This is the case with measures employing the aspect of density (fill) of the graphs with increasing size n and volume m. The density of a graph also has a negative correlation to the distribution of vertex degrees, as we can see with variance, standard deviation, and coefficient of variation values. This means that the denser the graphs are (fill increases), the more homogeneous the vertex degrees of the graphs become (descriptive statistics over vertex degrees become smaller). Almost no dependencies are exhibited by mean_degree, reciprocity, diameter, centrality measures, and the powerlaw_exponents, which measures the type of distribution of vertex (in-)degrees.

In the group of RDF graph measures, there are less inter-relationships. As a group, measures employing predicate degrees, max_predicate_list_degree, together with max_partial_in_degree, max_direct_in_degree as well as the typed_subjects measure, have strong positive mutual correlations. All of the mentioned measures grow with the size n and volume m of the graphs. Some individual mutual strong positive correlations can be observed, for instance, between repeated_predicate_lists and mean_predicate_list_degree, mean_direct_in_degree and mean_in_degree and mean_partial_in_degree. As in the first group of graph measures, all “mean” in-degree measures have strong correlations among each other as well as to the mean_degree.

5.1.2.Measure selection

Figure 2 highlights the measures that were selected by the individual tests.

Overall, there is variance and no particular consensus of the statistical tests. However, there are some agreements. Looking at agreements in all tests, only 13 measures are providing information gain; only three were dismissed by all tests, i.e., two degree-centrality measures and ratio_of_typed_subjects. 16 measures have agreements in three tests (threshold was not met in one of the tests); 10 measures met the threshold in only one test. With 30 measures, the pair Chi2 and Variance Threshold has the highest number of agreements; Mutual Information and Variance Threshold agree on 27 measures. The least agreements can be found for the pair Mutual Information and MINE (18).

Fig. 3.

Descriptive statistics of measures sorted out by feature selection methods (top) and measures considered meaningful (bottom). ^∗Indicates that x-axis is log-scaled.

5.1.3.Summary of results

With particular regard to RDF graphs and the above analysis, we conclude with the following observations:

The next subsections report the results on the reduced set of meaningful measures obtained from the feature selection methods. In particular, M′ is defined as the set of measures where at least three of the tests have an agreement, i.e., |M′|=29.

5.2.1.Characteristics of values

Figure 3 shows, by example, the distribution of values for two groups of measures. The first group at the top row shows exemplary measures which were sorted out by the feature selection approaches in Section 5.1, such as the mean total-degree and the mean out-degree; the bottom row shows exemplary features of M′. The figure shows all available knowledge domains except Media, Social Networking, and the User Generated, due to few dataset retrieved in these categories (cf. Table 2).

Regarding the mean total-degree, some categories show very similar median values, like Cross Domain, Life Sciences, and Publications. Cross Domain, Geography, Life Sciences, and Linguistics share a similar maximum value. However, regarding the outliers, Life Sciences contains a dataset that has by far the highest average degree, followed by a dataset in the Government category. The mean out-degree (outgoing predicates of subjects) is higher for most of the categories (two outliers can be observed with very high values). The boxes reveal that the majority of values are larger than the mean total-degree, which means that the mean total-degree is mainly influenced by the in-degree. This is particularly striking for datasets in the Geography and Life Sciences domains.

Fig. 4.

Measure variance. The lighter the color the lower the variance and the more homogeneous the values are within the corresponding category.

The last two plots in the first group show the mean_direct_out_degree and mean_labelled_out_degree measures, which describe the relationship of subjects to their average number of different objects and predicates, respectively. Overall, the number of different objects is higher than the number of predicates. The distribution of values is similar for Cross Domain and Publications, as well as for Geography and Linguistics, particularly for the predicates (mean_labelled_out_degree). Comparing mean_degree and mean_out_degree as well as mean_direct_out_degree and mean_labelled_out_degree with each other, we can see that they show very similar characteristics. Generally, the distribution of values is not symmetric (different whisker lengths of the boxes) and skewed, thus they do not follow a normal distribution. Further, there is little variability (short length of boxes).

Fig. 5.

Degree of variance across knowledge domains. A low/high value indicates low/high variance across knowledge domains. Colors encode graph measures (in light) and RDF graph measures. y-axis is log-scaled.

Below in Fig. 3 are exemplary measures of M′, i.e., those that were considered to be non-redundant and meaningful according to the feature selection approaches in Section 5.1. There is much higher variability in most of the measures and knowledge domains. Also, the number of outliers is larger. Please note that the x-axis is log scaled for some measures, which makes it hard to make statements about the skewness of the distributions; thus, we would like to point out h_index_d. It gives us the number of at least x RDF objects with x incoming predicates.

Lowest spread and little variability can be found for h_index_d. The distribution of values in Cross Domain, Geography, Government is highly skewed to the right, which means that most of the values are rather low. However, there are some datasets with quite high value above 4000, e.g., in Cross Domain, Government, Life Sciences, and Publications. The largest value can be found for a dataset in the Government domain.

5.2.2.Variability of values

As a first overview, Fig. 4 shows measure variance of the datasets within the given categories as a heat-map: the lighter the color, the lower the variance and therefore the more homogeneous the corresponding values are for the corresponding category and measure.

Overall, datasets in the Life Sciences, Cross Domain, and Government (in this order) have quite heterogeneous distributions of values for a high number of measures. On the contrary, only one, two, or three measures have high variance in the Publications, Linguistics, and Geography domain (in this order). Some measures exhibit high variance in just one category and a low variance in the others. Just to name a few: max_out_degree and max_partial_out_degree in Life Sciences, pseudo_diameter and distinct_classes in Linguistics, max_labelled_in_degree and mean_predicate_list_degree in Government, max_predicate_list_degree in Cross Domain, max_direct_out_degree in Publications. These measures may be used to discriminate categories against each other very well, as their characteristical distribution of values for a particular category can be considered meaningful. In turn, some measures also exhibit a rather low variance in one or two domains and higher in the others. These are, for instance, m, h_index_d, std_in_degree in Linguistics.

Figure 5 shows the degree of variance across knowledge domains. The scores are obtained by grouping datasets by category, taking the mean of the corresponding measure for all datasets per category, and then computing the standard deviation over these means. Lowest variances across all categories can be found for mean_out_degree, mean_direct_in_degree, pseudo_diameter, both h_index measures, std_dev_in_degree, coefficient_variation_out_degree, distinct_classes, and mean_predicate_list_degree. Among the top five measures with large dispersion between categories (m, m_unique, parallel_edges, n, and max_predicate_degree) are four measures employing graph edges. The figure also includes minimum (lower stroke) and maximum (upper stroke) values. For some measures, the minimum value varies significantly from the standard deviation value. To name a few: pseudo_diameter, max_labelled_in_degree, max_predicate_list_degree, and distinct_classes.

5.2.3.Summary of results

Fig. 6.

Overall measure importance while discriminating datasets (classification task (1)). Shown are mean values for all non-redundant measures m∈M′. Colors encode graph measures (in light) and RDF graph measures.

Fig. 7.

Per-category measure importance while discriminating datasets (classification task (2)). Measures are encoded by color throughout all knowledge domains.

5.3.1.Overall measure importance

Figure 6 shows the results of classification task (1). The colors encode graph measures (in light) and RDF graph measures. The x-axis shows all measures m∈M′. The y-axis shows the mean importance score obtained from 300 estimators’ feature importance calculation, in descending order. It can be interpreted as a percentage value of the extent to which a particular feature contributes to decrease the weighted impurity in the decision tree.

While the ranking shows a steadily decreasing order, the overall scores are rather low. The first 13 measures can be considered to have some impact. From the 14th value on, there is hardly a change, and the impact score is low.

Among the top 10 measures of the highest score are three graph measures (pseudo_diameter, coefficient_variation_out_degree, and distinct_classes) and seven RDF graph measures. Overall, measures employing the out-degree are favored. mean_predicate_list_degree, describing the mean number of repeated predicate used to describe subjects, has the highest score; m, describing the number of edges, the lowest.

5.3.2.Per-category measure importance

Figure 7 shows the results of classification task (2), where one can get a picture on measure performance in each of the categories. It shows per knowledge domain the top seven measures with the highest scores obtained from binary relevance method (one-vs-rest) with Random Forest classifier. Like in Fig. 6, the y-axis shows the degree of contribution to decrease impurity in the decision tree.

At first glance, we can see that the set of measures considered most important varies much across knowledge domains and that individual scores are higher than in classification task (1). Overall, there are 13 distinct measures considered here (after measure selection, the initial set of measures in M′ was 29). Among these, six measures are employing the max, three measures employing the mean, and four measures employing an other absolute value. To complete this overall observation: out of the 13 distinct measures, six employ outgoing edges, i.e., RDF predicates of subjects; two employ incoming edges of objects.

max_labelled_out_degree, mean_direct_in_degree and mean_out_degree are present in five out of six knowledge domains, although each with different scores and ranking. distinct_classes and max_direct_out_degree are present in four domains. Collecting the top two and top three measures of each knowledge domain results in having 10 and 11 distinct measures, respectively. No measure is present in exclusively one category. Hence, there seems to be no measure with particular importance in a specific category. However, distinct_classes, coefficient_variation_out_degree, and pseudo_diameter, have highest scores in Cross Domain, Life Sciences, and Linguistics, respectively. mean_predicate_list_degree is even scored highest in three domains: Geography, Government, and Publications. By far, mean_predicate_list_degree, coefficient_variation_out_degree have the highest scores in Geography, Life Sciences, and Publications, respectively. These measures can be considered most important in the corresponding categories. Their values have distinctive characteristics, which enable classifiers to discriminate datasets according to these categories. Looking closer, the results of this binary relevance task here aligns well with the single performance analysis from above: the top 10 measures from Fig. 6 are the ones which are most likely to be found in the corresponding categories in Fig. 7.

To illustrate the classification performance, Table 5 shows the scores of the binary relevance method employing the Random Forest classifier, performed on different sampling strategies as mentioned in Section 4.2.3, using the final set of features M′ obtained from Section 5.1. The micro score is the classifiers overall accuracy. The macro score gives the mean score per class. The last metric, macro weighted, additionally gives each class a weight, by respecting the number of seen samples while testing.

5.3.3.Summary of results

6.1.1.General observations

By identifying effective graph features describing and discriminating RDF datasets and applying such features to LOD datasets, we gained an understanding of the topological differences of real-world datasets within distinct categories. The topology of RDF graphs (knowledge graphs more generally speaking) is distinct from other graph datasets, such as social graphs, due to the prevalence of hierarchical relations, that is, relations within the TBox (e.g. rdfs:subClassOf) or between ABox and TBox (e.g. rdf:type). This complements traversal relations and, by this means, imposes special characteristics that lead to generally higher connectivity, shorter paths, and the existence of vertex-“hubs” with high attractiveness from other vertices.

This is very well reflected in the graph measures. For example, measures like the number of edges, the maximum degree, and the maximum in-degree perfectly correlate with each other (cf. Section 5.1). Looking closer at the values for those measures reveals that 83% of the RDF graphs have vertices with a maximum in-degree being exactly equal to the maximum degree (in 94% of the cases, it is even almost equal). In most graphs, vertices representing the type (vertices with an “RDF type”-edge incident) are the ones with the highest in-degree. Such behavior of modeling, which is typical for RDF graphs and generally accepted as best practice in the RDF community, involves high connectivity of the graph’s topology. More references to the schema enhance this effect. In turn, more profound is the loss of connectivity as soon as the graph misses/loses references to the schema.

As more vertices and edges adhere to the graphs, the more heterogeneous and unstable the connectivity becomes. As a consequence, the overall density shrinks (cf. negative correlation of m, max_degree with fill) and the tendency of the topology to generate large sub-graphs having the shape of a “star” increase. Due to this and the aforementioned topological characteristic, measures employing the in-degree (some descriptive statistical measures, predicate (list-) degree measures, typed subjects, etc.) show a high correlation among each other. A stable value with growing size and volume of the graph would result in a homogeneous distribution, leading to a more stable and equally distributed connectivity of vertices among each other. The two mentioned examples can be considered being particularly RDF graph specific phenomena, which can be measured with the provided graph measures.

6.1.2.Observations within distinct categories

Vocabulary usage has a significant impact on the graph’s topology since schema and cardinality definitions are directly reflected in the graphs as options/restrictions to append vertices and edges. Thus, some measures are considered having a particular impact in individual categories, as shown in Fig. 7. Cross Domain, for instance, has a diverse and irregular vocabulary usage, which implies a large number of mixed and heterogeneous datasets, with (larger) co-occurrence of schema references and type-statements (distinct_classes). Geography and Publications report on a regular usage of vocabularies. The recurrence of a fixed set of predicates (mean_predicate_list_degree) is the main distinguishable feature of these categories. Geography additionally reports on a proportionally high ratio of parallel edges of its datasets. Inherently, datasets in Linguistics stand out with a significantly larger path length of traversal relations (pseudo_diameter7). The modeling strategy there seems fairly concise, resulting in a low average number of types and outgoing predicates/edges per subject, which is reflected by the measures mean_out_degree and max_partial_out_degree.

In general, measure importance per category has a dependency to the way how publishers, data extraction tools, and researchers describe data. For example, according to the naming pattern datasets in Linguistics are clustered into three groups: universal-dependencies-treebank-… (63 datasets), apertium-rdf-… (22 datasets), and other (37 datasets). Other examples of clusters can be found in Life Sciences (bio2rdf-…, 26 datasets) and Publications (rkb-explorer-…, 32 datasets) categories. This implies similarities of vocabulary usage, which in turn is reflected in recurrences of particular patterns in the topological structure. On account of this fact, the prevalent measure impact is also influenced by the habits of people and tools populating datasets in the individual categories.

Therefore, category-specific topological characteristics should be reflected in samples, benchmarks, or synthetic data.

6.2.1.Low variability

As mentioned earlier, datasets in the individual knowledge domains show similarities in their topological structure. Thus, the set of measures considered being efficient and meaningful varies across these categories (cf. Fig. 7). According to the classifier, each of the 13 measures provides some form of information gain and meaning.

A somewhat naive intuition is that a measure with low variability is characteristic in a particular category and therefore could be considered important. The experiments show that this is not necessarily the case. In the first experiment measures with low variability (e.g., mean_out_degree, mean_direct_in_degree and pseudo_diameter) were preferred during category prediction and evaluated with higher impact scores (cf. Fig. 5 and 6). The second experiment, focusing on individual categories, showed a different situation. Measures were considered characteristic and assessed with higher impact scores as their per-category variability (shown in Fig. 4) was high. For example, mean_predicate_list_degree shows a high impact score in Government due to higher variability within and across categories (cf. Fig. 4 and 5). Similar applies for other measures, like coefficient_variation_out_degree, max_partial_out_degree, and max_labelled_out_degree. Cross Domain, for instance, employs only measures of low variability (e.g., distinct_classes, max_direct_out_degree, etc.). Thus, in our classification tasks, the classifier tries to find the right balance between a low variability across categories and a somewhat characteristic variability as a topological feature.

6.2.2.Type of measures

Compared to other types of graphs, like social networks, RDF knowledge graph topologies adhere special characteristics, such as the pervasive reference to schema elements, with rdf:type statements being the most famous reference. This peculiarity influences the assessment about the meaningfulness of measures with regard to the discrimination of categories. For example, the classification task in Section 5.3 showed that RDF graph measures are preferred and obtained higher scores over other graph invariants, such as h-index (cf. Fig. 6). Out of the 10 best performing features in classification task (1), seven were RDF graph measures. Further, measures employing the in-degree are considered less effective, due to their heterogeneous (“unstable”) value distributions. Hence, measures considering subjects and their out-degrees are considered more meaningful. Measures like the number of (parallel/unique) edges, maximal (in-) degree, maximum predicate (in-/out-) degree, and the number of typed subjects, are inherently high in variability within and across knowledge domains. Their heterogeneous character lets them be ineffective and not appropriate for dataset/category discrimination.

6.3.1.Size of the sample

The analysis of measure efficiency involved 280 datasets out of 1,163 (end of 2017). While this number seems low regarding the theoretically available number of datasets, compared to other qualitative studies on datasets from the LOD Cloud, for instance [11,12,21], it sounds reasonable and of sufficient representativeness. Unfortunately, this is the current situation and, without additionally querying SPARQL-endpoints, the most that one can get from crawling the LOD Cloud.

6.3.2.Computational cost

Using our framework and infrastructure, we computed the described measures and study the graph topology of large state-of-the-art RDF knowledge graphs such as the English DBpedia with over 1.5B edges (cf. Table 2). However, memory consumption is a crucial bottleneck considering scale and growth of RDF graphs. Further, on graphs with a particularly large number of edges (>100M), building temporary lists of edge labels and the repetitive linear iterations over lists of vertices has significant negative impact on performance (cf. Table 4). For many measures, scalability of measure computation could be approached through a divide-and-conquer approach, by splitting the large graph into partitions and merging the individual results one after another. In this sense, we have a beta-ready implementation1313 for all measures with the exception of ratios, such as subject-object-ratio), we implemented from [15]. However, we did not test extensively whether the implementation is reliable, and thus for this paper all measures for large graphs were computed by loading the entire graph into memory.

6.3.3.Unbalanced domain classes

In order to tackle the class imbalance of our sample, we investigated class weighting and over- and undersampling techniques on the training sample passed to the classifier. Oversampling creates synthetic datasets (no duplicates) in each class up to the number of datasets of the largest class; undersampling down-sampled all classes to the size of the smallest class.

Feature importance methods are sensitive to the data structure and the distribution of feature values, and thus all methods showed different scores for the corresponding measures. What is interesting though, the set of measures considered important was similar to a great extent, in particular the most important measure per category (e.g., mean_out_degree, mean_predicate_list_degree, pseudo_diameter, and max_labelled_out_degree). Further, the model was trained following best practices for model tuning and cross-validation-based model selection. Hence, we assume that the obtained impact ratio of the classifier for each feature is reliable.

6.3.4.Limited set of features

If one actually wanted to perform category prediction [2,26] or measure the structural similarity between RDF datasets [27], we could ask if the graph measures presented in this paper are appropriate and sufficient. As discussed earlier, vocabulary usage and the way how publishers, data extraction tools, and researchers describe data, has an impact on the graph’s topology. Employing merely ontological information of the RDF dataset is, however, not sufficient to reach acceptable prediction accuracy [2]. Our classification experiment showed that, by employing topological measures, the prediction of categories for datasets is possible. Thus, knowledge domain-related, topological, and dataset features should complement one another. Aligning and integrating other tools and features for the extraction of metadata and vocabulary usage [5] would achieve improvements in prediction accuracy. Further, the integration of measures to somewhat distinguish hierarchical and traversal relations in the graphs, as this is a key characteristic for RDF data, would be beneficial.

6.3.5.Application and generalization of the findings to other (non-RDF and non-LOD) graphs

With our framework, all of the measures in M and M′ can be computed on graph-like datasets from other knowledge domains, outside of the LOD Cloud. Although metrics introduced by Fernández et al. [15] are considered to characterize RDF graphs in particular, of which in this paper only some could be implemented in the framework3 and included in the study about measure efficiency, on closer inspection, most of them could also be applied to non-RDF graphs. distinct_classes, typed_subjects, and ratio_of_typed_subjects form exceptions, as they require edges explicitly labeled with rdf:type. To analyze non-RDF graphs, an essential requirement is to have some form of consistent labeling (literal or numeric) of the edges during graph initialization.

However, in this work, we investigate RDF graphs only. RDF graphs are multigraphs, which may contain multiple edges between the same pair of source and target vertices, and whose use of (partly) very specialized vocabularies exposes special characteristics to the graph’s topology. Thus, the results are unlikely to be applicable to non-RDF graphs and categories outside the LOD Cloud. Moreover, although following best practice techniques for avoiding overfitting, value normalization and feature selection, classification models are very task-specific. Models are tuned towards (a) the sample of RDF datasets we obtained and analyzed from the LOD Cloud, and (b) the final set of features obtained from the feature engineering step. Thus, the generalizability of our findings to other kinds of graphs (non-RDF) is an important part of future work.