2020/07/15 by Austin R. Benson, Jon Kleinberg, Benson, Austin R. +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2007.08075
openalex publication_date 2020/07/15 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In recent years, hypergraph generalizations of many graph cut problems have\nbeen introduced and analyzed as a way to better explore and understand complex\nsystems and datasets characterized by multiway relationships. Recent work has\nmade use of a generalized hypergraph cut function which for a hypergraph\n\H = (V,E) can be defined by associating each hyperedge e \∈ E\nwith a splitting function bf we, which assigns a penalty to each way of\nseparating the nodes of e. When each bf we is a submodular\ncardinality-based splitting function, meaning that bf we(S) = g(|S|) for\nsome concave function g, previous work has shown that a generalized\nhypergraph cut problem can be reduced to a directed graph cut problem on an\naugmented node set. However, existing reduction procedures often result in a\ndense graph, even when the hypergraph is sparse, which leads to slow runtimes\nfor algorithms that run on the reduced graph.\n We introduce a new framework of sparsifying hypergraph-to-graph reductions,\nwhere a hypergraph cut defined by submodular cardinality-based splitting\nfunctions is (1+\ε)-approximated by a cut on a directed graph. Our\ntechniques are based on approximating concave functions using piecewise linear\ncurves. For \ε > 0 we need at most O(\ε-1|e| \log |e|)\nedges to reduce any hyperedge e, which leads to faster runtimes for\napproximating generalized hypergraph s-t cut problems. For the machine\nlearning heuristic of a clique splitting function, our approach requires only\nO(|e| \ε-1/2 \log \log \(1)/(\ε)) edges. This\nsparsification leads to faster approximate min s-t graph cut algorithms for\ncertain classes of co-occurrence graphs. Finally, we apply our sparsification\ntechniques to develop approximation algorithms for minimizing sums of\ncardinality-based submodular functions.\n