Novel Graph Machine Learning Algorithms on Planar Coloured Graphs

Colour Refinement, Four-Colour Structure, and Chromatic Kernels for Learning

Abstract

A coloured graph carries a discrete attribute on each vertex, and when the underlying graph is planar the interaction between that attribute and the topology of the plane embedding becomes especially rich. This paper, a companion to the author’s study of learning on planar graphs, proposes four novel algorithms that make colour a first class citizen of graph machine learning on planar structures. We begin from two classical facts, that colour refinement in the sense of Weisfeiler and Leman produces the coarsest equitable partition of a graph, and that every planar graph is four colourable, and we show that each of these facts yields a concrete learning primitive on planar inputs. The first algorithm turns colour refinement into a permutation invariant feature map whose stable colouring is computed in near linear time on planar graphs. The second, chromatic block propagation, uses a proper four colouring to schedule harmonic label propagation as at most four fully parallel sub sweeps, because each colour class is an independent set with no internal coupling. The third builds a chromatic diffusion kernel that fuses colour refinement histograms with heat flow on the graph. The fourth uses colour classes as an independent set backbone for multilevel coarsening of the Laplacian. Each algorithm is analysed for correctness and cost, the intuition connecting equitable partitions to the Laplacian spectrum is made explicit, and behaviour is illustrated on coloured plane graphs and grids. The unifying message is that on planar coloured graphs the chromatic structure is not a nuisance to be hashed away but a schedule, a feature, and a coarsening all at once.