Pith. sign in

REVIEW 1 major objections 1 minor 35 references

Sensitivity-based importance sampling produces personalized knowledge graph summaries that approximate full datasets with bounded error for user queries.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-30 20:29 UTC pith:SW6K65YS

load-bearing objection The paper adapts sensitivity sampling from coresets to build per-user KG summaries and claims better accuracy than baselines, but the abstract leaves the error bound and sensitivity definition unshown. the 1 major comments →

arxiv 2605.14900 v1 pith:SW6K65YS submitted 2026-05-14 cs.AI

COREKG: Coreset-Guided Personalized Summarization of Knowledge Graphs

Sohel Aman Khan , Raghava Mutharaju , Supratim Shit This is my paper
classification cs.AI
keywords knowledge graph summarizationcoreset constructionpersonalized summarizationsensitivity samplingquery workloadapproximation error
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper adapts coreset theory to create small, user-specific summaries of large knowledge graphs. For any dataset and a given user's query workload, it samples triples according to sensitivity scores that capture each triple's importance to that workload. The resulting subset is guaranteed to approximate the full graph's characteristics up to a bounded error. A reader would care because the summaries require far less storage and deliver faster queries while preserving accuracy tailored to individual users.

Core claim

For a given dataset and a user-specific query workload, the approach samples a relevant subset of triples using sensitivity-based importance sampling. The subset approximates the characteristics of the full dataset with bounded approximation error. Sensitivity scores are defined to measure the importance of each triple with respect to the user's query workload, and these scores drive the coreset construction algorithm. Summaries are constructed independently for each user based on their query behaviour.

What carries the argument

Sensitivity-based importance sampling that constructs a coreset for a user query workload by weighting triples according to their contribution to answering queries in the workload.

Load-bearing premise

Sensitivity scores defined with respect to a user's query workload can be used to construct a coreset whose approximation error remains bounded for that workload.

What would settle it

Measure the actual query-answering error on the sampled subset for the target workload and check whether it exceeds the error bound predicted by the sensitivity sampling procedure.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The sampled subset preserves query-answering accuracy with bounded error for the given workload.
  • Structural coverage of the original graph is retained in the summary.
  • Storage size and query runtime drop substantially compared with the full graph.
  • The method yields higher query accuracy and coverage than GLIMPSE, PPR, iSummary, PEGASUS and APEX² on Freebase, WikiData and DBpedia.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same sampling procedure could be applied to streaming or frequently updated graphs by recomputing sensitivities only on changed triples.
  • Summaries built for similar users might be merged to reduce redundant storage while still respecting individual workloads.
  • The bounded-error guarantee could be tested by evaluating performance on queries drawn from a distribution close to but distinct from the original workload.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 1 minor

Summary. The manuscript presents COREKG, which adapts coreset theory to personalized KG summarization. For a dataset and user-specific query workload, it constructs per-user summaries by sampling triples via sensitivity-based importance sampling, claiming the resulting subset approximates the full KG with bounded approximation error. Summaries are built independently per user from sensitivity scores measuring triple importance w.r.t. the workload. Evaluation on Freebase, WikiData, and DBpedia reports higher query-answering accuracy and structural coverage than GLIMPSE, PPR, iSummary, PEGASUS, and APEX² while using only a tiny fraction of the original graph.

Significance. If the bounded-error guarantee can be established and the empirical gains are reproducible under detailed protocols, the work would supply a principled, workload-aware method for reducing KG size while preserving query utility. This could benefit storage-constrained and latency-sensitive KG applications such as question answering and visualization.

major comments (1)
  1. [Abstract] Abstract: the central claim that the sampled subset 'approximates the characteristics of the full dataset with bounded approximation error' is asserted without any derivation, explicit sensitivity definition, algorithm, or error bound; this is load-bearing for the contribution and cannot be assessed from the given text.
minor comments (1)
  1. The abstract contains the LaTeX fragment 'APEX$^2$' which should be corrected to APEX² for readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive feedback. The single major comment highlights a valid issue with the abstract's presentation of the core theoretical claim. We address it directly below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the sampled subset 'approximates the characteristics of the full dataset with bounded approximation error' is asserted without any derivation, explicit sensitivity definition, algorithm, or error bound; this is load-bearing for the contribution and cannot be assessed from the given text.

    Authors: We agree the abstract is too terse on this point. The full manuscript (Sections 3–4) defines sensitivity scores as the maximum influence of each triple on query answers under the workload, presents the importance-sampling algorithm, and derives the (1+ε) approximation bound via standard coreset analysis. To make the contribution assessable from the abstract, we will revise it to include a one-sentence reference to the sensitivity definition and the fact that the error bound follows from coreset theory (with a pointer to the relevant sections). revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper adapts standard coreset construction via sensitivity-based sampling to KG summarization. Sensitivity scores are defined with respect to a user query workload and then fed into a coreset algorithm that guarantees bounded approximation error; this is a direct, non-circular application of existing coreset theory rather than a self-referential definition or a fitted parameter renamed as a prediction. No self-citation chains, uniqueness theorems, or ansatzes imported from prior author work appear in the provided text, and the central claim (workload-specific coresets with bounded error) remains independent of its own outputs. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the central claim rests on the domain assumption that coreset sampling extends to KG triples via sensitivity scores; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption Coreset theory can be adapted to sample triples from knowledge graphs using sensitivity scores derived from user query workloads to achieve bounded approximation error.
    This assumption is invoked to justify the sampling procedure and error bound.

