arXiv:2505.20992cs.LGcs.SI2025-05KDD被引 3

不训练、一次前传,用随机噪声生成图节点的身份与位置嵌入。

Efficient Identity and Position Graph Embedding via Spectral-Based Random Feature Aggregation

  • 基于谱域特性,用无参数随机特征聚合实现高效嵌入
  • 仅一次前传即生成高质量身份与位置嵌入,无需训练
  • 适合对效率要求高、需快速获取结构信息的场景

图神经网络(GNN)通过特征聚合机制捕捉图结构,在多种任务中表现优异。根据需保留的拓扑属性(如节点角色或社区归属),图嵌入可分为身份嵌入和位置嵌入。然而,多数基于GNN的方法未能明确其捕获的属性。部分方法还因特征提取和训练等耗时耗内存步骤而效率低下。从图信号处理视角出发,我们发现图谱域中的高频与低频信息分别表征节点身份与位置。据此提出无参数的随机特征聚合(RFA)方法:(i)采用无学习参数的谱基GNN作为主干,(ii)仅以随机噪声为输入,(iii)通过一次前向传播(FFP)生成嵌入。受度修正谱聚类启发,进一步引入度修正机制。实验表明,两种带高通/低通滤波器的RFA变体均能通过一次FFP分别生成具有信息量的身份与位置嵌入,无需任何训练。RFA在嵌入质量与效率间取得更优平衡,优于多种基线方法。

原文摘要 · Abstract (English)

Graph neural networks (GNNs), which capture graph structures via a feature aggregation mechanism following the graph embedding framework, have demonstrated a powerful ability to support various tasks. According to the topology properties (e.g., structural roles or community memberships of nodes) to be preserved, graph embedding can be categorized into identity and position embedding. However, it is unclear for most GNN-based methods which property they can capture. Some of them may also suffer from low efficiency and scalability caused by several time- and space-consuming procedures (e.g., feature extraction and training). From a perspective of graph signal processing, we find that high- and low-frequency information in the graph spectral domain may characterize node identities and positions, respectively. Based on this investigation, we propose random feature aggregation (RFA) for efficient identity and position embedding, serving as an extreme ablation study regarding GNN feature aggregation. RFA (i) adopts a spectral-based GNN without learnable parameters as its backbone, (ii) only uses random noises as inputs, and (iii) derives embeddings via just one feed-forward propagation (FFP). Inspired by degree-corrected spectral clustering, we further introduce a degree correction mechanism to the GNN backbone. Surprisingly, our experiments demonstrate that two variants of RFA with high- and low-pass filters can respectively derive informative identity and position embeddings via just one FFP (i.e., without any training). As a result, RFA can achieve a better trade-off between quality and efficiency for both identity and position embedding over various baselines.

图神经网络谱方法无训练嵌入高效计算

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