Pith. sign in

REVIEW 3 major objections 4 minor 23 references

Node ranking in labeled networks

T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2502.01408 v1 pith:BCZJZQWS submitted 2025-02-03 cs.DS

Chamalee Wickrama Arachchi , Nikolaj Tatti This is my paper · ORCID
classification cs.DS MSC 68Q1768R1005C85
keywords labeltreeagonyscorenoderankingdirectedweightedgraphsNP-hardnessdivide-and-conquerheuristicexplainablehierarchylabels
topics P versus NP
open problems P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 3.4, Algorithm 3 (lines 13–14 and 24–25)] 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.
  2. [Section 3.1 / Section 7, Proposition 3.2] 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.
  3. [Section 3.4, initialization of counters] 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).
minor comments (4)
  1. [Algorithm 1] 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.
  2. [Proposition 3.4] 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.
  3. [Section 3.3] 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.
  4. [Table 2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation chain is self-contained and the central claims are not constructed from their inputs.

full rationale

The paper's central claims are derived independently of its conclusions: NP-hardness is proved in Section 7 by explicit self-contained reductions from k-Cover, the inapproximability statement follows from the zero-cost decision version, and the experimental claims compare Greedy against the label-free Agony baseline and, for single-label datasets, against an exact reduction to the polynomial-time label-free problem. The heuristic relies on Proposition 3.3, which is quoted from Tatti [19] and on the counter-update scheme in Algorithm 3, both attributed to prior published work by the second author; however, this is a parameter-free result with stated assumptions that do not include the L-agony problem, so the self-citation provides independent mathematical support rather than a circular reduction. Section 3.4 omits the proof that Algorithm 3 maintains the counters defined in Eqs. 3.1-3.4, and the pseudocode may contain a sign error in the d-counter updates for cross edges, but an omitted or even incorrect proof is a correctness or rigor concern, not a circularity concern, because the claimed result does not reduce by definition to the paper's inputs. No fitted parameter is renamed as a prediction, and no known result is merely relabeled. Therefore no load-bearing circular step is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The central method introduces one new formal object, the label tree, and relies on the modeling assumption that real hierarchies can be expressed by single-label binary splits. The objective (agony) and the counter-based speedups are imported from prior work. No numeric constants are fitted to data in the method itself; the synthetic data parameters are inputs to experiments, not free parameters of the algorithm.

assumptions (4)
  • domain assumption The penalty function p(d) = max(0, d+1) is an appropriate quality measure for hierarchies.
    Agony is imported from prior work (Gupte et al., Tatti) and treated as the objective; no justification is given for why this penalty shape is right for labeled networks.
  • domain assumption Each non-leaf of the label tree carries exactly one label, and traversal depends on a single label per node.
    This restriction is central to Definition 2.2; it limits expressiveness of the hypothesis space and is not defended in the paper beyond the goal of explainability.
  • domain assumption The greedy local split rule, choosing the label that most reduces agony at each step, leads to globally good trees.
    Since the problem is NP-hard, the paper resorts to heuristics; no approximation guarantee is proven for the greedy algorithm, only empirical validation.
  • standard math The NP-hardness reductions from k-Cover are valid.
    The constructions are given in Section 7 and appear sound aside from typos; they rely on standard reduction arguments.
invented entities (1)
  • Label tree independent evidence
    purpose: A binary decision tree whose internal nodes are labels and whose leaves are ranks; it defines the hypothesis space for explainable rankings.
    The label tree is a formal modeling construct, not a physical entity; it is evaluated empirically on real and synthetic datasets, giving it a falsifiable handle outside the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Node ranking in labeled networks." pith.science (2026). https://pith.science/paper/BCZJZQWS

@misc{pith2026250201408,
  author       = {Pith},
  title        = {Pith review of: Node ranking in labeled networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BCZJZQWS}},
  note         = {Machine review of arXiv:2502.01408}
}
abstract

