8000 New preconfiguration ultra: Jet refinement, unlocked flow model, more global work by schulzchristian · Pull Request #176 · KaHIP/KaHIP · GitHub
[go: up one dir, main page]

Skip to content

New preconfiguration ultra: Jet refinement, unlocked flow model, more global work - #176

Merged
schulzchristian merged 6 commits into
fix-flow-nochangefrom
ultra-preconfiguration
Nov 17, 2026
Merged

schulzchristian merged 6 commits into
fix-flow-nochangefrom
ultra-preconfiguration

Conversation

@schulzchristian
@schulzchristian schulzchristian commented Nov 17, 2026 •
Copy link
Copy Markdown
Member

Summary

This PR adds the preconfiguration ultra to kaffpa, kaffpaE and KaBaPE. It spends the time that v3.26 saved over v3.25 on better cuts: ultra starts from strong, keeps its balance rule, and stays below the running time of v3.25 strong on every job of our benchmark.

ultra was developed with Agentic Algorithm Engineering (AAE) [1, 2], run with a focus on solution quality: each change was stated as a hypothesis, implemented, measured on a fixed benchmark against a fixed quality gate, and kept only if the cuts improved.

Against v3.26 strong (imbalance 3%, 73 jobs):

  • cuts 2.2% smaller (Q = 0.9777 on the tuning graphs and on held-out graphs, 0.9729 on new seeds; 7% on social graphs);
  • 2.0x the time of v3.26 strong, and below the time of v3.25 strong on every job (geometric mean 0.64 of it);
  • inside kaffpaE and KaBaPE, at the same time limit: 0.5% to 1.6% smaller cuts than with strong inside.

Every change is guarded by a configuration field that only ultra sets, so every other preconfiguration gives exactly the partitions of the base branch. This PR is based on #175 (flow refinement: report no change when no flow problem can be built), which fixes a flow refinement bug for all configurations; ultra relies on that fix.

Usage

./deploy/kaffpa graph.graph --k 8 --preconfiguration=ultra
mpirun -n 24 ./deploy/kaffpaE graph.graph --k 8 --preconfiguration=ultra --time_limit=3600
  • command line: --preconfiguration=ultra (kaffpa, kaffpaE, KaBaPE, node_separator, which maps it to strong);
  • C/C++ interface: mode ULTRA (= 6) in kaffpa() and the other calls that take a mode;
  • Python: kahip.ULTRA;
  • settings: configuration::ultra in app/configuration.h.

What ultra does

ultra = strong plus:

  1. Jet refinement [3] on every level, before the k-way FM (field jet_refinement, lib/partition/uncoarsening/refinement/jet_refinement/). Jet is synchronous label propagation that also accepts bounded negative-gain moves, so FM starts outside its own local optimum.
    • Candidates: every unlocked boundary node v of a block A picks the adjacent block B it is most strongly connected to (ties: the lighter block). With gain g(v) = w(v, B) - w(v, A), v is a candidate if g(v) >= 0 or the loss -g(v) is below c * w(v, A), with c = 0.25 for unit node weights and 0.75 otherwise.
    • Afterburner: each candidate recomputes its gain as if every candidate of higher rank (larger gain, ties by node ID) had already moved. Only candidates whose recomputed gain is >= 0 move, all at once; moved nodes are locked for the next iteration.
    • Rebalancing: if the heaviest block exceeds the bound, the iteration rebalances instead: in every overloaded block, nodes are moved in order of loss per node weight until the block fits; boundary nodes go to their best connected block with room, interior nodes to the lightest block.
    • Jet keeps the partition with the smallest cut that is not heavier than the bound (or than the input, if that was heavier), and stops after 12 iterations without a cut below 0.999 times the best (at most 100 iterations).
  2. Unlocked flow model F_H [4] in the pairwise flow refinement (field flow_unlocked_model, cut_flow_problem_solver.cpp). For a pair of adjacent blocks (A, B), KaHIP grows a region around their boundary, sized with the flow region factor 8 of strong, and solves a max-flow problem on it. In the original model the outer border of the region is tied to source or sink with infinite capacity, so these nodes can never change sides. In F_H, each region node gets a source edge with the weight of its edges to A outside the region and a sink edge with the weight of its edges to B outside the region; edges to third blocks are left out, since they are cut on either side. The value of an s-t cut is then exactly the A-B cut of the partition it induces, and the same region offers a larger space of cuts. Without any source or sink edge, the original model is used. As in strong, the most balanced minimum cut is taken. The cut values of the pairs with third blocks are updated for nodes that changed sides.
  3. More global work: for k = 2, 3 V-cycles instead of 2; for k > 2, the best of 2 independent runs. The repetitions apply to the top level only (nested partitioner calls run once), and inside kaffpaE each operator makes a single run.
  4. kaffpaE / KaBaPE run the ultra kaffpa above in every operator (initial population, combine, mutation). Two changes apply to the evolutionary algorithm itself, both set only by ultra:
    • Balanced individuals first (mh_penalty_for_imbalance): an individual over the balance bound gets the fitness "total edge weight + 1 + overload", so it ranks behind every balanced individual in selection, exchange and the final choice. If the final partition is still over the bound, a negative-cycle rebalance moves nodes until every block fits.
    • Keep the input partition (mh_keep_input): if kaffpaE is started with --input_partition, that partition enters the population unchanged, so the result is never worse than the input.

