{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T15:58:42Z","timestamp":1783439922101,"version":"3.54.6"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T00:00:00Z","timestamp":1597881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014155","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100014155","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000005","name":"U.S. Department of Defense","doi-asserted-by":"publisher","award":["Vannevar Bush Faculty Fellowship"],"award-info":[{"award-number":["Vannevar Bush Faculty Fellowship"]}],"id":[{"id":"10.13039\/100000005","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1830274"],"award-info":[{"award-number":["DMS-1830274"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF19-1-0057, MURI"],"award-info":[{"award-number":["W911NF19-1-0057, MURI"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,8,23]]},"DOI":"10.1145\/3394486.3403222","type":"proceedings-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T23:03:55Z","timestamp":1597964635000},"page":"1708-1718","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Minimizing Localized Ratio Cut Objectives in Hypergraphs"],"prefix":"10.1145","author":[{"given":"Nate","family":"Veldt","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Austin R.","family":"Benson","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jon","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,8,20]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Sameer Agarwal Kristin Branson and Serge Belongie. 2006. Higher Order Learning with Graphs. In ICML. Sameer Agarwal Kristin Branson and Serge Belongie. 2006. Higher Order Learning with Graphs. In ICML.","DOI":"10.1145\/1143844.1143847"},{"key":"e_1_3_2_1_2_1","unstructured":"Sameer Agarwal Jongwoo Lim Lihi Zelnik-Manor Pietro Perona David Kriegman and Serge Belongie. 2005. Beyond Pairwise Clustering. In CVPR. Sameer Agarwal Jongwoo Lim Lihi Zelnik-Manor Pietro Perona David Kriegman and Serge Belongie. 2005. Beyond Pairwise Clustering. In CVPR."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Reid Andersen Fan Chung and Kevin Lang. 2006. Local Graph Partitioning using PageRank Vectors. In FOCS. Reid Andersen Fan Chung and Kevin Lang. 2006. Local Graph Partitioning using PageRank Vectors. In FOCS.","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_3_2_1_4_1","volume-title":"Lang","author":"Andersen Reid","year":"2008","unstructured":"Reid Andersen and Kevin J . Lang . 2008 . An Algorithm for Improving Graph Partitions (SODA '08). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA , 651--660. http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347154 Reid Andersen and Kevin J. Lang. 2008. An Algorithm for Improving Graph Partitions (SODA '08). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 651--660. http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347154"},{"key":"e_1_3_2_1_5_1","volume-title":"Simplicial closure and higher-order link prediction. PNAS","author":"Benson Austin R","year":"2018","unstructured":"Austin R Benson , Rediet Abebe , Michael T Schaub , Ali Jadbabaie , and Jon Kleinberg . 2018. Simplicial closure and higher-order link prediction. PNAS ( 2018 ). Austin R Benson, Rediet Abebe, Michael T Schaub, Ali Jadbabaie, and Jon Kleinberg. 2018. Simplicial closure and higher-order link prediction. PNAS (2018)."},{"key":"e_1_3_2_1_6_1","volume-title":"Higher-order organization of complex networks. Science","author":"Benson Austin R.","year":"2016","unstructured":"Austin R. Benson , David F. Gleich , and Jure Leskovec . 2016. Higher-order organization of complex networks. Science ( 2016 ). Austin R. Benson, David F. Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science (2016)."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645530.757779"},{"key":"e_1_3_2_1_8_1","unstructured":"T. H. Hubert Chan and Zhibin Liang. 2018. Generalizing the Hypergraph Laplacian via a Diffusion Process with Mediators. In COCOON. T. H. Hubert Chan and Zhibin Liang. 2018. Generalizing the Hypergraph Laplacian via a Diffusion Process with Mediators. In COCOON."},{"key":"e_1_3_2_1_9_1","volume-title":"Zhihao Gavin Tang, and Chenzi Zhang","author":"Hubert Chan T.-H.","year":"2018","unstructured":"T.-H. Hubert Chan , Anand Louis , Zhihao Gavin Tang, and Chenzi Zhang . 2018 . Spectral Properties of Hypergraph Laplacian and Approximation Algorithms. JACM ( 2018). T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang. 2018. Spectral Properties of Hypergraph Laplacian and Approximation Algorithms. JACM (2018)."},{"key":"e_1_3_2_1_10_1","volume-title":"Raphael","author":"Chitra Uthsav","year":"2019","unstructured":"Uthsav Chitra and Benjamin J . Raphael . 2019 . Random Walks on Hypergraphs with Edge-Dependent Vertex Weights. In ICML. Uthsav Chitra and Benjamin J. Raphael. 2019. Random Walks on Hypergraphs with Edge-Dependent Vertex Weights. In ICML."},{"key":"e_1_3_2_1_11_1","volume-title":"Spectral Graph Theory .American Math","author":"Chung Fan R. K.","unstructured":"Fan R. K. Chung . 1997. Spectral Graph Theory .American Math . Society . Fan R. K. Chung. 1997. Spectral Graph Theory .American Math. Society."},{"key":"e_1_3_2_1_12_1","volume-title":"V\u00e9gh","author":"Ene Alina","year":"2017","unstructured":"Alina Ene , Huy Nguyen , and L\u00e1szl\u00f3 A . V\u00e9gh . 2017 . Decomposable Submodular Function Minimization: Discrete and Continuous. In NeurIPS. Alina Ene, Huy Nguyen, and L\u00e1szl\u00f3 A. V\u00e9gh. 2017. Decomposable Submodular Function Minimization: Discrete and Continuous. In NeurIPS."},{"key":"e_1_3_2_1_13_1","volume-title":"Community detection in networks: A user guide. Physics Reports","author":"Fortunato Santo","year":"2016","unstructured":"Santo Fortunato and Darko Hric . 2016. Community detection in networks: A user guide. Physics Reports ( 2016 ). Santo Fortunato and Darko Hric. 2016. Community detection in networks: A user guide. Physics Reports (2016)."},{"key":"e_1_3_2_1_14_1","unstructured":"K. Fountoulakis M. Liu D. F. Gleich and M. W. Mahoney. 2020. Flow-based Algorithms for Improving Clusters: A Unifying Framework Software and Performance. arxiv: cs.LG\/2004.09608 K. Fountoulakis M. Liu D. F. Gleich and M. W. Mahoney. 2020. Flow-based Algorithms for Improving Clusters: A Unifying Framework Software and Performance. arxiv: cs.LG\/2004.09608"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel L. Lov\u00e1sz and A. Schrijver. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica (1981). M. Gr\u00f6tschel L. Lov\u00e1sz and A. Schrijver. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica (1981).","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_16_1","volume-title":"Approximation techniques for hypergraph partitioning problems. Discrete Applied Mathematics","author":"Hadley Scott W.","year":"1995","unstructured":"Scott W. Hadley . 1995. Approximation techniques for hypergraph partitioning problems. Discrete Applied Mathematics ( 1995 ). Scott W. Hadley. 1995. Approximation techniques for hypergraph partitioning problems. Discrete Applied Mathematics (1995)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Edmund Ihler Dorothea Wagner and Frank Wagner. 1993. Modeling hypergraphs by graphs with the same mincut properties. Inform. Process. Lett. (1993). Edmund Ihler Dorothea Wagner and Frank Wagner. 1993. Modeling hypergraphs by graphs with the same mincut properties. Inform. Process. Lett. (1993).","DOI":"10.1016\/0020-0190(93)90115-P"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Jianbo Shi and J. Malik. 2000. Normalized cuts and image segmentation. TPAMI (2000). Jianbo Shi and J. Malik. 2000. Normalized cuts and image segmentation. TPAMI (2000).","DOI":"10.1109\/34.868688"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Vladimir Kolmogorov. 2012. Minimizing a Sum of Submodular Functions. Discrete Appl. Math. (2012). Vladimir Kolmogorov. 2012. Minimizing a Sum of Submodular Functions. Discrete Appl. Math. (2012).","DOI":"10.1016\/j.dam.2012.05.025"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Kevin Lang and Satish Rao. 2004. A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts. In IPCO. Kevin Lang and Satish Rao. 2004. A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts. In IPCO.","DOI":"10.1007\/978-3-540-25960-2_25"},{"key":"e_1_3_2_1_21_1","volume-title":"Cutsets and partitions of hypergraphs. Networks","author":"Lawler E. L.","year":"1973","unstructured":"E. L. Lawler . 1973. Cutsets and partitions of hypergraphs. Networks ( 1973 ). E. L. Lawler. 1973. Cutsets and partitions of hypergraphs. Networks (1973)."},{"key":"e_1_3_2_1_22_1","unstructured":"Jianbo Li Jingrui He and Yada Zhu. 2018. E-tail product return prediction via hypergraph-based local graph cut. In KDD. 519--527. Jianbo Li Jingrui He and Yada Zhu. 2018. E-tail product return prediction via hypergraph-based local graph cut. In KDD. 519--527."},{"key":"e_1_3_2_1_23_1","unstructured":"Pan Li and Olgica Milenkovic. 2017. Inhomogeneous Hypergraph Clustering with Applications. In NeurIPS. Pan Li and Olgica Milenkovic. 2017. Inhomogeneous Hypergraph Clustering with Applications. In NeurIPS."},{"key":"e_1_3_2_1_24_1","unstructured":"Pan Li and Olgica Milenkovic. 2018a. Revisiting Decomposable Submodular Function Minimization with Incidence Relations. In NeurIPS. Pan Li and Olgica Milenkovic. 2018a. Revisiting Decomposable Submodular Function Minimization with Incidence Relations. In NeurIPS."},{"key":"e_1_3_2_1_25_1","unstructured":"Pan Li and Olgica Milenkovic. 2018b. Submodular Hypergraphs: p-Laplacians Cheeger Inequalities and Spectral Clustering. In ICML. Pan Li and Olgica Milenkovic. 2018b. Submodular Hypergraphs: p-Laplacians Cheeger Inequalities and Spectral Clustering. In ICML."},{"key":"e_1_3_2_1_26_1","unstructured":"Jianmo Ni Jiacheng Li and Julian McAuley. 2019. Justifying Recommendations using Distantly-Labeled Reviews and Fine-Grained Aspects. In EMNLP-IJCNLP. Jianmo Ni Jiacheng Li and Julian McAuley. 2019. Justifying Recommendations using Distantly-Labeled Reviews and Fine-Grained Aspects. In EMNLP-IJCNLP."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Lorenzo Orecchia and Zeyuan Allen Zhu. 2014. Flow-based Algorithms for Local Graph Clustering. In SODA. Lorenzo Orecchia and Zeyuan Allen Zhu. 2014. Flow-based Algorithms for Local Graph Clustering. In SODA.","DOI":"10.1137\/1.9781611973402.94"},{"key":"e_1_3_2_1_28_1","volume-title":"A faster strongly polynomial time algorithm for submodular function minimization. Mathematical Programming","author":"Orlin James B.","year":"2009","unstructured":"James B. Orlin . 2009. A faster strongly polynomial time algorithm for submodular function minimization. Mathematical Programming ( 2009 ). James B. Orlin. 2009. A faster strongly polynomial time algorithm for submodular function minimization. Mathematical Programming (2009)."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"James B. Orlin. 2013. Max Flows in $O(nm)$ Time or Better. In STOC. James B. Orlin. 2013. Max Flows in $O(nm)$ Time or Better. In STOC.","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"e_1_3_2_1_31_1","volume-title":"A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time. J. Comb. Theory Ser. B","author":"Schrijver Alexander","year":"2000","unstructured":"Alexander Schrijver . 2000. A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time. J. Comb. Theory Ser. B ( 2000 ). Alexander Schrijver. 2000. A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time. J. Comb. Theory Ser. B (2000)."},{"key":"e_1_3_2_1_32_1","unstructured":"Peter Stobbe and Andreas Krause. 2010. Efficient Minimization of Decomposable Submodular Functions. In NeurIPS. Peter Stobbe and Andreas Krause. 2010. Efficient Minimization of Decomposable Submodular Functions. In NeurIPS."},{"key":"e_1_3_2_1_33_1","volume-title":"Austin R. Benson, and Jon Kleinberg","author":"Veldt Nate","year":"2020","unstructured":"Nate Veldt , Austin R. Benson, and Jon Kleinberg . 2020 . Hypergraph Cuts with General Splitting Functions . arxiv: cs.DS\/2001.02817 Nate Veldt, Austin R. Benson, and Jon Kleinberg. 2020. Hypergraph Cuts with General Splitting Functions. arxiv: cs.DS\/2001.02817"},{"key":"e_1_3_2_1_34_1","unstructured":"Nate Veldt David Gleich and Michael Mahoney. 2016. A Simple and Strongly-Local Flow-Based Method for Cut Improvement. In ICML. Nate Veldt David Gleich and Michael Mahoney. 2016. A Simple and Strongly-Local Flow-Based Method for Cut Improvement. In ICML."},{"key":"e_1_3_2_1_35_1","volume-title":"Gleich","author":"Veldt Nate","year":"2019","unstructured":"Nate Veldt , Christine Klymko , and David F . Gleich . 2019 . Flow-Based Local Graph Clustering with Better Seed Set Inclusion. In SDM. Nate Veldt, Christine Klymko, and David F. Gleich. 2019. Flow-Based Local Graph Clustering with Better Seed Set Inclusion. In SDM."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Dorothea Wagner and Frank Wagner. 1993. Between min cut and graph bisection. In MFCS. Dorothea Wagner and Frank Wagner. 1993. Between min cut and graph bisection. In MFCS.","DOI":"10.1007\/3-540-57182-5_65"},{"key":"e_1_3_2_1_37_1","unstructured":"Naganand Yadati Madhav Nimishakavi Prateek Yadav Vikram Nitin Anand Louis and Partha Talukdar. 2019. HyperGCN: A New Method For Training Graph Convolutional Networks on Hypergraphs. In NeurIPS. Naganand Yadati Madhav Nimishakavi Prateek Yadav Vikram Nitin Anand Louis and Partha Talukdar. 2019. HyperGCN: A New Method For Training Graph Convolutional Networks on Hypergraphs. In NeurIPS."},{"key":"e_1_3_2_1_38_1","volume-title":"Jure Leskovec, and David F. Gleich.","author":"Yin Hao","year":"2017","unstructured":"Hao Yin , Austin R. Benson , Jure Leskovec, and David F. Gleich. 2017 . Local Higher-Order Graph Clustering. In KDD. Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. 2017. Local Higher-Order Graph Clustering. In KDD."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Dengyong Zhou Jiayuan Huang and Bernhard Sch\u00f6lkopf. 2006. Learning with Hypergraphs: Clustering Classification and Embedding. In NeurIPS. Dengyong Zhou Jiayuan Huang and Bernhard Sch\u00f6lkopf. 2006. Learning with Hypergraphs: Clustering Classification and Embedding. In NeurIPS.","DOI":"10.7551\/mitpress\/7503.003.0205"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"J. Y. Zien M. D. F. Schlag and P. K. Chan. 1999. Multilevel spectral hypergraph partitioning with arbitrary vertex sizes. IEEE TCAD (1999). J. Y. Zien M. D. F. Schlag and P. K. Chan. 1999. Multilevel spectral hypergraph partitioning with arbitrary vertex sizes. IEEE TCAD (1999).","DOI":"10.1109\/43.784130"}],"event":{"name":"KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Virtual Event CA USA","acronym":"KDD '20","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3394486.3403222","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3394486.3403222","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3394486.3403222","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:46Z","timestamp":1750197706000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3394486.3403222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,20]]},"references-count":40,"alternative-id":["10.1145\/3394486.3403222","10.1145\/3394486"],"URL":"https:\/\/doi.org\/10.1145\/3394486.3403222","relation":{},"subject":[],"published":{"date-parts":[[2020,8,20]]},"assertion":[{"value":"2020-08-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}