The entities in directed networks arising from real-world interactions are often naturally organized under some hierarchical structure. Given a directed, weighted, graph with edges and node labels, we introduce ranking problem where the obtained hierarchy should be described using node labels. Such method has the advantage to not only rank the nodes but also provide an explanation for such ranking. To this end, we define a binary tree called label tree, where each leaf represents a rank and each non-leaf contains a single label, which is then used to partition, and consequently, rank the nodes in the input graph. We measure the quality of trees using agony score, a penalty score that penalizes the edges from higher ranks to lower ranks based on the severity of the violation. We show that the problem is NP-hard, and even inapproximable if we limit the size of the label tree. Therefore, we resort to heuristics, and design a divide-and-conquer algorithm which runs in $\bigO{(n + m) \log n + \ell R}$, where $R$ is the number of node-label pairs in the given graph, $\ell$ is the number of nodes in the resulting label tree, and $n$ and $m$ denote the number of nodes and edges respectively. We also report an experimental study that shows that our algorithm can be applied to large networks, that it can find ground truth in synthetic datasets, and can produce explainable hierarchies in real-world datasets.

Figures

Figures reproduced from arXiv: 2502.01408 by the authors.

Figure 1
Figure 1. Graph G, label tree T , and the resulting hierarchy. The agony q(G, T ) = 5. a non-leaf node in T with a label t and a boolean value c. If c is true and, then a node v with t ∈ L(v) traverses to the left branch, otherwise to the right. If c is false, the branch roles are reversed. The following notations will be useful in the next section. Given a graph G, a label tree T , and a node α in T , we write V (α) to be th… view at source ↗
Figure 4
Figure 4. Agony score (q(T )) as a function of the con￾straint k for the cases of several false label probabil￾ities (θ) as shown in the legend. This experiment is done for |V | = 4 000, |E| ≈ 7 000, h = 15, µ = 0.05, and η = 0.9 using Greedy [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 3
Figure 3. Kendall’s τ coefficient as a function of η for the cases of several noise label probabilities (µ) shown in the legend. This experiment is done for |V | = 4 000, |E| = 7 000, θ = 0.15, and h = 10 using Greedy. we see that Kendall’s τ gradually increases when the percentage of forward edges increases. The coefficient significantly increases nearly at the 50% percentage, from negative to positive, due to the fact that … view at source ↗
Figures from the paper (6 more)
Figure 5
Figure 5. Figure 5: Discovered label trees for Physics (above) and DBLP (below) datasets. Solid lines indicate the branch for the nodes with the corresponding label. The label tree obtained for Physics-citation dataset is given in the top of [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 7
Figure 7. Figure 7: Discovered label tree obtained from noiseless [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 6
Figure 6. Figure 6: Ground truth label tree. Real-world data: Let us look at the trees ob￾tained Patent-citation dataset together with their la￾bels. This tree shows 7 levels. The label for the very first partition has become a patent class ** Classification Undetermined **. Then, the tre…
Figure 12
Figure 12. Figure 12: Label tree for EIES dataset using Algorithm 1. Solid lines indicate the branch for the nodes with the corresponding label. Agents Machine Learning Rank 3 Rank 1 Rank 2 [PITH_FULL_IMAGE:figures/full_fig_p012_12.png]
Figure 10
Figure 10. Figure 10: Label tree for Flickr dataset using Algorithm 1. Solid lines indicate the branch for the nodes with the corresponding label. Case based Theory Rank 3 Rank 1 Rank 2 [PITH_FULL_IMAGE:figures/full_fig_p012_10.png]
Figure 11
Figure 11. Figure 11: Label tree for Cora dataset using Algorithm 1. Solid lines indicate the branch for the nodes with the corresponding label. hierarchy levels in total. Based on the contacts between students, it is evident that mathematics and physics class students are highly sorted th…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Z. Bai, S. Ravi, and I. Davidson. Towards descrip- tion of block model on graph. In ECMLPKDD, pages 37–53, 2020

    work page 2020

  2. [2]

    Bothorel, J

    C. Bothorel, J. D. Cruz, M. Magnani, and B. Mi- cenkova. Clustering attributed graphs: models, measures and methods. Network Science, 3(3):408– 444, 2015

    work page 2015

  3. [3]

    Dinur and S

    I. Dinur and S. Safra. On the hardness of approx- imating minimum vertex cover. Annals of mathe- matics, pages 439–485, 2005

    work page 2005

  4. [4]

    A. E. Elo. The rating of chessplayers, past and present. Arco Pub., New York, 1978

    work page 1978

  5. [5]

    G. Even, B. Schieber, M. Sudan, et al. Approxi- mating minimum feedback sets and multicuts in di- rected graphs. Algorithmica, 20(2):151–174, 1998

    work page 1998

  6. [6]

    Falih, N

    I. Falih, N. Grozavu, R. Kanawati, and Y. Bennani. Community detection in attributed network. In WWW, pages 1299–1306, 2018

    work page 2018

  7. [7]

    Galbrun, A

    E. Galbrun, A. Gionis, and N. Tatti. Overlapping community detection in labeled graphs. DMKD, 28 (5):1586–1610, 2014

    work page 2014

  8. [8]

    Gupte, P

    M. Gupte, P. Shankar, J. Li, S. Muthukrishnan, and L. Iftode. Finding hierarchy in directed online social networks. In WWW, pages 557–566, 2011

    work page 2011

Show all 23 references
  1. [9]

    K. A. Jameson, M. C. Appleby, and L. C. Freeman. Finding an appropriate order for a hierarchy based on probabilistic dominance. Animal behaviour , 57 (5):991–998, 1999

    1999

  2. [10]

    J. M. Kleinberg. Authoritative sources in a hyper- linked environment. JACM, 46(5):604–632, 1999

    1999

  3. [11]

    J. Lu, J. Chen, and C. Zhang. Helsinki Multi-Model Data Repository. https://www.helsinki.fi/en/researchgroups/unified-d ata 2018

    2018

  4. [12]

    A. S. Maiya and T. Y. Berger-Wolf. Inferring the maximum likelihood hierarchy in social networks. In CSE, volume 4, pages 245–250, 2009

    2009

  5. [13]

    Memon, H

    N. Memon, H. L. Larsen, D. L. Hicks, and N. Harki- olakis. Retracted: detecting hidden hierarchy in terrorist networks: some case studies. In ISI, pages 477–489, 2008

    2008

  6. [14]

    Neumann, J

    S. Neumann, J. Ritter, and K. Budhathoki. Rank- ing the teams in european football leagues with agony. In MLSA@ECMLPKDD, 2018

    2018

  7. [15]

    S. Pool, F. Bonchi, and M. v. Leeuwen. Description-driven community detection. TIST, 5 (2):1–28, 2014

    2014

  8. [16]

    R. A. Rossi and N. K. Ahmed. The network data repository with interactive graph analyt- ics and visualization. In AAAI, 2015. URL https://networkrepository.com

    2015

  9. [17]

    R. Rowe, G. Creamer, S. Hershkop, and S. J. Stolfo. Automated social hierarchy detection through email network analysis. In WebKDD/SNA-KDD, pages 109–117, 2007

    2007

  10. [18]

    J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su. Arnetminer: extraction and mining of academic social networks. In KDD, pages 990–998, 2008

    2008

  11. [19]

    N. Tatti. Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks. DMKD, 31(3):702–738, 2017. 7 Proofs Proof. [Proposition 3.1] We will prove the hardness from k-Cover, a problem where we are given a family of subsetsC of a universe U and we asked...

    2017

  12. [20]

    Moreover, cαj≥ 2cαj+1

    We have shown that we can safely assume that αj+1 is a descendant of αj+1. Moreover, cαj≥ 2cαj+1. Since cα1≤ m + n, there can be at most O(log m)⊆O (log n) nodes. The argument for ∑ α ivα∈O (log n) is similar. Copyright © 2023 by SIAM Unauthorized reproduction of this article ...

    2023

  13. [21]

    Case based Theory Rank 3 Rank 1 Rank 2 Figure 11: Label tree for Cora dataset using Algorithm

    Solid lines indicate the branch for the nodes with the corresponding label. Case based Theory Rank 3 Rank 1 Rank 2 Figure 11: Label tree for Cora dataset using Algorithm

  14. [22]

    hierarchy levels in total

    Solid lines indicate the branch for the nodes with the corresponding label. hierarchy levels in total. Based on the contacts between students, it is evident that mathematics and physics class students are highly sorted than biology class students. Citation Index 10-20 Rank 1 C...

  15. [23]

    Agents Machine Learning Rank 3 Rank 1 Rank 2 Figure 13: Label tree for Citeseer dataset using Algo- rithm 1

    Solid lines indicate the branch for the nodes with the corresponding label. Agents Machine Learning Rank 3 Rank 1 Rank 2 Figure 13: Label tree for Citeseer dataset using Algo- rithm 1. Solid lines indicate the branch for the nodes with the corresponding label. Biology-1 Rank 1...

    2023

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.