计算机研究与发展杂志

计算机研究与发展杂志2024年第8期

• 动态有权图上的随机游走概率计算

  王涵之,易璐,魏哲巍,甘骏豪,袁野,文继荣,杜小勇,

  图上的随机游走概率计算是传统图论与现代数据挖掘领域普遍关注的问题之一.现有工作普遍关注静态图上的随机游走概率计算，却鲜少关注与实际应用场景更贴合的权重动态图.针对动态有权图上的随机游走概率计算问题，提出了一种基于硬币翻转采样的随机游走概率计算方法.相比于传统的基于权重采样的随机游走概率计算方法，所提方法可以在保证随机游走概率计算结果无偏的前提下，同时做到近似最优的随机游走概率计算复杂度和最优的采样结构更新复杂度.作为对比，现有方法或具有较大的计算时间复杂度，或依赖于复杂的索引结构而难以在动态图上即时更新.对所提方法做出了详细的理论分析，并在真实图数据集上进行模拟实验，实验结果证实了所提方法的有效性.

• 针对大规模动态图流三角形计数的边哈希分布式抽样算法

  何玉林,吴波,吴定明,黄哲学,菲律普弗尼尔-维格,

  三角形计数是大图分析的一个经典问题，近年的研究工作主要集中在针对静态流式图的三角形数量估计上，相关流式图抽样算法只能处理边的插入操作，无法处理边的删除操作；而现有的动态流式图抽样算法估计准确性又偏低.针对上述问题，提出了基于边哈希分配的分布式抽样（edgehashingassignment-baseddistributedsampling，EHADS）算法，它是一个用于估计动态流式图中三角形数量的分布式流算法，可以快速准确地估计动态流式图中的全局三角形数量以及每个顶点的局部三角形数量.EHADS算法只对输入的图流进行1次处理，并在多台机器上对边进行抽样.与先进的单机流算法相比，EHADS算法具有2点优势：1）在相同样本容量的情况下，EHADS算法以更短的运行时间获得了更小的估计误差，估计全局三角形数量的误差平均降低了31.79%，估计局部三角形数量的误差平均降低了23.35%；2）EHADS算法能够提供流式图中三角形数量的无偏估计，并且严格的数学证明显示该无偏估计具有更小的方差.

• 图多智能体任务建模视角下的协作子任务行为发现

  李超,李文斌,高阳,

  大量多智能体任务都表现出近似可分解结构，其中相同交互集合中智能体间交互强度大，而不同交互集合中智能体间交互强度小.有效建模该结构并利用其来协调智能体动作选择可以提升合作型多智能体任务中多智能体强化学习算法的学习效率.然而，目前已有工作通常忽视并且无法有效实现这一目标.为解决该问题，使用动态图来建模多智能体任务中的近似可分解结构，并由此提出一种名叫协作子任务行为（coordinatedsubtaskpattern，CSP）的新算法来增强智能体间局部以及全局协作.具体而言，CSP算法使用子任务来识别智能体间的交互集合，并利用双层策略结构来将所有智能体周期性地分配到多个子任务中.这种分配方式可以准确刻画动态图上智能体间的交互关系.基于这种子任务分配，CSP算法提出子任务内和子任务间行为约束来提升智能体间局部以及全局协作.这2种行为约束确保相同子任务内的部分智能体间可以预知彼此动作选择，同时所有智能体选择优异的联合动作来最大化整体任务性能.在星际争霸环境的多个地图上开展实验，实验结果表明CSP算法明显优于多种对比算法，验证了所提算法可以实现智能体间的高效协作.

• GraphMLP-Mixer：基于图-多层感知机架构的高效多行为序列推荐方法

  卢晓凯,封军,韩永强,王皓,陈恩红,

  在多行为序列推荐领域，图神经网络（GNNs）虽被广泛应用，但存在局限性，如对序列间协同信号建模不足和处理长距离依赖性等问题.针对这些问题，提出了一种新的解决框架GraphMLP-Mixer.该框架首先构造全局物品图来增强模型对序列间协同信号的建模，然后将感知机-混合器架构与图神经网络结合，得到图-感知机混合器模型对用户兴趣进行充分挖掘.GraphMLP-Mixer具有2个显著优势：一是能够有效捕捉用户行为的全局依赖性，同时减轻信息过压缩问题；二是其时间与空间效率显著提高，其复杂度与用户交互行为的数量成线性关系，优于现有基于GNN多行为序列推荐模型.在3个真实的公开数据集上进行实验，大量的实验结果验证了GraphMLP-Mixer在处理多行为序列推荐问题时的有效性和高效性.

