Prof. Olgica Milenkovic - Submodular Hypergraph Partitioning with Applications

Professor:
Olgica Milenkovic
Professor, Electrical & Computer Engineering Dept.
Research Professor, Coordinated Science Laboratory
University of Illinois Urbana-Champaign


Abstract:
Hypergraph partitioning is an important problem in machine learning, computer vision, VLSI design and network analytics. A widely used method for hypergraph partitioning relies on minimizing a normalized sum of the costs of placing hyperedges across clusters. Algorithmic solutions for this approach assume that different partitions of a hyperedge incur the same cost. However, this assumption fails to address settings in which different subsets of vertices in the same hyperedge provide different contributions to the underlying higher order relations. To accommodate nonuniform partitioning costs, we introduce the notions of inhomogeneous spectral hypergraph partitioning and submodular hypergraphs. Inhomogeneous spectral partitioning produces a quadratic approximation to the optimal solution if the costs satisfy submodularity constraints. We illustrate the advantages of inhomogenous over classical hypergraph partitioning on applications as diverse as structure learning of rankings, subspace segmentation and motif clustering.