nips nips2013 nips2013-196 knowledge-graph by maker-knowledge-mining

196 nips-2013-Modeling Overlapping Communities with Node Popularities

Source: pdf

Author: Prem Gopalan, Chong Wang, David Blei

Abstract: We develop a probabilistic approach for accurate network modeling using node popularities within the framework of the mixed-membership stochastic blockmodel (MMSB). Our model integrates two basic properties of nodes in social networks: homophily and preferential connection to popular nodes. We develop a scalable algorithm for posterior inference, based on a novel nonconjugate variant of stochastic variational inference. We evaluate the link prediction accuracy of our algorithm on nine real-world networks with up to 60,000 nodes, and on simulated networks with degree distributions that follow a power law. We demonstrate that the AMP predicts signiﬁcantly better than the MMSB. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract We develop a probabilistic approach for accurate network modeling using node popularities within the framework of the mixed-membership stochastic blockmodel (MMSB). [sent-6, score-0.627]

2 Our model integrates two basic properties of nodes in social networks: homophily and preferential connection to popular nodes. [sent-7, score-0.295]

3 We develop a scalable algorithm for posterior inference, based on a novel nonconjugate variant of stochastic variational inference. [sent-8, score-0.264]

4 We evaluate the link prediction accuracy of our algorithm on nine real-world networks with up to 60,000 nodes, and on simulated networks with degree distributions that follow a power law. [sent-9, score-0.249]

5 Examples of such networks include online social networks, collaboration networks and hyperlinked blogs. [sent-12, score-0.256]

6 A central problem in social network analysis is to identify hidden community structures and node properties that can best explain the network data and predict connections [19]. [sent-13, score-0.729]

7 Two node properties underlie the most successful models that explain how network connections are generated. [sent-14, score-0.322]

8 The second property that underlies many network models is homophily or similarity, according to which nodes with similar observed or unobserved attributes are more likely to connect to each other. [sent-18, score-0.257]

9 To best explain social network data, a probabilistic model must capture these competing node properties. [sent-19, score-0.384]

10 To capture homophily, our model is built on the mixed-membership stochastic blockmodel (MMSB) [2], a community detection model that allows nodes to belong to multiple communities. [sent-28, score-0.547]

11 (For example, a member of a large social network might belong to overlapping communities of neighbors, co-workers, and school friends. [sent-29, score-0.274]

12 ) The MMSB provides better ﬁts to real network data than single community models [23, 27], but cannot account for node popularities. [sent-30, score-0.584]

13 Speciﬁcally, we extend the assortative MMSB [9] to incorporate per-community node popularity. [sent-31, score-0.307]

14 We develop a scalable algorithm for posterior inference, based on a novel nonconjugate variant of stochastic variational inference [11]. [sent-32, score-0.31]

15 Each link denotes a collaboration between two authors, colored by the posterior estimate of its community assignment. [sent-34, score-0.488]

16 Each author node is sized by its estimated posterior popularity and colored by its dominant research community. [sent-35, score-0.442]

17 Following [14], we show an example where incorporating node popularities helps in accurately identifying communities (Right). [sent-37, score-0.557]

18 Further, using simulated networks, we show that node popularities are essential for predictive accuracy in the presence of power-law distributed node degrees. [sent-40, score-0.726]

19 [14] proposed the degree-corrected blockmodel that extends the classic stochastic blockmodels [23] to incorporate node popularities. [sent-44, score-0.394]

20 [16] proposed the latent cluster random effects model that extends the latent space model [10] to include node popularities. [sent-46, score-0.311]

21 Both models capture node similarity and popularity, but assume that unobserved similarity arises from each node participating in a single community. [sent-47, score-0.57]

22 Finally, the Poisson community model [4] is a probabilistic model of overlapping communities that implicitly captures degree-corrected mixedmemberships. [sent-48, score-0.457]

