{"id":"01cab04a-04be-4501-b9ae-d8ee596bf470","arxiv_id":"2412.11647","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Q-DISCO defines query-aligned densest subgraphs, shows NP-hardness, and offers Lagrangian and peeling heuristics that scale to large networks.","lead":"This paper introduces a new graph problem: find a dense community whose members' opinions, encoded as vectors, align with a query stance. It proves the problem is hard, then gives two fast heuristics that beat simple baselines on Twitter, DBLP, and Deezer networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The core hardness and heuristic guarantees are sound, but the Twitter-based 'valuable insights' claim rests on unvalidated GPT-3.5 opinion scores from a single-seed crawl, leaving the real-world utility conclusion weakly supported.","rationale":"The paper's theoretical contributions—NP-hardness (Prop. 1), ETH-hardness (Prop. 3), and the two heuristics with a-posteriori guarantees—are solid. I verified the approximation-preserving reduction: the value mapping is OPT_Q = OPT_Dam/2, and because any feasible Q-DISCO solution must contain at least as many singletons as original nodes, the back-mapping loses at most a factor 2, giving the claimed alpha-approximation for Dam_kS. I also verified Proposition 5's dual argument: the peeling algorithm removes the minimum-load node, so the maximum over removed-node loads equals the maximum of min-subset loads, i.e., l(T); allocating each edge's unit load to the first-removed endpoint yields a feasible dual solution with objective l(T), so l(T) >= OPT by weak duality. The proof is terse but correct. The reader's identified gap does not land. The remaining concern is the empirical validation of the real-world claims. The Twitter opinions are generated by GPT-3.5 with no human validation, and the crawl is seeded from a single extreme user, creating a biased sample. Since the problem and algorithms treat c_v as ground truth, any systematic error in these scores propagates into the case-study conclusions. This is a genuine limitation but not a fatal flaw: the algorithmic results and the DBLP/Deezer experiments with more objective features support the central method. The paper should either release the Twitter scores, validate them with a second labeler, or temper the real-world claims. Thus I keep the reader's CONDITIONAL verdict.","tokens_in":18985,"tokens_out":30571,"duration_ms":259500,"concrete_test":"Obtain or reconstruct the Twitter dataset (or ask the authors for the scores on a random subset), select 100 users, and have two independent human annotators (or a second, different LLM such as GPT-4) re-score a sample of their tweets on the Vax and Ukraine dimensions; average to user-level opinions as in Appendix B.1. Re-run Q-Peeling with the original and re-scored opinion vectors on the same graph and queries. If the resulting subgraphs in Table 3 have low overlap (e.g., Jaccard < 0.5) or the average agreements change sign, then the real-world conclusions are an artifact of the GPT-3.5 scoring; if they are stable, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central algorithmic argument is internally sound: I re-checked the reduction in Appendix A.1 and the dual construction in Appendix A.3, and Proposition 5's step equating l(T) with the dual objective is correct (edges allocated to the first-removed endpoint yield objective l(T), so l(T) >= OPT by weak duality). The load-bearing weakness is in the empirical support for the real-world claim. The Twitter dataset is crawled from a single self-declared Republican seed with strongly negative opinions, biasing the sample, and the opinion vectors are GPT-3.5 scores averaged over tweets with no validation against human judgments or a second model (Section B.1). Since the whole optimization is driven by c_v = p_v dot q, if these scores are noisy or not faithful to users' actual stances, then a subgraph satisfying c(S) >= theta may not correspond to a group that genuinely shares the queried position. The paper's case-study conclusions, such as finding a tightly connected group with positive opinions on both topics, therefore depend on unvalidated label accuracy. This does not overturn the NP-hardness or the a-posteriori guarantees, but it weakens the 'extract valuable insights' claim, which is part of the paper's central assertion.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript introduces Q-DISCO, a query-centric densest-subgraph problem in which each node carries a vector of opinions and the goal is to maximize subgraph density subject to the average dot-product agreement with a query vector being at least a threshold. It proves NP-hardness and ETH-based inapproximability through a reduction from the Densest at-Most-k Subgraph problem, and it proposes two heuristics: Q-Lagrange, based on a Lagrangian relaxation solved via the HDSP-PN algorithm, and Q-Peeling, a greedy peeling method interpreted through the dual of an LP relaxation. Both algorithms are accompanied by a-posteriori approximation guarantees. The empirical section tests the algorithms on Twitter, DBLP, and Deezer, with additional scalability experiments on four SNAP graphs.","tokens_in":19180,"tokens_out":11642,"duration_ms":119752,"significance":"If the claims hold, the paper makes a useful contribution to dense-subgraph discovery: the problem formulation is natural, the hardness results justify the heuristic approach, and the LP-dual interpretation gives a principled basis for the peeling algorithm. The a-posteriori guarantees are honest certificates rather than pre-test predictions, and the code is publicly available. The main weakness is that the real-world validation, especially on Twitter, depends on opinion scores produced by GPT-3.5 without validation against human judgments or an alternative model, and the crawl is explicitly biased by a single seed user; this limits the strength of the 'valuable insights' conclusions.","major_comments":[{"comment":"The Twitter opinion vectors are generated solely by GPT-3.5 with no validation against human labels, a second model, or any measure of label agreement, and the network was crawled from a single self-declared Republican seed with strongly negative opinions, as the paper itself acknowledges. Since every algorithm's objective is driven by c_v = p_v · q, a subgraph satisfying c(S) >= theta may be dense only with respect to unvalidated GPT-based scores and may not correspond to a group that genuinely shares the queried stance. Consequently, the claim in the abstract and Section 5.2 that the algorithms 'extract valuable insights' from the Twitter data is not fully supported. Please add validation of the opinion scores (e.g., a human-annotated subsample or a second LLM with agreement statistics), a robustness analysis under noise or systematic bias in the opinion scores, or substantially soften the real-world utility claim.","section":"Section B.1, Tables 2-3, Section 5.2"},{"comment":"There is an internal inconsistency in the description of the Agreement Filtering baseline: the text states that for query q=(1,1) with theta=0.5 the baseline returns an empty set, while Table 2 reports AF with density 0 and agreement 0.72, which suggests a singleton fallback rather than an empty set. Please clarify the exact behavior of AF and make the table and prose consistent.","section":"Section 5.2, Table 2 and case-study paragraph"}],"minor_comments":[{"comment":"The proof of Proposition 1 phrases the reduction as an 'if and only if' between source and target solutions with the same value val; more precisely, a DamkS solution of density val yields a Q-DISCO solution of density val/2, while a Q-DISCO solution of density val yields a DamkS solution of density at least 2val. The optimal-value correspondence is what the reduction needs, but the current wording is mathematically imprecise and should be corrected.","section":"Appendix A.1"},{"comment":"The proof of Proposition 5 states 'Recalling ℓ(T) >= OPT' without restating why this inequality holds; since it is central to the a-posteriori bound, the proof should explicitly note that the dual-feasible solution constructed from the peeling procedure has objective ℓ(T), so ℓ(T) is an upper bound on OPT by weak duality.","section":"Proposition 5 and Appendix A.3"},{"comment":"The description of the Twitter dataset would benefit from reporting how many tweets were excluded as irrelevant by GPT-3.5, how the per-user averages are computed when a user has tweets on only one topic, and whether the released dataset will include both the raw tweets and the opinion scores in a way that protects user privacy as claimed in the Ethical Considerations section.","section":"Section B.1"},{"comment":"The UB column is described only as an upper bound from Proposition 4; it would be helpful to state explicitly that the same bound is used for both Q-Lagrange and Q-Peeling, since the bound depends on the final Lagrange multiplier and is algorithm-specific.","section":"Table 4"}],"recommendation":"major_revision","confidential_remarks":"The theoretical core of the paper is sound and likely publishable once the empirical validation concerns are addressed. The load-bearing issue is not the algorithmic machinery but the strength of the real-world conclusions drawn from unvalidated opinion labels. I would be willing to reconsider a revised version that either validates the opinion scores or appropriately narrows the claims about practical insights."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this paper gives a new densest-subgraph variant where you maximize density subject to average agreement with a query vector being at least theta. That is genuinely different from HDSP-PN, which maximizes a weighted sum; the constraint version behaves very differently and is NP-hard. The reduction from DamkS is clean, and the ETH-based inapproximability follows from known DkS results. I checked the appendices; the proof of Proposition 5 is fine. The step equating the load l(T) with the dual objective works because you allocate each removed edge's unit load to the endpoint removed first, so weak duality gives l(T) >= OPT. The reader's worry about a gap there does not hold up.\n\nWhat the paper does well: the two heuristics are sensible and well-motivated. Q-Lagrange is a straightforward Lagrangian relaxation using the known polynomial HDSP-PN solver; Q-Peeling is a peeling procedure with a load that mixes degree and agreement, and the a-posteriori bounds in Propositions 4 and 5 are honest and useful for practitioners. The experiments cover a good range of graphs, including million-scale networks, and the code is public. On DBLP and Deezer the case studies are plausible and show the threshold can be used to navigate the density-agreement trade-off.\n\nThe soft spot is empirical, not algorithmic. The Twitter dataset is crawled from a single self-declared Republican seed with strongly negative opinions on both topics, so the sample is biased by construction. More importantly, the opinion vectors are GPT-3.5 scores averaged over tweets, with no validation against human labels or a second annotator. Since the whole optimization is driven by c_v = p_v dot q, noisy or systematically biased opinion scores mean the discovered subgraphs may not be groups that actually share the queried stance. The paper claims to extract 'valuable insights' from this data, but that claim is only as good as the label accuracy, which is not demonstrated. This is a weakness in the real-world conclusions, not in the core contributions. I'd also note the Twitter data is not yet public, which makes the qualitative claims hard to verify. Minor: no error bars or repeated-run variance in the performance tables, but the margins are often large enough that this is not decisive.\n\nWho is this for: anyone working on dense subgraph discovery, opinion-aware graph mining, or constrained graph optimization. It deserves a serious referee; the algorithmic parts are solid and the problem is likely to be useful. The empirical claims on Twitter need toning down or validation, but that is fixable. I would accept it for review with the expectation of revision.","headline":"Q-DISCO is a well-posed new primitive with sound hardness results and two practical heuristics; the main weakness is the unvalidated opinion labels in the Twitter case study, not the algorithmics.","tokens_in":19746,"tokens_out":2129,"would_cite":true,"duration_ms":18276,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R10","68Q17","05C85","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces Q-DISCO, proves the query-centric densest-subgraph problem is NP-hard and ETH-hard to approximate, and shows two heuristics that return dense query-aligned subgraphs in practice.","keywords":["Q-DISCO","densest subgraph","opinion mining","agreement constraint","NP-hardness","Lagrangian relaxation","greedy peeling","social network analysis"],"falsifier":"Construct a graph with two planted cliques of equal density: one whose members share a queried stance but have opinion vectors scaled so that their dot products with the query sit just below $\\theta$, and another whose members oppose the stance but have large dot products because of vector magnitude. If Q-DISCO or Q-Peeling returns the opposing clique, the dot-product agreement model is falsified as a measure of true alignment; a corrected variant should recover the shared-stance clique once opinion vectors are normalized.","tokens_in":18753,"feed_emoji":"🕸️","tokens_out":11359,"duration_ms":98045,"temperature":0.7,"pith_summary":"This paper introduces Q-DISCO, a formulation for opinion-labeled networks that asks for the densest subgraph whose nodes' average agreement with a query opinion vector is at least a threshold. The paper proves the problem is NP-hard even when every agreement is 0 or 1, and that under the Exponential Time Hypothesis no polynomial-time algorithm can approximate it within a factor of $n^{1/(\\log\\log n)^c}$ for some $c>0$. Because a practically acceptable approximation ratio is therefore out of reach, the authors design two heuristics: Q-Lagrange, built on a Lagrangian relaxation that becomes a weighted densest-subgraph instance solvable in strongly polynomial time, and Q-Peeling, a greedy peeling rule guided by the dual of a linear-programming relaxation. Both come with a-posteriori guarantees that become tight as the returned subgraph's agreement approaches the threshold, and the experiments show Q-Peeling finds denser query-aligned subgraphs than filtering or LP-rounding baselines on real social, co-authorship, and music-friendship networks. If the formulation is accepted, the paper provides a scalable primitive for locating cohesive opinion groups, compatible communities, or polarization niches.","feed_headline":"Dense groups matching a query opinion are NP-hard to find","feed_subtitle":"Two heuristics—Lagrangian and peeling—return near-optimal query-aligned groups on real networks.","key_machinery":"The machinery is the pair 'density objective plus agreement constraint', measured through the per-node agreement $c_v=\\boldsymbol{p}_v\\cdot\\boldsymbol{q}$ and the average agreement $c(S)$. Q-Lagrange's engine is the Lagrangian relaxation $\\max_{S\\subseteq V}\\ d(S)+\\lambda(c(S)-\\theta)$, which is exactly a weighted densest-subgraph problem with positive and negative node weights; the relaxation value $J(\\lambda)$ is a piecewise-linear convex function, so binary search on $\\lambda$ locates the smallest multiplier whose solution respects the constraint, and each evaluation uses a strongly-polynomial max-flow-based routine. Q-Peeling's engine is the dual of an LP relaxation of Q-DISCO, interpreted as a load-balancing problem: each node's load is $\\deg_{V'}(v)+z_2(c_v-\\theta)$, the peeling order removes minimum-load nodes, and the highest-load prefix set $T$ yields an upper bound on OPT; binary search on $z_2$ then steers toward feasible, dense prefixes. The load definition is what lets the algorithms trade edge density against opinion alignment in a single scalar.","core_discovery":"The central claim is that the query-centric densest subgraph is a natural but hard primitive: maximize $d(S)=|E(S)|/|S|$ subject to $c(S)=\\frac{1}{|S|}\\sum_{v\\in S}\\boldsymbol{p}_v\\cdot\\boldsymbol{q}\\ge\\theta$. The hardness reduction adds $k$ isolated nodes with agreement $1$ to an instance of the Densest at-Most-$k$-Subgraph problem, so a feasible set mixing original nodes with singletons corresponds exactly to a size-at-most-$k$ solution, giving NP-hardness for binary agreements and, through the known ETH-hardness of Densest $k$-Subgraph, an almost-polynomial approximation barrier. The paper's constructive response is two algorithms with instance-dependent guarantees: Q-Lagrange solves a Lagrangian relaxation by repeatedly invoking a strongly-polynomial algorithm for weighted densest subgraphs with positive and negative node weights, and Q-Peeling peels nodes by the load $\\deg_{V'}(v)+z_2(c_v-\\theta)$ while binary-searching $z_2$ using the LP dual; each outputs a feasible subgraph and an explicit bound on its gap from optimality. Empirically, the authors report Q-Peeling matches or beats the baselines and finds near-optimal solutions for most queries, and scales to graphs with tens of millions of edges.","pith_inferences":["Because the dot-product agreement is scale-sensitive, normalizing every opinion vector to unit length before forming $c_v$ would make the query semantics invariant to how loudly a user expresses an opinion; this is a direct, testable modification of the model rather than a new algorithm.","The hardness reduction from size-constrained densest subgraph suggests that adding any extra linear constraint on the node weights, such as a second topic threshold, is likely to preserve or increase the hardness, and the peeling load $\\deg(v)+z_2(c_v-\\theta)$ naturally extends by appending more weighted terms.","The a-posteriori bounds depend on observable quantities, so a practical deployment could report the gap $c(S_{\\rm out})-\\theta$ as a live quality indicator and tell a user whether to loosen the threshold.","On opinion-labeled social data, running Q-Peeling with a query and its negation, e.g., $+\\boldsymbol{q}$ and $-\\boldsymbol{q}$, would yield two subgraphs whose sizes and densities quantify the polarization of the network around that axis."],"forward_implications":["The ETH-hardness result means no polynomial-time algorithm can give a practically acceptable worst-case approximation for Q-DISCO, so the field should focus on heuristics with instance-dependent guarantees or on restricted input classes.","Q-Lagrange's a-posteriori bound gives practitioners a certificate: the closer the returned set's average agreement is to the threshold $\\theta$, the closer its density is to optimal.","Q-Peeling's guarantee is half the optimum minus a penalty proportional to the excess agreement of its last feasible set, so the same certificate logic applies in near-linear time.","Raising $\\theta$ continuously morphs the output from the graph's densest subgraph into a small, opinion-pure community, giving a controlled trade-off between density and alignment.","Both algorithms avoid LP solvers and run in near-linear time times a logarithmic number of iterations, so they scale to graphs with tens of millions of edges where LP-based baselines time out."],"supporting_citations":[{"why":"Establishes the NP-hardness of the Densest at-Most-k-Subgraph problem that the Q-DISCO hardness reduction starts from, and gives the reduction from DamkS to DkS used in Proposition 2.","marker":"[33]"},{"why":"Proves the ETH-hardness of approximating Densest k-Subgraph that Proposition 3 relies on to rule out almost-polynomial approximation ratios.","marker":"[43]"},{"why":"Provides the strongly-polynomial algorithm for the densest subgraph problem with positive and negative node weights, which Q-Lagrange invokes to solve each Lagrangian relaxation.","marker":"[29]"},{"why":"Supplies the LP relaxation and dual for the plain densest subgraph problem plus the greedy-peeling view, which Q-Peeling generalizes with agreement terms in the loads.","marker":"[13]"},{"why":"Introduces the Heavy and Dense Subgraph Problem with generalized node weights, the closest formulation that Q-DISCO extends by turning average weight into a constraint.","marker":"[21]"},{"why":"Supports the paper's choice of a large-language-model scorer for tweet opinions by showing such models outperform BERT-based alternatives without fine-tuning.","marker":"[64]"}],"fun_headline_variants":["Hard to find: dense groups matching a query opinion","Query-centric densest subgraphs are NP-hard to find","NP-hard dense subgraphs with opinion alignment still solved near-optimally","Q-DISCO: tackling NP-hard query-aligned dense subgraphs","Finding dense opinion-aligned groups is NP-hard; heuristics work"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole method assumes that the dot product between a node's opinion vector and the query vector faithfully captures how much that node agrees with the queried position; if the opinion vectors are noisy, inconsistently scaled, or mixed-stance, a set satisfying $c(S)\\ge\\theta$ may not actually share the query's stance.","fun_headline_variants_meta":{"raw":{"variants":["Hard to find: dense groups matching a query opinion","Query-centric densest subgraphs are NP-hard to find","NP-hard dense subgraphs with opinion alignment still solved near-optimally","Q-DISCO: tackling NP-hard query-aligned dense subgraphs","Finding dense opinion-aligned groups is NP-hard; heuristics work"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000311,"raw_usage":{"total_tokens":1826,"prompt_tokens":1055,"completion_tokens":771,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":671,"completion_tokens_details":{"reasoning_tokens":683}},"tokens_in":671,"tokens_out":771,"duration_ms":6515,"temperature":1.0,"reasoning_tokens":683,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:45:50.079736+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a graph with two planted cliques of equal density: one whose members share a queried stance but have opinion vectors scaled so that their dot products with the query sit just below $\\theta$, and another whose members oppose the stance but have large dot products because of vector magnitude. If Q-DISCO or Q-Peeling returns the opposing clique, the dot-product agreement model is falsified as a measure of true alignment; a corrected variant should recover the shared-stance clique once opinion vectors are normalized.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the NP-hardness of the Densest at-Most-k-Subgraph problem that the Q-DISCO hardness reduction starts from, and gives the reduction from DamkS to DkS used in Proposition 2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves the ETH-hardness of approximating Densest k-Subgraph that Proposition 3 relies on to rule out almost-polynomial approximation ratios."},{"cited_title":"Gleich, and Nate Veldt","cited_arxiv_id":null,"evidence_quote":"Provides the strongly-polynomial algorithm for the densest subgraph problem with positive and negative node weights, which Q-Lagrange invokes to solve each Lagrangian relaxation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the LP relaxation and dual for the plain densest subgraph problem plus the greedy-peeling view, which Q-Peeling generalizes with agreement terms in the loads."},{"cited_title":"Tsourakakis, and Francesco Bonchi","cited_arxiv_id":null,"evidence_quote":"Introduces the Heavy and Dense Subgraph Problem with generalized node weights, the closest formulation that Q-DISCO extends by turning average weight into a constraint."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supports the paper's choice of a large-language-model scorer for tweet opinions by showing such models outperform BERT-based alternatives without fine-tuning."}],"review_version":1}