# Minimizing the cost of clustering a hypergraph

Background and notation:

Whenever I speak of a hypergraph $G$, I mean a pair of finite sets $V_G,E_G$ and a function $g\colon E_G\to\mathbb{P}(V_G)\;$ assigning each edge a subset of vertices.

If $v\in V_G$ is a vertex, let $E_v=\{e\in E_G\mid v\in g(e)\}\;$ be the set of edges containing $v$; the cardinality $\#E_v$ is called the degree of $v$.

For $n\in\mathbb{N}$, let $E^n_G=\{e\in E_G\mid\#g(e)=n\}\;$ denote the set of $n$-ary edges. Suppose $v\in V_G$ is a vertex; we denote by $E^1_v=E_v\cap E^1_G$ the set of singleton edges at $v$.

Clustering, its cost, and the goal:

We define an operation on hypergraphs, called clustering: contracting a set of vertices and removing the resultant singleton edges. This operation can be repeated until the hypergraph is a single vertex with no edges, which we call the point. The process of clustering until we reach the point will be called a complete reduction of $G$. Each time we cluster, there is an associated cost, which we explain at the bottom of this section. The cost of a complete reduction is the maximum cost incurred in the process. The goal is to find a strategy that minimizes the cost of completely reducing $G$.

Given a vertex $v$, the singleton edge removal at $v$ is the hypergraph $G'=G-E^1_v$ with the same vertices but the singleton edges at $v$ removed $E_{G'}=E_G-E^1_v$. The cost for removing singleton edges at $v$ is its degree $\#E_v$.

Given a subset $C\subseteq V_G$, the contraction of $G$ by $C$, denoted $G/C$ is the result of identifying those vertices in $C$ to become a single vertex $v_C$. There is a natural bijection between the edges before and after a contraction, $E_G\cong E_{G/C}$. However, note that there are may be new 1-ary edges created by contraction.

By clustering a subset of vertices $C\subseteq V_G$, we mean contracting it to a single vertex $v_C$ and then removing singleton edges at $v_C$.

The cost for clustering is just the cost of the singleton-edge-removal step.

Examples:

1. We can always cluster the entire hypergraph $G$ at once. The contraction $G/V_G$ will have as many edges as $G$ but they all become 1-ary. Removing them, and thus completely reducing $G$, has a cost of $\#E_G$. This is generally the worst strategy.
2. Suppose that $G$ is the chain $*-*-*-*-*$. Contracting the first two vertices, we obtain $-*-*-*$; removing the singleton costs 2 and the result is $*-*-*$. We can repeat twice more, moving left to right, and the maximum cost incurred is 2. This is a cost-minimizing strategy, though note that there are several cost-minimizing strategies in this case.
3. For any hypergraph $G$, one can define a greedy algorithm that looks for pairs of vertices for which the cost of clustering is minimized. This strategy does not always win.

Questions:

1. Does this clustering question have a name?
2. Does it relate to known questions that have been studied?
3. Any ideas for an efficient algorithm?
• I think that each clustering strategy corresponds to a partition of $V_G$ along with an ordering of the blocks. There is a well-known "split-merge" random walk on partitions, see, e.g. arxiv.org/abs/1109.3915. Meanwhile, random walks on the symmetric group are easy to come by, e.g., in papers by Diaconis and coworkers. So you can explore the space of all clustering strategies by alternating such walks and performing simulated annealing. One caveat is that the alternating walk would likely fail to inherit any uniformity property of either of the two "factors". – Steve Huntsman May 1 '17 at 17:19