Look Before You Leap: Confirming Edge Signs in Random Walk with Restart for Accurate Personalized Node Ranking in Signed Networks

Abstract

Given a seed node in a network, the goal of personalized node ranking (PNR) is to rank the remaining nodes in an order relevant to the seed node by considering the structure of the network. With the emergence of signed networks with both positive and negative edges between nodes, there have been attempts to improve the accuracy of PNR by utilizing these edge signs together. The recently-proposed PNR methods for signed networks employed the signed random walk (SRW) models that consider edge signs based on the balance theory. However, the methods assume that the balance theory is always hold; thus, they have an inherent limitation of making the predictions of the relationships between nodes inaccurate. To address this limitation, we propose a new random-walk-based PNR approach, named as SCAN, with Sign verifiCAtioN. To do this, we design a strategy to verify the edge signs between the nodes predicted by the existing SRW models. Based on this strategy, we propose a SRW model that only allows the scores for correctly-predicted signs to be propagated to other nodes. Via extensive experiments using three real-world datasets, we validate the effectiveness of SCAN. Specifically, we demonstrate that SCAN significantly improves the accuracy of SRWR, the best performer among the existing PNR methods, by up to 13%/30% for the top-k/bottom-k node ranking tasks, respectively.