Technical Summary: COREKG – Coreset-Guided Personalized Summarization of Knowledge Graphs

1. Problem Statement

Knowledge Graphs (KGs) such as Freebase, DBpedia, and Wikidata have become central to applications like search engines, recommendation systems, and question answering (QA). However, their massive scale and high connectivity pose significant challenges for efficient querying, visualization, and reasoning. While general KG summarization methods exist to reduce data size, they often focus on capturing global structural patterns, resulting in summaries that are overly generalized and fail to address the specific information needs of individual users.

Existing personalized approaches, such as GLIMPSE and iSummary, attempt to tailor summaries to user interests but face limitations: GLIMPSE assumes dense query histories and lacks explicit control over summary sparsity, while iSummary relies heavily on aggregate workload coverage. Other methods like PEGASUS and APEX2 utilize heuristics or heat diffusion models that may lack formal approximation guarantees or struggle with sparse and skewed query logs. There is a need for a framework that provides personalized KG summarization with theoretical guarantees, computational efficiency, and robustness across diverse user query patterns without relying on dense historical data.

2. Methodology

The authors propose COREKG, a framework that adapts coreset theory to the domain of Knowledge Graphs. A coreset is a small, weighted subset of data that approximates a cost function with provable error bounds. COREKG constructs a personalized coreset for each user by sampling relevant triples based on sensitivity-based importance sampling.

2.1 Framework Overview

The COREKG pipeline operates independently for each user and consists of the following stages:

1. Preprocessing & User Modeling:

   • Seed Extraction: Each user is modeled by a set of "seed entities" (nodes of direct interest) extracted from their query history.
   • Query Filtering: The global query log is filtered to retain only queries mentioning at least one of the user's seed entities, creating a user-specific query workload.
   • Normalization: SPARQL queries are normalized (removing duplicates, expanding prefixes) to ensure semantic consistency.

2. Sensitivity Score Computation:

   • For a given user $u$ and their workload $Q$, the sensitivity $s(t)$ of a triple $t$ is calculated. This score quantifies the triple's importance to the user's specific queries.
   • Formally, $s(t) = \sum_{q \in Q} \frac{1}{|T_q|} \cdot \mathbb{I}[t \in T_q]$, where $T_q$ is the set of triples relevant to query $q$, and $\mathbb{I}$ is an indicator function.
   • Triples appearing frequently in a user's queries or in queries with small answer sets receive higher sensitivity scores. This ensures the sampling distribution is tailored to individual user behavior rather than global statistics.

3. Coreset Construction (Sampling & Weighting):

   • Triples are sampled from the original graph $G$ according to the probability distribution $p(t) = \frac{s(t)}{S}$, where $S$ is the total sensitivity.
   • Each sampled triple $t$ is assigned a weight $w(t) = \frac{1}{m \cdot p(t)} = \frac{S}{m \cdot s(t)}$, where $m$ is the sample size. This weighting corrects for sampling bias, ensuring the expected cost on the coreset matches the cost on the full graph.
   • The result is a weighted subgraph (the coreset) that approximates the full graph's utility for the user's specific workload.

2.2 Theoretical Guarantees

The paper provides a formal theorem (Theorem 4.1) establishing that the constructed coreset $C$ approximates the true cost of the full graph $G$ within a bounded relative error $\epsilon$ with high probability ($1-\delta$). The required sample size $m$ depends on the number of queries $|Q|$ and the desired error bounds, but is independent of the size of the full graph $|T|$.

3. Key Contributions

The paper outlines four primary contributions:

• COREKG Framework: A coreset-guided approach for personalized KG summarization that adapts coreset theory to graph data, offering provable approximation guarantees and practical scalability.
• Sensitivity-Based Sampling: A formulation that quantifies triple relevance based on user-specific query workloads, ensuring robustness across diverse personalization scenarios.
• Theoretical Bounds: A worst-case approximation guarantee on user-specific workload costs that is independent of the full graph size, with all query evaluations performed directly on the coreset.
• Empirical Validation: Extensive experiments demonstrating that COREKG outperforms state-of-the-art baselines (GLIMPSE, PPR, iSummary, PEGASUS, APEX2) in both query coverage and F1 score across Freebase, DBpedia, and Wikidata.

4. Experimental Results

The authors evaluated COREKG on three real-world datasets (Freebase, DBpedia, Wikidata) using SPARQL query workloads. The evaluation focused on Structural Coverage (preservation of query patterns) and F1 Score (query-answering accuracy).

• Performance: COREKG consistently achieved higher F1 scores and coverage than all baselines. For instance, on DBpedia, COREKG achieved an F1 score of 58.64% and coverage of 68.07%, significantly outperforming APEX2 (47.52% F1, 42.06% coverage) and iSummary (19.38% F1, 12.55% coverage).
• Budget Sensitivity: Across varying summary budgets (from 1,000 to 100,000 triples), COREKG maintained superior performance. While other methods like PEGASUS showed high coverage but extremely low F1 scores (indicating poor relevance), COREKG balanced both metrics effectively.
• Ablation Study:
  • Uniform Sampling (COREKG-Uniform): Replacing sensitivity sampling with uniform random sampling resulted in near-zero performance, confirming the necessity of query-based sensitivity.
  • Global Workload (COREKG-Global): Removing user-specific conditioning and using a global workload significantly degraded performance, validating the need for personalization.
  • Unweighted Sampling (COREKG-Unweighted): Assigning equal weights to samples led to substantial performance degradation, highlighting the importance of bias correction via weighting.

5. Significance and Claims

The paper claims that COREKG addresses the critical gap in existing summarization methods by shifting from global or aggregate user modeling to explicit per-user personalization grounded in theoretical guarantees.

• Efficiency: By maintaining only relevant information based on user query patterns, COREKG significantly reduces storage requirements and query runtime.
• Robustness: Unlike methods relying on heat diffusion or dense query histories, COREKG handles sparse and skewed workloads effectively through its sensitivity-based sampling.
• Theoretical Soundness: The method provides a "provable approximation guarantee," ensuring that the summary preserves the query-answering semantics of the full graph up to a small, bounded relative error.

The authors conclude that COREKG is a strong approach for personalized KG summarization, offering a viable alternative for handling large-scale KGs in data-driven applications where user-specific relevance and computational efficiency are paramount. The work explicitly notes limitations regarding the representativeness of sparse workloads and the lack of per-query (rather than aggregate) guarantees, identifying these as directions for future research.