Arrow Research search

Author name cluster

Pascal Schweitzer

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.

16 papers
2 author rows

Possible papers

16

CSL Conference 2025 Conference Paper

Computational Complexity of the Weisfeiler-Leman Dimension

  • Moritz Lichter
  • Simon Raßmann
  • Pascal Schweitzer

The Weisfeiler-Leman dimension of a graph G is the least number k such that the k-dimensional Weisfeiler-Leman algorithm distinguishes G from every other non-isomorphic graph, or equivalently, the least k such that G is definable in (k+1)-variable first-order logic with counting. The dimension is a standard measure of the descriptive or structural complexity of a graph and recently finds various applications in particular in the context of machine learning. This paper studies the complexity of computing the Weisfeiler-Leman dimension. We observe that deciding whether the Weisfeiler-Leman dimension of G is at most k is NP-hard, even if G is restricted to have 4-bounded color classes. For each fixed k ≥ 2, we give a polynomial-time algorithm that decides whether the Weisfeiler-Leman dimension of a given graph with 5-bounded color classes is at most k. Moreover, we show that for these bounds on the color classes, this is optimal because the problem is PTIME-hard under logspace-uniform AC_0-reductions. Furthermore, for each larger bound c on the color classes and each fixed k ≥ 2, we provide a polynomial-time decision algorithm for the abelian case, that is, for structures of which each color class has an abelian automorphism group. While the graph classes we consider may seem quite restrictive, graphs with 4-bounded abelian colors include CFI-graphs and multipedes, which form the basis of almost all known hard instances and lower bounds related to the Weisfeiler-Leman algorithm.

Details

CSL Conference 2025 Conference Paper

Finite Variable Counting Logics with Restricted Requantification

  • Simon Raßmann
  • Georg Schindling
  • Pascal Schweitzer

Counting logics with a bounded number of variables form one of the central concepts in descriptive complexity theory. Although they restrict the number of variables that a formula can contain, the variables can be nested within scopes of quantified occurrences of themselves. In other words, the variables can be requantified. We study the fragments obtained from counting logics by restricting requantification for some but not necessarily all the variables. Similar to the logics without limitation on requantification, we develop tools to investigate the restricted variants. Specifically, we introduce a bijective pebble game in which certain pebbles can only be placed once and for all, and a corresponding two-parametric family of Weisfeiler-Leman algorithms. We show close correspondences between the three concepts. By using a suitable cops-and-robber game and adaptations of the Cai-Fürer-Immerman construction, we completely clarify the relative expressive power of the new logics. We show that the restriction of requantification has beneficial algorithmic implications in terms of graph identification. Indeed, we argue that with regard to space complexity, non-requantifiable variables only incur an additive polynomial factor when testing for equivalence. In contrast, for all we know, requantifiable variables incur a multiplicative linear factor. Finally, we observe that graphs of bounded tree-depth and 3-connected planar graphs can be identified using no, respectively, only a very limited number of requantifiable variables.

Details

TMLR Journal 2023 Journal Article

A Systematic Approach to Universal Random Features in Graph Neural Networks

  • Billy Joe Franks
  • Markus Anders
  • Marius Kloft
  • Pascal Schweitzer

Universal random features (URF) are state of the art regarding practical graph neural networks that are provably universal. There is great diversity regarding terminology, methodology, benchmarks, and evaluation metrics used among existing URF. Not only does this make it increasingly difficult for practitioners to decide which technique to apply to a given problem, but it also stands in the way of systematic improvements. We propose a new comprehensive framework that captures all previous URF techniques. On the theoretical side, among other results, we formally prove that under natural conditions all instantiations of our framework are universal. The framework thus provides a new simple technique to prove universality results. On the practical side, we develop a method to systematically and automatically train URF. This in turn enables us to impartially and objectively compare all existing URF. New URF naturally emerge from our approach, and our experiments demonstrate that they improve the state of the art.

PDF Details

SAT Conference 2023 Conference Paper

Algorithms Transcending the SAT-Symmetry Interface

  • Markus Anders
  • Pascal Schweitzer
  • Mate Soos

Dedicated treatment of symmetries in satisfiability problems (SAT) is indispensable for solving various classes of instances arising in practice. However, the exploitation of symmetries usually takes a black box approach. Typically, off-the-shelf external, general-purpose symmetry detection tools are invoked to compute symmetry groups of a formula. The groups thus generated are a set of permutations passed to a separate tool to perform further analyzes to understand the structure of the groups. The result of this second computation is in turn used for tasks such as static symmetry breaking or dynamic pruning of the search space. Within this pipeline of tools, the detection and analysis of symmetries typically incurs the majority of the time overhead for symmetry exploitation. In this paper we advocate for a more holistic view of what we call the SAT-symmetry interface. We formulate a computational setting, centered around a new concept of joint graph/group pairs, to analyze and improve the detection and analysis of symmetries. Using our methods, no information is lost performing computational tasks lying on the SAT-symmetry interface. Having access to the entire input allows for simpler, yet efficient algorithms. Specifically, we devise algorithms and heuristics for computing finest direct disjoint decompositions, finding equivalent orbits, and finding natural symmetric group actions. Our algorithms run in what we call instance-quasi-linear time, i. e. , almost linear time in terms of the input size of the original formula and the description length of the symmetry group returned by symmetry detection tools. Our algorithms improve over both heuristics used in state-of-the-art symmetry exploitation tools, as well as theoretical general-purpose algorithms.