23 However, the standard EM inference under this model drives many of the per-node community parameters to zero, which makes it ineffective for prediction or model metrics based on prediction (e. [sent-49, score-0.329]

24 2 Modeling node popularity and similarity The assortative mixed-membership stochastic blockmodel (MMSB) [9] treats the links or non-links yab of a network as arising from interactions between nodes a and b. [sent-52, score-1.25]

25 Each node a is associated with community memberships πa , a distribution over communities. [sent-53, score-0.702]

26 The probability that two nodes are linked is governed by the similarity of their community memberships and the strength of their shared communities. [sent-54, score-0.707]

27 Given the communities of a pair of nodes, the link indicators yab are independent. [sent-55, score-0.533]

28 We draw yab repeatedly by choosing a community assignment (za→b , za←b ) for a pair of nodes (a, b), and drawing a binary value from a community distribution. [sent-56, score-1.032]

29 Speciﬁcally, the conditional probability of a link in MMSB is p(yab = 1|za→b,i , za←b,j , β) = K i=1 K j=1 za→b,i za←b,j βij , where β is the blockmodel matrix of community strength parameters to be estimated. [sent-57, score-0.492]

30 This captures node similarity in community memberships—if two nodes are linked, it is likely that the latent community indicators were the same. [sent-59, score-1.081]

31 2 In the proposed model, assortative MMSB with node popularities, or AMP, we introduce latent variables θa to capture the popularity of each node a, i. [sent-60, score-0.739]

32 , its propensity to attract links independent of its community memberships. [sent-62, score-0.408]

33 We capture the effect of node popularity and community similarity on link generation using a logit model logit (p(yab = 1|za→b , za←b , θ, β)) ≡ θa + θb + where we deﬁne indicators same community k. [sent-63, score-1.193]

34 This model is also similar in the spirit of the random effects model [10]—the node-speciﬁc K k effect θa captures the popularity of individual nodes while the k=1 δab βk term captures the interactions through latent communities. [sent-72, score-0.406]

35 For each node a, (a) Draw community memberships πa ∼ Dirichlet(α). [sent-78, score-0.702]

36 (c) Draw the probability of a link yab |za→b , za←b , θ, β ∼ logit−1 (za→b , za←b , θ, β). [sent-83, score-0.355]

37 Under the AMP, the similarities between the nodes’ community memberships and their respective popularities compete to explain the observations. [sent-84, score-0.686]

38 We can make AMP simpler by replacing the vector of K latent community strengths β with a single community strength β. [sent-85, score-0.711]

39 We analyze data with the AMP via the posterior distribution over the latent variables 2 2 p(π1:N , θ1:N , z, β1:K |y, α, µ0 , σ0 , σ1 ), where θ1:N represents the node popularities, and the posterior over π1:N represents the community memberships of the nodes. [sent-87, score-0.83]

40 This results in posterior estimates of the community memberships and popularities for each node and posterior estimates of the community assignments for each link. [sent-92, score-1.279]

41 With these estimates, we visualized the discovered community structure and the popular authors. [sent-93, score-0.326]

42 In general, with an estimate of this latent structure, we can study individual links, characterizing the extent to which they occur due to similarity between nodes and the extent to which they are an artifact of the popularity of the nodes. [sent-94, score-0.379]

43 3 A stochastic gradient algorithm for nonconjugate variational inference 2 2 Our goal is to compute the posterior distribution p(π1:N , θ1:N , z, β1:K |y, α, µ0 σ0 , σ1 ). [sent-95, score-0.353]

44 First, in variational inference the coordinate updates are available in closed form only when all the nodes in the graphical model satisfy conditional conjugacy. [sent-99, score-0.363]

45 To see this, note that the Gaussian priors on the popularity θ and the community strengths β are not conjugate to the conditional likelihood of the data. [sent-101, score-0.491]

46 Second, coordinate ascent algorithms iterate over all the O(N 2 ) node pairs making inference intractable for large networks. [sent-102, score-0.381]

47 We use the mean-ﬁeld family, with the following variational distributions: q(za→b = i, za←b = j) = φij ; ab q(βk ) = 2 N (βk ; µk , σβ ); q(πn ) = Dirichlet(πn ; γn ); 2 q(θn ) = N (θn ; λn , σθ ). [sent-107, score-0.288]

48 (2) The posterior over the joint distribution of link community assignments per node pair (a, b) is parameterized by the per-interaction memberships φab 1 , the community memberships by γ, the community strength distributions by µ and the popularity distributions by λ. [sent-108, score-1.832]

49 The remaining lines contain summations over all node pairs; we call these local terms. [sent-115, score-0.303]

50 The distinction between the global and local parameters is important—the updates to global parameters depends on all (or many) local parameters, while the updates to local parameters for a pair of nodes only depends on the relevant global and local parameters in that context. [sent-117, score-0.508]

51 Coordinate ascent inference must consider each pair of nodes at each iteration, but even a single pass through the O(N 2 ) node pairs can be prohibitive. [sent-119, score-0.529]

52 Nevertheless, by carefully manipulating the variational objective, we can develop a scalable stochastic variational inference algorithm for the AMP. [sent-122, score-0.354]

53 The data likelihood terms in the ELBO can be written as Eq [log p(yab |za→b , za←b , θ, β)] = yab Eq [xab ] − Eq [log(1 + exp(xab ))], (4) K k where we deﬁne xab ≡ θa + θb + k=1 βk δab . [sent-125, score-0.357]

54 6: global step 7: Update memberships γa , for each node a ∈ S, using stochastic natural gradients in Eq. [sent-137, score-0.585]

55 8: Update popularities λa , for each node a ∈ S using stochastic gradients in Eq. [sent-139, score-0.553]

56 9: Update community strengths µ using stochastic gradients in Eq. [sent-141, score-0.446]

57 10: Set ρa (t) = (τ0 + ta )−κ ; ta ← ta + 1, for each node a ∈ S. [sent-143, score-0.332]

58 3 The global step We optimize the ELBO with respect to the global variational parameters using stochastic gradient ascent. [sent-157, score-0.337]

59 The global step updates the global community memberships γ, the global popularity parameters λ and the global community strength parameters µ with a stochastic gradient of the lower bound on the ELBO L . [sent-162, score-1.315]

60 In [9], the authors update community memberships of all nodes after each iteration by obtaining the natural gradients of the ELBO 2 with respect to the vector γ of dimension N × K. [sent-163, score-0.651]

61 We use natural gradients for the memberships too, but use distinct stochastic optimizations for the memberships and popularity parameters of each node and maintain a separate learning rate for each node. [sent-164, score-0.868]

62 Since the variational objective is a sum of terms, we can cheaply compute a stochastic gradient by ﬁrst subsampling a subset of terms and then forming an appropriately scaled gradient. [sent-166, score-0.261]

63 At each iteration we sample a node uniformly at random from the N nodes in the network. [sent-168, score-0.379]

64 ) While a naive method will include all interactions of a sampled node as the observed pairs, we can leverage network sparsity for efﬁciency; in many real networks, only a small fraction of the node pairs are linked. [sent-170, score-0.601]