pith-pipeline@v0.9.1-grok · 5802 in / 1195 out tokens · 39539 ms · 2026-06-30T20:29:34.969763+00:00 · methodology

0 comments
read the original abstract

Knowledge Graphs (KGs) are extensively used across different domains and in several applications. Often, these KGs are very large in size. Such KGs become unwieldy for tasks such as question answering and visualization. Summarization of KGs offers a viable alternative in such cases. Furthermore, personalized KG summarization is crucial in the current data-driven world as it captures the specific requirements of users based on their query patterns. Since it only maintains relevant information, the personalized summaries of KG are small, resulting in significantly smaller storage requirements and query runtime. In this work, we adapt the coreset theory to create personalized KG summaries. For a given dataset and a user-specific query workload, we present an approach that samples a relevant subset of triples using sensitivity-based importance sampling. We ensure that the subset approximates the characteristics of the full dataset with bounded approximation error. We define sensitivity scores that measure the importance of a triple with respect to a user's query workload, which are then used by our coreset construction algorithm. We explicitly focus on personalized knowledge graph summarization by constructing summaries independently for each user based on their query behaviour. Our evaluation on Freebase, WikiData, and DBpedia shows that COREKG delivers higher query-answering accuracy and structural coverage than the state-of-the-art methods, such as GLIMPSE, PPR, iSummary, PEGASUS and APEX$^2$ while requiring only a tiny fraction of the original graph.

Figures

Figures reproduced from arXiv: 2605.14900 by Raghava Mutharaju, Sohel Aman Khan, Supratim Shit.

