{"id":"da9ce117-642b-49a9-b455-72479bbaa45a","arxiv_id":"2502.01435","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper introduces STC-DEN, a density score that interpolates between maximum clique and densest subgraph, proves it NP-hard for lambda<1, and provides ILP and heuristic solvers.","lead":"This paper defines a graph-mining problem that finds a dense community while labeling each friendship as strong or weak under the strong triadic closure rule, balancing the two edge types with a parameter. The extremal cases reproduce two classic problems, maximum clique and densest subgraph, and the paper gives exact and heuristic algorithms and tests them.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The unproved inequality in Prop 4.3's reduction is a real gap, but a straightforward derivation shows it holds; the NP-hardness claim is not jeopardized.","rationale":"The reader's weakest-assumption analysis identifies the only unprotected step in the central hardness reduction, so there is partial agreement. However, after working through the construction, the asserted inequality follows from the clique structure and the relabeling argument; it is a missing derivation rather than a false step. The handling of |W_i| ≤ 2, the forcing of all cliques and all v_j into U, and the final reduction from MinSTC are internally consistent. The experimental section does not bear on the complexity claim. The paper should add the two-line proof of the inequality, but the central claim itself appears correct. Hence the reader's CONDITIONAL verdict need not be strengthened; it should remain conditional only pending the requested derivation, with no change to the overall assessment.","tokens_in":19878,"tokens_out":17346,"duration_ms":160669,"concrete_test":"Insert a derivation of the inequality: for t = |W_i|, r = |{w ∈ W_i : v_{j(w)} ∈ U}|, and r_c ∈ {0,1}, show after relabeling that Δ(U\\W_i,U) ≤ (t−1)/2 + λr/t and Δ(U,U∪{c}) = t + λr_c, then verify (t−1)/2 + λ < t + λr_c for all t ≥ 3 and λ < 1. As an independent check, exhaustively enumerate all valid STC labelings on the small gadget with n = 5..6 and all possible W_i, U, r, r_c to confirm no counterexample exists; a counterexample would invalidate Proposition 4.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader correctly flags Appendix A.1, proof of Proposition 4.3: after defining W_i = U ∩ C_i, the proof asserts Δ(U\\W_i,U) < Δ(U,U∪{c}) for 3 ≤ |W_i| < n with only 'We can show' and no derivation. This inequality is load-bearing because it forces each W_i to be either empty or all of C_i. On inspection, the assertion can be proven. First relabel cross edges W_i–G as weak; this is STC-valid and score-preserving for t=|W_i|≥3 because each strong cross edge forces all internal clique edges incident to its endpoint to be weak, giving enough weak internal edges to compensate. Then the removed edges consist of t(t−1)/2 internal edges of weight at most 1 and r ≤ t cross edges of weight λ, so Δ(U\\W_i,U) ≤ (t−1)/2 + λr/t. Adding c to U adds t internal clique edges, which can be labeled strong, plus at most one cross edge to its matched vertex in G, labeled weak; hence Δ(U,U∪{c}) = t + λr_c with r_c ∈ {0,1}. Since λ < 1 and t ≥ 3, (t−1)/2 + λ < t ≤ t + λr_c. The inequality therefore holds. The proof is terse but not false; the paper should add this derivation. No other step in the reduction appears unsound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript introduces a parameterized dense-subgraph objective, stc-den (Problem 1): given an undirected graph and a user parameter λ ∈ [0,1], find a vertex set U and an STC-valid labeling L maximizing q(U,L;λ) = (m_s(U,L) + λm_w(U,L))/|U|, where m_s and m_w count strong and weak edges. The theoretical claims are: at λ = 1 the problem equals polynomial-time densest subgraph; at λ = 0 it equals maximum clique and is n^{1−ε}-inapproximable (Propositions 4.1–4.2); and for 0 < λ < 1 it is NP-hard via a reduction from MinSTC to a graph consisting of G plus k cliques of size n with matching-like cross edges (Proposition 4.3). Algorithmically, the paper gives an exact ILP (STC-ILP) over a Dinkelbach-style auxiliary problem with a (1/(1+ε)) guarantee and an exactness criterion (Propositions 5.1–5.3), an LP relaxation with a rounding heuristic (STC-LP, Propositions 5.4–5.5), and three further heuristics (STC-Cut, STC-Peel, Greedy), with complexity bounds. The experiments cover a synthetic block-model graph (ground-truth recovery for small λ), six real networks, and a DBLP case study, and the source code is released.","tokens_in":20155,"tokens_out":42148,"duration_ms":341632,"significance":"The paper's main contribution is the interpolation: the λ-family connects max clique and densest subgraph, with a simple 1/λ approximation for λ > 0, and the interior NP-hardness result (Proposition 4.3) is the key nontrivial claim. If the claims hold, this is a meaningful addition to the dense-subgraph and STC-labeling literatures and, to the authors' knowledge, the first combination of density with strong triadic closure. The paper ships reproducible code and its ILP/LP correctness arguments (Propositions 5.1–5.5) are standard and sound; the endpoint analyses (Propositions 4.1–4.2) are clean, and no fitted parameters enter the theory (λ is a user input). The main weakness is the state of the proof of Proposition 4.3: one load-bearing inequality is asserted without derivation (though it is true) and one displayed score computation is incorrect (though repairable). These defects are local, and I verified the repairs, so the claims are credible; the manuscript nevertheless needs those fixes before publication.","major_comments":[{"comment":"The assertion 'We can show that Δ(U\\W_i,U) < Δ(U,U∪{c})' is load-bearing: together with Lemma A.1 it forces every W_i to be either empty or the whole clique C_i, and without it the reduction from MinSTC does not go through. No derivation is given. I verified that the inequality is correct: after relabeling the cross edges between W_i and G as weak, an STC-valid and score-preserving move for t = |W_i| ≥ 3 (each strong cross edge forces all internal edges at its clique endpoint to be weak, so there are enough internal weak edges to compensate), the removed edges contribute Δ(U\\W_i,U) ≤ (t−1)/2 + λr/t ≤ (t−1)/2 + λ, while Δ(U,U∪{c}) = t + λr_c ≥ t, and (t−1)/2 + λ < t holds for t ≥ 3 and λ < 1. The derivation belongs in the paper; as written the central hardness proof rests on an unstated claim.","section":"Appendix A.1, proof of Proposition 4.3"},{"comment":"The computation 'q(C_i∪V,L′) = (n−1)/2+λ/2' near the end of the proof is incorrect. Under L′ (edges of E(C_i) strong, all remaining edges weak), the subgraph C_i∪V has m_s = C(n,2), m_w = n+|E(G)|, and |C_i∪V| = 2n, so q(C_i∪V,L′) = [C(n,2)+λ(n+|E(G)|)]/(2n), which can be strictly below (n−1)/2, for instance when G is edgeless and n ≥ 5. The contradiction that rules out an optimal U ⊆ V therefore fails as written. The step is repairable by using V∪(∪_i C_i) with all k cliques instead: that subgraph has score at least k((n−1)/2+λ)/(k+1), which exceeds (n−1)/2 because λk ≥ (n+1)/2 > (n−1)/2, but the manuscript needs this correction.","section":"Appendix A.1, proof of Proposition 4.3"}],"minor_comments":[{"comment":"The paper repeatedly misspells 'Max-Clique' as 'Max-Cliqe' (Section 4 and Appendix A.1), Section 1 contains 'a linear linear programming based heuristic', and Section 6 has 'prepossessing' instead of 'preprocessing'.","section":"Throughout"},{"comment":"The approximation algorithm for MinSTC is called 'maximal matching' in Section 3 but 'maximum matching' in the proof of Proposition 5.6; the running time O(n′+m′) quoted there is for greedy maximal matching, so the terminology should be made consistent.","section":"Section 3 and proof of Proposition 5.6"},{"comment":"The assertion that the optimal labeling of a full clique C_i has all internal edges strong and all cross edges weak is stated without proof; it is true by an exchange argument (labeling all cross edges weak and all internal edges strong is STC-valid and changes the score by (1−λ)(#internal weak edges − #strong cross edges), which is nonnegative because every strong cross edge forces its endpoint's internal edges weak), but the argument should be given.","section":"Appendix A.1, proof of Proposition 4.3"},{"comment":"The experimental comparison is among the proposed algorithms only; adding λ = 1 runs, where STC-ILP and the heuristics all reduce to the classical densest subgraph problem, would provide a calibration point for the ILP and the heuristics against a known exact polynomial-time baseline.","section":"Section 6"},{"comment":"The problem stc-relax(α) is used in Proposition 5.4 but is never formally defined; a displayed definition alongside Problem 3 would improve readability.","section":"Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is the KDD '24 conference version (per the copyright block) submitted for journal publication. The two issues flagged in the proof of Proposition 4.3 are both local and both repairable, and I verified the repairs in both cases; I do not doubt the truth of the theorem. The reader's report flagged only the 'We can show' gap; the incorrect q(C_i∪V) computation is a second, distinct defect that the authors should be asked to fix. Fit with the journal's scope is good for a graph-mining/algorithms venue. Citation practices are unremarkable: self-citations appear only in related work and do not carry the argument."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the STC-DEN objective is genuinely new, and the complexity story is mostly right. The reader's main worry—the unproved inequality in the Proposition 4.3 reduction—is a real presentation gap, but I checked the stress-test derivation and it holds. The paper should just add that derivation.\n\nWhat's new: fusing strong triadic closure with dense subgraph discovery is a natural step that hasn't been done. The two endpoint results are clean: λ=1 is densest subgraph, λ=0 is max clique. The NP-hardness for 0<λ<1 via MinSTC is new and, once the missing derivation is supplied, sound. The ILP, LP relaxation with rounding, and heuristics are standard adaptations, but they are competently done and the experiments show the methods work on synthetic and real data. The code is released, which is a plus.\n\nSoft spots: the Appendix A.1 proof of Prop 4.3 asserts the key inequality with 'We can show' and no derivation. I agree with the stress-test that it's derivable: after relabeling cross edges weak and internal clique edges strong, the score is preserved for t≥3, and the comparison (t−1)/2+λ < t gives the bound. Still, it's load-bearing and a referee should demand the actual steps. The experimental section has no variance estimates or statistical tests, and some comparisons (e.g., Greedy beating the others at synthetic λ=0.6) are not explained. Those are minor for this kind of paper.\n\nBottom line: this is a workmanlike, useful contribution for graph-mining readers. It gives a tunable objective with practical algorithms. I'd send it to peer review and ask for the proof expansion plus a few experimental clarifications.","headline":"A useful new dense-subgraph objective that interpolates max clique and densest subgraph; the flagged NP-hardness gap is real but easily repaired, and the paper deserves a serious referee.","tokens_in":20709,"tokens_out":4407,"would_cite":true,"duration_ms":37441,"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":"This paper defines a parameterized dense-subgraph score that interpolates between the polynomial densest-subgraph problem and the NP-hard maximum-clique problem, and claims the entire interior of the parameter range is NP-hard.","keywords":["dense subgraph","strong triadic closure","NP-hardness","maximum clique","densest subgraph","integer linear programming","graph mining","approximation algorithms"],"falsifier":"Take the construction from Proposition 4.3 with $\\lambda\\in(0,1)$, choose a clique $C_i$ of size $n$, a proper subset $W_i$ with $3\\le|W_i|