Graph Clustering Methods Derived from Column Subset Selection (Student Abstract)

Wei Mao, Guihong Wan, Haim SchweitzerAAAI 2024 · DOI

Introduction

Graph clustering is a fundamental task in data science, aimed at partitioning nodes into groups where internal connections are dense and external connections are sparse. The standard metric for evaluating such partitions is the Normalized Cut (NCut), which balances the weight of edges removed against the connectivity of the resulting clusters. Traditionally, this is solved via spectral clustering using the eigenvectors of the graph Laplacian. This paper introduces a novel theoretical bridge, proving that NCut minimization is mathematically equivalent to Column Subset Selection (CSS)—a technique typically used for feature selection and matrix approximation.

Theoretical Framework

The core of this research lies in redefining the graph structure through an Edge Matrix ($E$). For a graph with $n$ nodes and $m$ edges, $E$ is an $n \times m$ matrix where each column represents a single edge. By applying a normalization based on the degree matrix ($D$), the authors derive a normalized edge matrix $\tilde{E} = D^{-1/2}E$.

The Equivalence Theorem

The authors establish Theorem 3, which demonstrates that the NCut of a partition is exactly equal to the squared Frobenius norm error of approximating the full edge matrix $\tilde{E}$ using a subset of its columns. This shift in perspective transforms a combinatorial graph problem into a continuous matrix approximation problem. Furthermore, the authors prove that linear independence in the columns of $\tilde{E}$ corresponds to the absence of cycles in the graph. Thus, selecting $n-k$ linearly independent edges (columns) naturally results in a "forest" with exactly $k$ connected components.

The CSS-based Clustering Algorithm

Leveraging this equivalence, the authors propose a deterministic 4-step pipeline for graph partitioning:

  1. Construct the normalized edge matrix $\tilde{E}$.
  2. Select $n-k$ linearly independent columns using a standard CSS algorithm (acting as a "black box").
  3. Build a subgraph using only these selected edges.
  4. Identify the $k$ connected components of this subgraph as the final clusters.

Experimental Evaluation

The methodology was tested on the COIL dataset, specifically using image segmentation as a proxy for graph clustering. By treating pixels as nodes and adjacent pixel relationships as edges, the authors visualized how different algorithms partition the image of a mug.

Figure 2: A representative segmentation result on the COIL mug image, showing the clear identification of the central logo and the mug's outer boundary.

Key Results

The study compared the standard NJW spectral clustering algorithm against two CSS methods: QRP (based on QR factorization) and GREEDY (a modern iterative selection method).

  • Quantitative Performance: The GREEDY CSS algorithm consistently outperformed the standard NJW algorithm in minimizing the NCut value. For instance, at $k=6$ clusters, GREEDY achieved an NCut of 0.0137, compared to NJW's 0.0169.
  • Qualitative Performance: While different algorithms yielded different visual boundaries, the CSS-based methods produced structurally sound clusters. QRP, despite having a higher NCut value than GREEDY, produced visually intuitive segments, suggesting that different CSS strategies may capture distinct structural nuances.
Figure 3: A comparison of segmentation results across different algorithms. From left to right, the panels illustrate how different edge selection strategies (like those used in QRP or GREEDY) result in distinct topological partitions of the image.

Conclusion and Future Work

This work provides a powerful new framework for graph clustering by linking it to the well-studied field of Column Subset Selection. By treating NCut as a matrix approximation error, researchers can now apply a wide array of optimization techniques from linear algebra to solve graph problems. Future research will focus on the scalability of these methods for massive graphs and determining which specific CSS variants are optimal for different graph topologies.

Summary updated

BibTeX
@inproceedings{mao2024graph,
  author = {Wei Mao and Guihong Wan and Haim Schweitzer},
  title = {{Graph Clustering Methods Derived from Column Subset Selection (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i21.30479},
}
Figure