Composite Function Minimization for Hypergraph Laplacian Systems
Brett Larsen, Stanford University
Hypergraphs are a natural generalization of graphs that allow edges to be any subset of the vertices of the graph, referred to as hyperedges. Graphs are frequently used in machine learning as a natural model for a set of objects with pairwise relationships and techniques such as spectral clustering can then be used to partition the set of objects based on these relationships. In many real-world applications, however, restricting to pairwise relationships between objects is rather limiting compared to the complex relationships that can be modeled by a hyperedge. This complex structure also brings new optimization challenges in problems such as clustering, but we can frame these problems in many of the same terms as graphs (e.g. minimum cut, spectral partitions, cut sparsifiers). We present algorithmic improvements on two approaches recently taken in the literature. The first is solving hypergraph Laplacian systems using techniques from composite function minimization. The second expands on the recent generalization of Karger's random contraction for hypergraph mincut.
Abstract Author(s): Brett Larsen