用神经网络加速图划分，快得多还保持好效果
Neural Acceleration for Graph Partitioning
- 用神经网络替代传统特征值计算，逼近Fiedler向量
- 划分质量接近谱分割，计算开销大幅降低
- 适合大规模图划分任务，尤其内存受限场景
图划分在社交网络分析、VLSI设计等多个科学与工程领域中至关重要。谱方法因其能生成高质量划分并最小化边切割而广受认可，但其核心瓶颈在于计算图拉普拉斯矩阵的第二小特征值对应的特征向量（即Fiedler向量）时，面临内存和计算成本过高的问题。本文提出一种加速谱二分划分的方法，用简单的神经网络模型替代传统特征值计算，以近似得到Fiedler向量。实验表明，该方法在保持与谱二分相当划分质量的同时，显著降低了计算开销，提升了大规模问题下的可扩展性与效率。
原文摘要 · Abstract (English)
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 due to memory issues and computational costs. In this paper, we present an accelerated 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
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。