Inhomogeneous Hypergraph Clustering with Applications
Hypergraph partitioning is an important problem in machine learning, computer vision and network analytics. A widely used method for hypergraph partitioning relies on minimizing a normalized sum of the costs of partitioning hyperedges across clusters. Algorithmic solutions based on this approach assume that different partitions of a hyperedge incur the same cost. However, this assumption fails to leverage the fact that different subsets of vertices within the same hyperedge may have different structural importance. We hence propose a new hypergraph clustering technique, termed inhomogeneous hypergraph partitioning, which assigns different costs to different hyperedge cuts. We prove that inhomogeneous partitioning produces a quadratic approximation to the optimal solution if the inhomogeneous costs satisfy submodularity constraints. Moreover, we demonstrate that inhomogenous partitioning offers significant performance improvements in applications such as structure learning of rankings, subspace segmentation and motif clustering.
In this paper the authors consider a novel version of hypergraph clustering. Essentially, the novelty of the formulation is the following: the cost of a cut hyperedge depends on which nodes go on each side of the cut. This is quantified by a weight function over all possible subsets of nodes for each hyperedge. The complexity of such formulation may at first glance seem unnecessary, but the authors illustrate real-world applications where it makes sense to use their formulation. The paper is nicely written. My main critique is that some key ideas of the paper -as the authors point out themselves- are heavily based on [11]. 
Also some theoretical contributions are weak, both from a technical perspective and with respect to their generality. For instance, Theorem 3.1 is not hard to prove, and is true under certain conditions that may not hold. On the positive side, the authors do a good work with respect to analyzing the shortcomings of their method.Also, the experimental results are convincing to some extent. 
My comments follow:
1. The authors provide a motivational example in the introduction. I suggest that the caption under figure  1 should be significantly shortened. The authors may refer the reader to Section 1 for details instead. 
2. The authors should discuss in greater details hypergraph clustering, and specifically the formulation where we pay 1 for each edge cut. Τhere is no canonical matrix representation of hypergraphs, and optimizing over tensors is  NP-hard. The authors should check the paper "Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms" by Anand Louis (arxiv:1408.2425)  
3.  As pointed out by [21] there is a random walk interpretation for motif-clustering. Is there a natural random walk interpretation of the current formulation in the context of motif clustering? 
4.  The experimental results are convincing to some extent. It would have been nicer to see more results on motif-clustering. Is there a class of motifs and graphs where your method may significantly outperform existing methods [10,21]? 
Finally, there is a typo in the title, and couple of others (e.g., "is guaranteed to find a constant-approximation solutions"->"is guaranteed to find a constant-approximation solution") along the way. Use ispell or some other similar program to detect all typos, and correct them.