图同态卷积
本文研究了新颖的随机图嵌入算法,能在预期的多项式时间内区分所有非同构图,并基于 Lovasz 的同态计数理论实现对任意图的函数逼近,结果在多个基准图学习任务上表现竞争力。
Jun, 2023
通过分析图同态性的熵,我们提出了一种新的视角来研究图神经网络的泛化能力,并通过将图同态性与信息论度量联系起来,得出了适用于图和节点分类的泛化界限。通过我们提出的界限,能够捕捉到各种图结构的细微差别,包括但不限于路径、环和完全子图。通过图同态性,我们呈现了一个统一的框架,能够揭示广谱 GNN 模型的特性。通过在真实世界和人工合成数据集上观察到的泛化差距,我们验证了理论发现的实际可应用性。
Mar, 2024
本文研究了从连续矩阵群操作下闭合的流形采样的数据嵌入问题,提出并证明了特定矩阵的特征向量与群的幺模表示元素的张量积可导出表征群作用的扩散映射,该方法在聚类和配准数据点方面表现出色。
Jun, 2023
本文研究了用同构映射技术对图结构进行分析的方法,并通过引入颜色细化的广义,推广到了超图的结构分析。通过顶点彩色处理将超图和它的关联图中的同构映射联系起来,我们证明了当且仅当任何连通 Berig - 无圈超图 B 上的同构映射在两个超图 G 和 H 中的数量相同时,这种颜色细化的方法无法区分两个超图的结构。
Mar, 2019
图神经网络是一种用于学习图上不变函数的架构。本研究证明了现有方法中存在的不足,并提出了一种更精细化的方法,通过整合目标模式中所有结构的同构计数,实现了更加具有表达能力的架构,而不增加额外的计算复杂度。我们在标准基准数据集上进行了一系列理论和实证验证。
Feb, 2024
介绍一类称为 Graph Motif Parameters 的图参数,介绍如何根据这个框架更快地计算固定大小的子图在大图中的个数,以及针对一类这样的参数进行问题的复杂度二分,其中包括用于颜色保留的子图计数。
May, 2017
本研究通过引入 sigma 代数框架,将 GNN 的表现力和测试同构性的角度进行了比较,证明了不同类型的 GNN 的表现力在确定的条件下是等价的,提出了一种新的结构 Ring-GNN,该结构成功地区分了具有相同度数的非同构正则图,并在现实世界数据集上取得了良好的性能。
May, 2019
我们将神经网络的普适逼近定理推广到对于线性表示组不变或等变的映射,以建立一种像网络一样的计算模型,能够在能够逼近任何连续不变 / 等变映射的同时保持不变 / 等变。我们提出了完备的不变 / 等变网络的构造,通过引入中间多项式层,通过 Hilbert 和 Weyl 的定理证明了我们的构造方法。我们提出了适用于 SE(2)群的 “电荷守恒卷积” 模型,并证明其是连续 SE(2)等变信号变换的通用逼近器。
Apr, 2018