Agreement-Preserving Crossover for Hypergraph Modularity

Many real datasets record group interactions rather than pairs: a meeting of five students, a bill with twelve cosponsors, a browsing session touching eight hotels. These are hypergraphs, where one "hyperedge" ties together any number of nodes. Finding communities in them by maximizing modularity means scoring a partition by how much more internal hyperedge mass it has than a random null model would predict. That problem is NP-hard. The fastest practical tool, a hypergraph version of the Louvain greedy algorithm, scales to millions of nodes. Like all greedy modularity methods, though, it lands in different local optima depending on the arbitrary order in which it visits nodes.

We propose a genetic search over hypergraph partitions built around one recombination operator. When two parent partitions are combined, the child keeps every group of nodes that both parents place together, which is the partition analogue of a "longest common subsequence." The child then decides how to reconnect those preserved groups by cutting only where native hypergraph modularity says the connection is weakest, which is the analogue of a "distance-guided" cut. The claim is that this operator lets a population of Louvain-refined partitions combine what different basins got right. The result should be partitions that are more accurate and more reproducible than an equal budget of independent restarts, specifically on hypergraphs whose community signal lives in the group interactions and not in their pairwise shadows.

Core Claim

Two lines of evolutionary work supply the template. The distance-guided memetic algorithms for web-service composition (A memetic algorithm with distance-guided crossover, Cluster-Guided Genetic Algorithm, Distance-Guided Memetic Algorithm) do two things. They protect the common subsequence of two parent workflows. They split each parent at the pair of consecutive services that are farthest apart. On WSC08-1 this lowered mean fitness from 0.54 to 0.42, where lower is better. Both ingredients are tied to linear chromosomes and raw pairwise distances in kilometres or milliseconds. Neither has an obvious meaning for a partition of a hypergraph.

Our translation is as follows. Given parent partitions $P_1$ and $P_2$, the "common structure" is their meet. This is the set of nonempty intersections $C_i \cap C'_j$ of a block from each parent, and it is computable in linear time by hashing node labels. That matters because general common-substructure detection is quadratic or NP-hard. The meet also sidesteps label switching, the problem that the same community can carry different index numbers in different parents. HG-means solves label switching with Hungarian matching of centroids, but that approach needs Euclidean data.

The "distance" between two meet blocks is replaced by a null-model-corrected cohesion. We define it as the change in all-or-nothing (AON) hypergraph modularity from merging the two blocks. AON is the objective derived from the degree-corrected hypergraph blockmodel in Generative hypergraph clustering, where a hyperedge counts as internal only if all of its nodes fall in one community. The merge gain is computed directly on hyperedges, never on a clique projection. The child is formed by agglomerating meet blocks only along positive-gain boundaries, so cuts fall exactly at the most negative-gain boundaries, the hypergraph version of the "largest distance gap." The child is then polished by AON Louvain started from this partition.

What is new is a recombination operator for hypergraph partitions whose preserved building blocks and cut locations are both defined by the native hypergraph objective. Prior bridges between these areas offer either single-trajectory greedy hypergraph methods or population methods for pairwise graphs only.

Research Program

The first component is the operator and its cost. Computing the meet costs time linear in the number of nodes. Scoring merge gains between adjacent meet blocks costs time linear in the total hyperedge size, because each hyperedge touches a bounded number of meet blocks. This keeps a crossover no more expensive than one Louvain pass. We will verify this claim empirically on the largest instances.

The second component is the population loop. Parents are produced by AON Louvain under random vertex orders. Children replace parents under a diversity-aware rule: a child that is too close to an existing member, measured by variation of information, is rejected. This rule addresses the known failure of over-protecting common structure, which is premature collapse onto one basin. A mutation operator splits a single community along its most negative-gain internal boundary, reusing the same score.

The third component is analysis. We will relate the meet-preservation step to the constant communities of Constant Communities in Complex Networks, groups that co-occur across all randomized greedy runs. A constant community is the meet of many runs, frozen forever. Our meet is pairwise and re-formed every generation, so blocks preserved early can be dissolved later. We will test whether this difference matters.

We take the "near-optimal trap" of Network Clustering via Maximizing Modularity seriously. That work shows that a partition within 99% of optimal modularity can share no structure with the optimum. We therefore never report modularity alone; accuracy against ground truth and run-to-run reproducibility are co-primary outcomes.

