FPGN: follower prediction framework for infectious disease prevention

Jianke Yu, Xianhang Zhang, Hanchen Wang, Xiaoyang Wang, Wenjie Zhang, Ying Zhang

TL;DR

Researchers have introduced FPGN (Follower Prediction Graph Network), a specialized framework designed to identify "followers"—individuals who visit specific locations shortly after an infected person. By integrating temporal graph memory with structural density analysis, FPGN significantly outperforms traditional graph neural networks in predicting high-risk contacts, offering a powerful tool for pandemic management.

What Problem Does This Paper Address?

Effective pandemic management relies heavily on contact tracing. However, traditional methods often struggle with "follower prediction": identifying visitors who may have been exposed to a pathogen because they frequented a specific venue (like a cafe or gym) within a narrow time window after an infected individual.

From a data science perspective, this is a temporal bipartite graph problem. The graph contains two types of nodes—Visitors and Locations—with edges representing visits at specific timestamps.

Illustration of the follower prediction problem in a temporal bipartite graph.

The challenge is twofold:

  1. Structural: In a bipartite graph, there are no direct edges between visitors. Relationships must be inferred through shared locations.
  2. Temporal: "Following" behavior is strictly time-bound. If a person visits a cafe 10 minutes after an infected individual, they are a high-risk follower; if they visit three hours later, the risk is negligible.

Existing models often ignore the temporal sequence or fail to utilize the "closeness" of these time intervals effectively.

Methods

FPGN introduces a multi-stage pipeline to bridge these gaps, divided into an Information Recording Module and a Prediction Module.

The FPGN framework architecture, highlighting the Information Recording and Prediction modules.

Structural Feature Extraction ($(\alpha, \beta)$-core)

Instead of relying solely on node IDs, the model employs $(\alpha, \beta)$-core decomposition to identify dense subgraphs. This technique identifies "clusters" of visitors and locations, helping the model understand which nodes belong to highly active communities, which are statistically more likely to contain followers.

Time Interval Statistics

The model calculates the frequency, average time gap, and variance of intervals between visitors. This "closeness" data is integrated into the feature set, allowing the model to distinguish between coincidental visits and high-risk following behavior.

Optimized Memory Update

Inspired by Temporal Graph Networks (TGN), FPGN uses Gated Recurrent Units (GRUs) to maintain a "memory" for each node that evolves over time. Crucially, the authors modified the standard TGN architecture to update all vertex memories before the prediction phase, ensuring the model utilizes the most recent state for every visitor.

GAT-based Prediction

A Graph Attention Network (GAT) serves as the final prediction module. It uses a multi-head attention mechanism to weigh which previous visits are most relevant to the current prediction, effectively mapping different types of vertices (visitors vs. locations) into a shared space for relationship inference.

Datasets and Evaluation

Since no dedicated "follower prediction" dataset existed, the authors adapted two famous temporal bipartite benchmarks:

  • Wikipedia: 8,227 users and 1,000 pages (locations), representing users editing the same pages in sequence.
  • Reddit: 10,000 users and 984 subreddits (locations), representing users engaging in reply chains.

Ground truth followers were defined based on a specific time window relative to the total timespan of the dataset.

Key Results

FPGN was tested against six general GNN baselines (such as GCN, GAT, and SAGE) and two state-of-the-art temporal models (JODIE and NeurTW).

  • Superior Accuracy: On the Wikipedia dataset, FPGN achieved an Average Precision (AP) of 0.4620 and an AUC of 0.6250, outperforming the next best model (GNN-FiLM) by a significant margin.
  • Reddit Performance: The gains were even more pronounced on Reddit, where FPGN reached an AP of 0.5457 and an AUC of 0.7305.
  • Efficiency: While complex temporal models like JODIE and NeurTW failed to produce results on the Reddit dataset within 48 hours, FPGN remained computationally viable.
  • Ablation Success: Removing the time interval statistics or the $(\alpha, \beta)$-core features led to a measurable drop in performance, proving that both structural density and temporal precision are necessary for this task.

Limitations and Future Work

While FPGN represents a significant step forward, several areas for improvement remain:

  • Feature Incorporation: The current model is designed for "featureless" graphs. Incorporating node features, such as the type of location (e.g., indoor vs. outdoor), could further refine risk assessments.
  • Scalability: Although faster than some competitors, the $(\alpha, \beta)$-core computation and GRU memory updates still add overhead that could be optimized for larger datasets.
  • Privacy: Deploying such a system in the real world would require rigorous privacy-preserving measures, such as differential privacy, to protect individual identities while maintaining public health utility.

Summary updated

Abstract

In recent years, how to prevent the widespread transmission of infectious diseases in communities has been a research hot spot. Tracing close contact with infected individuals is one of the most severe problems. In this work, we present a model called Follower Prediction Graph Network (FPGN) to identify high-risk visitors, which is known as follower prediction. The model is designed to identify visitors who may be infected with a disease by tracking their activities at the exact location of infected visitors. FPGN is inspired by the state-of-the-art temporal graph edge prediction algorithm TGN and draws on the shortcomings of existing algorithms. It utilizes graph structure information based on (\(\alpha \), \(\beta \))-core, time interval statistics by using the statistics of timestamp information, and a GAT-based prediction module to achieve high accuracy in follower prediction. Extensive experiments are conducted on two real datasets, demonstrating the progress of FPGN. The experimental results show that FPGN can achieve the highest results compared with other SOTA baselines. Its AP scores are higher than 0.46, and its AUC scores are higher than 0.62.
BibTeX
@article{yu2023fpgn,
  author = {Jianke Yu and Xianhang Zhang and Hanchen Wang and Xiaoyang Wang and Wenjie Zhang and Ying Zhang},
  title = {{FPGN: follower prediction framework for infectious disease prevention}},
  journal = {WWW},
  year = {2023},
  doi = {10.1007/s11280-023-01205-8},
}
Figure