An assignment of colours to the vertices of a graph is stable if any two
vertices of the same colour have identically coloured neighbourhoods. The goal
of colour refinement is to find a stable colouring that uses a minimum number
of colours. This is a widely used subroutine for graph isomorphism testing
algorithms, since any automorphism needs to be colour preserving. We give an
$O((m+n)\log n)$ algorithm for finding a canonical version of such a stable
colouring, on graphs with $n$ vertices and $m$ edges. We show that no faster
algorithm is possible, under some modest assumptions about the type of
algorithm, which captures all known colour refinement algorithms.

给定一个具有 n 个顶点和 m 条边的图，我们给出了一个算法来找到稳定着色的规范版本，具有最少的颜色，并且该算法的时间复杂度为 O ((m+n) log n)。该算法被广泛用于图同构测试算法的子程序中。

规范颜色细化复杂度的紧密下界和上界

Tight Lower and Upper Bounds for the Complexity of Canonical Colour  Refinement

Colour refinement is a basic algorithmic routine for graph isomorphism
testing, appearing as a subroutine in almost all practical isomorphism solvers.
It partitions the vertices of a graph into "colour classes" in such a way that
all vertices in the same colour class have the same number of neighbours in
every colour class. Tinhofer (Disc. App. Math., 1991), Ramana, Scheinerman, and
Ullman (Disc. Math., 1994) and Godsil (Lin. Alg. and its App., 1997)
established a tight correspondence between colour refinement and fractional
isomorphisms of graphs, which are solutions to the LP relaxation of a natural
ILP formulation of graph isomorphism.
We introduce a version of colour refinement for matrices and extend existing
quasilinear algorithms for computing the colour classes. Then we generalise the
correspondence between colour refinement and fractional automorphisms and
develop a theory of fractional automorphisms and isomorphisms of matrices.
We apply our results to reduce the dimensions of systems of linear equations
and linear programs. Specifically, we show that any given LP L can efficiently
be transformed into a (potentially) smaller LP L' whose number of variables and
constraints is the number of colour classes of the colour refinement algorithm,
applied to a matrix associated with the LP. The transformation is such that we
can easily (by a linear mapping) map both feasible and optimal solutions back
and forth between the two LPs. We demonstrate empirically that colour
refinement can indeed greatly reduce the cost of solving linear programs.

该研究旨在介绍一种基于矩阵的着色技术，将其应用于线性方程组和线性规划问题，并展示该技术可以显着降低解决线性规划的成本。

基于颜色精炼的降维

Dimension Reduction via Colour Refinement

We give a new, simplified and detailed account of the correspondence between
levels of the Sherali-Adams relaxation of graph isomorphism and levels of
pebble-game equivalence with counting (higher-dimensional Weisfeiler-Lehman
colour refinement). The correspondence between basic colour refinement and
fractional isomorphism, due to Tinhofer (1986, 1991) and Ramana, Scheinerman
and Ullman (1994), is re-interpreted as the base level of Sherali-Adams and
generalised to higher levels in this sense by Atserias and Maneva (2012) and
Malkin (2014), who prove that the two resulting hierarchies interleave.
In carrying this analysis further, we here give
(a) a precise characterisation of the level-k Sherali-Adams relaxation in
terms of a modified counting pebble game;
(b) a variant of the Sherali-Adams levels that precisely match the k-pebble
counting game;
(c) a proof that the interleaving between these two hierarchies is strict.
We also investigate the variation based on boolean arithmetic instead of
real/rational arithmetic and obtain analogous correspondences and separations
for plain k-pebble equivalence (without counting). Our results are driven by
considerably simplified accounts of the underlying combinatorics and linear
algebra.

本研究简要地介绍了 Sherali-Adams 松弛的级别与计数（高维 Weisfeiler-Lehman 颜色细化）等级之间的对应关系，并对基本颜色细化和分数同构之间的对应关系进行了重新解释。同时本文还给出了一个修正的计数棋子游戏和 Sherali-Adams 松弛的级别 - k 的精确表述，并探讨了基于布尔算术而不是实数 / 有理算术的差异以及基于计数而不是简单的棋子等效性的变体。