RepBin: Constraint-Based Graph Representation Learning for Metagenomic Binning

Hansheng Xue, Vijini Mallawaarachchi, Yujia Zhang, Vaibhav Rajan, Yu Lin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationAAAI-22 Technical Tracks 4
Place of PublicationPalo Alto, California
PublisherAssociation for the Advancement of Artificial Intelligence
Number of pages9
ISBN (Electronic)1577358767, 9781577358763
Publication statusPublished - 28 Jun 2022
Externally publishedYes
Event36th AAAI Conference on Artificial Intelligence, AAAI 2022 - Virtual, Online
Duration: 22 Feb 20221 Mar 2022

Publication series

NameProceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022


Conference36th AAAI Conference on Artificial Intelligence, AAAI 2022
CityVirtual, Online


  • RepBin
  • mixed communities
  • Metagenomic binning
  • metagenomics
  • DNA subsequences
  • organisms


Dive into the research topics of 'RepBin: Constraint-Based Graph Representation Learning for Metagenomic Binning'. Together they form a unique fingerprint.

Cite this