Scalable Learning with Privacy over Graphs

Graphs have well-documented merits for modeling complex systems, including financial, biological, and social networks. Network nodes can also include attributes such as age or gender of users in a social network. However, the size of real-world networks can be massive, and nodal attributes can be unavailable. Moreover, new nodes may emerge over time, and their attributes must be inferred in real time. In this context, the present paper deals with scalable learning of nodal attributes by estimating a nodal function based on noisy observations at a subset of nodes. A multikernel-based approach is developed which is scalable to large-size networks. The novel method is capable of providing real-time evaluation of the function values on newly-joining nodes without resorting to a batch solver. In addition, the novel scheme only relies on an encrypted version of each node's connectivity, which promotes privacy. Experiments on real datasets corroborate the effectiveness of the proposed methods.