读完这篇论文的时候我脑子里冒出一句话原来把逐关系循环压成一次张量运算模型能跑快这么多。这篇笔记是系列的第九篇主题是《A Vectorized Relational Graph Convolutional Network for Multi-Relational Network Alignment》核心是用向量化关系图卷积网络Vectorized Relational GCN解决多关系网络对齐Multi-Relational Network Alignment问题。先说这篇笔记适合谁看。如果你正在做图神经网络相关课题或者手里有跨社交平台用户对齐、知识图谱实体对齐、多源网络融合这类任务这篇笔记能帮你搞清楚三件事多关系网络对齐为什么难传统关系图卷积为什么慢论文的向量化改造到底改在哪里。没有基础也没关系我会把关系图卷积拆开讲清楚再讨论向量化的思路是怎么一步步推出来的。1. 这篇论文到底想解决什么问题多关系网络对齐里最容易被忽略的效率瓶颈1.1 网络对齐任务的基本盘网络对齐Network Alignment这个任务一句话说清楚就是给定两个或多个网络这些网络的节点集合不同但节点之间存在潜在的对应关系我们的目标是找出这种对应。最典型的场景是跨平台用户匹配——某用户在平台A的账号和平台B的账号是同一个自然人两个平台的社交关系网络结构不一样但共同好友模式会留下线索网络对齐就是把这些线索充分利用起来找到哪两个节点指向同一实体。知识图谱对齐也属于这类问题。例如两套不同来源的知识图谱描述了大量实体有的实体说的是同一个现实对象但它们在不同图谱里的ID、属性写法、关系集合都不一样。网络对齐要利用图结构信息和关系语义信息把等价实体对找出来。这个任务有一个天然痛点网络之间没有全局一致的身份标识。我们不能直接做字符串匹配只能靠结构相似性和语义相似性推断。早期方法靠网络拓扑特征比如公共邻居数、度分布、局部图结构签名做匹配后来发展为学习节点嵌入表示——先把每个节点投影到一个低维向量空间再在这个空间里计算节点之间的相似度用距离近的节点对作为对齐结果。1.2 多关系带来的三个痛点单关系网络对齐已经有很多研究积累但现实网络几乎都是多关系网络。社交网络里有关注好友拉黑点赞这些不同的边类型知识图谱里有出生地配偶参与作品获奖记录这些语义各异的谓词。论文把这类网络称为多关系网络对每个节点来说它的邻居必须按关系分开看待不能不分青红皂白地揉成一团。从对齐的角度看多关系带来三个实际困难。第一不同关系的判别力不一样。配偶这个关系的指向性很强两个网络里如果A节点连接了配偶节点B节点也连接了配偶节点这几乎是决定性的证据而浏览过这类弱关系可能充满噪音对对齐帮助很小。模型需要学会自动权衡不同关系的重要性而不是对它们一视同仁。第二关系种类多导致模型参数爆炸。如果每种关系都分配一个独立的变换矩阵关系数一多模型参数量呈线性增长在知识图谱这种常有几百上千种谓词的场景里直接不可接受。第三两个网络的模式不一定同构。网络A有导师关系网络B可能把这个语义拆成两条边或者换了一种描述方式模型必须有一定鲁棒性不能因为关系名不一致就完全失效。这三个痛点不是并列关系第三个是任务层面的挑战前两个共同指向模型设计上的核心矛盾——如何既表达出关系的多样性和特异性又不让参数规模失控。论文标题里关键词之一是Vectorized说明作者的解法重点放在了计算效率上但我在读完整篇论文后发现向量化改造其实顺带解决了第二个痛点的一部分。下面从基线模型说起。2. 基线R-GCN是怎么做的逐个关系更新权重模型是好模型但跑起来很笨2.1 关系图卷积的经典公式与直觉关系图卷积网络R-GCN是在普通图卷积网络GCN基础上的扩展。普通GCN假设图上所有边都是同一种关系信息聚合时把所有邻居的表示线性加在一起再做归一化。这个操作在数学上很简洁但它抹掉了边类型的信息。R-GCN的思路很直接既然边有类型那就按类型组织邻居每种类型用一个独立的变换矩阵。用公式写出来R-GCN第l层到第l1层的更新规则是[ h_v^{(l1)} \sigma\left(\sum_{r \in \mathcal{R}} \sum_{u \in \mathcal{N}r(v)} \frac{1}{c{v,r}} W_r^{(l)} h_u^{(l)} W_0^{(l)} h_v^{(l)}\right) ]这里的符号含义\mathcal{R}是关系集合\mathcal{N}r(v) 是节点v在关系r下的邻居集合W_r^{(l)} 是关系r对应的变换矩阵c{v,r}是归一化因子通常取度也可以取可学习的常数W_0 是自环的变换矩阵\sigma是激活函数。直觉上每一层都在做同一件事把来自不同关系的邻居信息分别翻译成自己的语言通过W_r然后累加起来。这个过程很像一个人接收多方反馈——导师的意见、同事的意见、家人的意见每类意见说话的方式和权重不一样你不能直接把它们混成一句话听而是要先理解每种关系的角色再综合判断。2.2 两个层面的浪费参数与计算R-GCN第一次被提出来的时候论文作者自己也意识到参数问题很大。假设隐藏层维度是64关系数有500个光是W_r的参数量就是500乘以64乘以64也就是大约200万参数。这还只是单层。加深几层之后参数量就更夸张在中小规模数据集上很容易过拟合。经典R-GCN论文提出了两个缓解方案基分解basis decomposition和共享对角块shared diagonal blocks。基分解的做法是把每个W_r表示为若干基矩阵的线性组合比如W_r Σ_b a_{rb} V_b所有关系共享同一组基矩阵V_b每个关系只需要学习一个组合系数向量a_r参数量从关系数×维度×维度降到了基个数×(维度×维度 关系数×基个数)。共享对角块的做法是约束W_r为块对角矩阵而且这些块在不同关系间共享一部分权重进一步降低自由度。这两种方法在参数层面缓解了压力但论文认为它没有解决另一个层面的问题——计算层的浪费。我读完代码级的分析之后对这个问题特别有感触。在标准实现里R-GCN的处理流程是先初始化一个全零输出矩阵然后遍历关系集合对于每个关系r取出该关系对应的邻接矩阵切片做一次矩阵乘法和一次累加。伪代码大致是这样output zeros((N, d_out)) for r in range(R): neighbor_sum G_r H # 关系r的邻接矩阵乘节点特征 output neighbor_sum W_r问题出在遍历关系集合这个循环上。关系数R不是一个小常数知识图谱场景里轻松上百。每次循环都是一次独立的稀疏矩阵乘法GPU在这种模式下并行度很低因为每一步之间是串行依赖的——你必须等累加完成才能进入下一个关系虽然矩阵乘法本身是并行的但整个循环的吞吐量被拖住了。另外一个隐性浪费是内存访问模式。每个关系的邻接矩阵G_r都是一个稀疏矩阵按行或按列存储稀疏矩阵在GPU上做乘法时内存访问不连续访存延迟高。如果能把多个关系的计算合并成一次大矩阵操作就能大幅提高GPU利用率。论文把这种逐关系循环的实现称为非向量化实现认为它没有充分发挥现代深度学习框架的张量运算能力。这也解释了标题里Vectorized这个词的来源——作者要把这个循环压扁成一次向量化操作。3. 向量化改造的核心思路把关系循环压成张量运算3.1 关键创新点1关系维度的通道化改造读完论文的核心章节我觉得最值得记住的类比是把关系看成图像的通道。图像处理里有通道的概念——一张RGB彩色图像由红、绿、蓝三个通道叠加而成卷积模型在处理时把通道维度当成一个完整的维度参与运算而不是先处理红色通道、再处理绿色通道、最后处理蓝色通道。论文的向量化R-GCN做的事情很像这个把所有关系的邻接矩阵堆叠成一个大的邻接张量形状是(R, N, N)其中R是关系数N是节点数然后把这个张量作为整体参与计算。更具体地说论文的聚合公式可以写成[ H^{(l1)} \sigma\left( \sum_{r} G_r H^{(l)} W_r^{(l)} H^{(l)} W_0^{(l)} \right) ]用张量表达就是邻接张量\mathcal{G}与节点特征张量H^{(l)}做批量乘法得到中间结果再与关系权重张量\mathcal{W}^{(l)}做批量乘法。整个过程用einstein求和表示非常简洁# 对应论文的核心向量化聚合操作 # G: [R, N, N] 邻接张量H: [N, d_in] 节点特征W: [R, d_in, d_out] 权重张量 mid torch.einsum(rnk,kd-rnd, G, H) out torch.einsum(rnd,rde-ne, mid, W)这会带来两个直接改变。首先循环消失了所有关系在一个大的批量运算中同时处理GPU的利用率更高。其次这个写法让整个模型可以用自动微分框架端到端训练梯度的流动更加顺畅因为不再有Python级别的循环割裂计算图。3.2 关键创新点2权重张量的低秩设计通道化解决了计算效率问题但参数规模问题还在。论文在向量化权重张量的基础上引入低秩约束具体做法是把权重张量\mathcal{W}分解成两个小矩阵的乘积[ W_r U \cdot S_r ]其中U是所有关系共享的投影矩阵形状是(d_in, d_mid)S_r是每个关系特有的低维矩阵形状是(d_mid, d_out)。这样每个关系只学习一个小矩阵整体参数量从O(R × d_in × d_out)降到了O(d_in × d_mid R × d_mid × d_out)。这个设计有一个值得注意的细节共享矩阵U起到的作用是公共语义空间投影把输入特征先统一映射到一个语义更紧凑的空间然后每个关系在这个紧凑空间里做个性化变换。这和之前提到的基分解有异曲同工之处但放在向量化框架下实现起来更自然因为张量运算天然支持这种分解。在理解这个设计时我想到了一个生活化的类比一个翻译团队U是一本统一的专业术语词典S_r则相当于不同语种的翻译规则。先查词典U再用对应语法的规则排列S_r比每个语种都从头学一套词汇系统高效得多。3.3 复杂度对比与可扩展性讨论论文里最打动我的一张表是复杂度对比。可以自己手推一遍非向量化R-GCN每层的时间复杂度大约是O(R × (非零边数 × d_in N × d_in × d_out))因为要遍历所有关系。向量化版本通过把邻接张量堆叠成批量稀疏矩阵理论上对GPU的稀疏矩阵乘法非常友好时间复杂度不变但常数因子大幅降低。更重要的是可以用现代矩阵乘法库cuBLAS、cuSPARSE的最大化吞吐路径而不是Python循环。参数量方面完整R-GCN是R × d_in × d_out基分解R-GCN是B × d_in × d_out R × d_mid向量化低秩版本是d_in × d_mid R × d_mid × d_out。在d_out远小于d_in时向量化的参数量可以控制得比基分解更好同时保留了每个关系独立信息的表达力。空间复杂度也要提一句。朴素地把R个邻接矩阵堆成稠密张量(R, N, N)在节点数N比较大的时候会爆炸比如N10万R100稠密存储就是100 × 10万 × 10万根本存不下。论文里明确用的是稀疏张量格式COO/CSC只有非零边才占用空间。实操中如果自己复现一定要从第一步就建立稀疏张量不要先建稠密再转换否则中间峰值内存会崩。模型上限也值得说由于关系权重索引是按预定义的固定关系集合排布的模型天然无法处理训练阶段没出现过的新关系。如果想要让模型具备对全新关系的适应能力需要引入关系侧的特征比如关系名称的文本嵌入这大概是论文没有展开的一个未来方向。4. 对齐模块与训练策略嵌入算出来之后怎么才能对上人4.1 相似度度量与损失函数向量化R-GCN只负责生成节点嵌入表示对齐本身还需要一个决策模块。论文用的是典型的嵌入空间对齐思路对齐对(u, v)分别属于图A和图B通过模型得到各自的表示z_u和z_v然后计算两者的相似度相似度越高对齐的可能性越大。相似度度量方面论文选用的是负欧氏距离配合嵌入归一化。之所以不用余弦相似度是因为余弦相似度对向量的模长不敏感而多关系网络的度数差异很大时模长本身可能携带节点重要度信息。负欧氏距离则能保留这种信息。为了方便训练通常在计算前对嵌入做L2归一化此时负欧氏距离和余弦相似度在序关系上是等价的但梯度特性略有差异。损失函数用的是带边界的排序损失margin ranking loss[ \mathcal{L} \sum_{(u,v) \in \mathcal{P}} \sum_{(u,v) \in \mathcal{N}} \max(0, \gamma d(u,v) - d(u,v)) ]其中距离d可以取负相似度或欧氏距离\gamma是边界超参数\mathcal{P}是已知的锚点对齐对种子对\mathcal{N}是负样本对。这个损失函数的逻辑很直白让已知对齐的节点对距离尽量小让随机采样的负样本对距离尽量大并且拉开一个至少\gamma的差距。\gamma设太大会让训练不稳定设太小则区分度不足我自己在复现类似模型时一般从1.0起步调参顺序是先固定\gamma再调负样本数量。4.2 跨图负采样为什么重要负采样策略在训练中的影响比很多人想象的大。最容易被忽视的坑是所有负样本都从单个图内采样。如果负样本只来自图A内部或只来自图B内部模型学到的判别力是区分图内节点而不是区分跨图节点对。对齐任务需要的是后者——给定图A的节点u要在图B的千万个节点里把真正的对应节点v挑出来。正确的做法是跨图负采样对每一个正样本对齐对(u, v)从图B中随机采样若干节点作为u的负样本从图A中随机采样若干节点作为v的负样本。用不严谨但直观的话说负样本必须主要来自对方的域这样模型才知道要在对面这个池子里做检索。论文还提到了一个类似难负样本挖掘的细节纯随机负样本在训练后期几乎全是简单样本loss很低模型提升缓慢。更有效的做法是以一定比例混合随机负样本和高相似度难负样本前者保证基础判别力后者推动模型继续打磨边界。不过论文的主方法没有采用难负样本挖掘只是通过增大负样本数量来缓解这个问题我推测作者是为了控制实验变量的数量。4.3 训练中的收敛技巧谈到训练细节嵌入维度、层数、dropout、归一化方式都影响最终对齐精度。论文采用的网络结构其实不深通常是两层向量化R-GCN因为对齐任务靠的是结构信息过深的GCN层数会导致过平滑——所有节点的表示趋于一致反而损失判别力。一个在论文实验部分没有明说但我从设计逻辑里推断的细节是残差连接对这个模型很重要。多关系聚合后信息混杂程度高残差连接能保证节点自身的初始特征在图深度传播中不被完全冲淡。如果自己在框架里复现建议在每一层都加上自环变换和残差连接再观察验证集上的MRR指标变化。训练轮数方面论文报告的情况是向量化版本由于收敛更快需要的epoch数少于逐关系循环版本这在实验部分有专门的可视化曲线说明。背后的原因其实也好解释低秩权重张量减少了有效参数空间优化器需要探索的区域更小自然更容易收敛。对于一个动辄数小时的大规模对齐任务来说epoch数减少和单步耗时的下降叠加在一起收益非常可观。最后还有一个不能忽略的操作嵌入归一化。对齐分数计算前对嵌入做L2归一化能避免某个节点因为度数高导致嵌入模长大得离谱从而在相似度计算中占据不公平的优势。这一步在很多论文里只是顺手一提但实际场景里不做归一化的话最终对齐结果会被高连接度节点主导准确率下滑明显。5. 实验设计与主要结论效率提升多少精度损失多少5.1 数据集与评估指标论文在实验部分用了公开的学术基准数据集进行验证。数据集的选取挺讲究覆盖了知识图谱对齐和社交网络匹配两类典型场景。我没有在笔记里记所有数据集的统计细节但几个关键特征值得说明这些数据集的关系数从个位到数百个不等节点数从几万到几十万都有且存在相当数量的多对多关系一个实体关联多个同类实体。评估指标用的是对齐任务的标准配置Hits1、Hits10和MRRMean Reciprocal Rank。MRR的计算方式是取每个源节点在目标图上的候选排序中正确答案排名的倒数再对所有源节点取平均。这个指标比Hitsk更敏感能反映模型整体的排序质量。Hits1代表严格准确率Hits10则是更宽松的前10命中率。数据划分也走的是通用协议给定一部分已知对齐对作为训练种子用剩余的未知对齐对作为测试集。在这个协议下训练时模型只能见种子对不能见测试对否则评估就没有意义。5.2 效率-精度权衡的关键观察论文报告的主要结论可以梳理成三个方面。第一训练和推理效率的提升是显著的。这个提升不完全来自于理论复杂度的改变而更多来自张量化运算对GPU友好度的提升。在我的经验里向量化改造带来的单步耗时下降在小图上可能只有两三倍在大图上会拉开到接近一个数量级的差距。原因在于固定开销内核启动、内存分配被摊薄了而逐关系循环的固定开销是乘以R的。第二精度的表现很有意思向量化低秩版本在最简单的单关系数据集上精度比完整R-GCN略低但在多关系数据集上的精度持平甚至更高。低秩约束在高关系数场景下不仅没有拖累精度反而由于减少过拟合空间让模型学到的表征更稳健。这个现象在机器学习里很常见参数多不等于效果好约束往往就是先验。第三与其他对齐方法的对比中向量化R-GCN在节点结构区分度比较强的数据集上优势明显因为多关系信息得到充分利用但在结构非常稀疏的数据集上单纯的结构方法都表现平平这时候需要额外节点属性信息来兜底。5.3 消融实验的启示论文做了几组消融实验我在笔记里记下了两个印象深刻的结论。第一把共享投影矩阵U替换为单位矩阵即去掉低秩分解退化为每关系独立权重在关系数较多的数据集上测试精度下降。这说明共享投影矩阵承担的跨关系公共语义表达能力是有价值的它不是单纯的参数压缩而是正则化与细粒度表达的平衡点。第二把邻接张量从稀疏格式换成稠密格式在数据集规模较小的时候影响不大一旦节点数超过一个阈值稠密格式直接内存溢出。这个消融实验在工程实践上很有指导意义复现的时候从一开始就坚持稀疏张量存储不要贪图方便用稠密邻接矩阵。论文还对比了不同相似度度量欧氏距离、余弦、曼哈顿距离的差异结果差异不算太大但欧氏距离在排序稳定性上略胜一筹。看到这个结果我更确信了一个观点在嵌入对齐类任务里度量本身不是核心竞争力真正拉开差距的是嵌入的质量和训练策略。6. 阅读笔记与可以偷师的思路6.1 这篇论文最值钱的一个思想如果要我用一句话概括核心创新我会说把多关系GCN从关系循环改造成关系维度张量化再配合低秩权重分解同时解决了参数爆炸和计算低效两个问题。这个思路之所以优秀不是因为它发明了一个全新的模型家族而是它意识到了计算层面的瓶颈与参数层面的瓶颈实际上是同一个问题的两面。当你能把所有关系的权重张量堆在一起做运算的时候低秩分解自然就成了顺势的解决方案。很多论文是在模型效果上做文章这篇则是在工程实现的优雅性上找到了突破点。把关系当成通道这个思想迁移到其他领域也很有价值。任何包含多个类别、共享操作的结构化数据场景都可以尝试做类似的张量化改造。比如时间序列的多模态特征、推荐系统中的多种用户行为点击、收藏、购买、浏览时长本质上都和多关系同构都可以设计共享底座加关系参数的向量化模型。6.2 复现时容易踩的坑按顺序记录一下我在复现思路时最容易踩的坑。第一稀疏邻接张量的构建不能图省事。逐批量往一个大的稀疏张量里插入非零元素速度极其缓慢等于把一个本应向量化的过程做成了隐式循环。正确做法是分别维护每个关系下的边列表最后统一拼接成COO格式的张量一次性建立稀疏张量。数据预处理这一步花费的时间会在后续训练中成倍赚回来。第二einsum表达式的排列组合眼花缭乱很容易搞错维度的对应关系。建议画一个维度标记图把R关系数、N节点数、d_in、d_out四个维度在计算图上的移动方向标清楚再对照公式写代码。我在第一版复现时就把G和H的维度顺序写反了结果模型性能一直上不去找了好久才发现是维度不匹配导致的。第三负采样比例要控制好。负样本太多会让loss被简单负样本主导导致模型主要精力都在推开简单负样本上反而忽略了对难样本的精细区分。建议从1:5开始调以1:10为上限超过10以后收益显著递减计算开销却线性上升。第四嵌入归一化不能省。我在一个小型数据集上对比过有无归一化的差异归一化之后Hits1提升了好几个百分点。原因是不做归一化时大度数节点的嵌入模长天然偏大计算距离时占据支配地位把那些结构相似但度数相差较大的真实对齐对压到了后排。6.3 我看到的局限性论文的优点很突出局限性也真实存在。泛化到未知关系的能力缺失在前面已经提到这是一个方向性瓶颈。更深一层的局限是完全依赖结构信息的倾向性网络对齐问题里节点属性如用户名、姓名、头像特征往往能提供极强的弱监督信号论文的方法虽然能整合属性特征把它们拼接到初始嵌入里但没有设计一个专门的机制来权衡结构证据与属性证据的可靠性。在结构稀疏的数据集上属性信息可能是唯一的抓手纯结构方法的召回率会比较难看。另一个局限是两图之间的关系映射问题。论文假定两个网络的关系集合在语义上是一致的至少对齐对共享关系类型但实际场景中两个网络的定义往往不一致例如图A把家庭成员细分为父母/子女/配偶图B只有一个笼统的亲属关系。这种关系模式异构问题需要额外的关系对齐环节论文没有覆盖。6.4 可以扩展的方向结合我平时做图学习项目的经验这篇论文至少有三个方向的扩展值得尝试。第一个方向是为新关系生成嵌入。在低秩分解的基础上把关系也投影到低维空间甚至用关系名称的预训练文本嵌入代替可学习向量。这样遇到一个新关系时可以通过它的文本嵌入生成对应的权重近似让模型具备零样本的新关系适应能力。第二个方向是把这个模型接入到多源网络对齐的迭代式框架中。现有方法通常把嵌入计算和对齐决策分成两个阶段但如果把对齐结果作为软标签反馈到图结构里即用高置信度对齐对增加跨图边再跑一轮嵌入更新往往能显著提升最终的召回率。这种迭代重标注做法在社区里效果不错和这篇论文的向量化模型组合起来很自然。第三个方向是动态网络的增量对齐。论文的模型是静态图设计的但社交网络和知识图谱都是持续增长的新增节点和新增关系会改变整个图的邻居分布。把向量化聚合的稀疏张量表示设计成可增量更新的版本区块化存储邻接张量可以让模型在不全量重训的情况下完成节点增量对齐工程价值很高。