nips nips2012 nips2012-194 knowledge-graph by maker-knowledge-mining

194 nips-2012-Learning to Discover Social Circles in Ego Networks

Source: pdf

Author: Jure Leskovec, Julian J. Mcauley

Abstract: Our personal social networks are big and cluttered, and currently there is no good way to organize them. Social networking sites allow users to manually categorize their friends into social circles (e.g. ‘circles’ on Google+, and ‘lists’ on Facebook and Twitter), however they are laborious to construct and must be updated whenever a user’s network grows. We deﬁne a novel machine learning task of identifying users’ social circles. We pose the problem as a node clustering problem on a user’s ego-network, a network of connections between her friends. We develop a model for detecting circles that combines network structure as well as user proﬁle information. For each circle we learn its members and the circle-speciﬁc user proﬁle similarity metric. Modeling node membership to multiple circles allows us to detect overlapping as well as hierarchically nested circles. Experiments show that our model accurately identiﬁes circles on a diverse set of data from Facebook, Google+, and Twitter for all of which we obtain hand-labeled ground-truth. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Our personal social networks are big and cluttered, and currently there is no good way to organize them. [sent-5, score-0.274]

2 Social networking sites allow users to manually categorize their friends into social circles (e. [sent-6, score-1.115]

3 We develop a model for detecting circles that combines network structure as well as user proﬁle information. [sent-11, score-0.694]

4 For each circle we learn its members and the circle-speciﬁc user proﬁle similarity metric. [sent-12, score-0.564]

5 Modeling node membership to multiple circles allows us to detect overlapping as well as hierarchically nested circles. [sent-13, score-0.635]

6 Experiments show that our model accurately identiﬁes circles on a diverse set of data from Facebook, Google+, and Twitter for all of which we obtain hand-labeled ground-truth. [sent-14, score-0.488]

7 1 Introduction Online social networks allow users to follow streams of posts generated by hundreds of their friends and acquaintances. [sent-15, score-0.54]

8 Users’ friends generate overwhelming volumes of information and to cope with the ‘information overload’ they need to organize their personal social networks. [sent-16, score-0.398]

9 One of the main mechanisms for users of social networking sites to organize their networks and the content generated by them is to categorize their friends into what we refer to as social circles. [sent-17, score-0.831]

10 Practically all major social networks provide such functionality, for example, ‘circles’ on Google+, and ‘lists’ on Facebook and Twitter. [sent-18, score-0.2]

11 to hide personal information from coworkers), and for sharing groups of users that others may wish to follow. [sent-23, score-0.225]

12 Currently, users in Facebook, Google+ and Twitter identify their circles either manually, or in a na¨ve fashion by identifying friends sharing a common attribute. [sent-24, score-0.88]

13 Neither approach is particularly ı satisfactory: the former is time consuming and does not update automatically as a user adds more friends, while the latter fails to capture individual aspects of users’ communities, and may function poorly when proﬁle information is missing or withheld. [sent-25, score-0.177]

14 In particular, given a single user with her personal social network, our goal is to identify her circles, each of which is a subset of her friends. [sent-27, score-0.382]

15 Circles are user-speciﬁc as each user organizes her personal network of friends independently of all other users to whom she is not connected. [sent-28, score-0.589]

16 This means that we can formulate the problem of circle detection as a clustering problem on her ego-network, the network of friendships between her friends. [sent-29, score-0.456]

17 In Figure 1 we are given a single user u and we form a network between her friends vi . [sent-30, score-0.364]

18 We refer to the user u as the ego and to the nodes vi as alters. [sent-31, score-0.312]

19 The task then is to identify the circles to which each alter vi belongs, as in Figure 1. [sent-32, score-0.515]

20 We expect that circles are formed by densely-connected sets of alters [20]. [sent-36, score-0.535]

21 This network shows typical behavior that we observe in our data: Approximately 25% of our ground-truth circles (from Facebook) are contained completely within another circle, 50% overlap with another circle, and 25% of the circles have no members in common with any other circle. [sent-38, score-1.115]

22 The goal is to discover these circles given only the network between the ego’s friends. [sent-39, score-0.548]

23 We aim to discover circle memberships and to ﬁnd common properties around which circles form. [sent-40, score-0.931]

24 , alters belong to multiple circles simultaneously [1, 21, 28, 29], and many circles are hierarchically nested in larger ones (Figure 1). [sent-43, score-1.046]

25 Secondly, we expect that each circle is not only densely connected but its members also share common properties or traits [18, 28]. [sent-45, score-0.396]

