  (p,q)-clique enumeration on a bipartite graph is critical for calculating
clustering coefficient and detecting densest subgraph. It is necessary to carry
out subgraph enumeration while protecting users' privacy from any potential
attacker as the count of subgraph may contain sensitive information. Most
recent studies focus on the privacy protection algorithms based on edge LDP
(Local Differential Privacy). However, these algorithms suffer a large
estimation error due to the great amount of required noise. In this paper, we
propose a novel idea of k-stars LDP and a novel k-stars LDP algorithm for (p,
q)-clique enumeration with a small estimation error, where a k-stars is a
star-shaped graph with k nodes connecting to one node. The effectiveness of
edge LDP relies on its capacity to obfuscate the existence of an edge between
the user and his one-hop neighbors. This is based on the premise that a user
should be aware of the existence of his one-hop neighbors. Similarly, we can
apply this premise to k-stars as well, where an edge is a specific genre of
1-stars. Based on this fact, we first propose the k-stars neighboring list to
enable our algorithm to obfuscate the existence of k-stars with Warner' s RR.
Then, we propose the absolute value correction technique and the k-stars
sampling technique to further reduce the estimation error. Finally, with the
two-round user-collector interaction mechanism, we propose our k-stars LDP
algorithm to count the number of (p, q)-clique while successfully protecting
users' privacy. Both the theoretical analysis and experiments have showed the
superiority of our algorithm over the algorithms based on edge LDP.
