arXiv:2412.12916cs.LGcs.CY2024-12

用弹簧力模拟节点关系,实现快速且准确的链接符号预测。

Graph Spring Neural ODEs for Link Sign Prediction

  • 基于弹簧力设计新型消息传递层,仅依赖节点距离和方向计算位置。
  • 在大规模图上实现接近顶尖方法的准确率,生成速度提升最高达28000倍。
  • 适合需要高效推理的大规模符号网络任务,如社交关系分析。

符号图可编码节点间的正负关系,广泛用于建模在线行为。节点表示学习在符号图上已有广泛应用,如链接符号预测。尽管数据集规模持续增长,现有方法常以牺牲可扩展性换取精度。本文提出一种新型消息传递层——图弹簧网络(GSN),其灵感来自弹簧力模型。结合图神经普通微分方程(Graph Neural ODEs)形式化方法,通过优化嵌入空间中的系统动力学来解决下游预测任务。一旦动力学模型训练完成,新数据的嵌入生成可通过数值积分求解ODE实现。与传统图卷积和图注意力网络依赖完整输入节点位置的可学习向量函数不同,本方法仅需节点在潜在空间中的距离与边向量方向,并引入可学习标量函数进行计算。我们具体实现了一种名为弹簧神经网络(SPR-NN)的模型,采用小型神经网络模拟吸引与排斥弹簧力,专门针对链接符号预测进行训练。实验表明,该方法在保持接近最先进精度的同时,在大规模图上实现了最高达28,000倍的嵌入生成速度提升。

原文摘要 · Abstract (English)

Signed graphs allow for encoding positive and negative relations between nodes and are used to model various online activities. Node representation learning for signed graphs is a well-studied task with important applications such as sign prediction. While the size of datasets is ever-increasing, recent methods often sacrifice scalability for accuracy. We propose a novel message-passing layer architecture called Graph Spring Network (GSN) modeled after spring forces. We combine it with a Graph Neural Ordinary Differential Equations (ODEs) formalism to optimize the system dynamics in embedding space to solve a downstream prediction task. Once the dynamics is learned, embedding generation for novel datasets is done by solving the ODEs in time using a numerical integration scheme. Our GSN layer leverages the fast-to-compute edge vector directions and learnable scalar functions that only depend on nodes' distances in latent space to compute the nodes' positions. Conversely, Graph Convolution and Graph Attention Network layers rely on learnable vector functions that require the full positions of input nodes in latent space. We propose a specific implementation called Spring-Neural-Network (SPR-NN) using a set of small neural networks mimicking attracting and repulsing spring forces that we train for link sign prediction. Experiments show that our method achieves accuracy close to the state-of-the-art methods with node generation time speedup factors of up to 28,000 on large graphs.

符号图神经ODE图学习快速生成

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。