Can KaHyPar support zero vertex weight?

[chenmagi]

Hi,

I noticed that the current version of KaHyPar fails when the hypergraph contains some vertices with zero weight. Is it possible to implement a solution to address this issue?

best,

Magi

[SebastianSchlag]

Hi @chenmagi,

sorry for the delayed response.

I double-checked the code and it looks like we added the requirement to have non-zero vertex weights as part of our general input validation in #167.
If you compile KaHyPar with cmake flag KAHYPAR_INPUT_VALIDATION=OFF you can bypass that check.
In RELEASE mode, I was able to partition a weighted hypergraph with a couple of zero-weighted vertices. In DEBUG mode, this assertion got triggered:

kahypar/kahypar/partition/refinement/2way_fm_refiner.h

Lines 216 to 223 in 875464b

	// If Lmax0==Lmax1, then all border nodes should be active. However, if Lmax0 != Lmax1,
	// because k!=2^x or we intend to further partition the hypergraph into unequal number of
	// blocks, then it might not be possible to activate all refinement nodes, because a
	// part could be overweight regarding Lmax. Additionaly, if hypernode hn is a fixed
	// vertex, it should not be activated.
	ASSERT((_context.partition.max_part_weights[0] != _context.partition.max_part_weights[1]) ||
	_hg.isFixedVertex(hn) || _context.partition.use_individual_part_weights ||
	(!_hg.isBorderNode(hn) || _pq.isEnabled(1 - _hg.partID(hn))), V(hn));

Technically violating this assertion in the presence of vertices with weight zero might be fine. I'm not entirely sure though if we rely on non-zero vertex weights in other parts of the code. So it might make sense to sanity-check that partitions generated using the approach outlined above are actually valid.

@N-Maas @larsgottesbueren @TobiasHeuer Are you folks aware of anything that might break if we allow zero-weighted vertices?

[larsgottesbueren]

The only thing that came to mind is the heavy node penalty in heavy edge rating during coarsening. Div by zero is not nice, but that's an easy fix.

[larsgottesbueren]

PQ selection policies in IP? Also setting up max part weights and similar stuff might have some unexpected issues lurking

[N-Maas]

No, the requirement was not added in #167. Previous to the PR, the hypergraph parser already contained a check whether a node has weight zero and would abort if this was the case. #167 just moved the check to the generalized validation logic.

The original check was introduced with Commit dda4673 in May 2021. I don't know the reasoning. We added individual part weight support roughly at the same time, though this is probably unrelated.

[kittobi1992]

The question is if zero weight vertices really matters in the partition problem. For example, can we contract an zero weight vertex onto one of its neighbours, partition the hypergraph, revert the contraction, and then still prove some optimality? Any idea on that?

Basically, we can assign a zero weight vertex to any partition after partitioning for free. Can we do some greedy heuristic after partitioning to assign them?

[N-Maas]

Basically, we can assign a zero weight vertex to any partition after partitioning for free. Can we do some greedy heuristic after partitioning to assign them?

At least for bipartitioning, I'm pretty sure that assigning the zero weight vertices to a fixed partition is equivalent to solving a flow problem on the zero weight subgraph (just contract the blocks of non-zero vertices into single nodes, which are then source and sink). So it's doable, but a greedy approach is not sufficient for the general case.

However, since the cost of assigning the zero weight vertices depends on the partition of the remaining vertices, this does not allow to ignore them during partitioning. Heuristics like contraction onto a neighbor also won't allow optimality - you might choose the wrong neighbor, e.g., which is in a different block than all the other neighbors.

Therefore, special casing zero weight vertices doesn't seem particularly promising to me.

[chenmagi]

Hi,

@SebastianSchlag @N-Maas @larsgottesbueren @kittobi1992 Thank you for your comments. I rebuilt KaHyPar in RELEASE mode, and it now handles graphs with some zero-vertex weights.

Best,

Magi