Hard connected instances for Weisfeiler-Lehman test of isomorphism










4














There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm.



enter image description here



However, one of these graphs is disconnected. So what are the instances of undirected connected graphs for which WL algorithm fails?










share|cite|improve this question























  • Would connecting all vertices to a common vertex work?
    – Yuval Filmus
    yesterday






  • 1




    I guess what you mean is that you add additional node to the graphs above, which is connected to every vertex?
    – novadiva
    yesterday






  • 1




    @YuvalFilmus Epic finished, finally. :)
    – David Richerby
    yesterday






  • 1




    I don't remember WL but don't all $k$-regular $n$-vertex graphs all lead to the same result, thus fail WL?
    – Pål GD
    yesterday







  • 1




    @PÃ¥lGD Damnit, another short answer.
    – David Richerby
    8 hours ago















4














There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm.



enter image description here



However, one of these graphs is disconnected. So what are the instances of undirected connected graphs for which WL algorithm fails?










share|cite|improve this question























  • Would connecting all vertices to a common vertex work?
    – Yuval Filmus
    yesterday






  • 1




    I guess what you mean is that you add additional node to the graphs above, which is connected to every vertex?
    – novadiva
    yesterday






  • 1




    @YuvalFilmus Epic finished, finally. :)
    – David Richerby
    yesterday






  • 1




    I don't remember WL but don't all $k$-regular $n$-vertex graphs all lead to the same result, thus fail WL?
    – Pål GD
    yesterday







  • 1




    @PÃ¥lGD Damnit, another short answer.
    – David Richerby
    8 hours ago













4












4








4


1





There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm.



enter image description here



However, one of these graphs is disconnected. So what are the instances of undirected connected graphs for which WL algorithm fails?










share|cite|improve this question















There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm.



enter image description here



However, one of these graphs is disconnected. So what are the instances of undirected connected graphs for which WL algorithm fails?







graphs graph-theory combinatorics graph-isomorphism






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited yesterday

























asked yesterday









novadiva

1766




1766











  • Would connecting all vertices to a common vertex work?
    – Yuval Filmus
    yesterday






  • 1




    I guess what you mean is that you add additional node to the graphs above, which is connected to every vertex?
    – novadiva
    yesterday






  • 1




    @YuvalFilmus Epic finished, finally. :)
    – David Richerby
    yesterday






  • 1




    I don't remember WL but don't all $k$-regular $n$-vertex graphs all lead to the same result, thus fail WL?
    – Pål GD
    yesterday







  • 1




    @PÃ¥lGD Damnit, another short answer.
    – David Richerby
    8 hours ago
















  • Would connecting all vertices to a common vertex work?
    – Yuval Filmus
    yesterday






  • 1




    I guess what you mean is that you add additional node to the graphs above, which is connected to every vertex?
    – novadiva
    yesterday






  • 1




    @YuvalFilmus Epic finished, finally. :)
    – David Richerby
    yesterday






  • 1




    I don't remember WL but don't all $k$-regular $n$-vertex graphs all lead to the same result, thus fail WL?
    – Pål GD
    yesterday







  • 1




    @PÃ¥lGD Damnit, another short answer.
    – David Richerby
    8 hours ago















Would connecting all vertices to a common vertex work?
– Yuval Filmus
yesterday




Would connecting all vertices to a common vertex work?
– Yuval Filmus
yesterday




1




1




I guess what you mean is that you add additional node to the graphs above, which is connected to every vertex?
– novadiva
yesterday




I guess what you mean is that you add additional node to the graphs above, which is connected to every vertex?
– novadiva
yesterday




1




1




@YuvalFilmus Epic finished, finally. :)
– David Richerby
yesterday




@YuvalFilmus Epic finished, finally. :)
– David Richerby
yesterday




1




1




I don't remember WL but don't all $k$-regular $n$-vertex graphs all lead to the same result, thus fail WL?
– Pål GD
yesterday





I don't remember WL but don't all $k$-regular $n$-vertex graphs all lead to the same result, thus fail WL?
– Pål GD
yesterday





1




1




@PÃ¥lGD Damnit, another short answer.
– David Richerby
8 hours ago




@PÃ¥lGD Damnit, another short answer.
– David Richerby
8 hours ago










3 Answers
3






active

oldest

votes


















6














Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman. The following construction is due to Cai, Fürer and Immerman (An Optimal Lower Bound on the Number of Variables for Graph Identification, Combinatorica 12(4):389–410, 1992; PDF).



Take any connected, $3$-regular graph $G=(V,E)$. We will produce non-isomorphic graphs $G_parallel$ and $G_times$ from $G$, that are indistinguishable by Weisfeiler–Lehman. These will be made by producing a gadget for each vertex of $G$ and, for each edge $xyin E$, connecting the gadgets for $x$ and $y$ by a pair of parallel edges.



The vertices of $G_parallel$ are is defined as follows.



  • For each $xyin E$, we create four (distinct) vertices, $a_x,y$, $a_y,x$, $b_x,y$ and $b_y,x$.


  • For each $xin V$, we create a vertex $c_x,S$ for each odd-cardinality subset of $Gamma(x)$ (the neighbours of $x$ in $G$). So, if $x$'s neighbours are $u$, $v$ and $w$, we create vertices $c_x,u$, $c_x,v$, $c_x,w$ and $c_x,u,v,w$.


