Graphs are universal structures consisting of nodes and links. They have a wide range of applications in various domains such as social networks, biology, and recommender systems. Graph prediction problems involve predicting outcomes of nodes, links, or entire graphs. While these problems have been extensively studied, graph inverse problems, which involve backtracking graph inputs to achieve specific graph outputs, are less explored and represent open research areas. Graph inverse problems have significant applications, including graph source localization and network influence maximization. For instance, graph source localization identifies information sources in a graph that result in current information diffusion patterns, and it can be viewed as the reverse process of graph diffusion.

An Invertible Graph Diffusion Neural Network for Source Localization

Junxiang Wang, Junji Jiang, and Liang Zhao. An Invertible Graph Diffusion Neural Network for Source Localization. 31th International World Wide Web Conference (WWW 2022), (acceptance rate: 17.7%), Lyon, FR, Apr 2022. paper code slides

In this paper, we establish a generic framework of invertible graph diffusion models for source localization on graphs, namely Invertible Validity-aware Graph Diffusion (IVGD). 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.

Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems

Chen Ling, Junji Jiang, Junxiang Wang and Liang Zhao. Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems. in Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2022), research track (acceptance rate: 15.0%), Washington D.C, USA, Aug 2022. paper code

In this paper, we present a generic framework: Source Localization Variational AutoEncoder (SL-VAE) for locating the diffusion sources under arbitrary diffusion patterns. Particularly, we propose a probabilistic model that leverages the forward diffusion estimation model along with deep generative models to approximate the diffusion source distribution for quantifying the uncertainty. SL-VAE further utilizes prior knowledge of the source-observation pairs to characterize the complex patterns of diffusion sources by a learned generative prior. Lastly, a unified objective that integrates the forward diffusion estimation model is derived to enforce the model to generalize under arbitrary diffusion patterns.

Deep Graph Representation Learning and Optimization for Influence Maximization

Chen Ling, Junji Jiang, Junxiang Wang, My Thai, Lukas Xue, James Song, Meikang Qiu, and Liang Zhao. Deep Graph Representation Learning and Optimization for Influence Maximization. In proceedings of the International Conference on Machine Learning (ICML 2023), (acceptance rate: 27.9%), Honolulu, Hawaii, USA, July 2023. paper code

In this paper, we design a novel framework DeepIM to generatively characterize the latent representation of seed sets for the influence maximization problem, and we propose to learn the diversified information diffusion pattern in a data-driven and end-to-end manner. Finally, we design a novel objective function to infer optimal seed sets under flexible node-centrality-based budget constraints.

Datasets for Graph Source Localization

We provide the following benchmark networks for download:

This script provides the simulation of information diffusion using the above networks by five diffusion models: Independent Cascade(IM), Linear Threshold(LT), Susceptible Infectious(SI), Susceptible Infectious Recovered(SIR) and Susceptible Infectious Susceptible(SIS). It can be used for graph source localization problems.

Please cite our paper if you use our datasets in your paper:

@inproceedings{wang2022invertible, title={An invertible graph diffusion neural network for source localization},

author={Wang, Junxiang and Jiang, Junji and Zhao, Liang},

booktitle={Proceedings of the ACM Web Conference 2022},

pages={1058–1069},

year={2022} }

@inproceedings{ling2022source,

title={Source localization of graph diffusion via variational autoencoders for graph inverse problems},

author={Ling, Chen and Jiang, Junji and Wang, Junxiang and Liang, Zhao},

booktitle={Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining},

pages={1010–1020},

year={2022} }

Python Library for Graph Source Localization

A new Python library GraphSL is developed to support the research of the graph source localization problem. The documentation is available here. Feel free to contact me if you have any questions.