| 俞山青,方虚,王金焕,彭松涛.基于区间边界传播的DeepWalk可验证鲁棒性[J].高技术通讯(中文),2026,36(6):576~585 |
| 基于区间边界传播的DeepWalk可验证鲁棒性 |
| Certified robustness of DeepWalk based on interval bound propagation |
| |
| DOI：10. 3772 / j. issn. 1002 - 0470. 2026. 06. 003 |
| 中文关键词: DeepWalk； 链路预测； 区间边界传播法； 可验证鲁棒性 |
| 英文关键词: DeepWalk, link prediction, interval bound propagation, certified robustness |
| 基金项目: |
| 作者 | 单位 | | 俞山青 | （浙江工业大学信息工程学院杭州 310023） | | 方虚 | | | 王金焕 | | | 彭松涛 | |
|
| 摘要点击次数: 76 |
| 全文下载次数: 72 |
| 中文摘要: |
| 基于DeepWalk的图嵌入算法的非线性和复杂性使其可验证鲁棒性的研究变得十分困难。因此，本文提出了一种基于区间边界传播 (interval bound propagation，IBP)的方法，在节点度值攻击下验证DeepWalk在链路预测任务上的鲁棒性。本文将DeepWalk等效于对目标矩阵的奇异值分解任务，根据IBP的思想，首先将原始度值矩阵的扰动范围传递到目标矩阵，再传递到点的嵌入向量，获取其扰动区间作为约束条件，最终通过求解优化问题得到鲁棒验证结果。最后，利用本文提出的方法，对不同图网络规模、图网络密度和嵌入向量维数对可验证鲁棒节点对占比的影响进行了实验。结果显示平均鲁棒验证率最高可达63.63%。 |
| 英文摘要: |
| The highly nonlinear and complex nature of graph embedding algorithms based on DeepWalk makes it challenging to certify their robustness. Therefore, this paper proposes a method based on interval boundary propagation (IBP) to certify the robustness of DeepWalk against degree value attacks in link prediction tasks. This paper equates DeepWalk to the task of singular value decomposition of the target matrix. Following the idea of IBP, it first propagates the perturbation range from the original degree value matrix to the target matrix, then to the node’s embedding vectors, obtaining their perturbation intervals as constraints. Finally, it solves an optimization problem to obtain the robust certification results. Furthermore, the impacts of different graph scales, graph densities, and embedding dimensions on the proportion of certifiably robust node pairs are experimentally investigated. The experimental results demonstrate that the average robust certification rate can reach up to 63.63%. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|
