Timezone: »

 
Poster
Private Graphon Estimation for Sparse Graphs
Christian Borgs · Jennifer Chayes · Adam Smith

Tue Dec 08 04:00 PM -- 08:59 PM (PST) @ 210 C #91 #None
in Poster Session »
We design algorithms for fitting a high-dimensional statistical model to a large, sparse network without revealing sensitive information of individual members. Given a sparse input graph $G$, our algorithms output a node-differentially private nonparametric block model approximation. By node-differentially private, we mean that our output hides the insertion or removal of a vertex and all its adjacent edges. If $G$ is an instance of the network obtained from a generative nonparametric model defined in terms of a graphon $W$, our model guarantees consistency: as the number of vertices tends to infinity, the output of our algorithm converges to $W$ in an appropriate version of the $L_2$ norm. In particular, this means we can estimate the sizes of all multi-way cuts in $G$. Our results hold as long as $W$ is bounded, the average degree of $G$ grows at least like the log of the number of vertices, and the number of blocks goes to infinity at an appropriate rate. We give explicit error bounds in terms of the parameters of the model; in several settings, our bounds improve on or match known nonprivate results.
[ PDF] 

Author Information

Christian Borgs (Microsoft Research)
Jennifer Chayes (Microsoft Research)

Jennifer Chayes is Technical Fellow and Managing Director of Microsoft Research New England, New York City, and Montreal. She was for many years Professor of Mathematics at UCLA. She is author of over 140 academic papers and inventor of over 30 patents. Her research areas include phase transitions in computer science, structural and dynamical properties of networks, graph theory, graph algorithms, and computational biology. She is one of the inventors of the field of graphons, which are now widely used in the machine learning of massive networks. Chayes’ recent work focuses on machine learning, broadly defined. Chayes holds a BA in physics and biology from Wesleyan, where she graduated first in her class, and a PhD in physics from Princeton. She was a postdoctoral fellow at Harvard and Cornell. She is the recipient of the NSF Postdoc Fellowship, the Sloan Fellowship, the UCLA Distinguished Teaching Award, and the Anita Borg Institute Women of Leadership Vision Award. She has twice been a member of the Institute for Advanced Study in Princeton. Chayes is Fellow of the American Association for the Advancement of Science, the Fields Institute, the Association for Computing Machinery, and the American Mathematical Society, and the American Academy of Arts and Sciences. She is the winner of the 2015 John von Neumann Lecture Award, the highest honor of the Society of Industrial and Applied Mathematics. In 2016, she received an Honorary Doctorate from Leiden University. Chayes serves on numerous scientific boards and committees. She is a past VP of the American Mathematical Society, past Chair of Mathematics for the Association for the Advancement of Science, and past Chair of the Turing Award Selection Committee. She is also committed to diversity in the science and technology, and serves on many boards to increase representation of women and minorities in STEM.

Adam Smith (Pennsylvania State University)

More from the Same Authors