Mining Persistent Activity in Continually Evolving Networks

Caleb Belth, Xinyi Zheng, Danai Koutra

In the world of network analysis, we are often obsessed with what’s "trending." We count how many times a specific interaction happens—a "motif"—and assume that high frequency equals high importance. But what if a high-frequency event is just a short-lived burst, like a viral tweet that vanishes in a day? Conversely, what if a low-frequency event happens with clockwork regularity for years, like a subtle coordinated cyber-attack or a daily commute?

In their paper "Mining Persistent Activity in Continually Evolving Networks," Caleb Belth and his colleagues from the University of Michigan argue that to truly understand dynamic networks, we need to stop just counting and start measuring persistence.

TL;DR

The authors introduce a principled framework to identify activity that occurs consistently over time, rather than just frequently. They propose PENminer, an efficient algorithm that uses a novel entropy-based measure to distinguish between "bursty" anomalies and "subtly persistent" patterns, outperforming state-of-the-art anomaly detectors by up to 48% in AUC.

What Problem Does This Paper Address?

Traditional network mining focuses on frequency: how often does a pattern (like a triangle of friends interacting) occur? However, frequency can be misleading. A "bursty" event might have a massive count over a single hour but never happen again. Meanwhile, a "persistent" event might have a low total count but occur at regular intervals over months.

The gap in current research is the lack of a formal, scalable way to measure this "regularity" and "duration" across edge streams (continuous sequences of additions or deletions in a network). Without a measure for persistence, we miss subtle but vital behaviors—like the resilient taxi routes that kept running during Hurricane Sandy or the "stealthy" network intruders who intentionally stay under the radar.

Methods

The authors build their solution on three pillars:

  1. Activity Snippets: They extend the concept of "temporal motifs" to create "activity snippets." These are small sequences of edge updates that can either track specific nodes (e.g., User A emailing User B) or general patterns (e.g., any user replying to any other user).
  2. A Principled Persistence Measure: They define persistence ($P$) through four mathematical axioms and three properties. The final measure is a product of three components:
  3. Width ($W$): The percentage of the total time window covered by the activity.
  4. Frequency ($F$): The log-scale count of occurrences.
  5. Spread ($S$): A measure of how uniformly the occurrences are distributed, calculated using the Shannon Entropy of the time gaps between events.
  6. PENminer Framework:
    • oPENminer: An offline version for analyzing historical data.
  7. sPENminer: A streaming version that updates persistence scores in real-time. Crucially, they derived a way to update the entropy-based "spread" score incrementally, allowing the algorithm to handle massive data streams without re-calculating everything from scratch.

Datasets

The authors evaluated PENminer on a diverse set of real-world edge streams:

  • Transportation: NYC Taxi trips (3 billion edges), and bike-sharing data from Boston, Chicago, and Columbus.
  • Social/Communication: StackOverflow interactions, Reddit subreddit references, and a European research institute's email logs.
  • Security: The DARPA IP-to-IP network dataset, used specifically to test anomaly detection for network attacks.

Key Insights and Ideas

  • The "Persistence vs. Frequency" Plot (PvF): By plotting frequency on one axis and persistence on the other, the authors could visually separate behaviors. "Bursty" events appear in the top-left (high frequency, low persistence), while "subtly persistent" events appear in the bottom-right.
  • Resilience in Crisis: During Hurricane Sandy, most taxi routes in NYC were "bursty" (they stopped abruptly). However, PENminer identified specific routes—like those near hospitals—that remained "subtly persistent," highlighting the city's resilient infrastructure.
  • The Lifecycle of a Question: On StackOverflow, comments on questions are bursty (everyone jumps in at once), but comments on answers are persistent. This suggests that answers provide long-term utility, drawing users back over months or years.
  • Entropy as a Regularity Metric: Using Shannon entropy to measure the "gaps" between events is a clever way to quantify "regularity." If the gaps are all equal, entropy is maximized, indicating a perfectly regular, persistent behavior.

Key Results

  • Superior Anomaly Detection: In identifying "subtly persistent" anomalies (like a slow-and-steady bot attack), sPENminer outperformed baselines like Midas-R and SedanSpot by 9.8% to 48% in AUC.
  • Massive Speedup: The streaming algorithm, sPENminer, is incredibly efficient. It processed edge updates 10,000 to 360,000 times faster than the actual arrival rate of the data streams.
  • Linear Scalability: The offline algorithm's runtime scales linearly with the number of edge updates, making it viable for massive historical datasets.

Limitations and Future Work

While the framework is robust, the authors note a few areas for growth:

  • Parameter Sensitivity: The persistence measure relies on three exponents ($\alpha, \beta, \gamma$) that weight the importance of width, frequency, and spread. Currently, these are set manually based on the application.
  • Automated Tuning: The authors suggest that future work should focus on techniques for automatic parameter tuning to make the tool easier for non-experts to use.
  • Complex Snippets: While the paper handles small snippets well, mining very large, complex persistent subgraphs in real-time remains a computational challenge.

Summary updated

Abstract

Frequent pattern mining is a key area of study that gives insights into the structure and dynamics of evolving networks, such as social or road networks. However, not only does a network evolve, but often the way that it evolves, itself evolves. Thus, knowing, in addition to patterns' frequencies, for how long and how regularly they have occurred-i.e., their persistence-can add to our understanding of evolving networks. In this work, we propose the problem of mining activity that persists through time in continually evolving networks-i.e., activity that repeatedly and consistently occurs. We extend the notion of temporal motifs to capture activity among specific nodes, in what we call activity snippets, which are small sequences of edge-updates that reoccur. We propose axioms and properties that a measure of persistence should satisfy, and develop such a persistence measure. We also propose PENminer, an efficient framework for mining activity snippets' Persistence in Evolving Networks, and design both offline and streaming algorithms. We apply PENminer to numerous real, large-scale evolving networks and edge streams, and find activity that is surprisingly regular over a long period of time, but too infrequent to be discovered by aggregate count alone, and bursts of activity exposed by their lack of persistence. Our findings with PENminer include neighborhoods in NYC where taxi traffic persisted through Hurricane Sandy, the opening of new bike-stations, characteristics of social network users, and more. Moreover, we use PENminer towards identifying anomalies in multiple networks, outperforming baselines at identifying subtle anomalies by 9.8-48% in AUC.
BibTeX
@inproceedings{belth2020mining,
  author = {Caleb Belth and Xinyi Zheng and Danai Koutra},
  title = {{Mining Persistent Activity in Continually Evolving Networks}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2020},
  url = {https://openreview.net/forum?id=IDrCVXsa5My},
}

Loading related content...

Figure