Reconstructing Diffusion Networks from Incomplete Data

Hao Huang, Keqi Han, Beicheng Xu, Ting GanIJCAI 2022 · DOI

TL;DR

This paper introduces LIDO, a novel algorithm for reconstructing diffusion network topologies when only partial infection status data is available. LIDO iteratively infers the network structure, estimates infection probabilities, and imputes missing data, outperforming existing methods in accuracy, especially under high data incompleteness.

What Problem Does This Paper Address?

Understanding how information, diseases, or trends spread through networks is crucial, and this is often modeled by diffusion networks. Reconstructing the topology (who influences whom) of these networks is a key challenge. Traditional methods typically require complete information about when each node got infected (cascade data) or at least the final infection status of all nodes. However, in real-world scenarios like epidemic tracking or viral marketing, obtaining such complete data is often infeasible due to cost, logistical challenges, or simply missing observations. This paper tackles the problem of reconstructing diffusion network topologies when we only have partial observations of the final infection statuses of nodes.

Methods

The core of the paper is the LIDO (Learning from Incomplete Diffusion Observations) algorithm, which operates iteratively with three main steps:

  1. Topology Inference: LIDO first infers the network topology. Crucially, it doesn't rely on complete data. Instead, it uses the observed infection statuses and estimated values for the unobserved statuses. This step leverages existing methods like TENDS, which are designed for complete data, by providing them with imputed data.
  2. Probability Learning and Imputation Distribution: In this step, LIDO learns the optimal infection propagation probabilities between connected nodes based on the current inferred topology. Simultaneously, it learns the probability distributions for the unobserved infection statuses. This is done by maximizing the likelihood of the observed data, treating unobserved statuses as variables to be estimated.
  3. Imputation Update: The learned probability distributions are then used to sample new estimates for the unobserved infection statuses. These updated estimates are fed back into the topology inference step for the next iteration.

This iterative process continues until the inferred topology stabilizes. The algorithm is designed to handle the Independent Cascade (IC) model but can be extended to others.

Datasets

The paper evaluates LIDO on both synthetic and real-world datasets:

  • Synthetic Networks: LFR benchmark graphs were used to generate networks with varying sizes and average degrees.
  • Real-World Networks:
    • NetSci: A co-authorship network.
  • DUNF: A microblogging network.
  • MemeTracker: A dataset derived from news articles and blogs, where hyperlinks were used to construct a network and trace information propagation events. For this dataset, the authors generated a network of 1000 media sites and blogs with 4000 directed hyperlinks and simulated diffusion processes.

For evaluation, infection data was simulated on these networks. A significant portion of this simulated data was then randomly removed to create the "unobserved data" scenario.

Key Insights and Ideas

  • Iterative Imputation is Key: The core idea is that you can improve topology inference by iteratively guessing missing data, learning from those guesses, and then refining the guesses. This creates a virtuous cycle.
  • Handling Incompleteness is Crucial: Existing methods often assume complete data. LIDO directly addresses the practical reality of missing observations, showing significant gains in accuracy when data is incomplete.
  • LIDO's Robustness: The algorithm demonstrates robustness to network size and average degree, maintaining good accuracy where other methods might falter.
  • Trade-off Between Accuracy and Speed: While LIDO achieves higher accuracy, it generally takes longer than some benchmark methods, especially those that assume complete data and don't iterate.

Key Results

  • Superior Accuracy: LIDO consistently outperforms benchmark algorithms (MulTree, TENDS, POIND) in terms of F-score (a measure of accuracy) across various scenarios, particularly when the proportion of unobserved data is high.
  • Performance Gains with More Data: Increasing the number of diffusion processes (β) generally leads to better accuracy for all algorithms, with LIDO showing the most significant gains.
  • Convergence: LIDO exhibits fast convergence, with accuracy improving rapidly in the initial iterations.
  • Real-World Efficacy: The algorithm shows promising results on real-world datasets, demonstrating its practical applicability.

Limitations and Future Work

  • Running Time: While LIDO offers superior accuracy, its iterative nature leads to longer running times compared to some non-iterative methods, especially when dealing with a large amount of unobserved data.
  • Model Assumption: The current work focuses on the Independent Cascade (IC) model. Extending LIDO to other propagation models (like the Linear Threshold model) is a potential future direction.
  • Parameter Tuning: The paper mentions setting parameters like the number of sampling rounds (m) and the stopping condition for updating probabilities. Further exploration into optimal parameter tuning could be beneficial.

Summary updated

BibTeX
@inproceedings{huang2022reconstructing,
  author = {Hao Huang and Keqi Han and Beicheng Xu and Ting Gan},
  title = {{Reconstructing Diffusion Networks from Incomplete Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/428},
}
Figure