本发明提供一种隐私保护的数据交互关系图结构计算方法和系统，包括用户基于自身的邻接表添加噪声后得到自身的噪声度，并进行发送；用户基于接收的最大度对自身的邻接表进行图投影更新；用户基于更新后的邻接表，采用预设高斯机制的隐私预算和松弛项添加高斯噪声，得到自身的扰动计数，并进行发送；本发明找较优的最大度，完成图投影更新，同时让用户对数据进行本地拉普拉斯扰动和高斯扰动，并通过用户和数据收集方的节点交互信息，计算对图结构的相关查询，在满足本地差分隐私的前提下，对整个图的k‑star计数查询结果仍然达到较高的准确率。