REVIEW 2 major objections 5 minor 29 references
Dense Subgraph Discovery Meets Strong Triadic Closure
T0 review · 2 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the score $q(U,L;\lambda)=(m_s(U,L)+\lambda m_w(U,L))/|U|$, evaluated over a subgraph $U$ and a strong/weak labeling $L$ satisfying strong triadic closure. The STC rule is encoded through the wedge graph, where a wedge $(x,y,z)$ with both edges labeled strong forces the edge $(x,z)$ to exist, and in the ILP through the constraint $x_{ij}+x_{jk}\le y_j$. The hardness argument is carried by a marginal-ratio lemma (Lemma A.1) that says adding or deleting a vertex set improves the score exactly when the marginal contribution $\Delta(X,Y)$ crosses $q(Y,L)$, together with a construction of $k$ cliques of size $n$ attached to the input graph so that an optimal subgraph must either include a whole clique or none of it. The algorithmic machinery is fractional programming: stc-den is solved by binary search over $\alpha$ using the auxiliary problem stc-den($\alpha$), implemented as an ILP and relaxed to an LP.
What would settle it
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|<n$, and a vertex $c\in C_i\setminus W_i$, and compute $\Delta(U\setminus W_i,U)$ versus $\Delta(U,U\cup\{c\})$ exactly; if the former is not strictly smaller than the latter, the "We can show" step is false and the forcing argument in the hardness proof fails. One could then test whether stc-den for that $\lambda$ admits a polynomial algorithm or a PTAS.
Extended reading notes
Core claim
The paper's central claim is that optimizing $q(U,L;\lambda)=(m_s(U,L)+\lambda m_w(U,L))/|U|$ with an STC-compliant labeling yields a parameterized family whose endpoints are the polynomial densest-subgraph problem ($\lambda=1$) and the NP-hard maximum-clique problem ($\lambda=0$), and that every interior value $0<\lambda<1$ is NP-hard. The hardness proof reduces from MinSTC by attaching $k$ cliques of size $n$ to the input graph and using a marginal-ratio lemma to force each clique to be included wholly or not at all. The paper also provides an exact ILP-based solver and four polynomial-time heuristics, and reports experiments in which the heuristics recover planted dense components and run efficiently on real networks.
Load-bearing premise
The intermediate-$\lambda$ hardness result rests on an unproved inequality: the paper states "We can show" rather than deriving that adding a new clique vertex always increases the marginal score more than removing an incomplete chunk of a clique does, and the reduction from MinSTC collapses if that inequality fails for some graph and clique configuration.
Editorial extensions
If this is right
- At $\lambda=0$, stc-den is exactly maximum clique, so any exact solver for the new problem yields a maximum clique and the problem inherits the $n^{1-\epsilon}$ inapproximability bound unless P=NP.
- At $\lambda=1$, stc-den is exactly the densest subgraph problem, solvable in polynomial time by min-cut based algorithms; the family therefore has one tractable endpoint.
- For rational $\lambda=a/b$, STC-ILP returns a $(1+\epsilon)$-approximation in $O(\log n+\log b)$ ILP rounds and is exact when $\epsilon=2/(bn^3)$, giving a practical exact method on moderate-size graphs.
- STC-LP, STC-Cut, STC-Peel, and Greedy run in polynomial time, $O(nm)$ for Peel and Greedy and $O(mn\log n)$ for Cut, and recover the planted dense component in synthetic experiments for small $\lambda$.
- On real-world datasets STC-ILP achieves the highest scores where it terminates, STC-LP is the strongest scalable alternative in most cases, and the fraction of strong edges in returned subgraphs decreases as $\lambda$ grows.
Reading between the lines
- Because $\lambda=0$ hides maximum clique, the paper's negative results suggest that the real practical value of the problem lies in small-to-moderate $\lambda$, where near-clique structure matters; seeding the heuristics with maximal-clique routines is a natural testable extension the paper does not explore.
- The $1/\lambda$ approximation obtained by labeling all edges weak hints at a possible approximation hierarchy in $\lambda$; a $\lambda$-dependent approximation scheme, or hardness of approximation for fixed $\lambda<1$, would sharpen the picture beyond the paper's claims.
- The weighted variant used in the DBLP case study suggests the same STC-score framework transfers to edge-weighted graphs, but the paper does not analyze hardness for weighted inputs; proving or disproving NP-hardness there is an open test.
- If the unproved inequality in Proposition 4.3 fails, stc-den for $0<\lambda<1$ might be easier than NP-hard, so a direct computational check of that inequality on small random graphs is a cheap way to validate the paper's main hardness claim.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [Appendix A.1, proof of Proposition 4.3] 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.
- [Appendix A.1, proof of Proposition 4.3] 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.
minor comments (5)
- [Throughout] 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 3 and proof of Proposition 5.6] 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.
- [Appendix A.1, proof of Proposition 4.3] 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 6] 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 5.2] The problem stc-relax(α) is used in Proposition 5.4 but is never formally defined; a displayed definition alongside Problem 3 would improve readability.
Circularity Check
No significant circularity: the central reductions are self-contained and the only self-citation is a non-load-bearing related-work pointer; the flagged "We can show" inequality is a proof gap, not a circular step.
full rationale
The derivation chain does not reduce to its own inputs. For lambda=1, the equivalence to densest subgraph follows immediately from the definition q(U,L;lambda)=(ms+lambda*mw)/|U|: with lambda=1 every edge contributes weight 1 and the STC constraints do not restrict the objective, so no special result is imported. For lambda=0, Proposition 4.1 gives an actual proof that an optimal STC-compliant subgraph can be converted to a clique with at least the same score, and the inapproximability result imports only the external Max-Clique hardness of Zuckerman. Proposition 4.3 reduces the external NP-hard problem MinSTC [24] to stc-den with a construction whose parameters are fixed from lambda and n, not fitted to any target. The only load-bearing assertion that is underived is the inequality Delta(U\W_i,U) < Delta(U,U union {c}) in Appendix A.1, introduced by 'We can show'; this is a genuine proof gap that should be filled, but it is not circular: the inequality is a concrete analytic statement about the reduction, not an assumption of the NP-hardness conclusion. The algorithms and experiments likewise contain no fitted-input-called-prediction pattern: lambda is a user parameter, and the heuristics are benchmarked on planted and real data rather than tuned to the reported scores. The only self-citation is in Section 3, 'It has also been extended for multiple graph snapshots [2, 11, 23]'; reference [2] is a related-work pointer and is not used to justify any theorem, so it does not make the argument circular. Overall the paper is self-contained against external benchmarks, and the modest nonzero score reflects only that minor non-load-bearing self-citation.
Assumptions & free parameters
assumptions (4)
- domain assumption STC property is a meaningful model of tie strength, with edges labeled strong or weak subject to the wedge constraint.
- standard math Maximum clique is NP-hard and inapproximable within n^(1-epsilon) unless P=NP, and MinSTC reduces to minimum vertex cover in the wedge graph.
- standard math Dinkelbach fractional programming relation between stc-den(alpha) and stc-den.
- standard math Goldberg's densest subgraph algorithm runs in polynomial time via min-cut.
Cite this review
Pith. "Pith review of Dense Subgraph Discovery Meets Strong Triadic Closure." pith.science (2026). https://pith.science/paper/MGOFYMQZ
@misc{pith2026250201435,
author = {Pith},
title = {Pith review of: Dense Subgraph Discovery Meets Strong Triadic Closure},
year = {2026},
howpublished = {\url{https://pith.science/paper/MGOFYMQZ}},
note = {Machine review of arXiv:2502.01435}
}
abstract
Finding dense subgraphs is a core problem with numerous graph mining applications such as community detection in social networks and anomaly detection. However, in many real-world networks connections are not equal. One way to label edges as either strong or weak is to use strong triadic closure~(STC). Here, if one node connects strongly with two other nodes, then those two nodes should be connected at least with a weak edge. STC-labelings are not unique and finding the maximum number of strong edges is NP-hard. In this paper, we apply STC to dense subgraph discovery. More formally, our score for a given subgraph is the ratio between the sum of the number of strong edges and weak edges, weighted by a user parameter $\lambda$, and the number of nodes of the subgraph. Our goal is to find a subgraph and an STC-labeling maximizing the score. We show that for $\lambda = 1$, our problem is equivalent to finding the densest subgraph, while for $\lambda = 0$, our problem is equivalent to finding the largest clique, making our problem NP-hard. We propose an exact algorithm based on integer linear programming and four practical polynomial-time heuristics. We present an extensive experimental study that shows that our algorithms can find the ground truth in synthetic datasets and run efficiently in real-world datasets.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
Florian Adriaens, Tijl De Bie, Aristides Gionis, Jefrey Lijffijt, Antonis Matakos, and Polina Rozenshtein. 2020. Relaxing the strong triadic closure problem for edge strength inference. Data Mining and Knowledge Discovery 34 (2020), 611–651
work page 2020
-
[2]
Chamalee Wickrama Arachchi and Nikolaj Tatti. 2023. Jaccard-constrained dense subgraph discovery. arXiv preprint arXiv:2308.15936 (2023)
work page Pith review arXiv 2023
-
[3]
Yuichi Asahiro, Kazuo Iwama, Hisao Tamaki, and Takeshi Tokuyama. 2000. Greed- ily finding a dense subgraph. Journal of Algorithms 34, 2 (2000), 203–221
work page 2000
-
[4]
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. 2015. Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing . 173–182
work page 2015
-
[5]
Moses Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In APPROX. 84–95
work page 2000
-
[6]
Kenneth L Clarkson. 1983. A modification of the greedy algorithm for vertex cover. Inform. Process. Lett. 16, 1 (1983), 23–25
work page 1983
-
[7]
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press
2022
-
[8]
Werner Dinkelbach. 1967. On nonlinear fractional programming. Management science 13, 7 (1967), 492–498
work page 1967
Show all 29 references
-
[9]
Andrew V Goldberg. 1984. Finding a maximum density subgraph. (1984)
1984
-
[10]
Zoran Ivković and Errol L Lloyd. 1993. Fully dynamic maintenance of vertex cover. In International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 99–111
1993
-
[11]
Vinay Jethava and Niko Beerenwinkel. 2015. Finding dense subgraphs in rela- tional graphs. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. 641–654
2015
-
[12]
Narendra Karmarkar. 1984. A new polynomial-time algorithm for linear pro- gramming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing. 302–311
1984
-
[13]
Samir Khuller and Barna Saha. 2009. On finding dense subgraphs. InInternational colloquium on automata, languages, and programming . Springer, 597–608
2009
-
[14]
Athanasios L Konstantinidis, Stavros D Nikolopoulos, and Charis Papadopoulos
-
[15]
Athanasios L Konstantinidis and Charis Papadopoulos. 2020. Maximizing the strong triadic closure in split graphs and proper interval graphs. Discrete Applied Mathematics 285 (2020), 79–95
2020
-
[16]
Antonis Matakos and Aristides Gionis. 2022. Strengthening ties towards a highly- connected world. Data mining and knowledge discovery 36, 1 (2022), 448–476
2022
-
[17]
Lutz Oettershagen, Athanasios L Konstantinidis, and Giuseppe F Italiano. 2022. Inferring Tie Strength in Temporal Networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases . 69–85
2022
-
[18]
James B Orlin. 2013. Max flows in O (nm) time, or better. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing . 765–774
2013
-
[19]
Victor Reis and Thomas Rothvoss. 2023. The subspace flatness conjecture and faster integer programming. arXiv preprint arXiv:2303.14605 (2023)
2023
-
[20]
Rossi and Nesreen K
Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Reposi- tory with Interactive Graph Analytics and Visualization. In AAAI. https: //networkrepository.com
2015
-
[21]
Polina Rozenshtein, Nikolaj Tatti, and Aristides Gionis. 2017. Inferring the strength of social ties: a community-driven approach. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . 1017–1025
2017
-
[22]
Alexander Schrijver. 1998. Theory of Linear Integer Programming . John Wiley & Sons
1998
-
[23]
Konstantinos Semertzidis, Evaggelia Pitoura, Evimaria Terzi, and Panayiotis Tsaparas. 2019. Finding lasting dense subgraphs. Data mining and knowledge discovery 33, 5 (2019), 1417–1445
2019
-
[24]
Stavros Sintos and Panayiotis Tsaparas. 2014. Using strong triadic closure to characterize ties in social networks. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining . 1466–1475
2014
-
[25]
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. Arnet- miner: extraction and mining of academic social networks. In KDD. 990–998
2008
-
[26]
Charalampos Tsourakakis. 2015. The k-clique densest subgraph problem. In WWW. 1122–1132
2015
-
[27]
Jan van den Brand. 2020. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM, 259–278
2020
-
[28]
David Zuckerman. 2006. Linear degree extractors and the inapproximability of max clique and chromatic number. InProceedings of the thirty-eighth annual ACM symposium on Theory of computing . 681–690. A Appendix A.1 Computational complexity proofs Proof of Proposition 4.1. We w...
2006
-
[2018]
Theoretical Computer Science 740 (2018), 76–84
Strong triadic closure in cographs and graphs of low maximum degree. Theoretical Computer Science 740 (2018), 76–84
2018
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.