Unsupervised Learning from Noisy Networks with Applications to Hi-C Data
Complex networks play an important role in a plethora of disciplines in natural sciences. Cleaning up noisy observed networks poses an important challenge in network analysis. Existing methods utilize labeled data to alleviate the noise the noise levels. However, labeled data is usually expensive to collect while unlabeled data can be gathered cheaply. In this paper, we propose an optimization framework to mine useful structures from noisy networks in an unsupervised manner. The key feature of our optimization framework is its ability to utilize local structures as well as global patterns in the network. We extend our method to incorporate multiresolution networks in order to add further resistance in the presence of high-levels of noise. The framework is generalized to utilize partial labels in order to further enhance the performance. We empirically test the effectiveness of our method in denoising a network by demonstrating an improvement in community detection results on multi-resolution Hi-C data both with and without Capture-C-generated partial labels.
has been shown to have a fundamental impact on gene expression in biological processes [4]. For example, many genes are in 3D contact with genomic regions that are far away in the linear genome but close in 3D space. These genomic regions contain regulatory elements that control when the gene is active [5,6,34]. The rules by which regulatory elements come in contact with their target genes are still unclear [7]. While the exact mechanism for this selective interaction between the regulatory elements and the target genes is unknown, the 3D organization of the genome in domains of interaction seem to play a crucial role. Furthermore, topologically associated domains (TADs) [8], where local interactions are observed, are of potential biological interest as they have been shown to be conserved between mice and humans, which suggests an ancient root for higher order structures in the genome [8].
The interaction map of regulatory elements in a genome can be viewed as a network, where each node is a regulatory element and each link represents the interaction strength between two of the elements. In this context, we not only have prior knowledge about the types of structures in this interaction network, but we also have various types of noisy and incomplete observations of the links in this network based on recently-developed technologies.
One approach to observe these links is Hi-C, an experiment which uses high-throughput sequencing to construct a 2D contact map measuring the frequency with which pairs of genomic regions co-localize in 3D space. The results of Hi-C experiments can be summarized at multiple resolutions (lower resolutions are obtained by binning genomic regions together), ranging from 1 kb to 1 Mb [8][9][10]. Higher resolution maps capture more fine grained location interactions but the background noise generated by random collisions can be larger [11]. Lower resolution maps have less noise, but at the cost of losing the exact localization of genomic contacts. In addition to Hi-C, there are other experiment variants such as 4C, 5C and Capture-C technologies, which provide a new window into detection of a small number of interaction links with high confidence [12][13][14][15], by focusing sequencing resources on a selected subset of contacts. For these experiments the increased confidence comes at the cost of not measuring the full contact map. Thus, the integration of multi-resolution noisy Hi-C data with high-confidence Capture-C data is not only an interesting problem in the context of general network densoising but it is also biologically relevant.
The authors describe an optimization approach to identify clusters (communities) in a network while combining multiple noisy versions of the network. In addition their framework allows to incorporate high confidence evidence (though I’m not convinced that this part of their method is very effective). The authors apply their method to combine multiple resolutions of Hi-C data and analyze their approach on a simplified setting of disjoint blocks and in the presence of increasing amount of noise.
I believe the review of this paper should be done in 2 stages: 1) method; 2) application.  The method, as presented, is fairly general and could be applied to many different scenarios. It is a relatively novel method for network de-noising – combining multiple networks from noisy observations of the true underlying networks, in particular network that is made of more or less clear clusters. In this context the method is well described. I would be interested to know how well does it scale – the complexity and running time of the method on networks of various size. I understand that it probably doesn’t scale too well given that the genome had to be broken up into chromosomes and the chromosomes that were presented were not the largest. What is the resolution? How many nodes was the biggest network tested? Regularization in section 2.3 (to add high confidence edges) is not really fixing the edges – you could have the same number of completely different edges and it would still look ok (since you are only looking at sums here). Can you check how much it hurts you? You could regularize the edges directly… I think it would be interesting to see the effects of this regularization (the results in the experimental section support the fact that you are not using your high-confidence edges to the fullest…)  The application, I believe, is somewhat problematic. You start your paper talking about community detection. I’m not sure that’s the best or most important use of Hi-C data. You also keep talking about de-noising and community detection? Which is it? What is the biological motivation for community detection? Does one necessarily lead to the other? The link for me is missing. We don’t actually know whether true 3D genome data clusters nicely. Certainly, for many applications in biology, it would be nice to keep the 3D structure of this data preserved as a network rather than clusters. Going to the cluster level is really not the wholly grail of this data and in that, the method and the motivation of the work are misleading. In any case, I was not convinced by the motivation that cluster representation is the way to go (or even the right kind of embedding) for Hi-C data. The abstract was also misleading “we propose to mine useful structures from noisy networks”… - why are they useful? And also by structures here, I could imagine something more informative than relatively large clusters on which the method was ultimately tested.  In the same spirit, I’m not sure that in the method, as applied in this particular scenario, S should be low ranked, sparse yes, but low rank? I’m not sure that is true of the biology here.   Experiments To me, a more useful use of network denoising in the Hi-C data context would have been combining different resolutions of this data and testing the resulting denoised network with the Capture-C data – how well would your de-noising go? Also, there are other approaches combining multiple networks, such as Similarity Network Fusion (Wang et al, 2014) that this work could be compared to.  When you describe figure 2c in the text, you shouldn’t really be describing what is on the figure – that goes in the caption. In the caption of the figure, you shouldn’t really be describing that one method is performing better than the other, just what the figure is about, not the conclusions one would draw from it. The experimental section definitely requires some clarification, it is very confusing now. In figure 2a it’s not clear what you used as a baseline. In figure 2b – why is the \alpha_8 coefficient also going down?  Details: There are a lot of typos and strange use of long words, somebody has to read the manuscript very carefully and simplify/fix the English a bit. Section 3.1. Can you provide more intuition for J(R)? It’s not obvious what it captures. Line 123 L2 is not properly written In Figure 1 you first say that you combine (a,b,c) and then that you combine all 8 resolutions, so which is it? Please write what you actually have done and what is in the figure. If these are two different things, then please write that clearly. Figure 2c comes first, prior to Figures 2a and 2b, perhaps you could decouple these, so that they would be cited appropriately? They shouldn’t really be one figure