A minimal surface criterion for graph partitioning

Dominique  Zosso; Braxton  Osting

doi:10.3934/ipi.2016036

Article Contents

2016, Volume 10, Issue 4: 1149-1180. Doi: 10.3934/ipi.2016036

This issue Previous Article On the stable recovery of a metric from the hyperbolic DN map with incomplete data Next Article

A minimal surface criterion for graph partitioning

Dominique Zosso^1, and
Braxton Osting^2,

1.
Montana State University, Department of Mathematical Sciences, 2-214 Wilson Hall, Box 172400, Bozeman, MT 59717-2400
2.
University of Utah, Salt Lake City, Department of Mathematics, 155 S. 1400 E, Rm 233, Salt Lake City, UT 84112

Received: July 2015

Revised: May 2016

Published: November 2016

Abstract Related Papers Cited by

Abstract

We consider a geometric approach to graph partitioning based on the graph Beltrami energy, a discrete version of a functional that appears in classical minimal surface problems. More specifically, the optimality criterion is given by the sum of the minimal Beltrami energies of the partition components. Since the Beltrami energy interpolates between the Total Variation and Dirichlet energies, various results for optimal partitions for these two energies can be recovered. We adapt primal-dual convex optimization methods to solve for the minimal Beltrami energy for each component of a given partition. A rearrangement algorithm is proposed to find the graph partition to minimize a relaxed version of the objective. The method is applied to several clustering problems on graphs constructed from manifold discretizations, synthetic data, the MNIST handwritten digit dataset, and image segmentation. The model has a semisupervised extension and provides a natural representative for the clusters as well.

Keywords:

Mathematics Subject Classification: 65K15, 49Q05, 65Dxx, 68U10, 53C44.

Citation:

Related Papers

Cited by

References