Figure 1
Figure 1. Figure 1: COREKG Framework triple in C matches its true contribution in G, thereby remov￾ing sampling bias. Intuitively, triples that are sampled with lower probability receive higher weights, since they repre￾sent a larger portion of the original graph, whereas frequently sampled triples receive smaller weights. The coreset satisfies [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · 1 internal anchor

  1. [1]

    Practical Coreset Constructions for Machine Learning

    [Bachemet al., 2017 ] Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning. arXiv preprint arXiv:1703.06476,

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  2. [2]

    Scalable k-means clustering via lightweight core- sets

    [Bachemet al., 2018 ] Olivier Bachem, Mario Lucic, and Andreas Krause. Scalable k-means clustering via lightweight core- sets. InProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1119–1127,

    work page 2018

  3. [3]

    Freebase: a collabora- tively created graph database for structuring human knowledge

    [Bollackeret al., 2008 ] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: a collabora- tively created graph database for structuring human knowledge. InProceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 1247–1250,

    work page 2008

  4. [4]

    Near-optimal coresets for least-squares regression.IEEE transactions on information theory, 59(10):6880–6892,

    [Boutsidiset al., 2013 ] Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail. Near-optimal coresets for least-squares regression.IEEE transactions on information theory, 59(10):6880–6892,

    work page 2013

  5. [5]

    Efficient coreset constructions via sensitivity sampling

    [Bravermanet al., 2021 ] Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. Efficient coreset constructions via sensitivity sampling. InAsian Conference on Machine Learning, pages 948–963. PMLR,

    work page 2021

  6. [6]

    Query-oriented summarization of rdf graphs

    [ ˇCebiri´cet al., 2015 ] ˇSejla ˇCebiri´c, Franc ¸ois Goasdou´e, and Ioana Manolescu. Query-oriented summarization of rdf graphs. InBritish International Conference on Databases, pages 87–91. Springer,

    work page 2015

  7. [7]

    Relin: relatedness and informativeness-based centrality for entity summarization

    [Chenget al., 2011 ] Gong Cheng, Thanh Tran, and Yuzhong Qu. Relin: relatedness and informativeness-based centrality for entity summarization. InInternational semantic web conference, pages 114–129. Springer,

    work page 2011

  8. [8]

    Sampling algorithms and coresets for lp regression.SIAM Journal on Computing, 38(5):2060–2078,

    [Dasguptaet al., 2009 ] Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W Mahoney. Sampling algorithms and coresets for lp regression.SIAM Journal on Computing, 38(5):2060–2078,

    work page 2009

  9. [9]

    A unified framework for approximating and clustering data

    [Feldman and Langberg, 2011] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. InProceedings of the forty-third annual ACM symposium on Theory of computing, pages 569–578,

    work page 2011

  10. [10]

    Turning big data into tiny data: Constant-size coresets fork-means, pca and projective clustering

    [Feldmanet al., 2013 ] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets fork-means, pca and projective clustering. InProceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1434–1453. SIAM,

    work page 2013

  11. [11]

    Coresets for vector summarization with applications to network graphs

    [Feldmanet al., 2017 ] Dan Feldman, Sedat Ozer, and Daniela Rus. Coresets for vector summarization with applications to network graphs. InInternational Conference on Machine Learning, pages 1117–1125. PMLR,

    work page 2017

  12. [12]

    Incremental structural summarization of rdf graphs

    [Goasdou´eet al., 2019 ] Franc ¸ois Goasdou´e, Pawel Guzewicz, and Ioana Manolescu. Incremental structural summarization of rdf graphs. InEDBT 2019-22nd International Conference on Extending Database Technology,

    work page 2019

  13. [13]

    Faces: diversity-aware entity sum- marization using incremental hierarchical conceptual clustering

    [Gunaratnaet al., 2015 ] Kalpa Gunaratna, Krishnaparasad Thirunarayan, and Amit Sheth. Faces: diversity-aware entity sum- marization using incremental hierarchical conceptual clustering. InProceedings of the AAAI Conference on Artificial Intel- ligence,

    work page 2015

  14. [14]

    An analytical comparison of approaches to personalizing pagerank

    [Haveliwalaet al., 2003 ] Taher Haveliwala, Sepandar Kamvar, and Glen Jeh. An analytical comparison of approaches to personalizing pagerank. Technical report, Stanford,

    work page 2003

  15. [15]

    Secure logistic regression for vertical federated learning.IEEE Internet Computing,

    [Heet al., 2021 ] Daojing He, Runmeng Du, Shanshan Zhu, Min Zhang, Kaitai Liang, and Sammy Chan. Secure logistic regression for vertical federated learning.IEEE Internet Computing,

    work page 2021

  16. [16]

    Coresets for vertical federated learning: Reg- ularized linear regression andk-means clustering.Advances in Neural Information Processing Systems, 35:29566–29581,

    [Huanget al., 2022 ] Lingxiao Huang, Zhize Li, Jialin Sun, and Haoyu Zhao. Coresets for vertical federated learning: Reg- ularized linear regression andk-means clustering.Advances in Neural Information Processing Systems, 35:29566–29581,

    work page 2022

  17. [17]

    Lauren-knowledge graph summarization for question answering

    [Jalotaet al., 2021 ] Rricha Jalota, Daniel V ollmers, Diego Moussallem, and Axel-Cyrille Ngonga Ngomo. Lauren-knowledge graph summarization for question answering. In2021 IEEE 15th International Conference on Semantic Computing (ICSC), pages 221–226. IEEE,

    work page 2021

  18. [18]

    Personalized graph summarization: formulation, scalable algorithms, and applications

    [Kanget al., 2022 ] Shinhwan Kang, Kyuhan Lee, and Kijung Shin. Personalized graph summarization: formulation, scalable algorithms, and applications. In2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 2319–2332. IEEE,

    work page 2022

  19. [19]

    The power of summarization in graph mining and learning: smaller data, faster methods, more interpretability.Proceedings of the VLDB Endowment, 14(13):3416–3416,

    [Koutra, 2021] Danai Koutra. The power of summarization in graph mining and learning: smaller data, faster methods, more interpretability.Proceedings of the VLDB Endowment, 14(13):3416–3416,

    work page 2021

  20. [20]

    Utility-driven graph summarization.Pro- ceedings of the VLDB Endowment, 12(4):335–347,

    [Kumar and Efstathopoulos, 2018] K Ashwin Kumar and Petros Efstathopoulos. Utility-driven graph summarization.Pro- ceedings of the VLDB Endowment, 12(4):335–347,

    work page 2018

  21. [21]

    Apex2: Adaptive and extreme summarization for person- alized knowledge graphs

    [Liet al., 2025 ] Zihao Li, Dongqi Fu, Mengting Ai, and Jingrui He. Apex2: Adaptive and extreme summarization for person- alized knowledge graphs. InProceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V . 1, pages 741–752,

    work page 2025

  22. [22]

    Simple weak coresets for non-decomposable classification measures

    [Malaviyaet al., 2024 ] Jayesh Malaviya, Anirban Dasgupta, and Rachit Chhaya. Simple weak coresets for non-decomposable classification measures. InProceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 14289–14296,

    work page 2024

  23. [23]

    European Language Resources Association (ELRA),

    [Mendeset al., 2012 ] Pablo N Mendes, Max Jakob, and Christian Bizer.DBpedia: A multilingual cross-domain knowledge base. European Language Resources Association (ELRA),

    work page 2012

  24. [24]

    Graph-based abstractive summarization of ex- tracted essential knowledge for low-resource scenarios.FRONTIERS IN ARTIFICIAL INTELLIGENCE AND APPLICA- TIONS, 372:1747–1754,

    [Moroet al., 2023 ] Gianluca Moro, Luca Ragazzi, Lorenzo Valgimigli, et al. Graph-based abstractive summarization of ex- tracted essential knowledge for low-resource scenarios.FRONTIERS IN ARTIFICIAL INTELLIGENCE AND APPLICA- TIONS, 372:1747–1754,

    work page 2023

  25. [25]

    Efficient semantic summary graphs for querying large knowledge graphs.International Journal of Information Management Data Insights, 2(1):100082,

    [Niazmandet al., 2022 ] Emetis Niazmand, Gezim Sejdiu, Damien Graux, and Maria-Esther Vidal. Efficient semantic summary graphs for querying large knowledge graphs.International Journal of Information Management Data Insights, 2(1):100082,

    work page 2022

  26. [26]

    Knowledge graphs: Opportunities and challenges.Artificial Intelligence Review, 56(11):13071–13102,

    [Penget al., 2023 ] Ciyuan Peng, Feng Xia, Mehdi Naseriparsa, and Francesco Osborne. Knowledge graphs: Opportunities and challenges.Artificial Intelligence Review, 56(11):13071–13102,

    work page 2023

  27. [27]

    Personalized knowledge graph summarization: From the cloud to your pocket

    [Safaviet al., 2019 ] Tara Safavi, Caleb Belth, Lukas Faber, Davide Mottin, Emmanuel M¨uller, and Danai Koutra. Personalized knowledge graph summarization: From the cloud to your pocket. In2019 IEEE International Conference on Data Mining (ICDM), pages 528–537. IEEE,

    work page 2019

  28. [28]

    Graphsum: Scalable graph summarization for efficient question answering

    [Shabaniet al., 2024 ] Nasrin Shabani, Amin Beheshti, Jia Wu, Maryam Khanian Najafabadi, Jin Foo, and Alireza Jolfaei. Graphsum: Scalable graph summarization for efficient question answering. In27th International Conference on Extending Database Technology, EDBT 2024, pages 794–797. OpenProceedings. org,

    work page 2024

  29. [29]

    Online coresets for parameteric and non-parametric bregman clustering.Transactions on Machine Learning Research,

    [Shitet al., 2022 ] Supratim Shit, Anirban Dasgupta, Rachit Chhaya, and Jayesh Choudhari. Online coresets for parameteric and non-parametric bregman clustering.Transactions on Machine Learning Research,

    work page 2022

  30. [30]

    Improved coresets for verti- cal federated learning: Regularized linear and logistic regressions

    [Shitet al., 2025 ] Supratim Shit, Gurmehak Kaur Chadha, Surendra Kumar, and Bapi Chatterjee. Improved coresets for verti- cal federated learning: Regularized linear and logistic regressions. InInternational Conference on Machine Learning, pages 55303–55324. PMLR,

    work page 2025

  31. [31]

    Mining summaries for knowledge graph search.IEEE Transactions on Knowledge and Data Engineering, 30(10):1887–1900,

    [Songet al., 2018 ] Qi Song, Yinghui Wu, Peng Lin, Luna Xin Dong, and Hui Sun. Mining summaries for knowledge graph search.IEEE Transactions on Knowledge and Data Engineering, 30(10):1887–1900,

    work page 2018

  32. [32]

    Lsq 2.0: A linked dataset of sparql query logs.Semantic Web, 15(1):167–189,

    [Stadleret al., 2024 ] Claus Stadler, Muhammad Saleem, Qaiser Mehmood, Carlos Buil-Aranda, Michel Dumontier, Aidan Hogan, and Axel-Cyrille Ngonga Ngomo. Lsq 2.0: A linked dataset of sparql query logs.Semantic Web, 15(1):167–189,

    work page 2024

  33. [33]

    [Vassiliou, 2023] G. et al. Vassiliou. isummary: Workload-based, personalized summaries for knowledge graphs. InESWC,

    work page 2023

  34. [34]

    A survey on extractive knowledge graph summarization: applica- tions, approaches, evaluation, and future directions

    [Wang and Cheng, 2024] Xiaxia Wang and Gong Cheng. A survey on extractive knowledge graph summarization: applica- tions, approaches, evaluation, and future directions. InProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, pages 8290–8298,

    work page 2024

  35. [35]

    The value of seman- tic parse labeling for knowledge base question answering

    [Yihet al., 2016 ] Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming-Wei Chang, and Jina Suh. The value of seman- tic parse labeling for knowledge base question answering. InProceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 201–206, 2016

    work page 2016