The edges of $G_parallel$ are defined as follows. For each edge $xyin E$, we add:



  • the two edges $a_x,ya_y,x$ and $b_x,yb_y,x$;

  • the edges $a_x,yc_x,S$ for each $S$ such that $yin S$;

  • the edges $b_x,yc_x,S$ for each $S$ such that $ynotin S$.

Note that $G$ is undirected so if $xyin E$, then $yxin E$ also, and we follow the above rules twice for each edge of $G$.



Now, let $xy$ be any edge in $G$ and let $G_xy$ be the graph made from $G_parallel$ by deleting the edges $a_x,ya_y,x$ and $b_x,yb_y,x$ and replacing them with the "cross" edges $a_x,yb_y,x$ and $b_x,ya_y,x$. The following lemma is the key point of the construction.



Lemma 1. For any edges $uv,xyin E$, the graphs $G_uv$ and $G_xy$ are isomorphic.



Proof sketch. You can move the cross edge around the graph in the following sense. For any pair of edges $ij,jkin E$, there's an isomorphism of $G_ij$ that exchanges $a_j,i$ and $b_j,i$ and exchanges $a_j,k$ and $b_j,k$. This isomorphism is a permutation of the vertices $c_j,S$, and it fixes every other vertex in $G_ij$. If you draw the fragment of the graph corresponding to vertex $j$ and its incident edges, the isomorphism should be pretty obvious.



This means that $G_ijsimeq G_jk$, because the isomorphism "uncrosses" the edge $ij$ and "crosses" the edge $jk$. Since $G$ is connected, it contains a path whose first edge is $uv$ and whose last edge is $xy$, and we can use the isomorphisms corresponding to each adjacent pair of edges in this path to move the cross in $G_uv$ to $xy$. $Box$



By Lemma 1, we're entitled to use the name $G_times$ for an arbitrary graph $G_xy$. We now have the graphs $G_parallel$ and $G_times$; it remains to show that they're non-isomorphic and that they're indistinguishable to Weisfeiler–Lehman.



Lemma 2. For any connected, 3-regular graph $G$, we have $G_parallel notsimeq G_times$.



Proof sketch. It turns out that the only isomorphisms of $G_parallel$ and $G_times$ are isomorphisms induced by isomorphisms of $G$, and isomorphisms of the form used in the proof of Lemma 1. But no such isomorphism can transform $G_times$ into $G_parallel$ because $G_times$ has a cross edge and $G_parallel$ does not. $Box$



Now, indistinguishability. Weisfeiler–Lehman is definable in so-called "fixed-point logic with counting." This is first-order logic plus:



  • counting quantifiers: for each natural number $n$, you can write $exists^geq nx,varphi(x)$, meaning "There exist at least $n$ values of $x$ that satisfy $varphi$." This can already be expressed in ordinary first-order logic, just by saying that there exist distinct $x_1, dots, x_n$ that all satisfy $varphi$, but the (rather subtle) point here is that the counting quantifier only uses just one variable, whereas the "pure" first-order expression uses $n$ distinct variables.


  • inductive definitions. These let you build up a relation $R$ as follows. You start with $R=emptyset$. Then, you add to $R$ all the tuples that satisfy a formula $varphi$, and keep doing that until you run out of tuples to add. $varphi$ itself can depend on $R$, so you can build up some interesting things.


In particular, you can build up an equivalence relation corresponding to the colour-classes of Weisfeiler–Lehman. The counting quantifiers let you talk about the numbe of neighbours of each colour, and the inductive definitions let you recursively refine the colouring based on the number of neighbours of each colour in the previous step.



A separator of a graph $G=(V,E)$ is a set $Ssubseteq V$ such that no component of $G-S$ has more than $|V|/2$ vertices. In the following, I say "less than about $2k$" because I'm silently translating from fixed-point logic with counting to so-called "infinitary logic with counting", which roughly doubles the number of variables. I don't remember the exact details, and it's not important enough to hunt them down.



Theorem 3. Let $varphi$ be a formula of fixed-point logic with counting, using $k$ distinct variables. If $G$ is a graph with no separator of size less than about $2k$, then $varphi$ cannot distinguish $G_parallel$ from $G_times$.



Proof sketch. Very roughly speaking, while you're evaluating the formula $varphi$ on $G_parallel$ or $G_times$, you might need to consider $k$ vertices as being the value of some variables at the current iteration of an inductive construction and $k$ more variables as being the value of the variables at the previous iteration. The fact that $G$ has no small separators means that, even if we fix those vertices, we can still move the cross around in a large component of the rest of the graph, without the formula "knowing" that we've done that, so the formula can never "see" the cross, so it can never tell the difference between the graph with the cross and the graph without it. $Box$



For any fixed $d$, $d$-dimensional Weisfeiler–Lehman can be expressed as a formula of fixed-point logic with counting, using some number $k$ of variables ($kapprox 2d$ is enough, as I recall). Since that formula can't tell the difference between the non-isomorphic graphs $G_parallel$ and $G_times$ as long as $G$ has no small separators, nor can Weisfeiler–Lehman.



Guess who got a PhD doing this kind of stuff...






