Author name cluster

Sandra Kiefer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

CSL Conference 2026 Conference Paper

The Logic Behind Colour Refinement (Invited Talk)

Sandra Kiefer

Colour Refinement is a combinatorial algorithm that computes a vertex colouring for an input graph to reveal its structural properties. Each iteration of the algorithm refines the current colouring by assessing local information. More precisely, the new colour of a vertex is determined by its current colour and the multiset of colours in its neighbourhood. This refinement procedure continues until it reaches a stable partition of the vertex set into colour classes. On the practical side, the algorithm admits fast implementations. Because the final colouring is isomorphism-invariant, executing the algorithm on two graphs in parallel can be used to demonstrate that they are not isomorphic. From a theoretical perspective, the algorithm is arguably the most straightforward combinatorial approach to detecting asymmetries - specifically for distinguishing vertices that do not belong to the same orbit of the automorphism group of the graph. Its numerous connections to other areas in computer science stand as evidence of its robustness and naturalness and make it a fascinating object of research. Among the most elegant connections is the link to counting logic. Colour Refinement assigns distinct final colours to two vertices in a graph if and only if there is a formula in the two-variable fragment C² of the logic C that distinguishes them, meaning that the formula holds for precisely one of the two vertices. In fact, the vertex colours translate directly into logical formulas with one free variable. As a consequence, Colour Refinement distinguishes two graphs if and only if there is a C²-sentence that distinguishes them. This correspondence extends to higher dimensions: the k-variable fragment C^k of C corresponds to the (k-1)-dimensional extension of Colour Refinement, the (k-1)-dimensional Weisfeiler-Leman algorithm. This algorithm computes a unique colouring for a graph G if and only if G is definable in C^k, i. e. there is a sentence in C^k whose only models are G and its isomorphic copies. As a matter of fact, the link to the logic C goes even deeper: the number of Colour Refinement iterations required to compute distinct colours corresponds exactly to the quantifier depth of a distinguishing formula. Since the iterations induce a sequence of strictly nested vertex partitions, the process must terminate after at most n-1 rounds, where n is the number of vertices. Consequently, the value n-1 serves as a trivial upper bound on both the number of iterations and the quantifier depth required to distinguish any two (distinguishable) vertices in C². My talk provides an introduction to the link between the Colour Refinement procedure and the logic C². We revisit a simple characterisation of their expressivity on graphs and on general relational structures. The characterisation implies that the definability of a graph in C² can be checked very efficiently. We then discuss tight lower bounds on the quantifier depth of C²-formulas required to distinguish vertices. Through a thorough analysis of computational data from Colour Refinement executions, we constructed infinite families of graphs that witness those bounds. We finish with a presentation of a recent purely theoretical reverse-engineering approach to finding long-refinement graphs and a classification of all such graphs with small (or, equivalently, large) degrees. The talk is based on the collaborations[Sandra Kiefer and T. Devini de Mel, 2026; Kiefer and McKay, 2020; Sandra Kiefer et al. , 2022] and unpublished work.

Details

Highlights Conference 2023 Conference Abstract

Revisiting the growth of polyregular functions

Sandra Kiefer

Polyregular functions are the class of string-to-string functions definable by pebble transducers, an extension of finite-state automata with outputs and multiple two-way reading heads (pebbles) with a stack discipline. If a polyregular function can be computed with k pebbles, then its output length is bounded by a polynomial of degree k in the input length. But Bojańczyk has shown that the converse fails. We provide two alternative easier proofs. The first establishes by elementary means that some quadratic polyregular function requires 3 pebbles. The second proof - just as short, albeit less elementary - shows a stronger statement: for every k, there exists some polyregular function with quadratic growth whose output language differs from that of any k-fold composition of macro tree transducers (and which therefore cannot be computed by a k-pebble transducer). Along the way, we also refute a conjectured logical characterization of polyblind functions. Contributed talk given by Sandra Kiefer

Details

ICML Conference 2022 Conference Paper

SpeqNets: Sparsity-aware permutation-equivariant graph networks

Christopher Morris 0001
Gaurav Rattan
Sandra Kiefer
Siamak Ravanbakhsh

While message-passing graph neural networks have clear limitations in approximating permutation-equivariant functions over graphs or general relational data, more expressive, higher-order graph neural networks do not scale to large graphs. They either operate on $k$-order tensors or consider all $k$-node subgraphs, implying an exponential dependence on $k$ in memory requirements, and do not adapt to the sparsity of the graph. By introducing new heuristics for the graph isomorphism problem, we devise a class of universal, permutation-equivariant graph networks, which, unlike previous architectures, offer a fine-grained control between expressivity and scalability and adapt to the sparsity of the graph. These architectures lead to vastly reduced computation times compared to standard higher-order graph networks in the supervised node- and graph-level classification and regression regime while significantly improving standard graph neural network and graph kernel architectures in terms of predictive performance.

