Graph Machine Learning on Planar Graphs

Spectral Intuition, Separator Structure, and Algorithms for Learning on Plane-Embedded Data

Abstract

Planar graphs form a structurally rich yet computationally tractable class of graphs that arise naturally in image analysis, geographic information systems, circuit layout, and molecular chemistry. This paper develops graph machine learning tailored to planar graphs, with an emphasis on the mathematical intuition that connects the topology of a plane embedding to the spectral and combinatorial structure exploited by learning algorithms. We first recall that planarity forces sparsity through Euler’s formula and small vertex separators through the Lipton and Tarjan theorem, and we explain why these two facts to gether make planar learning problems well conditioned. We then treat three learning primitives in a unified way: spectral partitioning through the Fiedler vector of the graph Laplacian, semi-supervised classification through harmonic extension of labels, and similarity through diffusion kernels. Throughout we develop the electrical network interpretation, in which the harmonic solution is a potential and effective resistance is a learned distance, because this picture is especially transparent on planar graphs. Four algorithms are presented with complexity analysis, and their behaviour is illustrated on plane-embedded meshes and grids. The paper is intended as a mathematically motivated entry point for researchers who wish to learn on data whose relational structure can be drawn in the plane without crossings.