65 Following [2, 9], we have t−1 t ∂γa,k = −γa,k + αk + (a,b)∈links(a) φkk (t) + ab (a,b)∈nonlinks(a) φkk (t), ab (6) where links(a) and nonlinks(a) correspond to the set of links and non-links of a in the training set. [sent-173, score-0.457]

66 Therefore, the gradient of L with respect to the membership parameter γa , computed using all of the nodes’ links and a subsample of its non-links, is a noisy but unbiased estimate of the natural gradient in Eq. [sent-176, score-0.288]

67 5 The gradient of the approximate ELBO with respect to the popularity parameter λa is ∂λt = − a t−1 λa 2 σ1 + (a,b)∈links(a) ∪ nonlinks(a) (yab − rab sab ), (7) where we deﬁne rab as rab ≡ 2 2 exp{λa +σθ /2} exp{λb +σθ /2} . [sent-180, score-0.698]

68 2 2 1+exp{λa +σθ /2} exp{λb +σθ /2}sab (8) Finally, the stochastic gradient of L with respect to the global community strength parameter µk is ∂µt = k t−1 µ0 −µk 2 σ0 + N 2|S| (a,b)∈links(S) ∪ nonlinks(S) 2 φkk (yab − rab exp{µk + σβ /2}). [sent-181, score-0.642]

