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?

  • $\begingroup$ Maybe you are looking for spatial index or space-fillin-curve? $\endgroup$
    – Micromega
    Aug 1, 2011 at 22:55
  • $\begingroup$ Since your sum is "within and across clusters", I don't see where $\mathbf{P}$ comes in. $\endgroup$
    – user6973
    May 6, 2012 at 17:48
  • $\begingroup$ Thanks @RickyDemer, $\textbf{P}$ is encoded in the choice of the variables $x_i$. That said, in K-means for example we only look for contributions within clusters. $\endgroup$ May 6, 2012 at 17:52

1 Answer 1


One example of what you might call non-linear clustering is kernel-based clustering, where the similarity function is described by a (non-linear) kernel function. This is a weak form of non-linearity, since there's a lifting map that makes everything linear (albeit in a Hilbert space)

  • $\begingroup$ Thanks @Suresh, but everything I have seen on kernel-based clustering seems to be linear (maybe also quadratic?) in pairwise contributions between variables. The function $f$ above can measure the affinity of a clique of any size. I will clarify this in the question. $\endgroup$ Jul 28, 2011 at 17:56
  • $\begingroup$ ah I see what you mean. $\endgroup$ Jul 29, 2011 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.