关于单调最大求和 GNN 和 Datalog 的关系

May, 2023

关于单调最大求和 GNN 和 Datalog 的关系

On the Correspondence Between Monotonic Max-Sum GNNs and Datalog

David Tena Cucala, Bernardo Cuenca Grau, Boris Motik, Egor V. Kostylev

TL;DR本文主要研究基于图神经网络（GNN）的数据转换，并且分析了 GNN 的表达能力，提出一个处理 GNN 的标准编码，并且针对单调的最大 - 总和 GNN 和最大 GNN，证明了它们具有一定的表达能力，这些发现可以为进一步研究提供重要理论指导。

Abstract

Although there has been significant interest in applying machine learning techniques to structured data, the expressivity (i.e., a description of what can be learned) of such techniques is still poorly understood

machine learning data transformation graph neural networks expressivity max-sum gnns

发现论文，激发创造

关于聚合组合图神经网络推理的逻辑

提出了一种模态逻辑，在其中计数模态出现在线性不等式中。将每个公式转换为等价的图神经网络（GNN）。证明了广泛类别的 GNN 可以高效地转换为公式，从而明显改进了关于 GNN 的逻辑表达能力的文献。证明了可满足性问题的 PSPACE 完备性。这些结果将常规逻辑方法和 GNN 及其属性的推理前景结合起来，尤其适用于 GNN 查询、等价性检查等应用。证明了这种自然问题可以在多项式空间内解决。

Apr, 2024

有针对性的信息是否更有效？

图神经网络 (GNN) 是用于图的深度学习架构，其可表达性可以由具有计数的一阶逻辑的两个片段来描述。在非均匀设置中，两个 GNN 版本具有相同的可表达性，但在均匀设置中，第二个版本更为表达力强。

Mar, 2024

关于图神经网络的表达能力

该论文概述了图神经网络的 “表达能力” 概念，并就图神经网络的设计选择提供了有价值的见解。

Jan, 2024

图神经网络在知识图谱推理中的逻辑表现力

本文从逻辑表达式的角度对图神经网络进行了理论分析，实验结果验证了我们提出的实体标记方法的有效性，并揭示了基于标记技巧的最先进的方法为什么很有效。

Mar, 2023

混合图上的消息传递网络的泛化界限

研究了消息传递神经网络（MPNNs）的泛化能力，并给出了具体适用于具有规范化求和和平均聚合的 MPNNs 的泛化边界。在更现实和具有挑战性的情境下，通过分析简单的随机图、扰动的图标和稀疏图，得出结论表明，只要图形足够大，比训练集的大小复杂，MPNNs 仍然可以有效地泛化。

Apr, 2024

关于超图神经网络的表达能力和泛化性

研究了超图神经网络的表达能力、学习和（结构）通用性的框架，着重研究如何从有限数据集中学习，并对任意输入大小的图推理问题进行结构上的泛化。

Mar, 2023

无约束单调神经网络

该研究提出了一种无限制单调神经网络（UMNN）架构，基于函数导数严格为正，进而在自回归流中实现密度估计实验，并展示了 UMNN 提高变分推断的能力。

Aug, 2019

基于图神经网络的高效概率逻辑推理

本研究探讨了 Markov 逻辑网络和图神经网络的组合，并使用图神经网络进行 MLN 中的变分推理。研究提出了一种名为 ExpressGNN 的 GNN 变体，并通过多个基准数据集的广泛实验表明，ExpressGNN 在有效和高效的概率逻辑推理方面具有领先优势。

Jan, 2020

表达性单调神经网络

本文提出一种基于神经网络的单残差连接的加权受限架构，以实现对神经网络输入的任何子集的确切单调依赖，同时控制了神经网络的 Lipschitz 常数，从而提供了鲁棒性，该算法被用于训练强大，鲁棒和可解释的鉴别器，在多个基准测试中均取得了与当前最先进方法相媲美的性能。

Jul, 2023

图神经网络中池化的表达能力

本文研究图神经网络中的池化操作的表现力问题，并介绍了一种可以全面维持 message-passing 层的表现力的池化操作设计原则，进而通过实验验证其在图同构检测上的效果。

Apr, 2023