# How does naive vertex classification via color refinement induce a ranking on the vertices of a Graph $G$?

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!