How do you set sigma for the Gaussian similarity kernel?
Updated Answer

According to a reference paper in Spectral Clustering (von Luxburg) the $\sigma$ is simply set to 1. A further tuning can be applied with some visualization inspection but I did not find any discussion regarding setting this parameter.

Using code snippet below you see the effect:

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import pdist

def gausker(x1,x2,sigma):
    dist = np.linalg.norm(x1-x2)
    return np.exp(-dist**2/(2.*(sigma**2.)))

data = np.array([[0,0],[1,1],[1,0],[0,1],[10,10],[10,9],[9,10],[9,9]])
plt.figure()
plt.plot(data[:,0],data[:,1],'o',ms=20)
plt.show()
s = np.std(pdist(data))
for sigma in [1, s, 10, 100]:
    gaus = np.zeros((8,8))
    for ii in range(8):
        for jj in range(8):
            gaus[ii,jj] = gausker(data[ii,:],data[jj,:],sigma)
    plt.figure()
    plt.imshow(gaus,extent=[0, 1, 0, 1])
    plt.colorbar()
    plt.title(str(sigma))
    plt.show()


For Machine Learning algorithms is better to have more distinction. The Gaussian similarity kernel cares about local similarities. The image show the kernel for $\sigma=1$ 

Conceptually is similar to a k-nearest neighbors graph, since it considers local neighborhood and almost disregards the relationship between two nodes far apart.