Overlapping clustering of network data using cut metrics

Fernando Gama, Santiago Segarra, Alejandro Ribeiro

TL;DR

This paper introduces a novel method for hierarchical overlapping clustering of network data. It addresses the limitation of traditional clustering by allowing nodes to belong to multiple clusters at different levels of similarity, using a "cut metric" derived from averaging ultrametrics of perturbed network versions. This approach is demonstrated to be effective in uncovering complex data structures and is applied to real-world problems like digit classification and authorship attribution.

What Problem Does This Paper Address?

Clustering aims to group similar data points. Traditional methods create a single, non-overlapping partition. Hierarchical clustering offers multiple partitions at different similarity levels but still enforces exclusivity. This is problematic because real-world data often exhibits inherent overlap: a node might genuinely share characteristics with multiple groups. Existing overlapping clustering methods are typically non-hierarchical and don't capture varying degrees of similarity. This paper tackles the challenge of creating a clustering method that is both hierarchical (offering multiple resolution levels) and overlapping (allowing nodes to belong to multiple clusters simultaneously), providing a more nuanced representation of complex network data.

Methods

The core of the proposed method lies in constructing a "cut metric" from a given network. This cut metric is derived by:

  1. Dithering: Intentionally adding random noise to the original network's dissimilarity function multiple times to create slightly perturbed versions of the network.
  2. Hierarchical (Non-Overlapping) Clustering: Applying a standard hierarchical clustering algorithm (like Ward's method or UPGMA) to each of these perturbed networks. This yields a collection of "ultrametrics," which are a specific type of metric that captures hierarchical relationships.
  3. Averaging Ultrametrics: Convexly combining (averaging) these ultrametrics to produce a single "cut metric." This cut metric is a generalization that allows for overlapping structures.
  4. Generating Nested Coverings: Using the cut metric to define tolerance relations, which in turn generate a "nested collection of coverings." These coverings represent the hierarchical overlapping clusters at different resolution levels.

The paper also introduces "quasi-cut metrics" and "quasi-coverings" to handle directed networks where relationships are not symmetric.

Datasets

The paper evaluates its method on:

  • Synthetic Networks: Including a "dumbbell network," a "two clouds" network, a "multiple resolutions" network, and a "directed network" for authorship attribution. These are used to demonstrate the algorithm's behavior in controlled scenarios and its ability to overcome limitations of standard methods like single linkage.
  • MNIST Handwritten Digit Database: Used for classification tasks, specifically for distinguishing pairs of digits (1 and 7), triplets (6, 8, and 9), and quadruplets (0, 1, 2, and 7).
  • Shakespeare and Fletcher Plays Dataset: Used for authorship attribution, distinguishing plays by Shakespeare, Fletcher, and co-authored plays.
  • Shakespeare, Chapman, and Jonson Plays Dataset: Another authorship attribution task, including plays by these authors and a co-authored play.
  • Shakespeare and Marlowe Directed Network: Used to demonstrate the quasi-clustering method on directed data.

Key Insights and Ideas

  • Bridging Ultrametrics and Cut Metrics: The paper establishes a crucial link between ultrametrics (representing non-overlapping hierarchical structures) and cut metrics (which can represent overlapping structures). This connection is key to extending hierarchical clustering to the overlapping domain.
  • Dithering as a Noise Injection Tool: Intentionally perturbing the network data with noise and then averaging the results is a clever way to smooth out idiosyncrasies and derive a robust cut metric that captures underlying similarities.
  • Overlapping Function for Insight: The "overlapping function" is introduced as a valuable tool to quantify the degree of overlap at different resolutions. This helps in identifying "clusterable" datasets (where non-trivial, non-overlapping partitions exist) and in selecting meaningful resolution levels.
  • Overcoming Single Linkage's Chaining Effect: The method is shown to effectively handle scenarios where single linkage clustering suffers from the "chaining effect," where a long chain of weakly connected nodes can incorrectly merge distinct clusters.
  • Generalization to Directed Networks: The introduction of "quasi-cut metrics" and "quasi-coverings" extends the framework to directed networks, which are common in many real-world applications.

Key Results

  • Hierarchical Overlapping Clustering: The proposed method successfully generates nested collections of coverings, allowing nodes to belong to multiple clusters at different similarity levels.
  • Synthetic Network Performance: The method demonstrates intuitive results on synthetic data, correctly identifying clusters and overcoming limitations of traditional methods.
  • Handwritten Digit Classification:
    • For two-digit classification (1 and 7), an error rate of 0.5% was achieved.
  • For three-digit classification (6, 8, and 9), an error rate of 2.67% was achieved.
  • For four-digit classification (0, 1, 2, and 7), an error rate of 5% was achieved. In these cases, the proposed method produced the same clusters as hierarchical non-overlapping clustering but used the overlapping function to identify optimal resolutions.

  • Authorship Attribution:

    • For Shakespeare and Fletcher, the method identified co-authored plays as belonging to overlapping clusters, providing more nuanced results than non-overlapping methods.
  • For Shakespeare, Chapman, and Jonson, the method successfully identified co-authored plays and highlighted other plays that were difficult to classify.
  • Directed Network Analysis: The quasi-clustering method demonstrated its ability to handle asymmetric relationships, correctly identifying co-authored plays in a directed network context.

Limitations and Future Work

  • Choice of Hierarchical Method: The performance of the proposed method depends on the choice of the underlying hierarchical (non-overlapping) clustering algorithm (H). The paper notes that this choice should be problem-specific.
  • Parameter Sensitivity (J): While the number of perturbations (J) is not fundamental, the paper suggests that for J > 10, the output covers do not significantly depend on J. However, the optimal value of J might still require some tuning.
  • Uniqueness of Tolerance Relations: The paper points out that unlike the strict bijection between ultrametrics and dendrograms, a given covering does not uniquely determine a tolerance relation, and a nested collection of coverings does not uniquely determine a cut metric. This implies some flexibility but also a potential loss of information when going from coverings back to metrics.
  • Future Work: The paper implicitly suggests further exploration of quasi-clustering methods for directed networks and the application of the overlapping function for more in-depth data analysis. The authors also mention that cut metrics form a conic hull of ultrametrics, hinting at potential extensions using other combinations of ultrametrics.

Summary updated

Abstract

We present a novel method to hierarchically cluster networked data allowing nodes to simultaneously belong to multiple clusters. Given a network, our method outputs a cut metric on the underlying node set, which can be related to data coverings at different resolutions. The cut metric is obtained by averaging a set of ultrametrics, which are themselves the output of (non-overlapping) hierarchically clustering noisy versions of the original network of interest. The resulting algorithm is illustrated in synthetic networks and is used to classify handwritten digits from the MNIST database.
BibTeX
@inproceedings{gama2016overlapping,
  author = {Fernando Gama and Santiago Segarra and Alejandro Ribeiro},
  title = {{Overlapping clustering of network data using cut metrics}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2016},
  doi = {10.1109/icassp.2016.7472912},
}
Figure