Beyond Group Statistics: Local Relationship Priors for Private Graph Learning

Private graph learning infers a propagation structure from noisy relational reports. Group statistics constrain how much connectivity is assigned to groups, but agreement with these statistics need not determine which local relations help a downstream task. We study this distinction through the Group–Local Prior (GLP). Given a fixed private report, GLP separates report-derived connection mass from a public-feature neighborhood preference, constructs a feasible mass-matched target, and pools the two priors before conditioning on randomized edge responses. An observation argument motivates the local preference, while normalized-propagation analysis explains why reconstruction fidelity need not predict the task effect. Experiments on six graphs, up to 89,250 nodes, evaluate this design under matched joint privacy budgets. GLP achieves the highest mean accuracy among evaluated private-report methods in 27 of 28 conditions on the original four-graph grid. On full Physics, it leads the evaluated private methods in both accuracy and Macro-F1 at both budgets and under both backbones; on Flickr, it improves three of four backbone–metric means over matched HPGR. Relationship controls and frozen-parameter confirmation connect these gains to local correspondence and task-relevant propagation. Together, these results support relationship placement as a task-oriented design principle for private graph learning.