A Sample Dependent Decision Fusion Algorithm for Graph-based Semi-supervised Learning

Document Type : Original Article


Faculty of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran


On many occasions, the evaluation of a phenomenon based on a single feature could not solely be resulted in comprehensive and accurate results. Moreover, even if we have several features, we don’t know in advance, which feature offers a better description of the phenomenon. Thus, selecting the best features and especially their combination could lead to better results. An affinity graph is a tool that can describe the relationship between the samples. In this paper, we proposed a graph-based sample-based ranking method that sorts the graphs based on six proposed parameters. The sorting is performed such that the graphs at the top of the list have better performance compared to the graphs at the bottom. Furthermore, we propose a fusion method to merge the information of various features and improve the accuracy of label propagation. Moreover, a method is proposed for parameter optimizations and the ultimate decision fusion. The experimental results indicate that the proposed scheme, apart from correctly ranking the graphs according to their accuracy, in the fusion step, increases the accuracy compared to the use of a single feature.


1. Wang, B., Mezlini, A.M., Demir, F., Fiume, M., Tu, Z., Brudno, 
M., Haibe-Kains, B. and Goldenberg, A., “Similarity network
fusion for aggregating data types on a genomic scale”, Nature
Methods, Vol. 11, No. 3, (2014), 333–337.  
2. Zhu, X., “Semi-Supervised Learning: From Gaussian Fields to
Gaussian Processes”, (2003), 1-21.
3. Szummer, M. and Jaakkola, T., “Partially labeled classification
with Markov random walks”, In Advances in Neural
Information Processing Systems 14: Proceedings of the 2001
Conference (Vol. 2), MIT Press, (2002), 945–952.  
4. Joachims, T., “Transductive learning via spectral graph
partitioning”, In Proceedings of the 20th International
Conference on Machine Learning (ICML-03), (2003), 290–297.  
5. Sindhwani, V., Niyogi, P., and Belkin, M., “Beyond the point
cloud: from transductive to semi-supervised learning”, In
Proceedings of the 22nd international conference on Machine
learning, (2005), 824–831.  
6. Belkin, M., Niyogi, P., and Sindhwani, V., “Manifold
regularization: A geometric framework for learning from labeled
and unlabeled examples”, Journal of machine learning
research, Vol. 7, No. Nov, (2006), 2399–2434.  
7. Blum, A. and Chawla, S., “Learning from labeled and unlabeled
data using graph mincuts” In Proceedings of the Eighteenth
International Conference on Machine Learning, (2001), 19-26. 
8. Bengio, Y., Delalleau, O., and Le Roux, N., “label propagation
and quadratic criterion”, MIT Press, (2006), 35-112. 
9. Herbster, M., Pontil, M., and Wainer, L., “Online learning over
graphs”, In Proceedings of the 22nd international conference on
Machine learning, (2005), 305–312.  
10. Thrun, S., Saul, L.K., and Schölkopf, B., Advances in Neural
Information Processing Systems 16: Proceedings of the 2003
Conference, Vol. 16, MIT press (2004). 
11. Wang, B., Tu, Z., and Tsotsos, J. K., “Dynamic label
propagation for semi-supervised multi-class multi-label
classification”, In Proceedings of the IEEE international
conference on computer vision, (2013), 425–432.  
12. Gui, J., Hu, R., Zhao, Z. and Jia, W., “Semi-supervised learning
with local and global consistency”, International Journal of
Computer Mathematics, Vol. 91, No. 11, (2014), 2389–2402.  
13. Lu, J., Hu, J., and Tan, Y.-P., “Discriminative deep metric
learning for face and kinship verification”, IEEE Transactions
on Image Processing, Vol. 26, No. 9, (2017), 4269–4282.  
14. Mirmahboub, B., Mekhalfi, M. L., and Murino, V., “Person reidentification
by order-induced metric fusion”,
Neurocomputing, Vol. 275, (2018), 667–676.  
15. Zhang, H., Huang, T.S., Nasrabadi, N.M. and Zhang, Y.,
“Heterogeneous multi-metric learning for multi-sensor fusion”, 
In 14th International Conference on Information Fusion, (2011),
16. Zhang, L. and Zhang, D., “Metricfusion: Generalized metric
swarm learning for similarity measure”, Information Fusion,
Vol. 30, (2016), 80–90.  
17. Karasuyama, M. and Mamitsuka, H., “Multiple graph label
propagation by sparse integration”, IEEE Transactions on
Neural Networks and Learning Systems, Vol. 24, No. 12,
(2013), 1999–2012.  
18. Saeedeh, B. and Bosaghzadeh, A., “Deep graph fusion for graph
based label propagation”, In 2017 10th Iranian Conference on
Machine Vision and Image Processing (MVIP), (2017), 149–
19. An, L., Chen, X., and Yang, S., “Multi-graph feature level fusion
for person re-identification”, Neurocomputing, Vol. 259,
(2017), 39–45.  
20. Tong, T., Gray, K., Gao, Q., Chen, L., Rueckert, D. and
Alzheimer's Disease Neuroimaging Initiative, “Multi-modal
classification of Alzheimer’s disease using nonlinear graph
fusion”, Pattern Recognition, Vol. 63, (2017), 171–181.  
21. Lin, G., Liao, K., Sun, B., Chen, Y. and Zhao, F., “Dynamic
graph fusion label propagation for semi-supervised multimodality
classification”, Pattern Recognition, Vol. 68, (2017),
22. Zhang, H., Li, S., Shi, Y. and Yang, J., “Graph Fusion for Finger
Multimodal Biometrics”, IEEE Access, Vol. 7, (2019), 28607–
23. Cheng, Y., Li, Y., Liu, Q., Yao, Y., Sai Vijay Kumar Pedapudi,
V., Fan, X., Su, C. and Shen, S., “A graph based unsupervised
feature aggregation for face recognition”, In Proceedings of the
IEEE International Conference on Computer Vision Workshops,
(2019), 1-10. 
24. Zhu, X., Ghahramani, Z., and Lafferty, J. D., “Semi-supervised
learning using gaussian fields and harmonic functions”, In
Proceedings of the 20th International conference on Machine
learning (ICML-03), (2003), 912–919.  
25. Zhou, D., Bousquet, O., Lal, T.N., Weston, J. and Schölkopf, B.,
“Learning with local and global consistency”, In Advances in
Neural Information Processing Systems, (2004), 321–328. 
26. Dornaika, F., Kejani, M. T., and Bosaghzadeh, A., “Graph
construction using adaptive Local Hybrid Coding scheme”,
Neural Networks, Vol. 95, (2017), 91–101.  
27. Ojala, T., Pietikäinen, M., and Mäenpää, T., “Multiresolution
gray-scale and rotation invariant texture classification with local
binary patterns”, IEEE Transactions on Pattern Analysis &
Machine Intelligence, Vol. 24, No. 7, (2002), 971–987.  
28. Tuzel, O., Porikli, F., and Meer, P., “Region covariance: A fast
descriptor for detection and classification”, In European
conference on computer vision, Springer, Berlin, Heidelberg,
(2006), 589–600.  
29. Fujiwara, Y., Ida, Y., Arai, J., Nishimura, M. and Iwamura, S.,
“Fast algorithm for the lasso based l1-graph construction”, Proceedings of the VLDB Endowment, Vol. 10, No. 3, (2016),