Dimension Reduction via Colour Refinement
Dimension Reduction via Colour Refinement
复制标题
通过颜色细化减少维度
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Erkal Selman
中科院分区：
文献类型：
--
作者：
Martin Grohe;K. Kersting;Martin Mladenov;Erkal Selman
颜色细化是图同构检验的一个基本算法程序，几乎在所有实际的同构求解中都是作为子程序出现的。它将图形的顶点划分为“颜色类”，这样相同颜色类中的所有顶点在每个颜色类中都具有相同数量的邻居。Tinhofer(光盘。应用。数学。， 1991), Ramana, Scheinerman, and Ullman(光盘。数学。， 1994)和Godsil(林。Alg。及其应用程序，1997)建立了图的颜色细化和分数同构之间的紧密对应关系，这是图同构的自然ILP公式的LP松弛的解决方案。
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.