{"id":"41a41880-46ad-4a1b-97bb-ab1348a4e1ab","arxiv_id":"2504.20795","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper presents OptiUCF, an optimized algorithm that constructs a correct UCF-Index for (k,eta)-core queries on uncertain graphs by replacing division-based updates with on-demand dynamic programming recomputation.","lead":"A new algorithm called OptiUCF builds the UCF-Index for probabilistic (k,eta)-cores without the floating-point errors that make the previous construction wrong. It uses lazy recalculations and layered search to speed up a correct baseline by one to two orders of magnitude.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The correctness claim for OptiUCF depends on lower bounds staying valid after edge deletions, yet no proof or output-equivalence check establishes that the pruning preserves the exact peeling order.","rationale":"The reader's weakest-assumption analysis correctly identifies that the pruning rules in the lazy refreshing strategy must preserve the exact peeling order, and that the paper supplies no proof of this. My stress-test agrees with that broad concern and sharpens it: the specific risk is that lower bounds in Eq. (8) are defined on the current incident edge set of a vertex, but the paper does not show how these bounds are updated when an edge is deleted, nor that an old lower bound remains valid. If the deleted edge belonged to the top-K set, the old lower bound can overestimate the true k-probability, causing the Step 4 delay test to skip a required refresh and alter the peeling order. This is a concrete correctness risk, not merely a missing formal proof. At the same time, the paper is not internally inconsistent: if the implementation recomputes lower bounds whenever a neighbor is deleted, the pruning rules are plausible, and the baseline BC is genuinely correct because it refreshes by DP. The experiments also demonstrate large speedups and identify a real flaw in the prior EC algorithm. The missing piece is decisive empirical or formal evidence that OP and OP* produce exactly the same index as BC. Since the concern is not yet demonstrated as an actual error, CONDITIONAL remains the appropriate verdict, and the reader's recommendation should stand unchanged.","tokens_in":12429,"tokens_out":20513,"duration_ms":231416,"concrete_test":"Run the authors' implementation (or a re-implementation) with a checker that recomputes the full peeling order using the correct DP baseline BC and compares every eta-threshold produced by OP and OP* on all eight datasets, asserting exact equality. Additionally, run a targeted unit test: construct a small uncertain graph in which the first peeled vertex pcrt is the highest-probability neighbor of a vertex u with k=2 and u's other edges are low-probability, so that the old top-K lower bound for u becomes stale after pcrt is deleted; verify that OP* peels u before any vertex with probability above pcrt's probability and assigns the same threshold as BC.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that OptiUCF constructs a correct UCF-Index efficiently. The pruning decisions in Algorithm 3 (lines 20-24 and 12-13) and in the lazy refreshing strategy of Section 4.1 rest on lower bounds LB(u) for indefinite vertices: Step 4 delays a refresh when LB(u) >= k-prob(pnxt,G). These lower bounds come from Eq. (8), i.e., the top-K product bound and the beta-function bound, both computed from the current incident edge set of u. When a vertex pcrt is deleted and u is its neighbor, the deleted edge is no longer present, and if that edge was among u's top-k edges, the old LB(u) can exceed u's true k-probability in the remaining graph. For example, with k=2 and edges (u,pcrt)=0.9, (u,x)=0.1, (u,y)=0.1, the old top-2 product LB is 0.09, but after removing pcrt the true k-probability of u is only 0.01. If LB(u) is not recomputed after this deletion, the Step 4 test LB(u) >= k-prob(pnxt) can incorrectly conclude that u need not be refreshed, allowing a vertex with larger true k-probability to be peeled first. This raises curThres and assigns u an inflated eta-threshold, breaking correctness. The paper never specifies a lower-bound update procedure for removed edges and offers no correctness theorem for Algorithm 3; Theorem 2 only analyzes running time. The experiments in Section 5.2 quantify the errors of the old EC algorithm but never compare the eta-thresholds produced by OP or OP* with those produced by the correct baseline BC. Thus a genuine correctness bug in the pruning could go undetected despite the reported speedups.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the construction of the UCF-Index for (k,η)-cores on uncertain graphs. It observes that the existing index construction algorithm, which updates k-probabilities by recursive floating-point division, can produce incorrect thresholds. The paper proposes OptiUCF, which replaces division updates with exact DP refreshes, and accelerates this baseline with two techniques: (i) a lazy refreshing strategy using upper and lower bounds on k-probability, and (ii) a progressive refinement strategy that partitions vertices according to their η-thresholds from the previous k iteration. The authors claim that OptiUCF constructs a correct UCF-Index and runs one to two orders of magnitude faster than a DP-based baseline. Experiments on eight real-world graphs report running times, the error ratio of the old EC algorithm, and scalability results.","tokens_in":12699,"tokens_out":18465,"duration_ms":177334,"significance":"If the correctness claim were established, this would be a useful contribution: it would provide a way to build the UCF-Index without the floating-point division errors identified in prior work, and the proposed bound-based pruning is a natural and potentially effective optimization. The baseline algorithm (Algorithm 1) is sound in principle, and the upper/lower bound inequalities used for pruning are parameter-free and taken from known results. The empirical study is on substantial graphs and includes a demonstration that the previous EC algorithm has very high error rates. However, the central correctness claim is not supported by a proof, and the progressive refinement strategy appears to rely on a lower bound that is not valid for the dynamically shrinking graph. Because correctness is the paper's headline contribution, this issue is load-bearing.","major_comments":[{"comment":"The progressive refinement strategy uses η-thres_{k+1}(u) as a lower bound on the k-probability of u in the current subgraph G′. Corollary 1 only states k-prob(u,G) ≥ η-thres_{k+1}(u) for the original graph G. During the peeling phase for k, G′ is obtained by deleting vertices, and the k-probability of a vertex can only decrease when incident edges are removed. Thus η-thres_{k+1}(u) can exceed the true k-probability of u in G′. Concretely, if k=2 and u has three high-probability edges to vertices a,b,c whose own k-probabilities are small, then after a and b are peeled u may have degree below k and k-probability 0, while η-thres_3(u) is still high. The condition in Algorithm 3 line 14 (η_{i+1} < k-prob(pcrt,G′)) can then fail to add u's layer before a moderate-probability vertex c is peeled; c receives an inflated threshold and u is processed only after curThres has risen, yielding an incorrect index. The paper needs either a proof that η-thres_{k+1}(u) remains a valid lower bound on k-prob(u,G′) throughout the peeling, or a modification of the progressive refinement rule.","section":"Section 4.2 and Algorithm 3 (lines 14–16, 25–27)"},{"comment":"There is no correctness theorem for the pruning rules of OptiUCF. The paper asserts in Section 4.1 that Steps 2 and 4 avoid unnecessary refreshes, and Algorithm 2 (refKPROB) is described as returning the vertex with minimum k-probability, but no lemma or theorem states that these comparisons—using freshly computed or lazily maintained bounds—preserve the exact peeling order of the baseline. In particular, the manuscript does not specify how lower bounds stored in the heap D are updated when an incident edge is deleted, nor does it prove that the condition LB(u) ≥ k-prob(pnxt,G′) in Step 4 is sufficient to delay refreshing. Since the central claim is that OptiUCF constructs a correct UCF-Index, this missing invariant is a load-bearing gap that must be filled with a formal proof.","section":"Section 4.1 and Algorithms 2–3"},{"comment":"The accuracy experiments quantify the error of the old EC algorithm but never compare the η-thresholds produced by OP or OP* with those produced by the correct baseline BC. Given that no correctness proof is supplied, an empirical output-equivalence check is essential to support the claim that OP and OP* build a correct index. The authors should report, for each dataset and at least for a range of k, the fraction of vertices whose η-thres_k matches BC, or compare the resulting η-trees directly.","section":"Section 5.2"}],"minor_comments":[{"comment":"The statement of Theorem 2 contains unbalanced parentheses and an unexplained term k^2_max|E|; the proof sketch does not account for all terms, and the sentence 'In the worst-case scenario, we need to updated the k-probabilities of all vertices in D during each peeling' is not a complete derivation. Please restate the complexity bound and justify each term.","section":"Section 4.3, Theorem 2"},{"comment":"Definition 3 says the k-probability 'is the probability that Pr(deg(u,G)≥k)'; this should read 'is Pr(deg(u,G)≥k)' to avoid redundancy.","section":"Section 2.2, Definition 3"},{"comment":"The illustrative floating-point example in Figure 1 is helpful but the choice of ε=10^-3 is not connected to any actual machine precision; please clarify how the error bound from [8] is instantiated in this example.","section":"Section 1, Example 1 and Figure 1"},{"comment":"The running-time plots in Figure 5 would benefit from explicit axis labels and a note on whether the y-axis is logarithmic, since the claimed one-to-two-orders-of-magnitude improvement is otherwise hard to verify from the figure.","section":"Section 5.1"},{"comment":"There are several minor typographical issues: 'Problem Defnition 1' in Section 2.2, the inconsistent notation 'η-tree2' in Figure 2(b), and the phrase 'the probability that Pr(deg(u,G)≥k)' in Definition 3. A careful proofreading pass is recommended.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The most serious issue is the invalid use of η-thres_{k+1}(u) as a lower bound on the current subgraph in Section 4.2. If the authors cannot provide a correct invariant or a modified progressive refinement rule, the paper's central claim would fail. In that case, the manuscript should be rejected rather than accepted with minor changes. I would also ask the editor to ensure that the authors provide an output-equivalence comparison against the baseline before any revision is considered for acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nI've read the arXiv paper by Sun et al. on constructing the UCF-Index for (k,η)-cores without floating-point division errors. The problem is real: Yang et al.'s original construction uses recursive division and can be badly wrong on large graphs. Replacing that with a DP-based baseline is the obvious correct move, and the paper's optimization of that baseline is the actual contribution.\n\nWhat's good: the baseline BC is straightforward and correct. The lazy refreshing strategy is a reasonable combination of known bounds (Bonchi's beta-function bound and a top-K product bound) with on-demand DP recalculation. The progressive refinement using η-thresholds from the previous k is a neat way to reduce initialization cost. The experiments are extensive, four real graphs and four SNAP graphs, and the speedups over BC are consistently one to two orders of magnitude. That's a practical improvement.\n\nThe soft spot, as the reader's report notes, is the absence of a correctness proof for the pruning. Theorem 2 only analyzes running time. If the lazy strategy ever peeled a vertex out of order, the resulting η-thresholds would be inflated and the whole index would be wrong. The paper does not supply a proof, and it never verifies that OP/OP* produce the exact same thresholds as BC on any dataset. That's a real gap in evidence.\n\nHowever, I want to push back on the stress-test note's concrete counterexample. It claims that lower bounds can go stale after a neighbor's edge is deleted, allowing an inflated LB to delay a refresh. That would be a genuine bug, but it doesn't hold up. In Algorithm 3, line 19 removes pcrt, and then lines 20–24 process every neighbor of pcrt, recomputing bounds for each one. Any vertex whose incident edges changed is exactly a neighbor of the deleted vertex, so its stored LB is refreshed. A vertex in D that is not adjacent to the deleted vertex has an unchanged incident edge set, so its old LB remains valid. So the pruning looks sound on a careful reading. What's missing, then, is not a demonstrated error but a rigorous statement and proof that these invariants hold.\n\nWho this is for: researchers working on uncertain graph analysis, specifically core decomposition and index construction. A referee should ask for a correctness proof or at least an output-equivalence experiment. I'd take the paper, but with requiring that addition.\n\nBest,\n[You]","headline":"Plausibly fixes a real numerical bug in UCF-Index construction with a solid DP baseline and large speedups, but it still needs a correctness proof and an output-equivalence check; the stress-test's concrete counterexample does not survive close reading.","tokens_in":13280,"tokens_out":6252,"would_cite":true,"duration_ms":62875,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R10","05C85","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new algorithm builds the UCF-Index for $(k,\\eta)$-cores on uncertain graphs without the floating-point division errors that make the current index construction incorrect, and it runs one to two orders of magnitude faster than a correct…","keywords":["uncertain graphs","(k,eta)-core","UCF-Index","k-probability","core decomposition","floating-point error","lazy refreshing","progressive refinement"],"falsifier":"Run OptiUCF and an exact baseline that recomputes every affected $k$-probability by dynamic programming after every vertex deletion on all uncertain graphs with up to about a dozen vertices and edge probabilities drawn from $\\{0.1, 0.5, 0.9\\}$; any graph where the two algorithms produce different $\\eta$-thresholds for any vertex, or delete vertices in a different order, shows that the bound-based pruning does not preserve the exact decomposition.","tokens_in":12188,"feed_emoji":"⚙️","tokens_out":5673,"duration_ms":56824,"temperature":0.7,"pith_summary":"The paper claims that the state-of-the-art index for answering $(k,\\eta)$-core queries on uncertain graphs, the UCF-Index, is usually built incorrectly because its construction relies on recursive floating-point division to update $k$-probabilities during vertex peeling, and these errors worsen sharply as $k$ grows. To fix this, the paper proposes OptiUCF, which recomputes $k$-probabilities exactly by dynamic programming, but only for the vertices that truly need it, using tight bounds to skip or delay refreshes and a layer-by-layer search to find the minimum-probability vertex cheaply. If correct, this makes the UCF-Index both exact and practical: queries for any $k$ and $\\eta$ can be answered in optimal time, and construction is reported to be one to two orders of magnitude faster than a correct DP-based baseline on real-world graphs.","feed_headline":"Floating-point errors in (k,eta)-core index cured, 10-100x faster","feed_subtitle":"New construction recomputes k-probabilities only on demand, so the index is exact and still scales to millions of vertices.","key_machinery":"The mechanism is the combination of two bounds and an on-demand refresh loop. The $\\beta$-function based bound gives a constant-time interval $[\\mathrm{LB}(u),\\mathrm{UB}(u)]$ for each vertex's $k$-probability from its minimum and maximum incident edge probabilities, and the top-$K$ lower bound tightens $\\mathrm{LB}(u)$ using the product of the $k$ highest-probability edges of $u$ (Lemma 1). An additional lower bound comes from Corollary 1: for any vertex $u$, $k$-prob$(u,G) \\ge \\eta$-$\\mathrm{thres}_{k+1}(u)$, which supports the layer partition. Algorithm 2, refKPROB, uses these bounds to decide which indefinite vertices must have their exact $k$-probability recomputed by DP, while Algorithm 3, OptiUCF, manages the working set $V_w$ and adds layers progressively until the true minimum-probability vertex is found.","core_discovery":"The paper's central claim is that a correct UCF-Index for uncertain graphs can be constructed efficiently by replacing the error-prone recursive floating-point update of $k$-probabilities with exact dynamic-programming recomputation performed on demand. The proposed OptiUCF algorithm maintains upper and lower bounds on each vertex's $k$-probability and uses a lazy refreshing strategy: when a vertex is deleted, a neighbor is refreshed only if its upper bound exceeds the current threshold, and a neighbor whose lower bound is at least the current minimum $k$-probability is left un-refreshed. A further progressive refinement partitions vertices into layers using their $\\eta$-thresholds from the previous $k$, so the search for the minimum-probability vertex starts in the outermost layer and expands only when needed. The paper claims this yields a correct index for every $k$ and $\\eta$, with construction time one to two orders of magnitude faster than a baseline that recomputes every affected $k$-probability exactly.","pith_inferences":["The same bound-then-refresh-on-demand pattern could repair other uncertain-graph peeling indices that suffer from floating-point division drift, notably $(k,\\gamma)$-truss index construction, where the failure mechanism is analogous.","The pruning rules place a bet on the tightness of the bounds; a natural stress test is to instrument the algorithm and count how often a delayed vertex later turns out to have been the true minimum, which would tell whether the heuristic is robust on adversarial as well as real-world inputs.","The $\\eta$-threshold-based lower bound from Corollary 1 could make construction self-validating: if a vertex's stored threshold from layer $k+1$ ever exceeds its recomputed $k$-probability within the same layer, that would signal a violated bound before the index is used.","An alternative repair path, not explored in this paper, is to replace floating-point arithmetic with exact rational arithmetic or compensated summation in the update rule itself; if that were cheap enough, the need for bound-based pruning might disappear entirely."],"forward_implications":["Applications that rely on $(k,\\eta)$-cores, such as community search, fraud detection, and influence maximization, can now use a UCF-Index that is correct for all parameter combinations instead of one that degrades as $k$ grows.","The correct construction remains practical at scale: on the tested graphs the full algorithm was one to two orders of magnitude faster than a DP-based exact baseline and scaled smoothly to graphs with millions of vertices.","The error ratio of the previous construction approaches 100% on real graphs for large $k$, so avoiding floating-point division is a qualitative correctness requirement, not a minor numerical tweak.","Because the index supports online queries in time linear in the result size, the speedup in construction translates directly to more reliable and responsive interactive exploration of uncertain graphs.","The progressive refinement technique makes the index construction faster on larger graphs, as the gap between the optimized algorithm and the baseline widens with graph size."],"supporting_citations":[{"why":"Introduces the UCF-Index and its $\\eta$-tree structure, the index object this paper sets out to construct correctly, and supplies the $\\eta$-tree construction algorithm used in the pipeline.","marker":"[22]"},{"why":"Identifies the floating-point division error in recursive $k$-probability updates and proposes a DP-based recomputation as the correct alternative, which motivates the baseline and the correctness target.","marker":"[8]"},{"why":"Defines $(k,\\eta)$-cores, proves the beta-function based inequalities that give the paper's upper and lower bounds, and provides the possible-world DP formulation for $k$-probability.","marker":"[4]"},{"why":"Provides the beta-function table lookup that makes the beta-based bounds computable in constant time.","marker":"[15]"},{"why":"Supplies the linear-time $k$-core decomposition used to compute the initial core subgraph for each $k$ in the index construction.","marker":"[3]"},{"why":"Offers an accelerated dynamic programming algorithm for $\\eta$-degree computation, relevant to the exact refresh step that the lazy strategy invokes on demand.","marker":"[12]"}],"fun_headline_variants":["Exact (k,η)-core index construction kills floating-point errors","Correct (k,η)-core index 10–100x faster than flawed version","On-demand k-probabilities make (k,η)-core index exact","Lazy updates fix (k,η)-core index, cut time 100x","Exact (k,η)-core index scales to millions, no rounding errors"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm assumes that its bound-based pruning never changes which vertex actually has the smallest $k$-probability at each peeling step; specifically, a vertex can be safely skipped or delayed whenever its stored upper or lower bound says so, without a proof that this preserves the exact peeling order.","fun_headline_variants_meta":{"raw":{"variants":["Exact (k,η)-core index construction kills floating-point errors","Correct (k,η)-core index 10–100x faster than flawed version","On-demand k-probabilities make (k,η)-core index exact","Lazy updates fix (k,η)-core index, cut time 100x","Exact (k,η)-core index scales to millions, no rounding errors"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000657,"raw_usage":{"total_tokens":3014,"prompt_tokens":960,"completion_tokens":2054,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":576,"completion_tokens_details":{"reasoning_tokens":1949}},"tokens_in":576,"tokens_out":2054,"duration_ms":13657,"temperature":1.0,"reasoning_tokens":1949,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:19:53.149294+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run OptiUCF and an exact baseline that recomputes every affected $k$-probability by dynamic programming after every vertex deletion on all uncertain graphs with up to about a dozen vertices and edge probabilities drawn from $\\{0.1, 0.5, 0.9\\}$; any graph where the two algorithms produce different $\\eta$-thresholds for any vertex, or delete vertices in a different order, shows that the bound-based pruning does not preserve the exact decomposition.","supporting_citations":[{"cited_title":"Index-based optimal algo- rithm for computing k-cores in large uncertain graphs","cited_arxiv_id":null,"evidence_quote":"Introduces the UCF-Index and its $\\eta$-tree structure, the index object this paper sets out to construct correctly, and supplies the $\\eta$-tree construction algorithm used in the pipeline."},{"cited_title":"Core decomposition on un- certain graphs revisited","cited_arxiv_id":null,"evidence_quote":"Identifies the floating-point division error in recursive $k$-probability updates and proposes a DP-based recomputation as the correct alternative, which motivates the baseline and the correctness target."},{"cited_title":"Core decom- position of uncertain graphs","cited_arxiv_id":null,"evidence_quote":"Defines $(k,\\eta)$-cores, proves the beta-function based inequalities that give the paper's upper and lower bounds, and provides the possible-world DP formulation for $k$-probability."},{"cited_title":"Tables of the incomplete beta function, 1968","cited_arxiv_id":null,"evidence_quote":"Provides the beta-function table lookup that makes the beta-based bounds computable in constant time."},{"cited_title":"Improved algorithms for maximal clique search in uncertain networks","cited_arxiv_id":null,"evidence_quote":"Offers an accelerated dynamic programming algorithm for $\\eta$-degree computation, relevant to the exact refresh step that the lazy strategy invokes on demand."}],"review_version":1}