# RepBin: Constraint-based Graph Representation Learning for Metagenomic Binning

arXiv: https://arxiv.org/abs/2112.11696 · HTML: https://mlsanity.com/paper/2112.11696/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 57 references that are in the map.
- First posted on arXiv 22 Dec 2021.

## Builds on (most cited first, 13 of 13)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [A Survey on Network Embedding](https://mlsanity.com/paper/1711.08752/) (2017)
- [Attributed Graph Clustering via Adaptive Graph Convolution](https://mlsanity.com/paper/1906.01210/) (2019)
- [Unsupervised Attributed Multiplex Network Embedding](https://mlsanity.com/paper/1911.06750/) (2019)
- [A Framework for Deep Constrained Clustering -- Algorithms and Advances](https://mlsanity.com/paper/1901.10061/) (2019)

## Built on by (most cited first, 5 of 5)

- [Simple Contrastive Graph Clustering](https://mlsanity.com/paper/2205.07865/) (2022)
- [A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource](https://mlsanity.com/paper/2211.12875/) (2022)
- [Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation](https://mlsanity.com/paper/2507.13368/) (2025)
- [Graph Neural Networks for Microbial Genome Recovery](https://mlsanity.com/paper/2204.12270/) (2022)
- [Divide-Then-Rule: A Cluster-Driven Hierarchical Interpolator for Attribute-Missing Graphs](https://mlsanity.com/paper/2507.10595/) (2025)

## Abstract (arXiv)

Mixed communities of organisms are found in many environments (from the human gut to marine ecosystems) and can have profound impact on human health and the environment. Metagenomics studies the genomic material of such communities through high-throughput sequencing that yields DNA subsequences for subsequent analysis. A fundamental problem in the standard workflow, called binning, is to discover clusters, of genomic subsequences, associated with the unknown constituent organisms. Inherent noise in the subsequences, various biological constraints that need to be imposed on them and the skewed cluster size distribution exacerbate the difficulty of this unsupervised learning problem. In this paper, we present a new formulation using a graph where the nodes are subsequences and edges represent homophily information. In addition, we model biological constraints providing heterophilous signal about nodes that cannot be clustered together. We solve the binning problem by developing new algorithms for (i) graph representation learning that preserves both homophily relations and heterophily constraints (ii) constraint-based graph clustering method that addresses the problems of skewed cluster size distribution. Extensive experiments, on real and synthetic datasets, demonstrate that our approach, called RepBin, outperforms a wide variety of competing methods. Our constraint-based graph representation learning and clustering methods, that may be useful in other domains as well, advance the state-of-the-art in both metagenomics binning and graph representation learning.