Colloquia - S V N Vishwanathan/Purdue University, "Efficiently Sampling Multiplicative Attribute Graphs Using a Ball-Dropping Process," ACES 6.304

Contact Name: 
Jenna Whitney
Apr 20, 2012 11:00am - 12:00pm

There is a sign-up schedule for this event that can be found at

Type o

f Talk: Colloquia

Speaker/Affiliation: S V N Vishwanathan/Purdue Unive


Talk Audience: UTCS Faculty, Graduate Students, Undergraduate

Students, and Outside Interested Parties

Date/Time: Friday, April 20

, 2012, 11:00 am

Location: ACES 6.304

Host: Inderjit Dhillon

Talk Title: Sampling Multiplicative Attribute Graphs Using a Ball-Droppi

ng Process

Talk Abstract:
In this talk I will describe the first sub

-quadratic sampling algorithm for the Multiplicative Attribute Graph Model

(MAGM, Kim and Leskove 2010). To design our algorithm, we first define a

stochastic emph{ball-dropping process} (BDP). Although a special case of t

his process was introduced as an efficient approximate sampling algorithm f

or the Kronecker Product Graph Model (KPGM, Leskovec et al 2010), neither
emph{why} such an approximation works nor emph{what} is the actual distr

ibution this process is sampling from has been addressed so far to the best
of our knowledge. Our rigorous treatment of the BDP enables us to clarify

the rational behind a BDP approximation of KPGM, and design an efficient s

ampling algorithm for the MAGM. Joint work with Hyokun Yun.

Speaker Bi

Dr. Vishwanathan is an associate professor at Purdue University with j

oint appointments in the departments of Statistics and Computer Science. Pr

ior to coming to Purdue in fall 2008 he was a principal researcher in the S

tatistical Machine Learning program of NICTA with an adjunct appointment at
the College of Engineering and Computer Science, Australian National Univ


His recent research has focused on machine learning with empha

sis on on graphical models, structured prediction, kernel methods, and c

onvex optimization. He works on problems in pattern recognition, OCR, bio

-informatics, text analysis, and optimization.