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 traditional 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 2-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.
翻译:我们展示了一个我们称为Agentneal的新型图形神经网络,我们把它称为AgentNet, 专门设计用于图形层面的任务。 AgentNet 受亚线性算法的启发,它具有与图形大小无关的计算复杂性。 AgentNet 的架构与传统的图形神经网络的结构有根本的不同。 在AgentNet, 一些经过训练的“textit{neural代理商” 以智慧的方式在图形中走过, 然后共同决定输出。 我们对AgentNet 进行了广泛的理论分析。 我们对AgentNet 提供了广泛的理论分析: 我们显示, Agent Net 能够学会系统探索他们的邻居, 而AgentNet 可以区分一些甚至无法区分为 2-WL 的建筑结构。 此外, AgentNet 能够分离任何两个在子图谱上差异很大的图表。 我们用硬到差异的图形和真实世界的图形分类任务的合成实验证实了这些理论结果。 在这两种情况下,我们不仅比较标准 GNNS, 而且还比较了更昂贵的计算 GNNNN。</s>