Details

FOCS Conference 2023 Conference Paper

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements

  • Martin Grohe
  • Moritz Lichter
  • Daniel Neuen
  • Pascal Schweitzer

The k-dimensional Weisfeiler-Leman (k-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applications in Babai’s quasipolynomial-time isomorphism algorithm, practical isomorphism solvers, and algebraic graph theory. However, it also has surprising connections to other areas such as logic, proof complexity, combinatorial optimization, and machine learning. The algorithm iteratively computes a coloring of the k-tuples of vertices of a graph. Since Fürer’s linear lower bound [ICALP 2001], it has been an open question whether there is a super-linear lower bound for the iteration number for k-WL on graphs. We answer this question affirmatively, establishing an $\Omega\left(n^{k / 2}\right)$-lower bound for all k.

Details

CSL Conference 2021 Conference Paper

Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time

  • Moritz Lichter
  • Pascal Schweitzer

In the quest for a logic capturing Ptime the next natural classes of structures to consider are those with bounded color class size. We present a canonization procedure for graphs with dihedral color classes of bounded size in the logic of Choiceless Polynomial Time (CPT), which then captures Ptime on this class of structures. This is the first result of this form for non-abelian color classes. The first step proposes a normal form which comprises a "rigid assemblage". This roughly means that the local automorphism groups form 2-injective 3-factor subdirect products. Structures with color classes of bounded size can be reduced canonization preservingly to normal form in CPT. In the second step, we show that for graphs in normal form with dihedral color classes of bounded size, the canonization problem can be solved in CPT. We also show the same statement for general ternary structures in normal form if the dihedral groups are defined over odd domains.

Details

SODA Conference 2021 Conference Paper

Deep Weisfeiler Leman

  • Martin Grohe
  • Pascal Schweitzer
  • Daniel Wiebking

We introduce the framework of Deep Weisfeiler Leman algorithms ( DeepWL ), which allows the design of purely combinatorial graph isomorphism tests that are more powerful than the well-known Weisfeiler-Leman algorithm. We prove that, as an abstract computational model, polynomial-time DeepWL -algorithms have exactly the same expressiveness as the logic Choiceless Polynomial Time (with counting) introduced by Blass, Gurevich, and Shelah (Ann. Pure Appl. Logic. , 1999). It is a well-known open question whether the existence of a polynomial-time graph isomorphism test implies the existence of a polynomial-time canonisation algorithm. Our main technical result states that for each class of graphs (satisfying some mild closure condition), if there is a polynomial-time DeepWL isomorphism test, then there is a polynomial-time canonisation algorithm for this class. This implies that there is also a logic capturing polynomial time on this class.

Details

FOCS Conference 2018 Conference Paper

A Faster Isomorphism Test for Graphs of Small Degree

  • Martin Grohe
  • Daniel Neuen
  • Pascal Schweitzer

In a recent breakthrough, Babai (STOC 2016) gave quasipolynomial graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithms runs in time n^O((log d)^c), where n is the number of vertices of the input graphs, d is the maximum degree of the input graphs, and c is an absolute constant. The best previous isomorphism test for graphs of maximum degree d due to Babai, Kantor and Luks (FOCS 1983) runs in time n^O(d log d).

Details

FOCS Conference 2015 Conference Paper

Isomorphism Testing for Graphs of Bounded Rank Width

  • Martin Grohe
  • Pascal Schweitzer

We give an algorithm that, for every fixed k, decides isomorphism of graphs of rank width at most k in polynomial time. As the rank width of a graph is bounded in terms of its clique width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.

Details

JMLR Journal 2011 Journal Article

Weisfeiler-Lehman Graph Kernels

  • Nino Shervashidze
  • Pascal Schweitzer
  • Erik Jan van Leeuwen
  • Kurt Mehlhorn
  • Karsten M. Borgwardt

In this article, we propose a family of efficient kernels for large graphs with discrete node labels. Key to our method is a rapid feature extraction scheme based on the Weisfeiler-Lehman test of isomorphism on graphs. It maps the original graph to a sequence of graphs, whose node attributes capture topological and label information. A family of kernels can be defined based on this Weisfeiler-Lehman sequence of graphs, including a highly efficient kernel comparing subtree-like patterns. Its runtime scales only linearly in the number of edges of the graphs and the length of the Weisfeiler-Lehman graph sequence. In our experimental evaluation, our kernels outperform state-of-the-art graph kernels on several graph classification benchmark data sets in terms of accuracy and runtime. Our kernels open the door to large-scale applications of graph kernels in various disciplines such as computational biology and social network analysis. [abs] [ pdf ][ bib ] &copy JMLR 2011. ( edit, beta )

PDF Details