share|cite|improve this answer




























    5














    Connect all vertices to a common one.






    share|cite|improve this answer




























      2














      One epic answer by David, one simplest answer by Yuval. However, there is no graphs. I mean, actual visual graphs.



      Here is the famous beautiful negative instances to 1-dimensional Weisfeiler-Lehman test of graph isomorphism. The Shrikhande graph is at the left and the $4times 4$ rook's graph is at the right.
      https://mathematicaladd.wordpress.com/2017/02/06/visualizing-the-difference-between-the-4x4-rooks-graph-and-the-shrikhande-graph/The above picture is taken from mathematicaladd.wordpress.com.





      Both graphs are strongly regular with parameters $16,6,2,2$. In the Shrikhande graph, the neighbors of each vertex form a cycle of six vertices. In the $4times 4$ rook's graph, the neighbors of each vertex form two disjoint triangles.






      share|cite|improve this answer




















        Your Answer





        StackExchange.ifUsing("editor", function ()
        return StackExchange.using("mathjaxEditing", function ()
        StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
        StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
        );
        );
        , "mathjax-editing");

        StackExchange.ready(function()
        var channelOptions =
        tags: "".split(" "),
        id: "419"
        ;
        initTagRenderer("".split(" "), "".split(" "), channelOptions);

        StackExchange.using("externalEditor", function()
        // Have to fire editor after snippets, if snippets enabled
        if (StackExchange.settings.snippets.snippetsEnabled)
        StackExchange.using("snippets", function()
        createEditor();
        );

        else
        createEditor();

        );

        function createEditor()
        StackExchange.prepareEditor(
        heartbeatType: 'answer',
        autoActivateHeartbeat: false,
        convertImagesToLinks: false,
        noModals: true,
        showLowRepImageUploadWarning: true,
        reputationToPostImages: null,
        bindNavPrevention: true,
        postfix: "",
        imageUploader:
        brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
        contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
        allowUrls: true
        ,
        onDemand: true,
        discardSelector: ".discard-answer"
        ,immediatelyShowMarkdownHelp:true
        );



        );













        draft saved

        draft discarded


















        StackExchange.ready(
        function ()
        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102062%2fhard-connected-instances-for-weisfeiler-lehman-test-of-isomorphism%23new-answer', 'question_page');

        );

        Post as a guest















        Required, but never shown

























        3 Answers
        3






        active

        oldest

        votes








        3 Answers
        3






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        6














        Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman. The following construction is due to Cai, Fürer and Immerman (An Optimal Lower Bound on the Number of Variables for Graph Identification, Combinatorica 12(4):389–410, 1992; PDF).



        Take any connected, $3$-regular graph $G=(V,E)$. We will produce non-isomorphic graphs $G_parallel$ and $G_times$ from $G$, that are indistinguishable by Weisfeiler–Lehman. These will be made by producing a gadget for each vertex of $G$ and, for each edge $xyin E$, connecting the gadgets for $x$ and $y$ by a pair of parallel edges.



        The vertices of $G_parallel$ are is defined as follows.



        • For each $xyin E$, we create four (distinct) vertices, $a_x,y$, $a_y,x$, $b_x,y$ and $b_y,x$.


        • For each $xin V$, we create a vertex $c_x,S$ for each odd-cardinality subset of $Gamma(x)$ (the neighbours of $x$ in $G$). So, if $x$'s neighbours are $u$, $v$ and $w$, we create vertices $c_x,u$, $c_x,v$, $c_x,w$ and $c_x,u,v,w$.


        The edges of $G_parallel$ are defined as follows. For each edge $xyin E$, we add:



        • the two edges $a_x,ya_y,x$ and $b_x,yb_y,x$;

        • the edges $a_x,yc_x,S$ for each $S$ such that $yin S$;

        • the edges $b_x,yc_x,S$ for each $S$ such that $ynotin S$.

        Note that $G$ is undirected so if $xyin E$, then $yxin E$ also, and we follow the above rules twice for each edge of $G$.



        Now, let $xy$ be any edge in $G$ and let $G_xy$ be the graph made from $G_parallel$ by deleting the edges $a_x,ya_y,x$ and $b_x,yb_y,x$ and replacing them with the "cross" edges $a_x,yb_y,x$ and $b_x,ya_y,x$. The following lemma is the key point of the construction.



        Lemma 1. For any edges $uv,xyin E$, the graphs $G_uv$ and $G_xy$ are isomorphic.



        Proof sketch. You can move the cross edge around the graph in the following sense. For any pair of edges $ij,jkin E$, there's an isomorphism of $G_ij$ that exchanges $a_j,i$ and $b_j,i$ and exchanges $a_j,k$ and $b_j,k$. This isomorphism is a permutation of the vertices $c_j,S$, and it fixes every other vertex in $G_ij$. If you draw the fragment of the graph corresponding to vertex $j$ and its incident edges, the isomorphism should be pretty obvious.



        This means that $G_ijsimeq G_jk$, because the isomorphism "uncrosses" the edge $ij$ and "crosses" the edge $jk$. Since $G$ is connected, it contains a path whose first edge is $uv$ and whose last edge is $xy$, and we can use the isomorphisms corresponding to each adjacent pair of edges in this path to move the cross in $G_uv$ to $xy$. $Box$



        By Lemma 1, we're entitled to use the name $G_times$ for an arbitrary graph $G_xy$. We now have the graphs $G_parallel$ and $G_times$; it remains to show that they're non-isomorphic and that they're indistinguishable to Weisfeiler–Lehman.



        Lemma 2. For any connected, 3-regular graph $G$, we have $G_parallel notsimeq G_times$.



        Proof sketch. It turns out that the only isomorphisms of $G_parallel$ and $G_times$ are isomorphisms induced by isomorphisms of $G$, and isomorphisms of the form used in the proof of Lemma 1. But no such isomorphism can transform $G_times$ into $G_parallel$ because $G_times$ has a cross edge and $G_parallel$ does not. $Box$



        Now, indistinguishability. Weisfeiler–Lehman is definable in so-called "fixed-point logic with counting." This is first-order logic plus:



        • counting quantifiers: for each natural number $n$, you can write $exists^geq nx,varphi(x)$, meaning "There exist at least $n$ values of $x$ that satisfy $varphi$." This can already be expressed in ordinary first-order logic, just by saying that there exist distinct $x_1, dots, x_n$ that all satisfy $varphi$, but the (rather subtle) point here is that the counting quantifier only uses just one variable, whereas the "pure" first-order expression uses $n$ distinct variables.


        • inductive definitions. These let you build up a relation $R$ as follows. You start with $R=emptyset$. Then, you add to $R$ all the tuples that satisfy a formula $varphi$, and keep doing that until you run out of tuples to add. $varphi$ itself can depend on $R$, so you can build up some interesting things.


        In particular, you can build up an equivalence relation corresponding to the colour-classes of Weisfeiler–Lehman. The counting quantifiers let you talk about the numbe of neighbours of each colour, and the inductive definitions let you recursively refine the colouring based on the number of neighbours of each colour in the previous step.



        A separator of a graph $G=(V,E)$ is a set $Ssubseteq V$ such that no component of $G-S$ has more than $|V|/2$ vertices. In the following, I say "less than about $2k$" because I'm silently translating from fixed-point logic with counting to so-called "infinitary logic with counting", which roughly doubles the number of variables. I don't remember the exact details, and it's not important enough to hunt them down.



        Theorem 3. Let $varphi$ be a formula of fixed-point logic with counting, using $k$ distinct variables. If $G$ is a graph with no separator of size less than about $2k$, then $varphi$ cannot distinguish $G_parallel$ from $G_times$.



        Proof sketch. Very roughly speaking, while you're evaluating the formula $varphi$ on $G_parallel$ or $G_times$, you might need to consider $k$ vertices as being the value of some variables at the current iteration of an inductive construction and $k$ more variables as being the value of the variables at the previous iteration. The fact that $G$ has no small separators means that, even if we fix those vertices, we can still move the cross around in a large component of the rest of the graph, without the formula "knowing" that we've done that, so the formula can never "see" the cross, so it can never tell the difference between the graph with the cross and the graph without it. $Box$



        For any fixed $d$, $d$-dimensional Weisfeiler–Lehman can be expressed as a formula of fixed-point logic with counting, using some number $k$ of variables ($kapprox 2d$ is enough, as I recall). Since that formula can't tell the difference between the non-isomorphic graphs $G_parallel$ and $G_times$ as long as $G$ has no small separators, nor can Weisfeiler–Lehman.



        Guess who got a PhD doing this kind of stuff...






        share|cite|improve this answer

























          6














          Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman. The following construction is due to Cai, Fürer and Immerman (An Optimal Lower Bound on the Number of Variables for Graph Identification, Combinatorica 12(4):389–410, 1992; PDF).



          Take any connected, $3$-regular graph $G=(V,E)$. We will produce non-isomorphic graphs $G_parallel$ and $G_times$ from $G$, that are indistinguishable by Weisfeiler–Lehman. These will be made by producing a gadget for each vertex of $G$ and, for each edge $xyin E$, connecting the gadgets for $x$ and $y$ by a pair of parallel edges.



          The vertices of $G_parallel$ are is defined as follows.



          • For each $xyin E$, we create four (distinct) vertices, $a_x,y$, $a_y,x$, $b_x,y$ and $b_y,x$.


          • For each $xin V$, we create a vertex $c_x,S$ for each odd-cardinality subset of $Gamma(x)$ (the neighbours of $x$ in $G$). So, if $x$'s neighbours are $u$, $v$ and $w$, we create vertices $c_x,u$, $c_x,v$, $c_x,w$ and $c_x,u,v,w$.


          The edges of $G_parallel$ are defined as follows. For each edge $xyin E$, we add:



          • the two edges $a_x,ya_y,x$ and $b_x,yb_y,x$;

          • the edges $a_x,yc_x,S$ for each $S$ such that $yin S$;

          • the edges $b_x,yc_x,S$ for each $S$ such that $ynotin S$.

          Note that $G$ is undirected so if $xyin E$, then $yxin E$ also, and we follow the above rules twice for each edge of $G$.



          Now, let $xy$ be any edge in $G$ and let $G_xy$ be the graph made from $G_parallel$ by deleting the edges $a_x,ya_y,x$ and $b_x,yb_y,x$ and replacing them with the "cross" edges $a_x,yb_y,x$ and $b_x,ya_y,x$. The following lemma is the key point of the construction.



          Lemma 1. For any edges $uv,xyin E$, the graphs $G_uv$ and $G_xy$ are isomorphic.



          Proof sketch. You can move the cross edge around the graph in the following sense. For any pair of edges $ij,jkin E$, there's an isomorphism of $G_ij$ that exchanges $a_j,i$ and $b_j,i$ and exchanges $a_j,k$ and $b_j,k$. This isomorphism is a permutation of the vertices $c_j,S$, and it fixes every other vertex in $G_ij$. If you draw the fragment of the graph corresponding to vertex $j$ and its incident edges, the isomorphism should be pretty obvious.



          This means that $G_ijsimeq G_jk$, because the isomorphism "uncrosses" the edge $ij$ and "crosses" the edge $jk$. Since $G$ is connected, it contains a path whose first edge is $uv$ and whose last edge is $xy$, and we can use the isomorphisms corresponding to each adjacent pair of edges in this path to move the cross in $G_uv$ to $xy$. $Box$



          By Lemma 1, we're entitled to use the name $G_times$ for an arbitrary graph $G_xy$. We now have the graphs $G_parallel$ and $G_times$; it remains to show that they're non-isomorphic and that they're indistinguishable to Weisfeiler–Lehman.



          Lemma 2. For any connected, 3-regular graph $G$, we have $G_parallel notsimeq G_times$.



          Proof sketch. It turns out that the only isomorphisms of $G_parallel$ and $G_times$ are isomorphisms induced by isomorphisms of $G$, and isomorphisms of the form used in the proof of Lemma 1. But no such isomorphism can transform $G_times$ into $G_parallel$ because $G_times$ has a cross edge and $G_parallel$ does not. $Box$



          Now, indistinguishability. Weisfeiler–Lehman is definable in so-called "fixed-point logic with counting." This is first-order logic plus:



          • counting quantifiers: for each natural number $n$, you can write $exists^geq nx,varphi(x)$, meaning "There exist at least $n$ values of $x$ that satisfy $varphi$." This can already be expressed in ordinary first-order logic, just by saying that there exist distinct $x_1, dots, x_n$ that all satisfy $varphi$, but the (rather subtle) point here is that the counting quantifier only uses just one variable, whereas the "pure" first-order expression uses $n$ distinct variables.


          • inductive definitions. These let you build up a relation $R$ as follows. You start with $R=emptyset$. Then, you add to $R$ all the tuples that satisfy a formula $varphi$, and keep doing that until you run out of tuples to add. $varphi$ itself can depend on $R$, so you can build up some interesting things.


          In particular, you can build up an equivalence relation corresponding to the colour-classes of Weisfeiler–Lehman. The counting quantifiers let you talk about the numbe of neighbours of each colour, and the inductive definitions let you recursively refine the colouring based on the number of neighbours of each colour in the previous step.



          A separator of a graph $G=(V,E)$ is a set $Ssubseteq V$ such that no component of $G-S$ has more than $|V|/2$ vertices. In the following, I say "less than about $2k$" because I'm silently translating from fixed-point logic with counting to so-called "infinitary logic with counting", which roughly doubles the number of variables. I don't remember the exact details, and it's not important enough to hunt them down.



          Theorem 3. Let $varphi$ be a formula of fixed-point logic with counting, using $k$ distinct variables. If $G$ is a graph with no separator of size less than about $2k$, then $varphi$ cannot distinguish $G_parallel$ from $G_times$.



          Proof sketch. Very roughly speaking, while you're evaluating the formula $varphi$ on $G_parallel$ or $G_times$, you might need to consider $k$ vertices as being the value of some variables at the current iteration of an inductive construction and $k$ more variables as being the value of the variables at the previous iteration. The fact that $G$ has no small separators means that, even if we fix those vertices, we can still move the cross around in a large component of the rest of the graph, without the formula "knowing" that we've done that, so the formula can never "see" the cross, so it can never tell the difference between the graph with the cross and the graph without it. $Box$



          For any fixed $d$, $d$-dimensional Weisfeiler–Lehman can be expressed as a formula of fixed-point logic with counting, using some number $k$ of variables ($kapprox 2d$ is enough, as I recall). Since that formula can't tell the difference between the non-isomorphic graphs $G_parallel$ and $G_times$ as long as $G$ has no small separators, nor can Weisfeiler–Lehman.



          Guess who got a PhD doing this kind of stuff...






          share|cite|improve this answer























            6












            6








            6






            Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman. The following construction is due to Cai, Fürer and Immerman (An Optimal Lower Bound on the Number of Variables for Graph Identification, Combinatorica 12(4):389–410, 1992; PDF).



            Take any connected, $3$-regular graph $G=(V,E)$. We will produce non-isomorphic graphs $G_parallel$ and $G_times$ from $G$, that are indistinguishable by Weisfeiler–Lehman. These will be made by producing a gadget for each vertex of $G$ and, for each edge $xyin E$, connecting the gadgets for $x$ and $y$ by a pair of parallel edges.



            The vertices of $G_parallel$ are is defined as follows.



            • For each $xyin E$, we create four (distinct) vertices, $a_x,y$, $a_y,x$, $b_x,y$ and $b_y,x$.


            • For each $xin V$, we create a vertex $c_x,S$ for each odd-cardinality subset of $Gamma(x)$ (the neighbours of $x$ in $G$). So, if $x$'s neighbours are $u$, $v$ and $w$, we create vertices $c_x,u$, $c_x,v$, $c_x,w$ and $c_x,u,v,w$.


            The edges of $G_parallel$ are defined as follows. For each edge $xyin E$, we add:



            • the two edges $a_x,ya_y,x$ and $b_x,yb_y,x$;

            • the edges $a_x,yc_x,S$ for each $S$ such that $yin S$;

            • the edges $b_x,yc_x,S$ for each $S$ such that $ynotin S$.

            Note that $G$ is undirected so if $xyin E$, then $yxin E$ also, and we follow the above rules twice for each edge of $G$.



            Now, let $xy$ be any edge in $G$ and let $G_xy$ be the graph made from $G_parallel$ by deleting the edges $a_x,ya_y,x$ and $b_x,yb_y,x$ and replacing them with the "cross" edges $a_x,yb_y,x$ and $b_x,ya_y,x$. The following lemma is the key point of the construction.



            Lemma 1. For any edges $uv,xyin E$, the graphs $G_uv$ and $G_xy$ are isomorphic.



            Proof sketch. You can move the cross edge around the graph in the following sense. For any pair of edges $ij,jkin E$, there's an isomorphism of $G_ij$ that exchanges $a_j,i$ and $b_j,i$ and exchanges $a_j,k$ and $b_j,k$. This isomorphism is a permutation of the vertices $c_j,S$, and it fixes every other vertex in $G_ij$. If you draw the fragment of the graph corresponding to vertex $j$ and its incident edges, the isomorphism should be pretty obvious.



            This means that $G_ijsimeq G_jk$, because the isomorphism "uncrosses" the edge $ij$ and "crosses" the edge $jk$. Since $G$ is connected, it contains a path whose first edge is $uv$ and whose last edge is $xy$, and we can use the isomorphisms corresponding to each adjacent pair of edges in this path to move the cross in $G_uv$ to $xy$. $Box$



            By Lemma 1, we're entitled to use the name $G_times$ for an arbitrary graph $G_xy$. We now have the graphs $G_parallel$ and $G_times$; it remains to show that they're non-isomorphic and that they're indistinguishable to Weisfeiler–Lehman.



            Lemma 2. For any connected, 3-regular graph $G$, we have $G_parallel notsimeq G_times$.



            Proof sketch. It turns out that the only isomorphisms of $G_parallel$ and $G_times$ are isomorphisms induced by isomorphisms of $G$, and isomorphisms of the form used in the proof of Lemma 1. But no such isomorphism can transform $G_times$ into $G_parallel$ because $G_times$ has a cross edge and $G_parallel$ does not. $Box$



            Now, indistinguishability. Weisfeiler–Lehman is definable in so-called "fixed-point logic with counting." This is first-order logic plus:



            • counting quantifiers: for each natural number $n$, you can write $exists^geq nx,varphi(x)$, meaning "There exist at least $n$ values of $x$ that satisfy $varphi$." This can already be expressed in ordinary first-order logic, just by saying that there exist distinct $x_1, dots, x_n$ that all satisfy $varphi$, but the (rather subtle) point here is that the counting quantifier only uses just one variable, whereas the "pure" first-order expression uses $n$ distinct variables.


            • inductive definitions. These let you build up a relation $R$ as follows. You start with $R=emptyset$. Then, you add to $R$ all the tuples that satisfy a formula $varphi$, and keep doing that until you run out of tuples to add. $varphi$ itself can depend on $R$, so you can build up some interesting things.


            In particular, you can build up an equivalence relation corresponding to the colour-classes of Weisfeiler–Lehman. The counting quantifiers let you talk about the numbe of neighbours of each colour, and the inductive definitions let you recursively refine the colouring based on the number of neighbours of each colour in the previous step.



            A separator of a graph $G=(V,E)$ is a set $Ssubseteq V$ such that no component of $G-S$ has more than $|V|/2$ vertices. In the following, I say "less than about $2k$" because I'm silently translating from fixed-point logic with counting to so-called "infinitary logic with counting", which roughly doubles the number of variables. I don't remember the exact details, and it's not important enough to hunt them down.



            Theorem 3. Let $varphi$ be a formula of fixed-point logic with counting, using $k$ distinct variables. If $G$ is a graph with no separator of size less than about $2k$, then $varphi$ cannot distinguish $G_parallel$ from $G_times$.



            Proof sketch. Very roughly speaking, while you're evaluating the formula $varphi$ on $G_parallel$ or $G_times$, you might need to consider $k$ vertices as being the value of some variables at the current iteration of an inductive construction and $k$ more variables as being the value of the variables at the previous iteration. The fact that $G$ has no small separators means that, even if we fix those vertices, we can still move the cross around in a large component of the rest of the graph, without the formula "knowing" that we've done that, so the formula can never "see" the cross, so it can never tell the difference between the graph with the cross and the graph without it. $Box$



            For any fixed $d$, $d$-dimensional Weisfeiler–Lehman can be expressed as a formula of fixed-point logic with counting, using some number $k$ of variables ($kapprox 2d$ is enough, as I recall). Since that formula can't tell the difference between the non-isomorphic graphs $G_parallel$ and $G_times$ as long as $G$ has no small separators, nor can Weisfeiler–Lehman.



            Guess who got a PhD doing this kind of stuff...






            share|cite|improve this answer












            Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman. The following construction is due to Cai, Fürer and Immerman (An Optimal Lower Bound on the Number of Variables for Graph Identification, Combinatorica 12(4):389–410, 1992; PDF).



            Take any connected, $3$-regular graph $G=(V,E)$. We will produce non-isomorphic graphs $G_parallel$ and $G_times$ from $G$, that are indistinguishable by Weisfeiler–Lehman. These will be made by producing a gadget for each vertex of $G$ and, for each edge $xyin E$, connecting the gadgets for $x$ and $y$ by a pair of parallel edges.



            The vertices of $G_parallel$ are is defined as follows.



            • For each $xyin E$, we create four (distinct) vertices, $a_x,y$, $a_y,x$, $b_x,y$ and $b_y,x$.


            • For each $xin V$, we create a vertex $c_x,S$ for each odd-cardinality subset of $Gamma(x)$ (the neighbours of $x$ in $G$). So, if $x$'s neighbours are $u$, $v$ and $w$, we create vertices $c_x,u$, $c_x,v$, $c_x,w$ and $c_x,u,v,w$.


            The edges of $G_parallel$ are defined as follows. For each edge $xyin E$, we add:



            • the two edges $a_x,ya_y,x$ and $b_x,yb_y,x$;

            • the edges $a_x,yc_x,S$ for each $S$ such that $yin S$;

            • the edges $b_x,yc_x,S$ for each $S$ such that $ynotin S$.

            Note that $G$ is undirected so if $xyin E$, then $yxin E$ also, and we follow the above rules twice for each edge of $G$.



            Now, let $xy$ be any edge in $G$ and let $G_xy$ be the graph made from $G_parallel$ by deleting the edges $a_x,ya_y,x$ and $b_x,yb_y,x$ and replacing them with the "cross" edges $a_x,yb_y,x$ and $b_x,ya_y,x$. The following lemma is the key point of the construction.



            Lemma 1. For any edges $uv,xyin E$, the graphs $G_uv$ and $G_xy$ are isomorphic.



            Proof sketch. You can move the cross edge around the graph in the following sense. For any pair of edges $ij,jkin E$, there's an isomorphism of $G_ij$ that exchanges $a_j,i$ and $b_j,i$ and exchanges $a_j,k$ and $b_j,k$. This isomorphism is a permutation of the vertices $c_j,S$, and it fixes every other vertex in $G_ij$. If you draw the fragment of the graph corresponding to vertex $j$ and its incident edges, the isomorphism should be pretty obvious.



            This means that $G_ijsimeq G_jk$, because the isomorphism "uncrosses" the edge $ij$ and "crosses" the edge $jk$. Since $G$ is connected, it contains a path whose first edge is $uv$ and whose last edge is $xy$, and we can use the isomorphisms corresponding to each adjacent pair of edges in this path to move the cross in $G_uv$ to $xy$. $Box$



            By Lemma 1, we're entitled to use the name $G_times$ for an arbitrary graph $G_xy$. We now have the graphs $G_parallel$ and $G_times$; it remains to show that they're non-isomorphic and that they're indistinguishable to Weisfeiler–Lehman.



            Lemma 2. For any connected, 3-regular graph $G$, we have $G_parallel notsimeq G_times$.



            Proof sketch. It turns out that the only isomorphisms of $G_parallel$ and $G_times$ are isomorphisms induced by isomorphisms of $G$, and isomorphisms of the form used in the proof of Lemma 1. But no such isomorphism can transform $G_times$ into $G_parallel$ because $G_times$ has a cross edge and $G_parallel$ does not. $Box$



            Now, indistinguishability. Weisfeiler–Lehman is definable in so-called "fixed-point logic with counting." This is first-order logic plus:



            • counting quantifiers: for each natural number $n$, you can write $exists^geq nx,varphi(x)$, meaning "There exist at least $n$ values of $x$ that satisfy $varphi$." This can already be expressed in ordinary first-order logic, just by saying that there exist distinct $x_1, dots, x_n$ that all satisfy $varphi$, but the (rather subtle) point here is that the counting quantifier only uses just one variable, whereas the "pure" first-order expression uses $n$ distinct variables.


            • inductive definitions. These let you build up a relation $R$ as follows. You start with $R=emptyset$. Then, you add to $R$ all the tuples that satisfy a formula $varphi$, and keep doing that until you run out of tuples to add. $varphi$ itself can depend on $R$, so you can build up some interesting things.


            In particular, you can build up an equivalence relation corresponding to the colour-classes of Weisfeiler–Lehman. The counting quantifiers let you talk about the numbe of neighbours of each colour, and the inductive definitions let you recursively refine the colouring based on the number of neighbours of each colour in the previous step.



            A separator of a graph $G=(V,E)$ is a set $Ssubseteq V$ such that no component of $G-S$ has more than $|V|/2$ vertices. In the following, I say "less than about $2k$" because I'm silently translating from fixed-point logic with counting to so-called "infinitary logic with counting", which roughly doubles the number of variables. I don't remember the exact details, and it's not important enough to hunt them down.



            Theorem 3. Let $varphi$ be a formula of fixed-point logic with counting, using $k$ distinct variables. If $G$ is a graph with no separator of size less than about $2k$, then $varphi$ cannot distinguish $G_parallel$ from $G_times$.



            Proof sketch. Very roughly speaking, while you're evaluating the formula $varphi$ on $G_parallel$ or $G_times$, you might need to consider $k$ vertices as being the value of some variables at the current iteration of an inductive construction and $k$ more variables as being the value of the variables at the previous iteration. The fact that $G$ has no small separators means that, even if we fix those vertices, we can still move the cross around in a large component of the rest of the graph, without the formula "knowing" that we've done that, so the formula can never "see" the cross, so it can never tell the difference between the graph with the cross and the graph without it. $Box$



            For any fixed $d$, $d$-dimensional Weisfeiler–Lehman can be expressed as a formula of fixed-point logic with counting, using some number $k$ of variables ($kapprox 2d$ is enough, as I recall). Since that formula can't tell the difference between the non-isomorphic graphs $G_parallel$ and $G_times$ as long as $G$ has no small separators, nor can Weisfeiler–Lehman.



            Guess who got a PhD doing this kind of stuff...







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered yesterday









            David Richerby

            65.9k15100190




            65.9k15100190





















                5














                Connect all vertices to a common one.






                share|cite|improve this answer

























                  5














                  Connect all vertices to a common one.






                  share|cite|improve this answer























                    5












                    5








                    5






                    Connect all vertices to a common one.






                    share|cite|improve this answer












                    Connect all vertices to a common one.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered yesterday









                    Yuval Filmus

                    189k12177340




                    189k12177340





















                        2














                        One epic answer by David, one simplest answer by Yuval. However, there is no graphs. I mean, actual visual graphs.



                        Here is the famous beautiful negative instances to 1-dimensional Weisfeiler-Lehman test of graph isomorphism. The Shrikhande graph is at the left and the $4times 4$ rook's graph is at the right.
                        https://mathematicaladd.wordpress.com/2017/02/06/visualizing-the-difference-between-the-4x4-rooks-graph-and-the-shrikhande-graph/The above picture is taken from mathematicaladd.wordpress.com.





                        Both graphs are strongly regular with parameters $16,6,2,2$. In the Shrikhande graph, the neighbors of each vertex form a cycle of six vertices. In the $4times 4$ rook's graph, the neighbors of each vertex form two disjoint triangles.






                        share|cite|improve this answer

























                          2














                          One epic answer by David, one simplest answer by Yuval. However, there is no graphs. I mean, actual visual graphs.



                          Here is the famous beautiful negative instances to 1-dimensional Weisfeiler-Lehman test of graph isomorphism. The Shrikhande graph is at the left and the $4times 4$ rook's graph is at the right.
                          https://mathematicaladd.wordpress.com/2017/02/06/visualizing-the-difference-between-the-4x4-rooks-graph-and-the-shrikhande-graph/The above picture is taken from mathematicaladd.wordpress.com.





                          Both graphs are strongly regular with parameters $16,6,2,2$. In the Shrikhande graph, the neighbors of each vertex form a cycle of six vertices. In the $4times 4$ rook's graph, the neighbors of each vertex form two disjoint triangles.






                          share|cite|improve this answer























                            2












                            2








                            2






                            One epic answer by David, one simplest answer by Yuval. However, there is no graphs. I mean, actual visual graphs.



                            Here is the famous beautiful negative instances to 1-dimensional Weisfeiler-Lehman test of graph isomorphism. The Shrikhande graph is at the left and the $4times 4$ rook's graph is at the right.
                            https://mathematicaladd.wordpress.com/2017/02/06/visualizing-the-difference-between-the-4x4-rooks-graph-and-the-shrikhande-graph/The above picture is taken from mathematicaladd.wordpress.com.





                            Both graphs are strongly regular with parameters $16,6,2,2$. In the Shrikhande graph, the neighbors of each vertex form a cycle of six vertices. In the $4times 4$ rook's graph, the neighbors of each vertex form two disjoint triangles.






                            share|cite|improve this answer












                            One epic answer by David, one simplest answer by Yuval. However, there is no graphs. I mean, actual visual graphs.



                            Here is the famous beautiful negative instances to 1-dimensional Weisfeiler-Lehman test of graph isomorphism. The Shrikhande graph is at the left and the $4times 4$ rook's graph is at the right.
                            https://mathematicaladd.wordpress.com/2017/02/06/visualizing-the-difference-between-the-4x4-rooks-graph-and-the-shrikhande-graph/The above picture is taken from mathematicaladd.wordpress.com.





                            Both graphs are strongly regular with parameters $16,6,2,2$. In the Shrikhande graph, the neighbors of each vertex form a cycle of six vertices. In the $4times 4$ rook's graph, the neighbors of each vertex form two disjoint triangles.







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered 16 hours ago









                            Apass.Jack

                            6,8411533




                            6,8411533



























                                draft saved

                                draft discarded
















































                                Thanks for contributing an answer to Computer Science Stack Exchange!


                                • Please be sure to answer the question. Provide details and share your research!

                                But avoid …


                                • Asking for help, clarification, or responding to other answers.

                                • Making statements based on opinion; back them up with references or personal experience.

                                Use MathJax to format equations. MathJax reference.


                                To learn more, see our tips on writing great answers.





                                Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                                Please pay close attention to the following guidance:


                                • Please be sure to answer the question. Provide details and share your research!

                                But avoid …


                                • Asking for help, clarification, or responding to other answers.

                                • Making statements based on opinion; back them up with references or personal experience.

                                To learn more, see our tips on writing great answers.




                                draft saved


                                draft discarded














                                StackExchange.ready(
                                function ()
                                StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102062%2fhard-connected-instances-for-weisfeiler-lehman-test-of-isomorphism%23new-answer', 'question_page');

                                );

                                Post as a guest















                                Required, but never shown





















































                                Required, but never shown














                                Required, but never shown












                                Required, but never shown







                                Required, but never shown

































                                Required, but never shown














                                Required, but never shown












                                Required, but never shown







                                Required, but never shown







                                Popular posts from this blog

                                Top Tejano songwriter Luis Silva dead of heart attack at 64

                                政党

                                天津地下鉄3号線