NetRL: Task-Aware Network Denoising via Deep Reinforcement Learning

Network data is mostly hard to obtain and error-prone. However, most existing works assume that the studied network represents a perfect and complete picture of topological structure; nevertheless, it is rarely the case in real-world situations. Such studies, performing downstream applications (e.g., vertex classification, link prediction, etc.) directly on original networks, will suffer greatly due to the noise and deteriorate the application performance. In this paper, we propose NetRL, a novel method for network denoising, that works by creating missing edges and removing incorrect edges from a noisy network, thereby improving its quality and representative power. In particular, NetRL turns the problem of network denoising into edge sequences generation, which can be formulated as a Markov Decision Process. By doing this, NetRL takes the complex long-term dependency between edge creations into consideration, i.e., the existence of an edge depends on which edges have been generated so far. It further takes advantage of downstream task to guide the network denoising process, by providing a deep reinforcement learning framework to conduct direct optimization on this task-specific objective. As a result, NetRL ensures that the denoised network not only satisfies the topological property of the original network, but also improves the performance of the downstream application. Experimental results on real-world networks show that, comparing with several baseline methods, NetRL can denoise networks effectively with better performance for vertex classification. Meanwhile, NetRL can better preserve original network's properties (e.g., degree distribution and clustering coefficient. Our implementation is available at: https://github.com/galina0217/NetRL.