Hypergraph Embeddings Reveal How Metabolism Tracks Evolutionary Lineages

The biochemical reactions that keep an organism alive may carry a hidden signature of its evolutionary history. A new open-access study published in Algorithms for Molecular Biology on 29 April 2026 puts that idea to a large-scale test, comparing 14 different embedding methods for clustering metabolic networks and asking how well the resulting groups match known taxonomic classifications. The work, led by Mattia Cervellini, Blerina Sinaimeri, Catherine Matias and Alessio Martino, covers 8,467 organisms drawn from the Kyoto Encyclopedia of Genes and Genomes (KEGG) database and represents one of the broadest head-to-head comparisons of hypergraph representation techniques in a real biological setting.

Metabolic networks are usually modeled as graphs, with metabolites as nodes and pairwise interactions between chemical compounds as edges. But this representation is lossy by construction: many metabolic reactions involve more than two participants, and flattening them into pairwise links discards that higher-order structure. Hypergraphs offer a more faithful alternative, because a single hyperedge can connect any number of metabolites, mirroring a reaction with multiple substrates and products. In this study, nodes represent metabolites labeled with KEGG compound identifiers, and hyperedges represent complete chemical reactions, so each organism becomes a node-labeled hypergraph encoding its full reaction repertoire.

The central question is whether the topology of these hypergraphs reflects systematic differences among evolutionarily distinct organisms. If so, an unsupervised clustering of the hypergraphs should recover taxonomic groupings without ever being told what those groupings are. The researchers tested this at four hierarchical levels provided by the KEGG BRITE taxonomy: C1, the fundamental cellular organization separating Eukaryotes from Prokaryotes; C2, the six major divisions of Animals, Archaea, Bacteria, Fungi, Plants and Protists; C3, a finer grouping typically at class, order or phylum level; and C4, the genus level.

To compare embeddings fairly, the team held the downstream clustering algorithm constant. Every embedding was fed into the same hierarchical clustering procedure based on Ward linkage, a classical and robust choice. Because the clustering step never varies, any difference in performance can be attributed to the informativeness of the embedding space itself rather than artifacts of the algorithm. The hierarchical approach also yields an entire family of clustering solutions with different numbers of clusters in one pass, which proved useful since there is no simple way to guess the right number of clusters in advance and the researchers wanted to compare classifications at multiple granularities.

The 14 strategies fall into three families. Bag-of-Words-inspired methods treat a metabolic hypergraph like a document, building explicit vectors over an alphabet of 2,835 compounds (Bag of Nodes, using statistics such as degree, centrality, betweenness and PageRank) or 3,236 distinct metabolic reactions (Bag of Hyperedges, a binary vector marking which reactions an organism performs). Kernel methods, including the Histogram Cosine Kernel, Jaccard Kernel, Edit Kernel and Stratified Edit Kernel, instead produce implicit embeddings as pairwise similarity matrices, treating hypergraphs as simplicial complexes. Neural network methods include Graph2Vec, applied to clique projections of the hypergraphs, and a Hypergraph Auto-Encoder trained to reconstruct the incidence matrix, with three architectural variants tested.

Performance was scored with homogeneity, an entropy-based measure bounded between 0 and 1 that rewards clustering solutions in which each cluster draws from a single class, and with purity, the fraction of a cluster belonging to its majority class. Because homogeneity rises naturally as clusters multiply, the number of clusters for each method was chosen by maximizing the silhouette score near the true number of classes. At the finer C3 and C4 levels, rare classes were excluded: classes with at least 100 organisms were retained for C3, leaving 7,622 organisms in 18 classes, and classes with at least 20 organisms for C4, leaving 3,237 organisms in 70 classes.

The results show that the choice of embedding matters enormously. The standout performers were Bag of Hyperedges with Jaccard distance, the Histogram Cosine Kernel and the Hypergraph Auto-Encoder with hyperedges-only encoding. Bag of Hyperedges with Jaccard distance reached homogeneity scores of at least 0.8 at every taxonomic level, and slightly above 0.95 at C1. The Histogram Cosine Kernel achieved perfect separation of Eukaryotes and Prokaryotes at C1 with the number of clusters equal to the number of classes, and Graph2Vec and the hyperedges-only auto-encoder matched that perfect performance. Notably, all three best methods build their representations directly from the hypergraph rather than from a clique expansion, suggesting that projecting hyperedges down to pairwise cliques loses biologically important detail.

The picture becomes more nuanced at finer levels. At C2, all methods tended to split Bacteria across multiple pure clusters, with purity above 0.8, while Eukaryotic kingdoms such as Animals, Fungi, Plants and Protists remained mixed in a single less pure cluster with purity around 0.6. This indicates that in these embedding spaces, different kinds of Bacteria are more widely separated from one another than different eukaryotic kingdoms are from each other, plausibly because Bacteria dominate the dataset and span enormous metabolic diversity. At C3 the separation was far from perfect, with some clusters highly pure and others ranging from 0.4 to 0.7 purity. At C4, however, performance was remarkably strong, with the vast majority of genus-level clusters showing very high purity for all three methods. The authors note that the problem is inherently difficult: even prior graph-based approaches could not clearly distinguish Bacteria from Archaea within Prokaryotes.

The study also carries practical lessons about representation design. Hyperedge-based embeddings consistently outperformed node-based ones, which the authors attribute to the hyperedge set coinciding exactly with the chemical reactions an organism performs, effectively a fingerprint of its taxonomy. Within the auto-encoder family, variants using only hyperedge embeddings beat those incorporating node-level convolution, hinting that reaction information, not compound-level message passing on extremely sparse hypergraphs, drives effective embeddings. The Stratified Edit Kernel, which weights all hyperedge sizes equally, fared poorly, likely because second-order hyperedges abound in metabolic hypergraphs. The authors also flag limitations: they considered undirected structures, losing information about reaction directionality and causality, and ignored stoichiometry.

For the authors, the takeaway is that the embedding method should be chosen according to the downstream task. Bag-of-Words methods are interpretable but potentially huge and sparse; kernels are mathematically grounded but opaque; neural embeddings are compact and dense but entangled. Beyond taxonomy recovery, the team suggests these embeddings could support metabolic pathway reconstruction, prediction of missing reactions, identification of functionally similar organisms, or analysis of host-microbiome metabolic complementarity, though each would need task-specific evaluation criteria. Future work, they write, should target the stubborn C2 and C3 levels and explore directed interactions and multiset hyperedges that respect stoichiometric coefficients.

Subject of Research: Comparing hypergraph embedding methods for unsupervised clustering of metabolic networks by taxonomy

Article Title: Comparing the ability of embedding methods on metabolic hypergraphs for capturing taxonomy-based features

Article References: Cervellini, M., Sinaimeri, B., Matias, C., & Martino, A. (2026). Comparing the ability of embedding methods on metabolic hypergraphs for capturing taxonomy-based features. Algorithms for Molecular Biology, 21(1), Article 9. https://doi.org/10.1186/s13015-026-00298-w

Image Credits: AI Generated

DOI: 10.1186/s13015-026-00298-w

Keywords: metabolic networks, hypergraphs, embedding methods, unsupervised clustering, taxonomy, KEGG, bioinformatics, graph kernels, auto-encoders, Bag of Hyperedges, homogeneity, systems biology