1
$\begingroup$

Color refinement, also known as naive vertex classification or 1-dimensional Weisfeiler-Lehman algorithm, is a combinatorial algorithm that aims to classify the vertices of an undirected simple graph $G = (V,E)$ with set of vertices $V$ and set of edges $E\subseteq V \times V$ by similarity.

It iteratively partitions, or colors, the vertices in a sequence of refinement rounds. Initially, all vertices get the same color. Then in each refinement round, any two vertices $v, w \in V$ that still have the same color get different colors if there is some color $c$ such that $v$ and $w$ have a different number of neighbors of color $c$; otherwise they keep the same color. Thus after the first refinement round, two vertices have the same color if and only they have the same degree (number of incident edges). After the second round, they have the same color if and only if for each $k \in \mathbb{N}_{\geq 1}$ they have the same number of neighbors of degree $k$.

The refinement process necessarily has to stop if in some refinement round the partition induced by the colors is no longer refined, that is, all pairs of vertices that have the same color before the refinement round still have the same color after the round.

On the other hand, a graph labeling is a function $$l : V \rightarrow S $$ to some ordered set $S$, such as the real or integer numbers. Since $S$ is ordered, $l$ induces a weak ordering on the vertex set $V$, which can be used to construct a ranking of vertices in $V$. The ordering is weak (instead of total) since $l$ might not be injective and therefore there might be ties, but let us not worry about this and allow ties in our vertex ranking.

I have read in a paper (see below) that the Weisfeiler-Lehman algorithm can be used to construct a labeling $l$ on a graph and therefore can be used to induce a weak ordering on the vertex set $V$.

My question is: how can the Weisfeiler-Lehman algorithm be used to construct a graph labeling $l$? I only see that the algorithm classifies vertices according to their color, but I cannot see any obvious/canonical/natural way to "order" the colors to create some kind of hierarchy between different classes of colors.

The paper I was referring to is:

Niepert, Mathias, Mohamed Ahmed, and Konstantin Kutzkov. "Learning convolutional neural networks for graphs." International conference on machine learning. 2016.

Any insights and hints are greatly appreciated!

$\endgroup$

1 Answer 1

1
$\begingroup$

The short answer is that the refinement process acts on the colours in a particular (arbitrary) order, and that determines the order of the labels.

To take a specific example, this small graph with degree sequence [3, 3, 2, 2, 1, 1] :

enter image description here

The initial degree partition is [[1, 3], [2, 4], [0, 5]] - as you can see, the cells of the partition are ordered by degree. As cells are 'split' into new cells, they are put back into the partition in order of the invariants used to split.

So depending on the choices made in how to order, you get a particular canonical labelling. For code that I have (based on 'Combinatorial Algorithms: Generation, Enumeration, and Search' by Kreher and Stinson, ISBN 9780367400156) the next finer partition is [1,3|2|4|0|5] and the labels are [3|1|2|4|0|5].

The papers describing nAUTy go into more detail, and there is a visual overview on http://pallini.di.uniroma1.it/Introduction.html for traces.

$\endgroup$

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.