[IEEE VIS] PGraph: Bridging the Gap Between Machine Intelligence and Expert Intuition in Event Detection

TL;DR

PGraph is an interactive framework that transforms social media datasets into a unified graph structure where events are detected as "highly abnormal subgraphs." Unlike traditional black-box algorithms, PGraph allows human experts to interactively refine the detection process, achieving over 10% higher accuracy and near real-time performance (15s for 9.5M records) by combining non-parametric statistics with efficient graph traversal.

The "Two-Stage" Trap: Why Current Systems Fail

For years, social media event detection has been stuck in a linear pipeline:

1. Machine Extraction: Algorithms (Clustering, LDA, etc.) crunch data to find events.
2. Visual Analysis: Experts look at the results and try to make sense of them.

The problem? The expert—who often has the most context—is sidelined until the detection is already finished. If the algorithm misses a nuanced pattern because it lacks specific keyword weights or temporal context, the expert can't fix it. Furthermore, static models often struggle to scale across different temporal resolutions (e.g., minutes vs. hours).

Methodology: The PGraph Architecture

The core innovation lies in treating the entire dataset as a living, Heterogeneous Graph (PGraph).

1. Modeling Abnormality

Instead of simple frequency counts, PGraph uses a p-value calculation for every node (user, tweet, location, hashtag). By comparing current attributes (e.g., mention counts) against historical data, the system assigns an abnormality score between 0 and 1.

2. The Berk-Jones (BJ) Scan Statistic

To find an event, we need to find a group of connected nodes (a subgraph $S$) that is collectively "most abnormal." The authors use the Berk-Jones statistic, which measures the divergence (Kullback-Leibler) between the observed distribution of p-values in the subgraph and a uniform distribution.

3. Interactive Subgraph Expansion

This is where the human comes in. PGraph supports an iterative loop:

• Auto-Mode: The machine starts from the most abnormal node and expands to neighbors to maximize the BJ statistic.
• Interactive-Mode: An expert can force-select a node (e.g., "Hospital" in a World Cup context). The algorithm then re-optimizes the subgraph around this anchor, uncovering hidden connections that a purely automated search might have pruned.

Fig 1. PGraph organizes nodes and pre-sorts neighbors by abnormality to ensure efficient real-time expansion.

Efficiency and Multi-Resolution Aggregation

Handling 9.5 million tweets is computationally expensive. PGraph introduces Graph Aggregation. It builds fine-grained graphs (e.g., 2-minute slices) and aggregates them into coarser resolutions (hours, days) without re-processing raw data. Using Linear Time Subset Scanning (LTSS), the search complexity is reduced to $O(|V|\log |V|)$, enabling the system to respond to expert clicks almost instantly.

Real-World Case Study: The 2018 World Cup

The authors demonstrated PGraph's power using a Weibo dataset during the 2018 World Cup.

When the term "hospital" spiked, the machine initially found a subgraph related to legendary player Maradona. By interacting with the graph and selecting nodes like "score" or "Maradona's throat," the expert could piece together a specific narrative: Maradona's intense celebration of Messi's goal against Nigeria led to him being hospitalized for exhaustion.

Fig 2. The interactive loop: Experts select neighbors to uncover the "Why" behind an abnormal data spike.

Performance vs. Baselines

PGraph was compared against NPHGS and TSPSD.

• Accuracy: On the social media dataset, PGraph's accuracy was consistently 10% higher than traditional machine-only detection.
• Speed: In large-scale scenarios (Social Media), PGraph solved queries in 15 seconds, whereas NPHGS took 310 seconds and TSPSD took 618 seconds.

Fig 3. Accuracy comparison across different events—PGraph consistently leads on complex, high-volume datasets.

Conclusion

PGraph marks a shift from "Machine Detection + Human Visualization" to "Human-Centric Iterative Detection." By leveraging the mathematical rigor of scan statistics and the efficiency of graph aggregation, it provides a tool that doesn't just show the user what happened, but allows the user to investigate why it happened in real-time.

Limitations: While powerful, the system's effectiveness still relies on the quality of entity extraction (NLP) and the expert's familiarity with the domain to provide meaningful "clicks."