×

A neural network algorithm for semi-supervised node label learning from unbalanced data. (English) Zbl 1293.68222

Summary: Given a weighted graph and a partial node labeling, the graph classification problem consists in predicting the labels of all the nodes. In several application domains, from gene to social network analysis, the labeling is unbalanced: for instance positive labels may be much less than negatives. In this paper we present COSNet (COst Sensitive neural Network), a neural algorithm for predicting node labels in graphs with unbalanced labels. COSNet is based on a 2-parameter family of Hopfield networks, and consists of two main steps: (1) the network parameters are learned through a cost-sensitive optimization procedure; (2) a suitable Hopfield network restricted to the unlabeled nodes is considered and simulated. The reached equilibrium point induces the classification of the unlabeled nodes. The restriction of the dynamics leads to a significant reduction in time complexity and allows the algorithm to nicely scale with large networks. An experimental analysis on real-world unbalanced data, in the context of the genome-wide prediction of gene functions, shows the effectiveness of the proposed approach.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
92D10 Genetics and epigenetics
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Agresti, A.; Coull, B. A., Approximate is better than exact for interval estimation of binomial proportions, Statistical Science, 52, 119-126 (1998)
[2] Azran, A., The rendezvous algorithm: multiclass semi-supervised learning with Markov random walks, (Proceedings of the 24th international conference on machine learning. Proceedings of the 24th international conference on machine learning, ICML’07 (2007), ACM: ACM New York, NY, USA), 49-56
[3] Belkin, M.; Matveeva, I.; Niyogi, P., Regularization and semi-supervised learning on large graphs, (COLT (2004), Springer), 624-638 · Zbl 1078.68685
[4] Belkin, M.; Niyogi, P., Using manifold structure for partially labeled classification, Advances in Neural Information Processing Systems, 15, 929-936 (2003)
[5] Bengio, Y.; Delalleau, O.; Le Roux, N., Label propagation and quadratic criterion, (Chapelle, O.; Scholkopf, B.; Zien, A., Semi-supervised learning (2006), MIT Press), 193-216
[6] Bertoni, A.; Frasca, M.; Valentini, G., COSNet: a cost sensitive neural network for semi-supervised learning in graphs, (Machine learning and knowledge discovery in databases— European conference on machine learning and principles and practice of knowledge discovery in databases. Machine learning and knowledge discovery in databases— European conference on machine learning and principles and practice of knowledge discovery in databases, ECML PKDD (2011), Springer: Springer Berlin, Heidelberg), 219-234
[7] Bogdanov, P.; Singh, A. K., Molecular function prediction using neighborhood features, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 7, 208-217 (2010)
[8] Borgatti, S.; Mehra, A.; Brass, D.; Labianca, G., Network analysis in the social sciences, Science, 232, 892-895 (2009)
[9] Brown, M. P.S., Knowledge-based analysis of microarray gene expression data by using support vector machines, Proceedings of the National Academy of Sciences of the United States of America, 97, 267-276 (2000)
[10] Brown, L. D.; Cai, T. T.; Dasgupta, A., Interval estimation for a binomial proportion, Statistical Science, 16, 101-133 (2001) · Zbl 1059.62533
[11] Cesa-Bianchi, N.; Re, M.; Valentini, G., Synergy of multi-label hierarchical ensembles, data fusion, and cost-sensitive methods for gene functional inference, Machine Learning, 88, 209-241 (2012) · Zbl 1243.68234
[12] Cesa-Bianchi, N.; Valentini, G., Hierarchical cost-sensitive algorithms for genome-wide gene function prediction, Journal of Machine Learning Research, W&C Proceedings, Machine Learning in Systems Biology, 8, 14-29 (2010)
[13] Chua, H. N.; Sung, W.-K.; Wong, L., Exploiting indirect neighbours and topological weight to predict protein function from protein-protein interactions, Bioinformatics, 22, 1623-1630 (2006)
[14] Chua, H.; Sung, W.; Wong, L., An efficient strategy for extensive integration of diverse biological data for protein function prediction, Bioinformatics, 23, 3364-3373 (2007)
[16] Deng, M.; Chen, T.; Sun, F., An integrated probabilistic model for functional prediction of proteins, Journal of Computational Biology, 11, 463-475 (2004)
[17] Dorogovtsev, S.; Mendes, J., Evolution of networks: from biological nets to the Internet and WWW (2003), Oxford University Press: Oxford University Press Oxford · Zbl 1109.68537
[18] Eddy, S. R., Profile hidden Markov models, Bioinformatics, 14, 755-763 (1998)
[19] Finn, R.; Mistry, J.; Tate, J.; Coggill, P.; Heger, A.; Pollington, J., The Pfam protein families database, Nucleic Acids Research, 38, D211-D222 (2010)
[20] Friedberg, I., Automated protein function prediction—the genomic challenge, Briefings in Bioinformatics, 7, 225-242 (2006)
[21] Gasch, P., Genomic expression programs in the response of yeast cells to environmental changes, Molecular Biology of the Cell, 11, 4241-4257 (2000)
[22] Goldberg, A.; Tarjan, R., A new approach to the maximum flow problem, Journal of the ACM (JACM), 35, 921-940 (1988) · Zbl 0661.90031
[23] Hopfield, J., Neural networks and physical systems with emergent collective compatational abilities, Proceedings of the National Academy of Sciences of the United States of America, 79, 2554-2558 (1982) · Zbl 1369.92007
[24] Karaoz, U., Whole-genome annotation by using evidence integration in functional-linkage networks, Proceedings of the National Academy of Sciences of the United States of America, 101, 2888-2893 (2004)
[25] Kloft, M.; Brefeld, U.; Sonnenburg, S.; Laskov, P.; Müller, K.-R.; Zien, A., Efficient and accurate lp-norm multiple kernel learning, Advances in Neural Information Processing Systems, 22, 997-1005 (2009)
[27] Li, X.; Chen, H.; Li, J.; Zhang, Z., Gene function prediction with gene interaction networks: a context graph kernel approach, IEEE Transactions on Information Technology in Biomedicine, 14, 119-128 (2010)
[29] Marcotte, E.; Pellegrini, M.; Thompson, M.; Yeates, T.; Eisenberg, D., A combined algorithm for genome-wide prediction of protein function, Nature, 402, 83-86 (1999)
[30] Mostafavi, S.; Ray, D.; Farley, D. W.; Grouios, C.; Morris, Q., Genemania: a real-time multiple association network integration algorithm for predicting gene function, Genome Biology, 9, S4+ (2008)
[31] Murali, T. M.; Wu, C.-J.; Kasif, S., The art of gene function prediction, Nature Biotechnology, 24, 1474-1475 (2006)
[32] Nabieva, E.; Jim, K.; Agarwal, A.; Chazelle, B.; Singh, M., Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps, Bioinformatics, 21, 302-310 (2005)
[33] Oliver, S., Guilt-by-association goes global, Nature, 403, 601-603 (2000)
[34] Pavlidis, P.; Cai, J.; Weston, J.; Noble, W. S., Learning gene functional classifications from multiple data types, Journal of Computational Biology, 9, 401-411 (2002)
[35] Pena-Castillo, L., A critical assessment of Mus musculus gene function prediction using integrated genomic evidence, Genome Biology, 9, S1 (2008)
[36] Re, M.; Mesiti, M.; Valentini, G., A fast ranking algorithm for predicting gene functions in biomolecular networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 9, 1812-1818 (2012)
[37] Re, M.; Valentini, G., Cancer module genes ranking using kernelized score functions, BMC Bioinformatics, 13, S14 (2012)
[38] Rojas, R., Neural networks—a systematic introduction (1996), Springer-Verlag: Springer-Verlag Berlin · Zbl 0861.68072
[39] Ruepp, A., The FunCat, a functional annotation scheme for systematic classification of proteins from whole genomes, Nucleic Acids Research, 32, 5539-5545 (2004)
[40] Sharan, R.; Ulitsky, I.; Shamir, R., Network-based prediction of protein function, Molecular Systems Biology, 3, 88 (2007)
[41] Smola, A.; Kondor, I., Kernel and regularization on graphs, (Scholkopf, B.; Warmuth, M., Proc. of the annual conf. on computational learning theory. Proc. of the annual conf. on computational learning theory, Lecture notes in computer science (2003), Springer), 144-158 · Zbl 1274.68351
[42] Sonnenburg, S.; Rätsch, G.; Schäfer, C.; Schölkopf, B., Large scale multiple kernel learning, Journal of Machine Learning Research, 7, 1531-1565 (2006) · Zbl 1222.90072
[43] Spellman, P. T., Comprehensive identification of cell cycle-regulated genes of the yeast saccharomyces cerevisiae by microarray hybridization, Molecular Biology of the Cell, 9, 3273-3297 (1998)
[44] Stark, C.; Breitkreutz, B. J.; Reguly, T.; Boucher, L.; Breitkreutz, A.; Tyers, M., Biogrid: a general repository for interaction datasets, Nucleic Acids Research, 34, D535-D539 (2006)
[45] Szummer, M.; Jaakkola, T., Partially labeled classification with Markov random walks, Advances in Neural Information Processing Systems (NIPS), 14, 945-952 (2001), MIT Press
[46] Tsirukis, A. G.; Reklaitis, G. V.; Tenorio, M. F., Nonlinear optimization using generalized hopfield networks, Neural Computation, 1, 511-521 (1989)
[47] Tsuda, K.; Shin, H.; Scholkopf, B., Fast protein classification with multiple networks, Bioinformatics, 21, ii59-ii65 (2005)
[48] Valentini, G., True path rule hierarchical ensembles for genome-wide gene function prediction, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8, 832-847 (2011)
[49] Vazquez, A.; Flammini, A.; Maritan, A.; Vespignani, A., Global protein function prediction from protein-protein interaction networks, Nature Biotechnology, 21, 697-700 (2003)
[50] Von Mering, C., Comparative assessment of large-scale data sets of protein-protein interactions, Nature, 417, 399-403 (2002)
[51] Wang, D., Temporal pattern processing, (The handbook of brain theory and neural networks (2003)), 1163-1167
[52] Wilcoxon, F., Individual comparisons by ranking methods, Biometrics, 1, 80-83 (1945)
[53] Wuchty, S.; Ravasz, E.; Barabási, A. L., The architecture of biological networks, Complex Systems in Biomedicine, 5259, 165-181 (2003)
[54] Zhang, F.; Zhang, H., Applications of a neural network to watermarking capacity of digital image, Neurocomputing, 67, 345-349 (2005)
[55] Zhou, D., Learning with local and global consistency, Advances in Neural Information Processing Systems, 16, 321-328 (2004)
[56] Zhu, X.; Ghahramani, Z.; Lafferty, J., Semi-supervised learning using Gaussian fields and harmonic functions, (ICML (2003)), 912-919
[57] Zhu, W.; Hou, J.; Chen, Y.-P. P., Semantic and layered protein function prediction from ppi networks, Journal of Theoretical Biology, 267, 129-136 (2010) · Zbl 1410.92041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.