69 ab (9) As with the community membership gradients, notice that an unbiased estimate of the summation term over non-links in Eq. [sent-182, score-0.472]

70 To obtain an unbiased estimate of the true gradient with respect to µk , the summation over a node’s links and non-links must be scaled by the inverse probability of subsampling that node in Eq. [sent-185, score-0.439]

71 Since each pair is shared between two nodes, and we use a mini-batch with S nodes, the summations over N the node pairs are scaled by 2|S| in Eq. [sent-187, score-0.343]

72 7, (yab − rab sab ) is the residual for the pair (a, b), while in Eq. [sent-195, score-0.25]

73 9, (yab − rab exp{µk + 2 σβ /2}) is the residual for the pair (a, b) conditional on the latent community assignment for both nodes a and b being set to k. [sent-196, score-0.631]

74 Further, notice that the updates for the global parameters of node a and b, and the updates for µ depend only on the diagonal entries of the indicator variational matrix φab . [sent-197, score-0.477]

75 (10) We maintain separate learning rates ρa for each node a, and only update the γ and λ for the nodes in the mini-batch in each iteration. [sent-201, score-0.379]

76 There is a global learning rate ρ for the community strength parameters µ, which are updated in every iteration. [sent-202, score-0.395]

77 There is a per-interaction variational parameter of dimension K × K for each node pair—φab —representing the posterior approximation of which pair of communities are active in determining the link or non-link. [sent-209, score-0.646]

78 The coordinate ascent update for φab is 2 φkk ∝ exp Eq [log πa,k ] + Eq [log πb,k ] + yab µk − rab (exp{µk + σβ /2} − 1) ab (11) φij ab (12) ∝ exp Eq [log πa,i ] + Eq [log πb,j ] , i = j, where rab is deﬁned in Eq. [sent-210, score-1.014]

79 5 Initialization and convergence We initialize the community memberships γ using approximate posterior memberships from the variational inference algorithm for the MMSB [9]. [sent-214, score-0.857]

80 We initialized popularities λ to the logarithm of the normalized node degrees added to a small random offset, and initialized the strengths µ to zero. [sent-215, score-0.492]

81 N is the number of nodes, d is the percent of node pairs that are links and P is the mean perplexity over the links and nonlinks in the held-out test set. [sent-220, score-0.642]

82 4 Empirical study We use the predictive approach to evaluating model ﬁtness [8], comparing the predictive accuracy of AMP (Algorithm 1) to the stochastic variational inference algorithm for the MMSB with link sampling [9]. [sent-285, score-0.415]

83 We computed the link prediction accuracy using a test set of node pairs that are not observed during training. [sent-294, score-0.366]

84 We approximate the predictive distribution of a held-out node pair yab under the AMP using ˆ ˆ posterior estimates θ, β and π as ˆ p(yab |y) ≈ 3 za→b za←b ˆ ˆ p(yab |za→b , za←b , θ, β)p(za→b |ˆa )p(za←b |ˆb ). [sent-297, score-0.627]

85 020 2 4 6 8 2 4 6 8 amp mmsb 2 4 6 8 Ratio of max. [sent-319, score-0.696]

86 Perplexity is the exponential of the average predictive log likelihood of the held-out node pairs. [sent-325, score-0.312]

87 For mean precision and recall, we generate the top n pairs for each node ranked by the probability of a link between them. [sent-326, score-0.413]

88 The ranked list of pairs for each node includes nodes in the test set, as well as nodes in the training set that were non-links. [sent-327, score-0.555]

89 For the stochastic AMP algorithm, we set the “mini-batch” size S = N/100, where N is the number of nodes in the network and we set the non-link sample size m0 = 100. [sent-332, score-0.266]

90 We set the number of communities K = 2 for the political blog network and K = 20 2 for the US air; for all other networks, K was set to 100. [sent-333, score-0.282]