26 Thus we need to explicitly model different dimensions of user proﬁles along which each circle emerges. [sent-46, score-0.491]

27 We model circle afﬁliations as latent variables, and similarity between alters as a function of common proﬁle information. [sent-47, score-0.459]

28 This extends the notion of homophily [12] by allowing different circles to form along different social dimensions, an idea related to the concept of Blau spaces [16]. [sent-51, score-0.68]

29 We achieve this by allowing each circle to have a different deﬁnition of proﬁle similarity, so that one circle might form around friends from the same school, and another around friends from the same location. [sent-52, score-0.95]

30 We learn the model by simultaneously choosing node circle memberships and proﬁle similarity functions so as to best explain the observed data. [sent-53, score-0.51]

31 1 Experimental results show that by simultaneously considering social network structure as well as user proﬁle information our method performs signiﬁcantly better than natural alternatives and the current state-of-the-art. [sent-55, score-0.372]

32 Our method is completely unsupervised, and is able to automatically determine both the number of circles as well as the circles themselves. [sent-57, score-0.976]

33 Classical algorithms tend to identify communities based on node features [9] or graph structure [1, 21], but rarely use both in concert. [sent-60, score-0.201]

34 2 A Generative Model for Friendships in Social Circles We desire a model of circle formation with the following properties: (1) Nodes within circles should have common properties, or ‘aspects’. [sent-65, score-0.83]

35 (2) Different circles should be formed by different aspects, e. [sent-66, score-0.488]

36 one circle might be formed by family members, and another by students who attended the same university. [sent-68, score-0.346]

37 (3) Circles should be allowed to overlap, and ‘stronger’ circles should be allowed to form within ‘weaker’ ones, e. [sent-69, score-0.488]

38 a circle of friends from the same degree program may form within a circle 1 http://snap. [sent-71, score-0.792]

39 Ideally we would like to be able to pinpoint which aspects of a proﬁle caused a circle to form, so that the model is interpretable by the user. [sent-75, score-0.348]

40 The ‘center’ node u of the ego-network (the ‘ego’) is not included in G, but rather G consists only of u’s friends (the ‘alters’). [sent-77, score-0.203]

41 We deﬁne the ego-network in this way precisely because creators of circles do not themselves appear in their own circles. [sent-78, score-0.52]

42 For each ego-network, our goal is to predict a set of circles C = {C1 . [sent-79, score-0.488]

43 CK }, Ck ⊆ V , and associated parameter vectors θk that encode how each circle emerged. [sent-82, score-0.371]

44 We encode ‘user proﬁles’ into pairwise features φ(x, y) that in some way capture what properties the users x and y have in common. [sent-83, score-0.283]

45 We describe a model of social circles that treats circle memberships as latent variables. [sent-85, score-1.095]

46 Nodes within a common circle are given an opportunity to form an edge, which naturally leads to hierarchical and overlapping circles. [sent-86, score-0.385]

47 Our model of social circles is deﬁned as follows. [sent-88, score-0.654]

