4603:. This illustrates the phenomenon about labels depending on the execution order of the WLtest on the nodes. Either one finds another relabeling method that keeps uniqueness of labels, which becomes rather technical, or one skips the relabeling altogether and keeps the label strings, which blows up the length of the certificate significantly, or one applies WLtest to the union of the two tested graphs, as we did in the variant WLpair. Note that although
4695:
4686:
4677:
4067:
4058:
4168:
4159:
4049:
233:
4177:
80:
22:
2168:
Note that there is one major difference between k-WL and k-FWL: k-FWL checks what happens if a single node w is placed at any position of the k-tuple (and then computes the multiset of these k-tuples) while k-WL looks at the multisets that you get when changing the i-th component only of the original
4751:
are method to preprocess such graph based nonlinear data to simplify subsequent learning methods. Such graph kernels can be constructed by partially executing a
Weisfeiler Leman test and processing the partition that has been constructed up to that point. These Weisfeiler Leman graph kernels have
400:
is the number of nodes of the input graph as it has to split one partition in every refinement step and this can happen at most until every node has its own color. Note that there are graphs for which one needs this number of iterations, although in practice the number of rounds until terminating
1744:
1960:
949:
432:
Weisfeiler-Leman algorithm (k-FWL) are extensions of 1-WL from above operating on k-tuples instead of individual nodes. While their difference looks innocent on the first glance, it can be shown that k-WL and (k-1)-FWL (for k>2) distinguish the same pairs of graphs.
719:
1389:. For example, a 2-tuple has only two possible atomic types, namely the two nodes may share an edge, or they do not. Note that if the graph has multiple (different) edge relations or additional node features, membership in those is also represented in
1318:
214:
apart, then they are definitely different, but the other direction does not hold: for every variant of the WL-test (see below) there are non-isomorphic graphs where the difference is not detected. Those graphs are highly symmetric graphs such as
4407:
1569:
524:
1520:
4526:
290:(the difference has to do with non-edges and is irrelevant for all practical purposes as it is trivial to see that graphs with a different number of nodes are non-isomorphic). The algorithm proceeds as follows:
351:. One can then look at the histogram of colors of both graphs (counting the number of nodes after color refinement stabilized) and if they differ, this is a certificate that both graphs are not isomorphic.
1802:
783:
573:
4137:
4242:
1105:
4288:
2114:
2008:
997:
1798:
250:
1427:
1358:
779:
4622:
even if they have the same order. In fact WLtest terminates after a single round as seen in these examples of order 8, which are all 3-regular except the last one which is 5-regular.
1562:
566:
1168:
2143:
1387:
1163:
1134:
2065:
1054:
4546:
343:(after one iteration) might mean `a node with exactly 5 neighbors of color 0'. In practice this is achieved by running color refinement on the disjoint union graph of
2196:
4566:
2035:
1024:
404:
The refinement of the partition in each step is by processing for each node its label and the labels of its nearest neighbors. Therefore WLtest can be viewed as a
378:
2198:). Since both algorithms scale exponentially in k (both iterate over all k-tuples), the use of k-FWL is much more efficient than using the equivalent (k+1)-WL.
2163:
398:
182:
There are several versions of the test (e.g. k-WL and k-FWL) referred to in the literature by various names, which easily leads to confusion. Additionally,
4293:
1739:{\displaystyle c_{w}^{\ell }({\bar {v}})={\big (}c^{\ell -1}({\bar {v}}\!\!\leftarrow \!w),\dots ,c^{\ell -1}({\bar {v}}\!\!\leftarrow \!w){\big )}}
4752:
attracted considerable research in the decade after their publication. They are also implemented in dedicated libraries for graph kernels such as
447:
5022:
This
Weisfeiler Lehman framework operates on top of existing graph kernels and is inspired by the Weisfeiler-Lehman test of graph isomorphism .
1446:
4851:
4412:
4694:
1432:
The key idea of k-WL is to expand the neighborhood notion to k-tuples and then effectively run color refinement on the resulting graph.
1955:{\displaystyle c^{\ell }({\bar {v}})={\text{Hash}}{\big (}c^{\ell -1}({\bar {v}}),\{\!\{c_{w}^{\ell }({\bar {v}}):w\in V\}\!\}{\big )}}
944:{\displaystyle c^{\ell }({\bar {v}})={\text{Hash}}(c^{\ell -1}({\bar {v}}),c_{1}^{\ell }({\bar {v}}),\dots ,c_{k}^{\ell }({\bar {v}}))}
4086:
WLpair takes 4 rounds on 'G1' and 'G2'. The test fails as the certificates disagree. From the previous two instances we already know
4685:
4676:
272:
120:
61:
4960:
4784:
102:
4779:
applied in heuristic algorithms to reduce the computational cost for solving problems of high complexity such as instances of
4066:
4057:
4048:
254:
2678:
714:{\displaystyle c_{i}^{\ell }({\bar {v}})=\{\!\{c^{\ell -1}({\bar {w}}):{\bar {w}}\in {\mathcal {N}}_{i}({\bar {v}})\}\!\}}
4198:
of the graph isomorphism problem. Note that not every map of vertices that respects the labels gives an isomorphism. Let
149:
4611:
can get distinct certificates when WLtest is executed on them separately, they do get the same certificate by WLpair.
4089:
206:
and output a certificate that they are different or 'I don't know'. This means that if the heuristic is able to tell
4201:
1061:
287:
195:
176:
160:
4247:
4167:
4158:
2072:
4764:
4618:. WLtest cannot distinguish regular graphs of equal order, but WLpair can distinguish regular graphs of distinct
1967:
956:
98:
94:
1749:
4176:
4026:
1392:
1323:
724:
39:
32:
4915:
4980:
Shervashidze, Nino; Schweitzer, Pascal; Van
Leeuwen, Erik Jan; Mehlhorn, Kurt; Borgwardt, Karsten M. (2011).
4824:
Huang, Ningyuan; Villar, Soledad (2022), "A Short
Tutorial on the Weisfeiler-Lehman Test and Its Variants",
4740:
2276:# dictionary that will provide translation from a string of labels of a node and its neighbors to an integer
2172:
It can be shown (although only through the connection to logic) that k-FWL and (k+1)-WL are equivalent (for
243:
4194:
are isomorphic. Any isomorphism must respect the components and therefore the labels. This can be used for
4744:
1525:
529:
5040:
4079:
WLpair takes 4 rounds on 'G0' and 'G2'. The test fails as the certificates disagree. Indeed 'G0' has a
1313:{\displaystyle {\mathcal {N}}_{i}({\bar {v}})=\{(v_{1},\dots ,v_{i-1},w,v_{i+1},\dots ,v_{k}):w\in V\}}
331:
In order to use this algorithm as a graph isomorphism test, one runs the algorithm on two input graphs
5010:
4801:
4720:
4705:
4080:
409:
4826:
ICASSP 2021 - 2021 IEEE International
Conference on Acoustics, Speech and Signal Processing (ICASSP)
4857:
4829:
405:
172:
4739:
to represent the data in a high dimensional feature space after which linear techniques such as
2119:
1363:
1139:
1110:
175:, a normal form for graphs, while there is also a combinatorial interpretation in the spirit of
89:
may contain an excessive amount of intricate detail that may interest only a particular audience
2043:
1032:
4847:
4796:
4531:
145:
4981:
4882:
2175:
420:
This is the place where the aforementioned two variants of the WL algorithm appear. Both the
4874:
4839:
4768:
4753:
4732:
328:
The algorithm ends if the partition induced by two successive refinement steps is the same.
164:
4551:
2417:# a combination of labels from the node and its neighbors is encountered for the first time
2013:
1002:
4883:"A Reduction of a Graph to a Canonical Form and an Algebra Arising during This Reduction"
357:
2148:
383:
216:
43:
4787:. As stated above the Weisfeiler Leman test can also be applied in the later context.
4076:
WLpair takes 3 rounds on 'G0' and 'G1'. The test succeeds as the certificates agree.
5034:
4861:
4843:
4776:
4760:
4736:
4704:
Another example of two non-isomorphic graphs that WLpair cannot distinguish is given
4619:
4615:
4402:{\displaystyle \varphi (a)=D,\varphi (b)=C,\varphi (c)=B,\varphi (d)=E,\varphi (e)=A}
4195:
306:
get a different color if a) they had a different color before or b) there is a color
4936:
4878:
4772:
4748:
2169:
k-tuple. It then uses all those multisets in the hash that computes the new color.
183:
168:
137:
1136:
is given by the set of all k-tuples reachable by exchanging the i-th position of
232:
38:
The references used may be made clearer with a different or consistent style of
101:
any relevant information, and removing excessive detail that may be against
4961:"Expressive Power Of Graph Neural Networks And The Weisfeiler-Lehman Test"
4083:
of length 5, while 'G2' doesn't, thus 'G0' and 'G2' cannot be isomorphic.
519:{\displaystyle c^{0}({\bar {v}})={\text{Hash}}({\text{type}}({\bar {v}}))}
1515:{\displaystyle c^{0}({\bar {v}})={\text{Hash}}({\text{type}}({\bar {v}})}
1360:
of a tuple encodes the edge information between all pairs of nodes from
286:
The 1-dimensional graph isomorphism test is essentially the same as the
4780:
339:
in parallel, i.e. using the colors when splitting such that some color
257: in this section. Unsourced material may be challenged and removed.
4521:{\displaystyle \psi (a)=B,\psi (b)=C,\psi (c)=D,\psi (d)=E,\psi (e)=A}
2429:# assign the string of labels to a new number as an abbreviated label
4834:
226:
73:
15:
1175:
1068:
675:
2681:
code which includes the description of the first examples.
2441:# increase the counter for assigning new abbreviated labels
4719:
The theory behind the
Weisfeiler Leman test is applied in
2219:# OUTPUT: Certificates for G and H and whether they agree
4743:
can be applied. Data represented as graphs often behave
2216:# INPUT: two graphs G and H to be tested for isomorphism
4629:
has two connected components, while the others do not.
198:
are one-sided heuristics that take as input two graphs
4554:
4534:
4415:
4296:
4250:
4204:
4092:
2178:
2151:
2122:
2075:
2046:
2016:
1970:
1805:
1752:
1572:
1528:
1449:
1395:
1366:
1326:
1171:
1142:
1113:
1064:
1035:
1005:
959:
786:
727:
576:
532:
450:
386:
360:
2321:# set up the dictionary of labels for the next step
2264:# dictionary where every node gets the same label 0
190:
4938:Power and limits of the Weisfeiler-Leman algorithm
4647:WLtest applied to four regular graphs of order 8.
4560:
4540:
4520:
4401:
4282:
4236:
4131:
2190:
2157:
2137:
2108:
2059:
2029:
2002:
1954:
1792:
1738:
1556:
1514:
1421:
1381:
1352:
1312:
1157:
1128:
1099:
1048:
1018:
991:
943:
773:
713:
560:
518:
392:
372:
2102:
2098:
2097:
1941:
1889:
1722:
1718:
1717:
1661:
1657:
1656:
707:
616:
4132:{\displaystyle G_{1}\cong G_{0}\not \cong G_{2}}
296:All nodes are initialized with the same color 0
4237:{\displaystyle \varphi :G_{0}\rightarrow G_{1}}
2010:(both colorings induce identical partitions of
999:(both colorings induce identical partitions of
186:is spelled `Lehman' in several older articles.
4633:is 5-regular, while the others are 3-regular.
1100:{\displaystyle {\mathcal {N}}_{i}({\bar {v}})}
171:in 1968. The original formulation is based on
4625:All four graphs are pairwise non-isomorphic.
1947:
1844:
1731:
1611:
424:-dimensional Weisfeiler-Leman (k-WL) and the
8:
4819:
4817:
4283:{\displaystyle \psi :G_{0}\rightarrow G_{1}}
2109:{\displaystyle {\bar {v}}\!\!\leftarrow \!w}
1942:
1938:
1890:
1886:
1307:
1207:
708:
704:
617:
613:
144:is a heuristic test for the existence of an
4025:The first three examples are for graphs of
2145:where the i-th position is exchanged to be
2003:{\displaystyle c^{\ell }\equiv c^{\ell -1}}
992:{\displaystyle c^{\ell }\equiv c^{\ell -1}}
4693:
4684:
4675:
4175:
4166:
4157:
4065:
4056:
4047:
1793:{\displaystyle {\bar {v}}\in V^{k},w\in V}
4833:
4553:
4533:
4414:
4295:
4274:
4261:
4249:
4228:
4215:
4203:
4123:
4110:
4097:
4091:
2177:
2150:
2124:
2123:
2121:
2077:
2076:
2074:
2051:
2045:
2021:
2015:
1988:
1975:
1969:
1946:
1945:
1912:
1911:
1902:
1897:
1869:
1868:
1853:
1843:
1842:
1837:
1820:
1819:
1810:
1804:
1772:
1754:
1753:
1751:
1730:
1729:
1697:
1696:
1681:
1636:
1635:
1620:
1610:
1609:
1592:
1591:
1582:
1577:
1571:
1548:
1530:
1529:
1527:
1498:
1497:
1489:
1481:
1464:
1463:
1454:
1448:
1422:{\displaystyle {\text{type}}({\bar {v}})}
1405:
1404:
1396:
1394:
1368:
1367:
1365:
1353:{\displaystyle {\text{type}}({\bar {v}})}
1336:
1335:
1327:
1325:
1286:
1261:
1236:
1217:
1190:
1189:
1180:
1174:
1173:
1170:
1144:
1143:
1141:
1115:
1114:
1112:
1083:
1082:
1073:
1067:
1066:
1063:
1040:
1034:
1010:
1004:
977:
964:
958:
924:
923:
914:
909:
882:
881:
872:
867:
846:
845:
830:
818:
801:
800:
791:
785:
774:{\displaystyle {\bar {v}}\in V^{k},i\in }
747:
729:
728:
726:
690:
689:
680:
674:
673:
658:
657:
640:
639:
624:
596:
595:
586:
581:
575:
552:
534:
533:
531:
499:
498:
490:
482:
465:
464:
455:
449:
385:
359:
273:Learn how and when to remove this message
121:Learn how and when to remove this message
62:Learn how and when to remove this message
4916:"The Weisfeiler-Lehman Isomorphism Test"
4643:
4141:
4031:
4813:
354:The algorithm terminates after at most
142:Weisfeiler Leman graph isomorphism test
223:1-dimensional Weisfeiler-Leman (1-WL)
7:
4986:Journal of Machine Learning Research
4941:(PhD thesis). RWTH Aachen University
255:adding citations to reliable sources
133:Heuristic test for graph isomorphism
1557:{\displaystyle {\bar {v}}\in V^{k}}
561:{\displaystyle {\bar {v}}\in V^{k}}
4890:Nauchno-Technicheskaya Informatsia
14:
4982:"Weisfeiler-lehman graph kernels"
4959:Bronstein, Michael (2020-12-01).
1443:: a graph G = (V,E) # initialize
444:: a graph G = (V,E) # initialize
4844:10.1109/ICASSP39728.2021.9413523
231:
163:and has been first described by
159:. It is a generalization of the
78:
20:
401:tends to be very low (<10).
242:needs additional citations for
4727:Weisfeiler Leman graph kernels
4509:
4503:
4488:
4482:
4467:
4461:
4446:
4440:
4425:
4419:
4390:
4384:
4369:
4363:
4348:
4342:
4327:
4321:
4306:
4300:
4267:
4221:
2129:
2099:
2094:
2088:
2082:
1923:
1917:
1908:
1880:
1874:
1865:
1831:
1825:
1816:
1759:
1726:
1719:
1714:
1708:
1702:
1693:
1665:
1658:
1653:
1647:
1641:
1632:
1603:
1597:
1588:
1535:
1509:
1503:
1494:
1486:
1475:
1469:
1460:
1416:
1410:
1401:
1373:
1347:
1341:
1332:
1292:
1210:
1201:
1195:
1186:
1149:
1120:
1094:
1088:
1079:
938:
935:
929:
920:
893:
887:
878:
857:
851:
842:
823:
812:
806:
797:
768:
762:
734:
701:
695:
686:
663:
651:
645:
636:
607:
601:
592:
539:
513:
510:
504:
495:
487:
476:
470:
461:
1:
5011:"Weisfeiler Lehman Framework"
4775:are not to be confused with
416:Higher-order Weisfeiler-Leman
4914:Bieber, David (2019-05-10).
4568:constitutes an isomorphism.
103:Knowledge's inclusion policy
4735:of nonlinear data one uses
318:have a different number of
219:for 1-WL/color refinement.
179:and a connection to logic.
5057:
4614:The next example is about
3988:"Certificate 1:"
3970:"Certificate 0:"
2202:Examples and Code for 1-WL
2138:{\displaystyle {\bar {v}}}
1382:{\displaystyle {\bar {v}}}
1158:{\displaystyle {\bar {v}}}
1129:{\displaystyle {\bar {v}}}
408:which also connects it to
288:color refinement algorithm
161:color refinement algorithm
4783:problems in the field of
4765:artificial neural network
2060:{\displaystyle c^{\ell }}
1049:{\displaystyle c^{\ell }}
406:message passing algorithm
4595:when applying WLpair to
4571:When applying WLpair to
4541:{\displaystyle \varphi }
4006:"Test yields:"
2683:
2210:
4935:Kiefer, Sandra (2020).
4741:support vector machines
2191:{\displaystyle k\geq 2}
4828:, pp. 8533–8537,
4562:
4548:is not an isomorphism
4542:
4522:
4403:
4284:
4238:
4133:
2192:
2159:
2139:
2110:
2061:
2031:
2004:
1956:
1794:
1740:
1558:
1516:
1423:
1383:
1354:
1314:
1159:
1130:
1101:
1058:Here the neighborhood
1050:
1020:
993:
945:
775:
715:
562:
520:
394:
374:
4721:graph neural networks
4637:has no 3-cycle while
4591:gets the certificate
4587:. But the isomorphic
4563:
4561:{\displaystyle \psi }
4543:
4523:
4404:
4285:
4239:
4134:
2193:
2160:
2140:
2111:
2062:
2032:
2030:{\displaystyle V^{k}}
2005:
1957:
1795:
1741:
1559:
1517:
1424:
1384:
1355:
1315:
1160:
1131:
1102:
1051:
1021:
1019:{\displaystyle V^{k}}
994:
946:
776:
716:
563:
521:
410:graph neural networks
395:
375:
4802:Graph neural network
4669:of distinct degree.
4641:does have 3-cycles.
4552:
4532:
4413:
4294:
4248:
4202:
4090:
2677:Here is some actual
2176:
2149:
2120:
2073:
2044:
2014:
1968:
1803:
1750:
1570:
1526:
1447:
1393:
1364:
1324:
1169:
1140:
1111:
1062:
1033:
1003:
957:
784:
725:
574:
530:
448:
384:
358:
251:improve this article
2213:# ALGORITHM WLpairs
1907:
1587:
919:
877:
591:
373:{\displaystyle n-1}
322:-colored neighbors
4875:Weisfeiler, B. Yu.
4767:in the context of
4661:WLpair applied to
4650:WLpair applied to
4558:
4538:
4518:
4399:
4280:
4234:
4129:
2188:
2155:
2135:
2106:
2057:
2027:
2000:
1952:
1893:
1790:
1736:
1573:
1554:
1512:
1419:
1379:
1350:
1310:
1155:
1126:
1097:
1046:
1016:
989:
941:
905:
863:
771:
711:
577:
558:
516:
390:
370:
173:graph canonization
4853:978-1-7281-7605-5
4797:Graph isomorphism
4785:complexity theory
4702:
4701:
4290:be maps given by
4184:
4183:
4074:
4073:
2158:{\displaystyle w}
2132:
2085:
1920:
1877:
1840:
1828:
1762:
1705:
1644:
1600:
1538:
1506:
1492:
1484:
1472:
1413:
1399:
1376:
1344:
1330:
1198:
1152:
1123:
1091:
932:
890:
854:
821:
809:
737:
698:
666:
648:
604:
542:
507:
493:
485:
473:
393:{\displaystyle n}
283:
282:
275:
131:
130:
123:
72:
71:
64:
5048:
5025:
5024:
5019:
5018:
5007:
5001:
5000:
4998:
4997:
4977:
4971:
4970:
4968:
4967:
4956:
4950:
4949:
4947:
4946:
4932:
4926:
4925:
4923:
4922:
4911:
4905:
4904:
4902:
4901:
4887:
4871:
4865:
4864:
4837:
4821:
4769:machine learning
4733:machine learning
4697:
4688:
4679:
4658:of same degree.
4644:
4583:the certificate
4567:
4565:
4564:
4559:
4547:
4545:
4544:
4539:
4527:
4525:
4524:
4519:
4408:
4406:
4405:
4400:
4289:
4287:
4286:
4281:
4279:
4278:
4266:
4265:
4243:
4241:
4240:
4235:
4233:
4232:
4220:
4219:
4179:
4170:
4161:
4142:
4138:
4136:
4135:
4130:
4128:
4127:
4115:
4114:
4102:
4101:
4069:
4060:
4051:
4032:
4016:
4013:
4010:
4007:
4004:
4001:
3998:
3995:
3992:
3989:
3986:
3983:
3980:
3977:
3974:
3971:
3968:
3965:
3962:
3959:
3956:
3953:
3950:
3947:
3944:
3941:
3938:
3935:
3932:
3929:
3926:
3923:
3920:
3917:
3914:
3911:
3908:
3905:
3902:
3899:
3896:
3893:
3890:
3887:
3884:
3881:
3878:
3875:
3872:
3869:
3866:
3863:
3860:
3857:
3854:
3851:
3848:
3845:
3842:
3839:
3836:
3833:
3830:
3827:
3824:
3821:
3818:
3815:
3812:
3809:
3806:
3803:
3800:
3797:
3794:
3791:
3788:
3785:
3782:
3779:
3776:
3773:
3770:
3767:
3764:
3761:
3758:
3755:
3752:
3749:
3746:
3743:
3740:
3737:
3734:
3731:
3728:
3725:
3722:
3719:
3716:
3713:
3710:
3707:
3704:
3701:
3698:
3695:
3692:
3689:
3686:
3683:
3680:
3677:
3674:
3671:
3668:
3665:
3662:
3659:
3656:
3653:
3650:
3647:
3644:
3641:
3638:
3635:
3632:
3629:
3626:
3623:
3620:
3617:
3614:
3611:
3608:
3605:
3602:
3599:
3596:
3593:
3590:
3587:
3584:
3581:
3578:
3575:
3572:
3569:
3566:
3563:
3560:
3557:
3554:
3551:
3548:
3545:
3542:
3539:
3536:
3533:
3530:
3527:
3524:
3521:
3518:
3515:
3512:
3509:
3506:
3503:
3500:
3497:
3494:
3491:
3488:
3485:
3482:
3479:
3476:
3473:
3470:
3467:
3464:
3461:
3458:
3455:
3452:
3449:
3446:
3443:
3440:
3437:
3434:
3431:
3428:
3425:
3422:
3419:
3416:
3413:
3410:
3407:
3404:
3401:
3398:
3395:
3392:
3389:
3386:
3383:
3380:
3377:
3374:
3371:
3368:
3365:
3362:
3359:
3356:
3353:
3350:
3347:
3344:
3341:
3338:
3335:
3332:
3329:
3326:
3323:
3320:
3317:
3314:
3311:
3308:
3305:
3302:
3299:
3296:
3293:
3290:
3287:
3284:
3281:
3278:
3275:
3272:
3269:
3266:
3263:
3260:
3257:
3254:
3251:
3248:
3245:
3242:
3239:
3236:
3233:
3230:
3227:
3224:
3221:
3218:
3215:
3212:
3209:
3206:
3203:
3200:
3197:
3194:
3191:
3188:
3185:
3182:
3179:
3176:
3173:
3170:
3167:
3164:
3161:
3158:
3155:
3152:
3149:
3146:
3143:
3140:
3137:
3134:
3131:
3128:
3125:
3122:
3119:
3116:
3113:
3110:
3107:
3104:
3101:
3098:
3095:
3092:
3089:
3086:
3083:
3080:
3077:
3074:
3071:
3068:
3065:
3062:
3059:
3056:
3053:
3050:
3047:
3044:
3041:
3038:
3035:
3032:
3029:
3026:
3023:
3020:
3017:
3014:
3011:
3008:
3005:
3002:
2999:
2996:
2993:
2990:
2987:
2984:
2981:
2978:
2975:
2972:
2969:
2966:
2963:
2960:
2957:
2954:
2951:
2948:
2945:
2942:
2939:
2936:
2933:
2930:
2927:
2924:
2921:
2918:
2915:
2912:
2909:
2906:
2903:
2900:
2897:
2894:
2891:
2888:
2885:
2882:
2879:
2876:
2873:
2870:
2867:
2864:
2861:
2858:
2855:
2852:
2849:
2846:
2843:
2840:
2837:
2834:
2831:
2828:
2825:
2822:
2819:
2816:
2813:
2810:
2807:
2804:
2801:
2798:
2795:
2792:
2789:
2786:
2783:
2780:
2777:
2774:
2771:
2768:
2765:
2762:
2759:
2756:
2753:
2750:
2747:
2744:
2741:
2738:
2735:
2732:
2729:
2726:
2723:
2720:
2717:
2714:
2711:
2708:
2705:
2702:
2699:
2696:
2693:
2690:
2687:
2673:
2670:
2667:
2664:
2661:
2658:
2655:
2652:
2649:
2646:
2643:
2640:
2637:
2634:
2631:
2628:
2625:
2622:
2619:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2589:
2586:
2583:
2580:
2577:
2574:
2571:
2568:
2565:
2562:
2559:
2556:
2553:
2550:
2547:
2544:
2541:
2538:
2535:
2532:
2529:
2526:
2523:
2520:
2517:
2514:
2511:
2508:
2505:
2502:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2472:
2469:
2466:
2463:
2460:
2457:
2454:
2451:
2448:
2445:
2442:
2439:
2436:
2433:
2430:
2427:
2424:
2421:
2418:
2415:
2412:
2409:
2406:
2403:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2379:
2376:
2373:
2370:
2367:
2364:
2361:
2358:
2355:
2352:
2349:
2346:
2343:
2340:
2337:
2334:
2331:
2328:
2325:
2322:
2319:
2316:
2313:
2310:
2307:
2304:
2301:
2298:
2295:
2292:
2289:
2286:
2283:
2280:
2277:
2274:
2271:
2268:
2265:
2262:
2259:
2256:
2253:
2252:initializeLabels
2250:
2247:
2244:
2241:
2238:
2235:
2232:
2229:
2226:
2223:
2220:
2217:
2214:
2197:
2195:
2194:
2189:
2164:
2162:
2161:
2156:
2144:
2142:
2141:
2136:
2134:
2133:
2125:
2115:
2113:
2112:
2107:
2087:
2086:
2078:
2066:
2064:
2063:
2058:
2056:
2055:
2036:
2034:
2033:
2028:
2026:
2025:
2009:
2007:
2006:
2001:
1999:
1998:
1980:
1979:
1961:
1959:
1958:
1953:
1951:
1950:
1922:
1921:
1913:
1906:
1901:
1879:
1878:
1870:
1864:
1863:
1848:
1847:
1841:
1838:
1830:
1829:
1821:
1815:
1814:
1799:
1797:
1796:
1791:
1777:
1776:
1764:
1763:
1755:
1745:
1743:
1742:
1737:
1735:
1734:
1707:
1706:
1698:
1692:
1691:
1646:
1645:
1637:
1631:
1630:
1615:
1614:
1602:
1601:
1593:
1586:
1581:
1563:
1561:
1560:
1555:
1553:
1552:
1540:
1539:
1531:
1521:
1519:
1518:
1513:
1508:
1507:
1499:
1493:
1490:
1485:
1482:
1474:
1473:
1465:
1459:
1458:
1428:
1426:
1425:
1420:
1415:
1414:
1406:
1400:
1397:
1388:
1386:
1385:
1380:
1378:
1377:
1369:
1359:
1357:
1356:
1351:
1346:
1345:
1337:
1331:
1328:
1320:The atomic type
1319:
1317:
1316:
1311:
1291:
1290:
1272:
1271:
1247:
1246:
1222:
1221:
1200:
1199:
1191:
1185:
1184:
1179:
1178:
1164:
1162:
1161:
1156:
1154:
1153:
1145:
1135:
1133:
1132:
1127:
1125:
1124:
1116:
1106:
1104:
1103:
1098:
1093:
1092:
1084:
1078:
1077:
1072:
1071:
1055:
1053:
1052:
1047:
1045:
1044:
1025:
1023:
1022:
1017:
1015:
1014:
998:
996:
995:
990:
988:
987:
969:
968:
950:
948:
947:
942:
934:
933:
925:
918:
913:
892:
891:
883:
876:
871:
856:
855:
847:
841:
840:
822:
819:
811:
810:
802:
796:
795:
780:
778:
777:
772:
752:
751:
739:
738:
730:
720:
718:
717:
712:
700:
699:
691:
685:
684:
679:
678:
668:
667:
659:
650:
649:
641:
635:
634:
606:
605:
597:
590:
585:
567:
565:
564:
559:
557:
556:
544:
543:
535:
525:
523:
522:
517:
509:
508:
500:
494:
491:
486:
483:
475:
474:
466:
460:
459:
399:
397:
396:
391:
379:
377:
376:
371:
278:
271:
267:
264:
258:
235:
227:
196:color refinement
194:All variants of
177:color refinement
126:
119:
115:
112:
106:
82:
81:
74:
67:
60:
56:
53:
47:
24:
23:
16:
5056:
5055:
5051:
5050:
5049:
5047:
5046:
5045:
5031:
5030:
5029:
5028:
5016:
5014:
5009:
5008:
5004:
4995:
4993:
4979:
4978:
4974:
4965:
4963:
4958:
4957:
4953:
4944:
4942:
4934:
4933:
4929:
4920:
4918:
4913:
4912:
4908:
4899:
4897:
4885:
4873:
4872:
4868:
4854:
4823:
4822:
4815:
4810:
4793:
4729:
4717:
4711:
4550:
4549:
4530:
4529:
4411:
4410:
4292:
4291:
4270:
4257:
4246:
4245:
4224:
4211:
4200:
4199:
4119:
4106:
4093:
4088:
4087:
4023:
4018:
4017:
4014:
4011:
4008:
4005:
4002:
3999:
3996:
3993:
3990:
3987:
3984:
3981:
3978:
3975:
3972:
3969:
3966:
3963:
3960:
3957:
3954:
3951:
3948:
3945:
3942:
3939:
3936:
3933:
3930:
3927:
3924:
3921:
3918:
3915:
3912:
3909:
3906:
3903:
3900:
3897:
3894:
3891:
3888:
3885:
3882:
3879:
3876:
3873:
3870:
3867:
3864:
3861:
3858:
3855:
3852:
3849:
3846:
3843:
3840:
3837:
3834:
3831:
3828:
3825:
3822:
3819:
3816:
3813:
3810:
3807:
3804:
3801:
3798:
3795:
3792:
3789:
3786:
3783:
3780:
3777:
3774:
3771:
3768:
3765:
3762:
3759:
3756:
3753:
3750:
3747:
3744:
3741:
3738:
3735:
3732:
3729:
3726:
3723:
3720:
3717:
3714:
3711:
3708:
3705:
3702:
3699:
3696:
3693:
3690:
3687:
3684:
3681:
3678:
3675:
3672:
3669:
3666:
3663:
3660:
3657:
3654:
3651:
3648:
3646:glabelsCountNew
3645:
3642:
3639:
3636:
3633:
3630:
3627:
3624:
3621:
3619:glabelsCountNew
3618:
3615:
3612:
3609:
3606:
3603:
3600:
3597:
3594:
3592:glabelsCountNew
3591:
3588:
3585:
3582:
3579:
3576:
3573:
3570:
3567:
3564:
3561:
3558:
3555:
3552:
3549:
3546:
3543:
3540:
3537:
3534:
3531:
3528:
3525:
3522:
3519:
3516:
3513:
3510:
3507:
3504:
3501:
3498:
3495:
3492:
3489:
3486:
3483:
3480:
3477:
3474:
3471:
3468:
3465:
3462:
3459:
3456:
3453:
3450:
3447:
3444:
3441:
3438:
3435:
3432:
3429:
3426:
3423:
3420:
3417:
3414:
3411:
3409:glabelsCountNew
3408:
3405:
3402:
3399:
3396:
3393:
3390:
3387:
3384:
3381:
3378:
3375:
3372:
3369:
3366:
3363:
3360:
3357:
3354:
3351:
3348:
3345:
3342:
3339:
3336:
3333:
3330:
3327:
3324:
3321:
3318:
3315:
3312:
3309:
3306:
3303:
3300:
3297:
3294:
3291:
3288:
3285:
3282:
3279:
3276:
3273:
3270:
3267:
3264:
3261:
3258:
3255:
3252:
3249:
3246:
3243:
3240:
3237:
3234:
3231:
3228:
3225:
3222:
3219:
3216:
3213:
3210:
3207:
3204:
3201:
3198:
3195:
3192:
3189:
3186:
3183:
3180:
3177:
3174:
3171:
3168:
3165:
3162:
3159:
3156:
3153:
3150:
3147:
3144:
3141:
3138:
3135:
3132:
3129:
3126:
3123:
3120:
3117:
3114:
3111:
3108:
3105:
3102:
3099:
3096:
3093:
3090:
3087:
3084:
3081:
3078:
3075:
3072:
3069:
3066:
3063:
3060:
3057:
3054:
3051:
3048:
3045:
3042:
3039:
3036:
3033:
3030:
3027:
3024:
3021:
3018:
3015:
3012:
3009:
3006:
3003:
3000:
2997:
2994:
2991:
2988:
2985:
2982:
2979:
2976:
2973:
2970:
2967:
2964:
2961:
2958:
2955:
2952:
2949:
2946:
2943:
2940:
2937:
2934:
2931:
2928:
2925:
2922:
2919:
2916:
2913:
2910:
2907:
2904:
2901:
2898:
2895:
2892:
2889:
2886:
2883:
2880:
2877:
2874:
2871:
2868:
2865:
2862:
2859:
2856:
2853:
2850:
2847:
2844:
2841:
2838:
2835:
2832:
2829:
2826:
2823:
2820:
2817:
2814:
2811:
2808:
2805:
2802:
2799:
2796:
2793:
2790:
2787:
2784:
2781:
2778:
2775:
2772:
2769:
2766:
2763:
2760:
2757:
2754:
2751:
2748:
2745:
2742:
2739:
2736:
2733:
2730:
2727:
2724:
2721:
2718:
2715:
2712:
2709:
2706:
2703:
2700:
2697:
2694:
2691:
2688:
2685:
2675:
2674:
2671:
2668:
2665:
2662:
2659:
2656:
2653:
2650:
2647:
2644:
2641:
2638:
2635:
2632:
2629:
2626:
2623:
2620:
2617:
2614:
2611:
2608:
2605:
2602:
2599:
2596:
2593:
2590:
2587:
2584:
2581:
2578:
2575:
2572:
2569:
2566:
2563:
2560:
2557:
2554:
2551:
2548:
2545:
2542:
2539:
2536:
2533:
2530:
2527:
2524:
2521:
2518:
2515:
2512:
2509:
2506:
2503:
2500:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2476:
2473:
2470:
2467:
2464:
2461:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2431:
2428:
2425:
2422:
2419:
2416:
2413:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2371:
2368:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2344:
2341:
2338:
2335:
2332:
2329:
2326:
2323:
2320:
2317:
2314:
2311:
2308:
2305:
2302:
2299:
2296:
2293:
2290:
2287:
2284:
2281:
2278:
2275:
2272:
2269:
2266:
2263:
2260:
2257:
2254:
2251:
2248:
2245:
2242:
2239:
2236:
2233:
2230:
2227:
2224:
2221:
2218:
2215:
2212:
2209:
2204:
2174:
2173:
2147:
2146:
2118:
2117:
2071:
2070:
2067:
2047:
2042:
2041:
2017:
2012:
2011:
1984:
1971:
1966:
1965:
1849:
1806:
1801:
1800:
1768:
1748:
1747:
1677:
1616:
1568:
1567:
1544:
1524:
1523:
1450:
1445:
1444:
1438:
1391:
1390:
1362:
1361:
1322:
1321:
1282:
1257:
1232:
1213:
1172:
1167:
1166:
1138:
1137:
1109:
1108:
1065:
1060:
1059:
1056:
1036:
1031:
1030:
1006:
1001:
1000:
973:
960:
955:
954:
826:
787:
782:
781:
743:
723:
722:
672:
620:
572:
571:
548:
528:
527:
451:
446:
445:
439:
418:
382:
381:
356:
355:
285:
279:
268:
262:
259:
248:
236:
225:
192:
134:
127:
116:
110:
107:
93:Please help by
92:
83:
79:
68:
57:
51:
48:
37:
31:has an unclear
25:
21:
12:
11:
5:
5054:
5052:
5044:
5043:
5033:
5032:
5027:
5026:
5002:
4992:(9): 2539−2561
4972:
4951:
4927:
4906:
4866:
4852:
4812:
4811:
4809:
4806:
4805:
4804:
4799:
4792:
4789:
4728:
4725:
4716:
4713:
4700:
4699:
4690:
4681:
4671:
4670:
4659:
4648:
4616:regular graphs
4557:
4537:
4517:
4514:
4511:
4508:
4505:
4502:
4499:
4496:
4493:
4490:
4487:
4484:
4481:
4478:
4475:
4472:
4469:
4466:
4463:
4460:
4457:
4454:
4451:
4448:
4445:
4442:
4439:
4436:
4433:
4430:
4427:
4424:
4421:
4418:
4398:
4395:
4392:
4389:
4386:
4383:
4380:
4377:
4374:
4371:
4368:
4365:
4362:
4359:
4356:
4353:
4350:
4347:
4344:
4341:
4338:
4335:
4332:
4329:
4326:
4323:
4320:
4317:
4314:
4311:
4308:
4305:
4302:
4299:
4277:
4273:
4269:
4264:
4260:
4256:
4253:
4231:
4227:
4223:
4218:
4214:
4210:
4207:
4182:
4181:
4172:
4163:
4153:
4152:
4149:
4146:
4126:
4122:
4118:
4113:
4109:
4105:
4100:
4096:
4072:
4071:
4062:
4053:
4043:
4042:
4039:
4036:
4022:
4019:
2684:
2211:
2208:
2205:
2203:
2200:
2187:
2184:
2181:
2154:
2131:
2128:
2105:
2101:
2096:
2093:
2090:
2084:
2081:
2054:
2050:
2024:
2020:
1997:
1994:
1991:
1987:
1983:
1978:
1974:
1949:
1944:
1940:
1937:
1934:
1931:
1928:
1925:
1919:
1916:
1910:
1905:
1900:
1896:
1892:
1888:
1885:
1882:
1876:
1873:
1867:
1862:
1859:
1856:
1852:
1846:
1836:
1833:
1827:
1824:
1818:
1813:
1809:
1789:
1786:
1783:
1780:
1775:
1771:
1767:
1761:
1758:
1733:
1728:
1725:
1721:
1716:
1713:
1710:
1704:
1701:
1695:
1690:
1687:
1684:
1680:
1676:
1673:
1670:
1667:
1664:
1660:
1655:
1652:
1649:
1643:
1640:
1634:
1629:
1626:
1623:
1619:
1613:
1608:
1605:
1599:
1596:
1590:
1585:
1580:
1576:
1551:
1547:
1543:
1537:
1534:
1511:
1505:
1502:
1496:
1488:
1480:
1477:
1471:
1468:
1462:
1457:
1453:
1439:
1437:
1436:k-FWL (k>1)
1434:
1418:
1412:
1409:
1403:
1375:
1372:
1349:
1343:
1340:
1334:
1309:
1306:
1303:
1300:
1297:
1294:
1289:
1285:
1281:
1278:
1275:
1270:
1267:
1264:
1260:
1256:
1253:
1250:
1245:
1242:
1239:
1235:
1231:
1228:
1225:
1220:
1216:
1212:
1209:
1206:
1203:
1197:
1194:
1188:
1183:
1177:
1151:
1148:
1122:
1119:
1096:
1090:
1087:
1081:
1076:
1070:
1043:
1039:
1013:
1009:
986:
983:
980:
976:
972:
967:
963:
940:
937:
931:
928:
922:
917:
912:
908:
904:
901:
898:
895:
889:
886:
880:
875:
870:
866:
862:
859:
853:
850:
844:
839:
836:
833:
829:
825:
817:
814:
808:
805:
799:
794:
790:
770:
767:
764:
761:
758:
755:
750:
746:
742:
736:
733:
710:
706:
703:
697:
694:
688:
683:
677:
671:
665:
662:
656:
653:
647:
644:
638:
633:
630:
627:
623:
619:
615:
612:
609:
603:
600:
594:
589:
584:
580:
555:
551:
547:
541:
538:
515:
512:
506:
503:
497:
489:
481:
478:
472:
469:
463:
458:
454:
440:
438:
435:
417:
414:
389:
369:
366:
363:
294:Initialization
281:
280:
239:
237:
230:
224:
221:
217:regular graphs
191:
188:
132:
129:
128:
86:
84:
77:
70:
69:
33:citation style
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
5053:
5042:
5039:
5038:
5036:
5023:
5012:
5006:
5003:
4991:
4987:
4983:
4976:
4973:
4962:
4955:
4952:
4940:
4939:
4931:
4928:
4917:
4910:
4907:
4895:
4891:
4884:
4880:
4876:
4870:
4867:
4863:
4859:
4855:
4849:
4845:
4841:
4836:
4831:
4827:
4820:
4818:
4814:
4807:
4803:
4800:
4798:
4795:
4794:
4790:
4788:
4786:
4782:
4778:
4774:
4773:graph kernels
4770:
4766:
4762:
4757:
4755:
4750:
4749:Graph kernels
4746:
4742:
4738:
4734:
4726:
4724:
4722:
4714:
4712:
4709:
4707:
4698:
4696:
4691:
4689:
4687:
4682:
4680:
4678:
4673:
4672:
4668:
4664:
4660:
4657:
4653:
4649:
4646:
4645:
4642:
4640:
4636:
4632:
4628:
4623:
4621:
4617:
4612:
4610:
4606:
4602:
4598:
4594:
4590:
4586:
4582:
4578:
4574:
4569:
4555:
4535:
4515:
4512:
4506:
4500:
4497:
4494:
4491:
4485:
4479:
4476:
4473:
4470:
4464:
4458:
4455:
4452:
4449:
4443:
4437:
4434:
4431:
4428:
4422:
4416:
4396:
4393:
4387:
4381:
4378:
4375:
4372:
4366:
4360:
4357:
4354:
4351:
4345:
4339:
4336:
4333:
4330:
4324:
4318:
4315:
4312:
4309:
4303:
4297:
4275:
4271:
4262:
4258:
4254:
4251:
4229:
4225:
4216:
4212:
4208:
4205:
4197:
4196:kernelization
4193:
4189:
4180:
4178:
4173:
4171:
4169:
4164:
4162:
4160:
4155:
4154:
4150:
4147:
4144:
4143:
4140:
4124:
4120:
4116:
4111:
4107:
4103:
4098:
4094:
4084:
4082:
4077:
4070:
4068:
4063:
4061:
4059:
4054:
4052:
4050:
4045:
4044:
4040:
4037:
4034:
4033:
4030:
4028:
4020:
3922:"_"
3799:"_"
3535:"_"
2682:
2680:
2206:
2201:
2199:
2185:
2182:
2179:
2170:
2166:
2152:
2126:
2116:is the tuple
2103:
2091:
2079:
2052:
2048:
2040:
2022:
2018:
1995:
1992:
1989:
1985:
1981:
1976:
1972:
1964:
1935:
1932:
1929:
1926:
1914:
1903:
1898:
1894:
1883:
1871:
1860:
1857:
1854:
1850:
1834:
1822:
1811:
1807:
1787:
1784:
1781:
1778:
1773:
1769:
1765:
1756:
1723:
1711:
1699:
1688:
1685:
1682:
1678:
1674:
1671:
1668:
1662:
1650:
1638:
1627:
1624:
1621:
1617:
1606:
1594:
1583:
1578:
1574:
1566:
1549:
1545:
1541:
1532:
1500:
1478:
1466:
1455:
1451:
1442:
1435:
1433:
1430:
1407:
1370:
1338:
1304:
1301:
1298:
1295:
1287:
1283:
1279:
1276:
1273:
1268:
1265:
1262:
1258:
1254:
1251:
1248:
1243:
1240:
1237:
1233:
1229:
1226:
1223:
1218:
1214:
1204:
1192:
1181:
1146:
1117:
1107:of a k-tuple
1085:
1074:
1041:
1037:
1029:
1011:
1007:
984:
981:
978:
974:
970:
965:
961:
953:
926:
915:
910:
906:
902:
899:
896:
884:
873:
868:
864:
860:
848:
837:
834:
831:
827:
815:
803:
792:
788:
765:
759:
756:
753:
748:
744:
740:
731:
692:
681:
669:
660:
654:
642:
631:
628:
625:
621:
610:
598:
587:
582:
578:
570:
553:
549:
545:
536:
501:
479:
467:
456:
452:
443:
437:k-WL (k>1)
436:
434:
431:
428:-dimensional
427:
423:
415:
413:
411:
407:
402:
387:
380:rounds where
367:
364:
361:
352:
350:
346:
342:
338:
334:
329:
327:
323:
321:
317:
313:
309:
305:
301:
297:
295:
291:
289:
277:
274:
266:
263:December 2023
256:
252:
246:
245:
240:This section
238:
234:
229:
228:
222:
220:
218:
213:
209:
205:
201:
197:
189:
187:
185:
180:
178:
174:
170:
166:
162:
158:
154:
151:
147:
143:
139:
125:
122:
114:
111:December 2023
104:
100:
96:
90:
87:This article
85:
76:
75:
66:
63:
55:
52:December 2023
45:
41:
35:
34:
29:This article
27:
18:
17:
5041:Graph theory
5021:
5015:. Retrieved
5005:
4994:. Retrieved
4989:
4985:
4975:
4964:. Retrieved
4954:
4943:. Retrieved
4937:
4930:
4919:. Retrieved
4909:
4898:. Retrieved
4893:
4889:
4879:Leman, A. A.
4869:
4825:
4758:
4730:
4718:
4715:Applications
4710:
4703:
4692:
4683:
4674:
4666:
4662:
4655:
4651:
4638:
4634:
4630:
4626:
4624:
4613:
4608:
4604:
4600:
4596:
4592:
4588:
4584:
4580:
4576:
4572:
4570:
4191:
4187:
4185:
4174:
4165:
4156:
4085:
4078:
4075:
4064:
4055:
4046:
4024:
3994:certificate1
3976:certificate0
3934:certificate1
3928:certificate0
3901:certificate1
3871:""
3865:certificate1
3778:certificate0
3748:""
3742:certificate0
3640:glabelsCount
3613:glabelsCount
3358:glabelsCount
2676:
2645:certificateH
2639:certificateG
2588:certificateH
2540:certificateG
2171:
2167:
2068:
2038:
1962:
1564:
1440:
1431:
1057:
1027:
951:
568:
441:
429:
425:
421:
419:
403:
353:
348:
344:
340:
336:
332:
330:
325:
324:
319:
315:
311:
307:
303:
299:
298:
293:
292:
284:
269:
260:
249:Please help
244:verification
241:
211:
207:
203:
199:
193:
184:Andrey Leman
181:
156:
152:
148:between two
141:
138:graph theory
135:
117:
108:
95:spinning off
88:
58:
49:
30:
4579:we get for
2594:certificate
2546:certificate
326:Termination
146:isomorphism
5017:2023-10-29
4996:2023-10-29
4966:2023-10-28
4945:2023-10-29
4921:2023-10-28
4900:2023-10-28
4896:(9): 12–16
4835:2201.07083
4808:References
4759:Note that
4151:G1 vs. G2
4148:G0 vs. G2
4145:G0 vs. G1
3655:glabelsNew
3601:glabelsNew
3400:glabelsNew
3286:combineTwo
3067:combineTwo
2528:glabelsNew
2501:glabelsNew
2444:glabelsNew
2312:glabelsNew
2228:combineTwo
1522:) for all
310:such that
302:Two nodes
300:Refinement
165:Weisfeiler
99:relocating
44:footnoting
4862:235780517
4745:nonlinear
4593:7_7_8_8_9
4585:7_7_8_9_9
4556:ψ
4536:φ
4501:ψ
4480:ψ
4459:ψ
4438:ψ
4417:ψ
4382:φ
4361:φ
4340:φ
4319:φ
4298:φ
4268:→
4252:ψ
4222:→
4206:φ
4104:≅
4041:Graph G2
4038:Graph G1
4035:Graph G0
2492:different
2465:different
2375:neighbors
2183:≥
2130:¯
2100:←
2083:¯
2053:ℓ
1993:−
1990:ℓ
1982:≡
1977:ℓ
1933:∈
1918:¯
1904:ℓ
1875:¯
1858:−
1855:ℓ
1826:¯
1812:ℓ
1785:∈
1766:∈
1760:¯
1720:←
1703:¯
1686:−
1683:ℓ
1672:…
1659:←
1642:¯
1625:−
1622:ℓ
1598:¯
1584:ℓ
1542:∈
1536:¯
1504:¯
1470:¯
1411:¯
1374:¯
1342:¯
1302:∈
1277:…
1241:−
1227:…
1196:¯
1150:¯
1121:¯
1089:¯
1042:ℓ
982:−
979:ℓ
971:≡
966:ℓ
930:¯
916:ℓ
900:…
888:¯
874:ℓ
852:¯
835:−
832:ℓ
807:¯
793:ℓ
760:∈
741:∈
735:¯
696:¯
670:∈
664:¯
646:¯
629:−
626:ℓ
602:¯
588:ℓ
546:∈
540:¯
505:¯
471:¯
365:−
5035:Category
4881:(1968).
4791:See also
4771:such as
4528:. While
4117:≇
4021:Examples
3913:g1labels
3853:g1labels
3835:g1labels
3802:g1labels
3790:g0labels
3730:g0labels
3712:g0labels
3679:g0labels
3583:newlabel
3580:newlabel
3460:neighbor
3367:newlabel
3244:neighbor
3220:neighbor
3166:neighbor
3142:neighbor
2432:newLabel
2426:newLabel
2279:newLabel
1746:for all
721:for all
526:for all
430:folklore
40:citation
4781:NP-hard
4777:kernels
4761:kernels
4737:kernels
4186:Indeed
3847:glabels
3724:glabels
3673:glabels
3649:glabels
3484:glabels
3445:glabels
3349:glabels
3313:glabels
2522:glabels
2474:glabels
2351:glabels
2246:glabels
5013:. 2019
4860:
4850:
4754:GraKeL
4620:degree
4409:resp.
3841:append
3718:append
3607:labels
3574:labels
3568:labels
3478:append
3304:labels
3274:return
2679:Python
2612:labels
2609:sorted
2564:labels
2561:sorted
2495:labels
2486:number
2468:labels
2459:number
2450:labels
2420:labels
2411:labels
2267:labels
2039:return
1565:repeat
1028:return
569:repeat
150:graphs
140:, the
4886:(PDF)
4858:S2CID
4830:arXiv
4667:G8_03
4663:G8_02
4656:G8_01
4652:G8_00
4639:G8_02
4635:G8_01
4631:G8_03
4627:G8_00
4081:cycle
4027:order
4000:print
3982:print
3964:print
3961:False
3883:range
3817:range
3760:range
3694:range
3667:print
3562:label
3529:label
3511:range
3433:label
3385:while
3382:False
3331:range
3298:g5_02
3292:g5_00
2938:g5_02
2812:g5_01
2686:g5_00
2672:False
2405:label
2339:label
2297:while
2294:False
2069:Here
1963:until
1441:Input
952:until
442:Input
169:Leman
4848:ISBN
4763:for
4706:here
4665:and
4654:and
4607:and
4599:and
4575:and
4244:and
4190:and
4012:test
3955:test
3949:else
3946:True
3940:test
3859:sort
3736:sort
3661:copy
3634:else
3631:True
3625:done
3496:sort
3421:node
3394:done
3376:done
3268:copy
3193:node
3184:copy
3115:node
2666:test
2660:else
2657:True
2651:test
2627:part
2603:from
2579:part
2555:from
2534:copy
2516:else
2513:True
2507:done
2390:sort
2381:node
2327:node
2306:done
2288:done
2207:Code
1839:Hash
1491:type
1483:Hash
1398:type
1329:type
820:Hash
492:type
484:Hash
347:and
335:and
314:and
210:and
202:and
167:and
155:and
42:and
4840:doi
4731:In
4029:5.
3907:str
3898:)):
3889:len
3874:for
3832:)):
3823:len
3808:for
3784:str
3775:)):
3766:len
3751:for
3709:)):
3700:len
3685:for
3556:not
3541:str
3526:)):
3517:len
3502:for
3457:for
3439:str
3418:for
3388:not
3346:)):
3337:len
3322:for
3238:add
3217:for
3211:set
3190:for
3160:add
3139:for
3133:set
3112:for
3100:len
3064:def
2618:the
2606:the
2597:for
2570:the
2558:the
2549:for
2399:not
2393:())
2366:for
2360:str
2345:str
2324:for
2300:not
304:u,v
253:by
136:In
97:or
5037::
5020:.
4990:12
4988:.
4984:.
4892:.
4888:.
4877:;
4856:,
4846:,
4838:,
4816:^
4756:.
4747:.
4723:.
4708:.
4609:G2
4605:G1
4601:G2
4597:G1
4589:G1
4581:G0
4577:G2
4573:G0
4192:G1
4188:G0
4139:.
3931:==
3925:if
3904:+=
3895:g1
3880:in
3862:()
3829:g1
3814:in
3781:+=
3772:g0
3757:in
3739:()
3706:g0
3691:in
3664:()
3616:==
3610:if
3595:+=
3586:+=
3571:):
3565:in
3553:if
3547:s2
3532:+=
3523:s2
3508:in
3499:()
3490:s2
3472:s2
3463:in
3451:s2
3424:in
3406:{}
3397:):
3328:in
3319:{}
3310:{}
3271:()
3226:g2
3223:in
3214:()
3199:g2
3196:in
3187:()
3148:g1
3145:in
3136:()
3121:g1
3118:in
3106:g1
3091:{}
3082:):
3079:g2
3073:g1
3061:}}
3040:},
3013:},
2992:},
2971:},
2935:}}
2914:},
2887:},
2866:},
2839:},
2809:}}
2788:},
2767:},
2740:},
2719:},
2642:==
2636:if
2630:of
2615:of
2582:of
2567:of
2537:()
2504:):
2498:in
2489:of
2480:==
2471:in
2462:of
2453:if
2435:+=
2414:):
2408:in
2396:if
2378:of
2372:in
2330:in
2318:{}
2309:):
2273:{}
2165:.
2037:)
1429:.
1165::
1026:)
412:.
4999:.
4969:.
4948:.
4924:.
4903:.
4894:2
4842::
4832::
4516:A
4513:=
4510:)
4507:e
4504:(
4498:,
4495:E
4492:=
4489:)
4486:d
4483:(
4477:,
4474:D
4471:=
4468:)
4465:c
4462:(
4456:,
4453:C
4450:=
4447:)
4444:b
4441:(
4435:,
4432:B
4429:=
4426:)
4423:a
4420:(
4397:A
4394:=
4391:)
4388:e
4385:(
4379:,
4376:E
4373:=
4370:)
4367:d
4364:(
4358:,
4355:B
4352:=
4349:)
4346:c
4343:(
4337:,
4334:C
4331:=
4328:)
4325:b
4322:(
4316:,
4313:D
4310:=
4307:)
4304:a
4301:(
4276:1
4272:G
4263:0
4259:G
4255::
4230:1
4226:G
4217:0
4213:G
4209::
4125:2
4121:G
4112:0
4108:G
4099:1
4095:G
4015:)
4009:,
4003:(
3997:)
3991:,
3985:(
3979:)
3973:,
3967:(
3958:=
3952::
3943:=
3937::
3919:+
3916:)
3910:(
3892:(
3886:(
3877:i
3868:=
3856:.
3850:)
3844:(
3838:.
3826:(
3820:(
3811:i
3805:=
3796:+
3793:)
3787:(
3769:(
3763:(
3754:i
3745:=
3733:.
3727:)
3721:(
3715:.
3703:(
3697:(
3688:i
3682:=
3676:)
3670:(
3658:.
3652:=
3643:=
3637::
3628:=
3622::
3604:=
3598:1
3589:1
3577:=
3559:(
3550:)
3544:(
3538:+
3520:(
3514:(
3505:i
3493:.
3487:)
3481:(
3475:.
3469::
3466:g
3454:=
3448:)
3442:(
3436:=
3430::
3427:g
3415:0
3412:=
3403:=
3391:(
3379:=
3373:1
3370:=
3364:1
3361:=
3355:0
3352:=
3343:g
3340:(
3334:(
3325:i
3316:=
3307:=
3301:)
3295:,
3289:(
3283:=
3280:g
3277:g
3265:.
3262:s
3259:=
3256:g
3253:)
3250:n
3247:+
3241:(
3235:.
3232:s
3229::
3208:=
3205:s
3202::
3181:.
3178:s
3175:=
3172:g
3169:)
3163:(
3157:.
3154:s
3151::
3130:=
3127:s
3124::
3109:)
3103:(
3097:=
3094:n
3088:=
3085:g
3076:,
3070:(
3058:3
3055:,
3052:0
3049:{
3046::
3043:4
3037:4
3034:,
3031:2
3028:,
3025:1
3022:{
3019::
3016:3
3010:3
3007:,
3004:0
3001:{
2998::
2995:2
2989:3
2986:,
2983:0
2980:{
2977::
2974:1
2968:4
2965:,
2962:2
2959:,
2956:1
2953:{
2950::
2947:0
2944:{
2941:=
2932:1
2929:,
2926:0
2923:{
2920::
2917:4
2911:2
2908:,
2905:1
2902:,
2899:0
2896:{
2893::
2890:3
2884:3
2881:,
2878:1
2875:{
2872::
2869:2
2863:4
2860:,
2857:3
2854:,
2851:2
2848:{
2845::
2842:1
2836:4
2833:,
2830:3
2827:{
2824::
2821:0
2818:{
2815:=
2806:3
2803:,
2800:0
2797:{
2794::
2791:4
2785:4
2782:,
2779:2
2776:{
2773::
2770:3
2764:3
2761:,
2758:1
2755:,
2752:0
2749:{
2746::
2743:2
2737:2
2734:,
2731:0
2728:{
2725::
2722:1
2716:4
2713:,
2710:2
2707:,
2704:1
2701:{
2698::
2695:0
2692:{
2689:=
2669:=
2663::
2654:=
2648::
2633:U
2624:-
2621:H
2600:H
2591:=
2585:U
2576:-
2573:G
2552:G
2543:=
2531:.
2525:=
2519::
2510:=
2483:(
2477:)
2456:(
2447:=
2438:1
2423:=
2402:(
2387:.
2384:]
2369:x
2363:(
2357:+
2354:)
2348:(
2342:=
2336::
2333:U
2315:=
2303:(
2291:=
2285:1
2282:=
2270:=
2261:)
2258:U
2255:(
2249:=
2243:)
2240:H
2237:,
2234:G
2231:(
2225:=
2222:U
2186:2
2180:k
2153:w
2127:v
2104:w
2095:]
2092:i
2089:[
2080:v
2049:c
2023:k
2019:V
1996:1
1986:c
1973:c
1948:)
1943:}
1939:}
1936:V
1930:w
1927::
1924:)
1915:v
1909:(
1899:w
1895:c
1891:{
1887:{
1884:,
1881:)
1872:v
1866:(
1861:1
1851:c
1845:(
1835:=
1832:)
1823:v
1817:(
1808:c
1788:V
1782:w
1779:,
1774:k
1770:V
1757:v
1732:)
1727:)
1724:w
1715:]
1712:k
1709:[
1700:v
1694:(
1689:1
1679:c
1675:,
1669:,
1666:)
1663:w
1654:]
1651:1
1648:[
1639:v
1633:(
1628:1
1618:c
1612:(
1607:=
1604:)
1595:v
1589:(
1579:w
1575:c
1550:k
1546:V
1533:v
1510:)
1501:v
1495:(
1487:(
1479:=
1476:)
1467:v
1461:(
1456:0
1452:c
1417:)
1408:v
1402:(
1371:v
1348:)
1339:v
1333:(
1308:}
1305:V
1299:w
1296::
1293:)
1288:k
1284:v
1280:,
1274:,
1269:1
1266:+
1263:i
1259:v
1255:,
1252:w
1249:,
1244:1
1238:i
1234:v
1230:,
1224:,
1219:1
1215:v
1211:(
1208:{
1205:=
1202:)
1193:v
1187:(
1182:i
1176:N
1147:v
1118:v
1095:)
1086:v
1080:(
1075:i
1069:N
1038:c
1012:k
1008:V
985:1
975:c
962:c
939:)
936:)
927:v
921:(
911:k
907:c
903:,
897:,
894:)
885:v
879:(
869:1
865:c
861:,
858:)
849:v
843:(
838:1
828:c
824:(
816:=
813:)
804:v
798:(
789:c
769:]
766:k
763:[
757:i
754:,
749:k
745:V
732:v
709:}
705:}
702:)
693:v
687:(
682:i
676:N
661:w
655::
652:)
643:w
637:(
632:1
622:c
618:{
614:{
611:=
608:)
599:v
593:(
583:i
579:c
554:k
550:V
537:v
514:)
511:)
502:v
496:(
488:(
480:=
477:)
468:v
462:(
457:0
453:c
426:k
422:k
388:n
368:1
362:n
349:H
345:G
341:c
337:H
333:G
320:c
316:v
312:u
308:c
276:)
270:(
265:)
261:(
247:.
212:H
208:G
204:H
200:G
157:H
153:G
124:)
118:(
113:)
109:(
105:.
91:.
65:)
59:(
54:)
50:(
46:.
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.