Opened 9 years ago
Closed 13 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 )
Adding an implementation of the Weisfeiler-Lehman algorithm for partition / graph refinement.
Apply
Attachments (4)
Change History (25)
Changed 9 years ago by
comment:1 Changed 9 years ago by
- 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 9 years ago by
- Description modified (diff)
- Milestone set to sage-4.6.2
comment:3 Changed 9 years ago by
- 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 9 years ago by
- 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 9 years ago by
just a reminder that this must be fixed soon...
comment:6 follow-up: ↓ 7 Changed 9 years ago by
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 9 years ago by
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 9 years ago by
64x64 matrix with automorphisms (16 of them), which WL does not see - returns all the 64^{2 colours }
comment:8 Changed 9 years ago by
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 7 years ago by
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)
comment:10 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:11 Changed 6 years ago by
- Cc dimpase@… removed
- Description modified (diff)
- Work issues set to fix the bug with wl-bug example
comment:12 follow-up: ↓ 13 Changed 6 years ago by
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
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
By the way, what about STABIL-tests.h
, mentioned in STABIL.c
? Is it available anywhere?
comment:15 Changed 6 years ago by
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 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:17 Changed 6 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:18 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:19 Changed 16 months ago by
- 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 16 months ago by
- 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 13 months ago by
- Resolution set to invalid
- Status changed from positive_review to closed
Presuming these are all correctly reviewed as either duplicate, invalid, or wontfix.
patch to be applied to sage-main repository