Structural Predictability Regulation for Graph data
Guannan Ming, Tao Wu, Xiaofeng Liao, Xingping Xian · 2019 3rd International Conference on Electronic Information Technology and Computer Engineering (EITCE) · 2019
Graphs, also called "networks", have been proved to be an ideal paradigm for data representation in various domains, and structure prediction on graphs refers to estimating the potential relationship between objects from observed structures, being fundamental in many data analysis applications such as network alignment, network reconstruction and link prediction. Accordingly, to the users generating or utilizing the graph data, it is necessary to regulate the structural predictability of graphs against inference attack to protect the sensitive information about themselves or for error information reduction to mining more useful data about others respectively. In contrast to the existing works about graph structure perturbation for node ranking, information diffusion, etc., the structural predictability regulation problem, i.e., reducing or enhancing the accuracy of potential relationships prediction in graphs, hasn’t been extensively studied. This paper presents an active learning algorithm which selects the most representative links, and thus the structural predictability of graphs would be regulated via perturbing them. Specifically, with the assumption that graphs generally consist of regular and irregular components, in which the substructure with regular links has more equivalent paths supplied for the random walk processes, a random walk based link importance measuring algorithm is proposed to identify representative links. Extensive experiments on disparate real- world data sets demonstrate the effectiveness of the proposed graph structural predictability regulation method. In a word, the link importance estimation algorithm can capture the role of links accurately in terms of graph organization, and the structural predictability of graphs can be improved via irregular links based perturbation and be deteriorated by regular links based perturbation.