91 The ﬁrst four networks are small in size, and were ﬁt using the AMP model with a single community strength parameter. [sent-345, score-0.404]

92 All other networks were ﬁt with the AMP model with K community strength parameters. [sent-346, score-0.404]

93 Without node popularities, MMSB is dependent entirely on node memberships and community strengths to predict links. [sent-348, score-0.992]

94 Since K is held ﬁxed, communities are likely to have more nodes as N increases, making it increasingly difﬁcult for the MMSB to predict links. [sent-349, score-0.256]

95 For the AMP the mean precision at 10 for US Air, political blogs and netscience were 0. [sent-351, score-0.256]

96 We set a community size range of [200, 500] and a mean node degree of 10 with power-law exponent set to 2. [sent-361, score-0.554]

97 The skewness in degree distributions causes the community strength parameters of MMSB to overestimate or underestimate the linking patterns within communities. [sent-364, score-0.398]

98 The per-node popularities in the AMP can capture the heterogeneity in node degrees, while learning the corrected community strengths. [sent-365, score-0.724]

99 Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. [sent-510, score-0.317]

100 Finding community structure in networks using the eigenvectors of matrices. [sent-545, score-0.346]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('amp', 0.356), ('mmsb', 0.34), ('za', 0.321), ('community', 0.283), ('yab', 0.264), ('node', 0.239), ('popularities', 0.202), ('memberships', 0.18), ('ab', 0.166), ('popularity', 0.157), ('eq', 0.154), ('nodes', 0.14), ('rab', 0.14), ('links', 0.125), ('variational', 0.122), ('communities', 0.116), ('elbo', 0.107), ('collab', 0.093), ('netscience', 0.093), ('xab', 0.093), ('link', 0.091), ('nonlinks', 0.078), ('sab', 0.078), ('assortative', 0.068), ('collaboration', 0.068), ('kk', 0.068), ('political', 0.066), ('stochastic', 0.064), ('networks', 0.063), ('social', 0.062), ('network', 0.062), ('blockmodel', 0.06), ('strength', 0.058), ('homophily', 0.055), ('global', 0.054), ('strengths', 0.051), ('blogs', 0.05), ('gradients', 0.048), ('precision', 0.047), ('cond', 0.047), ('posterior', 0.046), ('predictive', 0.046), ('similarity', 0.046), ('inference', 0.046), ('air', 0.044), ('gradient', 0.043), ('brightkite', 0.041), ('astro', 0.041), ('relativity', 0.041), ('karrer', 0.041), ('exp', 0.039), ('perplexity', 0.039), ('preferential', 0.038), ('blog', 0.038), ('recommendations', 0.037), ('pairs', 0.036), ('latent', 0.036), ('summations', 0.036), ('ascent', 0.036), ('overlapping', 0.034), ('subsample', 0.033), ('logit', 0.032), ('mu', 0.032), ('nonconjugate', 0.032), ('degree', 0.032), ('subsampling', 0.032), ('pair', 0.032), ('updates', 0.031), ('ta', 0.031), ('blockmodels', 0.031), ('hepph', 0.031), ('hepth', 0.031), ('jeong', 0.031), ('krivitsky', 0.031), ('lfr', 0.031), ('linkkdd', 0.031), ('mat', 0.03), ('indicators', 0.03), ('draw', 0.03), ('local', 0.028), ('hep', 0.027), ('hyperlink', 0.027), ('log', 0.027), ('blei', 0.026), ('skewness', 0.025), ('interactions', 0.025), ('captures', 0.024), ('coordinate', 0.024), ('attachment', 0.024), ('replication', 0.024), ('physical', 0.024), ('membership', 0.023), ('raftery', 0.023), ('ph', 0.023), ('discovered', 0.022), ('noisy', 0.021), ('explain', 0.021), ('predicts', 0.021), ('gopalan', 0.021), ('visualized', 0.021)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999958 196 nips-2013-Modeling Overlapping Communities with Node Popularities

Author: Prem Gopalan, Chong Wang, David Blei

