Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present a new iterative algorithm for Densest subgraph (DSG) and Densest Subgraph Decomposition (DSG-LD) problems. The algorithm takes $O(\frac{\sqrt(m \Delta(G))}{\epsilon})$ iteration to converge to an $\epsilon$-additive approximate local decomposition vector, where each iteration takes $O(m)$ time. The paper describe a fractional peeling technique to round the fractional solution for densest subgraph decompositon. The theoretical contribution is supported with experiments by comparing the proposed algorithm with some state of the art algorithms on real world and synthetic datasets.   


strengths_and_weaknesses: **Strengths**
- An efficient, simple, and scalable (epsilon-additive) algorithm for DSG and DSG-LD
- Fractional peeling technique with strong theoretical and empirical results
- Connection DSG-LD to decomposition of Supermodular function (DSS)
- Empirical evaluation of the described algorithms and fractional peeling technique and its comparison to the state of the art algorithms
- The algorithm being parallelizable 
- The extension of the algorithm for hypergraphs
- The connection of the LP and QP for DSS
 
questions: No comments for now.
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors of this paper propose an iterative algorithm for densest subgraph detection and decomposition, where the proposed algorithm is guaranteed to converge to an \epsilon-additive approximate solution and the number of iterations needed is significantly smaller than [3]. Besides the theoretical contributions, the authors conduct extensive experiments on several large-scale real-world graphs to show the practical effectiveness and efficiency of their proposed algorithm.
strengths_and_weaknesses: 1. The proposed algorithm significantly improves the algorithm in [3].
2. The results of this paper also apply to the densest decomposition of a supermodular function, which is a more general problem.
3. The authors also conduct extensive experiments on a number of large-scale graphs. The experimental results demonstrate that the proposed algorithm is not only theoretically sound but also highly effective and efficient in practice.
questions: I do not have questions so far.
limitations: 1. It would be better if the authors could list the approximation guarantee and the time complexity of each existing algorithm in a Table. Then readers can easily compare the theoretical guarantees of this paper and existing studies.  
2. Although optimization definitely is an important topic in NeurIPS, my understanding is that optimization papers published in NeurIPS majorly focus on optimization problems closely related to machine learning. It seems to me that dense subgraph detection is not directly related to major machine learning problems and it is more extensively studied in the data mining community or the algorithm design community. The weak relevance of this paper to NeurIPS is the major reason that I give a score of 6 for this paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considered the densest subgraph, densest subgraph decomposition, and supermodular generalizations of these problems. They provided a fast and scalable algorithm that can compute a $\epsilon$ approximate local decomposition vector in $O(\sqrt{m\Delta(G)}/\epsilon)$ iterations, where $\Delta(G)$ is the maximum degree of graph G. 
They also showed that a fractional peeling algorithm can round the fractional solution to get an $\epsilon\sqrt{n}$ approximation dense decomposition. 
strengths_and_weaknesses: Strengths:
The densest subgraph and densest subgraph decomposition are classic and important problems. This paper provided a fast and scalable algorithm that reduces the number of iterations to converge to an $\epsilon$ approximate local decomposition vector. They showed an interesting connection between LP and its dual and QP.  
The paper is well-written and easy to follow. 
 


questions: 1. Is the improvement in the number of iterations to convergence mainly coming from the connection between the LP dual and the QP shown in Thm 4.3? 
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present a new algorithm for densest subgraph (DSG) and graph decomposition  (DSG-LD) in undirected graphs by leveraging (1) proximal method and (2) fractional peeling inspired by recent work of GREEDY++ which uses information from load vector of the dual LP for a modified iterative peeling. The method is shown theoretically and empirically to be faster than competing methods and the fractional peeling improves quality of the solution compared to direct ordering. 
strengths_and_weaknesses: + Well-explained paper starting from Charikar's dual LP with clear description of connection to supermodular functions and results therein. Parts of this are known (e.g. Danisch et al and Chekuri et al, SODA 2022) but the relevant parts for this paper are clearly presented.
+ Paper adapts iterative peeling based on dual load vector idea introduced in Boob et al. to the DSG-LD problem.   
+ Adapts proximal method for DSG and DSG-LD with theoretical results
+ Detailed empirical evaluation with good comparison highlighting different scenarios.
+ (Minor) Theoretical connection to the breakthrough result of [Peng et al, 2022] which promises new avenues for development of practical algorithms. 
+ (Minor) Extension of hypergraphs discussed in appendix 6.7 

The discussion in the main text is good but the proofs could be better illustrated in places (See some suggestions below).

- Section 6.1 (Rado, b-transportation) Suggest adding a figure showing B(V', E') for easier comprehension.
- Section 6.5 - please refer explicitly from main text in Section 5.4 (lines 266 or 269). Also the order of the appendix section and main text is inverted so suggest changing order of 6.5 and 6.7 
- Line 260. "outline the formal details in appendix `6.7`" 
- Section 6.4 - Proof of 5.6 requires very careful reading. Suggest adding a figure/Venn diagram showing T_t and summation in 619.
  
questions: - Lines 309-311 is not new information and may/should be removed? Poor performance of Greedy++ for CloseCliques is a known example which was highlighted in the original [Boob+] paper and later expanded upon in the [Chekuri+, SODA '22] paper.  
  
limitations: Yes, discussed in Conclusion L347-351
review_title: null

Meta-review: metareview: Overall the reviewers found the paper to tackle an important problem and the level of technical novelty was high. The experiments were also good. Clear accept. 
confidence: Certain
Decision: Accept