On the Substructure Countability of Graph Neural Networks
On the Substructure Countability of Graph Neural Networks
复制标题
DOI：
10.1109/tkde.2022.3223471
复制
发表时间：
2023-11
影响因子：
8.9
通讯作者：
Wenwen Xia;Yuchen Li;Shenghong Li
中科院分区：
文献类型：
--
作者：
Wenwen Xia;Yuchen Li;Shenghong Li
随着图神经网络（GNN）在图相关任务上取得的经验成功，研究它们在这些任务上的理论能力是很有趣的。在本文中，我们专注于GNN在子结构计数方面的理论能力，这是许多应用中的一项基本但具有挑战性的任务。以前的工作已经证明，2维Weisfeiler-Leman算法（2-WL）等价的GNN只能计数有限的子结构。然而，理论上更强大和计算上更易处理的GNN的子结构计数能力仍然不清楚。在本文中，我们研究的条件下，子结构是理论可数的k-WL等价GNNs，然后专注于3-WL等价的，这是目前最强大的理论与实际计算成本的情况。此外，我们提出了一个算法来确定3-WL等价GNNs的子结构的可数性。我们的研究结果表明，3-WL等价GNNs可以计数更多的子结构比2-WL等价的。然而，可数模式的比例和预测性能随着模式大小的增加而下降。因此，我们提出了一个层排列池（LPP）模型，更好的子结构计数性能。LPP首先将数据图分解为子图。然后，我们提出了一个层置换方案来表示每个分解的子图作为一组矩阵。最后，LPP利用神经网络对矩阵进行预测。我们在各种数据集上将LPP与几种最先进的GNN进行了比较。实验结果表明，在RMSE度量下，LPP平均优于基线84%。
With the empirical success of Graph Neural Networks (GNNs) on graph-related tasks, it is intriguing to investigate their theoretical power on these tasks. In this paper, we focus on GNNs’ theoretical power on substructure counting, a fundamental yet challenging task in many applications. Previous works have proven that the 2-dimensional Weisfeiler-Leman algorithm (2-WL) equivalent GNNs can only count limited substructures. However, the substructure counting ability of theoretically more powerful and computationally tractable GNNs remains unclear. In this paper, we study conditions for substructures to be theoretically countable by k-WL equivalent GNNs, and then focus on 3-WL equivalent ones, which are currently the most theoretically powerful instances with practical computational cost. Further, we propose an algorithm to determine the countability of substructures for 3-WL equivalent GNNs. Our results reveal that 3-WL equivalent GNNs can count considerably more substructures than 2-WL equivalent ones. However, the proportion of countable patterns and prediction performance decrease as the pattern size increases. Therefore, we propose a Layer Permutation Pooling (LPP) model for better substructure counting performance. LPP first decomposes the data graph into subgraphs. Then we propose a layer permutation scheme to represent each decomposed subgraph as a set of matrices. Finally, LPP utilizes a neural network to conduct predictions on matrices. We compare LPP with several state-of-the-art GNNs on various datasets. Experimental results show that LPP outperforms baselines by 84% on average with the RMSE metric.