Tracing Topic Transitions with Temporal Graph Clusters

Opportunistically, we chose to model local responses to the on-going event ”COVID-19” for a short duration. Thus, tweets were collected from a local community from Aug 19th to Sep 2nd. ”COVID-19” related tweets were identified by matching a set of manually selected hashtags for the corpus. The tweets of interests are pre-processed with Stanford CoreNLP ¹¹1Stanford CoreNLP ver. 3.9.2. to annotate the part-of-speech and named entities. The statistics of the dataset is shown in Table 1.

We treat each day as a timepoint and split the collected dataset based on the timestamp of the tweets. Temporal graphs are constructed using GoW with the nodes being the unique nouns or named entities extracted from tweets of the day. Furthermore, we employ normalized Point-wise Mutual Information (PMI) value as the edge weights between two nodes (1). In Equation (1), the marginal probabilities $p(x)$ and $p(y)$ and the joint probability $p(x,y)$ are computed as the proportions of the occurrence of tokens $x$ and $y$ in a total of $N$ tweets, where $n_{x}$, $n_{y}$, and $n_{xy}$ denote the (joint) frequency of tokens $x$ and $y$. For consistency and computational efficiency, we further normalize the PMI with self-information $h(x,y)$ which sets the boundary of the PMI value to $[-1,1]$ (2).

For the dataset used in this paper, nodes that are closely related to the fetching keywords of the tweets tend to co-occur with every other node, while their neighboring nodes might observe no connections between each other. We refer to this type of nodes as the bridging nodes in this paper. Many common graph clustering methods, such as spectral clustering (?) and highly connected subgraph clustering (?), achieve the grouping from graph cutting. One drawback of applying cutting based algorithm on graphs with bridging nodes is that no obvious local structures can be observed due to the inter-connectivity introduced by these nodes. More precisely, the cluster assignments for the neighboring nodes of a bridging node tend to fail as the graph cannot be cut in an appropriate way. As a result, the graph cutting mechanism tends to cluster each node into individual cluster. Thus, we propose to exclude the bridging nodes from the GoW during the clustering process, and treat them as belonging to each resulting clusters which have at least one edge in between. We locate a bridging node by its clustering coefficient $C_{i}\in[0,1]$ (?). As defined in Equation 3, clustering coefficient measures the embeddedness of a single nodes among its neighbors. A larger $C_{i}$ indicates the neighbors of $i$ tend to be more connected to form a community. In our case, the smaller the $C_{i}$ is, the more likely the node is to serves as bridging node.

• •

  $e_{i}$: number of edges between the neighbors of node $i$

• •

  $k_{i}$ and $k_{j}$: degree of node $i$ and $j$

• •

  $A_{ij}$: the edge weight between nodes $i$ and $j$

• •

  $2m$: sum of all edge weights

• •

  $c_{i}$ and $c_{j}$: communities of nodes $i$ and $j$

• •

  $\delta$: an indicator function, $\delta=1$ if $c_{i}=c_{j}$, $\delta=0$ otherwise

To achieve an optimal clustering, we determine the number of bridging nodes to exclude by incrementally removing the denser node from the graph based on a clustering quality metric. Modularity (?) is a common metric used for measuring community quality in graph theory. Given a partitioning of graph $G$, modularity $Q\in[-1,1]$ computes the difference between actual and expected number of edges within groups (Equation 4). A larger modularity value $Q$ indicates more significant community structure. Algorithm 1 outlines our method for finding optimal clustering. During each iteration, a node with the lowest $C_{i}$ is removed (with its edges) from the graph $G$ and the rest of the subgraph is clustered. The modularity value $Q$ is computed on the subgraph to determine the current clustering quality. The best clustering is achieved at the (first) max $Q$ value.

We adopt the random walk based Markov Clustering (MCL) (?) as our choice of graph clustering algorithms over other common graph cutting based clustering algorithms due to the drawbacks mentioned above. MCL simulates the stochastic flow in a graph which makes it more scalable. Furthermore, unlike other clustering algorithms, the number of clusters does not need to be pre-determined in MCL.

In many stream based data analysis tasks, modeling cluster transitions is the key to identify the evolution of the target of interests. Given a timepoint $t_{i}$, a cluster transition can be defined as ”the change experienced by a cluster that has been discovered at an earlier timepoint” (?). Previously proposed frameworks such as MONIC (?) and MEC (?) define a set of transition types between clusters across consecutive timepoints and use a matching function with a threshold to identify these types. We adopt the basic transition types defined in MONIC and MEC, and further extend them to make the framework more robust for our task. From timepoint $t_{i}$ to $t_{i+1}$, we define pairwise transition types for consecutive timepoints in Table 2 (first 7 types), where $X$ and $Y$ are clusters at timepoints $t_{i}$ and $t_{i+1}$ respectively, $\alpha$ is the threshold for the $match$ function to measure the overlaps between two clusters. In addition to transition types defined between pairs of consecutive timepoints, we introduce another transition type, namely, ”a cluster has re-emerged”, which measures the transition across non-consecutive timepoints. To visualize the transitions of a cluster in a global view, we model the set of transitions starting at a newly emerged cluster as a flow. In other words, we treat the pairwise transitions as the edges between the cluster nodes across different timepoints. When a transition exists between two cluster nodes, an edge with the transition type as value is assigned to connect them. It should be noted that to be computationally consistent with the basic transition types, the re-emergence transition is matched in respect of the last node in the sequence of the consecutive transitions.

