對於圖上節點的多標籤分類問題來說，傳統的傳播演算法十分依賴每筆資料的特徵資訊以建立轉移矩陣，並以此在圖上傳播標籤資訊。然而，隨著圖形資料的快速成長，要正確且完整地收集每一筆資料的所有特徵更顯費時昂貴，因此，傳播演算法在無特徵的圖形資料上通常難以取得較好的分類表現。根據我們的觀察，在此情況下，傳播演算法在傳播標籤資訊的過程時常發生忽略少數意見的問題。在這篇論文中，我們提出了一種稱為 Label Propagation-Based Classification (LPBC) 的框架使 Label Propagation (LP) 能較好的處理無特徵圖上的多標籤分類問題。透過特別的多標籤門檻學習，LPBC 減少了傳播演算法在傳播標籤資訊的過程中，忽略少數意見問題的發生，而實驗結果也展現了相較於 LP，我們所提出框架的有效性與效能的增強。

Recently, with the exponential growth of network data, collecting whole features of each node correctly is time-consuming and expensive. For a classification problem on networks, traditional propagation algorithms, which rely on the feature information to build transition matrix to propagate label information on networks, generally do not perform well when the feature information is not available. Our observation shows that the problem of minority ignorance occurs on the propagation process of traditional algorithms. In this paper, we propose a LPBC framework to allow the Label Propagation (LP) algorithm to deal with multi-label classification problem on non-feature networks. With a novel threshold learning process, LPBC reduces the minority ignorance when the label information is propagated. Experimental results demonstrated the effectiveness and the performance improvement of the proposed framework.

1. S. Nandanwar and M. N. Murty, “Structural neighborhood based classification of nodes in a network,” in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016. p. 1085-1094
2. W. Ye, L. Zhou, D. Mautz, C. Plant and C. Böhm, “Learning from Labeled and Unlabeled Vertices in Networks,” in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2017. p. 1265-1274.
3. Y. Zhao, L. Li and X. Wu, “Link Prediction-Based Multi-label Classification on Networked Data,” in Data Science in Cyberspace (DSC), IEEE International Conference on. IEEE, 2016. p. 61-68.
4. D. Wang, P. Cui and W. Zhu, “Structural deep network embedding,” in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016. p. 1225-1234.
5. B. Perozzi, R. Al-Rfou and S. Skiena, “Deepwalk: Online learning of social rep-resentations,” in Proceedings of the 20th ACM SIGKDD international confer-ence on Knowledge discovery and data mining. ACM, 2014. p. 701-710.
6. X. Li and Y. Guo, “Active Learning with Multi-Label SVM Classification,” in Proceedings of the 23rd International Joint Conference on Artificial Intelli-gence, 2013. p. 1479-1485.
7. L. Feremans, B. Cule, C. Vens and B. Goethals, “Combining Instance and Fea-ture neighbors for Efficient Multi-label Classification,” 2017.
8. Z. Lin and B. Dai, “Reweighting Forest for Extreme Multi-label Classification,” in International Conference on Big Data Analytics and Knowledge Discovery. Springer, Cham, 2017. p. 286-299.
9. X. Zhu and Z. Ghahramani, “Learning from labeled and unlabeled data with la-bel propagation,” in Technical Report CMU-CALD-02-107, Carnegie Mellon University, 2002.
10. O. Zoidi, E. Foriadou, N. Nikolaidis and I. Pitas, “Graph-based label propagation in digital media: A review,” ACM Computing Surveys (CSUR), 2015, 47.3: 48.
11. A. Anagnostopoulos, R. Kumar and M. Mahdian, “Influence and correlation in social networks,” in Proceedings of the 14th ACM SIGKDD international con-ference on Knowledge discovery and data mining. ACM, 2008. p. 7-15.
12. D. Zhou, O. Bousquet, T. N. Lal, J. Weston and B. Schölkopf, “Learning with local and global consistency,” in Advances in neural information processing sys-tems. 2004. p. 321-328.
13. M. Zhang, and Z. Zhou, “A review on multi-label learning algorithms,” IEEE transactions on knowledge and data engineering, 2014, 26.8: 1819-1837.
14. Goyal, Palash, and Emilio Ferrara. “Graph embedding techniques, applications, and performance: A survey,” Knowledge-Based Systems 151 (2018): 78-94.
15. Fan, Rong-En, et al. “LIBLINEAR: A library for large linear classifica-tion,” Journal of machine learning research 9.Aug (2008): 1871-1874.