[Paper] VS-Graph：可扩展且高效的图分类使用超维计算

Source: arXiv - 2512.03394v1

概览

本文提出了 VS‑Graph，一种将超轻量级的超维计算（HDC）引入图分类这一高要求任务的全新框架。通过用纯向量符号流水线取代基于反向传播的重量级图神经网络（GNN），作者实现了 竞争（甚至更优）的准确率，同时将训练时间缩短至 450 倍，使得在边缘设备和神经形态芯片上进行图学习成为可能。

主要贡献

• Spike Diffusion：一种基于拓扑的节点识别方案，直接将图结构编码为高维向量。
• Associative Message Passing：在超向量空间中完成的多跳邻域聚合，完全消除梯度更新的需求。
• 性能提升：在基准数据集（如 MUTAG、DD）上匹配或超越现代 GNN 基线，同时 比之前的 HDC 方法高出 4‑5 % 的准确率。
• 训练加速：由于没有反向传播，训练速度比传统 GNN 快 最高达 450 倍。
• 维度鲁棒性：即使将超向量压缩至 D = 128，仍能保持高准确率，为超紧凑硬件实现打开了大门。

方法论

1. 超向量编码 – 为每个节点分配一个随机的高维二进制（或双极）向量。图的邻接信息通过 Spike Diffusion 过程“脉冲”这些向量，使节点标识在邻居之间传播，并遵循图的拓扑结构。
2. 关联消息传递 – VS‑Graph 并不学习权重矩阵，而是通过向量符号体系（VSA）中典型的绑定（binding）和捆绑（bundling）操作，反复组合节点多跳邻域的脉冲向量，从而得到一个 图级超向量，聚合结构信息和特征信息。
3. 分类 – 最终的超向量与各类别原型进行相似度比较（如余弦相似度或汉明距离），相似度最高的类别即为预测结果。整个过程不需要梯度下降、损失函数或迭代轮次。

整个流水线 确定性，可以表示为一系列矩阵‑向量乘法和逐元素操作，天然适配 CPU、GPU，尤其是低功耗神经形态加速器。

结果与发现

• 训练时间：VS‑Graph 只需几秒，而 GNN 需要数分钟至数小时（最高 450 倍加速）。
• 维度测试：将超向量大小从 D = 10 000 降至 D = 128，在大多数基准上准确率下降 < 1 %，验证了对激进压缩的鲁棒性。
• 内存占用：模型仅存储每个类别的原型向量以及用于生成超向量的随机种子，总内存使用 < 1 MB（所有测试数据集）。

实际意义

• 边缘与物联网部署 – 开发者现在可以在微控制器或低功耗 ASIC 上运行基于图的推理（如分子属性检测、网络异常检测），无需完整的 GNN 堆栈。
• 快速原型 – 由于没有训练循环，数据科学家可以在分钟级而非小时级完成特征工程或图预处理的迭代。
• 神经形态硬件兼容 – 绑定/捆绑操作可直接映射到脉冲神经硬件，为未来超能效图分析奠定基础。
• 成本效益扩展 – 大规模图数据集（如社交网络子图分类）在普通云实例上也变得可处理，降低计算费用。

局限性与未来工作

• 表达能力上限 – 虽然 VS‑Graph 已缩小与 GNN 的差距，但在高度异质图（边属性占主导）上仍稍逊。
• 仅适用于静态图 – 当前形式假设图结构固定；将方法扩展到动态图或流式图是未来的研究方向。
• 可解释性受限 – 超向量相似度分数不如 GNN 中的注意力权重直观，调试难度更大。
• 硬件验证 – 作者展示了软件层面的加速，实际在边缘或神经形态芯片上的基准测试仍需进一步工作。

VS‑Graph 表明，受大脑启发的超维计算终于能够在图任务上与重量级深度学习竞争，为需要快速、轻量且可扩展图分类的开发者提供了实用路径。

作者

• Hamed Poursiami
• Shay Snyder
• Guojing Cong
• Thomas Potok
• Maryam Parsa

论文信息

• arXiv ID: 2512.03394v1
• 分类: cs.LG, cs.AI, cs.NE
• 发布日期: 2025 年 12 月 3 日
• PDF: Download PDF