基于磁符号拉普拉斯矩阵的加权符号有向图卷积网络

Weighted Signed Directed Graph Convolutional Network Based on Magnetic Signed Laplacian Matrix

摘要

加权符号有向图因可通过符号、方向和权重建模复杂系统相互作用，受到广泛关注．将基于拉普拉斯矩阵的谱图卷积方法应用于此类图研究极具价值，兼具简洁性与可解释性．但该应用面临三大挑战：拉普拉斯矩阵易丧失半正定性、可谱分解性和特征值有界性，限制了适用范围；模型性能对边数量和权重分布敏感，稳定性不足；计算成本较高、效率受限．为此，本文提出新型磁符号拉普拉斯矩阵，并基于该矩阵设计加权符号有向图卷积网络（Weighted Signed Directed Graph Convolutional Network， WSDGCN）．理论推导表明，该矩阵适配加权符号有向图时可保留拉普拉斯矩阵的核心优良性质，实现差异化拓扑表征的同时，对边权重表现出较好的鲁棒性．在合成及真实数据集上的节点分类与链路预测实验表明，本文方法与其他方法相比具有较为优异的性能．

Abstract

Weighted signed directed graphs have attracted widespread attention for their ability to model interactions in complex systems via signed, directed and weighted edges. Applying Laplacian-based spectral graph convolution methods to such graphs is of great value, as these methods are both concise and interpretable. However, such applications face three major challenges: the Laplacian matrix tends to lose positive semi-definiteness, spectral decomposability and eigenvalue boundedness, thus limiting its scope of application; model performance is sensitive to the number of edges and weight distribution of datasets, leading to poor stability; and the computational cost is high with limited efficiency. To address these issues, this paper proposes a novel magnetic signed Laplacian matrix and designs a Weighted Signed Directed Graph Convolutional Network (WSDGCN) based on this matrix. Theoretical derivation demonstrates that this matrix preserves the core superior properties of the Laplacian matrix when adapted to weighted signed directed graphs. While achieving differentiated topological characterization, it exhibits favorable robustness to edge weights. Experiments on node classification and link prediction tasks conducted on both synthetic and real-world datasets verify that the proposed method achieves superior performance compared with other competing methods.

Graphical abstract

关键词

加权符号有向图 / 磁符号拉普拉斯矩阵 / 图卷积网络 / 节点分类 / 链路预测

Key words

weighted signed directed graphs / magnetic signed Laplacian matrix / graph convolutional network / node classification / link prediction

0 引 言

实际应用中，数据多呈不规则非欧结构．区别于图像、视频等传统欧氏数据，图结构数据因可精准刻画实体间复杂依赖关系被广泛应用，社交网络^［1］、知识图谱^［2］、蛋白质互作网络^［3］等均可自然建模为图．图是由顶点与边构成的抽象结构，可按边的符号与方向性分为4类（图1），现有相关研究若无特殊说明，均默认采用无权图设定．

为有效捕捉图的局部结构与节点级特征，图卷积网络（Graph Convolutional Network， GCN）应运而生，成为图数据表示学习的核心工具^［4‒5］．广义上GCN可分为空域^［6‒11］与谱域^{［12‒13］}两类方法：空域方法基于图的拓扑结构聚合邻域节点信息，谱域方法则通过拉普拉斯矩阵特征谱在频域完成卷积操作．空域方法多以平衡理论、地位理论为核心建模依据，如SIDE^［14］通过符号有向图上的随机游走策略，隐性融入平衡理论；SGCN^［15］通过目标函数设计与平衡/非平衡路径的信息聚合，将平衡理论显式纳入模型；SNEA^［16］在SGCN基础上扩展，实现表达能力更强的嵌入学习；SiGAT^［17］将38种motifs融入图注意力网络（Graph Attention Network， GAT）^［10］，融合两大理论捕捉符号有向图的语义信息；SDGNN^［18］引入4组权重矩阵实现边类型建模，并设计专用损失函数；DWSGCN^［19］则进一步拓展该框架，通过构建加权邻接矩阵、优化模块度，实现基于加权符号有向图的社区检测．

本文关注的谱域方法，绝大多数基于Kipf等^［13］提出的图卷积网络模型GCNs，该模型通过一阶滤波器简化了切比雪夫图卷积网络ChebNet^［12］，实现高效的谱域卷积．此外，谱域方法的核心在于拉普拉斯矩阵\mathit{L}的构建，但在符号有向图中，边的符号与方向会分别破坏拉普拉斯矩阵\mathit{L}的半正定性和可谱分解性，导致传统图卷积网络中的拉普拉斯矩阵\mathit{L}不再适用．针对边的符号问题，Kunegis等^［20］和Dittrich等^［21］提出符号拉普拉斯矩阵\overline{\mathit{L}}，通过对度矩阵元素取绝对值保证了半正定性；针对边的方向问题，Zhang等^［22］提出MagNet模型，引入可谱分解的厄米特磁拉普拉斯矩阵{\mathit{L}}^{\left(q\right)}．但上述两种矩阵均无法同时适配符号有向图的符号和方向双重属性，故Singh等^［23］融合二者构造思路，提出符号磁拉普拉斯矩阵{\overline{\mathit{L}}}^q，突破了该核心瓶颈．然而，{\overline{\mathit{L}}}^q在加权符号有向图中易出现编码偏差，如同为正出边，权重差异会导致编码形式完全不一致（如\left(A_{ij},A_{ji}\right)=\left(\mathrm{1},\mathrm{0}\right)与\left(\mathrm{2},\mathrm{0}\right)时，编码结果分别为\mathrm{0.5}i和-\mathrm{1}），无法稳定表征同类连边．针对该问题，He等^［24］提出MSGNN，重构度矩阵的绝对值取法，通过自适应参数q缓解权重相关的编码问题；同期，Fiorini等^［25］提出SigMaNet，设计符号磁拉普拉斯矩阵{\mathit{L}}^{\sigma }，通过符号函数消除权重幅值对编码的干扰．但后续研究发现，上述两种矩阵均存在连边类型编码覆盖不全的缺陷．因此，Ko等^［26］提出SDGCN，利用分段函数构造磁拉普拉斯矩阵{\mathit{L}}^q，并重点优化异向异号边（）的编码形式；Fiorini等^［27］则提出QuaterGCN，通过引入四元数（a+bi+cj+dk）构造四元数拉普拉斯矩阵{\mathit{L}}^{\mathrm{ϙ}}，增强双向非零边（A_{ij}\ne A_{ji}\ne \mathrm{0}）的编码能力．尽管如此，SDGCN中的{\mathit{L}}^q因邻接矩阵仅表征节点间的连接状态，仍存在权重信息利用不充分的问题；QuaterGCN中的{\mathit{L}}^{\mathrm{ϙ}}则对符号有向图中的单向边存在编码冗余问题，且两种矩阵的构造方式均极为复杂，导致模型运行效率较低．

其余诸多未提及的广义拉普拉斯矩阵也存在类似问题．因此，本文旨在为加权符号有向图构造一种新型磁符号拉普拉斯矩阵{\mathit{L}}^{q\text{'}}，该矩阵需既满足经典拉普拉斯矩阵\mathit{L}的核心性质，又能充分利用边的符号、方向与权重信息，同时保持矩阵构造的简洁性，提升模型的运行效率．各类拉普拉斯矩阵的具体情况如表1所示．

1 基础知识

1.1 图

图论中，给定一个图结构\mathrm{𝒢}=\left\{V,E\right\}，其中：V=\{v_{\mathrm{1}},\dots ,v_n\}为节点集合，E=\{e_{\mathrm{1}},\dots ,e_m\}为边集合，n=|V|\mathrm{、}m=|E|分别为节点数量和边数量．若图\mathrm{𝒢}中一节点对\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)间存在一条连边e_{\mathrm{1}}，则有e_{\mathrm{1}}=\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)=\mathrm{1}．

1.2 邻接矩阵\mathit{A}与拉普拉斯矩阵\mathit{L}

