We consider a number of graph kernels and proximity measures including
commute-time kernel, regularized Laplacian kernel, heat kernel, exponential diffusion
kernel (also called “communicability”), etc., and the corresponding distances
as applied to clustering nodes in random graphs and several well-known datasets.
The model of generating random graphs involves edge probabilities for the pairs of
nodes that belong to the same class or different predefined classes of nodes. It turns
out that in most cases, logarithmic measures (i.e., measures resulting after taking
logarithm of the proximities) perform better while distinguishing underlying classes
than the “plain” measures. A comparison in terms of reject curves of interclass and
intra-class distances confirms this conclusion. A similar conclusion can be made for
several well-known datasets. A possible origin of this effect is that most kernels have
a multiplicative nature, while the nature of distances used in cluster algorithms is an
additive one (cf. the triangle inequality). The logarithmic transformation is a tool to
transform the first nature to the second one. Moreover, some distances corresponding
to the logarithmic measures possess ameaningful cutpoint additivity property. In our
experiments, the leader is usually the logarithmic Communicability measure. However,
we indicate some more complicated cases in which other measures, typically,
Communicability and plain Walk, can be the winners.