证明了ReLU在布尔查询上比其他激活函数更强大。
The Boolean Power of ReLU
- 用数学证明ReLU可表达更多布尔查询
- 揭示了ReLU-GNN比TrReLU-GNN更强大
- 适合图神经网络理论研究者阅读
我们证明，在仅含单个布尔节点特征的有限简单无向图上，任意最终恒定激活函数族Σ与实数系数组合下的Σ-MPLang所表达的布尔查询，严格属于ReLU-MPLang所表达的布尔查询子集。该结果解决了近期提出的开放问题：在布尔查询能力上，ReLU-MPLang是否强于trReLU-MPLang。特别地，这表明ReLU-GNN在布尔特征图上的布尔查询表达能力严格强于{TrReLU,id}-GNN。
原文摘要 · Abstract (English)
We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in $Σ$-MPLang, for any collection $Σ$ of eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the Boolean queries expressible in ReLU-MPLang. We thereby settle a recently posed open problem: whether ReLU-MPLang is more powerful than trReLU-MPLang when it comes to Boolean queries. In particular, this implies that ReLU-GNNs are strictly more expressive than {TrReLU,id}-GNNs with respect to Boolean queries on Boolean-featured graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。