Baselines

The naive reference point is a single run of AON Hypergraph Louvain from Generative hypergraph clustering with a random vertex order. This shows what one cheap greedy trajectory gives.

The strongest competitor is multi-start AON Louvain that keeps the best-modularity run. It is the honest version of "just restart more," and it has the same refinement engine as our method. We will run it with exactly the same total number of Louvain calls and the same wall-clock budget as the genetic search. Both use identical hypergraphs and the same AON affinity, selected by the information criterion described in that paper. Beating it means higher mean ARI or NMI against ground truth, together with lower across-seed variance of the final partition, at matched budget. Higher modularity alone does not count.

The second strong competitor is constant-community collapse applied to AON Louvain: run many restarts, freeze the nodes that always co-occur, and rerun. It is given the same budget.

On the 3-uniform 1984 Congressional voting hypergraph, the strongest published number is PTPM's misclassification rate of 0.07 (Projected Tensor Power Method), versus 0.08 for spectral clustering and 0.10 for local MLE. On TwitterFootball, IRMM reports an F1 of 0.5463 (Hypergraph Clustering: A Modularity Maximization Approach). For AON Louvain's ARI on Trivago, no reported number was found on Lacuna, so we will rerun it ourselves.

Two ablations isolate the key ingredient. The first keeps the meet but reassembles blocks at random, matching the number of resulting communities to the guided child. The second keeps the meet but scores merges with ordinary graph modularity on the degree-preserving clique reduction of Kumar et al. The first ablation tests whether guided cutting matters. The second tests whether the guidance must be hypergraph-native.

Why not just…?

Why not just restart AON Louvain many times and keep the best? This is the real threat, and our main comparison is built around it. Its weakness is that restarts never exchange information. Each one lands in whatever basin its vertex order leads to. Thai et al. show that the best-modularity basin need not be the structurally correct one. If equal-budget restarts match our ARI and stability, the operator adds nothing and we will say so. We expect the gap to appear on hypergraphs with many near-degenerate basins, such as the school-contact and cosponsorship data, and to vanish on easy ones.

Why not just collapse constant communities and rerun? Chakraborty and Srinivasan show that this drives modularity variance to near zero on the Jazz and Dolphin networks. However, it gives high variance on the US power grid and email interchange networks, which lack invariant cores. Freezing the all-runs meet is maximally conservative, and on such networks it preserves almost nothing. Our pairwise meet preserves agreement between two good partitions, which is a weaker requirement and should help exactly where constant communities fail. The amorphous-network comparison decides this directly.

Why not reduce the hypergraph to a weighted graph and run a pairwise memetic algorithm like Meme-Net? Memetic algorithm for community detection in networks already does population search on graphs and reports a Karate-club NMI of 0.699. Generative hypergraph clustering shows that clique projections are blind to communities carried only by three-node edges when the two-node edges are noise. The clique-reduction ablation, run on that exact synthetic regime, is the test. If it matches the native version there, our hypergraph-native claim is wrong.

Why not use spectral initialization followed by tensor power iterations? PTPM is near-linear and achieves exact recovery from a weakly correlated start. Producing that start cheaply, however, is the problem its authors leave open. We treat PTPM as a competitor on uniform hypergraphs. We also test the population's best partition as PTPM's initializer, which could make the two complementary rather than rival.

Proposed Experiments

The synthetic study uses 3-uniform and mixed-size hypergraph blockmodels. We sweep the strength of the higher-order signal while keeping the pairwise edges at pure noise, which reproduces the detectability experiment of the generative-clustering paper. We report ARI and the across-seed variation of information as functions of signal strength, matched compute, and graph size up to $10^6$ nodes.

The empirical study covers school contact, congressional cosponsorship and committees, Trivago, TwitterFootball, Cora, and Arnetminer. The 3-uniform congressional voting hypergraph allows a direct comparison with PTPM's 0.07. All comparisons use 30 seeds and Wilcoxon signed-rank tests at 0.05, mirroring the service-composition studies.

The decisive checks are three. The first is whether guided reassembly beats random reassembly of the same meet at fixed community count. The second is whether native AON scoring beats clique-reduced scoring in the regime where pairwise edges are noise. The third is whether the full method beats equal-budget multi-start Louvain on accuracy and reproducibility together. If only modularity improves, we will report that the method has fallen into the near-optimal trap rather than escaped it.