{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:31:02Z","timestamp":1765546262814},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2017,12,2]],"date-time":"2017-12-02T00:00:00Z","timestamp":1512172800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1007\/s10107-017-1214-8","type":"journal-article","created":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T22:40:32Z","timestamp":1512168032000},"page":"553-573","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Variational perspective on local graph clustering"],"prefix":"10.1007","volume":"174","author":[{"given":"Kimon","family":"Fountoulakis","sequence":"first","affiliation":[]},{"given":"Farbod","family":"Roosta-Khorasani","sequence":"additional","affiliation":[]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[]},{"given":"Xiang","family":"Cheng","sequence":"additional","affiliation":[]},{"given":"Michael W.","family":"Mahoney","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,2]]},"reference":[{"key":"1214_CR1","doi-asserted-by":"crossref","unstructured":"Andersen, R., Chung, F., Lang, K.: Local graph partitioning using pagerank vectors. In: FOCS \u201906 Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 475\u2013486 (2006)","DOI":"10.1109\/FOCS.2006.44"},{"key":"1214_CR2","unstructured":"Andersen, R., Lang, K.: An algorithm for improving graph partitions. In: SODA \u201908 Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 651\u2013660 (2008)"},{"issue":"2","key":"1214_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 5 (2009)","journal-title":"J. ACM"},{"issue":"1","key":"1214_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"key":"1214_CR5","doi-asserted-by":"crossref","unstructured":"Cheeger, J.: A lower bound for the smallest eigenvalue of the Laplacian. In: Problems in Analysis, Papers Dedicated to Salomon Bochner, pp. 195\u2013199. Princeton University Press (1969)","DOI":"10.1515\/9781400869312-013"},{"key":"1214_CR6","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.laa.2006.07.018","volume":"423","author":"F Chung","year":"2007","unstructured":"Chung, F.: Random walks and local cuts in graphs. Linear Algebra Appl. 423, 22\u201332 (2007)","journal-title":"Linear Algebra Appl."},{"key":"1214_CR7","unstructured":"Dhillon, I.S., Ravikumar, P.K., Tewari, A.: Nearest neighbor based greedy coordinate descent. In: Advances in Neural Information Processing Systems 24 (NIPS 2011) (2011)"},{"key":"1214_CR8","doi-asserted-by":"crossref","unstructured":"Eiron, N., McCurley, K.S., Tomlin, J.A.: Ranking the web frontier. In: Proceedings of the 13th International Conference on World Wide Web, pp. 309\u2013318 (2004)","DOI":"10.1145\/988672.988714"},{"key":"1214_CR9","unstructured":"Fountoulakis, K., Cheng, X., Shun, J., Roosta-Khorasani, F., Mahoney, M.W.: Exploiting optimization for local graph clustering. Technical report. Preprint arXiv:1602.01886 (2016)"},{"issue":"3","key":"1214_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1137\/140976649","volume":"57","author":"DF Gleich","year":"2015","unstructured":"Gleich, D.F.: Pagerank beyond the web. SIAM Rev. 57(3), 321\u2013363 (2015)","journal-title":"SIAM Rev."},{"key":"1214_CR11","unstructured":"Gleich, D.F., Mahoney, M.W.: Anti-differentiating approximation algorithms: a case study with min-cuts, spectral, and flow. In: Proceedings of the 31st International Conference on Machine Learning, pp. 1018\u20131025 (2014)"},{"issue":"6","key":"1214_CR12","doi-asserted-by":"publisher","first-page":"1844","DOI":"10.1137\/040609008","volume":"27","author":"L Grady","year":"2006","unstructured":"Grady, L., Schwartz, E.L.: Isoperimetric partitioning:a new algorithm for graph partitioning. SIAM J. Sci. Comput. 27(6), 1844\u20131866 (2006)","journal-title":"SIAM J. Sci. Comput."},{"issue":"3","key":"1214_CR13","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1287\/mnsc.17.3.219","volume":"17","author":"KM Hall","year":"1970","unstructured":"Hall, K.M.: An r-dimensional quadratic placement algorithm. Manag. Sci. 17(3), 219\u2013229 (1970)","journal-title":"Manag. Sci."},{"issue":"1","key":"1214_CR14","doi-asserted-by":"publisher","first-page":"012,821","DOI":"10.1103\/PhysRevE.91.012821","volume":"91","author":"LGS Jeub","year":"2015","unstructured":"Jeub, L.G.S., Balachandran, P., Porter, M.A., Mucha, P.J., Mahoney, M.W.: Think locally, act locally: the detection of small, medium-sized, and large communities in large networks. Phys. Rev. E 91(1), 012,821 (2015)","journal-title":"Phys. Rev. E"},{"key":"1214_CR15","doi-asserted-by":"crossref","unstructured":"Kloster, K., Gleich, D.F.: Heat kernel based community detection. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1386\u20131395 (2014)","DOI":"10.1145\/2623330.2623706"},{"key":"1214_CR16","doi-asserted-by":"crossref","unstructured":"Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: 29th Annual Symposium on Foundations of Computer Science, pp. 422\u2013431 (1988)","DOI":"10.1109\/SFCS.1988.21958"},{"issue":"1","key":"1214_CR17","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J Leskovec","year":"2011","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29\u2013123 (2011)","journal-title":"Internet Math."},{"key":"1214_CR18","first-page":"2339","volume":"13","author":"MW Mahoney","year":"2012","unstructured":"Mahoney, M.W., Orecchia, L., Vishnoi, N.K.: A local spectral method for graphs: with applications to improving graph partitions and exploring data graphs locally. J. Mach. Learn. Res. 13, 2339\u20132365 (2012)","journal-title":"J. Mach. Learn. Res."},{"key":"1214_CR19","doi-asserted-by":"crossref","unstructured":"Orecchia, L., Zhu, Z.A.: Flow-based algorithms for local graph clustering. In: SODA \u201914 Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1267\u20131286 (2014)","DOI":"10.1137\/1.9781611973402.94"},{"key":"1214_CR20","unstructured":"Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: bringing order to the web. Technical report, Stanford InfoLab (1999)"},{"issue":"3","key":"1214_CR21","first-page":"123","volume":"1","author":"N Parikh","year":"2013","unstructured":"Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1(3), 123\u2013231 (2013)","journal-title":"Found. Trends Optim."},{"issue":"3","key":"1214_CR22","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A Pothen","year":"1990","unstructured":"Pothen, A., Simon, H.D., Liou, K.P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11(3), 430\u2013452 (1990)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"1","key":"1214_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/080744888","volume":"42","author":"DA Spielman","year":"2013","unstructured":"Spielman, D.A., Teng, S.H.: A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J. Sci. Comput. 42(1), 1\u201326 (2013)","journal-title":"SIAM J. Sci. Comput."},{"key":"1214_CR24","volume-title":"Optimization for Machine Learning","author":"S Sra","year":"2012","unstructured":"Sra, S., Nowozin, S., Wright, S.J.: Optimization for Machine Learning. MIT Press, Cambridge (2012)"},{"key":"1214_CR25","unstructured":"Veldt, N., Gleich, D.F., Mahoney, M.W.: A simple and strongly-local flow-based method for cut improvement. Accepted to ICML (2016)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1214-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1214-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1214-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,7]],"date-time":"2019-10-07T04:27:14Z","timestamp":1570422434000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1214-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,2]]},"references-count":25,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["1214"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1214-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,2]]},"assertion":[{"value":"15 March 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}