高技术通讯2026，Vol.36Issue(6)：576-585,10.DOI:10.3772/j.issn.1002-0470.2026.06.003
基于区间边界传播的DeepWalk可验证鲁棒性
Certified robustness of DeepWalk based on interval bound propagation
摘要
Abstract
The highly nonlinear and complex nature of graph embedding algorithms based on DeepWalk makes it chal-lenging 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 em-bedding 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 em-bedding dimensions on the proportion of certifiably robust node pairs are experimentally investigated.The experi-mental results demonstrate that the average robust certification rate can reach up to 63.63%.关键词
DeepWalk/链路预测/区间边界传播法/可验证鲁棒性Key words
DeepWalk/link prediction/interval bound propagation/certified robustness引用本文复制引用
俞山青,方虚,王金焕,彭松涛..基于区间边界传播的DeepWalk可验证鲁棒性[J].高技术通讯,2026,36(6):576-585,10.基金项目
国家自然科学基金(62103374,U21B2001)和浙江省重点研发计划(2024C01025,2022C01018)资助项目. （62103374,U21B2001）
