TY - JOUR
T1 - Infer user preferences from aggregate measurements
T2 - A novel message passing algorithm for privacy attack
AU - Su, Du
AU - Lu, Yi
N1 - Funding Information:
Yi Lu is an associate professor in the ECE Department at UIUC. She received B.S., M.S. and Ph.D. in EE from Stanford University. She is a recipient of the Terman Engineering Scholastic Award, Stanford Graduate Fellowship, the Sigmetrics Best paper award in 2008, the Performance Best paper award in 2011, the NSF Career award in 2012, the Center of Advanced Study fellowship in 2014, the ACM SIGMETRICS Rising Star Award in 2016, and the ACM SIGMETRICS Test-of-time Paper Award in 2018. Her work focuses on developing scalable architectures and algorithms for large networking systems such as modern web services with dynamic content, cloud computing and social networks. Her work spans fundamental analysis and algorithm implementation, and emphasizes design of low-complexity easy-to-implement algorithms.
Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2021/1
Y1 - 2021/1
N2 - Social media platforms, such as Facebook and TikTok, have triggered debates on privacy. The recent transformation of social media into an increasingly centralized service, exemplified by TikTok, only exacerbates the matter. While aggregation has been deemed an effective way to combat privacy infringement, a high degree of centralization can make aggregation ineffective. We present a randomized article-push algorithm and a message-passing reconstruction algorithm that enable social media platforms to infer user preferences from only the publicly available aggregate data of article-reads, without storing any individual users’ actions. Its O(n) complexity allows the reconstruction algorithm to scale to a large population, as is typical of social media platforms. Moreover, the feasibility of the privacy attack depends on the algorithm using as few articles as possible. We determine the minimum number of articles needed for high probability inference. Given the proportion of users, 0<ϵ<1, who prefer a given topic, we design a push algorithm and a reconstruction algorithm that achieve an article-to-user ratio β=ϵ(1−ϵ), at which phase transition occurs. The analysis of the algorithm departs from the classic density evolution due to the lack of monotonicity in the per-iteration error probability, which makes it surprising that phase transition takes place. By formulating the inference problem as a compressed sensing problem, we show that our phase transition threshold ϵ(1−ϵ) is extremely close to that of compressed sensing, even when the latter algorithm is of a worst-case O(n3) complexity and uses a dense Gaussian measurement matrix.
AB - Social media platforms, such as Facebook and TikTok, have triggered debates on privacy. The recent transformation of social media into an increasingly centralized service, exemplified by TikTok, only exacerbates the matter. While aggregation has been deemed an effective way to combat privacy infringement, a high degree of centralization can make aggregation ineffective. We present a randomized article-push algorithm and a message-passing reconstruction algorithm that enable social media platforms to infer user preferences from only the publicly available aggregate data of article-reads, without storing any individual users’ actions. Its O(n) complexity allows the reconstruction algorithm to scale to a large population, as is typical of social media platforms. Moreover, the feasibility of the privacy attack depends on the algorithm using as few articles as possible. We determine the minimum number of articles needed for high probability inference. Given the proportion of users, 0<ϵ<1, who prefer a given topic, we design a push algorithm and a reconstruction algorithm that achieve an article-to-user ratio β=ϵ(1−ϵ), at which phase transition occurs. The analysis of the algorithm departs from the classic density evolution due to the lack of monotonicity in the per-iteration error probability, which makes it surprising that phase transition takes place. By formulating the inference problem as a compressed sensing problem, we show that our phase transition threshold ϵ(1−ϵ) is extremely close to that of compressed sensing, even when the latter algorithm is of a worst-case O(n3) complexity and uses a dense Gaussian measurement matrix.
KW - Density evolution
KW - Graphical model
KW - Probabilistic inference
UR - http://www.scopus.com/inward/record.url?scp=85092242849&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85092242849&partnerID=8YFLogxK
U2 - 10.1016/j.peva.2020.102148
DO - 10.1016/j.peva.2020.102148
M3 - Article
AN - SCOPUS:85092242849
SN - 0166-5316
VL - 145
JO - Performance Evaluation
JF - Performance Evaluation
M1 - 102148
ER -