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/school-mates etc can be uncovered by an unsupervised process by examining only the users' ego-network 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 `pseudo-boolean' 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 1-2 sentences

Given that the technical difficulty described above is resolved I recommend to accept this paper.

Masked Reviewer ID:	Assigned_Reviewer_4
Review:

Question

Summary
Social networks analysis. The paper studies the problem of automatically discovering users’ social circles from so-called 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 1-2 sentences

Nice well-written paper on an important issue in network science. Well-motivated method. Inference and evaluation could have been improved, as well as results and conclusion appear weak.

Masked Reviewer ID:	Assigned_Reviewer_9
Review:

Question

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 pre-study 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 write-up is very understandable and pleasant to follow.

Weak Points:

- The paper puts a lot of emphasis on how tree-structured 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 1-2 sentences

Relevant problem, simple but intuitive model. I dislike the emphasis on the feature generation that seems crude and ad hoc.