基于区间边界传播的DeepWalk可验证鲁棒性OA

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%.