{"id":"7aeb7840-da55-4691-bf8b-8cd7d53cf801","arxiv_id":"2502.01408","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new NP-hard problem, L-agony, ranks nodes via a binary label tree that explains the hierarchy, and a greedy divide-and-conquer heuristic is shown to recover ground-truth rankings in synthetic and real networks.","lead":"This paper defines a new problem: ranking nodes in a labeled, directed network using a decision tree whose splits are node labels, with the quality measured by the agony score. It proves the problem is NP-hard and inapproximable in the constrained case, and proposes a fast greedy heuristic that finds explainable hierarchies in large real-world networks.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 3's d(x) update for N→P cross edges has a sign error, corrupting gain computations after the first split.","rationale":"The reader's weakest assumption is that Section 3.4 leaves the correctness of Algorithm 3 unproven. I agree that this is a critical gap, but I go further: the pseudocode is not merely unproven, it is demonstrably wrong as written. The sign error in the d(x) update for N→P cross edges is a specific, checkable inconsistency, not just a missing proof. If the code in the linked repository implements the same rule, then the greedy algorithm's gain computations are corrupted after the first split, which would invalidate the experimental results and the central claim that the heuristic finds hierarchies with Kendall's tau above 0.9. The NP-hardness and inapproximability results remain plausible and are independent of the counter machinery, so the theoretical contribution may survive a correction. My recommendation is CONDITIONAL, matching the reader's verdict but with a sharper condition: the authors must fix the sign error (or confirm that the implementation uses the correct update) and provide the missing derivation for Algorithm 3. I do not see an additional load-bearing concern beyond this: the gain formula itself checks out algebraically, the complexity argument in Proposition 3.4 is plausible, and the experiments, though lacking error bars, are secondary to the algorithmic bug. The concern is internally inconsistent with the paper's own definitions, not merely outside current consensus, so it is a correctness risk rather than a novelty dispute.","tokens_in":15001,"tokens_out":17462,"duration_ms":155816,"concrete_test":"Trace Algorithm 3 on a minimal instance: let the initial root leaf α contain exactly two nodes u and v, with a single directed edge u→v of weight 1 and no other edges. Choose a split with N={u}, P={v}, so β={u}, γ={v}. Before the split, from Eq. 3.4, d(u)= -1 (one outgoing edge to V(α)) and d(v)= +1 (one incoming edge from V(α)). After executing Algorithm 3 lines 13–14 exactly as written, the printed code gives d(u)= -2 and d(v)= 0. But the definitions for the new tree require d(u)=0 (no edges from W_β∪V(β) to u, no edges from u to U_β∪V(β)) and d(v)=0. The discrepancy in d(u) confirms the sign error. A second, integrative check: on a small random labeled graph, run one split with Algorithm 3, then recompute the gain of a second split using the maintained counters versus a brute-force q(G,T′)-q(G,T) evaluation. If the counters are maintained as in the paper, the two gains will disagree.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's main algorithmic contribution is the greedy split procedure whose gain formula (Proposition 3.3, Eqs. 3.5–3.6) relies on the counters b, ib, ob, and d. Section 3.4 states that 'a straightforward calculation, which we will omit' shows Algorithm 3 maintains these counters correctly, but the pseudocode as written contains a concrete sign error in the d-counter updates. In both branches of Algorithm 3 (lines 13–14 and 24–25), for each edge e=(x,z) with x∈N and z∈P, the algorithm does 'decrease d(x), d(z) by w(e)'. After splitting α into β (containing N, rank i) and γ (containing P, rank i+1), the edge x→z goes from being an internal edge at equal rank to a forward edge from rank i to rank i+1. In the new tree, for x∈β, this edge is no longer an outgoing edge from x to U_β∪V(β), because P is now in W_β, so the contribution that was subtracted from d(x) in Eq. 3.4 must be added back: d(x) should increase by w(e). For z∈γ, the edge is no longer an incoming edge from W_γ∪V(γ), because N is now in U_γ, so d(z) should decrease by w(e). Thus the simultaneous decrease is correct for d(z) but wrong for d(x). Because d-values feed directly into every subsequent gain computation (Eqs. 3.5–3.6), this error propagates through all later splits, making the gains and the greedy tree incorrect. The omission of the counter-maintenance proof in Section 3.4 is therefore not a harmless gap: as written, the update rule is internally inconsistent with the definitions. This is the most load-bearing concern because it undermines the core heuristic and the experimental claims that 'for all these experiments Kendall's tau exceeds 0.9'; if the published pseudocode is followed, the algorithm would not compute the advertised gains. The NP-hardness reductions (Propositions 3.1 and 3.2) do not depend on this counter machinery and appear structurally sound, so the theoretical hardness claim is not similarly threatened.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines the L-agony problem: given a weighted directed graph with node labels, find a binary decision tree (a \"label tree\") that partitions the vertices into ordered ranks so as to minimize the agony score, optionally with a cardinality constraint on the number of leaves. The authors claim that the problem is NP-hard (Proposition 3.1) and remains NP-hard without the cardinality constraint (Proposition 3.2), that the constrained version is inapproximable (Corollary 3.1), and that a greedy divide-and-conquer heuristic runs in O((n+m) log n + ℓR) time. They report synthetic experiments in which the heuristic recovers ground-truth rankings with Kendall's tau above 0.9 and real-world experiments that yield interpretable label trees.","tokens_in":15350,"tokens_out":27935,"duration_ms":244474,"significance":"The problem studied is natural and the paper draws attention to an interesting contrast: unlabeled agony minimization is polynomial-time solvable, while the labeled-tree variant is NP-hard. If the algorithmic issues are repaired, the proposed heuristic could be a useful practical tool for explainable ranking in large networks. The paper also benefits from a formal complexity analysis, a stated running-time bound, and experiments on both synthetic and real-world data, with a code link provided. However, the central algorithmic claim depends on a counter-maintenance routine whose pseudocode appears to be incorrect, so the current version cannot be accepted as a reliable description of the proposed method.","major_comments":[{"comment":"For each edge e=(x,z) with x∈N and z∈P, the pseudocode performs \"decrease d(x), d(z) by w(e)\". After the split, β=N has rank i and γ=P has rank i+1, so the edge x→z is forward. According to Eq. (3.4), in the old tree this edge contributed -w(e) to d(x) and +w(e) to d(z). In the new tree, for x∈β the edge is no longer an outgoing edge to U_β∪V(β), so d(x) should increase by w(e); for z∈γ the edge is no longer an incoming edge from W_γ∪V(γ), so d(z) should decrease by w(e). The simultaneous decrease of both values is therefore wrong for d(x). Since every later split gain in Proposition 3.3 depends on d, this error invalidates the greedy choices after the first split. The omitted calculation in Section 3.4 cannot be correct; the update rule must be fixed and proved.","section":"Section 3.4, Algorithm 3 (lines 13–14 and 24–25)"},{"comment":"The reduction from k-Cover is plausible, but the write-up needs repair. The proof fixes a universe of n items and a family of m subsets, but then writes \"the items in U = u1,...,um\"; it should be u1,...,un. Also, \"L(w)=∅\" should presumably be L(x)=∅. More substantively, in the converse direction the proof counts \"the o sets corresponding to the labels occurring in the path to x\" and lets z1,...,zo be the corresponding vertices in S. If a label occurs more than once on that path, the same vertex si would be counted multiple times, and the inequality m-o+Σ(o-i+2) is not justified. The proof should either argue that repeated labels on a path can be eliminated without increasing q, or count distinct labels. The reduction is likely sound, but the proof as written is not complete.","section":"Section 3.1 / Section 7, Proposition 3.2"},{"comment":"The initialization of the counters for the root leaf is not specified. For the root, the sets U and W are empty, so b, ib, and ob are zero, but d(v) must be initialized to the total weight of incoming edges inside E(V,V) minus the total weight of outgoing edges inside E(V,V); otherwise the first call to Test is undefined. The paper should state this explicitly. In addition, the claim that the counter update is a straightforward omitted calculation starting from Eqs. 3.1–3.4 is not sufficient here, because the update rule in Algorithm 3 is not consistent with those equations (see Major Comment 1).","section":"Section 3.4, initialization of counters"}],"minor_comments":[{"comment":"In Algorithm 1, the variable ∆ is described as the \"reduction in score\", but Test returns q(T')−q(T), which is negative when the split improves the score. The condition \"if ∆ < 0\" is correct for the latter interpretation; please align the terminology and the comment.","section":"Algorithm 1"},{"comment":"The proof of the running time states that Test(α,t) costs O(|V(α,t)|) and the candidate search for α costs O(R), but it does not explicitly sum this over the O(ℓ) recursive calls; the final O(ℓR) term should be derived by summing over all internal nodes of the label tree.","section":"Proposition 3.4"},{"comment":"The symbol U is used both for the label universe and for the set of vertices with smaller rank; please use a different symbol (e.g., L for the label universe) to avoid confusion.","section":"Section 3.3"},{"comment":"In several synthetic rows qbase is much smaller than qtrue (e.g., Syn-2: 648 vs. 4,160), and the text only states that qdis is closer to qtrue. A brief explanation of why the label-free baseline achieves a much lower agony score (many more ranks) would help the reader interpret the comparison correctly.","section":"Table 2"}],"recommendation":"major_revision","confidential_remarks":"The paper draws heavily on [19], which is co-authored by the second author. This is not disqualifying, but the authors should make the provenance of Proposition 3.3 and the counter machinery explicit and confirm that the labeled adaptation is correct. Given the sign error in Algorithm 3, I recommend a major revision; the experimental sections should be checked against the corrected implementation, and the code link should be verified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear X,\n\nQuick take: the paper defines a genuinely new problem—ranking nodes with an explainable label tree while minimizing agony—and proves it NP-hard in two regimes. The k-Cover reductions look structurally sound, though sketched loosely. This is a contribution worth citing even if the heuristic has problems.\n\nThe greedy divide-and-conquer algorithm is where I have serious reservations. Section 3.4 omits the proof that Algorithm 3 maintains counters, calling it 'a straightforward calculation.' That would be fine if the pseudocode were obviously right. It is not. Consider an edge x→z with x in N and z in P during a split of α into β (rank i) and γ (rank i+1). Under the definition of d in Eq. 3.4, d(x) should increase by w(e): the edge is no longer an outgoing edge from x to V(α) but now goes to a higher rank, so the negative term in d(x) must be removed. Conversely, d(z) should decrease: the edge is no longer an incoming edge from V(α) but an incoming edge from a lower rank, so the positive term in d(z) must be dropped. Algorithm 3 decreases both d(x) and d(z). That sign error affects every gain computed after the first split (Eqs. 3.5–3.6), so the published algorithm would not make the greedy choices described. I cannot tell whether the experiments used the correct updates; the code repository is linked, but the paper itself is not reproducible as written. The root-leaf counter initialization is also unspecified, and the 'if Δ < 0' condition in Algorithm 1 is easy to misread because 'reduction' is never defined.\n\nThe hardness part stands independent of the counters. The experimental section has useful sanity checks: the single-label reduction to a label-free graph lets them compare against an exact Agony solver, and the discovered scores are close. The synthetic results are strong but come without error bars or variation across random seeds.\n\nWho is this for: people working on hierarchy discovery in labeled networks. It deserves peer review, but with the expectation of major revision—correct the d update, supply the counter-maintenance proof, or release tested code. I would not use the current pseudocode as a reference implementation.","headline":"Novel NP-hard ranking problem with a promising greedy idea, but the counter update in Algorithm 3 has a sign error that makes the published pseudocode incorrect.","tokens_in":15957,"tokens_out":9260,"would_cite":true,"duration_ms":81616,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68R10","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adding node labels to hierarchy ranking makes exact optimization NP-hard and bounded-leaf versions inapproximable, so the paper turns to a greedy label-tree heuristic that recovers true rankings in experiments.","keywords":["label tree","agony score","node ranking","directed weighted graphs","NP-hardness","divide-and-conquer heuristic","explainable hierarchy","node labels"],"falsifier":"Implement Algorithm 3 exactly as written on a small labeled graph, even a few dozen vertices, and after each split recompute $b$, $ib$, $ob$, and $d$ directly from Eqs. (3.1)--(3.4) over the current leaf sets. If any counter differs, the omitted calculation in Section 3.4 is wrong; then the gain scores from Proposition 3.3 are unreliable, and either the split decisions or the claimed running time would collapse.","tokens_in":14803,"feed_emoji":"🌳","tokens_out":13922,"duration_ms":113714,"temperature":0.7,"pith_summary":"The paper introduces the L-agony problem: given a directed, weighted graph whose vertices carry labels, find a binary decision tree called a label tree whose leaves are ranks and whose internal nodes test labels, minimizing the agony score $q(G,T)$, the weighted penalty for edges pointing from higher to lower ranks. Plain rank minimization under agony can be solved in polynomial time, but this label-constrained version is shown NP-hard, and even inapproximable when the number of leaves is bounded. The authors therefore design a greedy divide-and-conquer heuristic, running in $O((n+m)\\log n + \\ell R)$, that reuses counter bookkeeping from earlier work to evaluate splits without rescanning all edges. Experiments on synthetic planted hierarchies report the rank-correlation measure Kendall's tau above 0.9 in every tested configuration, while real-world citation and contact networks yield short label trees whose splits are human-readable.","feed_headline":"Label-based ranking is NP-hard; greedy tree recovers true ranks","feed_subtitle":"Even though optimizing label-tree ranks is NP-hard, a greedy heuristic finds near-true rankings quickly.","key_machinery":"The load-bearing object is the label tree: an ordered binary tree whose leaves are ranks, left to right, and whose internal nodes each carry one label and a Boolean deciding whether having that label sends a vertex left or right. The score being optimized is agony, $q(G,T)=\\sum_{(u,v)\\in E} w(e)\\max(0, r(u)-r(v)+1)$, which penalizes backward edges by how many rank levels they climb. To make greedy splits fast, the algorithm maintains four counters per leaf and per vertex---$b(\\alpha)$, $ib(\\alpha)$, $ob(\\alpha)$, and $d(v)$---defined in Eqs. (3.1)--(3.4), and uses Proposition 3.3, an identity inherited from earlier work, to express the score change of a split as $b(\\alpha)+ib(\\alpha)-\\sum_{y\\in Y_2} d(y)$ or the symmetric form. That identity is what lets a candidate label be tested in time proportional to the number of vertices carrying that label rather than the number of edges.","core_discovery":"The paper's central claim is a hardness boundary plus a practical workaround. Deciding whether there exists a label tree with zero agony is NP-complete via a reduction from the set-cover decision problem k-Cover, which immediately rules out any approximation algorithm for L-agony unless P=NP; the problem remains NP-hard even when the cardinality bound $k$ is removed. The constructive half is a greedy algorithm that starts from a single leaf, repeatedly tests each available label as a splitting test using the gain identity (3.5)--(3.6), and recurses on the two children. With counters maintained as in Algorithm 3, the authors argue the total time is $O((n+m)\\log n + \\ell R)$, where $R$ is the number of vertex--label pairs. In synthetic experiments the discovered rankings match planted ranks with Kendall's tau above 0.9 and recover the correct number of ranks, and on real datasets the returned trees are small enough to inspect.","pith_inferences":["Beyond the paper: because both hardness reductions start from k-Cover, the boundary likely persists under restrictions such as a small label universe; a natural follow-up is to test whether bounded-depth label trees or hierarchical label taxonomies become tractable.","Beyond the paper: the omitted counter-maintenance proof in Section 3.4 is directly checkable by implementation; a small test comparing maintained counters to recomputation after each split would settle whether the running-time and gain claims hold in code.","Beyond the paper: the label-tree idea transfers to other penalty functions, such as the constant backward-edge penalty underlying feedback arc set, but the hardness and near-linear-time guarantees would have to be re-proven for each new score.","Beyond the paper: the synthetic results suggest sensitivity is dominated by false labels rather than random extra labels, so a useful stress test is to make the false labels correlated with the true hierarchy instead of uniformly random."],"forward_implications":["Exact L-agony has no polynomial-time algorithm unless P=NP, and no bounded-leaf variant has any approximation guarantee unless P=NP, so heuristic search is the only general route.","A produced label tree doubles as an explanation: each rank is reached by a short sequence of label tests, so a practitioner can see why a node is ranked where it is.","On synthetic data with planted ranks, the heuristic recovers the correct number of ranks and a ranking with Kendall's tau above 0.9, even when 10% of nodes carry false labels.","The method's running time scales to graphs with hundreds of thousands of edges in tens of minutes, making explainable hierarchy mining feasible on real datasets.","When a limit $k$ on the number of ranks is imposed, the greedy tree can be pruned to the best $k$-leaf subtree by dynamic programming in $O(n k^2)$ time."],"supporting_citations":[{"why":"Defines agony as a backward-edge penalty and proves that minimizing it over plain ranks is polynomial-time, the baseline the paper's hardness result contrasts with.","marker":"[8]"},{"why":"Supplies the divide-and-conquer counter machinery and the split-gain identity that Greedy and its running-time analysis reuse, and provides the Agony baseline used in experiments.","marker":"[19]"},{"why":"Provides the Cora and Cite-seer network datasets used to test the heuristic and to compare against exact single-label ranking.","marker":"[16]"},{"why":"Provides the DBLP citation network and title-derived labels used in the real-world hierarchy evaluation.","marker":"[18]"},{"why":"Provides the patent-citation dataset with class, category, and subcategory labels used in the case-study trees.","marker":"[11]"}],"fun_headline_variants":["NP-hard label ranking by tree; greedy heuristic works fast","Label-tree optimization NP-hard; heuristic yields explainable ranks","Greedy algorithm recovers true ranks despite NP-hard label-tree problem","Explainable ranking from labels: NP-hard but fast heuristic succeeds","Hardness proof for labeled ranking, then near-linear heuristic recovers ranks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes, without giving the calculation, that Algorithm 3 updates the counters $b$, $ib$, $ob$, and $d$ exactly as their definitions require; the greedy gain scores and the $O((n+m)\\log n + \\ell R)$ running time are only valid if that update is correct.","fun_headline_variants_meta":{"raw":{"variants":["NP-hard label ranking by tree; greedy heuristic works fast","Label-tree optimization NP-hard; heuristic yields explainable ranks","Greedy algorithm recovers true ranks despite NP-hard label-tree problem","Explainable ranking from labels: NP-hard but fast heuristic succeeds","Hardness proof for labeled ranking, then near-linear heuristic recovers ranks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000209,"raw_usage":{"total_tokens":1433,"prompt_tokens":996,"completion_tokens":437,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":349}},"tokens_in":612,"tokens_out":437,"duration_ms":3782,"temperature":1.0,"reasoning_tokens":349,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T15:25:51.454950+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement Algorithm 3 exactly as written on a small labeled graph, even a few dozen vertices, and after each split recompute $b$, $ib$, $ob$, and $d$ directly from Eqs. (3.1)--(3.4) over the current leaf sets. If any counter differs, the omitted calculation in Section 3.4 is wrong; then the gain scores from Proposition 3.3 are unreliable, and either the split decisions or the claimed running time would collapse.","supporting_citations":[{"cited_title":"Gupte, P","cited_arxiv_id":null,"evidence_quote":"Defines agony as a backward-edge penalty and proves that minimizing it over plain ranks is polynomial-time, the baseline the paper's hardness result contrasts with."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the divide-and-conquer counter machinery and the split-gain identity that Greedy and its running-time analysis reuse, and provides the Agony baseline used in experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Cora and Cite-seer network datasets used to test the heuristic and to compare against exact single-label ranking."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the DBLP citation network and title-derived labels used in the real-world hierarchy evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the patent-citation dataset with class, category, and subcategory labels used in the case-study trees."}],"review_version":1}