Stochastic Blockmodeling for Online Advertising

Li Chen, Matthew Patton

Abstract

Online advertising is a massive industry where understanding website attributes is crucial for business strategies such as ad-targeting, content display, inventory purchase, and revenue prediction. However, classical inferences on users and sites are challenged by data that is voluminous, sparse, high-dimensional, and noisy. This paper introduces a stochastic blockmodeling framework for website relations induced by online user visitation. We propose two clustering algorithms to discover the intrinsic structures of websites and compare their performance against goodness-of-fit and deterministic graph partitioning methods. Our results demonstrate the effectiveness of these algorithms on both simulated data and a real-world AOL website dataset.

Introduction

In the current digital age, the ability to map the relationships between websites is a competitive necessity for advertisers. If two websites share a significant portion of their audience, they likely share thematic or demographic relevance. Identifying these latent relationships allows for more sophisticated inventory management and targeting.

Traditional clustering methods often rely on content analysis—which can be computationally expensive and language-dependent—or simple heuristics. This research approaches the problem through statistical graph inference. By treating websites as vertices and user co-visitation as edges, the challenge becomes identifying a mathematically principled way to group these vertices into communities that are both statistically consistent and practically useful.

Methodology: Stochastic Blockmodels (SBM)

The authors utilize the Stochastic Blockmodel (SBM) as the foundation for their clustering approach. In an SBM, vertices are partitioned into $K$ latent communities (blocks). The probability of an edge existing between any two vertices depends solely on the block memberships of those vertices.

The BIC-based Vertex Clustering Approach

The core contribution is a multi-step clustering framework (Algorithm 1) designed to handle the noise of web-scale graphs:

  1. Spectral Embedding: The graph’s adjacency matrix (Adjacency Spectral Embedding, or ASE) or Laplacian matrix (Laplacian Spectral Embedding, or LAP) is transformed into a lower-dimensional space ($D$) using the top eigenvectors. This reduces dimensionality while preserving structural information.
  2. Gaussian Mixture Modeling (GMM): Theoretical advancements have shown that spectral embeddings of SBMs asymptotically follow a mixture of Gaussian distributions. Consequently, the authors fit GMMs to the embedded data rather than using simpler methods like $k$-means.
  3. Model Selection: The Bayesian Information Criterion (BIC) is employed to automatically determine the optimal number of clusters ($K$) and the most appropriate covariance structure for the GMM, removing the need for manual parameter tuning.
  4. Benchmarking: The ASE and LAP algorithms are compared against the Integrated Classification Likelihood (ICL) method and the Louvain modularity-optimization algorithm, a popular deterministic graph partitioning tool.

Experimental Setup and Datasets

The framework was evaluated using two distinct data sources:

  • Simulation Data: Synthetic graphs with known "ground truth" block memberships were used to calculate the Adjusted Rand Index (ARI), measuring how closely the predicted clusters matched the actual ones.
  • AOL Website Graph: A real-world dataset representing user visitation patterns from July 1, 2014. This graph consisted of 1,569 websites (vertices). An edge was defined by at least one shared user between sites. The dataset was enriched with metadata including website topics, revenue, click counts, and total impressions.

Key Insights and Results

Statistical Accuracy

In simulation trials, the ASE and LAP methods were the only algorithms to consistently identify the correct number of blocks. They maintained high accuracy, with an average ARI exceeding 90%, even as noise levels varied.

Business and Semantic Relevance

When applied to the AOL dataset, the ASE algorithm proved superior in identifying clusters that were not just statistically sound, but economically meaningful.

  • Performance Metrics: ASE discovered more clusters that were statistically significant (at a 5% level) regarding revenue, clicks, and impressions compared to the Louvain or ICL methods.
  • Thematic Coherence: The clusters identified through graph structure naturally aligned with semantic categories. For instance, one cluster grouped sites related to reference and general interest, while another specifically grouped sites focused on politics, parenting, and teen-related content. Other algorithms failed to produce this level of topic-specific granularity.

Discussion and Future Work

The research demonstrates that the latent positions of websites in a graph can be effectively recovered using spectral embeddings and GMMs. By treating the graph as a statistical sample from an underlying SBM, the authors provide a rigorous justification for their clustering results.

However, some limitations remain. The authors noted a bias-variance tradeoff: as the number of clusters increases, the ARI tends to decrease, suggesting a limit to the granularity the model can achieve before noise begins to dominate. Additionally, this study focused on undirected and unweighted graphs. Future research could extend this framework to directed, weighted, or dynamic graphs that evolve over time to capture shifting user trends in the advertising ecosystem.

Summary updated

Abstract

Online advertising is an important and huge industry. Having knowledge of the website attributes can contribute greatly to business strategies for ad-targeting, content display, inventory purchase or revenue prediction. Classical inferences on users and sites impose challenge, because the data is voluminous, sparse, high-dimensional and noisy. In this paper, we introduce a stochastic blockmodeling for the website relations induced by the event of online user visitation. We propose two clustering algorithms to discover the instrinsic structures of websites, and compare the performance with a goodness-of-fit method and a deterministic graph partitioning method. We demonstrate the effectiveness of our algorithms on both simulation and AOL website dataset.
BibTeX
@inproceedings{chen2015stochastic,
  author = {Li Chen and Matthew Patton},
  title = {{Stochastic Blockmodeling for Online Advertising}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9714},
}
Figure