Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties
76
0
0.0
(
0
)
Added by
Oleg Verbitsky
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a fruitful approach to the Graph Isomorphism problem. 2-WL corresponds to the original algorithm suggested by Weisfeiler and Leman over 50 years ago. 1-WL is the classical color refinement routine. Indistinguishability by $k$-WL is an equivalence relation on graphs that is of fundamental importance for isomorphism testing, descriptive complexity theory, and graph similarity testing which is also of some relevance in artificial intelligence. Focusing on dimensions $k=1,2$, we investigate subgraph patterns whose counts are $k$-WL invariant, and whose occurrence is $k$-WL invariant. We achieve a complete description of all such patterns for dimension $k=1$ and considerably extend the previous results known for $k=2$.
rate research
Read More
The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of $k$-WL to recognition of graph properties. Let $G$ be an input graph with $n$ vertices. We show that, if $n$ is prime, then vertex-transitivity of $G$ can be seen in a straightforward way from the output of 2-WL on $G$ and on the vertex-individualized copies of $G$. However, if $n$ is divisible by 16, then $k$-WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with $n$ vertices as long as $k=o(sqrt n)$. Similar results are obtained for recognition of arc-transitivity.
We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of $n$-element structures that can be distinguished by a $k$-variable first-order sentence but where every such sentence requires quantifier depth at least $n^{Omega(k/log k)}$. Our trade-offs also apply to first-order counting logic, and by the known connection to the $k$-dimensional Weisfeiler--Leman algorithm imply near-optimal lower bounds on the number of refinement iterations. A key component in our proof is the hardness condensation technique recently introduced by [Razborov 16] in the context of proof complexity. We apply this method to reduce the domain size of relational structures while maintaining the minimal quantifier depth to distinguish them in finite variable logics.
The $k$-dimensional Weisfeiler-Leman procedure ($k$-WL), which colors $k$-tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are $k$-WL-equivalent if the $k$-dimensional Weisfeiler-Leman procedure produces the same final coloring on both graphs. 1-WL-equivalence is known as fractional isomorphism of graphs, and the $k$-WL-equivalence relation becomes finer as $k$ increases. We investigate to what extent standard graph parameters are preserved by $k$-WL-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of $k$-WL-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.
Given a pair of graphs $textbf{A}$ and $textbf{B}$, the problems of deciding whether there exists either a homomorphism or an isomorphism from $textbf{A}$ to $textbf{B}$ have received a lot of attention. While graph homomorphism is known to be NP-complete, the complexity of the graph isomorphism problem is not fully understood. A well-known combinatorial heuristic for graph isomorphism is the Weisfeiler-Leman test together with its higher order variants. On the other hand, both problems can be reformulated as integer programs and various LP methods can be applied to obtain high-quality relaxations that can still be solved efficiently. We study so-called fractional relaxations of these programs in the more general context where $textbf{A}$ and $textbf{B}$ are not graphs but arbitrary relational structures. We give a combinatorial characterization of the Sherali-Adams hierarchy applied to the homomorphism problem in terms of fractional isomorphism. Collaterally, we also extend a number of known results from graph theory to give a characterization of the notion of fractional isomorphism for relational structures in terms of the Weisfeiler-Leman test, equitable partitions, and counting homomorphisms from trees. As a result, we obtain a description of the families of CSPs that are closed under Weisfeiler-Leman invariance in terms of their polymorphisms as well as decidability by the first level of the Sherali-Adams hierarchy.
In this paper we combine many of the standard and more recent algebraic techniques for testing isomorphism of finite groups (GpI) with combinatorial techniques that have typically been applied to Graph Isomorphism. In particular, we show how to combine several state-of-the-art GpI algorithms for specific group classes into an algorithm for general GpI, namely: composition series isomorphism (Rosenbaum-Wagner, Theoret. Comp. Sci., 2015; Luks, 2015), recursively-refineable filters (Wilson, J. Group Theory, 2013), and low-genus GpI (Brooksbank-Maglione-Wilson, J. Algebra, 2017). Recursively-refineable filters -- a generalization of subgroup series -- form the skeleton of this framework, and we refine our filter by building a hypergraph encoding low-genus quotients, to which we then apply a hypergraph variant of the k-dimensional Weisfeiler-Leman technique. Our technique is flexible enough to readily incorporate additional hypergraph invariants or additional characteristic subgroups.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
