Graphical Model Sketch

Branislav Kveton, Hung Hai Bui, Mohammad Ghavamzadeh, Georgios Theocharous, S. Muthukrishnan, Siqi Sun

Abstract: Structured high-cardinality data poses a significant challenge for modeling and inference in modern data streams. While graphical models are effective for structured data, they struggle with high-cardinality variables. Conversely, the Count-Min (CM) sketch is a standard for high-cardinality data but fails to scale with dimensionality. This paper introduces Graphical Model Sketches, a framework that combines the structural benefits of Bayesian networks with the space efficiency of data sketches. By decomposing joint probabilities into sketched factors, these approximations achieve space complexity independent of variable cardinality and provide multiplicative error bounds that significantly outperform state-of-the-art methods.

1. Introduction

In domains such as online advertising, network traffic monitoring, and Natural Language Processing (NLP), practitioners frequently need to estimate the probability of specific events within massive data streams. For instance, an advertiser might ask: "What is the probability that a user from a specific city visits a particular product page after clicking a specific campaign link?"

Estimating these probabilities involves two primary hurdles:

  1. High Cardinality ($M$): Variables like User IDs or URLs can have millions of unique values. Storing a joint probability table for even two such variables would require $M^2$ entries, exceeding the RAM capacity of most systems.
  2. High Dimensionality ($K$): As the number of variables increases, the "curse of dimensionality" renders traditional sketching techniques, like the Count-Min (CM) sketch, ineffective. To maintain accuracy for 10 or more variables, a CM sketch would require astronomical memory or produce errors that dwarf the actual signal.

2. Methodology: Sketching the Graphical Model

The researchers propose a hybrid approach that leverages the structure of a Graphical Model (specifically a Bayesian network) to decompose the joint probability $P(X_1, ..., X_K)$ into smaller, manageable factors. Using the chain rule of probability, the joint distribution is represented as a product of conditional probabilities: $P(X_{child} | X_{parent})$.

Instead of sketching the entire joint distribution as a single entity, the framework sketches these individual factors. The paper analyzes three specific algorithmic implementations:

  • GMHash: A baseline version using simple hash tables to estimate ratios.
  • GMSketch: An enhanced version utilizing the "median trick"—taking the median of multiple independent estimates—to increase reliability and reduce variance.
  • GMFactorSketch: The flagship algorithm. It estimates each conditional probability factor as a ratio of two separate Count-Min sketches.

The defining characteristic of these algorithms is that their space complexity is independent of the cardinality $M$. The memory footprint depends only on the number of variables ($K$) and the desired precision, making it uniquely suited for massive-scale data.

3. Theoretical Contributions

A pivotal contribution of this work is the shift from additive error to multiplicative error. Standard CM sketches typically offer additive bounds (e.g., an estimate is accurate within $\pm \epsilon$). For rare events with very low probabilities, an additive error can be larger than the value itself, rendering the estimate useless. Graphical Model Sketches provide multiplicative error bounds, ensuring the error is proportional to the actual probability. This makes the model significantly more effective for "long-tail" data distributions.

Furthermore, the authors identify a query-specific constant, $\Delta(x)$, representing the minimum probability of any variable-parent pair in a query. They demonstrate that the space required is inversely proportional to this "hardness" constant, proving that their approach is order-optimal regarding the intrinsic difficulty of the query.

4. Experimental Evaluation

The framework was evaluated against the standard Count-Min sketch using both synthetic and real-world datasets:

  • Synthetic Naive Bayes: A model with 32 variables, each with a cardinality of $2^{16}$ (65,536 values), used to test performance on both frequent ("heavy") and rare ("light") events.
  • Adobe Marketing Cloud Data: A real-world dataset comprising 65 million page views. This data included six high-cardinality variables such as City, Page Name (over 42,000 unique values), and Campaign.

In both scenarios, GMFactorSketch outperformed the CM sketch by an order of magnitude. For a fixed memory budget, GMFactorSketch was significantly more likely to provide a "precise" estimate (defined as being within a factor of $e$ of the ground truth). On the Adobe dataset, while the CM sketch required massive amounts of memory to produce useful results, the Graphical Model Sketches achieved high accuracy with only a fraction of the space.

5. Conclusion and Future Work

Graphical Model Sketches represent a significant advancement in stream processing, offering a scalable solution for high-cardinality, high-dimensionality probability estimation. By using the graph structure as a "pre-compressor," the system only needs to account for the dependencies defined by the edges of the network.

However, some limitations remain for future exploration:

  • Structure Learning: The current model assumes the dependency structure is known. Future iterations could involve learning the graph structure dynamically from the stream.
  • Query Types: The current work focuses on "point queries" (specific outcomes). Extending the framework to handle "marginal queries" (probabilities of subsets of variables) is a logical next step.
  • Graph Complexity: While the analysis focuses on tree-structured graphs, extending these efficiencies to graphs with high treewidth (many loops) remains a challenge.

Summary updated

Abstract

Structured high-cardinality data arises in many domains, and poses a major challenge for both modeling and inference. Graphical models are a popular approach to modeling structured data but they are unsuitable for high-cardinality variables. The count-min (CM) sketch is a popular approach to estimating probabilities in high-cardinality data but it does not scale well beyond a few variables. In this work, we bring together the ideas of graphical models and count sketches; and propose and analyze several approaches to estimating probabilities in structured high-cardinality streams of data. The key idea of our approximations is to use the structure of a graphical model and approximately estimate its factors by "sketches", which hash high-cardinality variables using random projections. Our approximations are computationally efficient and their space complexity is independent of the cardinality of variables. Our error bounds are multiplicative and significantly improve upon those of the CM sketch, a state-of-the-art approach to estimating probabilities in streams. We evaluate our approximations on synthetic and real-world problems, and report an order of magnitude improvements over the CM sketch.
BibTeX
@inproceedings{kveton2016graphical,
  author = {Branislav Kveton and Hung Hai Bui and Mohammad Ghavamzadeh and Georgios Theocharous and S. Muthukrishnan and Siqi Sun},
  title = {{Graphical Model Sketch}},
  booktitle = {ECML/PKDD},
  year = {2016},
  url = {https://openreview.net/forum?id=x3P_AQwViWF},
}

Loading related content...

Figure