Balanced graph cuts: algorithms, analysis and applications

About This Grant

The project focuses on answering the question "How to divide a collection of objects into two groups such that the objects within each group can interact while the objects from different groups rarely interact?" As is well known, the past two decades have witnessed an exponential increase in the use of social or other networks, which consist of objects and connections between them, and carry a lot of information. These networks can be used to detect different groups of objects, each with similar characteristics or preferences. In materials science, advanced engineering alloys, such as steels and high-entropy alloys, may be thought of as 3-dimensional graphs with atoms residing at the nodes of a graph and its edges as bonds. These materials are often polycrystalline, and sudden, unexpected failures occur frequently in the form of fractures along crystal boundaries. Such failures are extremely costly, resulting in, for example, oil and gas spills and even bridge collapses. All the above problems can be cast as balanced graph cut problems, which are very challenging. In the literature, many existing approaches resort to approximate solutions. However, these solutions may differ significantly from the optimal ones. This proposal mainly focuses on the development of efficient and reliable methods for finding optimal graph cuts, which could significantly promote their applications to practical problems in the fields of materials science and social sciences. Partitioning a large data set into a prescribed number of subsets is a fundamental problem in machine learning, and it assumes wide applications in fields such as social networks, computer science, chemical engineering, and materials science. To conduct the partition, different balanced graph cuts have been proposed, including the Cheeger cut, the ratio cut, and the normalized cut. As one of the most important balanced graph cuts, the Cheeger cut is a challenging NP-hard problem. Existing approaches only provide approximate solutions. Recently, a novel nonlinear spectral graph theory was developed, and finding the Cheeger cut amounts to solving a constrained optimization problem with a non-smooth objective function over a non-convex set that consists of many different-dimensional simplex cells. The number of these cells is an exponential function of the number of vertices of a graph. Therefore, this raises another tough optimization problem. The proposed research in this project consists of three parts: 1) developing novel efficient and reliable numerical algorithms to solve the above-mentioned problem by using optimization techniques; 2) extending the existing nonlinear spectral graph theory to weighted graphs to enrich the theory and significantly expand its applications to real problems; 3) applying the proposed methods to tackle practical problems in metallurgical engineering and materials science. The projects discussed in this proposal also offer training opportunities for graduate and undergraduate students. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.