A Generalized Ratio Cut Objective in Graphs and Efficient Algorithm for Solving the Localized Generalized Expansion Ratio Problem

Abstract

In graph clustering, ratio cut objectives represent the ratio between the connectivity of the subgraph and some notation of the graph properties including size and density. These ratio cut objectives are widely studied and used for many tasks including graph partitioning. Specifically, the standard expansion ratio measures the ratio between subgraph’s connections to the rest of the graph and the subgraph size. This thesis introduces a generalized version of the standard expansion ratio objective and studies a localized variant of the expansion ratio problem by presenting its connections to existing problems and numerical results on existing problems.

The generalized version of the expansion ratio concerned in this thesis replaces the subgraph size with a convex function of the set size, generalizing more than one existing objective functions. The localized variant of the expansion ratio problem removes the constraint of subgraph size while restricting the resulting subgraph to a given seed set of nodes. While the original expansion problem is NP-hard to solve, this thesis introduces a polynomial-time algorithm for the novel localized variant of the problem. By varying the convex function and tuning parameters, numerical experiments show solving this new problem with the generalized objective allows one implicitly control the size of the resulting subgraph.