Back to MPhil? Oh, and the multi-matching is broken too

Interesting week this week, so most annoying and worrisome topic first: looks like I am still an MPhil student. It has become delightfully apparent that the examiners have not yet sent the Assessment Outcome form (of MPhil to PhD), and so as a result, I am still registered as an MPhil student. I just hope it doesn't interfere with my plans for finishing in 3 years (the Research Committee have been stubborn regarding forms in the past, and if they read the form as me having just completed the transfer, may dislike the idea of me trying to go for PhD with such small amount of time left).

Now that I have complained about it a little, I can move on to the next complaint: the multi-matching and its dislike of certain graphs. In the past few posts, I have reported good results regarding the reduction of runtime for many smaller graphs; however, tests on larger graphs took longer to run and so I was left waiting for those results.

It seems only a few of these tests came back with positive results, with some, specifically finan512, coming back with much higher runtimes (nearly 8x the original runtime measured in the Redosmium/MGF implementation). This extended runtime exists for all matching techniques, including the standard edge contraction.

The main difference in algorithms is the multi-matching, which relies on adjacent vertices being stored as a collection that is associated with individual vertices (similar to Walshaw, O(2E)), as opposed to the previous method of storing them as a separate collection (O(E)). Having received results for smaller graphs which were similar to the MGF, it was an assumption that the new coarsening algorithm and method of storing worked as it should of - these new results suggest differently.

As mentioned, finan512 has the unusually high runtime. Some analysis shows that the number of levels in the multilevel scheme has risen from 35 (on average) to over 600; reinforcing the notion that the problem lies in the coarsening scheme. Having investigated, it is difficult to see where the problem is coming from - the coarsening scheme runs as expected for smaller graphs.

Unable to see the problem, I have begun getting restless and irritated (perhaps why this MPhil thing has annoyed me more than it should). In any case, I plan to look at why finan512 and sierpinski10 have issues while others, such as dime20, do not, and if possible, fix this multi-matching/coarsening scheme so I can get some reliable results.

As a finishing note, it's been a while since I have shown any pictures of output, so here's two more recent layouts I have found particularly pleasing or interesting.

add20 drawn using a circular placement primitive (originally for smaller star type graphs but accidentally applied to the original graph - oddly enough).

dime20 drawn very quickly with a matching number of vertices (so any vertices with 7 or less adjacent vertices coarsened at once). The layout is very pleasing and seems not to show any issues with the local layout, however, the global layout appears tangled still. Investigation into the cause would be ideal (and would help global layout generation for huge graphs) but due to the above problem with multi-matching, is not yet a concern.