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.
The challenge is twofold:
- Structural: In a bipartite graph, there are no direct edges between visitors. Relationships must be inferred through shared locations.
- 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.
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