Reinforcement Learning-based Black-Box Evasion Attacks to Link Prediction in Dynamic Graphs

Graphs are often used to describe complex systems such as social networks, biology, social and economic organizations, communication systems, power grid, etc. These real-world systems often evolve with time and can be modeled as dynamic graphs, where nodes/entities or links/edges are dynamically added or deleted. Links, which represent the interactions between nodes, are of great importance in the analysis of dynamic graphs; and one particular important research problem is called link prediction in dynamic graphs (LPDG). Specifically, given historical graph data of a real-world system, LPDG aims to predict its future graph structure so as to better understand the evolution process. It is precisely that information in future graphs would be valuable in various applications such as online recommendations, studies on disease contagion, organizational studies, etc. Various LPDG methods have been proposed in the past decade. Conventional methods include feature-based methods [15, 39, 7, 20], generative methods [25, 37, 44], and deep neural networks [19, 30, 5]. Recently, graph embedding (GE) methods [24, 28, 12] and graph neural networks (GNNs) [17, 31, 35] have achieved great success in many graph-related tasks (e.g., node classification, link prediction, graph classification, etc.) for static graphs.