Quality and time evidence

Q is the geometric mean over the jobs of (mean cut of ultra + 1) / (mean cut of v3.26 strong + 1), each mean over the seeds. Lower is better. Every partition was checked by an independent checker that recomputes the cut and the block weights. Benchmark: the 73 strong jobs of the benchmark of #171 (mesh, road and social/web graphs, k = 2 to 256), imbalance 3%.

measure Q vs v3.26 strong
tuning graphs, 53 jobs, seeds 1 to 5 0.9777 (social 0.930, mesh 0.986, road 0.989; k = 2: 0.954)
held-out graphs (fe_tooth, netherlands, email-EuAll, rgg_n_2_18), 20 jobs, seeds 1 to 5 0.9777 (social 0.961, road 0.977, mesh 0.987)
held-out seeds 7 to 9, all 73 jobs 0.9729
  • Time (seed 1, 3 repetitions alternating with v3.26 strong, median per job): ultra takes 2.0x the time of v3.26 strong (total 2.09x, at most 2.9x) and 0.64x (geometric mean) the time of v3.25 strong, at most 0.954x on any job.
  • Balance (strict bound, imbalance 3%): partitions over the bound, ultra vs v3.26 strong: 0 / 265 vs 3 / 265 (tuning), 1 / 100 vs 2 / 100 (held-out graphs), 1 / 219 vs 4 / 219 (seeds 7 to 9). The ultra cases are instances where strong also fails (email-EuAll k = 256, 4elt k = 256).
  • Contributions: the unlocked flow model gives 0.3%, Jet 1.4% on top of it (6.5% on social graphs), the rest comes from the extra V-cycle (k = 2) and the best of 2 runs.
  • kaffpaE and KaBaPE (1 MPI process, 10 instances, seeds 1 to 5, the same fixed time limits for both sides = 1, 3 and 10 times the v3.26 strong kaffpa time), QE = geometric mean cut ratio, ultra inside vs strong inside:
mode, limit QE
kaffpaE x1 0.9907
kaffpaE x3 0.9912
kaffpaE x10 0.9946
KaBaPE (imbalance 0) x3 0.9870
KaBaPE (imbalance 0) x10 0.9838

No run of ultra inside kaffpaE or KaBaPE missed the balance bound.

These numbers were measured with the flow fix of #175 active in ultra and absent in v3.26 strong; on its own the fix moves strong cuts by less than 0.01% in geometric mean.

Compatibility

Every change is behind a configuration field that only ultra sets (flow_unlocked_model, jet_refinement, mh_penalty_for_imbalance, mh_keep_input, plus global_cycle_iterations / repetitions in configuration::ultra). The repetitions loop now runs nested partitioner calls once and kaffpaE sets repetitions = 1; every other preconfiguration has repetitions = 1 already. No new dependencies, no CMake option or compiler flag changes; one new source file (jet_refinement.cpp). ParHIP (parallel/modified_kahip) is not touched.

