Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper tackles the problem of cardinality-based decomposable submodular function minimization (Card-DSFM). DSFMs have been a popular topic of research, and the authors claim that the case when every component function is a cardinality based concave function is an important one in practical applications. For this subproblem, they derive the first approximation algorithms via reduction to sparse graph cuts.

Given a concave cardinality function, the aim is to model it via gadgets (directed graphs on which we will solve a max-flow instance). The authors show that the problem of finding such gadgets is equivalent to finding piecewise linear functions which can approximate the original function with minimum number of linear components. This problem is solved using a greedy method, which gives a better bound on the number of pieces than existing methods.

Once these are optimally computed, they are converted into equivalent gadgets. Once all gadgets are combined into a graph, a max-flow instance is run. The obtained minimum cut also gives a solution to the underlying Card-DSFM.
main_review: The results in this paper apply to a wide variety of practical problems, and formulating theoretical bounds for this problem as an approximation algorithm is a valuable contribution. 
Theoretical details are rigorously proved and much effort is gone into formalizing definitions and theorems for this problem. As the paper shows, the results outdo previous baseline results theoretically, even in the case of exact computation. These theoretical contributions, by themselves, are valuable and warrant acceptance in my opinion.

The experiments are also strong, and are able to showcase the strength of the method, in terms of getting better approximations in faster time as opposed to competing methods. The paper also showcases the effectiveness in using the proposed technique as an approximate reduction to graphs for existing methods, and shows improvements in runtimes.

The writing overall is of good quality. The authors do a good job of giving intuition about the technical details in words - however, this can still be improved upon in Section 3.

limitations_and_societal_impact: The authors make a genuine effort into analyzing their limitations, and also talk in some detail about possible negative societal effects of their work on impacts of the paper. There is a clear mention of how it only solves a particular class of problems, as compared to existing methods.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a fast approximate method for minimizing decomposable submodular function where each component is cardinality-based. The runtime is improved by exploiting sparse piecewise linear approximation to concave functions at integer points, which is combined with graph reduction to convert the original minimization problem as an s-t cut problem on a sparse graph. Empirical results show that the mehtod can be faster than state-of-the-art numerical methods. Moreover, the approximation ratios are generally much smaller than the worst-case approximation guarantee.
main_review: Decomposable submodular function minimization has many applications in machine learning. This paper considers a specific setting where the components are cardinality-based submodular functions. While the results obtained in this paper are interesting, they are not very surprising.

Overall, the paper is very well written and nicely structured. Theoretical analyses appear to be adequate. The proposed method can be a nice tool to have. However, the experiments do not seem to provide a strong evidence for the significance of this work. In particular, the running time of existing numerical methods does not seem to be a limiting factor that prevents the use of cardinality-based submodular functions in the two applications presented in the experiments. For example, for the hypergraph clustering case, why can't ACDM be applied? Are there hypergraph clustering experiments where the proposed method is compared with existing numerical methods?
limitations_and_societal_impact: I cannot think of any potential negative societal impact based on this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an algorithm for minimizing submodular functions that are the sum of cardinality-based components. This is a special case of decomposable submodular function minimization. Formally, the problem considered is to minimize $f(S) = \sum\limits_{e\in E} g_e(|S \cap e|)$, where $E\subseteq 2^V$ and $g_e$ are 1-dimensional concave functions. One instance of such functions are the region potentials used in image segmentation, where $g_e(x) = c_e \cdot x (|e| - x)$ for some constant $c_e \geq 0$. Such minimization problems are also considered in hypergraph clustering applications.

The authors propose an approximation algorithm that works by approximately reducing their problem to a graph min cut problem. The fact that concave functions can be _exactly_ represented by graphs is known, and the resulting number of edges in the graph is $O\left(\sum\limits_{e\in E} |e|^2\right)$. The main result of the paper is to show how to reduce the number of edges by allowing _approximate_ reductions, leading to a graph with $\widetilde{O}\left(\frac{1}{\epsilon} \sum\limits_{e\in E} |e|\right)$ edges while incurring an $(1+\epsilon)$-multiplicative error in the objective.

The idea is to simplify each concave function before converting it to a graph. Viewing each concave function as a piecewise linear function, the size of the resulting graph depends on the number of pieces. The authors present an algorithm that is able to find the _best_ (in terms of the number of pieces) $(1+\epsilon)$-approximation to this function. By known results, the optimal number of pieces is $\widetilde{O}\left(\frac{1}{\epsilon}\right)$, thus follows the $\widetilde{O}\left(\frac{1}{\epsilon} \sum\limits_{e\in E} |e|\right)$ bound on the number of edges.

For the special case of the region potentials $g_e(x) = c_e \cdot x (|e| - x)$, the authors are able to get a better bound of $\widetilde{O}\left(\frac{1}{\sqrt{\epsilon}} \sum\limits_{e\in E} |e|\right)$ on the number of edges.

The theoretical results are accompanied by experimental results in the problems of image segmentation and hypergraph clustering. For image segmentation, the results show a speedup of at least 3x in 3 out of 4 experiments compared to previous methods, while it is slower in 1 of the 4 experiments. For hypergraph clustering, the F1 score is improved by 3 percentage points at the expense of a 30% runtime increase.
main_review: **Originality**

The idea of finding the _optimal_ approximation to the concave functions and then turning the new function into a graph is very nice and original to the best of my knowledge. Also, the experimental work gives original insights into the performance of these algorithms.

