The rapid growth in both size and complexity of Knowledge Graphs (KGs), available on the web, has created a pressing demand for efective and eficient techniques to comprehend and explore them. Recently, semantic summaries have emerged as a promising solution to quickly grasp the contents of such KGs. However, these summaries often sufer from limitations, being static and lacking customization to accommodate user selections. Additionally, they struggle to handle the sheer scale of the Knowledge Graphs. In this demonstration, we present iSummary, a novel and scalable system able to construct personalized summaries. The main idea behind our approach is to exploit knowledge captured in existing user queries for identifying the most interesting resources and linking them, constructing as such highquality, personalized summaries. Our algorithm provides theoretical guarantees on the summary's quality, with a computational complexity linearly dependent on the number of queries in the query log.
CEUR ceur-ws.org
CEUR Workshop Proceedings user preferences but still rely on the KG to compute the summary which makes it computationally hard. Further, capturing a complete individual user query set is usually not feasible.
The iSummary solution. In this demonstration we present iSummary, which exploits generic logs already available through the SPARQL endpoints of the various KGs available online instead of relying on node weights or on individually provided sets of user queries. In order to generate a personalized summary iSummary only requires the selection of one or a few nodes that the user is mostly interested in. As previous users have already identified through their queries, the most common connections to the specific user-selected nodes, we exploit this information in order to formulate the generated summaries. In our demonstration, we explain how we can resolve the problem relying on existing query logs and we provide a solution to both the multiple weight assignment required and also to the computationally hard problem. The main paper of this work has already been presented at ESWC 2023 [7], whereas the system is available online1. To the best of our knowledge, it is the first approach to construct personalized, structural, non-quotient semantic summaries exploiting generic query workloads.
We depict the high-level architecture of the iSummary system in Figure 1 (right). The system comprises three main components. The GUI enables setting the configuration parameters (the size of the summary, selection of the nodes, and the dataset), visualizes the results, and presents the triples in the result summary. The service layer includes the query parser that processes the query logs, the node extractor in order to select the nodes to be included in the summary, and the path extractor & linker which connects the selected nodes. Finally, the data layer includes the various query logs per dataset.
Next, we present the problem of computing / -Personalized Summaries and we show that,
although they are useful, their computation is both impractical and computationally hard.
Definition 2.1 ( / -Personalized Summary). Given (
Note that we don’t actually require a weight to be assigned to all nodes, as the weight of all nodes can be by default zero, and the user only adds weights to a subset of them. Also, a solution to the / -Personalized Summary problem is not unique, as there might be many maximum-weight trees with the smallest size that are equally useful for the user. A nice property of the / -Personalized Summaries is that their quality is monotonically increasing as the increases. This means that as the summary size increases more relevant information is added to the summary for the same seed nodes selected by the user.
Lemma 2.1. Let be a / -Personalized Summary and +1 be a /(+1) -Personalized Summary for . Then ( +1 ) ≥ ( ), where () the sum of all node weights in .
Computing the / -Personalized Summary is both impractical, as diferent weights should be assigned to the graph nodes for each distinct user query, and computationally expensive, as it is equivalent to the Steiner-Tree problem which is NP-complete. Next, we present how iSummary provides an elegant approximate solution based on query workloads assuming that =1, i.e. to the -Personalized Summary problem, which can be easily generalizable for >1 as well. Resolving the problem of multiple weight assignments. Assume now that for the KG we have available a query log = { 1, ⋯ , } available. This assumption is reasonable, as all big KGs ofer a SPARQL endpoint that logs user queries for various purposes. Having such a query log available, we can use it to mine user preferences for the specific seed node that the user is interested in. The idea here is that if a user is interested in a -Personalized Summary for a node then we can use to identify relevant queries to , i.e., queries that include . In those queries, other nodes relevant to the user input will be available. In fact, as those queries have been issued by thousands of users, we assume that the most useful related nodes will be the ones that appear more frequently there.
Based on this assumption we can have multiple weight assignments, one per user input, as they occur from thousands of user queries that involve the provided user input and that are based on past users’ preferences, as expressed in their queries. Note here that we don’t need weights for the whole graph, as by default we can set the weight of the nodes that do not appear in the filtered user queries to zero.
Resolving the computational problem. Now that we have a way to assign personalized weights to the nodes, we next provide a computationally eficient procedure in order to link the selected nodes over a big graph. We start with a solution including a single node, the selected by the user, adding one node each time of the ones with the maximum weight till all remaining − 1 nodes are included in the summary. However, for doing so we will not use the original data graph but again relevant user queries. The main idea here is the following: link with the − 1 maximum weight nodes using the most frequent shortest paths from the user queries. The following theorem can be proved.
Theorem 2.2. The iSummary algorithm finds an approximate solution to the -Personalized Summary problem with a worst-case bound of 2, i.e., / ≤ 2 × (1 − /) , where and denote the total weight of a feasible solution and an optimal solution respectively, and l a constant, and scales linearly to the number of queries in the workload.
Example. Consider as an example, the KG shown in Figure 2, on the university domain.
Assume that for our example KG, we have available a query log consisting of the following SPARQL queries: Q1. SELECT ?x WHERE {x? a Person. y? a Professor. ?x advisor ?y.} Q2. SELECT ?x WHERE {x? a Person. y? a Organization. ?y affiliatedOf ?x.} Q3. SELECT ?x WHERE {x? a Person. y? a Organization. ?y affilatedOf ?x.
?y orgName "FORTH".} Now assume that a user is interested in a 2-Personalized Summary for the node . Based on the query log we can identify that relevant queries to user input are 1 , 2 , and 3 . Examining those queries we can identify that the useful nodes are the and . In fact, as is used in two queries it should be most useful according to the available query log. As we are looking for a 2-Personalized Summary it will be included in the result. Now instead of searching the graph shown in Figure 2 for linking with we will additionally iflter the queries including and , i.e. Q2 and Q3. For each one of those queries, we calculate the shortest path for linking and and we eventually select the most frequent shortest path to include in the summary. As such the 2-Personalized Summary for the node includes a single triple (, , ) .
To demonstrate the functionalities of iSummary, we will use DBpedia and Wikidata along with their corresponding query logs (58K queries for DBpedia and 192K queries for WikiData). The demonstration will proceed in six phases:
1. Introduction. In the first step we will explain the problem of computing a / Personalized Summary motivating its usefulness. Further, we will explain why it is computationally hard and also inconvenient by requiring users to provide multiple weights. Then we will explain the main ideas behind our approximate solution, exploiting query logs for efectively tackling both hardness of the problem and also multiple weights assignment.
2. Configuration. Then we will start the summarization process by selecting the KG to be summarized along with the corresponding query logs. In the configuration menu, the user can select the node for which she requires a summary and also the number of nodes to be included in the summary (i.e. the ).
3. Summary Graph. In this phase the result summary will be presented visually. Here we will explain how our algorithm mines the queries in order to identify the nodes that most frequently co-occur with the user input and then how again the queries are exploited to link the selected nodes by picking the smallest most frequent path that appears in the query log. The triples included in the summary will also be shown.
4. Summary for diferent sizes. We will explain the properties of a good summary explaining that it is better when it is able to maximize the fragments of queries that include user-selected nodes (i.e. to maximize the query coverage). Then we will demonstrate how coverage monotonically increases as the size of the summary increases as well.
5. Mini-Game. In this phase we will let conference participants ”play” with the system. We will play a mini-game asking them to return a summary for a few nodes and contrasting them with the result from iSummary.
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 Post-Doctoral Researchers” (iQARuS Project No 1147) and by the SafePolymed (GA 101057639) EU project.