校准和提升多关系和时间图上 GNN 的逻辑表达能力
本文从逻辑表达式的角度对图神经网络进行了理论分析,实验结果验证了我们提出的实体标记方法的有效性,并揭示了基于标记技巧的最先进的方法为什么很有效。
Mar, 2023
图神经网络的表达能力可以完全用合适的一阶逻辑片段来描述。本文通过证明 GC2 查询不能由具有多项式激活函数的图神经网络表示,证明了多项式和流行的非多项式激活函数之间存在分离关系。
Oct, 2023
我们提出了一种基于逻辑的可解释模型,用于学习图形,并通过图神经网络(GNN)提炼该模型的算法。我们通过决策树模型以及扩展的二阶逻辑(C2)从 GNN 中提炼可解释的逻辑分类器,测试结果表明在可被 C2 表达的情况下,我们的方法优于 GNN。
Jun, 2024
利用参数化的关系图神经网络 R-GNN [t],我们在仅使用二次空间嵌入的情况下近似了 $3$-GNNs,对于较低的 t 值,如 $t=1$ 和 $t=2$,通过交换较少的信息消息,我们经常得到几个规划领域所需的 $C_3$ 特性。实验结果表明,相较于普通的 R-GNNs 和也近似了 $3$-GNNs 的边转换器,R-GNN [$1$] 和 R-GNN [$2$] 取得了明显的性能提升。
Mar, 2024
本研究探讨使用关系学习算法如何进行逻辑推理,在设计了一套基于一阶逻辑的基准测试套件 GraphLog 后,我们使用图神经网络 (GNN) 来进行评估,并发现模型的泛化和适应能力强度受到训练中遇到的不同逻辑规则的多样性的影响。
Mar, 2020
我们提出了一种能够有效捕捉高阶关系进行推理和学习的因子图神经网络模型,并通过适当选择信息聚合操作,实现了 Max-Product 和 Sum-Product 循环置信传播的单一架构。通过在真实和合成数据集上进行广泛的实验评估,证明了该模型的潜力。
Aug, 2023
本文提出了一种新的可解释 AI 方法 CF^2,结合因果推断理论的概念,通过优化问题,生成了一种两个因果视角的模型无关框架,用于产生 GNN 解释,并提供了一组基于对照和实际推理的度量方法,用于定量评估生成解释的必要性和充分性,实验证明在真实世界的数据集上,无论是否提供基本真理解释,CF^2 的生成解释都比以前的最先进方法更好。
Feb, 2022
图神经网络 (GNN) 是用于图的深度学习架构,其可表达性可以由具有计数的一阶逻辑的两个片段来描述。在非均匀设置中,两个 GNN 版本具有相同的可表达性,但在均匀设置中,第二个版本更为表达力强。
Mar, 2024
对于具有浮点数和实数的循环图神经网络,我们给出了两种情况下的精确逻辑特征,对于浮点数,与循环 GNN 匹配的形式是一种具有计数的基于规则的模态逻辑,而对于实数,我们使用适当的无限模态逻辑,也带有计数。此外,相对于在单调二阶逻辑(MSO)中定义的图属性,我们的无限和基于规则的逻辑的表达力是相等的,这意味着具有实数和浮点数的循环 GNN 在 MSO 可定义的属性上具有相同的表达力,并且说明对于这样的属性,实数循环 GNN 也是由(有限的!)基于规则的模态逻辑来特征化的。
May, 2024
提出了一种模态逻辑,在其中计数模态出现在线性不等式中。将每个公式转换为等价的图神经网络(GNN)。证明了广泛类别的 GNN 可以高效地转换为公式,从而明显改进了关于 GNN 的逻辑表达能力的文献。证明了可满足性问题的 PSPACE 完备性。这些结果将常规逻辑方法和 GNN 及其属性的推理前景结合起来,尤其适用于 GNN 查询、等价性检查等应用。证明了这种自然问题可以在多项式空间内解决。
Apr, 2024