提出可寻址且保留数量信息的虚拟节点，提升图神经网络全局通信能力。
Designing a Good Virtual Node: Addressable and Cardinality-Preserving Global Memory for Message Passing Architectures
- 用可寻址交叉注意力实现独立读写全局状态
- 在有限颜色域下实现多重集的单射表示，支持1-WL精化
- 实验验证其在多重性感知任务中的有效性，计算开销为O(nMd)
虚拟节点为消息传递神经网络提供了简单的全局通信路径，但标准的节点-虚拟节点-节点流程会将图压缩为单一同质状态，并对所有节点广播相同信息。基于Mishayev等人的双半径分析，我们探讨如何在不使用自注意力的情况下，通过辅助虚拟内存缓解这一容量瓶颈。研究提出两个要求：首先，全局记忆应分解为可独立写入和读取的状态，可通过可寻址交叉注意力槽实现；其次，仅具备寻址能力不足以保留多重性，因为Softmax注意力对均匀复制具有不变性。通过将每个槽查询作为私有键/值锚点插入，恢复被丢弃的归一化质量，在有界颜色域下实现了能实施1-WL精化的单射多重集表示。在多重性感知的双半径、基元计数及受限链接集预测任务上的实验表明，该方法在算术复杂度为O(nMd)的条件下有效实现了可寻址且保基数的虚拟内存。
原文摘要 · Abstract (English)
Virtual nodes give message-passing neural networks a simple global communication route, but the standard node--VN--node pipeline compresses the graph into one homogeneous state and broadcasts it identically to every node. Building on the Two-Radius analysis of Mishayev et al., we ask how auxiliary virtual memory can relieve this finite-capacity bottleneck without self-attention. We identify two requirements. First, the global memory should be factorized into independently writable and readable states: this can be achieved using addressable cross-attention slots. Second, addressability alone does not preserve multiplicity, because softmax attention is invariant to uniform replication. Inserting each slot query as a private key/value anchor recovers the discarded normalization mass and yields, on bounded color domains, an injective multiset representation able to implement a 1-WL refinement. Experiments on multiplicity-aware Two-Radius, motif counting, and constrained link-set prediction support this addressable and cardinality-preserving virtual memory at (O(nMd)) arithmetic cost.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。