An Invertible Graph Diffusion Neural Network for Source Localization
An Invertible Graph Diffusion Neural Network for Source Localization
复制标题
DOI：
10.1145/3485447.3512155
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Junxiang Wang;Junji Jiang;Liang Zhao
中科院分区：
文献类型：
--
作者：
Junxiang Wang;Junji Jiang;Liang Zhao
在现实世界中，对图扩散现象（如错误信息传播）的来源进行定位是一项重要但极具挑战性的任务。现有的源定位模型通常严重依赖于手工制作的规则，并且只针对特定领域的应用程序进行定制。不幸的是，许多应用程序的图扩散过程的很大一部分对人类来说仍然是未知的，因此拥有表达模型来自动学习这些底层规则是很重要的。近年来，用于自动学习底层图扩散的表达模型如图神经网络（gnn）的研究兴起。然而，源定位是图扩散的逆问题，这是图中一个典型的逆问题，众所周知，它是病态的，因为它可以有多个解，因此不同于传统的（半）监督学习设置。本文旨在建立一个用于图源定位的可逆图扩散模型的通用框架，即可逆有效性感知图扩散（IVGD），以解决以下主要挑战：1)难以利用图扩散模型中的知识以端到端方式对其逆过程建模；2)难以确保推断源的有效性；3)源推理的效率和可扩展性。具体而言，首先，为了反向推断图扩散的来源，我们提出了一个图残差场景，使现有的图扩散模型具有可逆的理论保证；其次，我们开发了一种新的误差补偿机制，该机制可以学习抵消推断源的误差。最后，为了保证推断源的有效性，设计了一组新的有效性感知层，通过展开优化技术对约束进行灵活编码，将推断源投影到可行区域。提出了一种线性化技术来提高所提层的效率。从理论上证明了该算法的收敛性。在9个真实数据集上的广泛实验表明，我们提出的IVGD显着优于最先进的比较方法。我们已经在https://github.com/xianggebenben/IVGD上发布了我们的代码。
Localizing the source of graph diffusion phenomena, such as misinformation propagation, is an important yet extremely challenging task in the real world. Existing source localization models typically are heavily dependent on the hand-crafted rules and only tailored for certain domain-specific applications. Unfortunately, a large portion of the graph diffusion process for many applications is still unknown to human beings so it is important to have expressive models for learning such underlying rules automatically. Recently, there is a surge of research body on expressive models such as Graph Neural Networks (GNNs) for automatically learning the underlying graph diffusion. However, source localization is instead the inverse of graph diffusion, which is a typical inverse problem in graphs that is well-known to be ill-posed because there can be multiple solutions and hence different from the traditional (semi-)supervised learning settings. This paper aims to establish a generic framework of invertible graph diffusion models for source localization on graphs, namely Invertible Validity-aware Graph Diffusion (IVGD), to handle major challenges including 1) Difficulty to leverage knowledge in graph diffusion models for modeling their inverse processes in an end-to-end fashion, 2) Difficulty to ensure the validity of the inferred sources, and 3) Efficiency and scalability in source inference. Specifically, first, to inversely infer sources of graph diffusion, we propose a graph residual scenario to make existing graph diffusion models invertible with theoretical guarantees; second, we develop a novel error compensation mechanism that learns to offset the errors of the inferred sources. Finally, to ensure the validity of the inferred sources, a new set of validity-aware layers have been devised to project inferred sources to feasible regions by flexibly encoding constraints with unrolled optimization techniques. A linearization technique is proposed to strengthen the efficiency of our proposed layers. The convergence of the proposed IVGD is proven theoretically. Extensive experiments on nine real-world datasets demonstrate that our proposed IVGD outperforms state-of-the-art comparison methods significantly. We have released our code at https://github.com/xianggebenben/IVGD.