[1]	K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in Linear and Non-Linear Programming, Cambridge Univ. Press, 1958.
[2]	I. Babuska, The finite element method with penalty, Mathematics of Computation, 27 (1973), 221-228.doi: 10.1090/S0025-5718-1973-0351118-5.
[3]	D. A. Bader, H. Meyerhenke, P. Sanders and D. Wagner (eds.), Graph Partitioning and Graph Clustering, American Mathematical Society, 2013.doi: 10.1090/conm/588.
[4]	D. Barash, Fundamental relationship between bilateral filtering, adaptive smoothing, and the nonlinear diffusion equation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24 (2002), 844-847.doi: 10.1109/TPAMI.2002.1008390.
[5]	B. Bogosel, Shape Optimization and Spectral Problems, Ph.D. thesis, Chambéry, 2015.
[6]	B. Bogosel, Partitions minimizing an anisotropic length, 2016.
[7]	V. Bonnaillie-Noël and B. Helffer, Numerical analysis of nodal sets for eigenvalues of Aharonov-Bohm Hamiltonians on the square with application to minimal partitions, Experimental Mathematics, 20 (2011), 304-322.doi: 10.1080/10586458.2011.565240.
[8]	V. Bonnaillie-Noël, B. Helffer and G. Vial, Numerical simulations for nodal domains and spectral minimal partitions, ESAIM: Control, Optimisation and Calculus of Variations, 16 (2010), 221-246.doi: 10.1051/cocv:2008074.
[9]	V. Bonnaillie-Noël and C. Léna, Spectral minimal partitions for a family of tori, URL http://arxiv.org/abs/1503.04545.
[10]	B. Bourdin, D. Bucur and É. Oudet, Optimal partitions for eigenvalues, SIAM Journal on Scientific Computing, 31 (2010), 4100-4114.doi: 10.1137/090747087.
[11]	T. Brox and D. Cremers, On local region models and a statistical interpretation of the piecewise smooth Mumford-Shah functional, International Journal of Computer Vision, 84 (2009), 184-193.doi: 10.1007/s11263-008-0153-5.
[12]	D. Bucur, G. Butazzo and A. Henrot, Existence results for some optimal partition problems, Adv. Math. Sci. Appl., 8 (1998), 571-579.
[13]	D. Bucur and G. Butazzo, Variational Methods in Shape Optimization Problems, vol. 65 of Progress in Nonlinear Differential Equations and Their Applications, Birkhäuser Boston, 2005.
[14]	D. Bucur and B. Velichkov, Multiphase shape optimization problems, SIAM Journal on Control and Optimization, 52 (2014), 3556-3591.doi: 10.1137/130917272.
[15]	L. A. Cafferelli and F. H. Lin, An optimal partition problem for eigenvalues, Journal of Scientific Computing, 31 (2007), 5-18.doi: 10.1007/s10915-006-9114-8.
[16]	A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, 40 (2011), 120-145.doi: 10.1007/s10851-010-0251-1.
[17]	T. F. Chan and L. A. Vese, Active contours without edges, IEEE Transactions on Image Processing, 10 (2001), 266-277.doi: 10.1109/83.902291.
[18]	H. Cohn and A. Kumar, Universally optimal distribution of points on spheres, Journal of the American Mathematical Society, 20 (2007), 99-148.doi: 10.1090/S0894-0347-06-00546-7.
[19]	O. Cybulski, V. Babin and R. Holyst, Minimization of the Renyi entropy production in the space-partitioning process, Physical Review E, 71 (2005), 046130, 10pp.doi: 10.1103/PhysRevE.71.046130.
[20]	O. Cybulski and R. Holyst, Three-dimensional space partition based on the first Laplacian eigenvalues in cells, Physical Review E, 77 (2008), 056101, 8pp.doi: 10.1103/PhysRevE.77.056101.
[21]	L. Dascal, G. Rosman and R. Kimmel, Efficient Beltrami filtering of color images via vector extrapolation, in SSVM'07: Proceedings of the 1st international conference on Scale space and variational methods in computer vision, Springer-Verlag, 4485 (2007), 92-103.doi: 10.1007/978-3-540-72823-8_9.
[22]	A. P. Dempster, N. M. Laird and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society. Series B (Methodological), 39 (1977), 1-38.
[23]	J. Duchi, S. Shalev-Shwartz, Y. Singer and T. Chandra, Efficient projections onto the l1-ball for learning in high dimensions, in Proceedings of the 25th international conference on Machine learning - ICML '08, ACM Press, New York, New York, USA, 2008, 272-279.
[24]	I. Ekeland and R. Temam, Convex Analysis and Variational Problems, North-Holland Publishing Company, Amsterdam, 1976.
[25]	S. Esedoglu and F. Otto, Threshold dynamics for networks with arbitrary surface tensions, Communications on Pure and Applied Mathematics, 68 (2015), 808-864.doi: 10.1002/cpa.21527.
[26]	E. Esser, X. Zhang and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM Journal on Imaging Sciences, 3 (2010), 1015-1046.doi: 10.1137/09076934X.
[27]	M. Feigin and N. Sochen, Anisotropic regularization for inverse problems with application to the Wiener filter with Gaussian and impulse noise, in Scale Space and Variational Methods in Computer Vision, vol. 5567 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2009, 319-330.doi: 10.1007/978-3-642-02256-2_27.
[28]	R. Gabbrielli, A new counter-example to Kelvin's conjecture on minimal surfaces, Philosophical Magazine Letters, 89 (2009), 483-491.doi: 10.1080/09500830903022651.
[29]	C. Garcia-Cardona, E. Merkurjev, A. L. Bertozzi, A. Flenner and A. G. Percus, Multiclass data segmentation using diffuse interface methods on graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36 (2014), 1600-1613.doi: 10.1109/TPAMI.2014.2300478.
[30]	E. Giusti, Minimal Surfaces and Functions of Bounded Variation, Springer Science & Business Media, 1984.doi: 10.1007/978-1-4684-9486-0.
[31]	T. C. Hales, The honeycomb conjecture, Discrete & Computational Geometry, 25 (2001), 1-22.doi: 10.1007/s004540010071.
[32]	B. Helffer, On spectral minimal partitions: A survey, Milan J. Math., 78 (2010), 575-590.doi: 10.1007/s00032-010-0129-0.
[33]	B. Helffer and T. Hoffmann-Ostenhof, Remarks on two notions of spectral minimal partitions, Adv. Math. Sci. Appl., 20 (2010), 249-263.
[34]	B. Helffer, T. Hoffmann-Ostenhof and S. Terracini, On spectral minimal partitions: The case of the sphere, 2010, Around the research of Vladimir Maz'ya. III, Int. Math. Ser. (N. Y.), Springer, New York, 13 (2010), 153-178.doi: 10.1007/978-1-4419-1345-6_6.
[35]	C. Herring, Some theorems on the free energies of crystal surfaces, Physical Review, 82 (1951), 87-93.doi: 10.1103/PhysRev.82.87.
[36]	R. Kaftory, N. A. Sochen and Y. Y. Zeevi, Variational blind deconvolution of multi-channel images, Int. J. Imaging Syst. Technol., 15 (2005), 56-63.doi: 10.1002/ima.20038.
[37]	R. Kimmel, R. Malladi and N. Sochen, Images as embedded maps and minimal surfaces: Movies, color, texture, and volumetric medical images, Int. J. Comput. Vis., 39 (2000), 111-129.
[38]	C. Li, C.-Y. Kao, J. C. Gore and Z. Ding, Minimization of region-scalable fitting energy for image segmentation, IEEE Transactions on Image Processing, 17 (2008), 1940-1949.doi: 10.1109/TIP.2008.2002304.
[39]	Z. Liang and Y. Li, Beltrami flow in Hilbert space with applications to image denoising, Journal of Electronic Imaging, 21 (2012), 043019, 1-11.doi: 10.1117/1.JEI.21.4.043019.
[40]	S. Lloyd, Least squares quantization in PCM, IEEE Transactions on Information Theory, 28 (1982), 129-137.doi: 10.1109/TIT.1982.1056489.
[41]	L. Lopez-Perez, R. Deriche and N. Sochen, The Beltrami flow over triangulated manifolds, in CVAMIA and MMBIA Workshop at ECCV 2004, 3117 (2004), 135-144.doi: 10.1007/978-3-540-27816-0_12.
[42]	E. Merkurjev, T. Kostic and A. L. Bertozzi, An MBO scheme on graphs for segmentation and image processing, SIAM J. Imaging Sciences, 6 (2013), 1903-1930.doi: 10.1137/120886935.
[43]	B. Merriman, J. K. Bence and S. Osher, Diffusion Generated Motion by Mean Curvature, Technical report, UCLA CAM Report 92-18, 1992.
[44]	B. Merriman, J. K. Bence and S. Osher, Diffusion generated motion by mean curvature, AMS Selected Letters, Crystal Grower's Workshop, 73-83.
[45]	B. Osting and C. D. White, Nonnegative matrix factorization of transition matrices via eigenvalue optimization, in NIPS OPT, 2013.
[46]	B. Osting, C. D. White and É. Oudet, Minimal Dirichlet energy partitions for graphs, SIAM Journal on Scientific Computing, 36 (2014), A1635-A1651.doi: 10.1137/130934568.
[47]	É. Oudet, Approximation of partitions of least perimeter by $\Gamma$-convergence: around Kelvin's conjecture, Experimental Mathematics, 20 (2011), 260-270.doi: 10.1080/10586458.2011.565233.
[48]	J. Plateau, Statique Expérimentale et Théorique des Liquides Soumis Aux Seules Forces Moléculaires, Gauthier-Villars, Paris, 1873.
[49]	G. Pólya and G. Szegő, Isoperimetric inequalities in mathematical physics, Princeton University Press, 1951.
[50]	G. Rosman, X.-C. Tai, L. Dascal and R. Kimmel, Polyakov action for efficient color image processing, Trends and Topics in Computer Vision, the series Lecture Notes in Computer Science, 6554 (2010), 50-61.doi: 10.1007/978-3-642-35740-4_5.
[51]	A. Roussos and P. Maragos, Tensor-based image diffusions derived from generalizations of the total variation and Beltrami functionals, in 2010 IEEE International Conference on Image Processing, IEEE, 2010, 4141-4144.doi: 10.1109/ICIP.2010.5653241.
[52]	L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[53]	C. Sagiv, N. A. Sochen and Y. Y. Zeevi, Gabor feature space diffusion via the minimal weighted area method, in Energy Minimization Methods in Computer Vision and Pattern Recognition, 2134 (2001), 621-635.doi: 10.1007/3-540-44745-8_41.
[54]	H. Schaeffer and L. Vese, Variational dynamics of free triple junctions, Journal of Scientific Computing, 59 (2014), 386-411.doi: 10.1007/s10915-013-9767-z.
[55]	H. A. Schwarz, Gesammelte mathematische Abhandlungen, Springer Berlin Heidelberg, Berlin, Heidelberg, 1890.doi: 10.1007/978-3-642-50665-9.
[56]	W. Sir Thomson, On the division of space with minimum partitional area, Acta Mathematica, 11 (1887), 121-134.doi: 10.1007/BF02612322.
[57]	N. Sochen, R. Deriche and L. Lopez-Perez, The Beltrami flow over implicit manifolds, in 9th IEEE ICCV, 2003, 832-839.doi: 10.1109/ICCV.2003.1238434.
[58]	N. Sochen, R. Kimmel and R. Malladi, A general framework for low level vision, IEEE Transactions on Image Processing, 7 (1998), 310-318.doi: 10.1109/83.661181.
[59]	N. A. Sochen, Stochastic processes in vision: From Langevin to Beltrami, Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, 1 (2001), 288-293.doi: 10.1109/ICCV.2001.937531.
[60]	A. Spira, R. Kimmel and N. Sochen, A short-time Beltrami kernel for smoothing images and manifolds, IEEE Transactions on Image Processing, 16 (2007), 1628-1636.doi: 10.1109/TIP.2007.894253.
[61]	M. van den Berg and D. Bucur, On the torsion function with Robin or Dirichlet boundary conditions, Journal of Functional Analysis, 266 (2014), 1647-1666.doi: 10.1016/j.jfa.2013.07.007.
[62]	Y. van Gennip, N. Guillen, B. Osting and A. L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs, Milan Journal of Mathematics, 82 (2014), 3-65.doi: 10.1007/s00032-014-0216-8.
[63]	A. Wetzler and R. Kimmel, Efficient Beltrami flow in patch-space, in Scale Space and Variational Methods in Computer Vision 2011 (eds. A. M. Bruckstein, B. M. Haar Romeny, A. M. Bronstein and M. M. Bronstein), vol. 6667 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, 134-143.doi: 10.1007/978-3-642-24785-9_12.
[64]	Z. Yang, T. Hao, O. Dikmen, X. Chen and E. Oja, Clustering by nonnegative matrix factorization using graph random walk, in Advances in Neural Information Processing Systems 25, 2012, 1079-1087.
[65]	M. Zhu and T. Chan, An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration, Technical report, UCLA CAM Report 08-34, 2008.
[66]	M. Zhu, S. J. Wright and T. F. Chan, Duality-based algorithms for total-variation-regularized image restoration, Computational Optimization and Applications, 47 (2010), 377-400.doi: 10.1007/s10589-008-9225-2.
[67]	D. Zosso, J. An, J. Stevick, N. Takaki, M. Weiss, L. S. Slaughter, H. H. Cao, P. S. Weiss and A. L. Bertozzi, Image segmentation with dynamic artifacts detection and bias correction, submitted to: AIMS J. Inverse Problems and Imaging, 24.
[68]	D. Zosso and A. Bustin, A Primal-Dual Projected Gradient Algorithm for Efficient Beltrami Regularization, Technical report, UCLA CAM Report 14-52, 2014.