技术摘要：非线性拉普拉斯算子提升符号定向图学习性能

问题陈述

现实世界的系统通常涉及既具有符号性（正向/负向，例如信任/不信任、喜欢/不喜欢）又具有定向性（不对称，例如从 A 到 B 的影响流）的相互作用。虽然图神经网络（GNN）已成功应用于标准图，但将其推广到符号定向图（Signed-Directed Graphs）仍面临挑战。现有的方法主要依赖于线性拉普拉斯算子或复杂的磁性拉普拉斯算子，来分别处理方向性和符号性，或者通过特定的线性定义进行处理。目前缺乏专门针对符号定向网络设计非线性拉普拉斯算子的研究。其核心挑战在于如何定义一个既能有效捕捉这些图的组合结构，又能保持计算效率和下游任务（如节点分类和链路预测）表达能力的算子。

方法论：NLSD 与 NLSD-GNN

本文引入了一种新型的**符号定向图非线性拉普拉斯算子（NLSD）**以及相应的谱 GNN 框架 NLSD-GNN。

1. 非线性符号定向拉普拉斯算子 (NLSD)

作者将定向图的非线性拉普拉斯定义（Yoshida, 2016）进行了扩展，以纳入边符号。该算子 $L_G(x)$ 是节点势向量 $x \in \mathbb{R}^V$ 的函数：

1. 图变换（边丢弃与自环）：
   对于给定的势向量 $x$，原始符号定向图 $G$ 被转换为一个符号无向图 $G_x$：

   • 对于每个有向边 $(u, v)$ 及其符号 $s \in \{+, -\}$：
     • 如果 $x_u \geq x_v$：在 $G_x$ 中包含一条具有相同符号 $s$ 和权重 $w(e)$ 的无向边 $\{u, v\}$。
     • 如果 $x_u < x_v$：该边被“丢弃”，并引入具有相同符号 $s$ 且权重为 $w(e)/2$ 的自环 $\{u, u\}$ 和 $\{v, v\}$。
   • 这种机制确保了消息传递仅沿着势差与边方向一致（或通过自环中和）的边进行。

2. 拉普拉斯构造：
   针对生成的符号无向图 $G_x$，计算标准的线性拉普拉斯矩阵 $L_{G_x}$。最终算子的输出为 $L_G(x) = L_{G_x} x$。

3. 二次型性质：
   二次型 $Q_G(x) = x^\top L_G(x)$ 泛化了符号图和定向图的割（cut）属性。最小化该形式会促使顶点嵌入满足：对于正向边，尾部位于头部左侧（$x_u \geq x_v$）；对于负向边，尾部位于头部右侧（$x_u \leq x_v$），从而有效地捕捉结构平衡和方向性。

4. 理论保证：
   论文证明了所提算子是半正定的，且归一化拉普拉斯矩阵的特征值位于 $[0, 2]$ 范围内，这与传统的图拉普拉斯矩阵类似。

2. NLSD-GNN 架构

为了在 GNN 中利用该算子，作者提出了两种变体，用于从节点特征 $H$ 生成所需的势向量 $x$：

• NLSD-GNN-MLP： 使用带有 tanh 激活函数的多层感知机（MLP），逐步将节点特征的维度降低为每个节点的标量值（1D 向量）。
• NLSD-GNN-Fast： 使用随机投影将节点特征映射为标量值，提供了一种计算高效的替代方案。

工作流程：

1. 特征投影： 将节点特征 $H$ 投影为标量向量 $x$。
2. 图变换： 根据 $x$ 将输入的符号定向图转换为符号无向图 $G_x$。
3. 谱卷积： 在使用变换后图的线性拉普拉斯矩阵的基础上，应用标准的谱 GNN 层（例如 ChebNet 式层）。
4. 预测： 将输出传递至线性层和 softmax 进行节点分类，或进行拼接以进行链路预测。

核心贡献

1. 新型算子定义： 首次定义了专门用于符号定向图的非线性拉普拉斯算子，统一了定向图拉普拉斯（Yoshida, 2016）与符号图拉普拉斯（Hou et al., 2003）的概念。
2. 理论表达力： 证明了该算子满足类似于 Cheeger 不等式的性质，并具有适用于谱图理论的谱性质（半正定性和有界的特征值）。
3. 高效框架 (NLSD-GNN)： 一种谱 GNN 架构，利用非线性算子，无需在每一步都进行复杂的特征分解，而是依赖于稀疏-稠密矩阵乘法。
4. 全面评估： 在节点分类（定向图和符号定向图）和链路预测（符号、方向及多分类任务）上的广泛实验表明，该方法达到了最先进（SOTA）或极具竞争力的性能。

实验结果

节点分类

• 数据集： 在定向图（Cornell, Texas, Wisconsin, Cora-ML, CiteSeer）和异质定向图（Chameleon, Squirrel, Arxiv-Year, Roman-Empire）上进行了测试。
• 性能：
  • 在同质定向数据集上，NLSD-GNN 变体始终位列前三，在多个数据集上超越了 MagNet 等谱基准模型以及 SAGE 和 GAT 等非谱方法（例如，在 Texas 和 Wisconsin 上表现最佳，在 Cornell 上排名第二）。
  • 在异质定向图中，NLSD-GNN 超越了 MagNet 和其他谱方法，但并未超越专门针对异质性设计的模型（如 HoloNet 或 Dir-GNN，后者并非为符号数据设计）。

符号定向图上的链路预测

• 数据集： Bitcoin-Alpha, Bitcoin-OTC, Slashdot, Epinions。
• 任务： 符号预测 (SP)、方向预测 (DP) 以及多分类任务 (3C, 4C, 5C)。
• 性能：
  • NLSD-GNN-Fast 在几乎所有数据集和任务上都优于所有基准方法（包括 SGCN, SDGNN, SiGAT, SNEA, SSSNET, SigMaNet, MSGNN）。
  • 该模型在需要同时处理符号和方向的任务（4C 和 5C）中表现出特别的优势，验证了统一非线性算子的有效性。
  • 消融实验证实，结合符号特征和方向信息可以获得最佳结果。

重要性与主张

论文声称 NLSD-GNN 框架 成功弥合了谱图理论与符号定向图学习之间的鸿沟。通过引入一种根据节点势动态调整图结构的非线性拉普拉斯算子，该方法实现了：

• 整合符号与定向数据： 它有效地建模了边符号与方向之间的相互作用，而线性算子在不使用过多参数的情况下往往难以同时捕捉这两者。
• 实现卓越性能： 它在符号定向图的链路预测方面树立了新的最先进基准，并在节点分类中展现出强大的竞争力。
• 保持高效性： 通过使用随机投影或简单的 MLP 来生成势，结合稀疏矩阵运算，确保了该方法相比于其他谱方法具有较高的计算效率（复杂度为 $O(MFd)$）。

作者总结道，他们的工作为分析复杂的系统（如社交网络、金融信任网络和舆论动力学等既有符号又有方向的系统）提供了一个稳健、具有理论依据且在实践中有效的工具。