突破均匀表达性局限，提出更高效的图神经网络表达机制。
Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks
- 用佩弗安激活函数分析GNN表达能力，揭示均匀表达性不可行
- 证明参数量仅随最大度数对数增长，可高效处理大规模图
- 理论与实验结合，适用于实际应用中的大图场景
统一表达性保证图神经网络（GNN）在不依赖输入图规模的情况下表达查询，这对减少参数量具有重要意义。已有研究证明，使用ReLU激活函数的GNN可实现二元受控一阶逻辑（GC2）的统一表达性。本文证明，对于一类包含Sigmoid和Tanh的佩弗安激活函数，该性质无法实现，回应了Grohe（2021）提出的问题。尽管如此，这类GNN仍能以参数量仅随输入图最大度数对数增长的方式高效表达GC2查询。进一步地，通过特定激活函数设计，可实现参数量与度数的双对数依赖关系。这表明统一表达性可被合理放松，从而有效覆盖实际应用中的大规模图数据。实验验证了理论估计的准确性。
原文摘要 · Abstract (English)
Uniform expressivity guarantees that a Graph Neural Network (GNN) can express a query without the parameters depending on the size of the input graphs. This property is desirable in applications in order to have number of trainable parameters that is independent of the size of the input graphs. Uniform expressivity of the two variable guarded fragment (GC2) of first order logic is a well-celebrated result for Rectified Linear Unit (ReLU) GNNs [Barcelo & al., 2020]. In this article, we prove that uniform expressivity of GC2 queries is not possible for GNNs with a wide class of Pfaffian activation functions (including the sigmoid and tanh), answering a question formulated by [Grohe, 2021]. We also show that despite these limitations, many of those GNNs can still efficiently express GC2 queries in a way that the number of parameters remains logarithmic on the maximal degree of the input graphs. Furthermore, we demonstrate that a log-log dependency on the degree is achievable for a certain choice of activation function. This shows that uniform expressivity can be successfully relaxed by covering large graphs appearing in practical applications. Our experiments illustrates that our theoretical estimates hold in practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。