%0 Journal Article %1 christian2009withinnetwork %A Desrosiers, Christian %A Karypis, George %D 2009 %J Machine Learning and Knowledge Discovery in Databases %K classification ecml label multi pkdd similarity structural %P 260--275 %T Within-Network Classification Using Local Structure Similarity %U http://dx.doi.org/10.1007/978-3-642-04180-8_34 %X Within-network classification, where the goal is to classify the nodes of a partly labeled network, is a semi-supervised learning problem that has applications in several important domains like image processing, the classification of documents, and thedetection of malicious activities. While most methods for this problem infer the missing labels collectively based on thehypothesis that linked or nearby nodes are likely to have the same labels, there are many types of networks for which thisassumption fails, e.g., molecular graphs, trading networks, etc. In this paper, we present a collective classification method,based on relaxation labeling, that classifies entities of a network using their local structure. This method uses a marginalizedsimilarity kernel that compares the local structure of two nodes with random walks in the network. Through experimentationon different datasets, we show our method to be more accurate than several state-of-the-art approaches for this problem.