As far as I understand a large number of clustering problems can be formulated as:
$\underset{\textbf{P}}{ \text{argmin}} \; \sum_{i,j} f \left(x_i, x_j\right)$
where $\textbf{P}$ is a partitioning of $\mathbf{x}$. In other words, the goal is to find a partitioning that is optimal with respect to a sum of pairwise contributions of the variables within and/or across clusters. Problems such as K-means and correlation clustering can be written in the above form. For example, K-means minimizes the sum-of-squares which is known to be NP-hard.
I am wondering if there is any work on what I informally would call higher-order or clustering, where the functions $f$ measure the affinity of general cliques of variables
$\underset{\textbf{P}}{\text{argmax}}\; \sum_{c_i} f(\mathbf{x}_{c_i})$
for cliques $c_i$ in some set $C$.
Perhaps a more difficult problem is what I would informally call black-box clustering, i.e. problems of the above form where $f$ is unknown (i.e. we don't have access to an algebraic or analytical expression of $f$, but we can query it. I imagine using some sort of direct-search optimization method for solving such problems.
Does anybody know of if these problems have been addressed in the literature? Perhaps they are known by other names?
