Knowledge graphs have now become common on the web, ranging from small taxonomies for categorizing web sites, to large knowledge bases that contain a vast amount of structured content. To enable their quick understanding and exploration semantic summaries have been proposed. A key issue of structural semantic summaries is the identification of the most important nodes. Works in the area, usually employ a single centrality measure, capturing a specific perspective on the notion of a node's importance. However, combining multiple centrality measures could give a more objective view, on which nodes should be selected as the most important ones. In this paper, we present SumMER, a novel framework that explores machine learning techniques for optimally combining multiple centrality measures for selecting the most important nodes. The experiments performed show the benefit of our approach, effectively increasing the quality of the generated summaries.
art, structural non-quotient summarization methods [
The problem. For generic graphs, multiple centrality measures have been proposed,
each one perceiving importance using different criteria. However, there is no centrality
measure to dominate them all, and each one is appropriate for different notions of
importance over different types of graphs. On the other hand, we have already shown that
several of these centralities interrelate [
Our solution. We argue that combining multiple such measures could give us an objective view on which nodes should be selected as the most important ones. To this direction, in this paper, we present SumMER, effectively exploiting machine-learning algorithms for optimally combining multiple importance measures for node selection. To the best of our knowledge, no other approach so far combines structural summarization techniques with machine learning for RDF/S KBs. More specifically, for generating a summary using SuMMeR, we follow the three steps, shown in Fig. 1. The first two steps are trying to identify the top-k most important schema nodes, whereas the last one focuses on linking the selected schema nodes, possibly introducing additional nodes to the schema summary.
Selecting top-k nodes. The first step in identifying the top-k nodes in GS is to
calculate for each node its importance in the graph. As already mentioned, multiple graph
centrality measures have been proposed in the literature, each one capturing a different
perspective on the node’s importance. In this work we do not try to identify an optimal
centrality measure, as we believe that they offer different perspectives on a node’s
importance and that ideally, they should be all considered for assessing a node’s
importance. To this direction we exploit a diverse set of centrality measures that we
calculate for each node (i.e. degree, bridging, harmonic, radiality, ego, betweenness,
PageRank and HITS), shown in Fig.1. Note that many of those measures correlate as we
have already shown [
To explore the combination of multiple centrality measures for identifying the top-k schema nodes, we model the problem as a regression problem, trying to rank all schema nodes for selecting the top-k ones. In this paper, we explore the following machine learning algorithms: Adaboost regressor, Gradient Boosting regressor, Extra Tree regressor, Random Forest regressor, Linear regression, Decision Tree regressor, Bayesian Ridge and ElasticNet. As such for each schema node we construct a vector with the selected centrality measures as features, trying to identify the top-k most important nodes.
Linking schema nodes. Independent of the way the most important nodes are
selected, the next step is to link those nodes formulating a connected schema subgraph.
Similarly, to [
Next, we present an overview of the datasets used and the methodology for our experimentally evaluating the constructed summaries.
Datasets. For evaluating our approach, we use DBpedia v3.8, DBpedia v3.9, and the Semantic Web Dog Food (SWDF). For those versions we also have available query logs containing 50K user queries for v3.8, 110K user queries for v3.9 and 2.5K user queries, for SWDF provided by LSQ (https://aksw.github.io/LSQ/) that we exploit for evaluation as we shall see in the sequel. Table 1 summarizes the characteristics of the three ontology versions we use for our evaluation.
DBPedia 3.8 DBPedia 3.9 SWDF
Competitors. As ML has not been previously used for generating structural
summaries we compare our approach with RDFDigest+, the latest approach for generating
structural summaries that has been shown to outperform past approaches [
Constructing a “golden standard”. In order to construct a “golden standard” for the most important nodes, and to evaluate the regression models, we exploit the query logs for the three available ontology versions, calculating the schema nodes that are more frequently queried. We assess as the most important, the ones that have a higher frequency of appearance in the queries.
Metrics. For evaluating the performance of our machine learning algorithms, we used Mean Absolute Error (MAE) as commonly used for evaluating regression problems. However, note that as we are only looking for the top-k nodes, we evaluate those metrics on the aforementioned k nodes only. In addition, we calculate for each summary its coverage, i.e. we calculate for each query the percentage of the classes and properties that are included in the summary. Having the percentages of the classes and properties included in the summary, the query coverage is the weighted sum of these percentages. As our summaries are node based we give 0.8 weight to the percentage of the classes and 0.2 weight to the percentage of the properties.
Experiments. For the evaluation of the node selection of the various algorithms, we attempt to predict the top 10%, 15%, 20%, 25%, 30% of nodes to be included in the summary. For all the experiments, we use the DBpedia v3.9 as the training dataset and the DBpedia v3.8 and SWDF as the test datasets. We perform a feature selection step where we select the non-correlated centrality measures (betweenness, radiality, page rank, hits and instances), we train the selected models on DBpedia v3.9 and then we evaluate the train versus test set. We use 10-fold cross validation for the training dataset.
The results are shown in Fig. 2, and as presented, the Decision Tree regressor performs best in almost all cases, whereas most of the algorithms show a relatively good performance. Looking at the confusion matrices (not presented here due to lack of space) we can identify that the Decision Tree regressor is able to predict best the true positives in all summary sizes, outperforming among others the RDFDigest+ in all cases. The good performance on selecting the top-k nodes is also depicted in the subsequent calculation of the coverage for both DBpedia 3.8 and SWDF. As shown in Fig. 2 (right) SumMER is always better than RDFDigest+. 3
Overall, the results show that our approach is able to generate better summaries, that
are able to answer more query fragments than previous works. This is true, not only in
subsequent versions of the same ontology (DBpedia), but also in completely different
ontologies (SWDF), showing that our approach is able to generalize into semantic
graphs with different structure. Overall, Decision Trees Regression has been identified
as the best performing algorithm with stability over the different KBs used. For future
work, we intend to exploit machine-learning methods learning to rank [
This research project was supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the “2nd Call for H.F.R.I. Research Projects to support PostDoctoral Researchers” (iQARuS Project No 1147).