will a cluster with one object be considered as hyper edge ?

[Pierre-sirris]

Hello, we are using your library and we have a question regarding its assumptions, to be sure if it's by design or a possible issue.

When constructing hypergraph from clusters of different layers, will a cluster with one object be considered as hyper edge ? In the below figure will red cluster be considered as an edge ?

Consider a scenario where there are 24 objects represented with is ids from 100 to 123. There are two layers

1. Layer 1 with 7 clusters
2. Layer 2 with 6 clusters.
   When a hypergraph is constructed for the above setup, ideally number of hyper edges will be equal to total number of clusters (in this case the hypergraph should have 13 hyper edges). But the Kahypar library generates hypergraph with 10 hyper edges.
   When we look at edges for each node, clusters of single object are not considered as edge. In the below figure you can see the clusters of each layer and edges mapped to each cluster.
   In the edge-node mapping you can observe that for objects with ids 114,116,123 their clusters with single element are not considered.

Is this expected ?

[SebastianSchlag]

Hi @Pierre-sirris,

thanks for reaching out. Your observation is correct. KaHyPar ignores hyperedges that only contain a single vertex. This is by design, because a hyperedge containing a single vertex can never be cut and therefore these hyperedges are not relevant during partitioning - so ignoring them does not impact the partitioning quality.