On Pairwise Clustering with Side Information

Stephen Pasteris, Fabio Vitale, Claudio Gentile, Mark HerbsterarXiv 2017 · OpenReview

Abstract

Pairwise clustering, in general, partitions a set of items via a known similarity function. In our treatment, clustering is modeled as a transductive prediction problem. Thus rather than beginning with a known similarity function, the function instead is hidden and the learner only receives a random sample consisting of a subset of the pairwise similarities. An additional set of pairwise side-information may be given to the learner, which then determines the inductive bias of our algorithms. We measure performance not based on the recovery of the hidden similarity function, but instead on how well we classify each item. We give tight bounds on the number of misclassifications. We provide two algorithms. The first algorithm SACA is a simple agglomerative clustering algorithm which runs in near linear time, and which serves as a baseline for our analyses. Whereas the second algorithm, RGCA, enables the incorporation of side-information which may lead to improved bounds at the cost of a longer running time.

Introduction

Traditional clustering frameworks often assume access to a complete similarity matrix or a fully defined metric space. However, in many large-scale applications, computing all pairwise similarities is computationally prohibitive. This paper reframes pairwise clustering as a transductive prediction problem where the underlying similarity function is hidden. The learner must partition $n$ items into $k$ clusters using only a random sample of $m$ pairwise similarities and an auxiliary side-information graph that serves as an inductive bias.

Problem Formulation

The goal is to minimize the item misclassification error—the number of items placed in the wrong cluster relative to the ground truth. The learner is provided with:

  1. Sampled Similarities: A random subset of $m$ pairs labeled as similar or dissimilar.
  2. Side-Information Graph: A graph where edges represent "soft constraints," suggesting that connected nodes are likely to share a cluster.

Proposed Algorithms

The authors introduce two algorithms that represent a trade-off between computational speed and the ability to leverage side information.

Simple Agglomerative Clustering Algorithm (SACA)

SACA is a fast baseline that ignores side information. It initializes each item in its own cluster and merges clusters whenever a sampled pair is labeled as "similar." Utilizing a union-find data structure, SACA runs in near-linear time: $\mathcal{O}((n+m)\log^* n)$.

Robust Greedy Clustering Algorithm (RGCA)

RGCA is designed to exploit the side-information graph. It operates in two stages:

  1. Robustification: It builds a robust similarity graph by comparing the Jaccard distance of node neighborhoods to smooth out noise.
  2. Greedy Extraction: It iteratively selects the node with the highest degree, groups it with its neighbors to form a cluster, and removes them from the pool.

To process sampled pairs alongside side-information, RGCA is integrated with the Matrix Winnow online learning algorithm. While this improves theoretical error bounds, it increases the computational complexity to $\mathcal{O}(m n^3)$.

Theoretical Contributions

A significant portion of the paper is dedicated to proving tight statistical bounds on clustering performance.

Metric Translation

The authors establish a tight reduction between the Hamming Error (the number of incorrectly predicted pairwise similarities) and the Misclassification Error (the number of incorrectly clustered items). This allows the performance of the clustering algorithms to be analyzed through the lens of pairwise prediction accuracy.

Effective Resistance as Complexity

To quantify the utility of the side-information graph, the authors introduce the resistance-weighted cut-size ($\Phi_G^R$). By treating the graph as an electrical circuit where edges are resistors, this metric measures the global connectivity between clusters. Unlike simple edge-counting, $\Phi_G^R$ is globally density-independent, making it a more robust measure of the graph's inductive bias.

Key Results

The paper provides rigorous upper and lower bounds for the expected misclassification error:

  • SACA Performance: Without side information, the error is bounded by $\mathcal{O}(\frac{n^2}{m} k \log \frac{n^2}{m})$.
  • RGCA Performance: By utilizing the side-information graph, the error is bounded by $\mathcal{O}(\frac{n^2}{m} \Phi_G^R \log^3 n)$.

If the side-information graph is highly informative (where $\Phi_G^R \approx k$) and clusters are balanced, RGCA improves the error bound by a factor of $k/n$ compared to SACA. Through a randomized labeling strategy, the authors demonstrate that these bounds are essentially optimal up to logarithmic factors.

Conclusion and Future Work

This work provides a theoretical framework for clustering with partial information, highlighting the value of side information in reducing sample complexity. While SACA offers a highly efficient baseline, RGCA demonstrates how structured side-information can drastically improve accuracy. Future research directions include extending these guarantees to non-uniform sampling distributions and exploring active learning regimes where the algorithm can choose which pairwise queries to make.

Summary updated

Abstract

Pairwise clustering, in general, partitions a set of items via a known similarity function. In our treatment, clustering is modeled as a transductive prediction problem. Thus rather than beginning with a known similarity function, the function instead is hidden and the learner only receives a random sample consisting of a subset of the pairwise similarities. An additional set of pairwise side-information may be given to the learner, which then determines the inductive bias of our algorithms. We measure performance not based on the recovery of the hidden similarity function, but instead on how well we classify each item. We give tight bounds on the number of misclassifications. We provide two algorithms. The first algorithm SACA is a simple agglomerative clustering algorithm which runs in near linear time, and which serves as a baseline for our analyses. Whereas the second algorithm, RGCA, enables the incorporation of side-information which may lead to improved bounds at the cost of a longer running time.
BibTeX
@misc{pasteris2017pairwise,
  author = {Stephen Pasteris and Fabio Vitale and Claudio Gentile and Mark Herbster},
  title = {{On Pairwise Clustering with Side Information}},
  year = {2017},
  eprint = {1706.06474},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1706.06474},
}

Loading related content...

Figure