Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues
원문 초록
We consider a new semidefinite programming relaxation for directed edge expansion, which is obtained by adding triangle inequalities to the reweighted eigenvalue formulation. Applying the matrix multiplicative weight update method to this relaxation, we derive almost linear-time algorithms to achieve $O(\sqrt{\log{n}})$-approximation and Cheeger-type guarantee for directed edge expansion, as well as an improved cut-matching game for directed graphs. This provides a primal-dual flow-based framework to obtain the best known algorithms for directed graph partitioning. The same approach also works for vertex expansion and for hypergraphs, providing a simple and unified approach to achieve the best known results for different expansion problems and different algorithmic techniques.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
PGT-I: Scaling Spatiotemporal GNNs with Memory-Efficient Distributed Training
Demystifying Distributed Training of Graph Neural Networks for Link Prediction
DistMLIP: A Distributed Inference Platform for Machine Learning Interatomic Potentials
Hierarchical Superpixel Segmentation via Structural Information Theory
FairGP: A Scalable and Fair Graph Transformer Using Graph Partitioning
Towards the efficacy of federated prediction for epidemics on networks
토론
이 논문과 연결된 포럼 글이 아직 없습니다.