Weisfeiler-lehman refinement requires at least a linear number of iterations

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

Abstract

Let Lk,m be the set of formulas of first order logic containing only variables from x1, x2, ... xk and having quantifier depth at most m. Let Ck,m be the extension of L k,m obtained by allowing counting quantifiers meaning that there are at least i distinct xj 's. It is shown that for constants h ≥ 1, there are pairs of graphs such that h-dimensional Weisfeiler-Lehman refinement (h-dim W-L) can distinguish the two graphs, but requires at least a linear number of iterations. Despite of this slow progress, 2h-dim W-L only requires O(n) iterations, and 3h-1-dim W-L only requires O(log n) iterations. In terms of logic, this means that there is a c > 0 and a class of non-isomorphic pairs (GhnHhn) of graphs with G hn and Hhn having O(n) vertices such that the same sentences of Lh+1cn and Ch+1cn hold (h + 1 variables, depth cn), even though Ghn and H hn can already be distinguished by a sentence of L k,m and thus Ckm for some k > h and m = O(log n).

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings
EditorsFernando Orejas, Paul G. Spirakis, Jan van Leeuwen
PublisherSpringer Verlag
Pages322-333
Number of pages12
ISBN (Print)3540422870, 9783540422877
DOIs
StatePublished - 2001
Event28th International Colloquium on Automata, Languages and Programming, ICALP 2001 - Crete, Greece
Duration: Jul 8 2001Jul 12 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2076 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other28th International Colloquium on Automata, Languages and Programming, ICALP 2001
Country/TerritoryGreece
CityCrete
Period7/8/017/12/01

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Weisfeiler-lehman refinement requires at least a linear number of iterations'. Together they form a unique fingerprint.

Cite this