• 基于三分支图外部注意力网络的轻量化跨域序列推荐

  张劲羽,马晨曦,李超,赵中英,

  跨域序列推荐（cross-domainsequentialrecommendation，CSR）旨在通过挖掘用户在多域混合序列中的行为偏好来为其提供跨域个性化推荐服务.近年来，研究人员开始尝试将图卷积网络（graphconvolutionnetwork，GCN）集成到CSR中，以建模用户和项目之间的复杂关系.然而，基于图的CSR方法大多通过复杂的结构来捕捉用户在多个域中的序列行为模式，这导致其通常具有较高的计算复杂度和较大的内存开销，限制了模型在资源受限设备上的应用.此外，已有的轻量级图跨域序列推荐方法认为，应该采用单层聚合协议（singlelayeraggregatingprotocol，SLAP）来学习跨域序列图（cross-domainsequentialgraph，CSG）上的嵌入表示.基于这种协议的图卷积网络，能够规避多层聚合协议所带来的额外跨域噪声，但却难以捕捉域内的高阶序列依赖关系.为了解决上述挑战，提出了一种轻量级的三分支图外部注意力网络（tri-branchesgraphexternalattentionnetwork，TEA-Net）.具体而言，TEA-Net首先将原始CSG分为域间以及域内序列图，并设计了一种并行的三分支图卷积网络结构来学习图中的节点表示.该结构能够以较低的计算开销，在不引入额外跨域噪声的条件下，学习域间的低阶协同过滤关系和域内的高阶序列依赖关系.其次，在三分支结构的基础上，提出了一种改良的外部注意力（externalattention，EA）组件，该组件移除了EA中的非线性通道，使其能够以更低的开销挖掘项目序列依赖关系并将注意力权重在多个分支上共享.在2个真实数据集上进行了广泛的实验来验证TEA-Net的性能表现.与10种最先进的CSR方法相比，TEA-Net在轻量化性能和预测精度方面均取得了更好的结果.

• Graph4Cache：一种用于缓存预取的图神经网络模型

  尚晶,武智晖,肖智文,张逸飞,

  大多数计算系统利用缓存来减少数据访问时间，加快数据处理并平衡服务负载.缓存管理的关键在于确定即将被加载到缓存中或从缓存中丢弃的合适数据，以及进行缓存置换的合适时机，这对于提高缓存命中率至关重要.现有的缓存方案面临2个问题：在实时的、在线的缓存场景下难以洞察用户访问数据的热度信息，以及忽略了数据访问序列之间复杂的高阶信息.提出了一个基于GNN的缓存预取网络Graph4Cache.通过将单个访问序列建模为有向图（ASGraph），并引入虚拟节点聚合图中所有节点的信息和表示整个序列.然后由ASGraph的虚拟节点构造一个跨序列无向图（CSGraph）来学习跨序列特征，这极大地丰富了单个序列中有限的数据项转换模式.通过融合这2种图结构的信息，学习到了序列之间的高阶关联信息，并获取了丰富的用户意图.在多个公共数据集上的实验结果证明了该方法的有效性.Graph4Cache在P@20和MRR@20上均优于现有的缓存预测算法.

• 面向企业信用风险评估的多视角异质图神经网络方法

  魏少朋,梁婷,赵宇,庄福振,任福继,

  企业信用风险评估是一个重要且具有挑战的问题.由于金融市场中存在大量的异质关联关系，使得异质图神经网络天然适合建模企业信用风险.然而，现有大部分研究不能充分捕捉到复杂金融网络中企业的综合信用风险.针对此问题，提出了一个面向企业信用风险评估的多视角异质图神经网络方法——CRGNN.该方法包含自身风险编码器以及传染风险编码器，其中自身风险编码器建模基于企业特征信息的自身风险，传染风险编码器由新提出的分层异质图Transformer网络和分层异质图特征注意力网络2个子模块组成.这2个模块分别挖掘基于企业不同邻居视角的传染风险和基于不同特征维度视角的传染风险.为了充分利用异质关系信息，2个模块都采用了分层机制.在企业破产预测数据集SMEsD和企业信用评估数据集ECAD上进行了大量的实验，AUC指标相比最优基线模型分别提高了3.98个百分点和3.47个百分点.

