TY - GEN
T1 - Triangle Counting Under Edge Relationship Local Differential Privacy
T2 - 30th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2026
AU - Xia, Wenzheng
AU - Xu, Shuangqing
AU - Zheng, Yifeng
AU - Xu, Lei
AU - Hua, Zhongyun
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.
PY - 2026
Y1 - 2026
N2 - Triangle counting is a fundamental primitive in graph analysis. However, in decentralized graph settings, directly aggregating users’ local views would leak sensitive social connections. Ensuring edge privacy is challenging because users’ local views are often correlated. Existing methods typically focus on the Extended Local View (ELV) model, which assumes that users fully disclose their neighbor lists to all their neighbors. However, in realistic social network applications where users may selectively disclose their connections, this full-visibility assumption breaks, rendering ELV-based approaches inadequate. In this paper, we explicitly capture such selective disclosure behavior and formalize it as the Restricted ELV (RELV) model. With this as a foundation, we propose SEPALS, a new framework for accurate triangle counting under RELV. In SEPALS, we develop a targeted neighbor-list collection strategy to recover unobservable structural information and propose a redundancy-aware weighting mechanism to unbiasedly aggregate contributions from incomplete local views. We formally prove that SEPALS satisfies the advanced notion of edge relationship local differential privacy. SEPALS significantly outperforms baselines that directly adapt existing ELV-based approaches for the RELV model in accuracy.
AB - Triangle counting is a fundamental primitive in graph analysis. However, in decentralized graph settings, directly aggregating users’ local views would leak sensitive social connections. Ensuring edge privacy is challenging because users’ local views are often correlated. Existing methods typically focus on the Extended Local View (ELV) model, which assumes that users fully disclose their neighbor lists to all their neighbors. However, in realistic social network applications where users may selectively disclose their connections, this full-visibility assumption breaks, rendering ELV-based approaches inadequate. In this paper, we explicitly capture such selective disclosure behavior and formalize it as the Restricted ELV (RELV) model. With this as a foundation, we propose SEPALS, a new framework for accurate triangle counting under RELV. In SEPALS, we develop a targeted neighbor-list collection strategy to recover unobservable structural information and propose a redundancy-aware weighting mechanism to unbiasedly aggregate contributions from incomplete local views. We formally prove that SEPALS satisfies the advanced notion of edge relationship local differential privacy. SEPALS significantly outperforms baselines that directly adapt existing ELV-based approaches for the RELV model in accuracy.
KW - Decentralized graph analysis
KW - Edge relationship local differential privacy
KW - Triangle counting
UR - https://www.scopus.com/pages/publications/105041781356
U2 - 10.1007/978-981-92-1300-9_38
DO - 10.1007/978-981-92-1300-9_38
M3 - 会议稿件
AN - SCOPUS:105041781356
SN - 9789819212996
T3 - Lecture Notes in Computer Science
SP - 480
EP - 492
BT - Advances in Knowledge Discovery and Data Mining - 30th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2026, Proceedings
A2 - Wong, Raymond Chi-Wing
A2 - Tong, Hanghang
A2 - Lu, Hua
A2 - Kwok, James
A2 - Salim, Flora
A2 - Song, Yuanfeng
A2 - Yiu, Man Lung
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 9 June 2026 through 12 June 2026
ER -