{"id":"5b77b8c0-5e42-47d6-93c3-1e346ab6a611","arxiv_id":"2412.17336","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"APEX2 maintains an extremely small personalized knowledge graph by decaying old interest scores, diffusing new query heat, and incrementally re-sorting triples, outperforming static summarizers in simulated evolving-query experiments.","lead":"This paper presents APEX2, an algorithm that keeps a small personalized summary of a large knowledge graph up to date as a user's interests change, using a heat-like score that fades old interests. The authors test it on graphs up to 12 million triples with summaries as small as 0.0001% of the original, reporting better query-answering accuracy and speed than existing summarizers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"APEX2-N as implemented can exceed the storage budget K: it selects top-K entities and keeps all triples among them, so its reported F1 may be achieved with a larger-than-allowed PKG.","rationale":"The single most load-bearing weakness is not the unquantified expectation approximation in Theorems 4.1/4.3, although that is real, nor the asymmetric re-summarization interval, although that also weakens the comparison. Those issues can be repaired by adding assumptions or by equalizing update frequency. The budget violation in Algorithm 5 is a direct contradiction between the algorithm as written and the optimization problem it claims to solve (Eq. 2, |P(t)| <= K). The paper's best empirical performer is APEX2-N, and if its summaries are larger than K, the reported F1 values do not demonstrate 'extreme summarization' at the claimed compression ratio. This is checkable by instrumenting the released code; it is not a matter of subjective modeling choices. I therefore keep the verdict CONDITIONAL: before the SOTA claim can be accepted for APEX2-N, the authors must verify that |T_p| <= K holds at every evaluated timestamp, and if it does not, re-run the comparison with a strict triple-level budget. If the capped APEX2-N still matches or beats the baselines, the concern is fully resolved.","tokens_in":34086,"tokens_out":14039,"duration_ms":141970,"concrete_test":"Run the released code (github.com/iDEA-iSAIL-Lab-UIUC/APEX) on MetaQA and Freebase with the exact K values from Section 5.2. After every timestamp, print |T_p| for APEX2-N; if |T_p| > K at any evaluation point, the budget is violated. Then modify APEX2-N to enforce the triple budget strictly (e.g., greedily add triples by heat, or trim the induced subgraph to the top-K triples) and re-measure F1 against GLIMPSE and PageRank under the same update schedule. If capped APEX2-N no longer outperforms the baselines, the central claim collapses; if it still outperforms, the concern is resolved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Algorithm 5 in Appendix A.5 defines APEX2-N. In the initializing phase it chooses the top-K entities by heat to form E_p (line 6), then sets T_p to all triples whose endpoints are in E_p (line 7). In the updating phase, the while loop (lines 13-17) adds one entity at a time and again sets T_p to the induced triple set, with no final trimming. The paper's problem definition (Eq. 2) bounds the number of triples by K, and the compression ratios in Section 5.2 are stated as triple-count ratios (e.g., 0.01% of MetaQA's 231,103 triples is about 23 triples). But an induced subgraph on K entities can contain far more than K triples; adding a single high-degree entity can jump |T_p| from below K to well above K. Consequently APEX2-N's summary can violate the storage constraint. Since APEX2-N is the variant that 'outperforms all methods' in Figure 2, the headline claim of state-of-the-art effectiveness at extreme compression is not established for the reported results unless the code enforces a cap that the algorithm description omits.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes APEX2 and a variant APEX2-N for adaptive, extremely compressed personalized knowledge graph (PKG) summarization under evolving user interests. The method maintains a heat-based interest model with decay, incrementally updates entity/relation/triple preferences, and uses incremental sorting to select top-heat triples under a storage budget. The authors provide theoretical claims on adaptation speed and incremental time complexity, and report experiments on YAGO, DBPedia, MetaQA, and Freebase showing that APEX2 and APEX2-N outperform GLIMPSE, PEGASUS, iSummary, and personalized PageRank in next-query F1 at compression ratios below 0.1%.","tokens_in":34359,"tokens_out":6631,"duration_ms":59413,"significance":"If the claimed results hold, the paper would make an important step toward practical on-device PKGs: it targets the regime of extreme compression (≤0.1%) and continuous interest shift, which prior work (e.g., GLIMPSE, PEGASUS) was not designed for. The paper ships code and provides a clean problem formulation with a heat-decay mechanism that is intuitive and likely extensible. The theoretical results, though conditional on several assumptions, offer a starting point for reasoning about adaptation speed. The main empirical claim hinges on the correctness of the experiments, and two load-bearing issues currently prevent acceptance: APEX2-N may violate the stated storage budget, and the baselines are evaluated at a disadvantageous update frequency. The central idea is promising, but the current evidence is not sufficient to substantiate the headline claims.","major_comments":[{"comment":"APEX2-N does not enforce the size budget K on triples. The algorithm selects top-K entities in line 6 and then in lines 7 and 15 constructs T_p as all triples induced by those entities, with no final trimming. Because an induced subgraph on K entities can contain substantially more than K triples, the resulting PKG can violate the constraint |P| ≤ K from the problem definition in Eq. (2). The compression ratios reported in Section 5.2 are triple-based (e.g., 0.01% of MetaQA’s 231,103 triples corresponds to about 23 triples), so APEX2-N’s summaries may be much larger than the claimed budget. The F1 results for APEX2-N in Figure 2 and Table 3 are therefore not valid evidence for effectiveness at the stated compression ratios unless the code enforces a triple-level cap that is missing from Algorithm 5. Please revise the algorithm to guarantee |T_p| ≤ K (for example, by keeping only the top-K triples from the induced set) and rerun the experiments.","section":"§5.2, Algorithm 5 (Appendix A.5), Eq. (2)"},{"comment":"The main experimental comparison is not at equal update opportunity. APEX2 and APEX2-N update the summary every timestamp (R_APEX = 1), while the baselines GLIMPSE, PEGASUS, iSummary, and PageRank re-summarize only every R = 9 timestamps, as described in Section 5.1.3. Thus APEX receives nine times more update chances than the baselines. The additional experiments in Section 5.6 show that APEX2-N’s F1 drops from 0.858 to 0.680 when R_APEX increases from 1 to 6 on MetaQA, which suggests that a significant part of the advantage may be due to the asymmetric update schedule. To support the claim that APEX2 and APEX2-N outperform baselines, please report results at matched update frequencies (e.g., R_APEX = 9 for APEX methods or R = 1 for baselines, if computationally feasible).","section":"§5.1.3 and §5.3"},{"comment":"The query-count adaptation bounds in Theorems 4.1 and 4.3 rely on assumptions that are not stated in the theorem and are not validated empirically. The proofs in Appendices E.6 and E.7 replace products of entity/relation preferences by products of their expectations and assume the topics U and V have similar sizes, i.e., |E_u| ≈ |E_v| and |R_u| ≈ |R_v|, in order to obtain the closed-form bound b > log_gamma(...). Without these assumptions, the derivation does not produce the stated bound. Please state these assumptions explicitly in the theorems and either validate them on the benchmark KGs or discuss the sensitivity of the bound when they are violated.","section":"§4.1, Theorem 4.1 (proof in Appendix E.6) and Theorem 4.3 (proof in Appendix E.7)"}],"minor_comments":[{"comment":"The appendix proof labels do not match the main-text theorem numbers: E.2 proves the APEX2 time complexity (Theorem 4.2) but is titled Theorem 4.3; E.3 proves APEX2-N time complexity (Theorem 4.4) but is titled Theorem 4.5; E.6 proves APEX2 effectiveness (Theorem 4.1) but is titled Theorem 4.2; E.7 proves APEX2-N effectiveness (Theorem 4.3) but is titled Theorem 4.4. Please renumber for consistency.","section":"Appendix E: theorem numbering"},{"comment":"The condition in line 7, \"v in e\", is unclear and appears to contain a typo; it should presumably refer to entities being endpoints in E_p^(0) (or to the relation k). Please correct.","section":"Algorithm 5, line 7"},{"comment":"Equation (5) writes Pr(e|Q) with an unweighted indicator 1(e_o in q), whereas the vector q_total in Eq. (3) weights answer entities by 1/|A_i|. If Eq. (6) is the actual computation, please clarify that Eq. (5) is an informal illustration and point to Eq. (3)–(4) for the exact weighting.","section":"Eq. (5) and Eq. (6)"},{"comment":"The PageRank row for YAGO reports a mean of 22.81 with standard deviation 259.7, which is implausibly large relative to the mean; please check whether this is a typo or an artifact of a small number of outlier runs.","section":"Table 3"},{"comment":"The notation \"APEX-N2\" in Table 3 is inconsistent with the rest of the paper, which uses \"APEX2-N\"; please unify.","section":"Section 5.2 and Table 3"}],"recommendation":"major_revision","confidential_remarks":"The most serious issue is the APEX2-N budget violation: if the code does not cap the number of triples, the reported F1 for the best-performing variant is at a larger storage budget than stated, which would invalidate the extreme-compression claim. Even if the cap is enforced in the released code, the algorithm description must be corrected and the paper should state how the cap is implemented. The update-frequency asymmetry is also important; the authors should present at least one matched-frequency comparison (e.g., R_APEX = 9) to establish that the improvement is not an artifact of more frequent updates. The theoretical adaptation bound can be made rigorous by stating the size-similarity and expectation assumptions directly in the theorems, and by showing whether they hold on the benchmark datasets."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zihao Li and coauthors have written a paper worth a real referee, but it needs major surgery before it can be trusted as a published record. The core contribution—adaptive personalized KG summarization under extreme compression—is genuinely new, and they back it with shipped code and large-scale experiments on YAGO, DBpedia, MetaQA, and Freebase at compression ratios around 0.01% and below. The heat-decay model, incremental binary insertion sort, and the decay ablation are all reasonable engineering. The optimality proof for the incremental sort (Theorem 3.1) is clean.\n\nThe problems start with the definition of the problem. Equation 2 imposes a budget K on the number of triples, and the experiments report triple-count compression ratios. But Algorithm 5, APEX2-N, selects the top-K entities by heat and keeps all triples induced on those entities. The induced subgraph on K entities can contain far more than K triples—a clique would give ~K^2/2. The while loop in lines 13–17 adds an entity until T_p exceeds K, then exits, so the output can be arbitrarily over budget. Figure 2 shows APEX2-N as the best method, so the headline 'state-of-the-art at extreme compression' is not established unless the code enforces a cap that the pseudocode omits. The authors need to fix the algorithm (e.g., cap by triples, not entities) and re-run.\n\nSecond, the empirical comparison is not apples-to-apples. Baselines re-summarize every 9 timestamps (R=9), while APEX2 updates every timestamp (R_APEX=1). The paper justifies R=9 with a pre-experiment, but this still gives APEX2 more adaptation chances. The case study that gives baselines per-timestamp re-summarization is a good partial mitigation, but the main figure remains unfair.\n\nThird, the 'robust theoretical guarantees' are not rigorous. The effectiveness theorems (4.1, 4.3) replace products of preferences with products of expectations and assume similar-size topic areas. That turns the bound into a heuristic. The proof sketch in Appendix E shows the approximation steps explicitly. In the current form, the theory should be labeled as an analysis of the model, not a guarantee.\n\nMinor but annoying: the appendix theorem numbers don't match the main text. E.1 is labeled 'Theorem 4.1' but proves the sorting optimality (Theorem 3.1); E.4/E.5 prove GLIMPSE/PEGASUS non-adaptability but are labeled Theorem 3.1/3.2; E.6/E.7 are labeled 4.2/4.4 but prove the effectiveness results. This needs fixing.\n\nWho should read this? Researchers working on on-device KG summarization, evolving user interests, or incremental top-K maintenance. The paper deserves peer review, but I'd ask for a corrected algorithm for APEX2-N, an enforced-budget re-run, a same-update-frequency comparison (or a stronger justification), and a rewritten theory section that says what's heuristic and what's exact.","headline":"A genuinely new adaptive PKG summarization framework with shipped code, but the best variant can exceed its own triple budget and the main comparison gives it an unfair update-frequency advantage.","tokens_in":34856,"tokens_out":6619,"would_cite":true,"duration_ms":55477,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Personalized knowledge graphs can be summarized to 0.1% of their original size and still track a user's shifting interests, because APEX2 models interest as decaying heat and updates only the local neighborhood touched by each new query.","keywords":["adaptive summarization","personalized knowledge graph","knowledge graph summarization","heat diffusion","incremental sorting","extreme compression","evolving user interests","query answering"],"falsifier":"Run the adaptation experiment with two topics deliberately chosen to have very different average connectivity or very different sizes (e.g., a dense hub topic and a sparse peripheral topic) and record the number of queries until the summary's F1 on the new topic surpasses that on the old topic. If that measured count systematically falls outside the bound given by Theorem 4.1, or if replacing the synthetic query logs with a real anonymized SPARQL log changes the F1 ranking of APEX2 versus the baselines, the central claim would be weakened.","tokens_in":33897,"feed_emoji":"🔥","tokens_out":5794,"duration_ms":47668,"temperature":0.7,"pith_summary":"The paper claims that personalized knowledge graphs can be kept extremely small—down to 0.1% or less of the full graph—while still answering a user's next query accurately, even as the user's interests drift from one topic to another. It proposes APEX2, a framework that models user interest as heat on the knowledge graph, lets that heat decay and diffuse after each query, and incrementally updates a ranked summary so re-summarization does not require scanning the whole graph. The reported experiments on graphs with up to 12 million triples show APEX2 and its entity-focused variant APEX2-N beating the existing baselines on next-query F1 while running tens of times faster than the strongest baseline. If the claims hold, storing a personalized copy of a knowledge graph on a device becomes practical for very large graphs and for users whose interests change during the day.","feed_headline":"One framework keeps personalized knowledge graphs useful at 0.1% size","feed_subtitle":"Heat-based tracking lets tiny summaries follow shifting interests, beating static baselines on next-query accuracy.","key_machinery":"The load-bearing object is the sparse heat tensor $\\boldsymbol{H}$, defined entrywise as $\\boldsymbol{H}^{(T)}[i][j][k] = \\boldsymbol{e}^{(T)}[i]\\,\\boldsymbol{r}^{(T)}[j]\\,\\boldsymbol{e}^{(T)}[k]$, where $\\boldsymbol{e}$ is the diffused entity-interest vector and $\\boldsymbol{r}$ is the relation-frequency vector. The framework applies a decay-inject-diffuse cycle: at each timestamp all nonzero entries are multiplied by $\\gamma^3$, new query heat is injected, and only entries whose entities or relation changed are recalculated. A second mechanism, incremental binary insertion sort, reuses the previous sorted order and inserts the few changed entries in $O(k \\log n)$ comparisons, which Theorem 3.1 proves optimal. Together these make the per-timestamp update cost $O(c \\cdot |\\mathcal{Q}|^2 \\log(c|\\mathcal{Q}|))$, with $c$ the average number of neighbors within $d$ hops, independent of the number of entities in the full KG; an elimination threshold can reduce this to $O(c \\log c)$.","core_discovery":"APEX2 is presented as the first adaptive personalized knowledge-graph summarization framework that keeps the summary useful under extreme compression (budgets at or below 0.1% of the full graph). The core mechanism is a heat-based model of user interest: each query injects heat at the queried entity and its neighbors, heat decays by a factor $\\gamma$ each timestamp, and the summary is simply the $K$ triples with highest heat. Because decay only scales all scores and new queries affect only a small neighborhood, the ordering of triples can be maintained by incremental binary insertion sort, making the per-query update cost depend on the local connectivity of the queried area rather than on the size of the whole knowledge graph. The paper also proves an adaptation bound: after a user switches from topic $U$ to topic $V$, APEX2 needs at most about $\\log_\\gamma \\frac{1}{\\frac{A}{B}(1-\\gamma^a)}+1$ queries to re-adapt, where $A$ and $B$ are derived from the average connectivity of the two topics.","pith_inferences":["If the heat model is right, the same decay-inject-diffuse mechanism could be applied to other evolving personalization tasks, such as adaptive retrieval-augmented generation contexts or personalized recommendation, where the 'graph' is a user-specific interaction graph rather than a knowledge graph.","The paper leaves the entity-relation weight trade-off unresolved; a natural testable extension is to learn the weight per user or per query type from the query log instead of fixing it to 0 or 1.","The synthetic query logs are constructed as blocks of 10 same-topic queries; real interest shifts are likely more gradual and interleaved, so a stress test with probabilistic topic mixtures would show whether the adaptation bound degrades gracefully.","Because the update cost is independent of KG size once a threshold zeroes out decayed heat, the framework could in principle scale to graphs far beyond the 12-million-triple benchmarks tested, provided the local connectivity $c$ stays bounded."],"forward_implications":["Personalized knowledge graphs can be stored at compression ratios below 0.1% (as small as one triple per million) while still answering next queries with competitive F1, making on-device PKGs feasible for graphs with hundreds of millions of facts.","Users' shifting interests can be tracked without re-summarizing the whole graph: each new query triggers a local heat update and an incremental re-sort, so the cost per adapting phase is independent of the KG's total size.","APEX2-N, which ignores relations and tracks only entity heat, achieves higher next-query F1 than the full APEX2 in the experiments, suggesting that for short-horizon interest tracking entities matter more than relations.","The decay factor $\\gamma$ directly controls the trade-off between adapting to new interests and retaining useful old facts; setting $\\gamma$ near 1 (no forgetting) causes F1 to collapse under extreme compression.","Baseline methods that re-summarize periodically every 9 timestamps are dominated in both accuracy and speed, so existing static PKG summarizers are not a viable fallback for evolving interest."],"supporting_citations":[{"why":"Provides GLIMPSE, the sampling-based baseline whose triple-preference objective $\\Pr(e_i)\\Pr(r_k)\\Pr(e_j)$ APEX2 adopts, and whose non-adaptability is shown in Theorem B.1.","marker":"[55]"},{"why":"Provides PEGASUS, the merging-based personalized graph summarization baseline that APEX2 proves cannot evolve quickly after the size budget is reached (Theorem B.2).","marker":"[27]"},{"why":"Provides iSummary, the workload-based KG summarization baseline that collapses to simple caching under extreme compression.","marker":"[61]"},{"why":"Provides the closed-form $(\\boldsymbol{I} - \\alpha \\boldsymbol{A})^{-1}\\boldsymbol{q}$ used for the heat-diffusion interest vector and the personalized PageRank baseline.","marker":"[34]"},{"why":"Introduced the adaptive personalized KG summarization problem that this paper formalizes and extends to extreme size constraints.","marker":"[12]"},{"why":"Supplies the empirical observation that most real KG queries are simple 1-hop queries, justifying the query model and synthetic query design.","marker":"[6]"},{"why":"Supplies the heat diffusion mechanism used to propagate and decay user interest across entities.","marker":"[9]"}],"fun_headline_variants":["APEX2: adaptive summaries that follow shifting interests at 0.1% size","Heat-tracking keeps knowledge graph summaries useful at 0.1% size","Adaptive knowledge graph summaries for shifting interests, even at 0.1% size","APEX2: tiny summaries that track interests and adapt at 0.1% size","Knowledge graph summaries that evolve with your interests, even at 0.1% size"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The adaptation bound assumes the two topics have similar size and a well-defined average connectivity, and that products of user preferences can be replaced by products of their expectations; these approximations are not validated on the benchmark graphs, and the experiments further assume that synthetic topic-block query logs mimic real user behavior.","fun_headline_variants_meta":{"raw":{"variants":["APEX2: adaptive summaries that follow shifting interests at 0.1% size","Heat-tracking keeps knowledge graph summaries useful at 0.1% size","Adaptive knowledge graph summaries for shifting interests, even at 0.1% size","APEX2: tiny summaries that track interests and adapt at 0.1% size","Knowledge graph summaries that evolve with your interests, even at 0.1% size"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000721,"raw_usage":{"total_tokens":3290,"prompt_tokens":1053,"completion_tokens":2237,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":669,"completion_tokens_details":{"reasoning_tokens":2127}},"tokens_in":669,"tokens_out":2237,"duration_ms":16084,"temperature":1.0,"reasoning_tokens":2127,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:35:05.483080+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the adaptation experiment with two topics deliberately chosen to have very different average connectivity or very different sizes (e.g., a dense hub topic and a sparse peripheral topic) and record the number of queries until the summary's F1 on the new topic surpasses that on the old topic. If that measured count systematically falls outside the bound given by Theorem 4.1, or if replacing the synthetic query logs with a real anonymized SPARQL log changes the F1 ranking of APEX2 versus the baselines, the central claim would be weakened.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides GLIMPSE, the sampling-based baseline whose triple-preference objective $\\Pr(e_i)\\Pr(r_k)\\Pr(e_j)$ APEX2 adopts, and whose non-adaptability is shown in Theorem B.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides PEGASUS, the merging-based personalized graph summarization baseline that APEX2 proves cannot evolve quickly after the size budget is reached (Theorem B.2)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides iSummary, the workload-based KG summarization baseline that collapses to simple caching under extreme compression."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the closed-form $(\\boldsymbol{I} - \\alpha \\boldsymbol{A})^{-1}\\boldsymbol{q}$ used for the heat-diffusion interest vector and the personalized PageRank baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced the adaptive personalized KG summarization problem that this paper formalizes and extends to extreme size constraints."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the heat diffusion mechanism used to propagate and decay user interest across entities."}],"review_version":1}