• 基于异常感知的变分图自编码器的图级异常检测算法

  林馥,李明康,罗学雄,张书豪,张越,王梓桐,

  图异常检测在识别复杂数据结构的异常模式中具有重要作用，被广泛地应用于有害分子识别、金融欺诈检测、社交网络分析等领域.但目前的图异常检测研究大多数聚焦在节点级别的异常检测，针对图级别的异常检测方法仍然较少，且这些方法并不能对异常图数据进行充分挖掘，且对异常标签比较敏感，无法有效地捕捉异常样本的特征，存在模型泛化能力差、性能翻转问题，异常检测能力有待提升.提出了一种基于异常感知的变分图自编码器的图级异常检测算法（anomaly-awarevariationalgraphautoencoderbasedgraph-levelanomalydetectionalgorithm，VGAE-D），利用具有异常感知能力的变分图自编码器提取正常图和异常图数据的特征，并差异化正常图和异常图在编码空间中的编码信息分布，对图编码信息进一步挖掘来计算图的异常得分.在不同领域的8个公开数据集上进行实验，实验结果表明，提出的图级别异常检测方法能有效地对不同数据集中的异常图进行识别，异常检测性能高于目前主流的图级别异常方法，且具有少异常样本学习能力，较大程度上克服了性能翻转问题.

• 基于事件驱动的超图卷积网络的谣言检测方法

  曾智,赵书庆,刘欢,赵翔,罗敏楠,

  依靠社交平台谣言传播链检测谣言是社交网络分析研究中的一个重要课题.但以往的研究大多将这个任务过度简化为依靠评论的传播链检测谣言，忽略了对现实世界新闻帖的复杂用户和事件交互的关注，难以捕捉到这些信息提供的潜在检测线索.针对该挑战，提出了一个事件驱动的超图卷积网络（event-drivenhypergraphconvolutionalnetwork，EHGCN），首次尝试将新闻、用户和事件建模在一个统一的超图卷积网络之中，以提升谣言检测性能.具体而言，基于用户的中心网络构建同质用户圈，以增强用户感知的谣言检测.此外，EHGCN联合利用事件内的主事件和子事件关联以及事件间的不一致性关联来进行谣言检测.在3个真实世界的数据集上进行的实验结果验证了EHGCN相较于现有方法在谣言检测方面的优势.研究也证实EHGCN可以通过获取丰富的用户社交圈和事件信息，在谣言传播早期及时发现谣言.

• HSEGRL：一种分层可自解释的图表示学习模型

  李平,宋舒寒,张园,曹华伟,叶笑春,唐志敏,

  近年来，随着图神经网络（graphneuralnetwork，GNN）技术在社交、信息、化学、生物等领域的广泛应用，GNN可解释性也受到广泛的关注.然而，现有的解释方法无法捕获层次化的解释信息，同时，这些层次信息未能被充分利用以提升图分类任务的准确率.基于这一问题，提出了一种层次化自解释的图表示学习（hierarchicalself-explanationgraphrepresentationlearning，HSEGRL）模型，该模型通过发现图结构中的层次信息进行图分类预测的同时，输出层次化的模型自解释结果.具体而言，针对图层次信息的发现设计了提取信息的基本单元——解释子，该解释子由提取节点特征的编码器获取层次化解释感知子图的池化层和抽取高阶解释信息的解码器组成.其中，为了准确提取层次化的解释子图，针对该模型的池化操作进行了解释感知优化设计，该设计通过评估模型的拓扑及特征重要性，层次化地筛选解释子图，实现分层自解释的同时完成图分类任务.HSEGRL是一个功能完备且便于迁移的图表示学习自解释模型，可以层次化综合考虑模型的拓扑信息与节点特征信息.在模型有效性验证层面，分别在分子、蛋白质和社交数据集上进行大量实验，实验结果表明所提模型在图分类任务中的分类准确率高于已有的先进的GNN自解释模型和GNN模型，并通过可视化分层解释结果的信息证明了该解释方法可信.

