Leveraging Structure to Improve Classification Performance in Sparsely Labeled Networks

Gallagher, B ; Eliassi-Rad, T

Lawrence Livermore National Laboratory

关键词: Classification;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;    Algorithms;    Performance;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;   

DOI  :  10.2172/926032
RP-ID  :  UCRL-TR-235752
RP-ID  :  W-7405-ENG-48
RP-ID  :  926032

美国|英语

来源: UNT Digital Library

【 摘 要 】

We address the problem of classification in a partially labeled network (a.k.a. within-network classification), with an emphasis on tasks in which we have very few labeled instances to start with. Recent work has demonstrated the utility of collective classification (i.e., simultaneous inferences over class labels of related instances) in this general problem setting. However, the performance of collective classification algorithms can be adversely affected by the sparseness of labels in real-world networks. We show that on several real-world data sets, collective classification appears to offer little advantage in general and hurts performance in the worst cases. In this paper, we explore a complimentary approach to within-network classification that takes advantage of network structure. Our approach is motivated by the observation that real-world networks often provide a great deal more structural information than attribute information (e.g., class labels). Through experiments on supervised and semi-supervised classifiers of network data, we demonstrate that a small number of structural features can lead to consistent and sometimes dramatic improvements in classification performance. We also examine the relative utility of individual structural features and show that, in many cases, it is a combination of both local and global network structure that is most informative.