Streaming Min-Max Hypergraph Partitioning
In many applications, the data is of rich structure that can be represented by a hypergraph, where the data items are represented by vertices and the associations among items are represented by hyperedges. Equivalently, we are given an input bipartite graph with two types of vertices: items, and associations (which we refer to as topics). We consider the problem of partitioning the set of items into a given number of components such that the maximum number of topics covered by a component is minimized. This is a clustering problem with various applications, e.g. partitioning of a set of information objects such as documents, images, and videos, and load balancing in the context of modern computation platforms. In this paper, we focus on the streaming computation model for this problem, in which items arrive online one at a time and each item must be assigned irrevocably to a component at its arrival time. Motivated by scalability requirements, we focus on the class of streaming computation algorithms with memory limited to be at most linear in the number of components. We show that a greedy assignment strategy is able to recover a hidden co-clustering of items under a natural set of recovery conditions. We also report results of an extensive empirical evaluation, which demonstrate that this greedy strategy yields superior performance when compared with alternative approaches.
This paper proposes a simple greedy strategy for the min-max hypergraph partitioning problem under the streaming model. This paper defines a stochastic model for generating the input hypergraph and show the sufficient conditions for the asymptotical recovery of the hidden clusters for the hypergraphs generated using this model.I think the paper studies an interesting and important problem. The proposed stochastic model for graph generation seems interesting and novel. I find it interesting to see that the min-max graph partitioning problem can be almost recovered under certain conditions of the graph. However, I am mostly concerned about how realistic the stochastic model for generating the graph is: does the hidden co-clustering assumption about how the data is generated realistic in practice? I hope to see more justification of why this model is natural for real-world applications.   I think the authors should also cite a recent but very relevant paper below, which essentially considers the same problem of min-max graph partitioning and proposes an offline greedy algorithm very similar to the one proposed in this work. The offline greedy algorithm is claimed to run with time complexity of O(k|E|) , where k is the number of parts in the resulting partitioning and |E| is the number of edges in the bipartite graph. I am curious to see how the streaming greedy algorithm performs relative to the offline greedy algorithm empirically.    Graph Partitioning via Parallel Submodular Approximation to Accelerate Distributed Machine Learning Mu Li, Dave G. Andersen, Alexander J. Smola, 2015http://arxiv.org/pdf/1505.04636.pdfMinor comments:Line 168-171: It seems that this part of paper is trying to claim that the random partitioning of the graph can yield bad performance, but all it shows is that the random partitioning gives a cost of (1-1/e)m, whereas it is unclear what the global optimal is.Description of Alg 1 (Line 216-225): The notations used in Alg 1 are a bit confusing. At the beginning of Alg 1, S_i's are defined to be the assignment of the items, which makes me think that S_i should denote the set of items in block i. However, it seems that S_i is used to refer to the set of topics covered by the items in block i in the description of the algorithm. I find it quite confusing.