FPGN: follower prediction framework for infectious disease prevention

To be able to help the model extract information about the graph structure, we compute (\(\alpha \), \(\beta \))-core for each vertex. More specifically, we compute whether each vertex exists with a certain set of subgraphs satisfying (\(\alpha \), \(\beta \))-core and treat that graph structure information as a part of the vertex features. Thanks to the graph structure information, FPGN can produce more precise results. Given an upper threshold and a lower threshold for \(\alpha \) and \(\beta \), respectively: \(\alpha ^{-}_{\tau } \le \alpha \le \alpha ^{+}_{\tau }\), and \(\beta ^{-}_{\tau } \le \beta \le \beta ^{+}_{\tau }\), and then determine whether each vertex is within these (\(\alpha \), \(\beta \))-core subgraphs to obtain the graph structure characteristic matrix \({\textbf {R}}_s \in \mathbb {R}^{(|U| + |V|) \times d_s)}\), where \(d_s = (\alpha ^{+} - \alpha ^{-} + 1) \times (\beta ^{+} - \beta ^{-} + 1)\) equals the number of (\(\alpha \), \(\beta \))-core queried. Each vertex’s graph structure feature \({\textbf {r}}_s \in \{0, 1\}^{d_s}\) is a part of \({\textbf {R}}_s\). If the value of a dimension of the feature is 0, it means that the vertex does not exist in the (\(\alpha \), \(\beta \))-core corresponding to that dimension, and vice versa.

In the end, the characteristic matrix of the vertices used by FPGN is:where || is concatenation operation. Generating the vertex features by using the above way can provide rich graph structure information for FPGN while avoiding increasing its time complexity. For convenience in the description, we represent \({\textbf {R}}(u)\) as a characterization of u.

