CS Paper Radar

On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman

Fan Yang

cs.SI cs.AIcs.LG ·submitted 2026-09-14 22:34 UTC · v1
theory

Abstract

Whitney's theorem allows isomorphism testing for connected simple graphs, apart from $K_3$ and $K_{1,3}$, to be formulated as distinguishing their line graphs. However, the relation between fixed-dimensional Weisfeiler--Leman (WL) expressivity on line graphs and on their roots remains unresolved. We study this relation through Implicit Line-Graph WL (ILG-$k$-WL), which is exactly $k$-WL on $L(G)$, executed over the edges of $G$ with line-graph relations derived from endpoint incidence and without explicitly constructing $L(G)$. On the Whitney-general class, the relation between root-domain and line-graph WL depends on $k$. For $k=1,2$, ILG-$k$-WL adds no distinguishing power beyond root-domain $1$-WL and misses some pairs that $1$-WL separates. For $k=3$, we prove the backward containment $L(G)\equiv_{3\text{-WL}}L(H)\Rightarrow G\equiv_{3\text{-WL}}H$. Strongly regular witness pairs, including the Shrikhande/rook pair, show that ILG-$3$-WL is strictly more expressive than $3$-WL. The backward containment also extends to disconnected graphs with no isolated vertices when every connected component is Whitney-general. Deterministic ILG-$3$-WL separates all three substructure-counting witness pairs, all $105$ pairs in SR25, and $359$ of $400$ BREC pairs. An untrained dense ILG-$3$-GNN gives the same pairwise verdicts on these evaluations.

Comment
9 pages of main text. 40 pages in total

Closest papers

Nearest neighbours by meaning across the whole index.

Transfer of Weisfeiler-Leman equivalence under graph operations

cs.DM math.CO ·2026-11-03 ·Dmitriy Kunisky, Hamilton Sawczuk
theory similarity 0.72
Abstract

The Weisfeiler-Leman algorithms WL(k) for $k\ge1$ form a hierarchy of increasingly powerful tests for graph isomorphism. We study how the equivalence relations they induce on graphs transfer through a graph operation $Φ$: for a given $k$, what level of WL-equivalence between graphs $H_1$ and $H_2$ guarantees WL(k)-equivalence of graphs $Φ(H_1)$ and $Φ(H_2)$? We call the least such level the transfer parameter $τ_Φ(k)$ and determine it exactly for the line graph operation $Φ= L$: $τ_L(k)=2k+1$ for $k\ge2$, while $τ_L(1)=1$. We also extend these results to the $(r,S)$-line graphs, which generalize the line graph from edges to $r$-cliques by connecting two cliques when their intersection size lies in a prescribed set $S$. For these operations we prove that $τ_{r,S}(1)=r-1$ for every $S$ and, for certain choices of $S$, that $τ_{r,S}(k)=rk+r-1$ for $k\ge r$, and we bound the transfer parameter in the remaining range. Our upper bounds on transfer parameters follow from a treewidth analysis of diagrammatic expansions of homomorphism counts into $Φ(H)$ as linear combinations of homomorphism counts into $H$. The matching lower bounds combine explicit constructions of witness graphs with the homomorphism-distinguishing closedness of graphs of bounded treewidth.

0.16

Reversing the Mostar line-graph inequality with long pendant paths

cs.DM math.CO ·2026-09-30 ·Kerem Kat
theory similarity 0.64
Abstract · 19 pages, 4 figures. Ancillary code for exact finite checks

Let $K_t$ be obtained by attaching a pendant path of length $t$ to a fixed rooted graph $K$. We prove that $\mathrm{Mo}(L(K_t))-\mathrm{Mo}(K_t)$, the difference between its line-graph and original Mostar indices, is exactly affine on each parity class beyond a sharp uniform cutoff. The slope depends on distance-level neighbor counts and is positive for every non-bipartite core. Triangle chains give infinitely many graphs with $\mathrm{Mo}(L(G))>\mathrm{Mo}(G)$ at every positive cyclomatic number $c$, with maximum degree three, resolving Alex-Indulal Problem 3.3. At zero slope, a cactus branch-mass formula decides equality; identical vertex profiles need not give identical intercepts. Fixed cores giving equality for all sufficiently long attachments exist exactly when $c$ is odd. Maximum degree three suffices, and at every even $c$ a binary-tree construction gives equality on one eventual parity class.

0.20