We validate the topic transition results from our computer generated approach by applying the same transition framework to human annotated clusters. Each tweet is annotated with at most three noun (-phrase) labels which summarize the tweet the most by a human expert. The majority of the labels are directly selected from the tweets. Out-of-content labels are only generated when the tokens in a tweet cannot meaningfully summarize it.

A preliminary inspection over the manually and computationally generated clusters showed a mismatch in quantity of labels. In addition, we observed several co-occurring topics in the annotated clusters due to retweets. To merge the co-occurring topics in human annotated clusters, we employ frequent itemsets (?) to discover strongly associated topics. Support $supp$ is calculated as an indication of how frequently an itemset appears in the data (Equation 5). If two itemsets share the same $supp$ value and one itemset is the subset of another, we merge the subset into its parent.

• •

  $T$: a set of transactions of a given dataset.

It should be noted that the methods of clustering between computer generated and human-annotated data are very different. However, the trends should be visible regardless of the methods, provided that the clusters are done well.

To summarize, the average percentage of bridging nodes removed in each temporal GoW is 10.71% with an average $C_{i}$ of $0.44$. Timepoint specific data of the clusterings is shown in Table 3, where $\bar{C}_{rm}$, $\bar{C}_{all}$, $\bar{C}_{best}$ denote the average $C_{i}$ for removed nodes, the original GoW, and the best clustered subgraph respectively; and $\%_{rm}$ denotes the percentage of nodes removed. The best subgraphs across all timepoints showed an increase in average $C_{i}$ after the removal of bridging nodes, which confirms that the global embeddedness of the graph have become stronger. It is noteworthy that many of the best subgraphs achieve a nearly 1.0 (maximum boundry) average $C_{i}$, which suggests that the neighbors of each node in the subgraph are inter-connected. This can occur when the resulting subgraph is a complete graph or consists several fully connected components which are not inter-connected. Our results are latter. Another metric should be considered for future tasks as the clustering coefficient $C_{i}$ lacks the ability to differentiate the structural characteristics since it only considers the internal variance of the clusters.

In addition, we observed consistent converging trends among the modularity plots over all timepoints. As the nodes with lower $C_{i}$ get excluded from the subgraph, the resulting clustering quality starts to increase and gradually converges. Once a maximal modularity value is achieved, removing more bridging nodes will cause a decay in quality. Currently, our approach chose the result at the maximal modularity value as the optimal clustering. To increase generalizability and reduce computational cost, Algorithm 1 can be updated to stop when the modularity value starts to converge. Figure 1 illustrates an example clustering on Aug 19.

We applied the metrics defined in Table 2 to construct transition flows for both the computer generated clusters and human annotated label sets. An opportunistic threshold of $\alpha=2/3$ is used for the $match$ function to determine if two clusters are considered as the same, no other threshold have been attempted. The computational approach generated 34 independent transition flows with an average length of 2.41 timepoints per flow, while 151 clusters only exist across a single timepoint. On the other hand, the human annotation suggests that there are 17 independent transition flows with an average length of 4.53 timepoints per flow, and 68 sets only exist across a single timepoint.

It should be noted that the computer generated clusters are based on nouns and NE from tweets with no order in mind, while human-annotated clusters are based on three summarized terms per tweet. Thus, computer generated clusters group all topic per day together irrespective of which tweet they come from, while human annotated ones have an additional layer of summarization: each tweet to keywords. The mismatch in the number of clusters can thus be explained by this additional layer of complexity, and should not necessarily be treated as a negative result. What is more interesting to see is the patterns that emerge from repeating topics, within both layers, throughout two weeks of data.

Figure 2 demonstrates the cluster progression charts of the computational approach and human annotated topics side by side. It can be seen that many clusters, both computer and human generated, reappear overtime. One clear outlier is a sequence of human-annotated clusters that contains a series of various transitions for over a week. A shared label between these clusters denotes the name of a policy that the local community is enforcing to ensure safety during the pandemic. Coincidentally, the same policy name has been detected as the bridging node in computer generated clusters in nearly all timepoints during the clustering process. Further analysis suggests that the longest sequence of transitions in both computer and human generated clusters can be traced to the same topic not mentioned here due to anonymity requirement. Despite the differences between the cluster generating mechanisms, both transition flows progress similarly in trends of emergence, re-appearance, and disappearance.