为便于数据处理，需将上述“集合化”的抽象描述转化为“数值化”的可计算表征，即利用邻接矩阵\mathit{A}对图数据进行规则化表示．根据图结构的不同类型，邻接矩阵\mathit{A}也有相应的特定形式．简单图中，A_{ij}\in {\left\{\mathrm{0},\mathrm{1}\right\}}^{n\times n}，A_{ij}与A_{ji}必定相等，故\mathit{A}为实对称矩阵；符号图中，A_{ij}\in {\{\mathrm{0},\mathrm{1},-\mathrm{1}\}}^{n\times n}，但仍保持对称性；有向图中，A_{ij}\in {\{\mathrm{0},\mathrm{1}\}}^{n\times n}，则允许非对称性；对于加权符号有向图，其邻接矩阵\mathit{A}\in {\mathbb{R}}^{n\times n}，同时具有符号图的边权正负取值和有向图的非对称性，其中边权值w_{i,j}反映链接强度，是融合符号、方向和权重三重属性的复杂图结构．

经典拉普拉斯矩阵\mathit{L}一般仅适用于简单图，定义式为\mathit{L}=\mathit{D}-\mathit{A}，其中：度矩阵\mathit{D}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\{d_{\mathrm{1}},\dots ,d_n\}，d_i={\sum }_j^n{A}_{ij},i=\mathrm{1},\mathrm{2},\dots ,n．由上述定义可知，矩阵\mathit{L}是实对称半正定矩阵．结合谱定理可知，实对称矩阵均可进行谱分解，故矩阵\mathit{L}的另一公式为\mathit{L}=\mathit{U}\mathit{\Lambda }{\mathit{U}}^{\mathrm{T}}．此外，为提升数值计算稳定性，实际应用中常对其进行标准化处理，得到标准化拉普拉斯矩阵，即{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}={\mathit{D}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\mathit{L}{\mathit{D}}^{-\frac{\mathrm{1}}{\mathrm{2}}}．而Kipf等^［13］已证明矩阵{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}的特征值介于［0， 2］．由此可得关键结论：谱图卷积网络的收敛性与优化性质，要求拉普拉斯矩阵满足半正定性、可谱分解性、标准化后特征值有界性三大核心性质．

而现实应用场景中，几乎不会遇到理想的简单图，绝大多数图结构都带有权重、符号或方向，属于非简单图．经典拉普拉斯矩阵不仅无法适配这类复杂图的定义，更难以同时满足三大核心性质，无法支撑谱图卷积的稳定运行，故须构建适配复杂图的广义拉普拉斯矩阵．前文明确的三大核心性质，也为本文构造适用于加权符号有向图的广义拉普拉斯矩阵，提供了严格的理论约束．

1.3 谱域图卷积网络

面对不同的图结构，构建相应的广义拉普拉斯矩阵后，可以此为基础，搭建谱域图卷积网络框架．从图信号处理视角看，谱域图卷积网络的构造核心是通过图傅里叶变换（Graph Fourier Transform， GFT）与傅里叶逆变换（Inverse Graph Fourier Transform， IGFT），结合滤波操作实现信号表征．以单通道输入信号\mathit{f}\in {\mathbb{R}}^{n\times \mathrm{1}}为例，对于简单图，通过GFT与IGFT可得单次卷积处理后的图信号：

{\mathit{f}}^{\text{'}}:=\mathit{U}{\mathit{g}}_{\theta }{\mathit{U}}^{\mathrm{T}}\mathit{f},(1)

式中：滤波器{\mathit{g}}_{\theta }={\mathit{g}}_{\theta }(\mathit{\Lambda })=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\left\{{\mathit{g}}_{\theta }\left({\lambda }_{\mathrm{1}}\right),\dots ,{\mathit{g}}_{\theta }({\lambda }_n)\right\}，\mathit{\Lambda }为拉普拉斯矩阵\mathit{L}的特征值矩阵，具体滤波过程如图2所示．

针对滤波器{\mathit{g}}_{\theta }的构造方式，文献［12］提出一种多项式滤波算子（Poly-Filter），令{\mathit{g}}_{\theta }(\mathit{\Lambda })={\sum }_{k=\mathrm{0}}^K{\theta }_k{\mathit{\Lambda }}^k，一次卷积过程可被简化为{\mathit{f}}^{\text{'}}:=\mathit{U}{\mathit{g}}_{\theta }(\mathit{\Lambda }){\mathit{U}}^{\mathrm{T}}\mathit{f}={\sum }_{k=\mathrm{0}}^K{\theta }_k{\mathit{L}}^k\mathit{f}．ChebNet采用切比雪夫滤波器（Cheby-Filter），令{\mathit{g}}_{\theta }(\mathit{\Lambda })={\sum }_{k=\mathrm{0}}^K{\theta }_k{T}_k\left(\tilde{\mathit{\Lambda }}\right)，其中正交基函数T_k\left(y\right)=\mathrm{2}y{T}_{k-\mathrm{1}}\left(y\right)-T_{k-\mathrm{2}}\left(y\right)，且T_{\mathrm{0}}\left(y\right)=\mathrm{1}\mathrm{、}{T}_{\mathrm{1}}\left(y\right)=y．因T_k\left(y\right)中y\in [-\mathrm{1},\mathrm{1}]，而标准化拉普拉斯矩阵特征值{\mathit{\Lambda }}_{ii}={\lambda }_i\in [\mathrm{0},\mathrm{2}]，需通过线性变换令{\tilde{\Lambda }}_{ii}=\frac{\mathrm{2}{\Lambda }_{ii}}{{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}}-\mathrm{1}\in [-\mathrm{1},\mathrm{1}]．为进一步降低参数量，文献［13］提出简化版的切比雪夫滤波器（GCN-Filter），取K = 1，并设\theta ={\theta }_{\mathrm{0}}=-{\theta }_{\mathrm{1}}，当{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}\approx \mathrm{2}时，GCN-Filter为{\mathit{g}}_{\theta }(\mathit{\Lambda })=\theta (\mathrm{2}\mathit{I}-\mathit{\Lambda })，显著减少参数量的同时，还能较好维持模型性能．由此，该滤波器下的一次卷积过程为{\mathit{f}}^{\text{'}}=\theta \mathit{U}(\mathrm{2}\mathit{I}-\mathit{\Lambda }){\mathit{U}}^{\mathrm{T}}\mathit{f}=\theta \left(\mathit{I}+{\mathit{D}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\mathit{A}{\mathit{D}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\right)\mathit{f}．

类似地，将单通道图信号\mathit{f}\in {\mathbb{R}}^n扩展到多通道图信号\mathit{F}\in {\mathbb{R}}^{n\times d_{\mathrm{i}\mathrm{n}}}，一次卷积过程为{\mathit{F}}^{\text{'}}=\sigma \left(\left(\mathit{I}+{\mathit{D}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\mathit{A}{\mathit{D}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\right)\mathit{F}\mathit{\Theta }\right)．一般情况下，卷积网络的卷积次数L也是一个可选参数，那么该卷积网络可拆分为多个卷积过程，第\mathit{𝓁}次卷积结果为{\mathit{F}}^{\left(\mathit{𝓁}\right)}=\sigma \left(\left(\mathit{I}+{\mathit{D}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\mathit{A}{\mathit{D}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\right){\mathit{F}}^{\left(\mathit{𝓁}-\mathrm{1}\right)}{\mathit{\Theta }}^{\left(\mathit{𝓁}-\mathrm{1}\right)}\right)，其中：\sigma \left(·\right)为激活函数，\mathit{𝓁}=\mathrm{1},\mathrm{2},\dots ,L．

1.4 节点间连边类型划分

针对图中节点对的连边类型划分，在有向图中，邻接矩阵元素A_{ij}表示节点v_i指向节点v_j的连边权重，A_{ji}则表示节点v_j指向节点v_i的连边权重．二者组合可完整刻画节点对（v_i,v_j）的连接状态，实现节点对与邻接矩阵元素对（A_{ij},A_{ji}）的一一映射．本文将“正出负入边”与“正入负出边”统一归类为“异向异号边”，符号有向图与加权符号有向图的连边类型划分规则如表2所示．

2 基于磁符号拉普拉斯矩阵的加权符号有向图

2.1 磁符号拉普拉斯矩阵

2.1.1 磁符号拉普拉斯矩阵的构建

回顾现有广义拉普拉斯矩阵的构造方式，可为本文设计提供关键思路．尽管MSGNN^［24］与SigMaNet^［25］中的拉普拉斯矩阵可能存在编码冗余问题，但二者的设计思路清晰且具有创新性．MSGNN通过重构度矩阵，并在{\mathit{L}}^{(q)}中引入自适应参数q=\mathrm{1}/\left[\mathrm{2}\mathrm{m}\mathrm{a}{\mathrm{x}}_{i,j}\left(A_{ij}-A_{ji}\right)\right]；SigMaNet则引入符号函数．SDGCN^［26］虽未在{\mathit{H}}^q中充分利用权重信息，但{\mathit{H}}^q的编码覆盖全部9种连边类型．尽管QuaterGCN^［27］采用复杂的四元数构造方式，却实现针对性强且巧妙的编码．结合这些广义拉普拉斯矩阵的构造思路，提炼其优缺点，本文提出一种新的磁符号拉普拉斯矩阵{\mathit{L}}^{q\text{'}}，定义如下：

{\mathit{L}}^{q\text{'}}=\tilde{\mathit{D}}-{\mathit{H}}^{q\text{'}},

\tilde{\mathit{D}}=\frac{\mathrm{1}}{\mathrm{2}}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\left\{\left(\left|\mathit{A}\right|+\left|{\mathit{A}}^{\mathrm{T}}\right|\right)\mathit{e}\right\}, {\mathit{H}}^{q\text{'}}={\mathit{A}}_S\odot {\mathit{P}}^{q\text{'}},

{\mathit{A}}_S=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathit{A}+{\mathit{A}}^{\mathrm{T}}\right),{\mathit{P}}^{q\text{'}}=\mathrm{e}\mathrm{x}\mathrm{p}\left(i·{\mathit{\Theta }}^{q\text{'}}\right)+\mathit{M},

{\mathit{\Theta }}^{q\text{'}}=\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}|\mathit{A}|-\mathrm{s}\mathrm{g}\mathrm{n}|{\mathit{A}}^{\mathrm{T}}|\right),\mathit{M}=\mathit{U}\odot ｛i\mathrm{*}\mathrm{s}\mathrm{g}\mathrm{n}(|\mathit{A}|-|{\mathit{A}}^{\mathrm{T}}|)-\mathit{e}{\mathit{e}}^{\mathrm{T}}｝,

\mathit{U}=\left\{\mathit{e}{\mathit{e}}^{\mathrm{T}}-\mathrm{s}\mathrm{g}\mathrm{n}\left[\mathrm{s}\mathrm{g}\mathrm{n}\left(\mathit{A}\odot {\mathit{A}}^{\mathrm{T}}\right)+\mathit{e}{\mathit{e}}^{\mathrm{T}}\right]\right\},(2)

式中：\mathit{e}为全一向量；\odot为哈达玛积；i为虚数单位，i^{\mathrm{2}}=-\mathrm{1}；\mathrm{s}\mathrm{g}\mathrm{n}(\cdot )为作用于矩阵的逐元素符号函数，\mathrm{s}\mathrm{g}\mathrm{n}\left(A_{ij}\right)=\{\mathrm{1},\mathrm{0},-\mathrm{1}\}．相应地，其标准化形式为{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}}={\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}{\mathit{L}}^{q\text{'}}{\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}=\mathit{I}-{\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}{\mathit{A}}_S{\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\odot {\mathit{P}}^{q\text{'}}．

2.1.2 矩阵{\mathit{L}}^{q\text{'}}三大核心性质的证明

针对新构造的磁符号拉普拉斯矩阵{\mathit{L}}^{q\text{'}}，为保证适用于加权符号有向图，首先需要证明其满足半正定性、可谱分解性和标准化形式下的特征值有界性．

定理 1 加权符号有向图中，{\mathit{L}}^{q\text{'}}和{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}}均为厄密特矩阵，且满足可谱分解性．

证明 根据{\mathit{L}}^{q\text{'}}的定义，有{\mathit{L}}^{q{\text{'}}^{\mathrm{*}}}=(\tilde{\mathit{D}}-{\mathit{H}}^{q\text{'}}{)}^{\mathrm{*}}={\tilde{\mathit{D}}}^{\mathrm{*}}-{\mathit{H}}^{q{\text{'}}^{\mathrm{*}}}．由于\tilde{\mathit{D}}是实对角矩阵，其转置与共轭等于自身，即{\tilde{\mathit{D}}}^{\mathrm{*}}=\tilde{\mathit{D}}．基于{\mathit{H}}^{q\text{'}}的定义，由于符号函数\mathrm{s}\mathrm{g}\mathrm{n}(\cdot )与共轭转置运算可交换，得：

\begin{array}{l}{\mathit{H}}^{q{\text{'}}^{\mathrm{*}}}={\mathit{A}}_S^{\mathrm{*}}\odot {\left[\mathrm{e}\mathrm{x}\mathrm{p}\left(i\mathrm{*}\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}|\mathit{A}|-\mathrm{s}\mathrm{g}\mathrm{n}|{\mathit{A}}^{\mathrm{T}}|\right)\right)\right]}^{\mathrm{*}}+{\mathit{A}}_S^{\mathrm{*}}\odot {\mathit{M}}^{\mathrm{*}}\\ ={\mathit{A}}_S^{\mathrm{*}}\odot {\left[\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}|\mathit{A}|-\mathrm{s}\mathrm{g}\mathrm{n}|{\mathit{A}}^{\mathrm{T}}|\right)+i\mathrm{*}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}|\mathit{A}|-\mathrm{s}\mathrm{g}\mathrm{n}|{\mathit{A}}^{\mathrm{T}}|\right)\right]}^{\mathrm{*}}+{\mathit{A}}_S^{\mathrm{*}}\odot {\mathit{M}}^{\mathrm{*}}.\end{array}(3)

与\tilde{\mathit{D}}类似，{\mathit{A}}_S是实对称矩阵，满足{\mathit{A}}_S^{\mathrm{*}}={\mathit{A}}_S．由于\mathrm{c}\mathrm{o}\mathrm{s}(\cdot )是偶函数、\mathrm{s}\mathrm{i}\mathrm{n}(\cdot )是奇函数，故：

实部{\left[\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}\left|\mathit{A}\right|-\mathrm{s}\mathrm{g}\mathrm{n}\left|{\mathit{A}}^{\mathrm{T}}\right|\right)\right]}^{\mathrm{T}}=\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}|\mathit{A}|-\mathrm{s}\mathrm{g}\mathrm{n}|{\mathit{A}}^{\mathrm{T}}|\right),(4)

虚部{\left[\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}\left|\mathit{A}\right|-\mathrm{s}\mathrm{g}\mathrm{n}\left|{\mathit{A}}^{\mathrm{T}}\right|\right)\right]}^{\mathrm{T}}=-\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}|\mathit{A}|-\mathrm{s}\mathrm{g}\mathrm{n}|{\mathit{A}}^{\mathrm{T}}|\right).(5)

对于{\mathit{M}}^{\mathrm{*}}，

{\mathit{M}}^{\mathrm{*}}=\left\{\mathit{e}{\mathit{e}}^{\mathrm{T}}-\mathrm{s}\mathrm{g}\mathrm{n}{\left[\mathrm{s}\mathrm{g}\mathrm{n}\left(\mathit{A}\odot {\mathit{A}}^{\mathrm{T}}\right)+\mathit{e}{\mathit{e}}^{\mathrm{T}}\right]}^{\mathrm{*}}\right\}\odot {\left\{i\mathrm{*}\mathrm{s}\mathrm{g}\mathrm{n}\left(\left|\mathit{A}\right|-\left|{\mathit{A}}^{\mathrm{T}}\right|\right)-\mathit{e}{\mathit{e}}^T\right\}}_{}^{\mathrm{*}}

=\left\{\mathit{e}{\mathit{e}}^{\mathrm{T}}-\mathrm{s}\mathrm{g}\mathrm{n}\left[\mathrm{s}\mathrm{g}\mathrm{n}\left(\mathit{A}\odot {\mathit{A}}^{\mathrm{T}}\right)+\mathit{e}{\mathit{e}}^{\mathrm{T}}\right]\right\}\odot \left\{-i\mathrm{*}\mathrm{s}\mathrm{g}\mathrm{n}\left(\left|\mathit{A}\right|-\left|{\mathit{A}}^{\mathrm{T}}\right|\right)-\mathit{e}{\mathit{e}}^T\right\}.(6)

由此可见，{\mathit{M}}^{\mathrm{T}}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}=\mathit{M}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l},{\mathit{M}}^{\mathrm{T}}.\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{g}=-\mathit{M}.\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{g}，{\mathit{H}}^{q{\text{'}}^{\mathrm{*}}}={\mathit{H}}^{q\text{'}}，故{\mathit{L}}^{q{\text{'}}^{\mathrm{*}}}={\mathit{L}}^{q\text{'}}．同理，{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q{\text{'}}^{\mathrm{*}}}={\left[{\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}{\mathit{L}}^{q\text{'}}{\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\right]}^{\mathrm{*}}={\tilde{\mathit{D}}}^{-{\frac{\mathrm{1}}{\mathrm{2}}}^{\mathrm{*}}}{\mathit{L}}^{q{\text{'}}^{\mathrm{*}}}{\tilde{\mathit{D}}}^{-{\frac{\mathrm{1}}{\mathrm{2}}}^{\mathrm{*}}}={\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}{\mathit{L}}^{q\text{'}}{\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}={\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}}．根据广义谱定理可知，厄密特矩阵可谱分解，故{\mathit{L}}^{q\text{'}}和{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}}均可谱分解．

定理 2 加权符号有向图中，{\mathit{L}}^{q\text{'}}和{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}}均满足半正定性．

证明 由于{\mathit{L}}^{q\text{'}}为厄密特矩阵，对任意向量\mathit{x}\in {\mathbb{C}}^n，满足\left({\mathit{x}}^{\mathrm{*}}{\mathit{L}}^{q\text{'}}\mathit{x}\right).\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{g}=\mathrm{0}，故只需考虑其实部．特别地，根据式（2）判定器\mathit{M}的定义可知，M_{ij}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}\in \{\mathrm{0},-\mathrm{1}\}．

\mathrm{2}\left({\mathit{x}}^{\mathrm{*}}{\mathit{L}}^{q\text{'}}\mathit{x}\right).\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}=\mathrm{2}{\sum }_{i=\mathrm{1}}^n{\tilde{D}}_{ii}{\left|{\mathit{x}}_i\right|}^{\mathrm{2}}-\mathrm{2}{\sum }_{i,j=\mathrm{1}}^n{A}_{s_{ij}}{\mathit{x}}_i{\overline{\mathit{x}}}_j\left[\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}|A_{ij}|-\mathrm{s}\mathrm{g}\mathrm{n}|A_{ji}|\right)+M_{ij}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}\right].(7)

因{\tilde{D}}_{ii}=\frac{\mathrm{1}}{\mathrm{2}}{\sum }_{j=\mathrm{1}}^n(|A_{ij}|+|A_{ji}|)\ge \frac{\mathrm{1}}{\mathrm{2}}{\sum }_{j=\mathrm{1}}^n\left|A_{ij}+A_{ji}\right|={\sum }_{i,j=\mathrm{1}}^n\left|A_{s_{ij}}\right|，且 \left[\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}|A_{ij}|-\mathrm{s}\mathrm{g}\mathrm{n}|A_{ji}|\right)+M_{ij}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}\right]\in［- 2， 1］，有：

\begin{array}{l}\mathrm{2}\left({\mathit{x}}^{\mathrm{*}}{\mathit{L}}^{q\text{'}}\mathit{x}\right).\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}\ge \mathrm{2}{\sum }_{i,j=\mathrm{1}}^n\left|A_{s_{ij}}\right|{\left|{\mathit{x}}_i\right|}^{\mathrm{2}}-\mathrm{2}{\sum }_{i,j=\mathrm{1}}^n{A}_{s_{ij}}\left|{\mathit{x}}_i\right|\left|{\mathit{x}}_j\right|\\ ={\sum }_{i,j=\mathrm{1}}^n\left|A_{s_{ij}}\right|{\left|{\mathit{x}}_i\right|}^{\mathrm{2}}+{\sum }_{i,j=\mathrm{1}}^n\left|A_{s_{ij}}\right|{\left|{\mathit{x}}_j\right|}^{\mathrm{2}}-\mathrm{2}{\sum }_{i,j=\mathrm{1}}^n{A}_{s_{ij}}\left|{\mathit{x}}_i\right|\left|{\mathit{x}}_j\right|\\ ={\sum }_{i,j=\mathrm{1}}^n\left|A_{s_{ij}}\right|{(\left|{\mathit{x}}_i\right|-\left|{\mathit{x}}_j\right|)}^{\mathrm{2}}\ge \mathrm{0}.\end{array}(8)

同理，令\mathit{y}={\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\mathit{x}，有{\mathit{x}}^{\mathrm{*}}{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}}\mathit{x}={\mathit{x}}^{\mathrm{*}}{\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}{\mathit{L}}^{q\text{'}}{\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\mathit{x}．故{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}}也满足半正定性．

定理 3 加权符号有向图中，{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}}的特征值属于［0， 2］．

证明 由定理2可知，{\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}}满足半正定性，故\lambda ({\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}})\ge \mathrm{0}．为证明其上界为2，可利用Courant-Fischer定理^［28］．令\mathit{y}={\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\mathit{x}， {\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}=\underset{\mathit{x}\ne \mathrm{0}}{\mathrm{m}\mathrm{a}\mathrm{x}}\frac{{\mathit{x}}^{\mathrm{*}}{\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}{\mathit{L}}^{q\text{'}}{\tilde{\mathit{D}}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\mathit{x}}{{\mathit{x}}^{\mathrm{*}}\mathit{x}}=\underset{\mathit{y}\ne \mathrm{0}}{\mathrm{m}\mathrm{a}\mathrm{x}}\frac{{\mathit{y}}^{\mathrm{*}}{\mathit{L}}^{q\text{'}}\mathit{y}}{{\mathit{y}}^{\mathrm{*}}\tilde{\mathit{D}}\mathit{y}}，因\tilde{\mathit{D}}是对角矩阵，分母可表示为：

{\mathit{y}}^{\mathrm{*}}\tilde{\mathit{D}}\mathit{y}={\sum }_{i,j=\mathrm{1}}^n{\tilde{D}}_{ij}{\mathit{y}}_i{\overline{\mathit{y}}}_j={\sum }_{i=\mathrm{1}}^n{\tilde{D}}_{ii}|{\mathit{y}}_i{|}^{\mathrm{2}}=\frac{\mathrm{1}}{\mathrm{2}}{\sum }_{i,j=\mathrm{1}}^n\left(\left|A_{ij}\right|+\left|A_{ji}\right|\right)|{\mathit{y}}_i{|}^{\mathrm{2}}.(9)

此外，分子为{\mathit{y}}^{\mathrm{*}}{\mathit{L}}^{q\text{'}}\mathit{y}={\mathit{y}}^{\mathrm{*}}\left(\tilde{\mathit{D}}-{\mathit{H}}^{q\text{'}}\right)\mathit{y}={\mathit{y}}^{\mathrm{*}}\left(\tilde{\mathit{D}}-{\mathit{A}}_S\odot {\mathit{P}}^{q\text{'}}\right)\mathit{y}={\mathit{y}}^{\mathrm{*}}\tilde{\mathit{D}}\mathit{y}-{\mathit{y}}^{\mathrm{*}}{\mathit{A}}_S\mathit{y}\odot {\mathit{P}}^{q\text{'}}，其中：

\begin{array}{l}{\mathit{P}}^{q\text{'}}=\mathrm{e}\mathrm{x}\mathrm{p}\left(i\mathrm{*}\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}\left|\mathit{A}\right|-\mathrm{s}\mathrm{g}\mathrm{n}\left|{\mathit{A}}^{\mathrm{T}}\right|\right)\right)+\mathit{M}\\ =\mathrm{c}\mathrm{o}\mathrm{s}\left(\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}\left|\mathit{A}\right|-\mathrm{s}\mathrm{g}\mathrm{n}\left|{\mathit{A}}^{\mathrm{T}}\right|\right)\right)+i\mathrm{*}\mathrm{s}\mathrm{i}\mathrm{n}\left(\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}\left|\mathit{A}\right|-\mathrm{s}\mathrm{g}\mathrm{n}\left|{\mathit{A}}^{\mathrm{T}}\right|\right)\right)+\mathit{M}.\end{array}(10)

由于\left({\mathit{y}}^{\mathrm{*}}{\mathit{L}}^{q\text{'}}\mathit{y}\right).\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{g}=\mathrm{0}，只需关注其实部．故{\mathit{P}}^{q\text{'}}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}=\mathrm{c}\mathrm{o}\mathrm{s}\left(\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}\left|\mathit{A}\right|-\mathrm{s}\mathrm{g}\mathrm{n}\left|{\mathit{A}}^{\mathrm{T}}\right|\right)\right)+\mathit{M}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}．在type8~9类型中，\mathrm{c}\mathrm{o}\mathrm{s}(\cdot )=\mathrm{1},\mathit{M}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}=-\mathrm{1},\mathrm{故}{\mathit{P}}^{q\text{'}}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}=\mathrm{0}；在其他连边类型中，\mathrm{c}\mathrm{o}\mathrm{s}(\cdot )\in (-\mathrm{1},\mathrm{1}),\mathit{M}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}=\mathrm{0},{\mathit{P}}^{q\text{'}}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}\in (-\mathrm{1},\mathrm{1})．因此，{\mathit{P}}^{q\text{'}}.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}\in (-\mathrm{1},\mathrm{1})．所以，{\mathit{y}}^{\mathrm{*}}{\mathit{L}}^{q\text{'}}\mathit{y}={\mathit{y}}^{\mathrm{*}}\tilde{\mathit{D}}\mathit{y}-{\mathit{y}}^{\mathrm{*}}{\mathit{A}}_S\mathit{y}\odot {\mathit{P}}^{q\text{'}}\le {\mathit{y}}^{\mathrm{*}}\tilde{\mathit{D}}\mathit{y}+{\mathit{y}}^{\mathrm{*}}|{\mathit{A}}_S|\mathit{y}．

根据三角不等式，有|A_{S_{ij}}|=\frac{\mathrm{1}}{\mathrm{2}}|A_{ij}+A_{ji}|\le \frac{\mathrm{1}}{\mathrm{2}}(\left|A_{ij}\right|+\left|A_{ji}\right|)，故：

{\mathit{y}}^{\mathrm{*}}{\mathit{L}}^{q\text{'}}\mathit{y}\le {\mathit{y}}^{\mathrm{*}}\tilde{\mathit{D}}\mathit{y}+{\mathit{y}}^{\mathrm{*}}|{\mathit{A}}_S|\mathit{y}

=\frac{\mathrm{1}}{\mathrm{2}}{\sum }_{i,j=\mathrm{1}}^n\left(\left|A_{ij}\right|+\left|A_{ji}\right|\right){\left|{\mathit{y}}_i\right|}^{\mathrm{2}}+\frac{\mathrm{1}}{\mathrm{2}}{\sum }_{i,j=\mathrm{1}}^n\left(\left|A_{ij}\right|+\left|A_{ji}\right|\right)|{\mathit{y}}_i||{\mathit{y}}_j|

=\frac{\mathrm{1}}{\mathrm{2}}{\sum }_{i,j=\mathrm{1}}^n\left|A_{ij}\right|\left({\left|{\mathit{y}}_i\right|}^{\mathrm{2}}+{\left|{\mathit{y}}_j\right|}^{\mathrm{2}}+\mathrm{2}|{\mathit{y}}_i||{\mathit{y}}_j|\right)

=\frac{\mathrm{1}}{\mathrm{2}}{\sum }_{i,j=\mathrm{1}}^n\left|A_{ij}\right|{\left(\left|{\mathit{y}}_i\right|+\left|{\mathit{y}}_j\right|\right)}^{\mathrm{2}}\le {\sum }_{i,j=\mathrm{1}}^n\left|A_{ij}\right|\left({\left|{\mathit{y}}_i\right|}^{\mathrm{2}}+{\left|{\mathit{y}}_j\right|}^{\mathrm{2}}\right)

={\sum }_{i,j=\mathrm{1}}^n\left(\left|A_{ij}\right|+\left|A_{ji}\right|\right){\left|{\mathit{y}}_i\right|}^{\mathrm{2}}=\mathrm{2}{\mathit{y}}^{\mathrm{*}}\tilde{\mathit{D}}\mathit{y},(11)

可得{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}=\underset{\mathit{y}\ne \mathrm{0}}{\mathrm{m}\mathrm{a}\mathrm{x}}\frac{{\mathit{y}}^{\mathrm{*}}{\mathit{L}}^{q\text{'}}\mathit{y}}{{\mathit{y}}^{\mathrm{*}}\tilde{\mathit{D}}\mathit{y}}=\mathrm{2}，故\lambda \left({\mathit{L}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{q\text{'}}\right)\in [\mathrm{0},\mathrm{2}]．

2.1.3 编码问题解析

新型磁符号拉普拉斯矩阵{\mathit{L}}^{q\text{'}}({\mathit{L}}^{q\text{'}}=\tilde{\mathit{D}}-{\mathit{H}}^{q\text{'}})满足三大核心性质，仅是其适配谱域图卷积网络的必要前提，要实现更优的模型性能，矩阵编码与连边类型的一一映射必不可少．该构造形式下，\tilde{\mathit{D}}为实对称矩阵，且由于原图不含自环，{\mathit{H}}^{q\text{'}}对角线元素全为0，此时从{\mathit{H}}^{q\text{'}}上去解析节点间的编码问题会简单很多．{\mathit{H}}^{q\text{'}}可将加权符号有向图的17种连边类型映射至符号有向图的9种连边类型，该特性完全源于其针对性的结构设计．为便于读者理解，本文对{\mathit{H}}^{q\text{'}}按模块进行拆分．

由式（2）可知，{\mathit{H}}^{q\text{'}}={\mathit{A}}_S\odot {\mathit{P}}^{q\text{'}}，其中：{\mathit{P}}^{q\text{'}}=\mathrm{e}\mathrm{x}\mathrm{p}\left(i·{\mathit{\Theta }}^{q\text{'}}\right)+\mathit{M}，{\mathit{\Theta }}^{q\text{'}}=\mathrm{2}\mathrm{\pi }q\left(\mathrm{s}\mathrm{g}\mathrm{n}\left|\mathit{A}\right|-\mathrm{s}\mathrm{g}\mathrm{n}\left|{\mathit{A}}^{\mathrm{T}}\right|\right)．{\mathit{P}}^{q\text{'}}由一个欧拉核\mathrm{e}\mathrm{x}\mathrm{p}\left(i·{\mathit{\Theta }}^{q\text{'}}\right)和一个“异向异号边”判定器\mathit{M}组成．欧拉核与9种连边类型的对应关系如表3所示．欧拉核仅在出现单向边type4~7时发挥作用，编码为复数，并可通过其虚部的正负性反映入边和出边，其他连边类型下均编码为1．

判定器\mathit{M}=\mathit{U}\odot \left\{i\mathrm{*}\mathrm{s}\mathrm{g}\mathrm{n}\left(\left|\mathit{A}\right|-\left|{\mathit{A}}^{\mathrm{T}}\right|\right)-\mathit{e}{\mathit{e}}^{\mathrm{T}}\right\}与9种连边类型的对应关系如表4所示．判定器\mathit{M}专门为“异向异号边”设计，此时U_{ij}=\mathrm{1}，\mathit{M}被激活，随后通过对比\left|\mathit{A}\right|和\left|{\mathit{A}}^{\mathrm{T}}\right|的大小，即可确定判定器\mathit{M}的编码值．而当连边为其他7种类型时，U_{ij}=\mathrm{0}，则M_{ij}=\mathrm{0}．

将欧拉核与判定器\mathit{M}的编码结果整合起来，即\mathrm{e}\mathrm{x}\mathrm{p}\left(i·{\mathit{\Theta }}^{q\text{'}}\right)+\mathit{M}，再与{\mathit{A}}_S做哈达玛积，即可得{\mathit{H}}^{q\text{'}}={\mathit{A}}_S\odot (\mathrm{e}\mathrm{x}\mathrm{p}\left(i·{\mathit{\Theta }}^{q\text{'}}\right)+\mathit{M})的最终编码形式．为直观展示{\mathit{H}}^{q\text{'}}的最终编码形式，令\omega =|A_S(i,j)|，可视化结果如图3所示．

本文对{\mathit{H}}^{q\text{'}}编码的分析揭示了一种参数依赖的相位机制．对于单向边（type4~7），{\mathit{H}}^{q\text{'}}编码完全依赖欧拉核，其行为由q决定．为保证复平面上的一一映射并避免谱混叠，将q限制在［0， 0.25］范围内，使\mathrm{2}\mathrm{\pi }q\in [\mathrm{0},\frac{\mathrm{\pi }}{\mathrm{2}}]，即可将4种单向边分别映射到4个象限中．其余5种连边类型则分别对应4条从原点出发、沿坐标轴方向的射线和原点，实现9种连边类型下的一一映射、不重叠．再仔细对比每种编码的含义，可以发现：当q=\mathrm{0}时，适用模型退化为无向图情形；当q = 0.25时，type4和type7都退化为\omega i，type5和type6都映射为-\omega i，导致区分性丢失．相比之下，当q\in (\mathrm{0},\mathrm{0.25})时，\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{2}\mathrm{\pi }q\in (\mathrm{0},\mathrm{1})严格单调递减，\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{2}\mathrm{\pi }q\in (\mathrm{0},\mathrm{1})严格单调递增，从而为全部9种连边类型生成独特的复编码．其中最简洁的表示出现在q = 0.125处，此时\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{2}\mathrm{\pi }q=\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{2}\mathrm{\pi }q=\frac{\sqrt[]{\mathrm{2}}}{\mathrm{2}}，故本文采用此参数作为基准．

此时，9种编码可统一表示为\omega (a+bi)，其中：\omega反映权重大小，\mathrm{s}\mathrm{g}\mathrm{n}(a)反映符号，\mathrm{s}\mathrm{g}\mathrm{n}(ab)反映方向．如H_{ij}^{q\text{'}}=\sqrt[]{\mathrm{2}}(\mathrm{1}+i)（\omega =\mathrm{2},a=b=\frac{\sqrt[]{\mathrm{2}}}{\mathrm{2}}）时，由于a>\mathrm{0}且b>\mathrm{0}，其对应权重为2的正出边（type4）．

2.2 基于磁符号拉普拉斯矩阵的加权符号有向图卷积网络

2.2.1 滤波器的选择

在新型磁符号拉普拉斯矩阵构造完成并确保其在加权符号有向图中能够反映符号、方向和权重三重属性信息的同时，满足图卷积网络的使用前提（三大核心性质），且具有差异化的编码形式后，可以该矩阵为基础，搭建一个用于加权符号有向图的谱域图卷积网络模型．

谱域图卷积网络模型的搭建在完成拉普拉斯矩阵的定义后，需先确定好滤波器的构造方式．回顾切比雪夫滤波器Cheby-Filter（{\mathit{g}}_{\theta }\left(\mathit{\Lambda }\right)={\sum }_{k=\mathrm{0}}^K{\theta }_k{T}_k(\tilde{\mathit{\Lambda }})）和其一阶简化版GCN-Filter（{\mathit{g}}_{\theta }\left(\mathit{\Lambda }\right)={\theta }_{\mathrm{0}}\mathit{I}+{\theta }_{\mathrm{1}}(\mathit{\Lambda }-\mathit{I})）的构造方式，在模型性能和效率之间做出取舍，本文选择学习GCN-Filter，在Cheby-Filter的基础上保留K=\mathrm{1}的设定，但放松\theta ={\theta }_{\mathrm{0}}=-{\theta }_{\mathrm{1}}的强约束，保留两个独立可学习参数，继续以单通道输入信号\mathit{f}\in {\mathbb{C}}^{n\times \mathrm{1}}为例，由于\mathit{U}\tilde{\mathit{\Lambda }}{\mathit{U}}^{\mathrm{T}}=\tilde{\mathit{L}}，其中：\tilde{\mathit{\Lambda }}=\frac{\mathrm{2}\mathit{\Lambda }}{{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}}-\mathit{I}，\tilde{\mathit{L}}=\frac{\mathrm{2}\mathit{L}}{{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}}-\mathit{I}，代入式（1）可得一次卷积过程：

\mathit{f}\text{'}=\mathit{U}{\mathit{g}}_{\theta }\left(\mathit{\Lambda }\right){\mathit{U}}^{\mathrm{T}}\mathit{f}

=\mathit{U}\left({\sum }_{k=\mathrm{0}}^K{\theta }_k{T}_k\left(\tilde{\mathit{\Lambda }}\right)\right){\mathit{U}}^{\mathrm{T}}\mathit{f}

=\mathit{U}\left({\theta }_{\mathrm{0}}{T}_{\mathrm{0}}\left(\tilde{\mathit{\Lambda }}\right)+{\theta }_{\mathrm{1}}{T}_{\mathrm{1}}\left(\tilde{\mathit{\Lambda }}\right)\right){\mathit{U}}^{\mathrm{T}}\mathit{f}

=\mathit{U}({\theta }_{\mathrm{0}}+{\theta }_{\mathrm{1}}\tilde{\mathit{\Lambda }}){\mathit{U}}^{\mathrm{T}}\mathit{f}={\theta }_{\mathrm{0}}\mathit{f}+{\theta }_{\mathrm{1}}\tilde{\mathit{L}}\mathit{f}.(12)

扩展到多通道信号\mathit{F}\in {\mathbb{C}}^{n\times d_{\mathrm{i}\mathrm{n}}}，该卷积过程为：

\mathit{F}\text{'}=\sigma (\mathit{F}{\mathit{\Theta }}_{\mathrm{0}}+\tilde{\mathit{L}}\mathit{F}{\mathit{\Theta }}_{\mathrm{1}}+\mathit{B}),(13)

式中：\sigma \left(·\right)为非线性激活函数；{\mathit{\Theta }}_{\mathrm{0}},{\mathit{\Theta }}_{\mathrm{1}}\in {\mathbb{C}}^{d_{\mathrm{i}\mathrm{n}}\times d_{\mathrm{o}\mathrm{u}\mathrm{t}}}为可学习参数矩阵；\mathit{B}\in {\mathbb{C}}^{n\times d_{\mathrm{i}\mathrm{n}}}为偏置项矩阵；d_{\mathrm{i}\mathrm{n}}和d_{\mathrm{o}\mathrm{u}\mathrm{t}}分别为输入和输出的特征维度．

2.2.2 基于磁符号拉普拉斯矩阵的加权符号有向图卷积网络模型的构建

将本文构建的新型磁符号拉普拉斯矩阵{\mathit{L}}^{q\text{'}}代入上述一次卷积过程，即得可用于加权符号有向图的一次卷积网络模型{\mathit{F}}^{\text{'}}=\sigma (\mathit{F}{\mathit{\Theta }}_{\mathrm{0}}+{\tilde{\mathit{L}}}^{q\text{'}}\mathit{F}{\mathit{\Theta }}_{\mathrm{1}}+\mathit{B})．基于该公式，一次卷积过程不再需要按原始公式\mathit{f}\text{'}=\mathit{U}{\mathit{g}}_{\theta }\left(\mathit{\Lambda }\right){\mathit{U}}^{\mathrm{T}}\mathit{f}计算拉普拉斯矩阵的特征值\mathit{\Lambda }和特征向量\mathit{U}，仅需计算变形后的{\tilde{\mathit{L}}}^{q\text{'}}，极大提高了模型的运行效率．

本文中\mathit{F}\in {\mathbb{C}}^{n\times d_{\mathrm{i}\mathrm{n}}}，而一般常见的非线性激活函数大多只能处理实数，如\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}\left(·\right)等．故给出一个可适用于复数域的\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}\left(·\right)函数变体^{［24‒25］}，即\mathrm{c}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}\left(·\right)，定义式为：

(14)

此时该一次卷积过程为\mathit{F}\text{'}=\mathrm{c}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}(\mathit{F}{\mathit{\Theta }}_{\mathrm{0}}+{\tilde{\mathit{L}}}^{q\text{'}}\mathit{F}{\mathit{\Theta }}_{\mathrm{1}}+\mathit{B})．为实现卷积网络的构建，对上述单次卷积进行扩展，推导出卷积递推式：

{\mathit{F}}^{(\mathit{𝓁})}=\mathrm{c}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}({\mathit{F}}^{(\mathit{𝓁}-\mathrm{1})}{\mathit{\Theta }}_{\mathrm{0}}^{(\mathit{𝓁})}+{\tilde{\mathit{L}}}^{q\text{'}}{\mathit{F}}^{(\mathit{𝓁}-\mathrm{1})}{\mathit{\Theta }}_{\mathrm{1}}^{(\mathit{𝓁})}+{\mathit{B}}^{(\mathit{𝓁})}),(15)

式中：{\mathit{F}}^{(\mathit{𝓁})}\in {\mathbb{C}}^{n\times d_{\mathrm{o}\mathrm{u}\mathrm{t}}^{(\mathit{𝓁})}}，令d_{\mathrm{o}\mathrm{u}\mathrm{t}}^{(\mathrm{0})}=d_{\mathrm{i}\mathrm{n}}，其余情况下d_{\mathrm{o}\mathrm{u}\mathrm{t}}^{(\mathit{𝓁})}表示第ℓ层的输出维度，\mathit{𝓁}=\mathrm{1},\mathrm{2},\dots ,L．

结合下游任务的设计，对于最终表征\mathit{Z}，要求其元素属于实数域，故可利用\mathrm{u}\mathrm{n}\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{d}\left(·\right)函数将复数输入的实部矩阵和虚部矩阵左右拼接，即对于复数x\in {\mathbb{C}}^{a\times b}，定义式为：

\mathrm{u}\mathrm{n}\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{d}\left(x\right)=[x.\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l},x.\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{g}]\in {\mathbb{R}}^{a\times \mathrm{2}b}.(16)

故本文最终表征\mathit{Z}=\mathrm{u}\mathrm{n}\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{d}({\mathit{F}}^{\left(L\right)})\in {\mathbb{R}}^{n\times \mathrm{2}{d}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{(L)}}．为平衡模型的性能和复杂度，一般情况下设置L=\mathrm{2}，由此得到最终的模型整体框架，如图4所示．

3 实验分析

3.1 节点分类

3.1.1 数据获取

针对节点分类任务，本文通过符号有向随机块模型（Signed Directed Stochastic Block Model， SDSBM）生成模拟数据集．该模型可定义为SDSBM（\mathit{F}(\gamma ),n,p,\rho ,\eta），其中：\mathit{F}(\gamma )\in {\mathbb{R}}^{C\times C}为连接概率矩阵，是模型的核心参数，C表示块的数量；n控制生成节点的总规模；p表示边的稀疏度，与\mathit{F}(\gamma )共同决定边的存在概率（p\bullet \mathit{F}{(\gamma )}_{ij}）；\rho为最大块与最小块的规模比；\eta表示符号翻转概率，用于控制边符号的随机性．本文模拟数据集生成统一了基础参数：n=\mathrm{1}\mathrm{000},p=\mathrm{0.02},\rho =\mathrm{1.5},\eta =\mathrm{0.1},\gamma =\mathrm{0.1}；而\mathit{F}(\gamma )的定义沿用He等^［24］的设定．数据集分别命名为c3、c4、3c、4c和syn4，SDSBM具体数据生成机制请参阅文献［22， 24］．

具体而言，c3作为基础测试集，具有3个社区类别，可验证模型在标准符号有向图上的节点分类能力．c4在c3基础上增加1个社区，符号模式延续“正-负”交替，但复杂度显著提升．3c同样具有3个社区类别，其中两个社区间存在强烈的负向对抗关系，模拟“球迷-对手球迷”的典型场景，可用于验证模型对异构社区和强对抗关系的建模能力．4c则在3c基础上也增加1个社区，保留强负连接，同时引入更复杂的跨簇符号模式．syn4的正、负边概率分布相对均衡，可作为基准数据集，用于与现有图卷积模型进行定量对比，保证实验结果的复现性．此外，为提高模型性能可信度，本文还增设1个真实数据集Telegram，该数据集内部关系更加复杂混乱，能够有效体现各模型的非理想场景对应能力．

3.1.2 实验对比分析

正式实验前，本文选择一些可用于符号有向图的谱域方法作为对比，其均是在经典拉普拉斯矩阵基础上进行广义拉普拉斯矩阵的重新定义，与本文模型相似度高，对比的可信度高．针对不同数据集下不同算法的对比实验设置，一些基础设置均保持一致，如训练集、测试集与验证集比例设置为8∶1∶1、学习率为0.01、Dropout概率为0.5等．其余一些算法特有参数均以各自论文中的模型设置为准．节点分类任务中，本文采用十折交叉验证法提升实验结果的可靠性．实验过程中，得到十折验证每一折的准确率结果，并最终报告其平均值．表5展示了5种谱域方法在6个数据集上的测试集平均准确率结果．

由表5可知，在几乎所有数据集上，WSDGCN的准确率均取得最优或次优性能．与之相反，SDGCN在全部数据集上的表现较差，可能是因为该模型新构造的度矩阵（{\mathit{D}}_S=\frac{\mathrm{1}}{\mathrm{2}}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}((\mathit{A}+{\mathit{A}}^{\mathrm{T}})\mathit{e})）无法有效处理符号信息．对比各数据集下的模型性能可以发现，所有算法在3c和c3数据集上的表现均优于其他数据集．推测该性能提升的原因在于3c和c3数据集的社区数量更少（C = 3），而其余数据集的社区数量均为4；较低的结构复杂度可能是模型性能得以提升的关键因素．

3.2 链路预测

3.2.1 数据获取与评价指标确定

针对链路预测任务，本文选择4个真实数据集Bitcoin_Alpha^［29］、Bitcoin_Otc^［29］、Slashdot^［30］和Epinions^［31］，其节点与连边数量统计如表6所示．

有关链路预测任务的指标较多，本文选择Macro-F1、Micro-F1和AUC得分．此外，由于4个数据集规模均较大，实验中模型运行时间具有差异，本文也进行统计，以反映各模型在数据集上的效率．

有关加权符号有向图下的链路预测，本文进一步细化任务划分．需要说明的是，本文的“加权”主要体现在磁符号拉普拉斯矩阵构造及卷积传播过程中对边权信息的显式利用，而非将边权作为单独预测目标．关于权重信息，本文不作预测，这也是未来努力的方向之一．就符号和方向信息而言，根据数据形式\left(v_i,v_j,w_{ij}\right)\in {\mathbb{R}}^{m\times \mathrm{3}}，任务可划分为DEP任务和DSEP任务．链路方向和存在性预测（DEP）：给定一节点对\left(v_i,v_j\right)，模型需预测\left(v_i,v_j\right)\in E或\left(v_j,v_i\right)\in E或\left(v_i,v_j\right),\left(v_j,v_i\right)\notin E．链路方向、符号和存在性预测（DSEP）：给定一节点对\left(v_i,v_j\right)，模型需预测\left(v_i,v_j\right)\in E^{+}或\left(v_i,v_j\right)\in E^{-}或\left(v_j,v_i\right)\in E^{+}或\left(v_j,v_i\right)\in E^{-}或\left(v_i,v_j\right),\left(v_j,v_i\right)\notin E．

3.2.2 实验对比分析

两个链路预测任务下的对比实验均选取9个对比模型，包括空域方法（SGCN^［15］、SNEA^［16］、SSSNET^［32］、SiGAT^［17］、SDGNN^［18］）和谱域方法（MSGNN^［24］、SigMaNet^［25］、SDGCN^［26］、QuaterGCN^［27］），以更好验证本文模型的性能．

正式实验前，对核心超参数进行调优．如在固定其他超参数的前提下，将隐藏层维度在集合\{\mathrm{8},\mathrm{16},\dots ,\mathrm{72}\}内逐一调整，并基于AUC指标与运行时间的帕累托最优性，选定隐藏层维度为24．通过相同的调优策略，确定其余超参数的取值，如训练集比例为0.8、训练轮数为300．随后，开展不同模型间的性能对比．为保证实验公平性，其余模型均沿用原论文中公布的超参数设置．

如图5所示，在DEP和DSEP两类任务中，WSDGCN在4个数据集的3项评价指标上均取得较优性能，多数指标达到最优水平，部分指标表现接近最优；同时，在9种对比模型中保持了具有竞争力的运行时间，体现模型在性能与效率之间的良好平衡．此外，与其他算法相比，WSDGCN在不同数据集上的性能表现整体更为稳定．以DSEP任务下的AUC得分为例，WSDGCN的取值极差仅为0.025，远小于SDGCN的0.052，其性能波动范围较小，展现出较好的稳定性．

结合WSDGCN中磁符号拉普拉斯矩阵的构造方式来看，与MSGNN所用拉普拉斯矩阵相比，判别矩阵\mathit{M}的引入增加了模型的复杂度，导致计算时间略有上升；但针对9种边类型设计的差异化编码策略，是该模型取得较优性能的关键原因．由于数据集中type8~9的边类型占比极低，故WSDGCN相对MSGNN的性能提升效果并未表现得尤为显著．此外，对比谱域方法与空域方法的整体表现可以发现，谱域方法的平均性能普遍优于空域方法，且未在计算效率上做出大幅牺牲．值得注意的是，空域方法SiGAT的运行时间较长，可能与其注意力机制相关；而谱域方法QuaterGCN的运行时间偏长，主要原因是其磁符号拉普拉斯矩阵的构造方式过于复杂．

4 结 论

本文针对加权符号有向图的谱图卷积应用难点，提出新型磁符号拉普拉斯矩阵，并基于该矩阵构建了加权符号有向图卷积网络WSDGCN．所提磁符号拉普拉斯矩阵可对符号有向图9类连边实现差异化拓扑表征，将加权符号有向图的17种边情况自然映射至对应连边类型，在有效表征拓扑结构的同时，对边权重表现出较好的鲁棒性．多组实验结果表明，所提WSDGCN模型在不同数据集上均取得较优性能，兼具良好的鲁棒性与计算效率，验证了所提矩阵在复杂图结构建模中的有效性与泛化能力．

本研究仍存在两点局限：一是当type8与type9两类边的符号邻接矩阵{\mathit{A}}_S(i,j)取值相等时，模型存在极小概率出现编码结果重复的问题；二是当前研究对边权重信息的利用尚不充分，链路预测任务中仅对边的符号与方向进行预测，未直接融合边权重信息．上述问题将在今后的工作中继续开展研究．

参考文献

[1] Backstrom L， Leskovec J ．Supervised random walks：Predicting and recommending links in social networks［C/OL］//WSDM，2011：635-644．

[2] Zou X H ．A survey on application of knowledge graph［J］．Journal of Physics：Conference Series，2020，1487：012016.

[3] Kashyap S， Kumar S， Agarwal V，et al ．Protein protein interaction network analysis of differentially expressed genes to understand involved biological processes in coronary artery disease and its different severity［J］．Gene Reports，2018，12：50-60.

[4] Ma Y， Tang J L ．Deep learning on graphs［M］．Cambridge：Cambridge University Press，2021.

[5] Wu Z H， Pan S R， Chen F W，et al ．A comprehensive survey on graph neural networks［J］．IEEE Transactions on Neural Networks and Learning Systems，2021，32（1）：4-24.

[6] Atwood J， Towsley D ．Diffusion-convolutional neural networks［C/OL］//NIPS，2016：2001-2009．

[7] Niepert M， Ahmed M， Kutzkov K ．Learning convolutional neural networks for graphs［C/OL］//ICML，2016：2014-2023．

[8] Gilmer J， Schoenholz S S， Riley P F，et al ．Neural message passing for quantum chemistry［C/OL］//ICML，2017：1263-1272．

[9] Monti F， Bronstein M M， Bresson X ．Geometric matrix completion with recurrent multi-graph neural networks［C/OL］//NIPS，2017：3700-3710．

[10] Veličković P， Cucurull G， Casanova A，et al ．Graph attention networks［C/OL］//ICLR，2018：1-12．

[11] Hamilton W L， Ying R， Leskovec J ．Inductive representation learning on large graphs［C/OL］//NIPS，2017：1025-1035．

[12] Defferrard M， Bresson X， Vandergheynst P ．Convolutional neural networks on graphs with fast localized spectral filte-ring［C/OL］//NIPS，2016：3844-3852．

[13] Kipf T N， Welling M ．Semi-supervised classification with graph convolutional networks［C/OL］//ICLR，2017：1-14．

[14] Kim J， Park H， Lee J E，et al ．SIDE：Representation learning in signed directed networks［C/OL］//WWW，2018：509-518．

[15] Derr T， Ma Y， Tang J L ．Signed graph convolutional networks［C/OL］//ICDM，2018：929-934．

[16] Li Y， Tian Y， Zhang J W，et al ．Learning signed network embedding via graph attention［C/OL］//AAAI，2020：4772-4779．

[17] Huang J J， Shen H W， Hou L，et al ．Signed graph attention networks［C/OL］//ICANN，2019：566-577．

[18] Huang J J， Shen H W， Hou L，et al ．SDGNN：Learning node representation for signed directed networks［C/OL］//AAAI，2021：196-203．

[19] Cheng H， He C B， Liu H，et al ．Community detection based on directed weighted signed graph convolutional networks［J］．IEEE Transactions on Network Science and Engineering，2024，11（2）：1642-1654.

[20] Kunegis J， Schmidt S， Lommatzsch A，et al ．Spectral analysis of signed graphs for clustering，prediction and visua-lization［C/OL］//SDM，2010：559-570．

[21] Dittrich T， Matz G ．Signal processing on signed graphs：Fundamentals and potentials［J］．IEEE Signal Processing Magazine，2020，37（6）：86-98.

[22] Zhang X T， He Y X， Brugnone N，et al ．MagNet：A neural network for directed graphs［C/OL］//NeurIPS，2021：1-13．

[23] Singh R， Chen Y X ．Signed graph neural networks：A frequency perspective［C/OL］//NeurIPS，2023：1-19．

[24] He Y X， Perlmutter M， Reinert G，et al ．MSGNN：A spectral graph neural network based on a novel magnetic signed Laplacian［C/OL］//LoG，2022：1-39．

[25] Fiorini S， Coniglio S， Ciavotta M，et al ．SigMaNet：One Laplacian to rule them all［C/OL］//AAAI，2023：7568-7576．

[26] Ko T， Choi Y， Kim C K ．A spectral graph convolution for signed directed graphs via magnetic Laplacian［J］．Neural Networks，2023，164：562-574.

[27] Fiorini S， Coniglio S， Ciavotta M，et al ．Graph learning in 4D：A quaternion-valued Laplacian to enhance spectral GCNs［C/OL］//AAAI，2024：12006-12015．

[28] Golub G H， van Loan C F ．Matrix computations［M］．4th ed．Baltimore：Johns Hopkins University Press，2013.

[29] Kumar S， Spezzano F， Subrahmanian V S，et al ．Edge weight prediction in weighted signed networks［C/OL］//ICDM，2016：221-230．

[30] Kunegis J， Lommatzsch A， Bauckhage C ．The Slashdot Zoo：Mining a social network with negative edges［C/OL］//WWW，2009：741-750．

[31] Guha R， Kumar R， Raghavan P，et al ．Propagation of trust and distrust［C/OL］//WWW，2004：403-412．

[32] He Y X， Reinert G， Wang S C，et al ．SSSNET：Semi-supervised signed network clustering［C/OL］//SDM，2022：244-252．

基金资助

国家自然科学基金-地区科学基金“图的生成连通性及相关问题研究”(12461067)

贵州省基础研究计划（自然科学类）“基于压缩感知理论的谱聚类算法研究”(ZK〔2023〕298)