Symmetry-breaking symmetry in directed spectral partitioning

Abstract

We break the symmetry in classical spectral bi-partitioning in order to incentivise the alignment of directed cut edges. We use this to generate acyclic bi-partitions and furthermore topological orders of directed acyclic graphs with superb locality. The new approach outperforms the state-of-the-art Gorder algorithm by up to 17× on total reuse distance and minimum linear arrangement.

Abstract on arXiv

DOI arXiv PDF

Cite this work

@misc{symmetrybreakingsymmetryindirectedspectralpartitioning,
  title = {Symmetry-breaking symmetry in directed spectral partitioning},
  author = {Dimosthenis Pasadakis and Raphael S. Steiner and Pál András Papp and Toni Böhnlein and Albert-Jan N. Yzelman},
  year = {2026},
  note = {SPAA},
  url = {https://doi.org/10.1145/3816782.3819184}
}

Download