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:
- Varied Temporal Patterns: Propagation behavior is often cyclical or dependent on specific time windows (e.g., morning vs. night).
- Diverse Directions: The direction of influence between nodes can change or vanish depending on the temporal context.
- Mismatched Contents: As a contagion spreads, the associated textual descriptions may evolve (e.g., a "sensor alert" leading to a "system failure").
- 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.
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.
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