Color Refinement Distinguishes Connected Rooted Outerplanar Graphs

cs.DM cs.DSmath.CO ·2026-11-13 ·Louann Coste, M{ó}nika Csik{ó}s, Laurent Viennot
similarity 0.61
Abstract

Color refinement, also known as the $1$-dimensional Weisfeiler-Leman algorithm ($1$-WL), is a classical near-linear-time heuristic for graph isomorphism, which also captures the expressive power of message-passing graph neural networks. A long line of work asks on which graph classes $1$-WL, or its higher-dimensional variant $k$-WL, identifies every graph; the least such $k$ is the WL-dimension of the class. Planar graphs have WL-dimension at most $3$ (Kiefer, Ponomarenko and Schweitzer, 2019), and whether $2$-WL already distinguishes all planar graphs is a central open problem. We bring new insight on this question for outerplanar graphs, whose WL-dimension is $2$. We show that color refinement, i.e. 1-WL, distinguishes connected rooted outerplanar graphs: two non-isomorphic such graphs receive different stable colorings once a single vertex, the root, is individualized. The root is necessary, as there are non-isomorphic $2$-connected outerplanar graphs that color refinement does not distinguish. Our result extends to pseudo-rooted graphs, in which the stable coloring merely contains a singleton color class, and to non-connected graphs whose components all contain such a class. Consequently, the $(1,1)$-WL test of Rattan and Seppelt (2023) distinguishes all outerplanar graphs. We proceed by inversion: we reconstruct a connected rooted outerplanar graph, up to isomorphism, from its color graph, the weighted quotient of the graph by its stable color classes, together with its root color. The reconstruction runs in time linear in the output size and is canonical, which yields a near-linear-time canonization algorithm for these graphs. Our main tool is a dichotomy lemma, formalized in Rocq: in a rooted outerplanar graph with an equitable coloring, every block either receives pairwise distinct colors or admits a color-preserving mirror symmetry fixing its vertex closest to the root.

0.14

A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability

cs.LO cs.CCmath.CO ·2026-08-13 ·Radu Curticapean, Daniel Neuen, Amir Nikabadi, Tim Seppelt, Ben Young
theory similarity 0.61
Abstract

Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if they admit the same number of homomorphisms from every graph in $\mathcal{F}$. A wide range of relaxations of graph isomorphism arise this way: isomorphism itself over the class of all graphs [Lovász, Acta Math. Hung. 1967], equivalence under the $k$-dimensional Weisfeiler-Leman algorithm over the graphs of treewidth $\leq k$ [Dvořák, J. Graph Theory 2010], and quantum isomorphism over planar graphs [Mančinska-Roberson, FOCS 2020]. Since the class $\mathcal{F}$ is typically infinite, it is not clear a priori whether homomorphism indistinguishability over $\mathcal{F}$ is decidable; for planar graphs it is undecidable. Every class for which decidability was previously known is sparse. We give the first decidability results for dense graph classes: We introduce the dense Weisfeiler-Leman algorithm that decides homomorphism indistinguishability over the class of graphs of cliquewidth $\leq k$, the dense counterpart of treewidth. This relation was not previously known to be decidable. The algorithm colors $k$-tuples of vertex subsets rather than $k$-tuples of vertices. Beyond the class of all graphs of cliquewidth $\leq k$, we prove a general meta-theorem: homomorphism indistinguishability over every $\mathsf{CMSO}_1$-definable graph class of bounded cliquewidth is decidable, in randomized exponential time. For classes of bounded linear cliquewidth the bound improves to $\mathsf{PSPACE}$, and we show this is tight by exhibiting such a class for which the problem is $\mathsf{PSPACE}$-complete. These are the first general algorithms for homomorphism indistinguishability over dense graph classes.

0.33

Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width

cs.DM math.COcs.LO ·2026-10-07 ·Antonios Kalampakas
theory similarity 0.60
Abstract · 44 pages. Includes ancillary verification code