48 Given an ego-network G and a set of K circles C = {C1 . [sent-89, score-0.488]

49 (1) Ck {x,y} circles containing both nodes all other circles For each circle Ck , θk is the proﬁle similarity parameter that we will learn. [sent-93, score-1.393]

50 Since the feature vector φ(x, y) encodes the similarity between the proﬁles of two users x and y, the parameter vector θk encodes what dimensions of proﬁle similarity caused the circle to form, so that nodes within a circle Ck should ‘look similar’ according to θk . [sent-95, score-1.069]

51 Φ(e) − (3) e∈V ×V e∈E Next, we describe how to optimize node circle memberships C as well as the parameters of the user proﬁle similarity functions Θ = {(θk , αk )} (k = 1 . [sent-101, score-0.656]

52 3 Unsupervised Learning of Model Parameters ˆ ˆ ˆ Treating circles C as latent variables, we aim to ﬁnd Θ = {θ, α} so as to maximize the regularized log-likelihood of (eq. [sent-105, score-0.511]

53 7) is Ee (0, 0) = Ee (0, 1) = Ee (1, 0) Ee (1, 1) =  ok (e) − αk φ(e), θk − log(1 + eok (e)−αk − log(1 + eok (e)−αk φ(e),θk ), =  ok (e) + φ(e), θk − log(1 + eok (e)+ − log(1 + eok (e)+ φ(e),θk ), φ(e),θk φ(e),θk ), ), e∈E e∈E / e∈E . [sent-118, score-0.324]

54 This means that our method could be run on the full Facebook graph (for example), as circles are independently detected for each user, and the ego-networks typically contain only hundreds of nodes. [sent-136, score-0.514]

55 2 We were able to obtain ego-networks and ground-truth from three major social networking sites: Facebook, Google+, and Twitter. [sent-142, score-0.205]

56 From Facebook we obtained proﬁle and network data from 10 ego-networks, consisting of 193 circles and 4,039 users. [sent-143, score-0.548]

57 To do so we developed our own Facebook application and conducted a survey of ten users, who were asked to manually identify all the circles to which their friends belonged. [sent-144, score-0.7]

58 On average, users identiﬁed 19 circles in their ego-networks, with an average circle size of 22 friends. [sent-145, score-0.987]

59 Examples of such circles include students of common universities, sports teams, relatives, etc. [sent-146, score-0.542]

60 Examples of trees for two users x (blue) and y (pink) are shown at left. [sent-151, score-0.182]

61 (2) (bottom right) we sum over the leaf nodes in the ﬁrst scheme, maintaining the fact that the two users worked at the same institution, but discarding the identity of that institution. [sent-155, score-0.267]

62 From Google+ we obtained data from 133 ego-networks, consisting of 479 circles and 106,674 users. [sent-157, score-0.488]

63 The 133 ego-networks represent all 133 Google+ users who had shared at least two circles, and whose network information was publicly accessible at the time of our crawl. [sent-158, score-0.288]

64 The Google+ circles are quite different to those from Facebook, in the sense that their creators have chosen to release them publicly, and because Google+ is a directed network (note that our model can very naturally be applied to both to directed and undirected networks). [sent-159, score-0.58]

65 For example, one circle contains candidates from the 2012 republican primary, who presumably do not follow their followers, nor each other. [sent-160, score-0.317]

66 Finally, from Twitter we obtained data from 1,000 ego-networks, consisting of 4,869 circles (or ‘lists’ [10, 19, 27, 31]) and 81,362 users. [sent-161, score-0.488]

67 Our Facebook data is fully labeled, in the sense that we obtain every circle that a user considers to be a cohesive community, whereas our Google+ and Twitter data is only partially labeled, in the sense that we only have access to public circles. [sent-165, score-0.463]

68 For Twitter, many choices exist as proxies for user proﬁles; we simply collect data from two categories, namely the set of hashtags and mentions used by each user during two-weeks’ worth of tweets. [sent-170, score-0.34]

69 Suppose that users v ∈ V each have an associated proﬁle tree Tv , and that l ∈ Tv is a leaf in that tree. [sent-174, score-0.214]

70 We deﬁne the difference vector σx,y between two users x and y as a binary indicator encoding the proﬁle aspects where users x and y differ (Figure 2, top right): σx,y [l] = δ((l ∈ Tx ) = (l ∈ Ty )). [sent-175, score-0.395]

71 One way to address this is to form difference vectors based on the parents of leaf nodes: this way, we encode what proﬁle categories two users have in common, but disregard speciﬁc values (Figure 2, bottom right). [sent-178, score-0.315]

72 For example, we encode how many hashtags two users tweeted in common, but discard which hashtags they tweeted: σx,y [p] = l∈children(p) σx,y [l]. [sent-179, score-0.364]

73 The ﬁrst property we wish to model is that members of circles should have common relationships with each other: φ1 (x, y) = (1; −σx,y ). [sent-182, score-0.567]

74 (12) The second property we wish to model is that members of circles should have common relationships to the ego of the ego-network. [sent-183, score-0.68]

75 In this case, we consider the proﬁle tree Tu from the ego user u. [sent-184, score-0.259]

76 In both cases, we include a constant feature (‘1’), which controls the probability that edges form within circles, or equivalently it measures the extent to which circles are made up of friends. [sent-187, score-0.55]

77 Importantly, this allows us to predict memberships even for users who have no proﬁle information, simply due to their patterns of connectivity. [sent-188, score-0.283]

78 6 Experiments Although our method is unsupervised, we can evaluate it on ground-truth data by examining the maximum-likelihood assignments of the latent circles C = {C1 . [sent-194, score-0.511]

79 Our goal is that for a properly regularized model, the latent variables will align closely with the human ¯ ¯ ¯¯ labeled ground-truth circles C = {C1 . [sent-198, score-0.511]

80 To measure the alignment between a predicted circle C and a ground-truth ¯ ¯ circle C, we compute the Balanced Error Rate (BER) between the two circles [7], BER(C, C) = 1 2 ¯ |C\C| |C| ¯ + |C\C| . [sent-203, score-1.145]

81 Since we do not know the correspondence between ¯ circles in C and C, we compute the optimal match via linear assignment by maximizing: max ¯ f :C→C 1 |f | (1 − BER(C, f (C))), (15) C∈dom(f ) ¯ where f is a (partial) correspondence between C and C. [sent-209, score-0.488]

82 , forcing all circles to be aligned by allowing multiple predicted circles to match a single groundtruth circle or vice versa) lead to qualitatively similar results. [sent-214, score-1.341]

83 For each node, mixedmembership models predict a stochastic vector encoding partial circle memberships, which we threshold to generate ‘hard’ assignments. [sent-248, score-0.342]

84 We also considered Block-LDA [3], where we generate ‘documents’ by treating aspects of user proﬁles as words in a bag-of-words model. [sent-249, score-0.177]

85 We also considered the Low-Rank Embedding approach of [30], where node attributes and edge information are projected into a feature space where classical clustering techniques can be applied. [sent-252, score-0.175]

86 15), with the number of circles ˆ ˆ K determined as described in Section 3. [sent-258, score-0.488]

87 or Stanford 1 weight θ3,i people with PhDs weight θ3,i 1 weight θ2,i weight θ1,i Figure 4: Three detected circles on a small ego-network from Facebook, compared to three groundtruth circles (BER 0. [sent-273, score-1.147]

88 Our method correctly identiﬁes the largest circle (left), a sub-circle contained within it (center), and a third circle that signiﬁcantly overlaps with it (right). [sent-279, score-0.634]

89 For example the former features encode the fact that members of a particular community tend to speak German, while the latter features encode the fact that they speak the same language. [sent-283, score-0.364]

90 Using the ‘compressed’ features ψ 1 and ψ 2 does not signiﬁcantly impact performance, which is promising since they have far lower dimension than the full features; what this reveals is that it is sufﬁcient to model categories of attributes that users have in common (e. [sent-286, score-0.324]

91 There are a few explanations: Firstly, our Facebook data is complete, in the sense that survey participants manually labeled every circle in their ego-networks, whereas in other datasets we only observe publicly-visible circles, which may not be up-to-date. [sent-290, score-0.344]

92 A more basic difference lies in the nature of the networks themselves: edges in Facebook encode mutual ties, whereas edges in Google+ and Twitter encode follower relationships, which changes the role that circles serve [27]. [sent-292, score-0.694]

93 Our method is correctly able to identify overlapping circles as well as sub-circles (circles within circles). [sent-298, score-0.558]

94 Figure 5 shows parameter vectors learned for four circles for a particular Facebook user. [sent-299, score-0.488]

95 Positive weights indicate properties that users in a particular circle have in common. [sent-300, score-0.499]

96 Notice how the model naturally learns the social dimensions that lead to a social circle. [sent-301, score-0.36]

97 Connections between the lines: augmenting social networks with text. [sent-339, score-0.2]

98 Analysis of twitter lists as a potential source for discovering latent characteristics of users. [sent-362, score-0.314]

99 Representing degree distributions, clustering, and homophily in social networks with latent cluster random effects models. [sent-369, score-0.249]

100 You are who you know: Inferring user proﬁles in online social networks. [sent-407, score-0.312]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('circles', 0.488), ('pro', 0.326), ('circle', 0.317), ('facebook', 0.314), ('twitter', 0.247), ('users', 0.182), ('social', 0.166), ('friends', 0.158), ('google', 0.149), ('le', 0.148), ('user', 0.146), ('ck', 0.141), ('les', 0.113), ('ego', 0.113), ('name', 0.107), ('memberships', 0.101), ('communities', 0.082), ('cryptanalyst', 0.081), ('ber', 0.079), ('eok', 0.065), ('network', 0.06), ('encode', 0.054), ('members', 0.054), ('nodes', 0.053), ('clustering', 0.053), ('compressed', 0.05), ('balasubramanyan', 0.048), ('hashtags', 0.048), ('streich', 0.048), ('ee', 0.048), ('categories', 0.047), ('similarity', 0.047), ('alters', 0.047), ('education', 0.047), ('features', 0.047), ('node', 0.045), ('lists', 0.044), ('personal', 0.043), ('overlapping', 0.043), ('baselines', 0.04), ('networking', 0.039), ('speak', 0.037), ('membership', 0.036), ('community', 0.034), ('networks', 0.034), ('ok', 0.032), ('icdm', 0.032), ('edges', 0.032), ('creators', 0.032), ('dilly', 0.032), ('knox', 0.032), ('liations', 0.032), ('tweeted', 0.032), ('leaf', 0.032), ('organize', 0.031), ('aspects', 0.031), ('bic', 0.03), ('weight', 0.03), ('feature', 0.03), ('sites', 0.03), ('dk', 0.029), ('students', 0.029), ('turing', 0.029), ('yoshida', 0.029), ('jure', 0.029), ('position', 0.028), ('company', 0.028), ('unsupervised', 0.028), ('argmax', 0.028), ('dimensions', 0.028), ('identify', 0.027), ('college', 0.027), ('manually', 0.027), ('index', 0.027), ('handcock', 0.026), ('homophily', 0.026), ('friendships', 0.026), ('navy', 0.026), ('detected', 0.026), ('school', 0.026), ('embedding', 0.025), ('groundtruth', 0.025), ('modularity', 0.025), ('categorize', 0.025), ('universities', 0.025), ('mcauley', 0.025), ('mixedmembership', 0.025), ('common', 0.025), ('encodes', 0.024), ('edge', 0.024), ('false', 0.024), ('raftery', 0.024), ('attributes', 0.023), ('nested', 0.023), ('latent', 0.023), ('publicly', 0.023), ('predicted', 0.023), ('accessible', 0.023), ('score', 0.022), ('balanced', 0.022)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000004 194 nips-2012-Learning to Discover Social Circles in Ego Networks

Author: Jure Leskovec, Julian J. Mcauley

2 0.17244807 343 nips-2012-Tight Bounds on Profile Redundancy and Distinguishability

Author: Jayadev Acharya, Hirakendu Das, Alon Orlitsky

Abstract: The minimax KL-divergence of any distribution from all distributions in a collection P has several practical implications. In compression, it is called redundancy and represents the least additional number of bits over the entropy needed to encode the output of any distribution in P. In online estimation and learning, it is the lowest expected log-loss regret when guessing a sequence of random values generated by a distribution in P. In hypothesis testing, it upper bounds the largest number of distinguishable distributions in P. Motivated by problems ranging from population estimation to text classiﬁcation and speech recognition, several machine-learning and information-theory researchers have recently considered label-invariant observations and properties induced by i.i.d. distributions. A sufﬁcient statistic for all these properties is the data’s proﬁle, the multiset of the number of times each data element appears. Improving on a sequence of previous works, we show that the redundancy of the collection of distributions induced over proﬁles by length-n i.i.d. sequences is between 0.3 · n1/3 and n1/3 log2 n, in particular, establishing its exact growth power. 1

3 0.1129322 298 nips-2012-Scalable Inference of Overlapping Communities

Author: Prem Gopalan, Sean Gerrish, Michael Freedman, David M. Blei, David M. Mimno

Abstract: We develop a scalable algorithm for posterior inference of overlapping communities in large networks. Our algorithm is based on stochastic variational inference in the mixed-membership stochastic blockmodel (MMSB). It naturally interleaves subsampling the network with estimating its community structure. We apply our algorithm on ten large, real-world networks with up to 60,000 nodes. It converges several orders of magnitude faster than the state-of-the-art algorithm for MMSB, ﬁnds hundreds of communities in large real-world networks, and detects the true communities in 280 benchmark networks with equal or better accuracy compared to other scalable algorithms. 1

4 0.091962203 74 nips-2012-Collaborative Gaussian Processes for Preference Learning

Author: Neil Houlsby, Ferenc Huszar, Zoubin Ghahramani, Jose M. Hernández-lobato

Abstract: We present a new model based on Gaussian processes (GPs) for learning pairwise preferences expressed by multiple users. Inference is simpliﬁed by using a preference kernel for GPs which allows us to combine supervised GP learning of user preferences with unsupervised dimensionality reduction for multi-user systems. The model not only exploits collaborative information from the shared structure in user behavior, but may also incorporate user features if they are available. Approximate inference is implemented using a combination of expectation propagation and variational Bayes. Finally, we present an efﬁcient active learning strategy for querying preferences. The proposed technique performs favorably on real-world data against state-of-the-art multi-user preference learning algorithms. 1

5 0.084082067 183 nips-2012-Learning Partially Observable Models Using Temporally Abstract Decision Trees

Author: Erik Talvitie

Abstract: This paper introduces timeline trees, which are partial models of partially observable environments. Timeline trees are given some speciﬁc predictions to make and learn a decision tree over history. The main idea of timeline trees is to use temporally abstract features to identify and split on features of key events, spread arbitrarily far apart in the past (whereas previous decision-tree-based methods have been limited to a ﬁnite sufﬁx of history). Experiments demonstrate that timeline trees can learn to make high quality predictions in complex, partially observable environments with high-dimensional observations (e.g. an arcade game). 1

6 0.077782795 182 nips-2012-Learning Networks of Heterogeneous Influence

7 0.075720489 75 nips-2012-Collaborative Ranking With 17 Parameters

8 0.071921282 49 nips-2012-Automatic Feature Induction for Stagewise Collaborative Filtering

9 0.067727968 253 nips-2012-On Triangular versus Edge Representations --- Towards Scalable Modeling of Networks

10 0.065415114 178 nips-2012-Learning Label Trees for Probabilistic Modelling of Implicit Feedback

11 0.063098326 109 nips-2012-Efficient Monte Carlo Counterfactual Regret Minimization in Games with Many Player Actions

12 0.061638981 69 nips-2012-Clustering Sparse Graphs

13 0.061164185 199 nips-2012-Link Prediction in Graphs with Autoregressive Features

14 0.061078779 258 nips-2012-Online L1-Dictionary Learning with Application to Novel Document Detection

15 0.0599408 246 nips-2012-Nonparametric Max-Margin Matrix Factorization for Collaborative Prediction

16 0.059041053 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs

17 0.052460242 10 nips-2012-A Linear Time Active Learning Algorithm for Link Classification

18 0.052032914 286 nips-2012-Random Utility Theory for Social Choice

19 0.050035115 302 nips-2012-Scaling MPE Inference for Constrained Continuous Markov Random Fields with Consensus Optimization

20 0.048540995 106 nips-2012-Dynamical And-Or Graph Learning for Object Shape Modeling and Detection

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.135), (1, 0.034), (2, -0.048), (3, -0.032), (4, -0.031), (5, -0.053), (6, -0.005), (7, 0.005), (8, -0.067), (9, 0.103), (10, -0.039), (11, 0.039), (12, -0.065), (13, -0.015), (14, 0.021), (15, 0.049), (16, -0.042), (17, 0.047), (18, -0.027), (19, 0.006), (20, -0.075), (21, -0.001), (22, 0.078), (23, -0.076), (24, -0.018), (25, -0.064), (26, 0.048), (27, 0.016), (28, 0.043), (29, -0.02), (30, -0.042), (31, 0.006), (32, -0.084), (33, -0.01), (34, -0.065), (35, -0.028), (36, 0.117), (37, -0.001), (38, 0.031), (39, 0.039), (40, -0.01), (41, -0.014), (42, 0.014), (43, -0.035), (44, -0.087), (45, 0.0), (46, 0.196), (47, -0.087), (48, 0.065), (49, 0.04)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95972675 194 nips-2012-Learning to Discover Social Circles in Ego Networks

Author: Jure Leskovec, Julian J. Mcauley

2 0.65867221 298 nips-2012-Scalable Inference of Overlapping Communities

Author: Prem Gopalan, Sean Gerrish, Michael Freedman, David M. Blei, David M. Mimno

3 0.62592638 253 nips-2012-On Triangular versus Edge Representations --- Towards Scalable Modeling of Networks

Author: Qirong Ho, Junming Yin, Eric P. Xing

Abstract: In this paper, we argue for representing networks as a bag of triangular motifs, particularly for important network problems that current model-based approaches handle poorly due to computational bottlenecks incurred by using edge representations. Such approaches require both 1-edges and 0-edges (missing edges) to be provided as input, and as a consequence, approximate inference algorithms for these models usually require Ω(N 2 ) time per iteration, precluding their application to larger real-world networks. In contrast, triangular modeling requires less computation, while providing equivalent or better inference quality. A triangular motif is a vertex triple containing 2 or 3 edges, and the number of such motifs is 2 Θ( i Di ) (where Di is the degree of vertex i), which is much smaller than N 2 for low-maximum-degree networks. Using this representation, we develop a novel mixed-membership network model and approximate inference algorithm suitable for large networks with low max-degree. For networks with high maximum degree, the triangular motifs can be naturally subsampled in a node-centric fashion, allowing for much faster inference at a small cost in accuracy. Empirically, we demonstrate that our approach, when compared to that of an edge-based model, has faster runtime and improved accuracy for mixed-membership community detection. We conclude with a large-scale demonstration on an N ≈ 280, 000-node network, which is infeasible for network models with Ω(N 2 ) inference cost. 1

4 0.49622238 346 nips-2012-Topology Constraints in Graphical Models

Author: Marcelo Fiori, Pablo Musé, Guillermo Sapiro

Abstract: Graphical models are a very useful tool to describe and understand natural phenomena, from gene expression to climate change and social interactions. The topological structure of these graphs/networks is a fundamental part of the analysis, and in many cases the main goal of the study. However, little work has been done on incorporating prior topological knowledge onto the estimation of the underlying graphical models from sample data. In this work we propose extensions to the basic joint regression model for network estimation, which explicitly incorporate graph-topological constraints into the corresponding optimization approach. The ﬁrst proposed extension includes an eigenvector centrality constraint, thereby promoting this important prior topological property. The second developed extension promotes the formation of certain motifs, triangle-shaped ones in particular, which are known to exist for example in genetic regulatory networks. The presentation of the underlying formulations, which serve as examples of the introduction of topological constraints in network estimation, is complemented with examples in diverse datasets demonstrating the importance of incorporating such critical prior knowledge. 1

5 0.49292523 178 nips-2012-Learning Label Trees for Probabilistic Modelling of Implicit Feedback

Author: Andriy Mnih, Yee W. Teh

Abstract: User preferences for items can be inferred from either explicit feedback, such as item ratings, or implicit feedback, such as rental histories. Research in collaborative ﬁltering has concentrated on explicit feedback, resulting in the development of accurate and scalable models. However, since explicit feedback is often difﬁcult to collect it is important to develop effective models that take advantage of the more widely available implicit feedback. We introduce a probabilistic approach to collaborative ﬁltering with implicit feedback based on modelling the user’s item selection process. In the interests of scalability, we restrict our attention to treestructured distributions over items and develop a principled and efﬁcient algorithm for learning item trees from data. We also identify a problem with a widely used protocol for evaluating implicit feedback models and propose a way of addressing it using a small quantity of explicit feedback data. 1

6 0.49208012 49 nips-2012-Automatic Feature Induction for Stagewise Collaborative Filtering

7 0.48500809 343 nips-2012-Tight Bounds on Profile Redundancy and Distinguishability

8 0.47886917 183 nips-2012-Learning Partially Observable Models Using Temporally Abstract Decision Trees

9 0.47020078 215 nips-2012-Minimizing Uncertainty in Pipelines

10 0.44872314 103 nips-2012-Distributed Probabilistic Learning for Camera Networks with Missing Data

11 0.44637316 10 nips-2012-A Linear Time Active Learning Algorithm for Link Classification

12 0.44612181 165 nips-2012-Iterative ranking from pair-wise comparisons

13 0.43713072 75 nips-2012-Collaborative Ranking With 17 Parameters

14 0.43018743 189 nips-2012-Learning from the Wisdom of Crowds by Minimax Entropy

15 0.42881775 132 nips-2012-Fiedler Random Fields: A Large-Scale Spectral Approach to Statistical Network Modeling

16 0.42560124 74 nips-2012-Collaborative Gaussian Processes for Preference Learning

17 0.42272681 182 nips-2012-Learning Networks of Heterogeneous Influence

18 0.41376954 155 nips-2012-Human memory search as a random walk in a semantic network

19 0.41015184 345 nips-2012-Topic-Partitioned Multinetwork Embeddings

20 0.39286336 288 nips-2012-Rational inference of relative preferences

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.062), (7, 0.253), (21, 0.041), (36, 0.011), (38, 0.094), (39, 0.018), (42, 0.028), (54, 0.036), (55, 0.03), (74, 0.054), (76, 0.179), (80, 0.069), (92, 0.029)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.83593744 194 nips-2012-Learning to Discover Social Circles in Ego Networks

Author: Jure Leskovec, Julian J. Mcauley

2 0.79555076 170 nips-2012-Large Scale Distributed Deep Networks

Author: Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc'aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Quoc V. Le, Andrew Y. Ng

Abstract: Recent work in unsupervised feature learning and deep learning has shown that being able to train large models can dramatically improve performance. In this paper, we consider the problem of training a deep network with billions of parameters using tens of thousands of CPU cores. We have developed a software framework called DistBelief that can utilize computing clusters with thousands of machines to train large models. Within this framework, we have developed two algorithms for large-scale distributed training: (i) Downpour SGD, an asynchronous stochastic gradient descent procedure supporting a large number of model replicas, and (ii) Sandblaster, a framework that supports a variety of distributed batch optimization procedures, including a distributed implementation of L-BFGS. Downpour SGD and Sandblaster L-BFGS both increase the scale and speed of deep network training. We have successfully used our system to train a deep network 30x larger than previously reported in the literature, and achieves state-of-the-art performance on ImageNet, a visual object recognition task with 16 million images and 21k categories. We show that these same techniques dramatically accelerate the training of a more modestly- sized deep network for a commercial speech recognition service. Although we focus on and report performance of these methods as applied to training large neural networks, the underlying algorithms are applicable to any gradient-based machine learning algorithm. 1

3 0.70599693 358 nips-2012-Value Pursuit Iteration

Author: Amir M. Farahmand, Doina Precup

Abstract: Value Pursuit Iteration (VPI) is an approximate value iteration algorithm that ﬁnds a close to optimal policy for reinforcement learning problems with large state spaces. VPI has two main features: First, it is a nonparametric algorithm that ﬁnds a good sparse approximation of the optimal value function given a dictionary of features. The algorithm is almost insensitive to the number of irrelevant features. Second, after each iteration of VPI, the algorithm adds a set of functions based on the currently learned value function to the dictionary. This increases the representation power of the dictionary in a way that is directly relevant to the goal of having a good approximation of the optimal value function. We theoretically study VPI and provide a ﬁnite-sample error upper bound for it. 1

4 0.67710394 293 nips-2012-Relax and Randomize : From Value to Algorithms

Author: Sasha Rakhlin, Ohad Shamir, Karthik Sridharan

Abstract: We show a principled way of deriving online learning algorithms from a minimax analysis. Various upper bounds on the minimax value, previously thought to be non-constructive, are shown to yield algorithms. This allows us to seamlessly recover known methods and to derive new ones, also capturing such “unorthodox” methods as Follow the Perturbed Leader and the R2 forecaster. Understanding the inherent complexity of the learning problem thus leads to the development of algorithms. To illustrate our approach, we present several new algorithms, including a family of randomized methods that use the idea of a “random playout”. New versions of the Follow-the-Perturbed-Leader algorithms are presented, as well as methods based on the Littlestone’s dimension, efﬁcient methods for matrix completion with trace norm, and algorithms for the problems of transductive learning and prediction with static experts. 1

5 0.66732448 354 nips-2012-Truly Nonparametric Online Variational Inference for Hierarchical Dirichlet Processes

Author: Michael Bryant, Erik B. Sudderth

Abstract: Variational methods provide a computationally scalable alternative to Monte Carlo methods for large-scale, Bayesian nonparametric learning. In practice, however, conventional batch and online variational methods quickly become trapped in local optima. In this paper, we consider a nonparametric topic model based on the hierarchical Dirichlet process (HDP), and develop a novel online variational inference algorithm based on split-merge topic updates. We derive a simpler and faster variational approximation of the HDP, and show that by intelligently splitting and merging components of the variational posterior, we can achieve substantially better predictions of test data than conventional online and batch variational algorithms. For streaming analysis of large datasets where batch analysis is infeasible, we show that our split-merge updates better capture the nonparametric properties of the underlying model, allowing continual learning of new topics.

6 0.66509414 209 nips-2012-Max-Margin Structured Output Regression for Spatio-Temporal Action Localization

7 0.66076005 188 nips-2012-Learning from Distributions via Support Measure Machines

8 0.66068476 68 nips-2012-Clustering Aggregation as Maximum-Weight Independent Set

9 0.66056842 318 nips-2012-Sparse Approximate Manifolds for Differential Geometric MCMC

10 0.65853864 326 nips-2012-Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses

11 0.65811151 356 nips-2012-Unsupervised Structure Discovery for Semantic Analysis of Audio

12 0.6576854 210 nips-2012-Memorability of Image Regions

13 0.65688258 294 nips-2012-Repulsive Mixtures

14 0.65671968 90 nips-2012-Deep Learning of Invariant Features via Simulated Fixations in Video

15 0.65542024 99 nips-2012-Dip-means: an incremental clustering method for estimating the number of clusters

16 0.65481591 203 nips-2012-Locating Changes in Highly Dependent Data with Unknown Number of Change Points

17 0.65444142 307 nips-2012-Semi-Crowdsourced Clustering: Generalizing Crowd Labeling by Robust Distance Metric Learning

18 0.65427524 144 nips-2012-Gradient-based kernel method for feature extraction and variable selection

19 0.6541245 119 nips-2012-Entropy Estimations Using Correlated Symmetric Stable Random Projections

20 0.65392601 232 nips-2012-Multiplicative Forests for Continuous-Time Processes