{"id":"f0b910d7-907c-450a-bb08-d238029d8edb","arxiv_id":"1908.11788","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"LEKS, a tree-based local expansion algorithm, finds smaller-weight intimate-core groups in weighted graphs faster than the existing ICG-M heuristic on three real networks.","lead":"The authors present LEKS, a local-exploration algorithm that finds intimate-core groups, connected k-cores containing query nodes with minimum group weight, faster than the previous ICG-M method. The paper is relevant to anyone building community search or recommendation tools on large weighted networks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Local-expansion seeding is unproven: no size or quality guarantee links the tree-expanded candidate to a better ICG-M result, and the reported advantage rests on three datasets without paired statistical evidence.","rationale":"The reader's weakest assumption identifies exactly the load-bearing premise: local expansion from a small-weighted spanning tree produces a candidate whose ICG-M refinement yields a better group than refining the maximal connected k-core, with no approximation or size guarantee and only three empirical datasets as evidence. I find no internal contradiction in the algorithms; the framework is plausible, the experiments are directionally consistent with the claim, and the case study supports the mechanism on one illustrative query. The most serious risk is that the reported advantage is not robust: because both methods use the same greedy refinement, there is no formal reason a smaller initial candidate must lead to a lower final weight, and the averaged figures without error bars or paired tests cannot rule out chance or outlier-driven differences. This risk is addressable by releasing per-query data and performing a paired statistical comparison; it does not by itself invalidate the work, so the reader's CONDITIONAL verdict remains appropriate.","tokens_in":13846,"tokens_out":13356,"duration_ms":134150,"concrete_test":"Obtain from the authors the per-query-set outputs for the 100 query sets used in Exp-1 and Exp-2, and compute for each (dataset, k, |Q|) cell the paired difference d_i = w(LEKS_i) - w(ICG-M_i) with a 95% bootstrap or Wilcoxon confidence interval, together with the candidate-size ratio r = |G_Q| / |C_k|. The central claim is supported only if the upper confidence bound of d is below 0 in every cell and the median r is substantially below 1; if any cell's interval includes 0 or r is close to 1, the claimed superiority of LEKS over ICG-M is not established. This check requires no new experiments, only the per-query data and code that the paper should already have.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that LEKS-tree and LEKS-path return lower-weight intimate-core groups than ICG-M, and do so faster, depends on the assertion in Sections 4.2 and 4.4 that expanding a shortest-path tree yields a small candidate G_Q whose ICG-M refinement beats refining the maximal connected k-core. No theorem in the paper bounds |G_Q| relative to the maximal k-core; Section 4.4 explicitly acknowledges that G_Q can equal the maximal connected k-core in the worst case. Even when G_Q is smaller, the final weights are produced by the same greedy node-removal procedure as ICG-M, and set inclusion does not imply that the greedy outcome from the smaller set has lower weight: the local candidate may exclude a low-weight connected k-core that reaches the queries through nodes outside the BFS layers, or it may force a different local optimum. The protection mechanism in Section 4.5 is described in prose rather than in the pseudocode, and only covers a narrow condition (degree-k query nodes and their neighbors), so it is not auditable from the text. The only support for the load-bearing premise is Exp-1 and Exp-2 on three real networks, reported as averaged curves over 100 random query sets with no error bars, no paired significance tests, and no released code; a small number of heavy-tailed query sets could drive the observed mean differences. If the advantage is not systematic across query sets or does not persist on additional networks, the central comparative claim is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper addresses the intimate-core group search problem: given an undirected weighted graph, a set of query nodes Q, and an integer k, find a connected k-core containing Q with minimum total edge weight. The problem is NP-hard, so the paper follows the heuristic line of Zheng et al. [29], which starts from the maximal connected k-core and greedily deletes high-weight nodes (ICG-M). The proposed LEKS framework changes the starting point: it first builds a query-connecting tree (either an all-pairs shortest-path spanning tree or a sequential path-based tree), expands this tree level by level until a connected k-core containing Q is obtained, and then applies the ICG-M refinement on this smaller candidate graph. A protection mechanism is proposed to prevent removal of query nodes with degree exactly k. Experiments on wiki-vote, Flickr, and DBLP compare LEKS-tree and LEKS-path against ICG-M for k in {2,4,6,8} and |Q| in {1,...,7}, reporting lower group weights and lower running times, plus a DBLP case study.","tokens_in":14184,"tokens_out":8135,"duration_ms":71608,"significance":"If the empirical claim is correct, LEKS is a practically useful contribution: it provides a simple and natural way to shrink the initial candidate for a well-known NP-hard community-search problem, and the reported gains on three networks are substantial. The paper is clearly written and contains a reasonable algorithmic framework, complexity analyses for the tree-generation phases, and a concrete case study. The strengths are the local-exploration idea, the two tree-construction variants, and the attempt to protect critical query nodes. However, the central comparative claim is supported only by average curves without statistical tests or error bars, on three datasets and without released code, so the significance remains conditional. The lack of any worst-case or average-case analysis of the expansion phase is acceptable for a heuristic paper only if the experimental evidence is thorough, which is not currently the case.","major_comments":[{"comment":"The central premise that locally expanding a shortest-path tree yields a candidate GQ whose ICG-M refinement has lower group weight than refining the maximal connected k-core is not supported by any analysis. Section 4.4 explicitly concedes that GQ can equal the maximal connected k-core in the worst case, and even when GQ is a proper subgraph, the greedy deletion procedure could in principle find a heavier local optimum from the smaller set because GQ may exclude low-weight k-cores that connect queries through nodes outside the BFS layers. Because this premise is the basis for the paper's quality claim, it needs either formal support or a much stronger empirical justification than the three averaged curves currently provide.","section":"Section 4.4 / Algorithm 5 / Section 5, Exp-1"},{"comment":"The experimental evaluation is not sufficient to support the claim that LEKS 'always' finds smaller weights and is 'always' faster. Figures 5-8 report averages over 100 random query sets on three networks, with no error bars, standard deviations, or paired significance tests, and no code or random seeds are provided. On heavy-tailed network data, a small number of query sets could drive the reported mean differences, so the reader cannot verify that the advantage is systematic. The manuscript should add per-query distributions or significance tests, additional datasets, and a reproducibility statement.","section":"Section 5"},{"comment":"The protection mechanism is not auditable from the manuscript. Algorithm 2's refinement step is simply 'Apply ICG-M [29] on graph GQ', and the description of protecting query nodes with degree exactly k and their neighbors appears only in prose, without pseudocode or a precise modification of the ICG-M removal procedure. It is also unclear why the protection covers only the degree-exactly-k case, since a query node with degree > k could also be removed or collapsed during bulk deletion. The authors should specify the exact protected set and how the ICG-M subroutine is altered.","section":"Section 4.5"}],"minor_comments":[{"comment":"The complexity analysis of Algorithm 3 does not match its pseudocode: the loop over all pairs (q1,q2) in Q implies O(|Q|^2) shortest-path computations, while the text claims a single-source implementation in O(|Q| mk log nk). Please clarify which implementation is actually used.","section":"Section 4.3"},{"comment":"Reference [15] is a SIGMOD paper on truss decomposition, not a dataset repository; the statement 'All datasets are publicly available from [15]' should point to the actual data source.","section":"Section 5, Datasets"},{"comment":"The sentence 'ICG-M can find answers quickly for k=4, which achieves similar performance with LEKS methods' is vague; no separate k=4 results are highlighted.","section":"Section 5, Exp-1"},{"comment":"'Efficiency' is a typo; it should be 'Efficiency'.","section":"Figure 6 caption"},{"comment":"The phrase 'As pointed by [3,27,28]' has a grammar issue; it should be 'As pointed out by [3,27,28]'.","section":"Section 4.5"},{"comment":"The statement 'GQ in practice is always much smaller than it' is an empirical assertion that would benefit from a quantitative report of candidate sizes for all datasets.","section":"Section 4.4, after Algorithm 5"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's relation to [29] warrants editorial attention: one co-author appears in both papers, and the paper's main comparison is against that prior method. The overlap is not improper, but the authors should more clearly delineate the technical novelty and, if possible, include an independent implementation of the baseline. The current evaluation is the main barrier; even with minor revisions, the lack of statistical validation and reproducibility makes accept premature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper's contribution is a new local-seeding strategy for the NP-hard intimate-core group search problem. Instead of starting from the maximal connected k-core as the ICG-M baseline does, LEKS builds a shortest-path tree over the query nodes, expands it BFS layer by layer until a connected k-core appears, and only then runs ICG-M refinement. That is a legitimate idea, and it is not in the earlier paper by Zheng et al. The two tree-building variants (all-pairs MST and path-based) are reasonable, and the experiments on three real networks consistently show LEKS finding lower-weight groups and running faster.\n\nThe main weakness is that the comparative claim is entirely empirical and the empirics are thin. There are no error bars or significance tests, so we do not know whether the differences over 100 random query sets are systematic or driven by a few heavy-tailed cases. The text overclaims by saying LEKS 'always' beats ICG-M, while the k=4 plot shows them similar. No code is released, which makes the numbers hard to verify. The protection mechanism for critical query nodes is described in prose but not in the pseudocode, and it only covers query nodes with degree exactly k; the behavior for higher-degree query nodes during greedy removal is left implicit. There is also no theoretical guarantee that the local candidate leads to a better final output; the paper admits the candidate can equal the maximal k-core in the worst case. None of these are fatal for a heuristic paper, but together they mean the central claim rests on a small empirical base.\n\nI think the work is a solid, useful extension for the community-search subfield. The authors are not overselling the theory; they position LEKS as a practical method. If they release the code, add error bars or at least paired tests, and soften the 'always' language, it would be a good conference paper. Worth sending to a serious referee, but expect requests for additional datasets and a more auditable description of the protection mechanism.","headline":"New local-seeding heuristic for intimate-core group search shows consistent empirical gains over the previous state of the art, but the evaluation is under-powered and the protection mechanism is under-specified.","tokens_in":14656,"tokens_out":4302,"would_cite":true,"duration_ms":39336,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"By starting from a small weighted tree that connects the query nodes and expanding it locally, LEKS finds intimate-core groups with smaller total edge weight than the prior ICG-M method while running significantly faster on large…","keywords":["community search","k-core","weighted graphs","local exploration","core decomposition","intimate-core group","graph algorithms"],"falsifier":"Construct a weighted graph with two connected k-cores containing the same query nodes: one reachable only through a heavy edge and another slightly larger but composed of light edges. If LEKS's local expansion locks onto the first core and returns a higher group weight than ICG-M starting from the maximal core, the paper's claim of uniformly better quality fails; running both algorithms on this graph decides it.","tokens_in":13635,"feed_emoji":"🌐","tokens_out":6682,"duration_ms":53741,"temperature":0.7,"pith_summary":"Intimate-core group search asks for the connected k-core containing a given set of query nodes that has the smallest total edge weight. Prior state-of-the-art methods start from the maximal connected k-core and peel nodes away, which is slow when that core is large. This paper presents LEKS, a local-exploration framework that connects the query nodes with a low-weight tree, expands the tree level by level until it encloses a connected k-core, and then refines that candidate with the existing ICG-M deletion routine. On three real weighted networks, LEKS-tree and LEKS-path return groups with smaller group weights than ICG-M while running significantly faster, with LEKS-path the fastest in most cases. The message is that a query-centric local start can dominate a global start for this NP-hard problem, at least empirically.","feed_headline":"Local search finds tighter k-core groups in less time","feed_subtitle":"A tree-based local expansion beats the maximal k-core baseline on three networks, returning smaller group weights.","key_machinery":"The central object is the intimate-core group, a connected k-core containing all query nodes with minimum total edge weight, a problem known to be NP-hard. The mechanism that carries the argument is a three-phase pipeline: (1) tree generation, which uses Dijkstra shortest paths and a Prim minimum spanning tree (or a path-based variant) to build a small-weighted tree spanning the queries; (2) tree-to-graph expansion, which grows the tree level by level until the induced subgraph contains a connected k-core; (3) refinement with the ICG-M bulk-deletion routine, guarded by a protection mechanism that preserves query nodes and their required neighbors so the k-core does not collapse. The k-core index, which stores the coreness of every node and is built offline by core decomposition, lets each phase test k-core membership quickly.","core_discovery":"On the paper's own terms, the central discovery is that the quality and speed of intimate-core search are decided before refinement begins: a small, query-centric candidate subgraph yields better answers than the maximal connected k-core. LEKS builds that candidate in three phases: it first computes shortest paths among query nodes and merges them into a spanning tree (Algorithm 3) or a path-based tree (Algorithm 4); it then expands the tree level by level through the k-core until the induced subgraph contains a connected k-core; finally it applies ICG-M's bulk node removal. The experiments report lower group weights for both LEKS variants than ICG-M across k values from 2 to 8 and query-set sizes from 1 to 7 on wiki-vote, Flickr, and DBLP, plus running-time reductions, with the path variant fastest in most cases. The DBLP case study is the concrete illustration: for authors Huan Liu, Xia Hu, and Jiliang Tang at k=4, LEKS-path returns a 5-node, 10-edge 4-core of weight 1.6, whereas ICG-M returns a 12-node subgraph of weight 16.7.","pith_inferences":["The same tree-then-expand pattern could be transplanted to other dense-subgraph community models, such as k-truss or clique-percolation search, where the baseline currently starts from the global maximal structure.","A natural stress test is to run both algorithms on a broader set of graphs, including networks with skewed weight distributions or bridge-like heavy edges, to see whether LEKS ever returns a heavier group than ICG-M or produces a candidate as large as the maximal core.","The protection of query nodes connects LEKS to the anchored-k-core literature; formalizing the minimal set of nodes that must be protected for a query set would turn an empirical safeguard into a provable invariant."],"forward_implications":["Community search on large weighted graphs becomes interactive: because the initial candidate is local, LEKS can return an intimate group without ever materializing the maximal k-core.","The returned groups are more intimate under the edge-weight semantics, since lower group weight means tighter relationships; this matters for co-authorship, communication, and collaboration networks.","The offline k-core index makes repeated queries cheap, amortizing the core-decomposition cost over many online queries on the same graph.","The protection mechanism keeps the answer feasible during refinement, since query nodes and their required neighbors cannot be deleted by the peeling process.","LEKS-path offers a practical speed-quality tradeoff: it matches LEKS-tree in group weight while running fastest in most reported cases."],"supporting_citations":[{"why":"Defines the intimate-core group problem, proves NP-hardness, and provides the ICG-S/ICG-M refinement algorithms that LEKS uses as its baseline and final refinement step.","marker":"[29]"},{"why":"Supplies the O(m) core decomposition used to build the k-core index and to identify connected k-cores during expansion.","marker":"[2]"},{"why":"Provides Dijkstra and Prim algorithms used for shortest paths between query nodes and minimum spanning tree construction in tree generation.","marker":"[5]"},{"why":"Source of the three public real-world weighted networks used in the experimental comparison.","marker":"[15]"},{"why":"Anchored k-core problem motivates the protection mechanism that prevents critical query nodes from being deleted.","marker":"[3]"},{"why":"The OLAK algorithm for preventing k-core unraveling supports the design of protected critical nodes.","marker":"[27]"},{"why":"Collapsed k-core problem identifies critical users whose removal collapses the core, informing the query-node protection in refinement.","marker":"[28]"}],"fun_headline_variants":["Local tree search shrinks intimate-core groups","Query-first core search beats maximal k-core","LEKS: smaller k-core groups via local expansion","Fast intimate-core search from query to core","Tighter k-core answers from local exploration"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a small tree expanded locally around the query nodes yields a candidate subgraph that, after refinement, is at least as good as, and typically much smaller than, the maximal connected k-core; the paper supports this only empirically on three datasets and gives no worst-case guarantee.","fun_headline_variants_meta":{"raw":{"variants":["Local tree search shrinks intimate-core groups","Query-first core search beats maximal k-core","LEKS: smaller k-core groups via local expansion","Fast intimate-core search from query to core","Tighter k-core answers from local exploration"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000179,"raw_usage":{"total_tokens":1294,"prompt_tokens":933,"completion_tokens":361,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":293}},"tokens_in":549,"tokens_out":361,"duration_ms":3906,"temperature":1.0,"reasoning_tokens":293,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:06:51.158891+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a weighted graph with two connected k-cores containing the same query nodes: one reachable only through a heavy edge and another slightly larger but composed of light edges. If LEKS's local expansion locks onto the first core and returns a higher group weight than ICG-M starting from the maximal core, the paper's claim of uniformly better quality fails; running both algorithms on this graph decides it.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the intimate-core group problem, proves NP-hardness, and provides the ICG-S/ICG-M refinement algorithms that LEKS uses as its baseline and final refinement step."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Dijkstra and Prim algorithms used for shortest paths between query nodes and minimum spanning tree construction in tree generation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the three public real-world weighted networks used in the experimental comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Anchored k-core problem motivates the protection mechanism that prevents critical query nodes from being deleted."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The OLAK algorithm for preventing k-core unraveling supports the design of protected critical nodes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Collapsed k-core problem identifies critical users whose removal collapses the core, informing the query-node protection in refinement."}],"review_version":1}