6
$\begingroup$

I am currently trying to partition a scale-free ("big") graph (around 20k vertices, 500k edges) into appropriate sub-graphs. Having derived the Laplacian of the graph, I tried running an approach based on the spectral gap and Fiedler-vector, however, not really unexpectedly, ended up with vertex valuations (i.e. components of the corresponding eigenvector) being close to zero for a majority of the nodes. Clearly, there is no obvious cut in the graph.

Nevertheless, even if it's just for the sake of showing that several methods fail on graphs following the spectral features of the one I am working on, I would like to further explore spectral clustering approaches - some of which require a fixed k denoting the number of partitions.

I am aware of the use of the BIC and AIC with respect to k-means-clustering. What would interest me is, whether these criteria are also used in the realm of spectral graph clustering? Is there any rationale allowing to establish a link between the spectra of graphs and model selection criteria like the BIC and AIC?

Any input is much appreciated!


Additions:

So, I have run a few tests. I have tried RSB with the median for the cutoff value c. I used high-evidence (low false positive rate, possibly high false negative rate) cluster-data to validate against (roughly ~250 non-overlapping groups), in a rather "poor man's" fashion, so nothing fancy at all. The initial cut already affected more than 235 clusters, even though many of them are actually rather small (we are talking about an avg. of around 75 here). I tried deviating from the median by the MAD (towards the valuation with the highest absolute value) which resulted in a bad performance as well. After some further tries, I ended up choosing the 1st- or 3rd-quartile of the valuation distribution, which allowed some small and rather trivial cuts. Nevertheless, the spectral gap never looked promising and the characteristic valuation simply horrible.

For computing them I used ARPACK (IRLM), so I expect the results to be considerably accurate in double precision. Here's a plot of the characteristic valuation (log2, just quick and dirty) after the first 2 iterations (which both yielded 2 clusters of roughly 36 nodes each) - the core seems to be too dense.

run0 run1

I thought about at least buying Fan Chung's more recent book on spectral clustering (spectral clustering), since I liked reading through the previous work (at least the first two chapters). They were dry to the bone, but nevertheless quite informative.

$\endgroup$
  • 1
    $\begingroup$ What I know so far about using AIC or BIC as internal clustering criterion is that the number of parameters in its formula is the product of the number of clusters and the number of variables (dimensions). Thereby it is questionable whether AIC/BIC is applicable to a graph (a similarity matrix) unless it is put into space of some dimensions, that is, become objects X variables data. $\endgroup$ – ttnphns Jul 9 '12 at 17:24
  • $\begingroup$ @ttnphns: Thank you for your comment. I wonder if that could be achieved by reformulating the problem as a vector clustering problem. Being neither an expert in one or the other field, the main purpose of this post was to ask for approaches that might have already been pursued. $\endgroup$ – limbonic Jul 10 '12 at 16:46
  • $\begingroup$ You always can translate a similarity-of-objects matrix into objects X dimensions data by means of Multidimensional Scaling (MDS) with minimal lost of information. Then you can use AIC/BIC-based clustering criterion to find the optimal number of clusters. On my web-page, there's a SPSS macro to compute it (if you use SPSS). $\endgroup$ – ttnphns Jul 10 '12 at 18:13
  • $\begingroup$ I am not using SPSS, but thanks for the pointer, I will check it out! $\endgroup$ – limbonic Jul 10 '12 at 20:11
  • 2
    $\begingroup$ Tangential remark: I've always thought that for many purposes and many algorithms 'scale-freeness' obfuscates cluster structure, due to the large pull exerted by hub nodes. It depends on the application, but I would usually look for a way to filter out hub nodes. Have you considered algorithms like Louvain (which yields a tree), Affinity Propagation clustering and MCL? The latter two do not require the number of clusters to be set (but have parameters that affect coarseness). They probably won't work well on a scale-free network though. $\endgroup$ – micans Jul 11 '12 at 9:00
3
$\begingroup$

AIC and BIC are used for constraining the complexity of a range of models competing to explain the same data. Following on the heels of results in complexity theory and machine learning, there is reason to believe that in some scenarios, using these proxies for complexity gives useful info about the model that explains the data best while having the smallest generalization error.

In this case, you would first need to propose some model that produces the graph spectra you are seeing. You could postulate some different components that produce the graph you see, such as a mixture model.

For example, if you were working with the common telephone data set from Belgium (where there is a trivial cut to make between those who speak French and those who speak Dutch), you would need to postulate the mechanism (language preference correlated to region or something) that actually causes the two different segments of the graph.

Then, once you have a model, you would use AIC or BIC as a means for optimizing the parameter choices for fitting that model with your observed graph data. If the number of different causal clusters is something you include in the model, then it's something your optimization routine will spit back out under AIC or BIC constraints.

But it's not really the same thing as normalized cut, which does not exactly model anything about the graph. Normalized cut (and other spectral segmentation methods) proposes a cost function that may or may not be related to anything about your graph, and then makes cuts so as to minimize the cost.

If the cost functional used by the segmentation method does not meaningfully correspond to aspects of the data generating process that gives rise to your graph, then the segmentation performance can be arbitrarily bad. As you say, this is a reason why one-size-fits-all graph cutting procedures must be used delicately, with careful consideration of what the cost functional means for your data.

I have a few sources for this, and I'll come back and document it later this evening.

$\endgroup$
  • $\begingroup$ Thank you for your post! I will have to think this through. During the last months, I have been reading up on bits and chunks in the realm of graph theory, not really concentrating on anything in particular. Personally, I would like to deviate from the idea of global clustering anyway, since it simply does not seem feasible for real-world networks you come across nowadays. Most optimization criteria in the end come down to more the less the same results. From as descriptive point of view, I found Leskovec's Papers quite interesting. Looking forward to your additions (if you find the time)! $\endgroup$ – limbonic Jul 10 '12 at 20:16
  • $\begingroup$ @EMS, also Looking forward to your additions, thanks $\endgroup$ – denis Jul 17 '12 at 12:14
  • $\begingroup$ Thanks for the reminder; it's just been very busy at work. I will get to it shortly though. $\endgroup$ – ely Jul 17 '12 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.