A few good predictions: selective node labeling in a social network

Chaudhari, Gaurish ; Avadhanula, Vashist ; Sarawagi, Sunita (2014) A few good predictions: selective node labeling in a social network In: Proceedings of the 7th ACM international conference on Web search and data mining.

[img] PDF
973kB

Official URL: http://doi.org/10.1145/2556195.2556241

Related URL: http://dx.doi.org/10.1145/2556195.2556241

Abstract

Many social network applications face the following problem: given a network G=(V,E) with labels on a small subset O \subset V of nodes and an optional set of features on nodes and edges, predict the labels of the remaining nodes. Much research has gone into designing learning models and inference algorithms for accurate predictions in this setting. However, a core hurdle to any prediction effort is that for many nodes there is insufficient evidence for inferring a label. We propose that instead of focusing on the impossible task of providing high accuracy over all nodes, we should focus on selectively making the few node predictions which will be correct with high probability. Any selective prediction strategy will require that the scores attached to node predictions be well-calibrated. Our evaluations show that existing prediction algorithms are poorly calibrated. We propose a new method of training a graphical model using a conditional likelihood objective that provides better calibration than the existing joint likelihood objective. We augment it with a decoupled confidence model created using a novel unbiased training process. Empirical evaluation on two large social networks show that we are able to select a large number of predictions with accuracy as high as 95%, even when the best overall accuracy is only 40%.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to ACM, Inc
ID Code:128355
Deposited On:19 Oct 2022 10:13
Last Modified:14 Nov 2022 10:45

Repository Staff Only: item control page