본 논문은 에지 로컬 차등 프라이버시(edge local differential privacy) 하에서 서브그래프 개수를 세는 과정에서 해시 함수를 사용하여 통신 비용을 줄이는 방법을 제안합니다. 기존의 에지 로컬 차등 프라이버시 기반 그래프 통계량 계산 알고리즘들은 높은 통신 비용으로 인해 대규모 그래프에 적용하기 어려운데, 본 논문에서는 선형 합동 해싱(linear congruence hashing)을 도입하여 이 문제를 해결합니다. 샘플링 비율 $s$를 사용하여 통신 비용을 $s^2$만큼 줄일 수 있지만, 발표된 그래프 통계량의 분산은 $s$만큼 증가합니다. 실험 결과, 통신 비용이 동일한 경우 삼각형 개수에 대한 $\ell_2$-error가 기존 최고 성능 알고리즘에 비해 최대 1000배까지 감소함을 보였습니다.
