LAGr_MarkovClustering inconsistent/ different result to micans

[pfmephisto]

Hi,

I am not sure if it's my use of LAGr_MarkovClustering that is wrong, but I can't get it to consistently produce the results that I expect.

I have the following test dataset which should result in 3 clusters but when running it through the LAGr_MarkovClustering algorithm it results in as many clusters as there are nodes, though passing the same dataset through the micans mcl implementation indeed result in 3 clusters. Sometimes by reducing the adjacency matrix I have managed to get it to produce the correct clusters or using inflation values < 1. I also had a look at the experimental/benchmark/mcl_demo.c file but so far I can not see what the issue might be.

Link to my code and a link to the test data

Image of the adjacency matrix:

[DrTimothyAldenDavis]

The result of Markov clustering isn't unique, so maybe that's what's going on here. It depends on the expansion coefficient and inflation coefficients.

There's a weird part of the code where the input parameter "i" is shadowed by a loop variable. That should be rewritten I think. See:

LAGraph/experimental/algorithm/LAGr_MarkovClustering.c

Lines 157 to 167 in e2539e2

	// subsequent expansion steps
	for (int i = 1; i < e - 1; i++)
	{
	// T = T^2
	GRB_TRY(GrB_mxm(T, NULL, NULL, GrB_PLUS_TIMES_SEMIRING_FP32,
	T, T, NULL));
	}
	// Inflation step
	GRB_TRY(GrB_Matrix_apply_BinaryOp2nd_FP32(
	T, NULL, NULL, GxB_POW_FP32, T, (double)i, NULL));

I think the input parameter "i" should be renamed, and it likely should be a double, not an int, anyway.

However, this code wierdness doesn't mean the method is flawed. Just strange.

So I'm not sure why you're seeing the results you are seeing. Unless it's because the coefficients differ.

Cam's algorithm is desribed in his Honors Thesis, a copy of which is in the papers/ folder. I can take a look at it, and the code, to see if I can understand where your result differs from the LAGr_MarkovClustering method in LAGraph.

[pfmephisto]

Thanks a lot for looking in to this. In my local version, I also patched the inflation parameter to be a double, though I wouldn’t expect that alone to change the clustering outcome. Most of my tests have been with both inflation and expansion set to 2.

As for the micans implementation, I don’t think it allows configuring the expansion factor and seems to be hard-coded to 2.
I’d really appreciate any help I can get as I'm not quite sure where to start.