REVIEW 4 major objections 6 minor 24 references
Fair densest subgraph across multiple graphs
T0 review · 4 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read The paper proves that two fair variants of the densest subgraph problem across graph snapshots are NP-hard, gives exact integer-programming algorithms and greedy heuristics, and evaluates them on real and synthetic data.
desk verdict A useful, correct addition to the densest-subgraph toolkit; the central hardness results hold, and the soft spots are presentation-level rather than load-bearing. 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 load-bearing mechanism is the density functional $d(S, G_i) = |E(S, G_i)|/|S|$ together with the range functional $\Delta(S,\mathcal{G}) = \max_i d(S,G_i) - \min_i d(S,G_i)$. The integer programs convert vertex selection into binary variables $y_i$ and edge selection into $x_{ij}$, forcing $x_{ij} = \min(y_i, y_j)$, and encode the fairness constraint $b(S,\mathcal{G}) \le \alpha|S|$, where $b(S,\mathcal{G}) = \max_i m(S,G_i) - \min_i m(S,G_i)$. Because the density objective is a fraction, the paper uses Dinkelbach-style fractional programming: instead of maximizing $d(S,\mathcal{G})$ directly, it maximizes $\sum_i m(S,G_i) - \gamma|S|$ for a guessed $\gamma$ and binary-searches $\gamma$, which is the device that turns each density query into one integer linear program.
What would settle it
Run the $\alpha = 0$ reduction on a graph $H$ known to have no $k$-clique: if any subset $S$ yields $d(S,G_1) = d(S,G_2) = (k-1)/4$, the reduction is wrong. More broadly, an exact polynomial-time algorithm for FDS on two snapshots with equal vertex sets would refute NP-hardness unless P=NP.
Extended reading notes
Core claim
On the paper's own terms, the discovery is that imposing near-equal densities across snapshots flips the classic densest subgraph problem from polynomial-time solvable to NP-hard. The hardness holds in the extreme case $\alpha = 0$, where both snapshots must induce exactly the same density, and the proof reduces from $k$-Clique by building two snapshots over a common vertex set: $G_1$ is the clique-test graph plus $k$ isolated helper vertices, and $G_2$ is a $k$-clique on those helpers. A subset achieves equal densities and total density $(k-1)/2$ exactly when the helper vertices are balanced with a $k$-clique in $G_1$. The same construction shows SDS is inapproximable. For solving the problems, the paper defines auxiliary objectives $\text{FDS}(\gamma)$ and $\text{SDS}(\gamma)$ that subtract $\gamma$ times the vertex count from edge counts, solves them as integer linear programs, and wraps them in a binary search that gives a $(1+\varepsilon)$ approximation, or an exact result once $\varepsilon$ is below the gap between distinct density values.
Load-bearing premise
All results assume the snapshots share one vertex set and density is $|E(S)|/|S|$; if either changes, the $k$-Clique reductions and the constraint encoding $b(S,\mathcal{G}) \le \alpha|S|$ would have to be rebuilt.
Editorial extensions
If this is right
- The unconstrained total-density problem on graph sequences is polynomial-time solvable, but adding any fixed density-spread constraint makes it NP-hard, even for $\alpha = 0$.
- The smallest-difference variant SDS has no polynomial-time multiplicative approximation unless P=NP, so the exact IP solver is the only way to get provable answers.
- The binary-search IP algorithms return a solution within a $(1+\varepsilon)$ factor, and become exact when $\varepsilon$ is small enough that the search interval cannot straddle two distinct density values.
- The greedy heuristics recover planted fair components in synthetic data and produce reasonable solutions on real datasets, offering a practical alternative when the IP solvers are too slow.
- The DBLP case study indicates that tuning $\alpha$ or $\sigma$ gives an analyst a direct trade-off between total density and diversity across venues or time snapshots.
Reading between the lines
- A likely next test is whether the hardness survives a different density measure, such as $m(S)/\binom{|S|}{2}$ or triangle density, which the authors explicitly leave to future work; those measures change the fractional-programming structure and may shift the boundary.
- The equivalence $\Delta(S,\mathcal{G}) \le \alpha \iff b(S,\mathcal{G}) \le \alpha|S|$ depends on dividing edge counts by the same $|S|$; if snapshots had different vertex sets or weights, the IP constraint would need a different normalization, so the complexity results should be read within the common-vertex-set model.
- For very large snapshot sequences the exact IP solvers will be limited by exponential worst-case runtime; a promising practical direction, not explored here, is to strengthen the LP relaxation or add cutting planes so the binary search runs faster than the reported one-hour cutoffs.
- The case study hints at a concrete use: tuning $\alpha$ or $\sigma$ lets an analyst trade total density against venue or temporal diversity, something the minimum-densest-subgraph baseline cannot do since it has no trade-off parameter.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines two multi-snapshot densest-subgraph problems with fairness constraints: FDS (maximize total density subject to the range of per-snapshot densities being at most alpha) and SDS (minimize the density range subject to total density at least sigma). It proves FDS NP-hard and SDS NP-hard and inapproximable unless P=NP, using reductions from k-Clique. It then proposes exact algorithms based on fractional programming and integer linear programming (FDS-IP and SDS-IP) with (1+epsilon)-type guarantees, two polynomial-time greedy heuristics (FDS-Grd and SDS-Grd), and an IP-based solver for the existing MDS baseline. Experiments on synthetic and real-world datasets evaluate recovery of a planted fair component, solution quality, and runtime; a DBLP case study illustrates trade-offs between density and fairness.
Significance. The complexity results are the paper's main contribution and they appear sound: the alpha=0 reduction forces equal densities, and the threshold argument correctly forces a balanced set W union U of size 2k and a clique. The SDS inapproximability via the zero-OPT argument is also standard and correct. The IP formulations are a reasonable way to solve the problems exactly on moderate instances, and the synthetic experiments include a planted ground-truth component with Jaccard recovery, which is a useful form of validation. The paper is honest about the exponential worst case of the exact solvers and the lack of guarantees for the heuristics. My main concerns are formal: Proposition 4 contains an incorrect sentence in the exactness proof, the proofs of Propositions 6 and 7 are omitted, and one reported experimental solution appears infeasible; none of these undermines the core reductions, but they need to be fixed before the paper is fully acceptable.
major comments (4)
- [§4.1, Proposition 4] In the exactness proof, the statement 'd(S, G) is a rational number with a numerator of at most n' is false; the correct invariant is that d(S, G) can be written with denominator |S| <= n, so two distinct achievable densities differ by at least 1/n^2. The displayed bounds 'gamma* − gamma > n−2' and 'U − L ≤ n−2' appear to be rendering errors for n^{-2}. As written the proof of the exactness claim gamma = gamma* does not go through; please restate the rational-gap argument with the correct denominator bound and exponents.
- [§4.2 and §4.5, Propositions 6 and 7] The proofs of Propositions 6 and 7 are omitted with the note that they are similar to Proposition 4. These propositions provide the approximation and exactness guarantees for SDS-IP and MDS-IP, so they are load-bearing for the algorithmic claims. Please supply complete proofs or detailed proof sketches; the SDS case in particular involves a minimization search with an upper-bound return, so the exactness argument is not literally identical to the FDS case.
- [§4.2, SDS-IP] The binary search for SDS-IP is described as stopping when 'U − L ≤ (1 + epsilon)L', but this condition is inconsistent with the claimed gamma <= (1+epsilon)gamma* guarantee; it should be U − L <= epsilon L (as in FDS-IP), and the search interval should start at L = 0 and U = (n−1)/2 (or another stated bound). Please correct the stopping rule and specify the initialization.
- [Table 3] In the Twitter-user dataset with alpha = 0.3, the FDS-IP row reports Δ = 0.5, which violates the feasibility constraint Δ <= alpha. Since Constraint (5) should prevent this, either the table entry or the implementation is wrong. Please correct the entry and verify that every reported solution satisfies its stated alpha; the same check should be applied to Table 4.
minor comments (6)
- [§3, Proposition 2] When Δ(S,G)=0, the common density is at least (k−1)/4 (because the total density must be at least sigma=(k−1)/2), not necessarily equal to it; the subsequent clique argument still works with '>=' in place of '=' and should be updated.
- [Table 3 caption] The caption describes alpha as the 'minimum value of the allowed induced density difference', but per Problem 2 it is the maximum allowed difference.
- [§6.5] The text refers to 'Figure 1d', but the figure only contains panels (a)–(c); the reference should be to Figure 1c.
- [§4.3, Algorithm 1] The update rule for the greedy heuristic is only loosely specified; please state how ties are broken, what 'while changes to Δ(S)' means formally, and give a termination and running-time bound for the algorithm.
- [Table 4] The formatting of several rows (e.g., Twitter-#) is garbled, with missing or ambiguous cells; please provide a clean table with clearly separated IP and GR columns.
- [§4.4] The description of FDS-Grd's first phase says it runs SDS-Grd for sigma in {i/k * dtds}, but it does not state a default for k in the main text; the experimental section mentions k=20 then k=100, so please state the parameter setting in the algorithm description.
Circularity Check
No significant circularity: the NP-hardness reductions are external (k-Clique), the algorithms follow from fractional programming, and the experiments are validation rather than prediction.
full rationale
The paper's derivation chain is self-contained. The FDS hardness proof (Proposition 1) reduces k-Clique to the two-snapshot instance with α=0; the forced equality of densities and the bounds on d(S,G1) and d(S,G2) imply |W|=|T|=k and that W is a k-clique, so the reduction does not presuppose the target result. The SDS hardness and inapproximability proof (Proposition 2) uses the same construction with σ=(k−1)/2 and the standard zero-OPT argument: a multiplicative approximation would have to certify ∆=0 when the optimum is 0. The exact algorithms (Section 4) are justified by the fractional-programming Propositions 3 and 5, and the integer programs directly encode the equivalence between the density-range constraint and the edge-difference constraint; no parameter is fitted to data and then relabeled as a prediction. The synthetic experiments plant a ground-truth fair component, set α and σ to that component's known values, and then check recovery; this is standard validation, not circularity. The only same-author citation, Arachchi and Tatti [3], appears in related work as a pointer to a different problem and is not load-bearing for any claim in this paper. The omitted proofs for Propositions 6 and 7 and the supplementary MDS-IP proof, together with the typographical 'n−2' in Proposition 4, are presentation issues that do not create circularity.
Assumptions & free parameters
assumptions (5)
- domain assumption All graph snapshots are defined over the same vertex set V
- domain assumption Density is measured as |E(S)|/|S|
- standard math k-Clique is NP-complete
- standard math Dinkelbach fractional programming equivalence
- domain assumption Exact optimal solutions from the integer programming solver
Cite this review
Pith. "Pith review of Fair densest subgraph across multiple graphs." pith.science (2026). https://pith.science/paper/QHXFX46L
@misc{pith2026250201381,
author = {Pith},
title = {Pith review of: Fair densest subgraph across multiple graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/QHXFX46L}},
note = {Machine review of arXiv:2502.01381}
}
abstract
Many real-world networks can be modeled as graphs. Finding dense subgraphs is a key problem in graph mining with applications in diverse domains. In this paper, we consider two variants of the densest subgraph problem where multiple graph snapshots are given and the goal is to find a fair densest subgraph without over-representing the density among the graph snapshots. More formally, given a set of graphs and input parameter $\alpha$, we find a dense subgraph maximizing the sum of densities across snapshots such that the difference between the maximum and minimum induced density is at most $\alpha$. We prove that this problem is NP-hard and present an integer programming based, exact algorithm and a practical polynomial-time heuristic. We also consider a minimization variant where given an input parameter $\sigma$, we find a dense subgraph which minimizes the difference between the maximum and minimum density while inducing a total density of at least $\sigma$ across the graph snapshots. We prove the NP-hardness of the problem and propose two algorithms: an exponential time algorithm based on integer programming and a greedy algorithm. We present an extensive experimental study that shows that our algorithms can find the ground truth in synthetic dataset and produce good results in real-world datasets. Finally, we present case studies that show the usefulness of our problem.
Figures
Reference graph
Works this paper leans on
-
[1]
Ahmadian, S., Epasto, A., Kumar, R., Mahdian, M.: Cluste ring without over-representation. In: KDD. pp. 267–275 (2019)
work page 2019
- [2]
-
[3]
arXiv preprint arXiv:2308.15936 (2023)
Arachchi, C.W., Tatti, N.: Jaccard-constrained dense s ubgraph discovery. arXiv preprint arXiv:2308.15936 (2023)
arXiv 2023
-
[4]
Charikar, M.: Greedy approximation algorithms for findi ng dense compo- nents in a graph. In: APPROX. pp. 84–95 (2000)
work page 2000
-
[5]
https://doi.org/10.48550/ARXIV.1802.06361, https://arxiv.org/abs/1802.06361
Charikar, M., Naamad, Y., Wu, J.: On finding dense common subgraphs (2018). https://doi.org/10.48550/ARXIV.1802.06361, https://arxiv.org/abs/1802.06361
-
[6]
M anagement science 13(7), 492–498 (1967) Fair densest subgraph across multiple graphs 17
Dinkelbach, W.: On nonlinear fractional programming. M anagement science 13(7), 492–498 (1967) Fair densest subgraph across multiple graphs 17
work page 1967
-
[7]
Du, X., Jin, R., Ding, L., Lee, V.E., Thornton, J.H.: Migr ation motif: A spatial-temporal pattern mining approach for financial mar kets. In: KDD. pp. 1135–1144 (2009)
work page 2009
-
[8]
Bioi nformatics 22(14), e150–e157 (2006)
Fratkin, E., Naughton, B.T., Brutlag, D.L., Batzoglou, S.: Motifcut: reg- ulatory motifs finding with maximum density subgraphs. Bioi nformatics 22(14), e150–e157 (2006)
work page 2006
Show all 24 references
-
[9]
TKDD 14(1), 1–40 (2020)
Galimberti, E., Bonchi, F., Gullo, F., Lanciano, T.: Cor e decomposition in multilayer networks: Theory, algorithms, and application s. TKDD 14(1), 1–40 (2020)
2020
-
[10]
Goldberg, A.V.: Finding a maximum density subgraph (19 84)
-
[11]
In: STOC
Håstad, J.: Clique is hard to approximate within n1− ǫ. In: STOC. pp. 627– 636 (1996)
1996
-
[12]
In: ECMLPKDD
Jethava, V., Beerenwinkel, N.: Finding dense subgraph s in relational graphs. In: ECMLPKDD. pp. 641–654 (2015)
2015
-
[13]
Leskovec, J., Backstrom, L., Kleinberg, J.: Meme-trac king and the dynamics of the news cycle. In: KDD. pp. 497–506 (2009)
2009
-
[14]
In: ASO NAM
Mehrabi, N., Morstatter, F., Peng, N., Galstyan, A.: De biasing community detection: the importance of lowly connected nodes. In: ASO NAM. pp. 509– 512 (2019)
2019
-
[15]
ACM computing surv eys (CSUR) 54(6), 1–35 (2021)
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., Ga lstyan, A.: A survey on bias and fairness in machine learning. ACM computing surv eys (CSUR) 54(6), 1–35 (2021)
2021
-
[16]
In: KDD (2023)
Miyauchi, A., Chen, T., Sotiropoulos, K., Tsourakakis , C.E.: Densest diverse subgraphs: How to plan a successful cocktail party with dive rsity. In: KDD (2023)
2023
-
[17]
arXiv preprint arXiv:2402.09124 (2024)
Oettershagen, L., Wang, H., Gionis, A.: Finding denses t subgraphs with edge-color constraints. arXiv preprint arXiv:2402.09124 (2024)
2024 arXiv
-
[18]
KAIS 62(4), 1611–1639 (2020)
Rozenshtein, P., Bonchi, F., Gionis, A., Sozio, M., Tat ti, N.: Finding events in temporal networks: segmentation meets densest subgraph discovery. KAIS 62(4), 1611–1639 (2020)
2020
-
[19]
J ohn Wiley & Sons (Jun 1998)
Schrijver, A.: Theory of Linear Integer Programming. J ohn Wiley & Sons (Jun 1998)
1998
-
[20]
DMKD 33(5), 1417–1445 (2019)
Semertzidis, K., Pitoura, E., Terzi, E., Tsaparas, P.: Finding lasting dense subgraphs. DMKD 33(5), 1417–1445 (2019)
2019
-
[21]
In: EDBT/ICDT Workshops
Tsantarliotis, P., Pitoura, E.: Topic detection using a critical term graph on news-related tweets. In: EDBT/ICDT Workshops. pp. 177–182 (2015)
2015
-
[22]
Tsourakakis, C.: The k-clique densest subgraph proble m. In: WWW. pp. 1122–1132 (2015)
2015
-
[23]
Tsourakakis, C., Bonchi, F., Gionis, A., Gullo, F., Tsi arli, M.: Denser than the densest subgraph: extracting optimal quasi-cliques wi th quality guar- antees. In: KDD. pp. 104–112 (2013)
2013
-
[24]
In: WOSN
Viswanath, B., Mislove, A., Cha, M., Gummadi, K.P.: On t he evolution of user interaction in facebook. In: WOSN. pp. 37–42 (2009) arXiv:2502.01381v1 [cs.DS] 3 Feb 2025 Fair densest subgraph across multiple graphs: supplementary material No Author Given No Institute Given A Sol...
2009 arXiv
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.