The Weisfeiler-Leman (WL) algorithm tests graph isomorphism by assigning colours to $d$-tuples of vertices and iteratively refining the colouring according to neighbourhood configurations until it stabilizes. Increasing $d$ allows the test to detect finer structural differences between graphs, but the computational cost grows exponentially with $d$. The central question is which dimension allows us to distinguish nonisomorphic graphs. We relate a sufficient such dimension to the structure of a graph $G$ through a rank decomposition over $\mathbb F_2$. The two parameters governing the bound are the maximum cut rank $w$ and the fork load $\ell$, which is the largest sum of the parent and two child cut ranks at a fork in the decomposition tree. We prove that WL in dimension $\max\{\ell+1,2w+2\}$ distinguishes every finite nonempty vertex-coloured graph $G$ with such a decomposition from every graph not isomorphic to $G$. Consequently, for $k\geq1$, graphs of rank width at most $k$ can be distinguished from every nonisomorphic graph in dimension $3k+1$, graphs of linear rank width at most $k$ in dimension $2k+2$, and edgeless graphs in dimension one. Uncoloured Cai-Fürer-Immerman (CFI) constructions give linear lower bounds for both width parameters, so the upper bounds are tight up to constant factors.

0.29

Countable Graphs with Finite Path-width: Characterisation and Universality

cs.DM math.CO ·2026-08-27 ·Tony Huynh, Freddie Illingworth, Nikolai Karol, Florian Lehner, Chun-Hung Liu +2 more
theory similarity 0.57
Abstract

We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs that do not have infinitely many vertices of infinite degree, do not have infinitely many pairwise disjoint infinite paths, and contain no subdivision of some finite tree of maximum degree 3. We then investigate universality under the subgraph relation for graphs of bounded path-width or line-width. In particular, we prove that there exists a universal graph with line-width $\mathcal{O}(k^2)$ for the class of graphs with line-width at most $k$. In contrast, we show that no graph of finite path-width is universal for the class of locally finite graphs with path-width $1$. Finally, we show that for each $k\geq 2$, every universal graph for the class of graphs with path-width at most $k$ has line-width at least $k + 1$.

0.14

An Almost-tight Size Lower Bound for Bounded Treewidth Homomorphism-Distinguishability

cs.DM ·2026-11-02 ·Moritz Lichter, Harry Vinall-Smeeth
theory similarity 0.57
Abstract · 66 pages

One way to compare two graphs $G_1, G_2$ is to check whether there is some graph $H$ in a graph class $\mathcal{H}$, such that the number of homomorphisms from $H$ to $G_1$ is not equal to that from $H$ to $G_2$. This is the field of homomorphism distinguishability which has gained a lot of traction in recent years. In this paper, we study the case where $\mathcal{H}$ is the class of graphs of treewidth $k$. This has connections to important concepts in logic, machine learning, combinatorial optimization and proof complexity. In particular, Dvořák showed that $G_1$ and $G_2$ can be distinguished by a homomorphism count from a graph of treewidth $k$ iff $G_1$ and $G_2$ are distinguishable by the $k$-dimensional Weisfeiler-Leman algorithm. While the relation between the iteration number of this algorithm and the depth of the tree-decomposition of a distinguishing graph is understood, our understanding of the \emph{size} of $H$ is limited. We show a $2^{Ω(n^{k/2})}$ lower bound on the size of a graph of treewidth $k$ required to distinguish two graphs of order $n$. This bound is proved via a new combinatorial game along with a construction which uses a recent compression technique for CFI graphs. It is almost tight to the known $2^{O(n^{k+1})}$ upper bound and is an exponential improvement on the previous best known lower bound.

0.25

Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number

cs.DS math.CO ·2026-09-21 ·Andrea Munaro
theory similarity 0.57
Abstract · 29 pages

We establish a strongly sublinear counterpart of a recent result of Chudnovsky, E S, and Lokshtanov (arXiv 2025) on treewidth and tree-independence number. Namely, we prove that a hereditary graph class has strongly sublinear tree-independence number if and only if, for every fixed clique bound, its graphs of bounded clique number have strongly sublinear treewidth. In fact, this is part of a broader equivalence theorem. For hereditary classes, these conditions are also equivalent to having clique-dependent polynomial expansion, to admitting balanced separators whose size is bounded by $Kω(G)^s |V(G)|^{1-β}$ for fixed $K,s,β>0$, and to admitting balanced clique-based separators of strongly sublinear size (equivalently, weight). Thus, we show that all these properties, which arose independently in the study of subexponential-time exact algorithms and polynomial-time approximation schemes, in fact describe the same hereditary graph classes. As a consequence of our equivalence theorem, we also show that every hereditary class $\mathcal C$ with strongly sublinear tree-independence number admits a subexponential-time algorithm that, given $G\in\mathcal C$, computes a tree decomposition of $G$ with strongly sublinear independence number.

0.24