Overlap-Robust Decision Boundary Learning for Within-Network Classification

Abstract

We study the problem of within network classification, where given a partially labeled network, we infer the labels of the remaining nodes based on the link structure. Conventional loss functions penalize a node based on a function of its predicted label and target label. Such loss functions under-perform while learning on a network having overlapping classes. In relational setting, even though the ground truth is not known for the unlabeled nodes, some evidence is present in the form of labeling acquired by the nodes in their neighborhood. We propose a structural loss function for learning in networks based on the hypothesis that loss is induced when a node fails to acquire a label that is consistent with the labels of the majority of the nodes in its neighborhood. We further combine this with a novel semantic regularizer, which we call homophily regularizer, to capture the smooth transition of discriminatory power and behavior of semantically similar nodes. The proposed structural loss along with the regularizer permits relaxation labeling. Through extensive comparative study on different real-world datasets, we found that our method improves over the state-of-the-art approaches.