A Quality Metric for Visualization of Clusters in Graphs

Amyra Meidiana, Seok-Hee Hong, Peter Eades, Daniel A. Keim

Abstract

Traditionally, graph quality metrics focus on readability, but recent studies show the need for metrics which are more specific to the discovery of patterns in graphs. Cluster analysis is a popular task within graph analysis, yet there is no metric yet explicitly quantifying how well a drawing of a graph represents its cluster structure.

Introduction

In graph visualization, drawings are typically evaluated based on aesthetic criteria, such as minimizing edge crossings or maintaining uniform edge lengths. While these criteria improve general readability, they do not necessarily facilitate the discovery of high-level patterns like communities or clusters. As networks grow in size and complexity, traditional readability metrics often fail to prevent the formation of "hairballs"—layouts where distinct communities become visually indistinguishable. This paper addresses the lack of a standard metric to quantify how effectively a specific layout represents the underlying cluster structure of the data.

Methodology: The Clustering Quality (CQ) Metric

The authors propose a novel Clustering Quality (CQ) metric designed to treat graph drawings as spatial data problems. The calculation follows a three-step framework:

  1. Layout: A graph $G$ with known ground-truth clusters $C$ is projected into a 2D node-link drawing $D$ using a chosen layout algorithm.
  2. Geometric Clustering: The 2D coordinates of the nodes in $D$ are treated as a point cloud. A geometric clustering algorithm, specifically k-means, is applied to find spatial clusters $C'$ based purely on proximity, ignoring edges.
  3. Comparison: The resulting geometric clusters $C'$ are compared against the ground-truth clusters $C$ using statistical similarity measures such as the Adjusted Rand Index (ARI) or Mutual Information (AMI).
The three-step framework for calculating Clustering Quality (CQ).

A high CQ score (approaching 1.0) indicates that the layout algorithm successfully placed nodes from the same community close together while maintaining separation from other communities.

Experimental Setup and Datasets

The metric was validated using both synthetic and real-world datasets:

  • Validation Sets: Ten synthetic graphs with diverse topologies (e.g., stars, trees, paths) to ensure metric robustness across different structural shapes.
  • Real-World Networks: Datasets including revije-90 (magazine co-authorship), SS-Butterfly (biological data), and email-Eu-core (large-scale institutional communication).

Key Results and Validation

The researchers conducted "deformation experiments" to test the metric's sensitivity. By progressively adding noise to node positions, they demonstrated that the CQ score decreases consistently as the visual distinctness of clusters degrades.

Deformation experiment showing the visual degradation of cluster structure from Step 0 to Step 9.

Algorithm Performance

  • Specialized Layouts: Algorithms optimized for cluster representation, such as LinLog, tsNET, and Backbone, consistently achieved the highest CQ scores.
  • General-Purpose Layouts: Among standard force-directed solvers, sfdp performed remarkably well, often outperforming more complex stress-based or spectral methods.
  • Metric Sensitivity: The study found that ARI and the Fowlkes-Mallows Index (FMI) are particularly sensitive to layout distortions, making them ideal for identifying subtle failures in cluster representation.

Discussion and Limitations

While the CQ metric provides a rigorous way to evaluate cluster visualization, it introduces certain trade-offs. For instance, algorithms like LinLog can achieve near-perfect CQ scores by collapsing clusters into single points, which maximizes separation but destroys internal readability.

Furthermore, the current reliance on k-means assumes clusters are roughly spherical. Future work may explore density-based clustering (e.g., DBSCAN) to better capture non-spherical visual structures. Additionally, human-subject studies are needed to correlate high CQ scores with improved user performance in pattern discovery tasks.

Conclusion

The Clustering Quality (CQ) metric offers a mathematical foundation for evaluating how well graph layouts reveal community structures. By moving beyond simple aesthetics toward pattern-specific metrics, researchers can better select and refine algorithms for large-scale network analysis.

Summary updated

Abstract

Traditionally, graph quality metrics focus on readability, but recent studies show the need for metrics which are more specific to the discovery of patterns in graphs. Cluster analysis is a popular task within graph analysis, yet there is no metric yet explicitly quantifying how well a drawing of a graph represents its cluster structure.
BibTeX
@inproceedings{meidiana2019quality,
  author = {Amyra Meidiana and Seok-Hee Hong and Peter Eades and Daniel A. Keim},
  title = {{A Quality Metric for Visualization of Clusters in Graphs}},
  booktitle = {GD},
  year = {2019},
  url = {https://openreview.net/forum?id=nVoeR9r7lU},
}
Figure