May, 2023

利用本地化提高图神经网络的表达能力

TL;DR本文提出局部Weisfeiler-Leman(WL)算法以提高表达能力和降低计算复杂度,并解决所有k的局部 k-WL 的子图计数问题。研究证明,本地k-WL可以表达更多模式,但在表达能力上最多与(k + 1) -WL一样,比应用于整个图的k-WL更具有时间和空间效率。用局部 k-WL 等效的两个图的子图和诱导子图的计数是不变的。该算法也引入了局部和递归的 Layer k-WL以及一个可扩展片段技术,可用于任意k,以保证使用仅1-WL的确切计数,同时比Papp和Wattenhofer(2022a)提到的GNN层次更具表达能力。