We study the problem of inferring labels on the nodes of a graph.
Given a partially labeled graph, our goal is to infer a label for each
unlabeled node of the graph. Additionally, since the set of nodes and
labels are potentially large, we need methods that use limited space
and are simple to implement. Our main contribution is an iterative
framework to solve this problem, using variety of methods to combine
label distributions from neighbors and summarize resulting distributions at any node. We show experimental results on the Wikipedia graph.
A complementary problem on graphs is to limit what can be learned,
ie., privacy. We study bipartite graphs given by social interactions.
We present a new anonymization technique based on partitioning nodes
of a graph into classes and provide privacy guarantees without
altering the graph structure. Further, we present experimental results
on anonymizing data from a popular social network, and demonstrate the
high utility achieved on several queries while guaranteeing privacy.
