检索结果-内蒙古大学图书馆

The Iteration Number of the Weisfeiler-Leman Algorithm

ACM Transactions on Computational logic 2025年第1期26卷 1-31页

作者： Grohe, Martin Lichter, Moritz Neuen, Daniel RWTH Aachen University Aachen Germany Max Planck Institute for Informatics Saarbrücken Germany

We prove new upper and lower bounds on the number of iterations the -dimensional Weisfeiler-Leman algorithm (-WL) requires until stabilization. For , we show that -WL stabilizes after at most iterations (where denotes the number of vertices of the input structures), obtaining the first improvement over the trivial upper bound of and extending a previous upper bound of for .We complement our upper bounds by constructing -ary relational structures on which -WL requires at least iterations to stabilize. This improves over a previous lower bound of .We also investigate tradeoffs between the dimension and the iteration number of WL, and show that -WL, where , can simulate the -WL algorithm using only many iterations, but still requires at least iterations for any (that is sufficiently smaller than ).The number of iterations required by -WL to distinguish two structures corresponds to the quantifier rank of a sentence distinguishing them in the -variable fragment of first-order logic with counting quantifiers. Hence, our results also imply new upper and lower bounds on the quantifier rank required in the logic , as well as tradeoffs between variable number and quantifier rank. © 2025 Copyright held by the owner/author(s).

关键词： Weisfeiler-Leman algorithm iteration number first-order logic with counting quantifiers

来源：评论

学校读者我要写书评

暂无评论

The Iteration Number of the Weisfeiler-Leman Algorithm 38

The Iteration Number of the Weisfeiler-Leman Algorithm

引用

38th Annual ACM/IEEE Symposium on logic in Computer Science (LICS)

作者： Grohe, Martin Lichter, Moritz Neuen, Daniel Rhein Westfal TH Aachen Aachen Germany Tech Univ Darmstadt Darmstadt Germany Univ Bremen Bremen Germany

ISBN: (纸本)9798350335873

We prove new upper and lower bounds on the number of iterations the k-dimensional Weisfeiler-Leman algorithm (k-WL) requires until stabilization. For k >= 3, we show that k-WL stabilizes after at most O(kn(k-1) log n) iterations (where n denotes the number of vertices of the input structures), obtaining the first improvement over the trivial upper bound of n(k) - 1 and extending a previous upper bound of O(n log n) for k = 2 [Lichter et al., LICS 2019]. We complement our upper bounds by constructing k-ary relational structures on which k-WL requires at least n(Omega(k)) iterations to stabilize. This improves over a previous lower bound of n(Omega(k/ log k)) [Berkholz, Nordstr om, LICS 2016]. We also investigate tradeoffs between the dimension and the iteration number of WL, and show that d-WL, where d = inverted right perpendicular 3(k+1)/2 inverted left perpendicular, can simulate the k-WL algorithm using only O(k2 center dot n(left perpendiculark/2right perpendicular+1) log n) many iterations, but still requires at least n(Omega(k)) iterations for any d (that is sufficiently smaller than n). The number of iterations required by k-WL to distinguish two structures corresponds to the quantifier rank of a sentence distinguishing them in the (k + 1)-variable fragment Ck+ 1 of first-order logic with counting quantifiers. Hence, our results also imply new upper and lower bounds on the quantifier rank required in the logic Ck+1, as well as tradeoffs between variable number and quantifier rank.

关键词： Weisfeiler-Leman algorithm iteration number first-order logic with counting quantifiers quantifier rank

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：