
Reviews For Paper
Paper ID 
272 
Title 
Learning to Discover Social Circles in Ego Networks 
Masked Reviewer ID:

Assigned_Reviewer_10

Review:


Question  
Comments to author(s). First provide a
summary of the paper, and then address the following criteria: Quality,
clarity, originality and significance. (For detailed reviewing
guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions) 
The authors investigate a creation of groups or circles in social networks.
They suggest that groups of friends/family/colleagues/schoolmates
etc can be uncovered by an unsupervised process by examining only the
users' egonetwork which is the social network reduced on a single
user's set of connections.
Such groups, they claim, are identifiable by both the the local network structure and the users' profile features.
The main point of the paper, as I see it, is that these two types of information must be utilized simultaneously.
The authors propose a statistical model for which they try to fit to the ego network.
Model parameters and clustering are simultaneously optimized to maximize the log likelihood of the evidence (the network).
Let L(Theta,C) be the log likelihood of the evidence given model parameters Theta and clustering C.
An expectation maximization algorithm is proposed which maximizes L over Theta and C alternately.
Maximizing over Theta given C amounts to solving a convex optimization problem.
Alas, finding C given Theta is hard. The authors resort to using general purpose `pseudoboolean' solvers for this task.
This step is quite problematic from the model prospective. The
authors allow clusters to overlap and be of arbitrary size and number.
It is unclear why the trivial solution assigning each edge (above
probability 1/2) a cluster of size 2 which includes its two end points
is not good.
That will give an optimal solution for C which is uninformative. I
could not understand from the manuscript what prevents this trivial
solution. The authors should explain this.
Experimentally, the authors give very compelling evidence to suport their claims.
Their experimentation and data are thorough and produce, what seems to be, quite impressive results.
Since I am not an expert on this topic, I cannot vouch for the completeness of the references.

Please summarize your review in 12 sentences 
Given that the technical difficulty described above is resolved I recommend to accept this paper.

Masked Reviewer ID:

Assigned_Reviewer_4

Review:


Question  
Comments to author(s). First provide a
summary of the paper, and then address the following criteria: Quality,
clarity, originality and significance. (For detailed reviewing
guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions) 
Summary
Social networks analysis. The paper studies the problem of
automatically discovering usersâ€™ social circles from socalled Ego
networks (i.e. the network formed by extraction a node and its
neighbors). Proposes a simple probabilistic model with latent multiple
assignments to "circles". Results are good, method works best in
Facebook data.
COMMENTS:
Significance:
This type of social network analysis may have obvious business
applications (can help to form social circles) but could also be of
importance for better understanding of mechanisms in network science.
Quality:
Simple well motivated model. Use powerful option tools. Could have
been more careful on the complexity issues, and discussion of uniqueness
of the solution. Uses BIC and simple cross validation for model choice
and parameters  could have been much better argued why these choice are
made (including the range of lambdas, is it not data dependent??).
Clarity:
Very clear state of the art, methods and experiments. Machine
learning tools could have been better argued. Conclusions are weak.
Originality:
Moderate, many similar methods. Similar work on "dyadic prediction"
with soft latent variables exist in the literature (Menon&Elkan,
http://arxiv.org/abs/1006.2156)

Please summarize your review in 12 sentences 
Nice wellwritten paper on an important
issue in network science. Wellmotivated method. Inference and
evaluation could have been improved, as well as results and conclusion
appear weak.

Masked Reviewer ID:

Assigned_Reviewer_9

Review:


Question  
Comments to author(s). First provide a
summary of the paper, and then address the following criteria: Quality,
clarity, originality and significance. (For detailed reviewing
guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions) 
Summary:
The authors suggest an
algorithm for automatically detecting social circles within ego networks
of online friends, thereby alleviating the users from manually creating
and updating lists of friends. They suggest to learn weighted
similarity metric for each circle with a simple discriminative model. As
features they convert 2 profile trees (or 2 sets of hash tags) into a
binary feature vector. The paper emphasizes four ways to convert the
profile information into features: between friend and ego / between two
mutual friends combined with or without a compression schema. The
compression schema aggregates that two categories are shared, but
ignores the values, e.g. ignoring the information which affiliation was
shared in the feature vector. For twitter data the compression scheme
just counts the number of hash tags in common. The model accounts for
hard assignments to overlapping and fully including circles. The
inference algorithm is cast as a pseudo boolean optimization problem
(making use of a software package). The model was evaluated on three
data sets against a fair amount of baselines with respect to BER
(Balanced Error Rate) and F1.
Strong Points:
 The authors work on a very interesting problem that is very relevant in practice.

The model is simple but intuitive. I like the prestudy on labeled data
from Facebook confirming that a decent fraction of the circles are
fully included in another.
 The evaluation is very thorough. Demonstrating the maturity of the work.
 the writeup is very understandable and pleasant to follow.
Weak Points:

The paper puts a lot of emphasis on how treestructured profiles are
turned into binary feature vectors. This discussion is not very
elaborate, the feature construction seems arbitrary. (see more below)

Omitting circles that could not be aligned in the evaluation seems not
right to me. I also got the impression that multiple predicted cycles
can be mapped to one ground truth circle. Choosing B^3 ("B cubed") would
alleviated the problem.
Value:
I deem the paper valuable due to its practical applicability.
Detailed Comments:

extraction of Binary features from trees has been well studied, e.g.
Haussler "Convolution kernels on discrete structures", 1999 or
Vishwanathan and Smola "Fast kernels for string and tree matching",
2004.
 Twitter experiment: I can't follow why the sheer number
of hash tags in common should contain any useful information. Could the
authors comment on that?
 Do you still find fully included circles in the twitter data set with the compressed features?

Given that all four variants perform similarly on twitter, I am
curious: How would the model perform with only the "edge exists" (i.e.
feature index 0 in Figure 5) would perform? Is the profile info helping
for the twitter at all  or is the nature of hard assignments earning
the performance of 0.7 (1  BER)?
 Equation 1: p(x,y) = exp{ sum_{x,y} ...)  Are those different x and y on both sides of the equation?
 I assume you Equation 3 is for l_{\Theta^K} as references in Equation 9. Right?

Why can't you include all four kinds of features into one feature
vector and let the weights decide which ones are most informative?

Please summarize your review in 12 sentences 
Relevant problem, simple but intuitive
model. I dislike the emphasis on the feature generation that seems crude
and ad hoc.

 