Details

Highlights Conference 2022 Conference Abstract

Treelike Decompositions for Transductions of Sparse Graphs

Sandra Kiefer

We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs - more precisely, from classes of bounded expansion and from nowhere dense classes. In both cases, the decomposition takes the form of a single coloured rooted tree of bounded depth where, in addition, there can be links between nodes that are not related in the tree. The constraint is that the structure formed by the tree and the links has to be sparse. Using the decomposition theorem for transductions of nowhere dense classes, we show that they admit low-shrubdepth covers of size O(n^ε), where n is the vertex count and ε>0 is any fixed real. This solves an open problem posed by Gajarský et al. (ACM TOCL '20) and also by Briański et al. (SIDMA '21). The talk is based on work conducted with Jan Dreier, Jakub Gajarský, Michał Pilipczuk, and Szymon Toruńczyk.

Details

Highlights Conference 2021 Conference Abstract

Logarithmic Weisfeiler-Leman Identifies All Planar Graphs

Sandra Kiefer

The Weisfeiler-Leman (WL) algorithm is a well-known combinatorial procedure for detecting symmetries in graphs that is widely used in graph-isomorphism tests. It proceeds by iteratively computing vertex colours. The number of iterations needed to obtain the final output is crucial for the parallelisability of the algorithm. In my presentation, I would like to present an overview of our recent proof that there is a constant k such that every planar graph can be identified (that is, distinguished from every non-isomorphic graph) by the k-dimensional WL algorithm within a logarithmic number of iterations. This generalises a result due to Verbitsky, who proved the same for 3-connected planar graphs. The number of iterations needed by the k-dimensional WL algorithm to identify a graph corresponds to the quantifier depth of a sentence that defines the graph in the (k+1)-variable fragment C^(k+1) of first-order logic with counting quantifiers. Thus, our result implies that every planar graph is definable by a C^(k+1)-sentence of logarithmic quantifier depth. The discussed result was obtained in collaboration with Martin Grohe. The corresponding paper has been accepted for publication at ICALP 2021 and the full version will appear on arXiv in the next days.

Details

Highlights Conference 2020 Conference Abstract

String-to-String Interpretations with Polynomial-Size Output

Sandra Kiefer

String-to-string MSO interpretations are like Courcelle’s MSO transductions, except that a single output position can be represented using a tuple of input positions instead of just a single input position. In particular, the output length is polynomial in the input length, as opposed to MSO transductions, which have output of linear length. We show that string-to-string MSO interpretations are exactly the polyregular functions. The latter class has various characterizations, one of which is that it consists of the string-to-string functions recognized by pebble transducers. Our main result implies the surprising fact that string-to-string MSO interpretations are closed under composition. This is joint work with Mikołaj Bojańczyk and Nathan Lhote and the corresponding paper was published at ICALP 2019. (It has not yet been presented at Highlights.)

Details

MFCS Conference 2019 Conference Paper

The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs

Sandra Kiefer
Daniel Neuen

The Weisfeiler-Leman procedure is a widely-used approach for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into bi- and triconnected components. We prove that the 2-dimensional Weisfeiler-Leman algorithm implicitly computes the decomposition of a graph into its triconnected components. Thus, the dimension of the algorithm needed to distinguish two given graphs is at most the dimension required to distinguish the corresponding decompositions into 3-connected components (assuming dimension at least 2). This result implies that for k >= 2, the k-dimensional algorithm distinguishes k-separators, i. e. , k-tuples of vertices that separate the graph, from other vertex k-tuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes. In an application of the results, we show the new upper bound of k on the Weisfeiler-Leman dimension of graphs of treewidth at most k. Using a construction by Cai, Fürer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2.

Details

Highlights Conference 2018 Conference Abstract

Distinguishing Graphs via Logics with Counting

Sandra Kiefer

ABSTRACT. The Weisfeiler-Leman algorithm is a combinatorial procedure that plays a crucial role both in theoretical and practical research on the graph isomorphism problem. For every k there is a k-dimensional version of the algorithm, which iteratively refines a partition of the set of k-tuples of vertices of the input graph. Two graphs are non-isomorphic if (but not only if) their final partitions computed by the algorithm differ. In this talk, I will give a very brief introduction to the mechanisms of the Weisfeiler-Leman algorithm and present some of our results: We have studied the number of iterations which the algorithm takes to stabilize. We have found new upper bounds for the iteration number of the 2-dimensional algorithm as well as recently a tight new lower bound for the 1-dimensional algorithm, which I will discuss in the talk. By a famous result established by Cai, Fürer and Immerman, a graph is identified by the k-dimensional Weisfeiler-Leman algorithm if and only if it is definable in C^(k+1), first order logic with counting and restricted to k + 1 variables. Via this correspondence, the number of iterations the algorithm needs to distinguish two graphs corresponds to the quantifier depth of the corresponding counting logic.

Details