2 0.25627074 180 nips-2013-Low-rank matrix reconstruction and clustering via approximate message passing

Author: Ryosuke Matsushita, Toshiyuki Tanaka

Abstract: We study the problem of reconstructing low-rank matrices from their noisy observations. We formulate the problem in the Bayesian framework, which allows us to exploit structural properties of matrices in addition to low-rankedness, such as sparsity. We propose an efﬁcient approximate message passing algorithm, derived from the belief propagation algorithm, to perform the Bayesian inference for matrix reconstruction. We have also successfully applied the proposed algorithm to a clustering problem, by reformulating it as a low-rank matrix reconstruction problem with an additional structural property. Numerical experiments show that the proposed algorithm outperforms Lloyd’s K-means algorithm. 1

3 0.2325514 13 nips-2013-A Scalable Approach to Probabilistic Latent Space Inference of Large-Scale Networks

Author: Junming Yin, Qirong Ho, Eric Xing

Abstract: We propose a scalable approach for making inference about latent spaces of large networks. With a succinct representation of networks as a bag of triangular motifs, a parsimonious statistical model, and an efﬁcient stochastic variational inference algorithm, we are able to analyze real networks with over a million vertices and hundreds of latent roles on a single machine in a matter of hours, a setting that is out of reach for many existing methods. When compared to the state-of-the-art probabilistic approaches, our method is several orders of magnitude faster, with competitive or improved accuracy for latent space recovery and link prediction. 1

4 0.20340011 104 nips-2013-Efficient Online Inference for Bayesian Nonparametric Relational Models

Author: Dae Il Kim, Prem Gopalan, David Blei, Erik Sudderth

Abstract: Stochastic block models characterize observed network relationships via latent community memberships. In large social networks, we expect entities to participate in multiple communities, and the number of communities to grow with the network size. We introduce a new model for these phenomena, the hierarchical Dirichlet process relational model, which allows nodes to have mixed membership in an unbounded set of communities. To allow scalable learning, we derive an online stochastic variational inference algorithm. Focusing on assortative models of undirected networks, we also propose an efﬁcient structured mean ﬁeld variational bound, and online methods for automatically pruning unused communities. Compared to state-of-the-art online learning methods for parametric relational models, we show signiﬁcantly improved perplexity and link prediction accuracy for sparse networks with tens of thousands of nodes. We also showcase an analysis of LittleSis, a large network of who-knows-who at the heights of business and government. 1

5 0.16838242 213 nips-2013-Nonparametric Multi-group Membership Model for Dynamic Networks

Author: Myunghwan Kim, Jure Leskovec

Abstract: unkown-abstract

6 0.12968524 109 nips-2013-Estimating LASSO Risk and Noise Level

7 0.12759776 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

8 0.094718978 187 nips-2013-Memoized Online Variational Inference for Dirichlet Process Mixture Models

9 0.090523131 47 nips-2013-Bayesian Hierarchical Community Discovery

10 0.089700468 288 nips-2013-Scalable Influence Estimation in Continuous-Time Diffusion Networks

11 0.088368356 66 nips-2013-Computing the Stationary Distribution Locally

12 0.083498813 289 nips-2013-Scalable kernels for graphs with continuous attributes

13 0.081994861 7 nips-2013-A Gang of Bandits

14 0.069866888 59 nips-2013-Blind Calibration in Compressed Sensing using Message Passing Algorithms

15 0.066937611 229 nips-2013-Online Learning of Nonparametric Mixture Models via Sequential Variational Approximation

16 0.065579034 359 nips-2013-Σ-Optimality for Active Learning on Gaussian Random Fields

17 0.063937329 143 nips-2013-Integrated Non-Factorized Variational Inference

18 0.05711665 345 nips-2013-Variance Reduction for Stochastic Gradient Optimization

19 0.056931738 151 nips-2013-Learning Chordal Markov Networks by Constraint Satisfaction

