TEALS: Time-aware Text Embedding Approach to Leverage Subgraphs

Saeid Hosseini, Saeed Najafi Pour, Ngai-Man Cheung, Mohammad Reza Kangavari, Xiaofang Zhou, Yuval Elovici

Abstract

Contagions such as viruses or rumors spread through nodes in propagation graphs. Identifying subgraphs of highly relevant nodes is critical for various applications, yet it is complicated by shifting propagation patterns, evolving textual content, and temporal dynamics that affect word co-occurrence. We present TEALS, a novel framework that integrates a neural network-based time-aware word embedding (TWE) component with a temporal generative model to compute edge weights across multiple temporal facets. By employing a Max-Heap Graph cutting algorithm, TEALS efficiently generates subgraphs. Experimental results on real-world datasets demonstrate that TEALS outperforms existing methods, highlighting the importance of temporal dynamics in both word embedding and propagation modeling.

Introduction

In dynamic networks, "contagions"—ranging from social media rumors to technical system faults—propagate between nodes over time. Identifying tightly connected subgraphs within these networks is essential for effective intervention, whether for vaccination strategies, rumor control, or industrial maintenance. However, traditional graph mining and topic-modeling approaches often fail to capture the fluid nature of these networks.

The TEALS (Temporal-Textual Embedding Approach to Leverage Subgraphs) framework addresses these challenges by leveraging both the temporal and textual dimensions of node data. By recognizing that propagation patterns and word meanings are not static, TEALS provides a more accurate representation of node correlations.

Challenges in Dynamic Propagation Networks

Existing methods for subgraph mining face four primary hurdles:

  1. Varied Temporal Patterns: Propagation behavior is often cyclical or dependent on specific time windows (e.g., morning vs. night).
  2. Diverse Directions: The direction of influence between nodes can change or vanish depending on the temporal context.
  3. Mismatched Contents: As a contagion spreads, the associated textual descriptions may evolve (e.g., a "sensor alert" leading to a "system failure").
  4. Skewed Word Meanings: Standard static word embeddings (like Word2vec) do not account for shifts in word co-occurrence patterns over time, leading to inaccuracies in dynamic contexts.

The TEALS Framework

The TEALS framework decomposes the subgraph mining task into two main phases: offline edge-weight computation and online graph-cutting.

The TEALS system architecture, illustrating the offline processing of temporal and textual models and the online subgraph generation.

Temporal Slabs and Multi-facet Modeling

A key innovation in TEALS is the move away from treating time as a simple linear sequence. Instead, the model employs Hierarchical Agglomerative Clustering (HAC) to group similar time intervals into "temporal slabs." For instance, hours between 6 AM and 11 AM might be clustered into a single "morning" slab if they exhibit similar propagation characteristics across the dataset.

Hierarchical Agglomerative Clustering (HAC) results for different temporal facets (day, week), used to define discrete temporal slabs.

Time-aware Word Embedding (TWE)

The TWE component uses a neural network to learn word vectors that are sensitive to these temporal slabs. It considers:

  • Contiguity: The frequency of word co-occurrence within specific slabs.
  • Depth: The hierarchical influence of "parent" facets (e.g., a specific day) on "child" facets (e.g., a specific hour).

Multifacet Generative Model (MGM) and MaxHGC

Complementing the textual analysis, the MGM is a probabilistic model that calculates node relationship likelihoods based on the timing of events (e.g., alarms). It uses an Expectation-Maximization (EM) approach to handle missing data. Finally, the Max-Heap Graph-Cutting (MaxHGC) algorithm uses a greedy approach to efficiently partition the network into the most correlated subgraphs, bypassing the NP-hard complexity of traditional isomorphic tests.

Experimental Evaluation

TEALS was validated using two real-world datasets, ST-0 and ST-1, which track fault propagation across Singaporean train stations. These datasets involve over 1 million nodes and hundreds of different contagion types (alarms).

Key Results

  • Superior Accuracy: TEALS consistently outperformed state-of-the-art rivals such as PTM and CTA in F-measure for subgraph retrieval.
  • Embedding Effectiveness: The time-aware embedding (TWE) significantly improved performance over standard Original Word Embedding (OWE). In the ST-0 dataset, TWE achieved a mean forecast value of ~0.65, compared to ~0.57 for OWE.
  • Scalability and Robustness: By processing data in discrete slabs, TEALS supports parallel computation. Furthermore, its "trigger" mechanism allows it to maintain effectiveness as datasets grow by re-initializing similarity grids to account for new temporal shifts.

Conclusion

TEALS demonstrates that accounting for multi-aspect temporal dimensions is crucial for accurately modeling propagation networks. By integrating time-aware embeddings with a generative temporal model, the framework successfully identifies hidden structures in dynamic data. Future work will focus on automating hyper-parameter tuning and exploring directed edge modeling to further refine causal chain identification.

Summary updated

Abstract

Contagions (e.g. virus, gossip) spread over the nodes in propagation graphs. We can use the temporal and textual data of the nodes to compute the edge weights and then generate subgraphs with highly relevant nodes. This is beneficial to many applications. Yet, challenges abound. First, the propagation pattern between each pair of nodes may change by time. Second, not always the same contagion propagates. Hence, the state-of-the-art text mining approaches including topic-modeling cannot effectively compute the edge weights. Third, since the propagation is affected by time, the word-word co-occurrence patterns may differ in various temporal dimensions, that can decrease the effectiveness of word embedding approaches. We argue that multi-aspect temporal dimensions (hour, day, etc) should be considered to better calculate the correlation weights between the nodes. In this work, we devise a novel framework that on the one hand, integrates a neural network based time-aware word embedding component to construct the word vectors through multiple temporal facets, and on the other hand, uses a temporal generative model to compute the weights. Subsequently, we propose a Max-Heap Graph cutting algorithm to generate subgraphs. We validate our model through comprehensive experiments on real-world datasets. The results show that our model can retrieve the subgraphs more effective than other rivals and the temporal dynamics should be noticed both in word embedding and propagation processes.
BibTeX
@inproceedings{hosseini2020teals,
  author = {Saeid Hosseini and Saeed Najafi Pour and Ngai-Man Cheung and Mohammad Reza Kangavari and Xiaofang Zhou and Yuval Elovici},
  title = {{TEALS: Time-aware Text Embedding Approach to Leverage Subgraphs}},
  booktitle = {Data Min. Knowl. Discov},
  year = {2020},
  url = {https://openreview.net/forum?id=osvX6R3sZ4Q},
}

Loading related content...

Figure