Trend Mining in Dynamic Attributed Graphs

Elise Desmier, Marc Plantevit, Céline Robardet, Jean-François Boulicaut

Abstract

This paper presents a novel framework for discovering "trend sub-graphs" within dynamic networks where node attributes evolve over time. By prioritizing the direction of change (trends) over raw numerical values and enforcing topological connectivity, the proposed MINTAG algorithm efficiently extracts meaningful patterns from complex datasets, including social networks, flight records, and satellite imagery.

Introduction

In the modern data landscape, dynamic attributed graphs—networks where both connections (edges) and entity properties (node attributes) evolve—are ubiquitous. A significant challenge in analyzing these graphs is identifying "co-evolution patterns": groups of nodes that are topologically close and exhibit similar behavior over time.

Comparing raw numerical values often fails due to noise and individual variability. For instance, two researchers might both increase their publication counts, but at vastly different scales (e.g., 1 to 2 vs. 10 to 20). This research addresses this by mining for trends (the sign of the derivative) rather than absolute values, ensuring discovered patterns are robust and topologically cohesive.

Methodology

The authors define a Trend Dynamic Sub-graph as a set of vertices that are connected (within a user-defined maximum diameter), share a common set of attribute trends (e.g., "Attribute X is increasing"), and persist over a specific sequence of time stamps.

Conceptual representation of a trend pattern over time.

The MINTAG Algorithm

To find these patterns, the MINTAG (MINing Trend Attributed Graphs) algorithm was developed. It utilizes a lattice-based enumeration strategy to traverse the search space of possible sub-graphs in a depth-first manner.

The MINTAG algorithm pseudocode.

Key technical features include:

  • Constraint Propagation: MINTAG handles various constraints—such as minimum size, volume, and diameter—to prune the search space effectively. The authors successfully derived propagation mechanisms for non-monotonic constraints like diameter, significantly boosting performance.
  • Interestingness Measures: To filter trivial results, the authors introduce:
  • Vertex Specificity: Uniqueness of the trend to the pattern nodes compared to the rest of the graph.
  • Trend Relevancy: An entropy-based measure ensuring attributes outside the pattern do not share the same trend.
  • Temporal Dynamic: Distinguishing between sudden "bursts" and constant background trends.

Experimental Evaluation

The authors evaluated MINTAG on three real-world datasets: DBLP (co-authorship), US Flights (airport delays), and Brazil Landslides (satellite imagery segments).

Key Results

  • Efficiency: MINTAG demonstrated high scalability, processing DBLP and Flight data in seconds and the 400k-node Landslide dataset in approximately two hours.
  • Domain Discovery:
    • In DBLP, it identified shifts in publication trends related to the emergence of the PVLDB journal.
  • In US Flights, it accurately pinpointed airports with arrival delay spikes following Hurricane Katrina.
  • In Brazil Landslides, the algorithm correctly identified 69% of true landslide regions by detecting specific decreases in vegetation indices.

Discussion and Conclusion

By abstracting data into binary trends ($+$ or $-$), MINTAG becomes resilient to inter-individual variability and captures the directional evolution of communities. The enforcement of a diameter constraint ensures that discovered patterns represent localized phenomena rather than coincidental similarities.

While efficient, calculating the shortest paths for the diameter constraint remains a computational bottleneck for extremely large graphs. Additionally, the current binary trend model does not account for the magnitude of change. Future work may explore more complex temporal logic and real-time streaming graph data.

Summary updated

BibTeX
@inproceedings{desmier2013trend,
  author = {Elise Desmier and Marc Plantevit and Céline Robardet and Jean-François Boulicaut},
  title = {{Trend Mining in Dynamic Attributed Graphs}},
  booktitle = {ECML/PKDD},
  year = {2013},
  doi = {10.1007/978-3-642-40988-2\_42},
}
Figure