20 0.055984661 349 nips-2013-Visual Concept Learning: Combining Machine Vision and Bayesian Generalization on Concept Hierarchies

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.146), (1, 0.048), (2, -0.047), (3, -0.003), (4, 0.035), (5, 0.112), (6, 0.118), (7, -0.02), (8, 0.104), (9, -0.013), (10, 0.079), (11, 0.01), (12, 0.188), (13, -0.101), (14, -0.082), (15, -0.105), (16, 0.033), (17, 0.033), (18, -0.033), (19, -0.154), (20, 0.235), (21, -0.115), (22, -0.054), (23, -0.091), (24, 0.028), (25, 0.044), (26, -0.002), (27, 0.082), (28, 0.23), (29, -0.162), (30, -0.073), (31, -0.049), (32, 0.065), (33, -0.019), (34, -0.014), (35, -0.13), (36, -0.02), (37, 0.094), (38, 0.1), (39, 0.105), (40, 0.136), (41, -0.048), (42, 0.02), (43, 0.052), (44, 0.133), (45, -0.036), (46, 0.066), (47, 0.017), (48, 0.108), (49, 0.003)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.94785225 196 nips-2013-Modeling Overlapping Communities with Node Popularities

Author: Prem Gopalan, Chong Wang, David Blei

2 0.82363236 104 nips-2013-Efficient Online Inference for Bayesian Nonparametric Relational Models

Author: Dae Il Kim, Prem Gopalan, David Blei, Erik Sudderth

3 0.73168296 13 nips-2013-A Scalable Approach to Probabilistic Latent Space Inference of Large-Scale Networks

Author: Junming Yin, Qirong Ho, Eric Xing

4 0.63251245 213 nips-2013-Nonparametric Multi-group Membership Model for Dynamic Networks

Author: Myunghwan Kim, Jure Leskovec

Abstract: unkown-abstract

5 0.58056557 180 nips-2013-Low-rank matrix reconstruction and clustering via approximate message passing

Author: Ryosuke Matsushita, Toshiyuki Tanaka

6 0.51777107 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

7 0.4847239 47 nips-2013-Bayesian Hierarchical Community Discovery

8 0.45346221 189 nips-2013-Message Passing Inference with Chemical Reaction Networks

9 0.4413859 288 nips-2013-Scalable Influence Estimation in Continuous-Time Diffusion Networks

10 0.43561098 187 nips-2013-Memoized Online Variational Inference for Dirichlet Process Mixture Models

11 0.41348919 316 nips-2013-Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

12 0.40551251 343 nips-2013-Unsupervised Structure Learning of Stochastic And-Or Grammars

13 0.40261525 7 nips-2013-A Gang of Bandits

14 0.39914858 3 nips-2013-A* Lasso for Learning a Sparse Bayesian Network Structure for Continuous Variables

15 0.36779213 59 nips-2013-Blind Calibration in Compressed Sensing using Message Passing Algorithms

16 0.36262456 61 nips-2013-Capacity of strong attractor patterns to model behavioural and cognitive prototypes

17 0.36051676 291 nips-2013-Sensor Selection in High-Dimensional Gaussian Trees with Nuisances

18 0.36042875 345 nips-2013-Variance Reduction for Stochastic Gradient Optimization

19 0.35400337 294 nips-2013-Similarity Component Analysis

20 0.35344735 151 nips-2013-Learning Chordal Markov Networks by Constraint Satisfaction

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(16, 0.033), (33, 0.091), (34, 0.099), (41, 0.034), (49, 0.034), (56, 0.062), (70, 0.049), (85, 0.139), (89, 0.028), (91, 0.297), (93, 0.032), (95, 0.01)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.76208484 26 nips-2013-Adaptive Market Making via Online Learning

Author: Jacob Abernethy, Satyen Kale

Abstract: We consider the design of strategies for market making in an exchange. A market maker generally seeks to proﬁt from the difference between the buy and sell price of an asset, yet the market maker also takes exposure risk in the event of large price movements. Proﬁt guarantees for market making strategies have typically required certain stochastic assumptions on the price ﬂuctuations of the asset in question; for example, assuming a model in which the price process is mean reverting. We propose a class of “spread-based” market making strategies whose performance can be controlled even under worst-case (adversarial) settings. We prove structural properties of these strategies which allows us to design a master algorithm which obtains low regret relative to the best such strategy in hindsight. We run a set of experiments showing favorable performance on recent real-world stock price data. 1

