Triangle Counting Under Edge Relationship Local Differential Privacy: The Case of Restricted Extended Local Views

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.