Graph-regularized semi-supervised learning has been used effectively for classification when (i) instances are connected through a graph, and (ii) labeled data is scarce. If available, using multiple relations (or graphs) between the instances can improve the prediction performance. On the other hand, when these relations have varying levels of veracity and exhibit varying relevance for the task, very noisy and or irrelevant relations may deteriorate the performance. As a result, an effective weighing scheme needs to be put in place. In this work, we propose a robust and scalable approach for multi-relational graph-regularized semi-supervised classification. Under a convex optimization scheme, we simultaneously infer weights for the multiple graphs as well as a solution. We provide a careful analysis of the inferred weights, based on which we devise an algorithm that filters out irrelevant and noisy graphs and produces weights proportional to the informativeness of the remaining graphs. Moreover, the proposed method is linearly scalable w.r.t. the number of edges in the union of the multiple graphs. Through extensive experiments we show that our method yields superior results under different noise models, and under increasing number of noisy graphs and intensity of noise, as compared to a list of baselines and state-of-the-art approaches.
Mostafavi al @cite_33 @cite_29 construct the optimal composite graph by solving a linear regression problem using labeled data, later also used by Luo al @cite_37 . Different from most semi-supervised transductive methods that leverage both labeled and unlabeled data, these use only the labeled data to estimate the graph weights.
@cite_37 @cite_29 @cite_33
2120688086 2124649441
Motivation: Many algorithms that integrate multiple functional association networks for predicting gene function construct a composite network as a weighted sum of the individual networks and then use the composite network to predict gene function. The weight assigned to an individual network represents the usefulness of that network in predicting a given gene function. However, because many categories of gene function have a small number of annotations, the process of assigning these network weights is prone to overfitting. Results: Here, we address this problem by proposing a novel approach to combining multiple functional association networks. In particular, we present a method where network weights are simultaneously optimized on sets of related function categories. The method is simpler and faster than existing approaches. Further, we show that it produces composite networks with improved function prediction accuracy using five example species (yeast, mouse, fly, Esherichia coli and human). Availability: Networks and code are available from: http: morrislab.med.utoronto.ca sara SW Contact:smostafavi@cs.toronto.edu; quaid.morris@utoronto.ca Supplementary information:Supplementary data are available at Bioinformatics online. Background: Most successful computational approaches for protein function prediction integrate multiple genomics and proteomics data sources to make inferences about the function of unknown proteins. The most accurate of these algorithms have long running times, making them unsuitable for real-time protein function prediction in large genomes. As a result, the predictions of these algorithms are stored in static databases that can easily become outdated. We propose a new algorithm, GeneMANIA, that is as accurate as the leading methods, while capable of predicting protein function in real-time. Results: We use a fast heuristic algorithm, derived from ridge regression, to integrate multiple functional association networks and predict gene function from a single process-specific network using label propagation. Our algorithm is efficient enough to be deployed on a modern webserver and is as accurate as, or more so than, the leading methods on the MouseFunc I benchmark and a new yeast function prediction benchmark; it is robust to redundant and irrelevant data and requires, on average, less than ten seconds of computation time on tasks from these benchmarks. Conclusion: GeneMANIA is fast enough to predict gene function on-the-fly while achieving stateof-the-art accuracy. A prototype version of a GeneMANIA-based webserver is available at http: morrislab.med.utoronto.ca prototype.