Checked against the base branch #175:

  • kaffpa, all six old preconfigurations: 2907 / 2907 runs bit identical (sha256 of the partition file; the identity set of Flow refinement: report no change when no flow problem can be built #175: 537 benchmark jobs x seeds 1 to 3 plus the crosscheck grid at imbalance 1, 3, 5%);
  • node_separator, all six old preconfigurations on 4elt and PGPgiantcompo: 12 / 12 bit identical;
  • kaffpaE with --time_limit=0 (deterministic: initial population only; 1 MPI process; fast, eco, strong, strongsocial on 4elt and PGPgiantcompo, k = 8, imbalance 3% and 0, i.e. kaffpaE and KaBaPE): 16 / 16 bit identical (the same runs of the base branch repeat bit identically). kaffpaE runs with a time limit depend on wall time and were not compared;
  • builds: without MPI (-DNOMPI=ON), with MPI including ParHIP, and every commit of the series on its own (kaffpa, interface_test);
  • interface_test runs; a copy of it with mode ULTRA runs. The Python test of the CI was not run locally (no pybind11 on the test machine).

ultra itself gives the same partitions as our development branch, where the numbers above were measured: kaffpa 18 / 18 runs (6 graphs x k = 2, 8, 64), kaffpaE with --time_limit=0 4 / 4 runs, bit identical. The development branch also had a weighted tabu search and KaBaPE relax-and-rebalance rounds, both switched off in ultra because they gave no gain; they are left out of this PR.

Commits

  1. ultra preconfiguration: strong with more global work: the preconfiguration, command line, C/C++ interface, Python constant, README.
  2. ultra: unlocked flow model in pairwise flow refinement
  3. ultra: Jet refinement before the k-way FM on every level
  4. ultra: kaffpaE keeps the balance bound and the input partition
  5. ultra: mode constant ULTRA = 6 in the Java wrapper and the Python example
  6. Version 3.28: README news (ultra preconfiguration, flow refinement fix) and version bump: CMake project version, lib/version.h, README title and a "NEW in v3.28" section.

25 files, +611 / -10.

References

  1. D. A. Bader, A. Chhabra, E. Großmann, M. Henzinger, A. Noe, C. Schulz. Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts. arXiv:2609.07204, 2026. https://doi.org/10.48550/arXiv.2609.07204
  2. Agentic Algorithm Engineering, code: https://github.com/CHSZLab/AgenticAlgorithmEngineering
  3. M. S. Gilbert, K. Madduri, E. G. Boman, S. Rajamanickam. Jet: Multilevel Graph Partitioning on Graphics Processing Units. SIAM Journal on Scientific Computing 46(5), 2024. https://doi.org/10.1137/23M1559129
  4. T. Heuer, P. Sanders, S. Schlag. Network Flow-Based Refinement for Multilevel Hypergraph Partitioning. ACM Journal of Experimental Algorithmics 24(1), 2019. https://doi.org/10.1145/3329872

New preconfiguration ultra (kaffpa --preconfiguration=ultra, also kaffpaE and node_separator; interface
mode ULTRA = 6, kahip.ULTRA in Python). It starts from strong and spends more work per run: 3 V-cycles
for k = 2, otherwise the best of 2 independent runs. Repetitions apply to the top level only (nested
partitioner calls run once), and kaffpaE computes one partition per operator. Every other
preconfiguration keeps repetitions = 1, so its output is unchanged.
Field flow_unlocked_model, set only by ultra. The flow network of a block pair (A, B) follows the
model F_H of Heuer, Sanders and Schlag (ACM JEA 2019): region nodes are connected to source or sink
by the weight of their edges to the rest of their own block, and edges to third blocks are left out,
so nodes next to the region border can change sides. The value of an s-t cut is then exactly the A-B
cut of the partition it induces. Without any source or sink edge the original model is used. The cut
values of the pairs with third blocks are updated for nodes that changed sides.
Field jet_refinement, set only by ultra. Jet (Gilbert, Madduri, Boman, Rajamanickam, SIAM J. Sci.
Comput. 2024) is a label propagation refinement that also takes negative-gain moves, filters them with
an afterburner that evaluates each move against the moves of higher priority, and rebalances
overloaded blocks. It runs before the k-way FM on every uncoarsening level.
Two fields, set only by ultra. mh_penalty_for_imbalance: individuals over the balance bound rank
behind every balanced one, in the fitness and in the final choice, and a final partition still over
the bound is rebalanced with the negative-cycle model. mh_keep_input: when kaffpaE starts from
--input_partition, that partition enters the population unchanged as one individual, so the result is
never worse than the input.
@schulzchristian
schulzchristian merged commit 2de2ee8 into fix-flow-nochange Nov 17, 2026
schulzchristian added a commit that referenced this pull request Nov 17, 2026
New preconfiguration ultra: Jet refinement, unlocked flow model, more global work (to master, see #176)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant

0