### Finding Cheeger cuts via 1-Laplacian of graphs

- Series
- Applied and Computational Mathematics Seminar
- Time
- Monday, September 23, 2024 - 14:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Wei Zhu – University of Alabama at Tuscaloosa

Finding Cheeger cuts of graphs is an NP-hard problem, and one often resorts to approximate solutions. In the literature, spectral graph theory provides the most popular approaches for obtaining such approximate solutions. Recently, K.C. Chang introduced a novel nonlinear spectral graph theory and proved that the seek of Cheeger cuts is equivalent to solving a constrained optimization problem. However, this resulting optimization problem is also very challenging as it involves a non-differentiable function over a non-convex set that is composed of simplex cells of different dimensions. In this talk, we will discuss an ADMM algorithm for solving this optimization problem and provide some convergence analysis. Experimental results will be presented for typical graphs, including Petersen's graph and Cockroach graphs, the well-known Zachary karate club graph, and some preliminary applications in material sciences.