Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
复制标题
DOI：
10.48550/arxiv.2211.03232
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Anders Aamand;Justin Y. Chen;P. Indyk;Shyam Narayanan;R. Rubinfeld;Nicholas Schiefer;Sandeep Silwal-
中科院分区：
文献类型：
--
作者：
Anders Aamand;Justin Y. Chen;P. Indyk;Shyam Narayanan;R. Rubinfeld;Nicholas Schiefer;Sandeep Silwal-
最近的工作表明，图神经网络(GNN)在区分不同构图方面的表达能力与Weisfeeller-Lehman(WL)图测试完全相同。特别是，它们表明，可以用GNN来模拟WL测试。然而，这些模拟涉及用于图节点数$n$的大小为多项式甚至指数的‘组合’函数的神经网络，以及以$n$为线性长度的特征向量。我们提出了一种改进的WL测试在GNN上的模拟，具有更低的复杂度。特别地，在每个节点中实现组合函数的神经网络在$n$中只有多对数个参数，并且GNN中节点之间交换的特征向量仅由$O(\logn)$位组成。我们还给出了特征向量长度和神经网络大小的对数下界，表明我们的构造是(接近)最优的。
Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GNNs. However, those simulations involve neural networks for the 'combine' function of size polynomial or even exponential in the number of graph nodes $n$, as well as feature vectors of length linear in $n$. We present an improved simulation of the WL test on GNNs with \emph{exponentially} lower complexity. In particular, the neural network implementing the combine function in each node has only a polylogarithmic number of parameters in $n$, and the feature vectors exchanged by the nodes of GNN consists of only $O(\log n)$ bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (near)-optimality of our construction.