Toward accurate weight-based measurement and periodic edge measurement in graph stream

Zhuo Li, YuXuan Zhao, Jindian Liu, Yu Zhang, Kaihua Liu

In the world of big data, graph streams—sequences of edges arriving at lightning speed—are everywhere, from social media interactions to network traffic logs. Analyzing these streams in real-time is a massive challenge: the data is too large to store in full, so researchers use "sketches" (compact summaries) to estimate properties like edge weights. However, most existing sketches stumble when the data is "skewed" (a few nodes or edges doing most of the work) or when trying to find periodic patterns.

A new paper from researchers at Tianjin University and Peng Cheng Laboratory introduces PMatrix, a novel graph sketch framework designed to handle non-uniform data distributions and detect periodic edges with unprecedented accuracy.

TL;DR

PMatrix is a dual-structure graph sketch that simultaneously handles skewed edge weights and node degrees while introducing a dedicated mechanism for periodic edge detection. It reduces measurement error (ARE) by up to 99.82% compared to state-of-the-art methods and achieves a perfect 100% F1-score in identifying periodic network activity.

What Problem Does This Paper Address?

Most graph stream algorithms face two major hurdles:

  1. The Skew Problem: Real-world data isn't uniform. A tiny fraction of edges often carry the most weight ("heavy hitters"), and a few "super-nodes" have massive degrees. Standard sketches often suffer from "hash collisions," where light edges are accidentally lumped in with heavy ones, leading to massive overestimation errors.
  2. The Periodicity Gap: Many critical network events are periodic—think of a botnet checking in with a server every hour or a consumer's recurring shopping habits. Despite its importance for security (APT detection) and marketing, few graph sketches are designed to find these "periodic edges" efficiently.

Existing solutions usually tackle one type of skew but ignore the other, and almost none address periodicity in a memory-efficient way.

Methods

The core innovation of PMatrix is its dual-storage architecture, which separates the "noise" of light edges from the "signal" of heavy or periodic ones:

  • The Filter Part (3D Adjacency Matrix): This acts as the first line of defense. It uses a 3D structure ($w_1 \times w_1 \times d$) to record weights and timestamps. If an edge's weight stays below a threshold ($T$), it stays here. This "filters" out the vast majority of light edges that would otherwise cause collisions in the main storage.
  • The Candidate Part (2D Adjacency Matrix): Once an edge crosses the threshold, it is promoted to the Candidate Part. This part stores the actual keys (source and destination IDs) and detailed metadata.
  • Collision Management: To handle high-degree nodes, the Candidate Part uses unique Source-collision ($S$) and Destination-collision ($D$) counters. If a bucket becomes too crowded due to a high-degree node, PMatrix dynamically allocates more space in adjacent rows or columns to minimize errors.
  • Periodicity Detection: By storing the interval ($V$) between edge arrivals in the Candidate Part, PMatrix can identify edges that appear with a fixed frequency.

Datasets

The authors evaluated PMatrix using three diverse, real-world datasets:

  • MAWI: IP-trace datasets from a trans-Pacific link between Japan and the US (241M edges).
  • Twitter: A dataset of scraped follow lists (1.7M edges).
  • CAIDA: Anonymized IP traces (445M edges).

Key Insights and Ideas

  • Separation is Key: By using a threshold to separate light and heavy edges into different structures, PMatrix prevents the "heavy" data from being drowned out by the "light" data, which constitutes the bulk of the stream.
  • Addressing Node Degree Skew: Most sketches focus on edge weight. By adding specific counters for source and destination collisions, PMatrix acknowledges that a node with millions of connections (like a popular celebrity on Twitter) requires a different storage strategy than a typical user.
  • Reversibility: Unlike many sketches that are "one-way" (you can ask about an edge, but you can't list all heavy edges), PMatrix is reversible. Because it stores keys in the Candidate Part, it can directly output a list of heavy hitters and periodic edges.

Key Results

PMatrix was tested on both standard CPUs and Open vSwitch (OVS) platforms, showing dominant performance:

  • Accuracy: It reduced the Average Relative Error (ARE) by 62.29% to 99.82% compared to state-of-the-art sketches like TCM, DMatrix, and Cuckoo Matrix.
  • Periodicity: In periodic edge measurement, PMatrix achieved a 100% Precision and Recall (F1-score of 1.0) with an ARE lower than $9 \times 10^{-4}$.
  • Throughput: On the OVS platform, it maintained a packet processing rate of 14.54 Mpps (Million packets per second), proving it is fast enough for high-speed production networks.

Limitations and Future Work

While PMatrix is highly effective, the paper leaves a few areas for further exploration:

  • Threshold Sensitivity: The performance relies on setting the correct threshold ($T$) to separate light and heavy edges. The paper doesn't discuss an automated way to tune this threshold dynamically as traffic patterns change.
  • Memory Overhead: While the authors emphasize efficient memory usage, the Candidate Part's requirement to store full keys and timestamps means it has a higher memory floor than "lossy" sketches that only store counters.
  • Complex Periodicity: The current model focuses on "fixed" intervals. Future work could extend this to detect "quasi-periodic" edges that have slight jitters or variations in their arrival times.

Paper Citation: Zhuo Li, et al. "Toward Accurate Weight-based Measurement and Periodic Edge Measurement in Graph Stream." Research Square/World Wide Web, 2025. DOI: 10.1007/s11280-025-01378-4

Summary updated

Abstract

<title>Abstract</title> Graph streams of sequentially arriving edges are commonly used to represent complex structured data in interactive networks. Typically, graph streams are extremely large and high-velocity. Existing schemes by using graph sketch for summarizing graph stream have demonstrated significant success in handling both storage and query tasks. However, the performance degradation caused by non-uniformly distributions of edge weight and node degree remains unresolved. Current schemes only consider one type of non-uniformly distributions. Meanwhile, there are many periodic edges appearing within the graph streams and finding such periodic edges is crucial for network applications. However, there are no established measurements that predominantly focus on finding periodic edge. To this end, a general graph sketch framework called PMatrix is proposed. PMatrix not only can detect periodic edges, but also adapts to the non-uniformly distributions of edge weight and node degree simultaneously. The performance of PMatrix is evaluated on both CPU and OVS platforms. The experimental results show that PMatrix achieves substantial improvements in measurement precision, reducing the ARE by 62.29% to 99.82% compared with the state-of-the-art graph sketches. For periodic edge measurement, PMatrix has low ARE and F1-Score reaches 100%.
BibTeX
@article{li2025toward,
  author = {Zhuo Li and YuXuan Zhao and Jindian Liu and Yu Zhang and Kaihua Liu},
  title = {{Toward accurate weight-based measurement and periodic edge measurement in graph stream}},
  journal = {WWW},
  year = {2025},
  doi = {10.1007/s11280-025-01378-4},
}

Loading related content...

Figure