# Introducing weights into spectral clustering

Suppose I have a data set with points $x_i$ and a dissimilarity measure $d_{ij}$ between each pair, as well as a weight $w_{ij}$ that qualifies the quality of this dissimilarity. I have two problems:

• The first one is how to introduce weights when performing spectral clustering. Like in the Shi-Malik, Ng-Jordan-Weiss versions, where only the distances are used.

• The second one is that my dissimilarity measure does not exists sometimes. In these cases, it has zero weight. How to introduce these cases in the algorithm? I suppose the zero weight solves the problem if I know how to introduce them.

An idea I had is to perform the similarity transformation as: $$s_{ij} = w_{ij} e^{-\frac{d^2_{ij}}{\sigma^2}}$$ but I feel it does not make sense since the weigth should reflect the importance of the measure, not the measure itself.

The data is not Euclidean, so I can use only this dissimilarity measure. Any reference is appreciated.

• Does "my dissimilarity measure does not exists sometimes" mean that you have missing data ro the dissimilarity is zero? Nov 9 '15 at 23:53
• The dissimilarity is a function between two points that is sometimes not defined. There is no reasonable value to give. Nov 10 '15 at 12:48

What happens in Spectral Clustering is simply finding some blocks in the data according to the property for which your matrix is defined. If it's similarity you get the similar data points.

• The first one is how to introduce weights when performing spectral clustering. Like in the Shi-Malik, Ng-Jordan-Weiss versions, where only the distances are used.

Do not get confused. All what you need is to introduce your similarity measure which can be weighted. Just insert all the weights into a classical spectral clustering version (Shi-Malik or Ng or whatever) and there you go!

• The second one is that my dissimilarity measure does not exists sometimes. In these cases, it has zero weight. How to introduce these cases in the algorithm? I suppose the zero weight solves the problem if I know how to introduce them.

I think this should not be a big issue. Just put zero and try your algorithm with a mock data and see what happens. If didn't work, try to fill missing values by some statistical indicators e.g. mean of the data and see the result.