![]() | This article has an unclear citation style .(December 2023) |
![]() | This article may contain an excessive amount of intricate detail that may interest only a particular audience.(December 2023) |
In graph theory, the Weisfeiler Leman graph isomorphism test is a heuristic test for the existence of an isomorphism between two graphs G and H. [1] It is a generalization of the color refinement algorithm and has been first described by Weisfeiler and Leman in 1968. [2] The original formulation is based on graph canonization, a normal form for graphs, while there is also a combinatorial interpretation in the spirit of color refinement and a connection to logic.
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, Andrey Leman is spelled `Lehman' in several older articles.
All variants of color refinement are one-sided heuristics that take as input two graphs G and H and output a certificate that they are different or 'I don't know'. This means that if the heuristic is able to tell G and H 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 regular graphs for 1-WL/color refinement.
This section needs additional citations for verification .(December 2023) |
The 1-dimensional graph isomorphism test is essentially the same as the color refinement algorithm (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:
Initialization All nodes are initialized with the same color 0
Refinement Two nodes u,v get a different color if a) they had a different color before or b) there is a color c such that u and v have a different number of c-colored neighbors
Termination The algorithm ends if the partition induced by two successive refinement steps is the same.
In order to use this algorithm as a graph isomorphism test, one runs the algorithm on two input graphs G and H in parallel, i.e. using the colors when splitting such that some color c (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 G and H. 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.
The algorithm terminates after at most rounds where 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 tends to be very low (<10).
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 message passing algorithm which also connects it to graph neural networks.
This is the place where the aforementioned two variants of the WL algorithm appear. Both the k-dimensional Weisfeiler-Leman (k-WL) and the k-dimensional folklore 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.
Input: a graph G = (V,E) # initialize for all repeat for all until (both colorings induce identical partitions of ) return
Here the neighborhood of a k-tuple is given by the set of all k-tuples reachable by exchanging the i-th position of : The atomic type of a tuple encodes the edge information between all pairs of nodes from . 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 .
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.
Input: a graph G = (V,E) # initialize ) for all repeat for all until (both colorings induce identical partitions of ) return
Here is the tuple where the i-th position is exchanged to be .
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 k-tuple. It then uses all those multisets in the hash that computes the new color.
It can be shown (although only through the connection to logic) that k-FWL and (k+1)-WL are equivalent (for ). 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.
# ALGORITHM WLpairs# INPUT: two graphs G and H to be tested for isomorphism# OUTPUT: Certificates for G and H and whether they agreeU=combineTwo(G,H)glabels=initializeLabels(U)# dictionary where every node gets the same label 0labels={}# dictionary that will provide translation from a string of labels of a node and its neighbors to an integernewLabel=1done=Falsewhilenot(done):glabelsNew={}# set up the dictionary of labels for the next stepfornodeinU:label=str(glabels[node])+str([glabels[x]forxinneighborsofnode].sort())ifnot(labelinlabels):# a combination of labels from the node and its neighbors is encountered for the first timelabels[label]=newLabel# assign the string of labels to a new number as an abbreviated labelnewLabel+=1# increase the counter for assigning new abbreviated labelsglabelsNew[node]=labels[label]if(numberofdifferentlabelsinglabels)==(numberofdifferentlabelsinglabelsNew):done=Trueelse:glabels=glabelsNew.copy()certificateG=certificateforGfromthesortedlabelsoftheG-partofUcertificateH=certificateforHfromthesortedlabelsoftheH-partofUifcertificateG==certificateH:test=Trueelse:test=False
Here is some actual Python code which includes the description of the first examples.
g5_00={0:{1,2,4},1:{0,2},2:{0,1,3},3:{2,4},4:{0,3}}g5_01={0:{3,4},1:{2,3,4},2:{1,3},3:{0,1,2},4:{0,1}}g5_02={0:{1,2,4},1:{0,3},2:{0,3},3:{1,2,4},4:{0,3}}defcombineTwo(g1,g2):g={}n=len(g1)fornodeing1:s=set()forneighboring1[node]:s.add(neighbor)g[node]=s.copy()fornodeing2:s=set()forneighboring2[node]:s.add(neighbor+n)g[node+n]=s.copy()returngg=combineTwo(g5_00,g5_02)labels={}glabels={}foriinrange(len(g)):glabels[i]=0glabelsCount=1newlabel=1done=Falsewhilenot(done):glabelsNew={}glabelsCountNew=0fornodeing:label=str(glabels[node])s2=[]forneighboring[node]:s2.append(glabels[neighbor])s2.sort()foriinrange(len(s2)):label+="_"+str(s2[i])ifnot(labelinlabels):labels[label]=newlabelnewlabel+=1glabelsCountNew+=1glabelsNew[node]=labels[label]ifglabelsCount==glabelsCountNew:done=Trueelse:glabelsCount=glabelsCountNewglabels=glabelsNew.copy()print(glabels)g0labels=[]foriinrange(len(g0)):g0labels.append(glabels[i])g0labels.sort()certificate0=""foriinrange(len(g0)):certificate0+=str(g0labels[i])+"_"g1labels=[]foriinrange(len(g1)):g1labels.append(glabels[i+len(g0)])g1labels.sort()certificate1=""foriinrange(len(g1)):certificate1+=str(g1labels[i])+"_"ifcertificate0==certificate1:test=Trueelse:test=Falseprint("Certificate 0:",certificate0)print("Certificate 1:",certificate1)print("Test yields:",test)
The first three examples are for graphs of order 5. [3]
Graph G0 | Graph G1 | Graph G2 |
---|---|---|
WLpair takes 3 rounds on 'G0' and 'G1'. The test succeeds as the certificates agree.
WLpair takes 4 rounds on 'G0' and 'G2'. The test fails as the certificates disagree. Indeed 'G0' has a cycle of length 5, while 'G2' doesn't, thus 'G0' and 'G2' cannot be isomorphic.
WLpair takes 4 rounds on 'G1' and 'G2'. The test fails as the certificates disagree. From the previous two instances we already know .
G0 vs. G1 | G0 vs. G2 | G1 vs. G2 |
---|---|---|
Indeed G0 and G1 are isomorphic. Any isomorphism must respect the components and therefore the labels. This can be used for kernelization of the graph isomorphism problem. Note that not every map of vertices that respects the labels gives an isomorphism. Let and be maps given by resp. . While is not an isomorphism constitutes an isomorphism.
When applying WLpair to G0 and G2 we get for G0 the certificate 7_7_8_9_9. But the isomorphic G1 gets the certificate 7_7_8_8_9 when applying WLpair to G1 and G2. 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 G1 and G2 can get distinct certificates when WLtest is executed on them separately, they do get the same certificate by WLpair.
The next example is about regular graphs. WLtest cannot distinguish regular graphs of equal order, [4] : 31 but WLpair can distinguish regular graphs of distinct degree 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.
All four graphs are pairwise non-isomorphic. G8_00 has two connected components, while the others do not. G8_03 is 5-regular, while the others are 3-regular. G8_01 has no 3-cycle while G8_02 does have 3-cycles.
WLtest applied to four regular graphs of order 8. | WLpair applied to G8_00 and G8_01 of same degree. | WLpair applied to G8_02 and G8_03 of distinct degree. |
---|---|---|
Another example of two non-isomorphic graphs that WLpair cannot distinguish is given here. [5]
The theory behind the Weisfeiler Leman test is applied in graph neural networks.
In machine learning of nonlinear data one uses kernels to represent the data in a high dimensional feature space after which linear techniques such as support vector machines can be applied. Data represented as graphs often behave nonlinear. Graph kernels 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. [6] These Weisfeiler Leman graph kernels have attracted considerable research in the decade after their publication. [1] They are also implemented in dedicated libraries for graph kernels such as GraKeL. [7]
Note that kernels for artificial neural network in the context of machine learning such as graph kernels are not to be confused with kernels applied in heuristic algorithms to reduce the computational cost for solving problems of high complexity such as instances of NP-hard problems in the field of complexity theory. As stated above the Weisfeiler Leman test can also be applied in the later context.
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.
In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is in D, or has a neighbor in D. The domination numberγ(G) is the number of vertices in a smallest dominating set for G.
In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges, that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge.
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
In mathematics, Bochner's theorem characterizes the Fourier transform of a positive finite Borel measure on the real line. More generally in harmonic analysis, Bochner's theorem asserts that under Fourier transform a continuous positive-definite function on a locally compact abelian group corresponds to a finite positive measure on the Pontryagin dual group. The case of sequences was first established by Gustav Herglotz
In mathematics, a Klein geometry is a type of geometry motivated by Felix Klein in his influential Erlangen program. More specifically, it is a homogeneous space X together with a transitive action on X by a Lie group G, which acts as the symmetry group of the geometry.
In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has other meanings.
In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others. Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see Buluc et al. (2013). Two common examples of graph partitioning are minimum cut and maximum cut problems.
Network motifs are recurrent and statistically significant subgraphs or patterns of a larger graph. All networks, including biological networks, social networks, technological networks and more, can be represented as graphs, which include a wide variety of subgraphs.
In database theory, a conjunctive query is a restricted form of first-order queries using the logical conjunction operator. Many first-order queries can be written as conjunctive queries. In particular, a large part of queries issued on relational databases can be expressed in this way. Conjunctive queries also have a number of desirable theoretical properties that larger classes of queries do not share.
Isomap is a nonlinear dimensionality reduction method. It is one of several widely used low-dimensional embedding methods. Isomap is used for computing a quasi-isometric, low-dimensional embedding of a set of high-dimensional data points. The algorithm provides a simple method for estimating the intrinsic geometry of a data manifold based on a rough estimate of each data point’s neighbors on the manifold. Isomap is highly efficient and generally applicable to a broad range of data sources and dimensionalities.
In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs. It is named after Brenda Baker, who announced it in a 1983 conference and published it in the Journal of the ACM in 1994.
In structure mining, a graph kernel is a kernel function that computes an inner product on graphs. Graph kernels can be intuitively understood as functions measuring the similarity of pairs of graphs. They allow kernelized learning algorithms such as support vector machines to work directly on graphs, without having to do feature extraction to transform them to fixed-length, real-valued feature vectors. They find applications in bioinformatics, in chemoinformatics, and in social network analysis.
In mathematical logic and computer science, two-variable logic is the fragment of first-order logic where formulae can be written using only two different variables. This fragment is usually studied without function symbols.
In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that can be used in these sentences. The first-order logic of graphs concerns sentences in which the variables and predicates concern individual vertices and edges of a graph, while monadic second-order graph logic allows quantification over sets of vertices or edges. Logics based on least fixed point operators allow more general predicates over tuples of vertices, but these predicates can only be constructed through fixed-point operators, restricting their power.
A graph neural network (GNN) belongs to a class of artificial neural networks for processing data that can be represented as graphs.
In graph theory and theoretical computer science, the colour refinement algorithm also known as the naive vertex classification, or the 1-dimensional version of the Weisfeiler-Leman algorithm, is a routine used for testing whether two graphs are isomorphic. While it solves graph isomorphism on almost all graphs, there are graphs such as all regular graphs that cannot be distinguished using colour refinement.
This Weisfeiler Lehman framework operates on top of existing graph kernels and is inspired by the Weisfeiler-Lehman test of graph isomorphism [WL68].