• 基于元素分离与整体注意力的图卷积网络框架

  祝传振,王璇,郑强,

  目前，图卷积网络在处理图数据等非结构化数据方面具有很大的潜力，然而在处理稠密连接图时仍面临一定的挑战，因为其基于节点的邻域信息聚合机制容易导致整个网络图出现过度平滑现象从而弱化网络图的表达能力.稀疏图的构建在一定程度上能够缓解网络图在卷积过程中的过度平滑现象，但是稀疏图容易丢失信息且稀疏化的过程缺乏统一标准，从而影响模型的一致性和可解释性.为此，提出了一种基于元素分离与整体注意力的图卷积网络框架（EH-GCN）.该框架无需建立在稀疏图的基础之上，不仅能够在稠密连接图分别学习图的连接特征和节点特征，而且采用全局注意力机制进行连接特征和节点特征的整合，从而克服了传统图卷积网络框架在应对稠密连接图时的局限性，提高了网络图的特征表达能力.首先在ADNI，ABIDE和AIBL这3个脑影像数据集上构建全连接脑网络，验证了EH-GCN在稠密连接图分类任务中的有效性.随后，所提模型在FRANKENSTEIN化学分子图数据集上进行了测试，证明了其强大的泛化能力.此外，所提模型的可解释性分析结果与先前的神经病理学研究一致，进一步证明了所提模型的生物学基础.

• 基于图提示微调的交通流量预测

  赖培源,李程,王增辉,王昌栋,廖德章,

  交通流量预测是建设智慧城市重要的基础功能，对城市的交通管理和用户出行规划具有重要意义.由于时间维度和空间维度的扩展，交通流量的数据具有规模大、增长快速、实时更新等特征，传统的训练模型通常需要将大量的历史数据进行训练预测，导致较长的计算时间和较高的算力成本，因此，如何使用低计算成本的预测模型来满足广泛的流量预测需求是重要的技术挑战.近年来兴起的提示微调范式在自然语言处理的下游任务推广中取得了较好的效果，受其启发，提出利用少量的实时数据来微调优化大规模历史数据预训练的模型，为交通流量模型预测的优化应用提出了一种新的思路.通过引入图提示微调的交通流量预测（trafficflowpredictionbasedongraphprompt-finetuning，TPGPF）模型的泛化能力，在时空多维度下的交通流量图预测模型中，基于历史数据集进行预测模型的预训练，并引入可学习的提示向量，在预训练模型固化的情况下指导预训练的自监督学习模型，以适应新的数据预测任务，提升交通流量预测模型的通用性和有效性.通过在5个公开数据集上进行了大量的实验，证明了TPGPF的有效性.

• 基于规则提示的知识图谱通用推理预训练模型

  崔员宁,孙泽群,胡伟,

  知识图谱是存储真实世界海量知识的图数据库，为大量知识驱动的下游任务提供了数据支持.知识图谱往往具有不完备性，存在大量缺失的事实，因此知识图谱推理任务基于已知事实推理新结论来补全知识图谱.随着知识工程及其商业应用的研究与发展，大量通用和领域知识图谱被构建.现有知识图谱推理方法大多面向单一知识图谱的补全，不具备通用推理能力.近年来，受预训练大语言模型通用能力的启发，一些通用的知识图谱推理预训练模型被提出.针对现有预训练模型无法识别高质量推理模式的问题，提出一个基于规则提示的知识图谱通用推理预训练模型——RulePreM，该模型筛选与利用高质量推理规则来提高知识图谱上的推理能力.首先基于推理规则构建关系IO图和一个编码器RuleGNN对关系进行编码，然后将关系编码作为提示来编码知识图谱中的实体，最后对候选实体进行打分预测.还提出一种结合规则置信度的注意力机制，来进一步减少低质量推理模式的影响.实验结果表明，所提出的模型在43个不同设定下的知识图谱上具有良好的通用推理能力，平均性能指标均优于现有的有监督模型和预训练模型.

• 图神经常微分方程综述

  焦鹏飞,陈舒欣,郭翾,何东晓,刘栋,

  图神经网络（graphneuralnetwork，GNN）是处理图结构数据的强大工具，能够捕捉节点间的复杂关系和特征.但GNN的离散架构导致其在表示图结构、建模图演化、适应不规则数据和计算开销等方面面临诸多挑战.面对这些挑战，神经常微分方程（ordinarydifferentialequation，ODE）由于能够模拟系统状态的连续变化，具备“连续深度”的编码和推断能力，被作为解决GNN面临挑战的全新方法而引入.然而，神经ODE是为欧式结构数据设计的，无法直接捕捉图结构特性.因此，提出了图神经ODE，一种将神经ODE与GNN结合的新架构，可以更好地适应图结构数据并充分利用其特性.近年来，图神经ODE相关研究已经深入到图机器学习的各个方向中，引发了新的研究热潮.在此背景下，适时地对图神经ODE研究前沿进行了系统性综述.首先，回顾了GNN的关键优势和面临的诸多挑战，阐述了引入神经ODE并与GNN结合的理论基础和实践意义.随后，详细介绍了图神经ODE的背景和基本概念，并提出了一种新颖的分类方法，在此基础上对当前的相关方法进行了全面描述.然后，介绍了相关研究常用的验证方法，包括下游任务及数据集.进一步，深入探讨了图神经ODE在多个实用领域上的应用.最后，对图神经ODE面临的挑战和未来发展趋势进行了总结和展望.