It is crucial for the follower prediction problem to get information on the time interval between the follower’s journey to a certain location and that of the leader. This information can help the model discover the following behavior and solve the follower prediction problem. Firstly, the number of times the same follower and leader travel to the same location sequentially can reveal the correlation between them. This information can be obtained statistically using the following formula:where \([\cdot ]\) is Iverson bracket. It is a useful tool for mapping any statement to a function of the free variables in that statement. This bracket serves as a kind of truth-value indicator to assign a value of 1 to any true statement and 0 to any false statement:And \({\textbf {S}}_{n, (u, u')}\) denotes the number of locations where the follower \(u'\) arrives to follow the leader u. \({\textbf {S}}_n\) can record the frequency of follow-up between two visitors very well, which can play a significant role in the following prediction.

Then we count the closeness of the following actions for each follower, i.e., the time interval between two visitors arriving at the same location. The smaller the time interval, the closer that follower is to that leader. However, the follower can follow the leader in multiple locations. To better inform the model, we calculated the average and variance of their time intervals. Given a leader u, a follower \(u'\), We can get the average statistics and variance statistics of \(\Delta \):Using this statistical information, it is possible to help the model gain a better understanding of the relationship between visitors. This information can be used to build features that highlight the relationship between leaders and followers:where Norm is the normalization operation. The features \({\textbf {S}}\) obtained will help the model optimize the parameters during the training process. The details of the training process will be explained in Section 3.5.

To better learn the temporal graph information, FPGN mines the vertex memory with temporal information. Given a visitor record triplet (u, v, t), which means that the visitor u arrives at the location v at timestamp t with message \({\textbf {M}}_{(u,v)} = {\textbf {R}}(u) || {\textbf {R}}(v)\). The memory of time t for u is defined as \({\textbf {F}}_u(t)\), and \({\textbf {F}}_u(0) = \{0\}^{1 \times d}\) where d is the dimension of the memory. The memory of u and v is calculated separately. For the sake of description, we only describe the process of updating u’s memory.

To better explore the historical activity message of vertices, all activity timestamps \(T_u(t)\) of u earlier than time t will be extracted and synthesized into vectors \({\textbf {T}}_u(t) \in \mathbb {R}^{1 \times |T_u(t)|}\). And memories \({\textbf {M}}_u(t)\) of u at those times are also involved in the vertex memory update task. FPGN first encodes the activity of u:where \(\cos (\cdot )\) is the cosine function; \({\textbf {W}}_t\) is a matrix of trainable parameters and \({\textbf {b}}_t\) is a trainable parameter; \(t_u\) is the timestamp of the last activity of u; \({\textbf {I}}_{(t,u)} \in \mathbb {R}^{1 \times |T_u(t)|}\) is a vector whose elements are all 1 with dimensions \(1 \times |T_u(t)|\). It should be noted that \(t_u\) is initialized with a value of 0.

In order to extract information about the past activities of u, we need to extract all neighbors of u before time t from the adjacency matrix set A. This can be done by defining the set of neighbors of u at time t as follows:where \({\textbf {A}}^{t}\) is the adjacency matrix at time t, and \({\textbf {A}}_{u, v}^{t} = 1\) if u and v connected with each other at time t. After obtaining these neighboring vertices, we can then get the message between u and them, these neighbors’ memories at that time, and the past memories of u at all timestamps before t:then, concatenate \({\textbf {X}}_u\), \({\textbf {X}}_{\mathcal {N}_u^t}\) and \({\textbf {M}}_{\mathcal {N}_u^t}\), as well as \({\textbf {X}}_{t, u}\) to obtain the initial memory of u:where \({\textbf {X}}_{t, u}^{init}\) is the initial memory of u at timestamp t.

Because early activity records should not have too much influence on the present, and each vertex memory at every moment contains activity information before that moment, to make FPGN pay more attention to recent activity information and reduce its computational cost, we only keep the latest \(\mathcal {K}\) sets of initial memory \(\bar{{\textbf {X}}}_u^{init}(t)\) in \({\textbf {X}}_u^{init}(t)\).

LSTM is a widely used recurrent neural network architecture that is particularly suited to processing sequential data, such as speech and text [35, 38]. There are many works that handle temporal graphs using LSTM and have achieved good performance [6, 50] nowadays. However, recent research has found that the newer Gated Recurrent Unit (GRU) [10] architecture offers comparable performance to LSTM while being more computationally efficient [5, 5, 51], making it an attractive alternative for processing temporal graph datasets. Therefore, in this work, we chose to use GRU to obtain vertex memories.

To be more precise, during each time step, a GRU unit utilizes the initial memories \(\bar{{\textbf {X}}}_u^{init}(t)\) and the most recent memories of u, denoted as \({\textbf {F}}_{u}(t')\), to compute the reset gate \({\textbf {p}}_{t}\) and update gate \({\textbf {q}}_{t}\) in the following manner:where \(\sigma \) is non-linear activation functions, \({\textbf {W}}_{px}\), \({\textbf {W}}_{pf}\) and \({\textbf {W}}_{qx}\), \({\textbf {W}}_{qf}\) are weight matrices, and \({\textbf {b}}_{p}\), \({\textbf {b}}_{q}\) are bias vectors. The reset gate controls how much of the previous memories should be ignored, while the update gate controls how many new memories should be added to the initial memories. The candidate memory \(\widetilde{{\textbf {F}}}_{u}(t)\) is then computed as follows:where \(\odot \) denotes the element-wise product, \({\textbf {W}}_{x}\) and \({\textbf {W}}_{f}\) are weight matrices and \({\textbf {b}}_f\) is a bias vector. Finally, the new memory of u \({\textbf {F}}_{u}(t)\) is calculated as a linear interpolation between the previous memory and the candidate memory, controlled by the update gate:GRU’s mechanism allows it to process temporal graphs by selectively retaining or discarding information as time passes. This feature enables GRU to store and analyze data over an extended period, making it an effective tool for handling dynamic and evolving datasets. After completing the training of all data through the above method, we can obtain the final vertex memories:where \(\Gamma _{n}\) is the last timestamp of vertex n.

Each round of memory update for each vertex requires tracing the vertices that were previously connected to it. Therefore, after each round of vertex memory update for a triplet (u, v, t), the edges involved in that round of update need to be saved into the adjacency matrix \({\textbf {A}}^t\), that is to say, \({\textbf {A}}^t_{u,v} = 1\).

Additionally, after acquiring \({\textbf {F}}\), utilizing all the connection information for improved follower predictions is imperative. Thus, amalgamating all the adjacency matrices from each time step into a single matrix becomes necessary:

To the best of our knowledge, there is currently no open-source dataset available for predicting followers. To address this gap, we utilized the widely-used temporal bipartite graph datasets named Wikipedia and Reddit [16, 21, 33, 47] to create our own dataset. The statistical details of these two datasets are presented in Table 1.

In the follower prediction problem, we consider all connections to only have the meaning of “visit,” so the dataset we use does not include edge features. We use \(80\%\) of the data in each dataset as the training set and the remaining \(20\%\) as the test set. Additionally, \(20\%\) of the training set is treated as a validation set. It should be noted that in order to ensure that the model does not test visitors who have not seen before, we remove visitors that only appear in the test set.

To generate ground truth, we set a fixed ratio time window. Specifically, assuming the time span of the dataset is \(\Gamma \), two visitors u and \(u'\), and a location v, we consider u and \(u'\) are leader and follower when \(\Delta (u, u', v) \le \Gamma \times 10^{-4}\). The negative samples are generated from samples other than the positive samples, and the number of negative samples is twice that of the positive samples. In the Wikipedia dataset, the links represent users’ edits to Wikipedia pages. The obtained Wikidata dataset can help FPGN predict those who follow other editors in editing Wikipedia pages. Reddit contains numerous user interaction information in numerous posts. The Reddit dataset obtained using the above method allows FPGN to predict followers who engage in reply conversations with specific users.

To the best of our knowledge, there is currently no model specifically optimized for the follower prediction problem. Therefore, we use six widely used GNN models: GCN [19], GAT [42], GE [53], SAGE [15], GNN-FiLM [4] and GIN [49] as baselines, where GE is the general GNN layer adapted from [53]. All of these algorithms have the structure shown in (2), but differ in the way they aggregate and update the information.

In addition, since the edge prediction problem on temporal graphs is similar to the follower prediction problem, we also compare with state-of-the-art algorithms JODIE [20] and NeurTW [16]. JODIE employs two recurrent neural networks to update a visitor’s and a location’s embedding at every interaction. In addition, this model has a novel projection operator that learns to estimate the embedding of the visitor at any time in the future. And to make the method scalable, a t-Batch algorithm is developed that creates time-consistent batches and leads to faster training. NeurTW conduct spatiotemporal-biased random walks to retrieve a set of representative motifs, enabling temporal vertices to be characterized effectively. With a component based on neural ordinary differential equations, the extracted motifs allow for irregularly sampled temporal vertices to be embedded explicitly over multiple different interaction time intervals. To enrich the supervision signals, a harder contrastive pretext task is designed for model optimization. It should be noted that TGN is also a state-of-the-art algorithm for solving edge prediction problems on temporal graphs. However, as explained in Section 1, TGN cannot be directly applied to the follower prediction problem. Therefore, we do not compare TGN in accuracy evaluation experiments. Instead, we analyze the effectiveness of optimizing TGN for the follower prediction problem in ablation experiments and show that TGN does not outperform FPGN on this task.