Opened 8 years ago

Closed 3 months ago

#10482 closed enhancement (invalid)

Add Weisfeiler-Lehman algorithm to sage.graphs

Reported by: kini Owned by: kini
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords: weisfeiler-lehman algorithm, graphs, coherent configurations, refinement
Cc: Merged in:
Authors: Keshav Kini Reviewers:
Report Upstream: N/A Work issues: fix the bug with wl-bug example
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by chapoton)


See this sage-devel thread.

Adding an implementation of the Weisfeiler-Lehman algorithm for partition / graph refinement.

Apply

*trac_10482-wlrefine_rebased.patch

Attachments (4)

trac_10482-wlrefine (43.0 KB) - added by kini 8 years ago.
patch to be applied to sage-main repository
trac_10482-wlrefine.patch (43.0 KB) - added by kini 8 years ago.
Sorry, here it is with a ".patch" extension. To be applied to sage-main.
wl-bug (12.1 KB) - added by dimpase 8 years ago.
64x64 matrix with automorphisms (16 of them), which WL does not see - returns all the 642 colours
trac_10482-wlrefine_rebased.patch (42.8 KB) - added by dimpase 6 years ago.
rebased for Sage 5.12 (the bug not fixed...)

Download all attachments as: .zip

Change History (25)

Changed 8 years ago by kini

patch to be applied to sage-main repository

Changed 8 years ago by kini

Sorry, here it is with a ".patch" extension. To be applied to sage-main.

comment:1 Changed 8 years ago by dimpase

  • Description modified (diff)

this all works OK (on sage 4.6.1.alpha3); what I do not know is whether GraphWL should be installed as a method for graphs.

Dima

comment:2 Changed 8 years ago by dimpase

  • Description modified (diff)
  • Milestone set to sage-4.6.2

comment:3 Changed 8 years ago by kini

  • Authors set to Keshav Kini
  • Status changed from new to needs_review

Sorry, didn't realize I should have marked this as "needs review".

By the way, something I wasn't able to figure out - why (with this patch applied) does sage.graphs.wlrefine.sage alias to sage (the top-level module)? Why does sage.graphs.wlrefine.sage even appear in the first place?

comment:4 Changed 8 years ago by dimpase

  • Status changed from needs_review to needs_work

Can we have a mildly interesting example in the doctest, i.e. refining which does not produce an orbital-induced refinement? The smallest non-directed example like this is the Shrikhande strongly regular graph on 16 vertices; a the smallest directed example a certain tournament on 15 vertices.

Shrikhande graph is mentioned on #9136. Maybe you can contribute its Sage implementation along the way!

comment:5 Changed 8 years ago by dimpase

just a reminder that this must be fixed soon...

comment:6 follow-up: Changed 8 years ago by kini

Sorry about that - I was planning to rebase on 4.7 after it comes out (as this is clearly not getting into Sage by then). Is that OK? If not I'll rebase on 4.7.rc2 (there have been some changes to the patch since I created this ticket).

comment:7 in reply to: ↑ 6 Changed 8 years ago by dimpase

Replying to kini:

Sorry about that - I was planning to rebase on 4.7 after it comes out (as this is clearly not getting into Sage by then). Is that OK? If not I'll rebase on 4.7.rc2 (there have been some changes to the patch since I created this ticket).

it works on 4.7.rc1, I didn't check rc2.

Changed 8 years ago by dimpase

64x64 matrix with automorphisms (16 of them), which WL does not see - returns all the 642 colours

comment:8 Changed 8 years ago by dimpase

I attached an example of 64x64 matrix with nontrivial automorphisms, which WL does not see, and colours every matrix entry in its own colour.

comment:9 Changed 6 years ago by dimpase

an optimal canonical labellling algorithm is described here: http://www.automata.rwth-aachen.de/~grohe/pub/berbongro13.pdf It runs in O((n+m)log n) time, with n, resp. m, being #of vertices (resp. edges). (that's not the problem on this ticket though, it's a coarser classification of vertices)

Last edited 6 years ago by dimpase (previous) (diff)

comment:10 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 6 years ago by dimpase

rebased for Sage 5.12 (the bug not fixed...)

comment:11 Changed 6 years ago by dimpase

  • Cc dimpase@… removed
  • Description modified (diff)
  • Work issues set to fix the bug with wl-bug example

comment:12 follow-up: Changed 6 years ago by kini

I'm not sure what to do with this now. As I recall, I did try stepping carefully through the code back in 2011, and it was doing what I expected it to do, and as far as I could tell it also matched what's written in the paper I based the code on. Yet the answer is wrong for the wl-bug case.

So either the code doesn't do what I thought it did after all (certainly possible), or I misread the paper or other resources in some subtle way, or the algorithm in the paper is wrong in some subtle way (I wrote STABIL.c more or less completely based on the description of the algorithm in the paper and not on the original code, which does work on wl-bug). I'm not sure which of these is the case, and now I don't any longer remember the code I wrote or the contents of the paper well enough to try to find out which of these is the case.

Perhaps at this point the better solution is to just use the old code (which is what you originally suggested in 2010). My code was supposed to allow for a wider variety of input and more memory usage than made sense back in the 80s, but all of that is worthless if the output is not correct... :(

comment:13 in reply to: ↑ 12 Changed 6 years ago by dimpase

Replying to kini:

I'm not sure what to do with this now. As I recall, I did try stepping carefully through the code back in 2011, and it was doing what I expected it to do, and as far as I could tell it also matched what's written in the paper I based the code on. Yet the answer is wrong for the wl-bug case.

The strategy for debugging is obvious: what happens, mathematically, is that a basis of 0-1 matrices for a matrix algebra is built incrementally. One just has to trace this carefully: at some point instead of creating a minimal 0-1 basis, the procedure breaks. This might need a bit of extra code, allowing outputting the current basis in some "dumb" machine-readable form at any iteration. Then you can compare what happens in the implementation (it computes the product A_i A_j of two (presumed-)basis elements {A_k}, each of them represented as a linked list, and tries to decompose it into a Z-linear combination of the A_k's. When it fails, this means that it has to locate an A_k that needs to be spit into a number of 0-1 matrices, do this splitting, etc).

comment:14 Changed 6 years ago by dimpase

By the way, what about STABIL-tests.h, mentioned in STABIL.c? Is it available anywhere?

comment:15 Changed 6 years ago by kini

There was at one point a repository containing this code and the original files from stabprogs.tgz. I think it was on www1.spms.ntu.edu.sg, but my directory there has been cleaned out by now... I found an old clone of it on banana just now, though. I put it up at http://github.com/kini/stabprogs and gave you access to it. I added a testing script, and formatted the wl-bug adjacency matrix like the other input files and added that too. STABIL-tests.h is there as well and as you can see, it does something like what you described in comment 13. Well, not that machine-readable, I suppose...

comment:16 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:17 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:18 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:19 Changed 5 months ago by chapoton

  • Description modified (diff)
  • Keywords weisfeiler-lehman added; weisfeiler-leman removed
  • Summary changed from Add Weisfeiler-Leman algorithm to sage.graphs to Add Weisfeiler-Lehman algorithm to sage.graphs

comment:20 Changed 5 months ago by dimpase

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from needs_work to positive_review

The bug is not going to be fixed by the author. This is superseded by #25802, with a much better implementation.

comment:21 Changed 3 months ago by embray

  • Resolution set to invalid
  • Status changed from positive_review to closed

Presuming these are all correctly reviewed as either duplicate, invalid, or wontfix.

Note: See TracTickets for help on using tickets.