{"id":"46ca9697-1855-403f-969c-07cabad0d644","arxiv_id":"2607.27640","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"The Dynamic Exploration Graph extends the authors' earlier Exploration Graph with a deletion mechanism and a fixed-parameter expansion rule, and reports faster build times and better recall-speed trade-offs than HNSW, DiskANN, and SWINN on three standard datasets.","lead":"This paper introduces the Dynamic Exploration Graph, a graph index for approximate nearest neighbor search that supports both adding and deleting data points while keeping the graph connected and fast. It is relevant because multimedia search and recommendation systems often work with continuously changing datasets, where most existing indexes degrade when points are removed.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Inspect the deletion path after each vertex removal to see whether every size-k 2-hop neighborhood list is truly nonempty; the paper gives no invariant that one exists.","rationale":"The reader identified the same load-bearing assumption: Algorithm 2's restoration procedure is asserted to restore connectivity and regularity, but no proof is provided. My analysis of Step 5 (lines 30-39) finds a concrete unsecured presupposition: the loop assumes the 2-hop neighborhood of a vertex with a missing edge, and later the neighbor set of a selected v_B, always contains an eligible non-neighbor, so that an edge can be moved without creating a duplicate or self-loop. Nothing in the stated invariants (even degree, Eulerian property, small deletion count, the special-case of |V| <= d) rules out the situation where the residual graph has a tiny final component, e.g., a few vertices whose only usable 2-hop candidate is already a neighbor. The paper's own Table 1 lists consecutive claims (fully dynamic, search reachability, graph connectivity), and the deletion algorithm is the only place where these properties are tied to an unverified code path. The fix is to prove or empirically verify the invariant; the most direct empirical check is to run the code with an invariant checker on adversarial deletion patterns. I therefore agree with the reader's CONDITIONAL verdict and see no reason to move toward ACCEPT or REJECT without that verification.","tokens_in":10500,"tokens_out":1649,"duration_ms":14740,"concrete_test":"Instrument the public DEG implementation and run the adversarial stress test: take SIFT1M/Deep1M, build the graph, then delete vertices in batches with deliberately chosen patterns that maximize fragmentation (e.g., delete all vertices within a small radius of a random pivot at once, delete a clique's vertices, or delete half the vertices in one bulk pass). For each deletion, directly verify the graph invariants: (1) every vertex has degree exactly d, (2) the graph is connected via BFS from an arbitrary remaining vertex, and (3) every vertex is reachable from an arbitrary query's entry point. If the check fails on any deletion, the connectivity/regularity guarantee is falsified.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's claim that DEG always remains connected, even-regular, and search-reachable after arbitrary insertions and deletions rests on Algorithm 2, but no invariant or proof is supplied for it. The described loop in Step 5 (lines 30-39) appears to assume that for every remaining vertex v_A with a missing edge, the 2-hop neighborhood V_n contains at least one vertex v_B not already adjacent to v_A, and that thereafter each v_C, which is another vertex with a missing edge, has some non-neighbor v_D in N(G,v_B) whose edge can be removed. These existential requirements are asserted and not derived from the prior invariants (even regularity, Eulerian property, edge count parity). On a non-Eulerian subgraph, or if components merge in a way that leaves a vertex with all neighbors occupied in a small final component, the special-case loop could terminate with empty v_D, leaving the affected vertices with the wrong degree or the graph disconnected. That would break the guarantee that search can reach all remaining vertices and would invalidate the claim that deletions require no tombstones and no stale vertices. The reader correctly identified this as the central unproved step. The reported experiments may still show good average performance, but the headline guarantee of connectivity is exactly what is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes the Dynamic Exploration Graph (DEG), an extension of the authors' prior continuously refining Exploration Graph (crEG), for approximate nearest neighbor search in dynamic datasets. DEG is designed to support both insertions and deletions while maintaining an even-regular undirected graph with guaranteed connectivity. Two claimed innovations are a vertex deletion algorithm that repairs the graph immediately without tombstones, and a data distribution-agnostic graph expansion method. The paper presents pseudocode for reduction, restoration, and extension (Algorithms 1-4), and reports experiments on SIFT1M, Deep1M, and GloVe in static, online, and streaming scenarios, comparing DEG against HNSW, DiskANN, and SWINN. The reported results show DEG with lower construction times and higher search efficiency in most settings.","tokens_in":10918,"tokens_out":6162,"duration_ms":52825,"significance":"If the connectivity and regularity guarantees for the deletion algorithm are correct, DEG would be a practically valuable fully dynamic graph-based ANNS index, avoiding the tombstone overhead of HNSW and the delayed consolidation of FreshDiskANN. The paper includes an open-source implementation, which is a strength for reproducibility. The comparison against external baselines on three standard datasets is a useful empirical contribution. However, the paper's central theoretical claim—that Algorithm 2 always restores connectivity and even regularity after arbitrary deletions—is asserted without proof. Since this guarantee is the basis for the paper's main contribution and for the claim that deletions leave no stale vertices, the manuscript is not yet ready for acceptance. The empirical evaluation also lacks any measure of run-to-run variability, which weakens the strength of the performance claims.","major_comments":[{"comment":"The headline claim that the deletion mechanism 'guarantees graph connectivity' (Abstract and Section 5) is not established. No invariant or proof is given that RestoreGraph terminates with a connected, even-regular graph after removing an arbitrary vertex. In particular, Step 5 (lines 30-39) assumes that for every remaining vertex v_A there exists a non-neighbor v_B in its 2-hop neighborhood, and that for each v_C there exists v_D in N(G,v_B) satisfying the stated non-adjacency conditions. These existential requirements are asserted but not derived from the graph's even-regularity, Eulerian property, or edge-count parity. If the 2-hop neighborhood is fully occupied, or if the candidate set for v_D is empty in a small or non-Eulerian component, the special-case loop can terminate without repairing degree or connectivity. Because this is the load-bearing guarantee for immediate deletion without tombstones, a rigorous proof or a redesigned algorithm with a verified invariant is required.","section":"Section 5.1, Algorithm 2"},{"comment":"The pseudocode for RestoreGraph is not executable as written and its control flow is unclear. Line 8 uses an undefined symbol n in 'S ← N(G,v) ∪ {n}'; this appears to be a typo for '{v}', but as written the algorithm cannot be run. In addition, the while condition on line 6 is 'c < |Vi|/2 - 1', where c counts newly reachable involved vertices, not the number of subgraphs; the accompanying text in Section 5.1 Step 4 refers to 'only d/2−1 subgraphs remain', but the Step 3 loop on lines 17-23 actually runs until |L| = 1, i.e., until all subgraphs are merged. The relationship between c, the number of subgraphs, and the stopping condition needs to be explained, and the pseudocode must be corrected, because Algorithm 2 is the specification of the paper's central correctness claim.","section":"Algorithm 2, lines 8 and 16-24"},{"comment":"All experimental results are single runs with no reported variance, error bars, or number of trials. The paper's central empirical claim—that DEG surpasses existing algorithms in construction time and search efficiency—therefore cannot be assessed for statistical reliability. For example, Table 3 reports DEG T2 at 11.0 minutes versus HNSW T2 at 23.7 minutes on SIFT1M; without multiple trials or standard deviations, it is unclear whether such margins are meaningful. Please report multiple runs or confidence intervals for the key comparisons.","section":"Section 6, Figure 2 and Table 3"}],"minor_comments":[{"comment":"The phrase 'the OptimizeEdge method from crEG where used' should read 'was used'.","section":"Section 6.1"},{"comment":"The caption contains the garbled phrase 'the gray vertices form re individual a vertex induced subgraphs'; it should be 'the gray vertices form individual vertex-induced subgraphs'.","section":"Figure 1 caption"},{"comment":"The statement that 'a minimum regularity of 4 is required to avoid cycles and isolated vertices' is not justified as written: a 2-regular connected graph is a single cycle and has no isolated vertices. The intended property (perhaps avoiding bridges or ensuring 2-edge-connectivity) should be stated precisely.","section":"Section 5, paragraph on Even Regularity"},{"comment":"The claim that indexing and reduction time complexity 'appears logarithmic' is based on fitted curves, but no goodness-of-fit values (e.g., R²) are reported, so the reader cannot judge the quality of the fits.","section":"Section 7, Figure 3"},{"comment":"The description of scenario T3 is confusing: it says to build with the second half and then remove a vertex from the second half while adding a vertex from the first half; consider clarifying the intended stream direction and the resulting index contents.","section":"Section 6.2"}],"recommendation":"major_revision","confidential_remarks":"The paper extends the authors' own prior work (crEG), and the novelty rests primarily on the deletion and restoration algorithm. The missing proof of the connectivity guarantee is the main obstacle; without it, the central contribution is not established. The empirical work is potentially strong, but the absence of variance reporting further weakens the comparison. I recommend major revision rather than rejection because the issues are fixable within the manuscript's scope (by adding a proof or revising the claim, and by adding repeated trials)."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper delivers a genuinely useful extension of the authors' crEG: a fully dynamic even-regular graph that removes vertices immediately instead of tombstoning them, plus a distribution-agnostic expansion rule. If the numbers hold, this is the kind of thing practitioners will adopt. The experimental section is coherent and the code is public, which counts.\n\nWhat's actually new is the deletion-and-repair routine (Algorithms 1 and 2) and the fixed-parameter expansion in Algorithm 3. The deletion routine is not in the earlier crEG work, and neither is the extension scheme that avoids a tuned hyperparameter. The comparison against HNSW, DiskANN, and SWINN in three scenarios is reasonable, and the build-time advantage is striking.\n\nThe soft spot is exactly the one the stress-test note flags: Algorithm 2's connectivity restoration is not proved. Step 5 assumes that for every remaining vertex with a missing edge, you can always find a partner in the 2-hop neighborhood, and then a suitable vertex to rewire. That existential assumption is not derived from the even-regular/Eulerian invariants. The abstract and Table 1 claim 'guarantees graph connectivity' with no proof. This is load-bearing: if a deletion can strand a vertex with the wrong degree or leave the graph disconnected, the 'no tombstones, fully dynamic' claim fails. I don't see an obvious counterexample in the paper, but the authors need to either supply an invariant and proof or soften the guarantee to 'maintains connectivity in practice.'\n\nMinor issues: no run-to-run variance or error bars anywhere; the SWINN comparison is undercut by their observation that their implementation is slower than serial scan; and FreshDiskANN, which is directly relevant to dynamic deletion, is not among the baselines. The 'data distribution-agnostic' claim is supported only by three datasets, all with similar LID range.\n\nWho should read this: anyone building dynamic ANNS for recommendation or multimedia retrieval, and researchers working on graph repair. It deserves a serious referee: the contribution is concrete and the experiments are mostly well designed. But the referee should push hard on Algorithm 2 before signing off.","headline":"A practically useful dynamic ANNS graph with immediate deletion, held back by an unproved connectivity guarantee in the repair step.","tokens_in":11288,"tokens_out":2318,"would_cite":true,"duration_ms":21642,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"DEG supports instant vertex deletion with guaranteed connectivity and runs at static-index speed.","keywords":["approximate nearest neighbor search","dynamic graph index","even-regular graph","graph connectivity","vertex deletion","streaming data","online data","multimedia retrieval"],"falsifier":"Build a small even-regular graph such as DEG_4 on random points, delete a vertex whose former neighbors lie in separate dense clusters, and run Algorithm 2; if any pair of remaining vertices is disconnected or any vertex ends with degree different from d, the guarantee fails.","tokens_in":10325,"feed_emoji":"🔍","tokens_out":5974,"duration_ms":44588,"temperature":0.7,"pith_summary":"The paper introduces the Dynamic Exploration Graph (DEG), a graph-based index for approximate nearest neighbor search that supports immediate insertion and deletion of data points. It claims DEG keeps search speed and recall comparable to the best static graph methods while also handling streaming and online datasets, something most graph indexes cannot do without marking deleted vertices as tombstones. Two mechanisms carry the claim: a deletion routine that reconnects the graph after removing a vertex, and a distribution-agnostic expansion routine that attaches new vertices without a tuned hyperparameter. If correct, DEG would remove a long-standing bottleneck for multimedia retrieval over evolving data.","feed_headline":"Remove data points instantly and keep search fast","feed_subtitle":"DEG, a new graph index, supports streaming and online data at static-index speeds with no tombstoned vertices left behind.","key_machinery":"The central object is an even-regular undirected graph (degree d, with d at least 4) maintained as an Eulerian graph, so every edge lies on a cycle and the graph is 2-edge-connected. That property is what makes deletion feasible: after a vertex is removed, each of its neighbors still has an alternative path through the graph. The load-bearing mechanism is the restoration routine (Algorithm 2), which forms induced subgraphs from the deleted vertex's neighbors, merges them via simultaneous BFS until d/2−1 components remain, then adds circular edges and repairs degrees so the graph stays regular and connected. The expansion routine (Algorithm 3) uses a range search to find candidate neighbors, applies an MRNG check to prefer edges that will help navigation, and feeds any vertex that lost an edge back into the same restoration routine.","core_discovery":"The central claim is that a graph index can be fully dynamic—both insertions and deletions—without sacrificing the speed and connectivity that make graph-based approximate nearest neighbor search work. DEG is an even-regular undirected graph built on the continuously refining Exploration Graph. To delete a vertex, it isolates the vertex and runs a restoration procedure (Algorithm 2) that merges the remaining components via breadth-first search and adds circular edges among the deleted vertex's former neighbors, restoring both connectivity and degree regularity. To insert a vertex, it attaches to the closest candidates from a range search, occasionally stealing an edge from a saturated neighbor, and then reuses the same restoration routine. In experiments on SIFT1M, Deep1M, and GloVe, the paper reports DEG builds faster than HNSW, DiskANN, and SWINN, and achieves higher queries per second at recall above 95% in static, streaming, and online scenarios.","pith_inferences":["If the connectivity guarantee holds, the restoration routine could be adapted to other even-regular graph indexes, providing a general recipe for immediate deletion in navigable small-world graphs.","The BFS-based subgraph merging may implicitly rely on local clustering; a testable extension would be measuring whether deletion cost worsens on datasets with high local intrinsic dimension where neighborhoods overlap less.","Since the paper compares against tombstoning and periodic consolidation, a natural follow-up is whether DEG's immediate deletion remains competitive under burst deletions where many vertices are removed at once."],"forward_implications":["DEG can be used as a drop-in index for collections that change over time, since it removes vertices immediately instead of marking them deleted, avoiding the slowdown that tombstoning causes in HNSW-style indexes.","Construction and deletion costs grow logarithmically with index size, suggesting the approach scales beyond the million-point datasets tested here.","Because the same graph structure performs at parity with static state-of-the-art graphs in the static scenario, a single index design can serve static, streaming, and online workloads without reconfiguration.","The distribution-agnostic expansion removes a hyperparameter that would otherwise need retuning when the data distribution drifts."],"supporting_citations":[{"why":"Supplies the continuously refining Exploration Graph that DEG builds on, including the extend-and-refine method DEG replaces.","marker":"[10]"},{"why":"HNSW is the primary incremental graph baseline; its mark-deleted behavior is the comparison point for dynamic search.","marker":"[15]"},{"why":"SWINN is the streaming sliding-window baseline that DEG outperforms in the streaming scenario.","marker":"[16]"},{"why":"FreshDiskANN is the dynamic two-layer index baseline that uses delayed consolidation for deletions.","marker":"[22]"},{"why":"Survey that supplies benchmark parameter settings and contextualizes graph construction complexity.","marker":"[26]"},{"why":"Provides the quartic-graph construction that underpins the Eulerian 2-edge-connectivity property DEG relies on for deletion.","marker":"[23]"},{"why":"Range search algorithm used in DEG's graph extension to find candidate neighbors for a new vertex.","marker":"[11]"}],"fun_headline_variants":["Dynamic graph index keeps search fast after deletions","Delete points and keep ANN search speed intact","DEG: dynamic graphs for evolving multimedia datasets","Streaming data? DEG maintains fast ANN search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The connectivity guarantee rests on an unproved claim that the restoration procedure in Algorithm 2 always reconnects every component left by a deleted vertex; the paper offers no invariant or proof, only a special-case loop.","fun_headline_variants_meta":{"raw":{"variants":["Dynamic graph index keeps search fast after deletions","Delete points and keep ANN search speed intact","DEG: dynamic graphs for evolving multimedia datasets","Streaming data? DEG maintains fast ANN search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000127,"raw_usage":{"total_tokens":1096,"prompt_tokens":912,"completion_tokens":184,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":528,"completion_tokens_details":{"reasoning_tokens":127}},"tokens_in":528,"tokens_out":184,"duration_ms":2502,"temperature":1.0,"reasoning_tokens":127,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:23:05.333331+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a small even-regular graph such as DEG_4 on random points, delete a vertex whose former neighbors lie in separate dense clusters, and run Algorithm 2; if any pair of remaining vertices is disconnected or any vertex ends with degree different from d, the guarantee fails.","supporting_citations":[{"cited_title":"In: Gurrin, C., Kongkachandra, R., Schoeffmann, K., Dang-Nguyen, D.T., Rossetto, L., Satoh, S., Zhou, L","cited_arxiv_id":null,"evidence_quote":"Supplies the continuously refining Exploration Graph that DEG builds on, including the extend-and-refine method DEG replaces."},{"cited_title":"IEEE Trans","cited_arxiv_id":null,"evidence_quote":"HNSW is the primary incremental graph baseline; its mark-deleted behavior is the comparison point for dynamic search."},{"cited_title":"Journal of Combinatorial Theory, Series B16(2), 124–133 (1974)","cited_arxiv_id":null,"evidence_quote":"Provides the quartic-graph construction that underpins the Eulerian 2-edge-connectivity property DEG relies on for deletion."},{"cited_title":"IPSJ Trans","cited_arxiv_id":null,"evidence_quote":"Range search algorithm used in DEG's graph extension to find candidate neighbors for a new vertex."}],"review_version":2}