Learnability of Competitive Threshold Models

Yifan Wang, Guangmo TongIJCAI 2022 · DOI

TL;DR

This paper tackles the challenge of learning how social contagions spread through competitive threshold models. They propose a novel approach by simulating these complex diffusion processes using artificial neural networks, proving their model is PAC-learnable and developing an efficient learning algorithm. This work offers a theoretically grounded and practically effective method for understanding and predicting social influence.

What Problem Does This Paper Address?

Understanding how information, behaviors, or trends spread through social networks (social contagions) is crucial for applications like viral marketing and misinformation detection. The "competitive threshold model" is a popular framework for modeling this, where a node adopts a behavior if the total influence from its active neighbors exceeds a certain threshold, and among competing influences, the strongest one wins. However, a fundamental question has been: how well can we learn these models from data? Specifically, can we theoretically guarantee that we can learn these models and develop efficient algorithms to do so, especially when dealing with multiple simultaneous cascades? This paper aims to bridge this gap by providing a theoretical framework for the learnability of these models and demonstrating a practical learning method.

Methods

The core innovation lies in simulating the competitive threshold model using artificial neural networks. Instead of treating the diffusion process as a black box, the authors design neural networks whose layer structures explicitly mimic the steps of the diffusion process.

  • Model Design: They propose a specific neural network architecture that can simulate the one-step diffusion process of the CLT model. This involves two main phases:
  • Phase 1 (Influence Summation): This phase uses layers with piecewise polynomial activation functions to calculate the influence summation from active neighbors for each cascade at each node.
  • Phase 2 (Pairwise Comparison & Status Recovery): This phase employs a hierarchy of layers to compare the influence summations from different cascades, identify the winning cascade, and recover the node's final status. This is achieved by cleverly encoding cascade identities into the network's activations, allowing for both comparison and retrieval of the winning cascade's index.
  • PAC Learnability: Based on this neural network simulation, they prove that the competitive threshold model is PAC (Probably Approximately Correct) learnable. This means that with a sufficient number of training samples, the learning algorithm can produce a model that is likely to be close to the true model.
  • Efficient Learning Algorithm: They design an efficient empirical risk minimization (ERM) algorithm. This algorithm leverages the neural network structure and the properties of piecewise linear functions to find the model parameters through linear programming, ensuring a provable sample complexity.

Datasets

The paper uses synthetic and real-world datasets for evaluation:

  • Synthetic Graphs: Kronecker and power-law graph structures are used. These are standard choices for simulating network properties.
  • Real Graph: The "Higgs" graph, derived from monitoring message spreading related to the discovery of a new particle, is used. This provides a more realistic network structure.

The authors generate samples by simulating the diffusion process on these graphs for a given number of cascades and initial seed nodes. They do not introduce new benchmark datasets but rather use existing graph structures to test their method.

Key Insights and Ideas

  • Neural Networks as Explicit Simulators: The most significant insight is the idea of designing neural networks that explicitly simulate the steps of a diffusion model, rather than just learning a black-box mapping. This allows for theoretical analysis of learnability.
  • Encoding Cascade Identity: A clever trick is used to encode cascade identity into the neural network's activations. This is crucial for the pairwise comparison phase, as it allows the network to not only determine which cascade has the highest influence but also to identify which cascade it is, which is necessary for subsequent steps.
  • PAC Learnability of Complex Models: Proving PAC learnability for competitive threshold models, especially with multiple cascades, is a substantial theoretical contribution. It provides a formal guarantee for the learning process.
  • Explainability through Simulation: The explicit simulation approach offers a degree of explainability. The intermediate activations in the network can be interpreted as representing the influence summations and cascade identities at different stages of the diffusion process.

Key Results

  • Superior Performance: The proposed method significantly outperforms off-the-shelf learning methods (Logistic Regression, SVM, MLP) in terms of F1 score, precision, and accuracy across various graph structures and numbers of cascades. For instance, on the Higgs dataset with 100 training samples, their method achieves near-perfect accuracy (e.g., 0.999) compared to MLP's 0.939.
  • Data Efficiency: The paper highlights that their method achieves good performance without requiring an excessive number of data points, suggesting it is data-efficient.
  • Robustness: The results are statistically robust, with small standard deviations across multiple runs.
  • Explainability: The authors note that the hidden features in their neural network model align with the node status during the diffusion process, making the model more transparent than typical surrogate modeling approaches.

Limitations and Future Work

  • Limitations:
    • The current work focuses on the competitive linear threshold model. The authors acknowledge that extending this approach to other models like the independent cascade model or voter model remains an open question.
  • The theoretical analysis relies on assumptions about finite precision for model parameters, which is a standard assumption in computational learning theory but might not perfectly reflect all real-world scenarios.
  • Future Work:
    • Investigating how to explicitly simulate other classic diffusion models using neural networks.
  • Exploring advanced representation techniques that might achieve even better learning performance with sufficient samples.
  • Further research into the explainability aspects of their neural network simulation approach.

Summary updated

BibTeX
@inproceedings{wang2022learnability,
  author = {Yifan Wang and Guangmo Tong},
  title = {{Learnability of Competitive Threshold Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/553},
}
Figure