Kernels and, broadly speaking, similarity measures on
graphs are extensively used in graph-based unsupervised and semisupervised
learning algorithms as well as in the link prediction problem.
We analytically study proximity and distance properties of various kernels
and similarity measures on graphs. This can potentially be useful
for recommending the adoption of one or another similarity measure in
a machine learning method. Also, we numerically compare various similarity
measures in the context of spectral clustering and observe that
normalized heat-type similarity measures with log modification generally
perform the best.