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

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

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