Hypergraph cuts with general splitting functions. (English) Zbl 1494.05080
Summary: The minimum \(s\)-\(t\) cut problem in graphs is one of the most fundamental problems in combinatorial optimization, and graph cuts underlie algorithms throughout discrete mathematics, theoretical computer science, operations research, and data science. While graphs are a standard model for pairwise relationships, hypergraphs provide the flexibility to model multiway relationships and are now a standard model for complex data and systems. However, when generalizing from graphs to hypergraphs, the notion of a “cut hyperedge” is less clear, as a hyperedge’s node can be split in several ways. Here, we develop a framework for hypergraph cuts by considering the problem of separating two terminal nodes in a hypergraph in a way that minimizes a sum of penalties at split hyperedges. In our setup, different ways of splitting the same hyperedge have different penalties, and the penalty is encoded by what we call a splitting function.
Our framework opens a rich space on the foundations of hypergraph cuts. We first identify a natural class of cardinality-based hyperedge splitting functions that depend only on the number of nodes on each side of the split. In this case, we show that the general hypergraph \(s\)-\(t\) cut problem can be reduced to a tractable graph \(s\)-\(t\) cut problem if and only if the splitting functions are submodular. We also identify a wide regime of non-submodular splitting functions for which the problem is NP-hard. Finally, we outline several open questions on general hypergraph cut problems.
Our framework opens a rich space on the foundations of hypergraph cuts. We first identify a natural class of cardinality-based hyperedge splitting functions that depend only on the number of nodes on each side of the split. In this case, we show that the general hypergraph \(s\)-\(t\) cut problem can be reduced to a tractable graph \(s\)-\(t\) cut problem if and only if the splitting functions are submodular. We also identify a wide regime of non-submodular splitting functions for which the problem is NP-hard. Finally, we outline several open questions on general hypergraph cut problems.
MSC:
| 05C65 | Hypergraphs |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C27 | Combinatorial optimization |
References:
| [1] | S. Agarwal, K. Branson, and S. Belongie, Higher order learning with graphs, in Proceedings of the 23rd International Conference on Machine Learning, ICML ’06, ACM, 2006, pp. 17-24, http://doi.acm.org/10.1145/1143844.1143847. |
| [2] | S. Agarwal, J. Lim, L. Zelnik-Manor, P. Perona, D. Kriegman, and S. Belongie, Beyond pairwise clustering, in Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR ’05, IEEE Computer Society, 2005, pp. 838-845, https://doi.org/10.1109/CVPR.2005.89. |
| [3] | K. Akbudak and C. Aykanat, Simultaneous input and output matrix partitioning for outer-product-parallel sparse matrix-matrix multiplication, SIAM J. Sci. Comput., 36 (2014), pp. C568-C590, https://doi.org/10.1137/13092589X. · Zbl 1307.65050 |
| [4] | K. Akbudak, E. Kayaaslan, and C. Aykanat, Hypergraph partitioning based models and methods for exploiting cache locality in sparse matrix-vector multiplication, SIAM J. Sci. Comput., 35 (2013), pp. C237-C262, https://doi.org/10.1137/100813956. · Zbl 1278.65047 |
| [5] | R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys., 74 (2002), pp. 47-97, https://link.aps.org/doi/10.1103/RevModPhys.74.47. · Zbl 1205.82086 |
| [6] | C. Alpert, J.-H. Huang, and A. Kahng, Multilevel circuit partitioning, IEEE Trans. Computer-Aided Des. Integrated Circuits Syst., 17 (1998), pp. 655-667, https://doi.org/10.1109/43.712098. |
| [7] | C. J. Alpert and A. B. Kahng, Recent directions in netlist partitioning: A survey, Integration, 19 (1995), pp. 1-81, http://www.sciencedirect.com/science/article/pii/0167926095000084. · Zbl 0876.94063 |
| [8] | R. Andersen and K. J. Lang, An algorithm for improving graph partitions, in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, SIAM, 2008, pp. 651-660, http://dl.acm.org/citation.cfm?id=1347082.1347154. · Zbl 1192.68868 |
| [9] | G. Ballard, A. Druinsky, N. Knight, and O. Schwartz, Hypergraph partitioning for sparse matrix-matrix multiplication, ACM Trans. Parallel Comput., 3 (2016), pp. 18:1-18:34, http://doi.acm.org/10.1145/3015144. |
| [10] | D. S. Bassett, N. F. Wymbs, M. A. Porter, P. J. Mucha, and S. T. Grafton, Cross-linked structure of network evolution, Chaos, 24 (2014), art. 013112, https://doi.org/10.1063/1.4858457. · Zbl 1374.34103 |
| [11] | A. R. Benson, Three hypergraph eigenvector centralities, SIAM J. Math. Data Sci., 1 (2019), pp. 293-312, https://doi.org/10.1137/18m1203031. · Zbl 1499.05432 |
| [12] | A. R. Benson, R. Abebe, M. T. Schaub, A. Jadbabaie, and J. Kleinberg, Simplicial closure and higher-order link prediction, Proc. Natl. Acad. Sci. USA, 115 (2018), pp. E11221-E11230, https://www.pnas.org/content/115/48/E11221. |
| [13] | A. R. Benson, D. F. Gleich, and J. Leskovec, Higher-order organization of complex networks, Science, 353 (2016), pp. 163-166, http://science.sciencemag.org/content/353/6295/163. |
| [14] | A. L. Bertozzi and A. Flenner, Diffuse interface models on graphs for classification of high dimensional data, SIAM Rev., 58 (2016), pp. 293-328, https://doi.org/10.1137/16M1070426. · Zbl 1339.68287 |
| [15] | A. Blum and S. Chawla, Learning from labeled and unlabeled data using graph mincuts, in Proceedings of the Eighteenth International Conference on Machine Learning, ICML ’01, Morgan Kaufmann, 2001, pp. 19-26, http://dl.acm.org/citation.cfm?id=645530.757779. |
| [16] | Y. Boykov and V. Kolmogorov, An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, IEEE Trans. Pattern Anal. Mach. Intell., 26 (2004), pp. 1124-1137, https://doi.org/10.1109/TPAMI.2004.60. · Zbl 1005.68964 |
| [17] | Ü. V. Çatalyürek and C. Aykanat, Hypergraph model for mapping repeated sparse matrix-vector product computations onto multicomputers, in Proceedings of International Conference on High Performance Computing, 1995. |
| [18] | Ü. V. Çatalyürek and C. Aykanat, PaToH (partitioning tool for hypergraphs), in Encyclopedia of Parallel Computing, Springer, 2011, pp. 1479-1487. |
| [19] | Ü. V. Çatalyürek, C. Aykanat, and E. Kayaaslan, Hypergraph partitioning-based fill-reducing ordering for symmetric matrices, SIAM J. Sci. Comput., 33 (2011), pp. 1996-2023, https://doi.org/10.1137/090757575. · Zbl 1410.65077 |
| [20] | Ü. V. Çatalyürek, C. Aykanat, and B. Uçar, On two-dimensional sparse matrix partitioning: Models, methods, and a recipe, SIAM J. Sci. Comput., 32 (2010), pp. 656-683, https://doi.org/10.1137/080737770. · Zbl 1298.05198 |
| [21] | A. Cevahir, A. Nukada, and S. Matsuoka, High performance conjugate gradient solver on multi-GPU clusters using hypergraph partitioning, Comput. Sci. Res. Develop., 25 (2010), pp. 83-91, https://doi.org/10.1007/s00450-010-0112-6. |
| [22] | K. Chandrasekara, C. Xu, and X. Yu, Hypergraph \(k\)-cut in randomized polynomial time, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, SIAM, 2018, pp. 1426-1438, https://doi.org/10.1137/1.9781611975031.94. · Zbl 1403.68152 |
| [23] | C. Chekuri and V. Madan, Simple and fast rounding algorithms for directed and node-weighted multiway cut, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’16, SIAM, 2016, pp. 797-807, https://doi.org/10.1137/1.9781611974331.ch57. · Zbl 1410.05197 |
| [24] | P. S. Chodrow, N. Veldt, and A. R. Benson, Generative hypergraph clustering: From blockmodels to modularity, Sci. Adv., 7 (2021), art. eabh1303, https://www.science.org/doi/abs/10.1126/sciadv.abh1303. |
| [25] | J. Cong and S. K. Lim, Multiway partitioning with pairwise movement, in 1998 IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers (IEEE Cat. No.98CB36287), 1998, pp. 512-516. |
| [26] | W. H. Cunningham, Minimum cuts, modular functions, and matroid polyhedra, Networks, 15 (1985), pp. 205-215, https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230150206. · Zbl 0581.90059 |
| [27] | N. R. Devanur, S. Dughmi, R. Schwartz, A. Sharma, and M. Singh, On the Approximation of Submodular Functions, preprint, https://arxiv.org/abs/1304.4948, 2013. |
| [28] | K. Devine, E. Boman, R. Heaphy, R. Bisseling, and U. Catalyurek, Parallel hypergraph partitioning for scientific computing, in Proceedings of the 20th IEEE International Parallel Distributed Processing Symposium, 2006, art. 1639359, https://doi.org/10.1109/IPDPS.2006.1639359. |
| [29] | E. A. Dinic, Algorithm for solution of a problem of maximum flow in networks with power estimation, Soviet Math. Dokl., 11 (1970), pp. 1277-1280. · Zbl 0219.90046 |
| [30] | D. Easley and J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010. · Zbl 1205.91007 |
| [31] | J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19 (1972), pp. 248-264, https://doi.org/10.1145/321694.321699. · Zbl 0318.90024 |
| [32] | A. Ene, H. Nguyen, and L. A. Végh, Decomposable submodular function minimization: Discrete and continuous, in Proceedings of the 2017 International Conference on Neural Information Processing Systems, NIPS ’17, Curran Associates, 2017, pp. 2870-2880, http://papers.nips.cc/paper/6880-decomposable-submodular-function-minimization-discrete-and-continuous.pdf. |
| [33] | E. Estrada and J. A. Rodríguez-Velázquez, Subgraph centrality and clustering in complex hyper-networks, Phys. A, 364 (2006), pp. 581-594, https://doi.org/10.1016/j.physa.2005.12.002. |
| [34] | S. Even and R. E. Tarjan, Network flow and testing graph connectivity, SIAM J. Comput., 4 (1975), pp. 507-518, https://doi.org/10.1137/0204043. · Zbl 0328.90031 |
| [35] | D. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, 2010. · Zbl 0139.13701 |
| [36] | K. Fountoulakis, M. Liu, D. F. Gleich, and M. W. Mahoney, Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance, preprint, https://arxiv.org/abs/2004.09608, 2020. |
| [37] | D. Freedman and P. Drineas, Energy minimization via graph cuts: Settling what is possible, in 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR ’05, Vol. 2, 2005, pp. 939-946. |
| [38] | S. Fujishige and S. B. Patkar, Realization of set functions as cut functions of graphs and hypergraphs, Discrete Math., 226 (2001), pp. 199-210, http://www.sciencedirect.com/science/article/pii/S0012365X00001643. · Zbl 0969.90015 |
| [39] | Y. Gao, Y. P. Liu, and R. Peng, Fully dynamic electrical flows: Sparse maxflow faster than Goldberg-Rao, in 62nd Annual IEEE Symposium on Foundations of Computer Science, FOCS ’21, 2021, pp. 516-527, https://arxiv.org/abs/2101.07233. |
| [40] | N. Garg, V. V. Vazirani, and M. Yannakakis, Multiway cuts in directed and node weighted graphs, in Automata, Languages and Programming, S. Abiteboul and E. Shamir, eds., Springer, Berlin, Heidelberg, 1994, pp. 487-498, https://doi.org/10.1007/3-540-58201-0_92. · Zbl 1418.68168 |
| [41] | A. V. Goldberg, Finding a Maximum Density Subgraph, Tech. Report UCB/CSD-84-171, University of California at Berkeley, 1984. |
| [42] | A. V. Goldberg and R. E. Tarjan, A new approach to the maximum flow problem, in Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC ’86, ACM, 1986, pp. 136-146, http://doi.acm.org/10.1145/12130.12144. |
| [43] | V. M. Govindu, A tensor decomposition for geometric grouping and segmentation, in 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR ’05, Vol. 1, 2005, pp. 1150-1157, https://doi.org/10.1109/CVPR.2005.50. |
| [44] | M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), pp. 169-197, https://doi.org/10.1007/BF02579273. · Zbl 0492.90056 |
| [45] | M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Vol. 2, Springer Science & Business Media, 2012. · Zbl 0837.05001 |
| [46] | S. W. Hadley, Approximation techniques for hypergraph partitioning problems, Discrete Appl. Math., 59 (1995), pp. 115-127, http://www.sciencedirect.com/science/article/pii/0166218X93E0166V. · Zbl 0824.05048 |
| [47] | S. W. Hadley, B. L. Mark, and A. Vannelli, An efficient eigenvector approach for finding netlist partitions, IEEE Trans. Computer-Aided Des. Integrated Circuits Sys., 11 (1992), pp. 885-892, https://doi.org/10.1109/43.144852. |
| [48] | M. Hein, S. Setzer, L. Jost, and S. S. Rangapuram, The total variation on hypergraphs-learning on hypergraphs revisited, in Proceedings of the 2013 International Conference on Neural Information Processing Systems, NIPS ’13, Curran Associates, 2013, pp. 2427-2435, http://dl.acm.org/citation.cfm?id=2999792.2999883. |
| [49] | T. Heuer, P. Sanders, and S. Schlag, Network flow-based refinement for multilevel hypergraph partitioning, in 17th International Symposium on Experimental Algorithms, SEA ’18, G. D’Angelo, ed., LIPIcs. Leibniz Int. Proc. Inform. 103, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018, art. 1, http://drops.dagstuhl.de/opus/volltexte/2018/8936. · Zbl 1492.68105 |
| [50] | T. Hu and K. Moerder, Multiterminal flows in a hypergraph, in VLSI Circuit Layout: Theory and Design, IEEE Press, 1985, pp. 87-93. |
| [51] | T. Hu, H. Xiong, W. Zhou, S. Y. Sung, and H. Luo, Hypergraph partitioning for document clustering: A unified clique perspective, in Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’08, ACM, 2008, pp. 871-872, https://doi.acm.org/10.1145/1390334.1390548. |
| [52] | J. Huang, R. Zhang, and J. X. Yu, Scalable hypergraph learning and processing, in Proceedings of the 2015 IEEE International Conference on Data Mining, ICDM ’15, IEEE Computer Society, 2015, pp. 775-780, https://doi.org/10.1109/ICDM.2015.33. |
| [53] | Y. Huang, Q. Liu, and D. Metaxas, Video object segmentation by hypergraph cut, in 2009 IEEE Conference on Computer Vision and Pattern Recognition, CVPR ’09, 2009, pp. 1738-1745, https://doi.org/10.1109/CVPR.2009.5206795. |
| [54] | E. Ihler, D. Wagner, and F. Wagner, Modeling hypergraphs by graphs with the same mincut properties, Inform. Process. Lett., 45 (1993), pp. 171-175, http://www.sciencedirect.com/science/article/pii/002001909390115P. · Zbl 0768.68147 |
| [55] | S. Iwata, L. Fleischer, and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, J. ACM, 48 (2001), pp. 761-777, https://doi.org/10.1145/502090.502096. · Zbl 1127.90402 |
| [56] | S. Iwata and J. B. Orlin, A simple combinatorial algorithm for submodular function minimization, in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’09, SIAM, 2009, pp. 1230-1237, https://doi.org/10.1137/1.9781611973068.133. · Zbl 1423.90226 |
| [57] | S. Jegelka, F. Bach, and S. Sra, Reflection methods for user-friendly submodular optimization, in Proceedings of the 2013 International Conference on Neural Information Processing Systems, NeurIPS ’13, Curran Associates, 2013, pp. 1313-1321. |
| [58] | S. Jegelka, H. Lin, and J. A. Bilmes, On fast approximate submodular minimization, in Proceedings of the 2011 International Conference on Neural Information Processing Systems, NIPS ’11, Curran Associates, 2011, pp. 460-468, http://papers.nips.cc/paper/4348-on-fast-approximate-submodular-minimization.pdf. |
| [59] | G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, Multilevel hypergraph partitioning: Applications in VLSI domain, IEEE Trans. Very Large Scale Integration (VLSI) Systems, 7 (1999), pp. 69-79, https://doi.org/10.1109/92.748202. |
| [60] | G. Karypis and V. Kumar, Multilevel k-way hypergraph partitioning, in Proceedings of the 36th Annual ACM/IEEE Design Automation Conference, DAC ’99, ACM, 1999, pp. 343-348, http://doi.acm.org/10.1145/309847.309954. · Zbl 0918.68073 |
| [61] | E. Kayaaslan, A. Pinar, Ü. Çatalyürek, and C. Aykanat, Partitioning hypergraphs in scientific computing applications through vertex separators on graphs, SIAM J. Sci. Comput., 34 (2012), pp. A970-A992, https://doi.org/10.1137/100810022. · Zbl 1245.05104 |
| [62] | J. A. Kelner, Y. T. Lee, L. Orecchia, and A. Sidford, An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations, in Proceedings of the Twenty-Fourth ACM-SIAM Symposium on Discrete Algorithms, SODA ’13, SIAM, 2013, pp. 217-226, https://doi.org/10.1137/1.9781611973402.16. · Zbl 1423.05177 |
| [63] | S. Kim, S. Nowozin, P. Kohli, and C. D. Yoo, Higher-order correlation clustering for image segmentation, in Proceedings of the 2011 International Conference on Neural Information Processing Systems, NIPS ’11, Curran Associates, 2011, pp. 1530-1538, http://papers.nips.cc/paper/4406-higher-order-correlation-clustering-for-image-segmentation.pdf. |
| [64] | V. King, S. Rao, and R. Tarjan, A faster deterministic maximum flow algorithm, in Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’92, SIAM, 1992, pp. 157-164, http://dl.acm.org/citation.cfm?id=139404.139438. · Zbl 0829.68094 |
| [65] | P. Kohli, P. H. Torr, et al., Robust higher order potentials for enforcing label consistency, Internat. J. Computer Vis., 82 (2009), pp. 302-324. |
| [66] | V. Kolmogorov, Minimizing a sum of submodular functions, Discrete Appl. Math., 160 (2012), pp. 2246-2258. · Zbl 1274.90461 |
| [67] | V. Kolmogorov and R. Zabin, What energy functions can be minimized via graph cuts?, IEEE Trans. Pattern Anal. Machine Intell., 26 (2004), pp. 147-159, https://doi.org/10.1109/TPAMI.2004.1262177. |
| [68] | R. Lambiotte, M. Rosvall, and I. Scholtes, From networks to optimal higher-order models of complex systems, Nature Phys., 15 (2019), pp. 313-320, https://doi.org/10.1038/s41567-019-0459-y. |
| [69] | K. Lang and S. Rao, A flow-based method for improving the expansion or conductance of graph cuts, in International Conference on Integer Programming and Combinatorial Optimization, IPCO ’04, Springer, Berlin, Heidelberg, 2004, pp. 325-337, https://doi.org/10.1007/978-3-540-25960-2_25. · Zbl 1092.68631 |
| [70] | E. L. Lawler, Cutsets and partitions of hypergraphs, Networks, 3 (1973), pp. 275-285, https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230030306. · Zbl 0262.05126 |
| [71] | Y. T. Lee and A. Sidford, Path finding methods for linear programming: Solving linear programs in \(\tilde{O}\sqrt{rank}\) iterations and faster algorithms for maximum flow, in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS ’14, IEEE, 2014, pp. 424-433. |
| [72] | P. Li and O. Milenkovic, Inhomogeneous hypergraph clustering with applications, in Proceedings of the 2017 International Conference on Neural Information Processing Systems, NIPS ’17, Curran Associates, 2017, pp. 2308-2318, http://papers.nips.cc/paper/6825-inhomogeneous-hypergraph-clustering-with-applications.pdf. |
| [73] | P. Li and O. Milenkovic, Revisiting decomposable submodular function minimization with incidence relations, in Proceedings of the 2018 International Conference on Neural Information Processing Systems, NIPS ’18, Curran Associates, 2018, pp. 2242-2252. |
| [74] | P. Li and O. Milenkovic, Submodular hypergraphs: p-Laplacians, Cheeger inequalities and spectral clustering, in International Conference on Machine Learning, 2018, pp. 3020-3029, http://proceedings.mlr.press/v80/li18e/li18e.pdf. |
| [75] | H. Liu and D. F. Wong, Network-flow-based multiway partitioning with area and pin constraints, IEEE Trans. Computer-Aided Des. Integrated Circuits Syst., 17 (1998), pp. 50-59, https://doi.org/10.1109/43.673632. |
| [76] | M. Liu, N. Veldt, H. Song, P. Li, and D. F. Gleich, Strongly local hypergraph diffusions for clustering and semi-supervised learning, in Proceedings of the Web Conference 2021, WWW ’21, 2021, pp. 2092-2103, https://doi.org/10.1145/3442381.3449887. |
| [77] | T. Michoel and B. Nachtergaele, Alignment and integration of complex networks by hypergraph-based spectral clustering, Phys. Rev. E, 86 (2012), art. 056111, https://link.aps.org/doi/10.1103/PhysRevE.86.056111. |
| [78] | L. Neuhäuser, A. Mellor, and R. Lambiotte, Multibody interactions and nonlinear consensus dynamics on networked systems, Phys. Rev. E, 101 (2020), art. 032310, https://doi.org/10.1103/PhysRevE.101.032310. |
| [79] | M. E. J. Newman, The structure and function of complex networks, SIAM Rev., 45 (2003), pp. 167-256, https://doi.org/10.1137/S003614450342480. · Zbl 1029.68010 |
| [80] | P. Ochs and T. Brox, Higher order motion models and spectral clustering, in 2012 IEEE Conference on Computer Vision and Pattern Recognition, CVPR ’12, 2012, pp. 614-621, https://doi.org/10.1109/CVPR.2012.6247728. |
| [81] | L. Orecchia and Z. A. Zhu, Flow-based algorithms for local graph clustering, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, SIAM, 2014, pp. 1267-1286, http://dl.acm.org/citation.cfm?id=2634074.2634168. · Zbl 1422.68311 |
| [82] | J. B. Orlin, A faster strongly polynomial time algorithm for submodular function minimization, Math. Program., 118 (2009), pp. 237-251, https://doi.org/10.1007/s10107-007-0189-2. · Zbl 1179.90290 |
| [83] | J. B. Orlin, Max flows in \(O(nm)\) time, or better, in Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, ACM, 2013, pp. 765-774, https://doi.org/10.1145/2488608.2488705. · Zbl 1293.05151 |
| [84] | R. Peng, Approximate undirected maximum flows in \(O(m{polylog}(n))\) time, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’16, SIAM, 2016, pp. 1862-1867, https://doi.org/10.1137/1.9781611974331.ch130. · Zbl 1410.68306 |
| [85] | M. A. Porter, Nonlinearity + networks: A 2020 vision, in Emerging Frontiers in Nonlinear Science, P. G. Kevrekidis, J. Cuevas-Maraver, and A. Saxena, eds., Springer, Cham, 2020, pp. 131-159, https://doi.org/10.1007/978-3-030-44992-6_6. · Zbl 1435.00056 |
| [86] | P. Purkait, T. Chin, A. Sadri, and D. Suter, Clustering with hypergraphs: The case for large hyperedges, IEEE Trans. Pattern Anal. Mach. Intell., 39 (2017), pp. 1697-1711, https://doi.org/10.1109/TPAMI.2016.2614980. |
| [87] | T. J. Schaefer, The complexity of satisfiability problems, in Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, ACM, 1978, pp. 216-226, http://doi.acm.org/10.1145/800133.804350. · Zbl 1282.68143 |
| [88] | S. Schlag, V. Henne, T. Heuer, H. Meyerhenke, P. Sanders, and C. Schulz, k-way hypergraph partitioning via n-level recursive bisection, in Proceedings of the Meeting on Algorithm Engineering and Experiments, ALENEX ’16, 2016, pp. 53-67, https://epubs.siam.org/doi/abs/10.1137/1.9781611974317.5. · Zbl 1430.68239 |
| [89] | A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B, 80 (2000), pp. 346-355, https://doi.org/10.1006/jctb.2000.1989. · Zbl 1052.90067 |
| [90] | N. Selvakkumaran and G. Karypis, Multiobjective hypergraph-partitioning algorithms for cut and maximum subdomain-degree minimization, IEEE Trans. Computer-Aided Des. Integrated Circuits Syst., 25 (2006), pp. 504-517, https://doi.org/10.1109/tcad.2005.854637. |
| [91] | I. Shanu, C. Arora, and P. Singla, Min norm point algorithm for higher order MRF-MAP inference, in 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR ’16, 2016, pp. 5365-5374. |
| [92] | J. Sherman, Nearly maximum flows in nearly linear time, in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS ’13, 2013, pp. 263-269, https://doi.org/10.1109/FOCS.2013.36. |
| [93] | P. Stobbe and A. Krause, Efficient minimization of decomposable submodular functions, in Proceedings of the 2010 International Conference on Neural Information Processing Systems, NIPS ’10, Curran Associates, 2010, pp. 2208-2216. |
| [94] | W.-J. Sun and C. Sechen, Efficient and effective placement for very large circuits, IEEE Trans. Computer-Aided Des. Integrated Circuits Syst., 14 (1995), pp. 349-359, https://doi.org/10.1109/43.365125. |
| [95] | Z. Tian, T. Hwang, and R. Kuang, A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge, Bioinform., 25 (2009), pp. 2831-2838, https://doi.org/10.1093/bioinformatics/btp467. |
| [96] | B. Uçar and C. Aykanat, Revisiting hypergraph models for sparse matrix partitioning, SIAM Rev., 49 (2007), pp. 595-603, https://doi.org/10.1137/060662459. · Zbl 1130.65061 |
| [97] | J. van den Brand, Y. T. Lee, Y. P. Liu, T. Saranurak, A. Sidford, Z. Song, and D. Wang, Minimum cost flows, MDPs, and \(\ell_1\)-regression in nearly linear time for dense instances, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, ACM, 2021, pp. 859-869, https://doi.org/10.1145/3406325.3451108. · Zbl 07765216 |
| [98] | A. Vannelli and S. W. Hadley, A Gomory-Hu cut tree representation of a netlist partitioning problem, IEEE Trans. Circuits Syst., 37 (1990), pp. 1133-1139, https://doi.org/10.1109/31.57601. · Zbl 0733.94027 |
| [99] | N. Veldt, A. R. Benson, and J. Kleinberg, Hypergraph Cuts with General Splitting Functions, preprint, https://arxiv.org/abs/2001.02817, 2020. |
| [100] | N. Veldt, A. R. Benson, and J. Kleinberg, Minimizing localized ratio cut objectives in hypergraphs, in Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’20, ACM, 2020, pp. 1708-1718, https://doi.org/10.1145/3394486.3403222. |
| [101] | N. Veldt, A. R. Benson, and J. Kleinberg, Approximate decomposable submodular function minimization for cardinality-based components, in Proceedings of the 2021 International Conference on Neural Information Processing Systems, NeurIPS ’21, 2021, pp. 3744-3756, https://arxiv.org/abs/2110.14859. |
| [102] | N. Veldt, D. Gleich, and M. Mahoney, A simple and strongly-local flow-based method for cut improvement, in Proceedings of the 33rd International Conference on Machine Learning, ICML ’16, Vol. 48, PMLR, 2016, pp. 1938-1947, http://proceedings.mlr.press/v48/veldt16.html. |
| [103] | N. Yadati, M. Nimishakavi, P. Yadav, V. Nitin, A. Louis, and P. Talukdar, HyperGCN: A new method for training graph convolutional networks on hypergraphs, in Proceedings of the 2019 International Conference on Neural Information Processing Systems, NeurIPS ’19, Curran Associates, 2019, pp. 1509-1520, https://proceedings.neurips.cc/paper/2019/file/1efa39bcaec6f3900149160693694536-Paper.pdf. |
| [104] | Y. Yamaguchi, Realizing symmetric set functions as hypergraph cut capacity, Discrete Math., 339 (2016), pp. 2007-2017, https://doi.org/10.1016/j.disc.2016.02.010. · Zbl 1336.05145 |
| [105] | H. H. Yang and D. F. Wong, Efficient network flow based min-cut balanced partitioning, IEEE Trans. Computer-Aided Des. Integrated Circuits Syst., 15 (1996), pp. 1533-1540, https://doi.org/10.1109/43.552086. |
| [106] | J. R. Yaros and T. Imielinski, Imbalanced hypergraph partitioning and improvements for consensus clustering, in 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, 2013, pp. 358-365, https://doi.org/10.1109/ICTAI.2013.61. |
| [107] | D. Zhou, J. Huang, and B. Schölkopf, Learning with hypergraphs: Clustering, classification, and embedding, in Proceedings of the 2006 International Conference on Neural Information Processing Systems, NIPS ’06, MIT Press, 2006, pp. 1601-1608, http://dl.acm.org/citation.cfm?id=2976456.2976657. |
| [108] | J. Y. Zien, M. D. F. Schlag, and P. K. Chan, Multilevel spectral hypergraph partitioning with arbitrary vertex sizes, IEEE Trans. Computer-Aided Des. Integrated Circuits Syst., 18 (1999), pp. 1389-1399, https://doi.org/10.1109/43.784130. |
| [109] | S. Živnỳ, D. A. Cohen, and P. G. Jeavons, The expressive power of binary submodular functions, Discrete Appl. Math., 157 (2009), pp. 3347-3358. · Zbl 1229.90093 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
