Blog
The latest from Google Research
KDD 2015 Best Research Paper Award: “Algorithms for Public-Private Social Networks”
Monday, August 17, 2015
Posted by Posted by Corinna Cortes, Head, Google Research NY
The
21st ACM conference on Knowledge Discovery and Data Mining
(KDD’15), a main venue for academic and industry research in data management, information retrieval, data mining and machine learning, was held last week in Sydney, Australia. In the past several years, Google has been actively participating in KDD, with several Googlers presenting work at the conference in the research and industrial tracks. This year Googlers presented 12 papers at KDD (listed below, with Googlers in
blue
), all of which are
freely available
at the
ACM Digital Library
.
One of these papers,
Efficient Algorithms for Public-Private Social Networks
, co-authored by Googlers
Ravi Kumar
,
Silvio Lattanzi
,
Vahab Mirrokni
, former Googler intern
Alessandro Epasto
and research visitor
Flavio Chierichetti
, was awarded
Best Research Paper
. The inspiration for this paper comes from studying social networks and the importance of addressing privacy issues in analyzing such networks.
Privacy issues dictate the way information is shared among the members of the social network. In the simplest case, a user can mark some of her friends as private; this would make the connections (
edges
) between this user and these friends visible only to the user. In a different instantiation of privacy, a user can be a member of a private group; in this case, all the edges among the group members are to be considered private. Thus, each user in the social network has her own view of the link structure of the network. These privacy issues also influence the way in which the network itself can be viewed and processed by algorithms. For example, one cannot use the list of private friends of user X for suggesting potential friends or public news items to another user on the network, but one can use this list for the purpose of suggesting friends for user X.
As a result, enforcing these privacy guarantees translates to solving a different algorithmic problem for each user in the network, and for this reason, developing algorithms that process these social graphs and respect these privacy guarantees can become computationally expensive.
In a recent study
, Dey et al. crawled a snapshot of 1.4 million New York City Facebook users and reported that 52.6% of them hid their friends list. As more users make a larger portion of their social neighborhoods private, these computational issues become more important.
Motivated by the above, this paper introduces the
public-private
model of
graphs
, where each user (node) in the public graph has an associated private graph. In this model, the public graph is visible to everyone, and the private graph at each node is visible only to each specific user. Thus, any given user sees their graph as a union of their private graph and the public graph.
From algorithmic point of view, the paper explores two powerful computational paradigms for efficiently studying large graphs, namely,
sketching
and
sampling
, and focuses on some key problems in social networks such as similarity ranking, and clustering. In the
sketching
model, the paper shows how to efficiently approximate the neighborhood function, which in turn can be used to approximate various notions of centrality scores for each node - such centrality scores like the
PageRank
score have important applications in ranking and recommender systems. In the
sampling
model, the paper focuses on all-pair shortest path distances, node similarities, and correlation clustering, and develop algorithms that computes these notions on a given public-private graph and at the same time. The paper also illustrates the effectiveness of this model and the computational efficiency of the algorithms by performing experiments on real-world social networks.
The public-private model is an abstraction that can be used to develop efficient social network algorithms. This work leaves a number of open interesting research directions such as: obtaining efficient algorithms for the densest subgraph/community detection problems, influence maximization, computing other pairwise similarity scores, and most importantly, recommendation systems.
KDD’15 Papers, co-authored by
Googlers
:
Efficient Algorithms for Public-Private Social Networks
(Best Paper Award)
Flavio Chierichetti, Alessandro Epasto,
Ravi Kumar
,
Silvio Lattanzi
,
Vahab Mirrokni
Large-Scale Distributed Bayesian Matrix Factorization using Stochastic Gradient MCMC
Sungjin Ahn,
Anoop Korattikara
, Nathan Liu, Suju Rajan, Max Welling
TimeMachine: Timeline Generation for Knowledge-Base Entities
Tim Althoff,
Xin Luna Dong
,
Kevin Murphy
,
Safa Alai
,
Van Dang
,
Wei Zhang
Algorithmic Cartography: Placing Points of Interest and Ads on Maps
Mohammad Mahdian
, Okke Schrijvers,
Sergei Vassilvitskii
Stream Sampling for Frequency Cap Statistics
Edith Cohen
Dirichlet-Hawkes Processes with Applications to Clustering Continuous-Time Document Streams
Nan Du, Mehrdad Farajtabar,
Amr Ahmed
, Alexander J.Smola, Le Song
Adaptation Algorithm and Theory Based on Generalized Discrepancy
Corinna Cortes
,
Mehryar Mohri
, Andrés Muñoz Medina (now at Google)
Estimating Local Intrinsic Dimensionality
Laurent Amsaleg, Oussama Chelly, Teddy Furon, Stéphane Girard, Michael E. Houle Ken-ichi Kawarabayashi,
Michael Nett
Unified and Contrasting Cuts in Multiple Graphs: Application to Medical Imaging Segmentation
Chia-Tung Kuo,
Xiang Wang
, Peter Walker, Owen Carmichael, Jieping Ye, Ian Davidson
Going In-depth: Finding Longform on the Web
Virginia Smith,
Miriam Connor
,
Isabelle Stanton
Annotating needles in the haystack without looking: Product information extraction from emails
Weinan Zhang,
Amr Ahmed
,
Jie Yang
, Vanja Josifovski, Alexander Smola
Focusing on the Long-term: It's Good for Users and Business
Diane Tang
,
Henning Hohnhold
,
Deirdre O'Brien
Labels
accessibility
ACL
ACM
Acoustic Modeling
Adaptive Data Analysis
ads
adsense
adwords
Africa
AI
AI for Social Good
Algorithms
Android
Android Wear
API
App Engine
App Inventor
April Fools
Art
Audio
Augmented Reality
Australia
Automatic Speech Recognition
AutoML
Awards
BigQuery
Cantonese
Chemistry
China
Chrome
Cloud Computing
Collaboration
Compression
Computational Imaging
Computational Photography
Computer Science
Computer Vision
conference
conferences
Conservation
correlate
Course Builder
crowd-sourcing
CVPR
Data Center
Data Discovery
data science
datasets
Deep Learning
DeepDream
DeepMind
distributed systems
Diversity
Earth Engine
economics
Education
Electronic Commerce and Algorithms
electronics
EMEA
EMNLP
Encryption
entities
Entity Salience
Environment
Europe
Exacycle
Expander
Faculty Institute
Faculty Summit
Flu Trends
Fusion Tables
gamification
Gboard
Gmail
Google Accelerated Science
Google Books
Google Brain
Google Cloud Platform
Google Docs
Google Drive
Google Genomics
Google Maps
Google Photos
Google Play Apps
Google Science Fair
Google Sheets
Google Translate
Google Trips
Google Voice Search
Google+
Government
grants
Graph
Graph Mining
Hardware
HCI
Health
High Dynamic Range Imaging
ICCV
ICLR
ICML
ICSE
Image Annotation
Image Classification
Image Processing
Inbox
India
Information Retrieval
internationalization
Internet of Things
Interspeech
IPython
Journalism
jsm
jsm2011
K-12
Kaggle
KDD
Keyboard Input
Klingon
Korean
Labs
Linear Optimization
localization
Low-Light Photography
Machine Hearing
Machine Intelligence
Machine Learning
Machine Perception
Machine Translation
Magenta
MapReduce
market algorithms
Market Research
materials science
Mixed Reality
ML
ML Fairness
MOOC
Moore's Law
Multimodal Learning
NAACL
Natural Language Processing
Natural Language Understanding
Network Management
Networks
Neural Networks
NeurIPS
Nexus
Ngram
NIPS
NLP
On-device Learning
open source
operating systems
Optical Character Recognition
optimization
osdi
osdi10
patents
Peer Review
ph.d. fellowship
PhD Fellowship
PhotoScan
Physics
PiLab
Pixel
Policy
Professional Development
Proposals
Public Data Explorer
publication
Publications
Quantum AI
Quantum Computing
Recommender Systems
Reinforcement Learning
renewable energy
Research
Research Awards
resource optimization
Responsible AI
Robotics
schema.org
Search
search ads
Security and Privacy
Self-Supervised Learning
Semantic Models
Semi-supervised Learning
SIGCOMM
SIGMOD
Site Reliability Engineering
Social Networks
Software
Sound Search
Speech
Speech Recognition
statistics
Structured Data
Style Transfer
Supervised Learning
Systems
TensorBoard
TensorFlow
TPU
Translate
trends
TTS
TV
UI
University Relations
UNIX
Unsupervised Learning
User Experience
video
Video Analysis
Virtual Reality
Vision Research
Visiting Faculty
Visualization
VLDB
Voice Search
Wiki
wikipedia
WWW
Year in Review
YouTube
Archive
2022
May
Apr
Mar
Feb
Jan
2021
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2020
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2019
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2018
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2017
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2016
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2015
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2014
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2013
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2012
Dec
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2011
Dec
Nov
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2010
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2009
Dec
Nov
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2008
Dec
Nov
Oct
Sep
Jul
May
Apr
Mar
Feb
2007
Oct
Sep
Aug
Jul
Jun
Feb
2006
Dec
Nov
Sep
Aug
Jul
Jun
Apr
Mar
Feb
Feed
Follow @googleai
Give us feedback in our
Product Forums
.
