Pith. sign in

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 →

arxiv 2502.01381 v1 pith:QHXFX46L submitted 2025-02-03 cs.DS

classification cs.DS MSC 68Q1768R1090C10
keywords fairdensestsubgraphgraphsnapshotstemporalnetworksNP-hardnessintegerprogrammingfractionalgreedyheuristicdensityrange
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

This paper studies how to find a dense subgraph common to several graph snapshots without letting one snapshot dominate the density score. It introduces and analyzes two optimization problems: FDS, which maximizes the sum of per-snapshot densities subject to the gap between the maximum and minimum snapshot density being at most $\alpha$, and SDS, which minimizes that gap subject to a lower bound $\sigma$ on the total density. The paper's central claims are that both problems are NP-hard, that SDS has no multiplicative polynomial-time approximation unless P=NP, and that the hardness can be met in practice with exact integer-programming solvers plus polynomial-time heuristics. The motivation is fairness: standard sum-density maximization can return a subgraph that is dense in one time window and empty in all others, whereas these formulations keep the induced density spread across snapshots.

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.

Watch

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

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

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

4 major / 6 minor

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)
  1. [§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.
  2. [§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.
  3. [§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.
  4. [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)
  1. [§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.
  2. [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.
  3. [§6.5] The text refers to 'Figure 1d', but the figure only contains panels (a)–(c); the reference should be to Figure 1c.
  4. [§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.
  5. [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.
  6. [§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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no free parameters in its derivation: α, σ, and ε are user-specified inputs to the optimization problems, not fitted values. The core assumptions are the common-vertex-set model and the |E|/|S| density measure (Section 2), the NP-completeness of k-Clique used in the reductions (Section 3), and the exactness of the ILP solver used by the IP-based algorithms (Section 4). No new entities are postulated.

assumptions (5)
  • domain assumption All graph snapshots are defined over the same vertex set V
    Stated in Section 2: each snapshot G_i=(V,E_i) is defined over the same set of nodes. This is required for the definitions of density sums and for the reductions in Section 3.
  • domain assumption Density is measured as |E(S)|/|S|
    Section 2 defines d(S,G_i)=|E(S,G_i)|/|S|. The hardness and algorithms are tied to this density measure; other measures (e.g., edge proportion m(S)/C(|S|,2)) lead to different problems, as noted in Section 5.
  • standard math k-Clique is NP-complete
    Used as the source problem in the reductions of Proposition 1 and Proposition 2 (Section 3).
  • standard math Dinkelbach fractional programming equivalence
    The relationship between FDS and FDS(γ) in Proposition 3 relies on the fractional programming framework, citing Dinkelbach [6] (Section 4.1).
  • domain assumption Exact optimal solutions from the integer programming solver
    The exact algorithms FDS-IP, SDS-IP, and MDS-IP call an ILP solver (Gurobi) at each binary-search step; the approximation guarantees hold only if the solver returns an optimal solution to the IP (Section 4).

how reviews work

0 comments
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

Figures reproduced from arXiv: 2502.01381 by the authors.

Figure 1
Figure 1. Dense subgraphs among different conferences in [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 22 canonical work pages

  1. [1]

    Ahmadian, S., Epasto, A., Kumar, R., Mahdian, M.: Cluste ring without over-representation. In: KDD. pp. 267–275 (2019)

  2. [2]

    In: CIKM

    Anagnostopoulos, A., Becchetti, L., Fazzone, A., Mengh ini, C., Schwiegelshohn, C.: Spectral relaxations and fair densest subgraphs. In: CIKM. pp. 35–44 (2020)

  3. [3]

    arXiv preprint arXiv:2308.15936 (2023)

    Arachchi, C.W., Tatti, N.: Jaccard-constrained dense s ubgraph discovery. arXiv preprint arXiv:2308.15936 (2023)

  4. [4]

    In: APPROX

    Charikar, M.: Greedy approximation algorithms for findi ng dense compo- nents in a graph. In: APPROX. pp. 84–95 (2000)

  5. [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. [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

  7. [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)

  8. [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)

Show all 24 references
  1. [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)

  2. [10]

    Goldberg, A.V.: Finding a maximum density subgraph (19 84)

  3. [11]

    In: STOC

    Håstad, J.: Clique is hard to approximate within n1− ǫ. In: STOC. pp. 627– 636 (1996)

  4. [12]

    In: ECMLPKDD

    Jethava, V., Beerenwinkel, N.: Finding dense subgraph s in relational graphs. In: ECMLPKDD. pp. 641–654 (2015)

  5. [13]

    Leskovec, J., Backstrom, L., Kleinberg, J.: Meme-trac king and the dynamics of the news cycle. In: KDD. pp. 497–506 (2009)

  6. [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)

  7. [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)

  8. [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)

  9. [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)

  10. [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)

  11. [19]

    J ohn Wiley & Sons (Jun 1998)

    Schrijver, A.: Theory of Linear Integer Programming. J ohn Wiley & Sons (Jun 1998)

  12. [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)

  13. [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)

  14. [22]

    Tsourakakis, C.: The k-clique densest subgraph proble m. In: WWW. pp. 1122–1132 (2015)

  15. [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)

  16. [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...

Pith tools

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