**Quality**

I checked most of the theoretical results and they are sound. The experimental section is explained well and seems like a fair analysis between different methods, albeit quite limited (e.g. only 4 image segmentation examples). However, I have doubts regarding the theoretical comparison between methods in Section 4. 

-The discussion in lines 214-220 seems misguided to me. The fact that exact algorithms don't give a speedup when the error tolerance increases does _not_ make them worse than approximation algorithms. Additionally, the statement about multiplicative approximation doesn't make much sense to me, in the context of comparing to exact algorithms. I would just remove this paragraph.

-In Section 4, it should be emphasized that all previous methods are more general, as they work with arbitrary submodular functions. This is written in other parts of the paper, but should be emphasized in this section which compares different results. In particular, certain runtimes from previous work can be improved in the case of cardinality functions. As an example, in the $\sum\limits_{e} |e|^2 \theta_e$ dependence in [4], the $\theta_e$ comes from solving problems of the form $\min_S f_e(S) + w(S)$, where $w$ is linear. If $f_e$ is a cardinality function, these can be easily solved by sorting, immediately improving this term to $\sum\limits_{e} |e|^2$.

-On the same note, it seems to me that it might be possible to plug the graph approximation results in the current paper into [4] in an almost black-box way to replace the existing graph approximation routine, in order to give an _exact_ algorithm for Card-DSFM running in time $\widetilde{O}\left(T_{mf}(n+R, \mu)\right)$. The authors could mention a statement to this effect, as it seems to be a natural connection.

-Another question I had was regarding the region potentials. Since these correspond to complete graphs, one can very easily sparsify them (by uniformly sampling a few edges from them). I am curious how the performance would compare to the authors' approach.

**Clarity**

The writing is nice in general. I appreciate the authors' sharing the code and data, as well as documentation. I tried to run the code, but it seems that read_data.jl is missing. I also have some minor comments.

-Line 54: “lead” -> “leads”

-Line 148: “solving” -> “solve”

-Line 227: “runtimes” -> “runtime”

-Line 249: “which will faster” -> “which will be faster”

-Line 288: Space missing

-Line 353: “leading to the first approximation algorithms for cardinality-based DSFM” -> “leading to the first approximation algorithms specifically for cardinality-based DSFM”

-Multiple places: “DFSM” -> “DSFM”

**Significance**

This seems like a result that is significant in practice. As the authors note, cardinality-based functions are common in image segmentation, hypergraph clustering, etc, and this paper improves the runtime considerably in the practical examples tested, although for conclusive statements to be made, more experiments would need to be done.
limitations_and_societal_impact: The limitation that I could find in the paper is that there are not enough experiments to make a conclusive practical evaluation (e.g. only 4 image segmentation examples). The authors have addressed the societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work studies minimizing decomposable submodular functions, which are of the form f(S) = \sum_{e \in E}f_e(S \cap e), where each f_e is a ``simple'' submodular function. In many practical applications, f_e(A) is cardinality based, that is, f_e(A) = g_e(|A|) for some concave function g_e. Several discrete/continuous algorithms have been proposed to minimize such decomposable submodular functions. One combinatorial approach to tackle this problem is to introduce a gadget graph G_e so that, for any A, g_e(|A|) is equal to the minimum cut of G_e subject to A (in addition to some special vertex) being contained in one side of the cut. It is known that any cardinality-based submodular function can be represented this way as a gadget graph of O(|e|) vertices and O(|e|^2) edges.

The main contribution of this work is providing a method for constructing a gadget graph that ``approximates'' cardinality-based submodular function instead of exactly simulating it. Specifically, it is shown that, to obtain a multiplicative error of 1 \pm epsilon, we only need O(epsilon^{-1} |e| log |e|) edges. A lower bound of O(epsilon^{-1/2} |e| log |e|) is also shown. When g(x) = x(k-x), which often appears in practice, it is shown that the number of edges can be further improved to O(\epsilon^{-1/2}log log epsilon^{-1} \cdot |e|). These results are obtained by approximating the concave function g_e with a piecewise linear function l and then representing l as a gadget graph.

Empirical results on image segmentation tasks show that the proposed approximate reduction outputs a much smaller gadget graph compared to the exact reduction without much sacrificing the quality of the solution. For example, for some choice of the parameters, the size of the output graph becomes 0.013 (1/0.013?) times smaller while the multiplicative error is merely 1 \pm 4*10^-3. It is then confirmed that the trade-off of the approximation ratio and runtime of the proposed method is much better than those of other methods. It is also empirically investigated that the quality of hypergraph clustering does not deteriorate much by replacing the objective submodular functions with gadget graphs obtained by the proposed approximate reduction.
main_review: - The biggest issue in evaluating this work is that I don't fully understand the relevance of this study. I understand that the proposed method outperforms other methods when there are large e's in the input decomposable submodular function. But in practice are there large e's? I understand there are a few of them as in the hypergraph used in the experiment on local clustering, but can't we just ignore those large hyperedges and quickly get a good approximation?
- Related to the question above, in the image segmentation task, what is the max/average size of e?
- It is nice that a detailed comparison of time complexity is provided because it is often implicit in the literature, which blurs the difference between existing methods.

limitations_and_societal_impact: N/A
review_title: null

Meta-review: The reviewers appreciate the problem and the technical contribution of the paper.
Decision: Accept (Poster)