We present a novel graph neural network we call AgentNet, which is designed specifically for graph-level tasks. AgentNet is inspired by sublinear algorithms, featuring a computational complexity that is independent of the graph size. The architecture of AgentNet differs fundamentally from the architectures of known graph neural networks. In AgentNet, some trained \textit{neural agents} intelligently walk the graph, and then collectively decide on the output. We provide an extensive theoretical analysis of AgentNet: We show that the agents can learn to systematically explore their neighborhood and that AgentNet can distinguish some structures that are even indistinguishable by 3-WL. Moreover, AgentNet is able to separate any two graphs which are sufficiently different in terms of subgraphs. We confirm these theoretical results with synthetic experiments on hard-to-distinguish graphs and real-world graph classification tasks. In both cases, we compare favorably not only to standard GNNs but also to computationally more expensive GNN extensions.
翻译:我们展示了一个新的图形神经网络, 我们称之为 Agent 网络, 它专门设计为图形级任务。 Agent Net 受亚线性算法的启发, 它具有与图形大小无关的计算复杂性。 Agent Net 的架构与已知的图形神经网络的结构根本不同。 在 AgentNet 中, 一些受过训练的 \ textit{neural 代理商明智地走在图形上, 然后集体决定了输出。 我们对 Agent Net 提供了广泛的理论分析 : 我们显示, Agent 网络可以学会系统地探索他们的邻里, Agent Net 可以区分一些甚至无法被3-WL 区分的结构。 此外, Agent Net 可以分离任何两个在子图上差异很大的图表。 我们确认这些理论结果, 在硬到分裂的图形和真实世界的图形分类任务上进行合成实验。 在这两种情况下, 我们不仅比较标准 GNNS, 而且比较地比较更昂贵的 GNN 。