"Neural acceleration of graph partitioning" by Vishvam Patel

Author

Vishvam Patel

Date of Award

2025

Document Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

Committee Chair

Joshua Booth

Committee Member

Jacob Hauenstein

Committee Member

Gou-Hui Zhang

Research Advisor

Joshua Booth

Subject(s)

Graph theory--Data processing, Partitions (Mathematics), Neural networks (Computer science)

Abstract

Graph Partitioning is a critical problem in numerous scientific and engineering domains including social network analysis, VLSI design, and many more. Spectral methods are known to produce quality partitions while minimizing edge cuts for a wide range of problems. However, the computational cost associated with the calculation of the Fiedler vector, an eigenvector associated with the second smallest eigenvalue of the graph Laplacian, remains a significant bottleneck. In this paper, we present an neural acceleration approach to spectral bisection partitioning by replacing the traditional eigenvalue calculation with a simple artificial neural network model to approximate the fiedler vector. We demonstrate that our approach achieves partitioning quality comparable to spectral bisection while significantly reducing the computational overhead, making it more scalable and efficient for large-scale problems.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.