TEAGS: time-aware text embedding approach to generate subgraphs

Saeid Hosseini, Saeed Najafi Pour, Ngai-Man Cheung, Hongzhi Yin, Mohammad Reza Kangavari, Xiaofang Zhou

TL;DR

This paper introduces TEAGS, a novel framework for generating subgraphs of highly correlated nodes in dynamic propagation networks. TEAGS uniquely combines time-aware word embeddings with a generative model to capture complex temporal and textual influences on contagion spread, outperforming existing methods in subgraph mining.

What Problem Does This Paper Address?

Propagation processes, like the spread of viruses or information, are ubiquitous in networks (e.g., social media, epidemiology). Identifying "tightly connected subgraphs" – groups of nodes that are highly correlated – is crucial for applications like disease control and targeted interventions. However, existing methods struggle with several challenges:

  • Temporal Dynamics: The way nodes influence each other can change significantly over time (e.g., a node might spread information during the day but not at night).
  • Contagion Diversity: Different types of "contagions" (information, viruses) can propagate, and their behavior might vary.
  • Word Embedding Limitations: Traditional word embedding techniques, which rely on word co-occurrence, often fail to account for how these co-occurrence patterns shift across different temporal facets (hours, days, seasons). This makes it difficult to accurately compute the correlation weights between nodes based on their textual content.

TEAGS aims to address these limitations by explicitly modeling the time-aware and multi-aspect nature of propagation.

Methods

TEAGS employs a sophisticated, two-phase approach:

1. Offline Processing:

  • Similarity Grids: The framework first constructs "similarity grids" to capture temporal and textual correlations.
  • Textual Similarity: Aggregates textual content from nodes within specific temporal splits (e.g., all tweets from 5 AM) and uses a modified TF-IDF approach to weigh words. Then, cosine similarity is used to compare split vectors.
  • Temporal Similarity: Identifies nodes infected by the same alarm type within pairs of temporal splits and uses linear correlation to compute similarity.
  • Acquiring Temporal Slabs: Hierarchical Agglomerative Clustering (HAC) is used on the similarity grids to group similar temporal splits into "multifacet temporal slabs." These slabs represent unified temporal dimensions (e.g., a slab for "morning hours on weekdays").
  • Time-Aware Word Embedding (TWE): This is a core innovation. Unlike traditional word embeddings that treat all co-occurrences equally, TWE models how word co-occurrence patterns change across different temporal facets. It uses two key attributes:
  • Contiguity: Measures how often word pairs appear together within the same temporal slab.
  • Depth: Accounts for the influence of parent temporal dimensions (e.g., how the "hour" dimension is affected by the "day" or "week").
  • Multifacet Generative Model (MGM): This model computes edge weights by considering multiple temporal dimensions simultaneously, capturing the joint probability of contagion spread between nodes across various time facets.
  • Coherence Score: A weighted combination of three scores – global semantic coherence (from Original Word Embedding), multi-aspect temporal-semantic balance (from TWE), and time-only correlation (from MGM) – is used to determine the final edge weight between nodes.

2. Online Processing:

  • Bilateral Network Generation: The coherence scores are used to construct a single-edged undirected graph representing the propagation network.
  • Max-Heap Graph Cutting: A novel Max-Heap Graph Cutting algorithm is employed to efficiently extract subgraphs. This algorithm prioritizes edges with higher weights, aiming to maximize intra-subgraph correlations while minimizing the number of edges used.

Datasets

The paper uses two real-world datasets:

  • ST-0 and ST-1: These datasets, collected in 2016, report how faults propagate between nodes in two Singaporean train stations. They contain over 1 million nodes each, with up to 300 contagions per node.

Key Insights and Ideas

  • Temporal Dynamics are Crucial: The paper strongly emphasizes that simply considering sequential time is insufficient. Propagation patterns are influenced by multiple temporal facets (hour, day, week, month) that interact.
  • Word Embeddings Need Time Awareness: Traditional word embeddings fail to capture how word co-occurrence shifts over time, leading to inaccurate correlation estimates. TEAGS's TWE module directly addresses this by modeling temporal variations.
  • Multi-Aspect Influence: The influence of one node on another is not a single value but a complex interplay of temporal and textual factors across different dimensions. TEAGS's generative model and coherence score aim to capture this complexity.
  • Big Clusters are Better: The experiments show that using "big clusters" (larger groups of merged temporal splits) in the slab acquisition phase leads to better subgraph mining performance compared to "small clusters."
  • Textual Semantics Remain Dominant: While temporal features are vital, the paper notes that textual semantics (captured by word embeddings) often play a more dominant role in subgraph mining effectiveness, especially when compared to purely temporal models.

Key Results

  • Subgraph Mining Performance: TEAGS consistently outperforms existing methods in subgraph mining, achieving higher F-measures. For instance, in ST-0, TWE_Dep with more than 20 word vector items achieved better results than OWE and TWE_Con. In ST-1, TWE_Con showed superior performance.
  • Comparison with Baselines: TEAGS (specifically its TEALS variant) demonstrates significant improvements over other models like PTM, CTA, BDI, and MATES, particularly in F-measure.
  • Robustness to Data Variation: TWE_Con and TWE_Dep show more robustness to changes in similarity grids as the dataset grows compared to MGM, which relies more heavily on temporal grids.
  • Efficiency: While increasing the parameter $\zeta$ (related to the number of similar words used in embedding) slightly increases processing time, TEAGS remains efficient, especially due to its parallelizable nature.

Limitations and Future Work

  • Trigger Interval Tuning: The paper highlights the need to regenerate similarity grids periodically. While TEAGS provides a method to estimate trigger intervals, further research could optimize this process.
  • Computational Complexity: While TEAGS is designed for efficiency, the complexity of graph-cutting algorithms can still be a bottleneck for extremely large graphs.
  • Parameter Optimization: The effectiveness of TEAGS depends on parameters like $\lambda$ and $\beta$ in the coherence score. While the paper uses optimization to find good values, automated parameter tuning could be explored.
  • Future Work: The authors suggest exploring more sophisticated temporal models and investigating the impact of different contagion types and propagation mechanisms. They also mention the potential for parallelizing the Max-Heap Graph Cutting algorithm.

Summary updated

Abstract

Contagions (e.g. virus and gossip) spread over the nodes in propagation graphs. We can use temporal-textual contents of nodes to compute the edge weights and 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, current 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 which adversely impacts the performance 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 time-aware word embedding component to construct the word vectors through multiple temporal facets, and on the other hand, uses a time-only multi-facet generative model to compute the weights. Subsequently, we propose a Max-Heap Graph cutting algorithm to generate subgraphs. We validate our model through experiments on real-world datasets. The results show that our model can generate the subgraphs more effective than other rivals and temporal dynamics must be adhered in the modeling of the dynamical processes.
BibTeX
@inproceedings{hosseini2020teags,
  author = {Saeid Hosseini and Saeed Najafi Pour and Ngai-Man Cheung and Hongzhi Yin and Mohammad Reza Kangavari and Xiaofang Zhou},
  title = {{TEAGS: time-aware text embedding approach to generate subgraphs}},
  booktitle = {Data Min. Knowl. Discov},
  year = {2020},
  url = {https://openreview.net/forum?id=osvX6R3sZ4Q},
}
Figure