Source-linked AI summary
Network Enhancement: a general method to denoise weighted biological networks
Bo Wang, Armin Pourshafeie, Marinka Zitnik, Junjie Zhu, Carlos D. Bustamante, Serafim Batzoglou, Jure Leskovec
TL;DR
Biological network analyses face noisy inputs that can hinder gene-function analysis, TAD detection, and similarity-based retrieval. The paper proposes Network Enhancement, a doubly stochastic denoising method whose spectral properties support improved downstream network performance and clarify its diffusion mechanism.
Problem
Noisy biological and similarity networks can hamper gene-function analysis, accurate TAD detection, and image retrieval.
Method
Network Enhancement denoises weighted undirected networks using a symmetric doubly stochastic matrix whose spectral transformation compresses small eigenvalue gaps and expands large ones.
Results
NE preserves eigenvectors, increases the eigengap for large eigenvalues, and improves downstream network performance through its diffusion mechanism.
Takeaways & Limitations
NE provides a general approach for denoising weighted undirected networks and improving downstream network performance.
Takeaways & Limitations
NE could be extended to use small amounts of accurately labeled data in its denoising methodology.
Abstract
from arXiv · showhide
Networks are ubiquitous in biology where they encode connectivity patterns at all scales of organization, from molecular to the biome. However, biological networks are noisy due to the limitations of measurement technology and inherent natural variation, which can hamper discovery of network patterns and dynamics. We propose Network Enhancement (NE), a method for improving the signal-to-noise ratio of undirected, weighted networks. NE uses a doubly stochastic matrix operator that induces sparsity and provides a closed-form solution that increases spectral eigengap of the input network. As a result, NE removes weak edges, enhances real connections, and leads to better downstream performance. Experiments show that NE improves gene function prediction by denoising tissue-specific interaction networks, alleviates interpretation of noisy Hi-C contact maps from the human genome, and boosts fine-grained identification accuracy of species. Our results indicate that NE is widely applicable for denoising biological networks.
Results
Across tissue, Hi-C, and image-similarity networks, Network Enhancement improved downstream prediction or community and cluster identification over raw or alternative-denoised networks.
- Human tissue networks: 12.0% average gene-function prediction improvement followed denoising across 22 human tissues and four denoising algorithms.All denoising algorithms improved average prediction performance.
- Human tissue networks: Relevant tissue-specific functions consistently ranked near the top by edge density, including blood coagulation in plasma and brain morphogenesis in brain networks.These rankings indicate improved signal-to-noise ratio in tissue networks.
- Hi-C interaction networks: NE achieved higher average Hi-C community-identification NMI than MU, ND, DSD, and raw data at both tested resolutions.MU achieved average NMI of 0.85 and 0.84, while raw data achieved 0.81 and 0.67 at 1kb and 5kb, respectively.
- Fine-grained species identification: NE transformed tangled butterfly-image similarity networks into 10 visible species clusters and improved retrieval of correct affinities.For top 40 retrievals, NE improved the raw network by 18.6%; for top 80, performance improved 41% over raw and more than 25% over the second-best alternative.
Discussion
The paper presents Network Enhancement as a general method for denoising weighted undirected networks. Its diffusion process preserves network structure while improving spectral properties and downstream analyses, with several extensions identified for future work.
- Network Enhancement is proposed as a general method for denoising weighted undirected networks.
- NE uses a symmetric, positive semi-definite, doubly stochastic matrix instead of a row-normalized transition matrix.
- The diffusion preserves eigenvectors, increases the eigengap for large eigenvalues, and disproportionately trims small eigenvalues.
- Extensive experiments show that NE fits biological network-analysis pipelines and improves downstream network performance.
- Future work includes using small amounts of labeled data, extending NE to multimodal networks, and integrating it with other analytic pipelines.
Methods
NE transforms a weighted network into an enhanced network on the same nodes by applying a localized diffusion process based on a symmetric doubly stochastic matrix. The process preserves key network properties, has a closed-form equilibrium, and modifies the spectrum to support downstream analysis.
- The goal of NE is to produce a network with a better representation of underlying module membership than the input network.
- NE replaces the generally asymmetric row-normalized transition matrix with a symmetric doubly stochastic matrix that yields a scale-free node-similarity matrix.
- The diffusion uses local structures and random walks of length three or less, while strengthening self-similarities.
- At every iteration, NE preserves symmetry and the doubly stochastic property, producing an undirected network with the same normalization as the initial network.
- The converged network has a closed-form spectral mapping that preserves eigenvectors, increases gaps between large eigenvalues, and reduces gaps between small eigenvalues.
- These spectral changes are associated with improved community detection and higher-order network analysis.
Supplementary information
The paper lists contributors from Stanford University and the Chan Zuckerberg Biohub, with one author currently at Illumina.
- The authors are affiliated with Stanford University departments spanning computer science, physics, electrical engineering, and biomedical data science.
- The affiliations also include the Chan Zuckerberg Biohub in San Francisco.
- One listed author is identified as currently working at Illumina Inc.
Supplementary Figures
Across supplementary evaluations, NE consistently outperforms alternative denoising methods for gene-function prediction and fine-grained species identification, with performance assessed across cross-validation settings and hyper-parameter choices.
- Gene function prediction: NE achieved the highest average AUROC across 22 tissues under leave-one-out cross-validation, reaching 0.742 versus 0.616 for RAW networks.The comparison included MU, ND, and DSD denoising methods.
- Gene function prediction: NE achieved the highest average AUROC across 22 tissues under 5-fold cross-validation, reaching 0.706 versus 0.572 for RAW networks.The same comparison included MU, ND, and DSD.
- Species identification: The butterfly-species evaluation examined sensitivity to σ, k, and the NE parameters K and α.The panels cover similarity-network construction and network-enhancement settings.
- Species identification: NE outperformed alternative methods for species identification across various values of K used in K-NN pruning.NE and MU performed better for smaller K, DSD improved as K increased, and ND performed best at an intermediate K.
Supplementary Note 1: Further information on datasets
The supplementary experiments assemble tissue-specific interaction, gene-function, Hi-C, and butterfly-image datasets, then apply denoising or similarity-network construction before downstream prediction or identification.
- Tissue-specific gene networks: Tissue-specific gene interaction networks from GIANT were filtered for edges with evidence supporting tissue-specific functional interactions before denoising.The resulting networks were used as input to a random-walk-based prediction procedure.
- Tissue-specific gene networks: Gene functions were defined using high-confidence Gene Ontology annotations restricted to specified experimental evidence codes and filtered for qualifiers.The annotations were retrieved from NCBI gene2go data in August 2016.
- Tissue-specific gene networks: The tissue-function mapping produced 22 tissues containing 309 tissue-specific gene functions, with each function supported by at least 20 associated genes.Mappings came from Greene et al. and used text matching followed by manual curation.
- Hi-C contact maps: Hi-C contact matrices were normalized with SQRTVC, and non-overlapping Arrowhead clusters were subsampled to create confident labels for downstream community detection.The selection used the first 15 eligible clusters per chromosome.
- Butterfly species identification: The butterfly dataset contained 832 images from 10 species classes, represented using Fisher Vector and VLAD descriptors with dense SIFT.The two encoding methods were combined through the network-based approach.
- Butterfly species identification: Similarity graphs were constructed from image features using Gaussian or locally scaled kernels, with k = 20 and σ = 0.5 as default values.The local-scale formulation estimates variance from each point’s top k neighbors.
Supplementary Note 2: Definition of Evaluation Metrics
The supplementary note defines clustering consistency and retrieval accuracy metrics used to evaluate network-based identification, emphasizing agreement with true labels and correct same-class retrievals.
- Clustering evaluation: Normalized Mutual Information is computed as I(U, V) / max{H(U), H(V)} to measure consistency between two clusterings.I(U, V) is mutual information, while H(U) and H(V) are clustering entropies.
- Clustering evaluation: The mutual-information calculation uses the number of data points and cluster cardinalities from the two assignments.The associated entropy terms quantify each clustering assignment.
- Image retrieval evaluation: Retrieval accuracy for a query is based on the fraction of retrieved objects sharing the query’s class, and mean accuracy averages this quantity across all images.Correct retrievals are images from the same class as the query.
Supplementary Note 3: Theoretical analysis of Network Enhancement
Network Enhancement (NE) iteratively diffuses a weighted network through a symmetric doubly stochastic operator while preserving key structural properties. The process has a closed-form equilibrium, preserves eigenvectors, and enlarges eigengaps among large eigenvalues, improving robustness to perturbations.
- Network Enhancement Preserves Properties of DSM: NE constructs a symmetric doubly stochastic transition operator from a weighted graph and preserves symmetry, normalization, and positive semidefiniteness across iterations.Theorem 1 states that every W_t remains a symmetric DSM, remains positive semidefinite when initialized positive semidefinite, and converges to a symmetric DSM.
- Network Enhancement Preserves Properties of DSM: W_t converges to the non-trivial equilibrium graph W_t→1 = (1−α)T(I−αT^2)^−1.The equilibrium is the closed-form limit of the diffusion process, initialized with W_t=0 = W and regularized by α.
- Spectral Analysis of Network Enhancement: NE preserves the eigenvectors of the initial symmetric DSM while applying the nonlinear eigenvalue map f_α(λ) to its eigenvalues.The transformation provides a spectral description of the converged graph without changing the original eigenvectors.
- Spectral Analysis of Network Enhancement: NE increases eigengaps associated with large eigenvalues and thereby improves the graph’s robustness to symmetric perturbations.The perturbation analysis links the enlarged leading eigengaps to a smaller upper bound on the distance between perturbed and unperturbed leading eigenspaces.
- Spectral Analysis of Network Enhancement: With α=0.85, c(α)=0.78; NE expands gaps above this threshold while compressing gaps among smaller eigenvalues.All eigenvalues are reduced, but small eigenvalues are reduced more aggressively than large eigenvalues, producing a smoothed PCA-like effect without eliminating singular values.