Title: First-order Logic with Counting, the Weisfeiler-Lehman Algorithms, and Graph Neural Networks

Speaker: Yijia Chen (Shanghai Jiao Tong University)

Time: 2025/05/12 (Monday) 15:10-18:00

Location: Room B112, Lee Shau Kee Humanities Buildings No.2 (李兆基人文学苑2号楼), Peking University

Abstract: 

First-order logic (FO) with counting extends FO with the so-called counting quantifiers. Although it is no more expressive than FO as a whole, its fragment C^k consisting of the sentences with at most k variables turns outs to be more powerful than its FO counterpart FO^k. In this talk I will present some remarkable connections between C^k, a combinatorial algorithm known as (k-1)-dimensional Weisfeiler-Leman algorithm, and high-order Graph Neural Network (GNN).

It is worth noting that the high dimensional Weisfeiler-Leman algorithms are important heuristics for the graph isomorphism problem. So we will also briefly explain the ingenious graph-theoretic construction of Cai, Fuerer, and Immerman (CFI) that witnesses the failure of those algorithms and our recent efforts to lift the CFI-construction from colored graphs to uncolored graphs. Among others, this implies C^{k+1} is more expressive than C^k on uncolored graphs.