4
$\begingroup$

I am reading An Optimal Lower Bound on the Number of Variables for Graph Identification (1992)

On page 4 , the paper says,

The second hope was partly based on the following result of Cameron [14], obtained independently by Gol’fand (cf. [19, 31]). Let us call a graph k-regular, if the number of common neighbors of a k element subset of vertices only depends on the isomorphism type of the subgraph induced by the k vertices. (1-regular and 2-regular graphs are well known as regular and strongly regular graphs respectively.) Cameron and Gol’fand have shown that apart from the pentagon and the line graph of K(3,3), only the trivial examples of 5-regular graphs exist, namely the disjoint unions of complete graphs of equal size, and their complements (complete multipartite graphs). These graphs are homogeneous, i.e., all isomorphisms of their subgraphs extend to automorphisms. Therefore, they are immune to k-dim W-L refinements for any k: No refinement beyond the isomorphism type of k-tuples will follow. However, for any other graph, the Cameron-Gol’fand result assures us that the 5-dim W-L method will give at least some nontrivial partitioning of the 5-tuples.

W-L refinement and Weisfeiler-Lehman Method has same meaning. I understand 1 dimensional Weisfeiler-Lehman Method or vertex classification. But I am having hard time to grasp k dimensional Weisfeiler-Lehman Method or k-tuple coloring algorithm (named k-dim W-L by Babai) for $k>2$.

Can anyone provide an example for k dimensional Weisfeiler-Lehman Method for $k>2$ or give an explanation ? It would be helpful, to understand the process.

Thanks!

$\endgroup$

1 Answer 1

0
+50
$\begingroup$

For $k \geq 2$, $k$-WL works as follows:

  • Initial Coloring: Two $k$-tuples of vertices $(g_{1}, \ldots, g_{k})$ and $(h_{1}, \ldots, h_{k})$ receive the same initial color precisely if the map $g_{i} \mapsto h_{i}$ for all $i \in [k]$ is an isomorphism of the subgraphs induced by $\{g_{1}, \ldots, g_{k}\}$ and $\{h_{1}, \ldots, h_{k}\}$. Note that we are asking if a specific map (the map sending $g_{i} \mapsto h_{i}$) is an isomorphism; this is more specific than asking if the induced subgraphs are isomorphic.

  • Refinement: The color assigned to a given $k$-tuple $\overline{g}$ at round $r > 0$ takes into account (i) the color assigned to $\overline{g}$ at round $r-1$, and (ii) the multiset of colors of the "nearby" $k$-tuples (plus some additional structure). Here, nearby means Hamming distance $1$. Intuitively, the color assigned to $\overline{g}$ at round $r$ takes into account the closed Hamming distance $1$ neighborhood.

The precise formulation of the refinement step can be found in the WL literature (e.g., Section 2.2 https://arxiv.org/pdf/2106.16218.pdf). The notation isn't intuitive, and most folks in the WL community don't think about the colored $k$-tuples directly. Rather, they use the Ehrenfeucht--Fraisse pebble game formulation to analyze WL. In other words, don't worry too much about the technicalities of the refinement step beyond the intuition in the last paragraph.

There are two pebble games equivalent to WL: one by Immerman & Lander, and the other by Hella. We are given two graphs $G$ and $H$. In both games, we have two players: Spoiler and Duplicator. Spoiler's goal is to establish that $G \not \cong H$, while Duplicator seeks to match (or duplicate) structure Spoiler points out in one graph in the other.

Each round of Hella's game proceeds as follow:

  1. Spoiler picks up a pair of pebbles $(p_{i}, p_{i}')$. This could be an unused pair of pebbles or a pair already on vertices.

  2. We check the winning condition. Namely, consider the pebbles on vertices. Is the map $p_{j} \mapsto p_{j}'$ for all $j$ an isomorphism of the corresponding induced subgraphs? If so, Duplicator wins at the given round. Otherwise, Spoiler wins.

  3. Duplicator chooses a bijection $f : V(G) \to V(H)$.

  4. Spoiler places pebble $p_{i}$ on some vertex $v \in V(G)$ and $p_{i}'$ on $f(v)$.

It is known that $k$-WL run for $r$-rounds is equivalent to the following:

  • The $(k+1)$-pebble, $r$-round pebble game (both Hella's version and the version by Immerman & Lander)
  • The $(k+1)$-variable, quantifier depth $\leq r$ fragment of First Order logic with counting quantifiers. This fragment is denoted $\mathcal{C}_{k+1,r}$.

Edit: While there are folks that think about higher-dimensional WL in terms of the colorings (c.f., Babai's quasipolynomial-time GI paper), most of the WL community thinks about WL in terms of Descriptive Complexity (Pebble Game and Logics; see for instance, the works of Grohe, Kiefer, Neuen, and Schweitzer). I am partial to the pebble game b/c it allows us to get our hands around higher-dimensional WL with a little more ease.

Here are some examples.

Claim: Let $G, H$ be graphs on $n$ vertices. Suppose Duplicator chooses a bijection $f : V(G) \to V(H)$ such that $\text{deg}(v) \neq \text{deg}(f(v))$. Then Spoiler can win with $2$ pebbles and $2$ rounds.

Proof: WLOG, suppose $\text{deg}(v) > \text{deg}(f(v))$; otherwise, we reverse the roles of $G$ and $H$. Spoiler begins by pebbling $v \mapsto f(v)$. Let $f' : V(G) \to V(H)$ be the bijection Duplicator selects at the next round. As $\text{deg}(v) < \text{deg}(f(v))$, there exists $u \in N(v)$ such that $f'(u) \not \in N(f(v))$. Spoiler pebbles $u$. As $uv \in E(G)$ and $f'(u)f(v) \not \in E(H)$, the map $(v, u) \mapsto (f(v), f'(u))$ is not an isomorphism of the induced subgraphs. So Spoiler wins.

Claim: Suppose $G$ and $H$ are graphs on $n$ vertices with different degree sequences. Then Spoiler can win with $2$ pebbles and $2$ rounds.

Proof: As $G$ and $H$ have different degree sequences, any bijection $f : V(G) \to V(H)$ Duplicator chooses must map some vertex $v$ to $f(v)$ where $\text{deg}(v) \neq \text{deg}(f(v))$. Spoiler wins by the previous claim.

Claim: Suppose $G$ is connected and $H$ is not. Then Spoiler can win.

Proof: Spoiler pebbles some vertex $v$ at the first round. Let $f : V(G) \to V(H)$ be the next bijection Duplicator selects. Necessarily, Duplicator must map some vertex $u \in V(G)$ to some vertex $f(u)$ where $f(u), f(v)$ belong to different components. Spoiler pebbles $u \mapsto f(u)$. Using one additional pebble, Spoiler explores the path from $u \to v$ and wins.

Here are some exercises:

  • Analyze the third claim. How many rounds are required? Can you improve the round complexity to use $O(\log n)$ rounds? [Hint: Use a repeated halving strategy.]
  • Can you show that if $G$ contains a cycle and $H$ does not, then Spoiler wins?
  • Can you show that if $G$ is a tree and $H$ is not, then Spoiler wins?

Note that whenever Spoiler wins, WL will distinguish the two graphs.

$\endgroup$
2
  • $\begingroup$ Plz provide an example to illustrate. $\endgroup$
    – Michael
    Jun 16 at 17:19
  • $\begingroup$ I edited my answer yesterday. Check now. $\endgroup$
    – ml0105
    Jun 24 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.