Example systems and methods enhance user privacy by performing efficient on-device public-private computation on a combination of public and private data, such as, for example, public and private graph data. In particular, the on-device public-private computation framework described herein can enable a device associated with an entity to efficiently compute a combined output that takes into account and is explicitly based upon a combination of data that is associated with the entity and data that is associated with one or more other entities that are private connections of the entity, all without revealing to a centralized computing system a set of locally stored private data that identifies the one or more other entities that are private connections of the entity.