# What is graph clustering?

There are several (family of) algorithms that can be used to cluster a set of $$d$$-dimensional points: for example, k-means, k-medoids, hierarchical clustering (agglomerative or divisive).

What is graph-based clustering? Are we clustering the nodes or edges of a graph instead of a set of $$d$$-dimensional (as e.g. in k-means)? Couldn't we just use k-means to also cluster a set of nodes?

• I could have asked this question on cs.stackexchange.com and it would have likely been a more appropriate action (given the generality of this question), but, given that this is also related to unsupervised learning and thus ML and AI, I decided to ask it here, in order to enrich our website. – nbro Mar 20 at 17:02
• Not to be confused with clustering multiple different graphs based on e.g. their edit distance or geometric properties, as in eurocg2019.uu.nl/papers/45.pdf – Discrete lizard Mar 21 at 11:57
• @Discretelizard Yes, this is also noted in the paper I mentioned in my answer (maybe I should have pointed this out in my answer). – nbro Mar 21 at 14:11
• @Discretelizard Nice! (We'd welcome a second answer, hint hint:) – DukeZhou Mar 21 at 18:54
• @DukeZhou Well, eh I could definitely tell something about clustering multiple graphs instead of the points in them, but that does not seem to be what this question is about. – Discrete lizard Mar 21 at 18:57

A simple (hierarchical and divisive) algorithm to perform clustering on a graph is based on first finding the minimum spanning tree of the graph (using e.g. Kruskal's algorithm), $$T$$. It then proceeds in iterations. At each iteration, we remove from $$T$$ the edge with the highest weight. Given that $$T$$ is a tree, the removal of an edge from $$T$$ will create a forest (with connected components). So, after the removal of the edge of highest weight from $$T$$, we will have two connected components. These two connected components will represent two clusters. So, after one iteration, we will have two clusters. At the next iteration, we remove the edge with the second highest weight, and this will create other connected components, and so on, until, possibly, all nodes are in their own cluster (that is, all edges have been removed from $$T$$).
There are several limitations of this algorithm. For example, it only considers the edges of the initial graph that are shared with $$T$$ (that is, it only considers the edges of the minimum spanning tree). It also requires the edges of the graph to be weighted. It does not require the number of clusters to be known in advance (like any other hierarchical clustering algorithm), but we still need to choose the optimal number of clusters (after the algorithm has terminated). We can do that in several ways. A way to do it would be to have a threshold value $$t$$ that is used to decide when we should stop removing edges from $$T$$: more specifically, we will keep removing edges from $$T$$ until the next highest weight is higher than this threshold $$t$$.