Whether reality exists independently of conscious human observers is irrelevant, as pattern finding/making organism we cannot help but notice. In observing, we impose structure. The act of grouping like with like, or drawing classes and dividing based on characteristics, may seem like a forced and arbitrary byproduct of how we make sense of the world. However, it is also necessary, as good judgment requires good discernment. The difficulty is not that there are many ways to classify, but that different classifications reveal different aspects of reality.
Prior to molecular genetics, organisms were classified almost entirely by appearance and geography. Through that lens, the sugar glider and the flying squirrel appeared to be close relatives: both are small nocturnal mammals possessing a membrane between their limbs that allows them to glide. Genetic evidence revealed a different story. Flying squirrels are rodents, whereas sugar gliders are marsupials, their last common ancestor lying deep in mammalian history. Their striking resemblance is therefore not evidence of close ancestry but of convergent evolution, independent evolutionary solutions to similar ecological pressures.
Neither classification is entirely “wrong.” One captures functional similarity; the other, evolutionary history. The distinction illustrates a broader principle: every hierarchy is the consequence of a criterion. In this post, we explore that principle in the setting of weighted graphs, comparing two methods that reveal multi-scale structure for fundamentally different reasons.
Definitions
Consider the (non-negative) weighted graph.
$G=(V:=\{1,2,…,n\},~E \subseteq V \times V \setminus \{\{i,i\}~|~i \in V\}, w : E \to \mathbb{R}_+ )$
From graphs, we can derive a subsequent structure revealing mathematical objects.
We are going to consider hierarchical clustering methods. These are methods that produce a hierarchy of nested partitions $\Pi_0 \preceq \Pi_1 \preceq \cdots \preceq \Pi_k$, where $\Pi_i : = \{P_1^{(i)},\ldots,P_{k_i}^{(i)}\}$ is a set of parts, with $V = {\cup}_{j=1}^{k_i}P^{(i)}_{k}$ and $P^{(i)}_{j} \cap P^{(i)}_{l} = \emptyset$ for all $j\neq l \in [k_i]$), and for each $P \in \Pi_i and \Pi_j$ there is a $Q \in \Pi_j$ such that $P \subseteq Q$ when $i \leq j$. Without loss of generality, we can take $\Pi_0 = \{\{v\}~|~v \in V\}$ to be the finest possible partition, and $\Pi_k = V$ to be the coarsest. Taken as a whole, the hierarchy of nested partitions $T := (\Pi_0, \Pi_1,…, \Pi_k)$ can be represented in a direct acyclic graph (DAG) where nodes.
Metrics
- Weighted adjacency matrix $A_w = {[} A_{u,v}:= w(u,v){]}_{u,v \in V}$
- Weighted degree matrix $D_W = { [} \begin{cases} \deg_w(u) & \text{if}~u=v \\ 0 & \text{else}\end{cases} { ]}_{u,v \in V}$
- $\deg_w(u) := \sum_{\{u,v\}\in E} w(u,v)$
- Modularity is defined per partition as follows: $M(G, \Pi,w) := \frac{1}{2 |E|} \sum_{u,v}{(} A_{uv} – \frac{\deg_w(u)\deg_w(v)}{2|E|} {)} \delta(u, v)$, where $\delta(u,v):= \begin{cases} 1 & \text{if}~p_{\Pi}(u)=p_{\Pi}(v)\\ 0 & \text{else} \end{cases}$ and $p_{\Pi}: V \in u \mapsto P \in \Pi$ is the map that assigns each vertex uniquely to a partition. We hence use modularity to quantify the quality of a vertex partition, i.e., the added value over a random partitioning of vertices.
Algorithms
A weighted average-linkage agglomerative clustering, adapted from Sokal–Michener/UPGMA
Input: weighted graph G=(V,E,w), w:E->[0,1]
P0 := {{v} : v in V}; H := P0; t := 0
Define W(A,B) := average{ w(u,v) : u in A, v in B, {u,v} in E }, default 0
while |Pt| > 1:
choose distinct A,B in Pt maximizing W(A,B)
C := A ∪ B
Pt+1 := (Pt \ {A,B}) ∪ {C}
add dendrogram node C with children A,B
t := t+1
return P0,...,Pt and dendrogram nodes HA. Loukas-style local-variation multi-level graph coarsening
Input: weighted G0=(V0,E0,w0), target sizes n0>...>nk
P0 := {{v}: v∈V0}
for i = 0,...,k-1:
form candidate connected sets C ⊆ Vi, e.g. edges or small stars
for each C compute local-variation score LV(C)
// spectral error caused by contracting C
greedily choose disjoint candidates with smallest LV(C)
until |Vi+1| ≈ n_{i+1}
contract each chosen C into one supernode; keep unchosen nodes singleton
define Gi+1 as quotient graph with summed inter-block weights
lift each supernode/block back to its subset of original V0
Pi+1 := partition of V0 induced by those lifted blocks
return P0,...,Pk and quotient graphs G0,...,GkNote the difference in objectives: linkage optimizes similarity between nodes while Loukas’s minimizes spectral distortion.
Examples
We generate synthetic examples in a process that can be thought of as the reverse of graph coarsening. Successive levels spawn multiple interconnected nodes in the places of previous nodes.
regular bottom-up clustering
A. Loukas’s local-variation multi-level graph coarsening
| metric\method | bottom-up | Loukas |
|---|---|---|
| Modularity of partition 1 | 0.753680 | 0.660973 |
| Modularity of partition 2 | 0.869930 | 0.838135 |
| Modularity of partition 3 | 0.756068 | 0.593664 |
Observe that we did not show the trivial partitions.
Conclusion
When considering hierarchical clusters, one must keep in mind that no single method is canonical, nor are they arbitrary (except for random ones). Each hierarchy is driven by a metric/method, which shapes the structure it detects. In a trite sense, what we find is defined by what we search for and how we search for it.