same-paper 2 0.72870046 196 nips-2013-Modeling Overlapping Communities with Node Popularities

Author: Prem Gopalan, Chong Wang, David Blei

3 0.68137801 25 nips-2013-Adaptive Anonymity via $b$-Matching

Author: Krzysztof M. Choromanski, Tony Jebara, Kui Tang

Abstract: The adaptive anonymity problem is formalized where each individual shares their data along with an integer value to indicate their personal level of desired privacy. This problem leads to a generalization of k-anonymity to the b-matching setting. Novel algorithms and theory are provided to implement this type of anonymity. The relaxation achieves better utility, admits theoretical privacy guarantees that are as strong, and, most importantly, accommodates a variable level of anonymity for each individual. Empirical results conﬁrm improved utility on benchmark and social data-sets.

4 0.56696743 168 nips-2013-Learning to Pass Expectation Propagation Messages

Author: Nicolas Heess, Daniel Tarlow, John Winn

Abstract: Expectation Propagation (EP) is a popular approximate posterior inference algorithm that often provides a fast and accurate alternative to sampling-based methods. However, while the EP framework in theory allows for complex nonGaussian factors, there is still a signiﬁcant practical barrier to using them within EP, because doing so requires the implementation of message update operators, which can be difﬁcult and require hand-crafted approximations. In this work, we study the question of whether it is possible to automatically derive fast and accurate EP updates by learning a discriminative model (e.g., a neural network or random forest) to map EP message inputs to EP message outputs. We address the practical concerns that arise in the process, and we provide empirical analysis on several challenging and diverse factors, indicating that there is a space of factors where this approach appears promising. 1

5 0.56160408 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

Author: Tai Qin, Karl Rohe

Abstract: Spectral clustering is a fast and popular algorithm for ﬁnding clusters in networks. Recently, Chaudhuri et al. [1] and Amini et al. [2] proposed inspired variations on the algorithm that artiﬁcially inﬂate the node degrees for improved statistical performance. The current paper extends the previous statistical estimation results to the more canonical spectral clustering algorithm in a way that removes any assumption on the minimum degree and provides guidance on the choice of the tuning parameter. Moreover, our results show how the “star shape” in the eigenvectors–a common feature of empirical networks–can be explained by the Degree-Corrected Stochastic Blockmodel and the Extended Planted Partition model, two statistical models that allow for highly heterogeneous degrees. Throughout, the paper characterizes and justiﬁes several of the variations of the spectral clustering algorithm in terms of these models. 1

6 0.56001633 7 nips-2013-A Gang of Bandits

7 0.54358107 332 nips-2013-Tracking Time-varying Graphical Structure

8 0.52483481 140 nips-2013-Improved and Generalized Upper Bounds on the Complexity of Policy Iteration

9 0.52208143 104 nips-2013-Efficient Online Inference for Bayesian Nonparametric Relational Models

10 0.51182091 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints

11 0.50184423 232 nips-2013-Online PCA for Contaminated Data

12 0.49608201 206 nips-2013-Near-Optimal Entrywise Sampling for Data Matrices

13 0.49405965 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

14 0.49312729 289 nips-2013-Scalable kernels for graphs with continuous attributes

15 0.4893533 316 nips-2013-Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

16 0.48810741 278 nips-2013-Reward Mapping for Transfer in Long-Lived Agents

17 0.48748758 262 nips-2013-Real-Time Inference for a Gamma Process Model of Neural Spiking

18 0.48724028 350 nips-2013-Wavelets on Graphs via Deep Learning

19 0.48719433 213 nips-2013-Nonparametric Multi-group Membership Model for Dynamic Networks

20 0.4857786 159 nips-2013-Learning Prices for Repeated Auctions with Strategic Buyers