Sampling for Approximate Bipartite Network Projection

Nesreen K. Ahmed, Nick G. Duffield, Liangzhen XiaIJCAI 2018 · DOI

TL;DR

This paper introduces a novel, single-pass algorithm called SIMADAPT for efficiently estimating the similarity matrix of large bipartite networks, which are common in real-world applications like e-commerce and social networks. By adaptively sampling bipartite edges and their resulting similarity updates, the method achieves accurate projections with significantly reduced computational resources compared to existing approaches.

What Problem Does This Paper Address?

Many real-world systems can be modeled as bipartite networks, where two distinct types of entities are connected by interactions (e.g., users and products, authors and papers). Analyzing these networks often involves "projecting" them onto a single type of entity to understand relationships within that group. For instance, projecting a user-product network onto users can reveal which users have similar purchasing behaviors. A common way to quantify this similarity is by counting shared neighbors in the bipartite graph.

However, for massive, dynamic bipartite networks (like those generated by continuous user activity), directly computing this similarity matrix is computationally prohibitive due to the sheer number of potential node pairs and the ever-growing stream of new interactions. This paper addresses the challenge of obtaining an accurate approximation of this similarity matrix from a streaming bipartite graph, where edges arrive sequentially and storage is limited. The goal is to efficiently identify the most similar pairs of nodes without processing the entire dataset.

Methods

The core of the paper's contribution lies in its novel sampling algorithm, SIMADAPT, which operates in two main stages:

  1. Adaptive Bipartite Edge Sampling: The algorithm maintains a reservoir of sampled bipartite edges. Crucially, this sampling is adaptive and weighted. Edges are assigned a priority based on their "topological importance," which is related to the degrees of the nodes they connect. This ensures that edges contributing to higher potential similarities are more likely to be kept in the sample. A priority queue is used to manage this reservoir, dynamically adjusting the sampling based on incoming edges and their priorities.
  2. Weighted Similarity Update Aggregation: As new bipartite edges arrive, they can generate updates to the similarity scores between pairs of nodes in the projected graph. The algorithm uses these updates, weighted by their inverse probability of being sampled, to build an unbiased estimate of the similarity matrix. This aggregation is also performed using a fixed-size reservoir, ensuring bounded memory usage.

The paper also introduces a non-adaptive variant, SIMFIXED, and a baseline SIMUNIF for comparison. A key aspect of SIMADAPT is its ability to dynamically update edge weights and sampling probabilities, allowing it to adapt to the evolving structure of the bipartite graph.

Datasets

The authors evaluated their methods on three real-world bipartite datasets:

  • RATING: Represents user-product ratings.
  • MOVIE: Represents user-movie reviews.
  • GITHUB: Represents user-project memberships.

These datasets are publicly available from the Network Repository. The paper does not introduce new benchmarks but uses these existing, large-scale datasets to demonstrate the effectiveness of their streaming approach.

Key Insights and Ideas

  • Adaptive Sampling is Crucial: The paper strongly suggests that simply sampling edges uniformly (SIMUNIF) or using fixed weights (SIMFIXED) is significantly less effective than an adaptive approach (SIMADAPT). The ability to dynamically adjust sampling priorities based on incoming data is key to capturing high-similarity pairs.
  • Common Neighbors as a Proxy for Similarity: The paper leverages the intuition that the number of common neighbors between two nodes in a bipartite graph is a strong indicator of their similarity in the projected graph. This is a well-established concept, but the paper applies it within a novel streaming sampling framework.
  • Wedges as Similarity Units: The authors frame the computation of common neighbors as counting "wedges" (a path of length two in the bipartite graph). This perspective helps in understanding how individual bipartite edges contribute to similarity updates.
  • Filtering Improves Robustness: The experimental results highlight that a simple filtering step on similarity estimates (removing those with very few contributing updates) significantly reduces noise and improves the accuracy of the final projection, especially in the presence of estimation noise.

Key Results

  • Significant Accuracy Improvement: SIMADAPT consistently outperforms baseline methods (SIMPLE, CNHASH) and its non-adaptive counterpart (SIMFIXED) by at least an order of magnitude in terms of Weighted Relative Error (WRE) and 1-rank correlation, especially for the top-ranked similarity edges.
  • Efficiency with Small Samples: The proposed methods achieve high accuracy with surprisingly small sample sizes. For instance, a 10% sample of bipartite edges and a 10% sample of similarity updates (using PBA) yielded weighted relative errors of about 10⁻², and rank correlations close to 1 for the top-ranked edges.
  • Scalability: The algorithms are designed for streaming environments and operate with fixed storage, making them suitable for massive, dynamic graphs where traditional methods fail.
  • Adaptive vs. Non-Adaptive: SIMADAPT shows a noticeable advantage over SIMFIXED, particularly when the edge sample rate ($f_m$) is higher (e.g., $\ge 20\%$), demonstrating the benefit of adaptive sampling.

Limitations and Future Work

  • Focus on Common Neighbors: The paper primarily focuses on the common neighbors metric for similarity. While this is a widely used metric, future work could explore adapting the sampling scheme to other similarity measures (e.g., those based on random walks or other graph kernels).
  • Performance at Highest Ranks: While SIMADAPT excels at identifying high-similarity pairs, its accuracy can degrade for the very highest ranks, where SIMUNIF sometimes performs slightly better. This suggests potential trade-offs in sampling strategies for different parts of the similarity distribution.
  • Parameter Tuning: The performance of the adaptive sampling scheme is dependent on the chosen reservoir sizes ($m$ for edges, $n$ for similarity estimates). While the paper provides experimental results with specific values, further research could explore more automated or adaptive parameter selection strategies.
  • Generalization to Other Graph Structures: The current work is specific to bipartite networks. Extending these adaptive sampling and aggregation techniques to general graphs or other network structures could be a valuable future direction.

Summary updated

BibTeX
@inproceedings{ahmed2018sampling,
  author = {Nesreen K. Ahmed and Nick G. Duffield and Liangzhen Xia},
  title = {{Sampling for Approximate Bipartite Network Projection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/456},
}
Figure