• 图终身学习：综述

  刘壮,董子宸,董宜琳,尚家名,张帆,陈雨然,楼佩妍,孙欣然,王昱,赵军,WayneLin,

  图终身学习（lifelonggraphlearning，LGL）是一个新兴领域，旨在实现对图结构数据的持续学习，以解决现有任务上的灾难性遗忘问题，并使得顺序更新的模型能够适应新出现的图任务.尽管LGL展现出良好的学习能力，但如何持续提高其性能仍然是一个至关重要的问题.为填补现有研究对这一方面的空白，对最近在LGL领域的研究进行了全面调查和总结.首先，重新分类了LGL的现有方法，重点关注克服灾难性遗忘的方法.随后，系统地分析了这些方法的优缺点，并探讨了实现持续性能提升的潜在解决方案.该研究着重于如何在持续学习的过程中避免对旧任务的遗忘，同时快速适应新任务的挑战.最后，还就LGL的未来发展方向进行了讨论，涵盖了其在应用领域、开放性问题等方面的潜在影响，并具体分析了这些方向对持续性能改进的潜在影响.这些讨论将有助于指导未来LGL研究的方向，推动这一领域的进一步发展与应用.

• 面向SIMD指令集的SM4算法比特切片优化

  王闯,丁滟,黄辰林,宋连涛,

  SM4算法是中国自主设计的商用分组密码算法，其加解密计算性能成为影响信息系统数据机密性保障的重要因素之一.现有SM4算法优化主要面向硬件设计和软件查表等方向展开研究，分别存在依赖特定硬件环境、效率低下且易遭受侧信道攻击等问题.比特切片技术通过对输入数据重组实现了并行化高效分组密码处理，可以抵御针对缓存的侧信道攻击.然而现有切片分组密码研究对硬件平台相关性强、处理器架构支持单一，并且并行化处理流水启动较慢，面向小规模数据的加解密操作难以充分发挥单指令多数据（singleinstructionmultipledata，SIMD）等先进指令集的优势.针对上述问题，首先提出了一种跨平台的通用切片分组密码算法模型，支持面向不同的处理器指令字长提供一致化的通用数据切片方法.在此基础上，提出了一种面向SIMD指令集的细粒度切片并行处理SM4优化算法，通过细粒度明文切片重组与线性处理优化有效缩短算法启动时间.实验结果表明，相比通用SM4算法，优化的SM4比特切片算法加密速率最高可达438.0MBps，加密每字节所需的时钟周期最快高达7.0CPB（cycle/B），加密性能平均提升80.4%~430.3%.

• 一种面向联盟链Hyperledger Fabric的并发冲突事务优化方法

  吴海博,刘辉,孙毅,李俊,

  随着区块链技术应用的普及，联盟链HyperledgerFabric（简称Fabric）已成为知名区块链开源平台，并得到广泛关注.然而Fabric仍受困于并发事务间冲突问题，冲突发生时会引发大量无效交易上链，导致吞吐量下降，阻碍其发展.对于该问题，现有面向块内冲突的方案缺乏高效的冲突检测和避免方法，同时现有研究往往忽略区块间冲突对吞吐量的不利影响.提出了一种Fabric的优化方案Fabric-HT（fabricwithhighthroughput），从区块内和区块间2方面入手，有效降低事务间并发冲突和提高系统吞吐量.针对区块内事务冲突，提出了一种事务调度机制，根据块内冲突事务集定义了一种高效数据结构——依赖关系链，识别具有“危险结构”的事务并提前中止，合理调度事务和消除冲突；针对区块间事务冲突，将冲突事务检测提前至排序节点完成，建立以“推送-匹配”为核心的冲突事务早期避免机制.在多场景下开展大量实验，结果表明Fabric-HT在吞吐量、事务中止率、事务平均执行时间、无效事务空间占用率等方面均优于对比方案.Fabric-HT吞吐量最高可达Fabric的9.51倍，是最新优化方案FabricSharp的1.18倍；空间利用率上相比FabricSharp提升了14%.此外，Fabric-HT也表现出较好的鲁棒性和抗攻击能力.