What are reasonable values of edge weights?

[andreas-brostrom]

Hello,

We have added METIS to our physics simulator to partition simulation grids, but we are having some issues with stability. In order to "force" connection between certain nodes, we tried to set extreme values for their edge weights (e.g. max int). Sometimes we are getting segmentation faults, and sometime we aren't, typically by changing the number of partitions. This is both with libmetis and with standalone gpmetis. I realize that this is an extreme example, but we have also experienced problems with edge weights far smaller. Also, the fact that we are getting segmentation faults is a bit troublesome.

I noticed issue #73 which claims that high ratios of weights are causing problems. I would not assume those ratios of 55/1 to be particularly high, and if so, we would have to reconsider how we determine our graph weights.

Can someone either offer some clarification on what range of edge weights and/or ratios are reasonable, or point me to some documentation that does?

Thank you!

[euphoricpoptarts]

Using large weights between important vertex pairs would not necessarily guarantee that those vertices will end up in the same part of a partition. If you must guarantee certain vertex sets in the same part, I would recommend instead generating a new graph which is induced from the original graph by merging such vertex sets into "coarse" vertices. You can then partition that graph instead, and assign each vertex in the original graph to the part given by its corresponding "coarse" vertex. If the results you are getting when Metis doesn't segfault are good enough for you, then ignore this suggestion.

The use of very large vertex weights, especially max int, is extremely likely to lead to integer overflow that I'd imagine is the source of the segfaults you're seeing. It's kind of an implicit assumption in the code (and most partitioning codes for that matter) that your weights are nowhere close to max int. A good rule of thumb would be to have the sum of all your edge weights be less than max int. This is the only way to guarantee that integer overflow won't happen. Otherwise, you can enable 64 bit ints in your configuration options. You could probably keep your forcing weights at around the 32 bit int max without problems by doing this.

[andreas-brostrom]

Thank you for your clarifications and suggestions. Indeed, integer overflow due to high edge weights seems like a reasonable cause of the crashes. I will look into whether we need a kind of "super-node" approach as you suggest to hard constrain the connections, or if simply lowering the weights while keeping a high relative value for the specific edges is good enough for our needs.