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

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

Source: pdf

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

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Spectral clustering is a fast and popular algorithm for ﬁnding clusters in networks. [sent-5, score-0.174]

2 [2] proposed inspired variations on the algorithm that artiﬁcially inﬂate the node degrees for improved statistical performance. [sent-8, score-0.241]

3 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. [sent-9, score-0.531]

4 Throughout, the paper characterizes and justiﬁes several of the variations of the spectral clustering algorithm in terms of these models. [sent-11, score-0.338]

5 Spectral clustering is a fast and popular technique for ﬁnding communities in networks. [sent-16, score-0.161]

6 Several previous authors have studied the estimation properties of spectral clustering under various statistical network models (McSherry [3], Dasgupta et al. [sent-17, score-0.373]

7 [2] proposed two inspired ways of artiﬁcially inﬂating the node degrees in ways that provide statistical regularization to spectral clustering. [sent-24, score-0.485]

8 This paper examines the statistical estimation performance of regularized spectral clustering under the Degree-Corrected Stochastic Blockmodel (DC-SBM), an extension of the Stochastic Blockmodel (SBM) that allows for heterogeneous degrees (Holland and Leinhardt [9], Karrer and Newman [10]). [sent-25, score-0.581]

9 The SBM and the DC-SBM are closely related to the planted partition model and the extended planted partition model, respectively. [sent-26, score-0.294]

10 We extend the previous results in the following ways: (a) In contrast to previous studies, this paper studies the regularization step with a canonical version of spectral clustering that uses k-means. [sent-27, score-0.374]

11 The results do not require any assumptions on the minimum expected node degree; instead, there is a threshold demonstrating that higher degree nodes are easier to cluster. [sent-28, score-0.55]

12 This threshold is a function of the leverage scores that have proven essential in other contexts, for both graph algorithms and network data analysis (see Mahoney [11] and references therein). [sent-29, score-0.255]

13 These are the ﬁrst results that relate leverage scores to the statistical performance 1 of spectral clustering. [sent-30, score-0.418]

14 This demonstrates how projecting the rows of the eigenvector matrix onto the unit sphere (an algorithmic step proposed by Ng et al. [sent-34, score-0.249]

15 , vN } is the vertex or node set and E is the edge set. [sent-41, score-0.217]

16 E contains a pair (i, j) if there is an edge between node i and j. [sent-43, score-0.217]

17 Aij , j The following notations will be used throughout the paper: ||·|| denotes the spectral norm, and ||·||F denotes the Frobenius norm. [sent-47, score-0.208]

18 2 The Algorithm: Regularized Spectral Clustering (RSC) For a sparse network with strong degree heterogeneity, standard spectral clustering often fails to function properly (Amini et al. [sent-52, score-0.533]

19 The spectral algorithm proposed and studied by Chaudhuri et al. [sent-56, score-0.243]

20 [1] divides the nodes into two random subsets and only uses the induced subgraph on one of those random subsets to compute the spectral decomposition. [sent-57, score-0.366]

21 In this paper, we will study the more traditional version of spectral algorithm that uses the spectral decomposition on the entire matrix (Ng et al. [sent-58, score-0.491]

22 Deﬁne the regularized spectral clustering (RSC) algorithm as follows: 1. [sent-60, score-0.415]

23 Given input adjacency matrix A, number of clusters K, and regularizer τ , calculate the regularized graph Laplacian Lτ . [sent-61, score-0.278]

24 (As discussed later, a good default for τ is the average node degree. [sent-62, score-0.169]

25 This paper will refer to “standard spectral clustering” as the above algorithm with L replacing Lτ . [sent-87, score-0.208]

26 These spectral algorithms have two main steps: 1) ﬁnd the principal eigenspace of the (regularized) graph Laplacian; 2) determine the clusters in the low dimensional eigenspace. [sent-88, score-0.297]

27 2 3 The Degree-Corrected Stochastic Blockmodel (DC-SBM) In the Stochastic Blockmodel (SBM), each node belongs to one of K blocks. [sent-93, score-0.169]

28 Each edge corresponds to an independent Bernoulli random variable where the probability of an edge between any two nodes depends only on the block memberships of the two nodes (Holland and Leinhardt [9]). [sent-94, score-0.52]

29 One limitation of the SBM is that it presumes all nodes within the same block have the same expected degree. [sent-115, score-0.296]

30 The Degree-Corrected Stochastic Blockmodel (DC-SBM) (Karrer and Newman [10]) is a generalization of the SBM that adds an additional set of parameters (θi > 0 for each node i) that control the node degrees. [sent-116, score-0.338]

31 Then the probability of an edge between node i and node j is θi θj Bzi zj , where θi θj Bzi zj ∈ [0, 1] for any i, j = 1, 2, . [sent-118, score-0.554]

32 Under this constraint, B has explicit meaning: If s = t, Bst represents the expected number of links between block s and block t and if s = t, Bst is twice the expected number of links within block s. [sent-125, score-0.384]

33 This matrix can be expressed as a product of the matrices, A = ΘZBZ T Θ, where (1) Θ ∈ RN ×N is a diagonal matrix whose ii’th element is θi and (2) Z ∈ {0, 1}N ×K is the membership matrix with Zit = 1 if and only if node i belongs to block t (i. [sent-128, score-0.481]

34 This section shows that with the population adjacency matrix A and a proper regularizer τ , RSC perfectly reconstructs the block partition. [sent-133, score-0.264]

35 Deﬁne the diagonal matrix D to contain the expected node degrees, Dii = j Aij and deﬁne Dτ = D + τ I where τ ≥ 0 is the regularizer. [sent-134, score-0.272]

36 Then, deﬁne the population graph Laplacian L and the population version of regularized graph Laplacian Lτ , both elements of RN ×N , in the following way: L = D −1/2 A D −1/2 , −1/2 −1/2 Lτ = D τ A Dτ . [sent-135, score-0.255]

37 A couple lines of algebra shows that [DB ]ss = Ws is the total expected degrees of nodes from block s and that Dii = θi [DB ]zi zi . [sent-137, score-0.448]

38 2 demonstrates that Lτ has a similarly simple form that separates the block-related information (BL ) and node speciﬁc information (Θτ ). [sent-146, score-0.169]

39 First, if two nodes i and j belong to the same block, then the corresponding rows of Xτ (denoted as Xτi and Xτj ) both point θτ in the same direction, but with different lengths: ||Xτi ||2 = ( θτiδz ,z )1/2 . [sent-162, score-0.218]

40 Second, if two nodes j j j i i and j belong to different blocks, then Xτi and Xτj are orthogonal to each other. [sent-163, score-0.185]

41 Third, if zi = zj then after projecting these points onto the sphere as in Xτ∗ , the rows are equal: [Xτ∗ ]i = [Xτ∗ ]j = Uzi . [sent-164, score-0.31]

42 Finally, if zi = zj , then the rows are perpendicular, [Xτ∗ ]i ⊥ [Xτ∗ ]j . [sent-165, score-0.224]

43 Note that if Θ were the identity matrix, then the left panel in Figure 1 would look like the right panel in Figure 1; without degree heterogeneity, there would be no star shape and no need for a projection step. [sent-168, score-0.365]

44 This suggests that the star shaped ﬁgure often observed in data analysis stems from the degree heterogeneity in the network. [sent-169, score-0.262]

45 Without normalization (left panel), the nodes with same block membership share the same direction in the projected space. [sent-200, score-0.317]

46 After normalization (right panel), nodes with same block membership share the same position in the projected space. [sent-201, score-0.317]

47 Let δ be the minimum expected degree of G, that is δ = mini Dii . [sent-213, score-0.223]

48 This is the fundamental reason that RSC works for networks containing some nodes with extremely small degrees. [sent-224, score-0.193]

49 The next theorem bounds the difference between the empirical and population eigenvectors (and their row normalized versions) in terms of the Frobenius norm. [sent-227, score-0.196]

50 Similarly, run k-means on the rows of the population eigenvector matrix Xτ∗ and deﬁne the population centroids C1 , . [sent-249, score-0.243]

51 In essence, we consider node i correctly clustered if Ci is closer to Ci than it is to any other Cj for all j with Zj = Zi . [sent-253, score-0.2]

52 Because clustering only requires estimation of the correct subspace, our deﬁnition of correctly clustered is amended with the rotation O T ∈ RK×K , ∗ the matrix which minimizes Xτ O T − Xτ∗ F . [sent-259, score-0.201]

53 If Ci O T is closer to Ci than it is to any other Cj for j with Zj = Zi , then we say that node i is correctly clustered. [sent-263, score-0.169]

54 (Main Theorem) Suppose A ∈ RN ×N is an adjacency matrix of a graph G generated from the DC-SBM with K blocks and parameters {B, Z, Θ}. [sent-270, score-0.205]

55 Setting τ equal to the average node degree balances these terms. [sent-283, score-0.329]

56 Speciﬁcally, if the minimum expected degree δ = O(ln N ), then we need τ ≥ c( ) ln N to have enough regularization to satisfy condition (b) on δ + τ . [sent-285, score-0.371]

57 The matrix Z T Θτ Z is diagonal and the (s, s)’th element is the summation of θi within block s. [sent-288, score-0.181]

58 If EM = ω(N ln N ) where M = i Dii is the sum of the node degrees, then τ = ω(M/N ) sends the smallest diagonal entry of Z T Θτ Z to 0, sending λK , the smallest eigenvalue of C, to zero. [sent-289, score-0.314]

59 Remark 2 (Thresholding m): Mahoney [11] (and references therein) shows how the leverage scores of A and L are informative for both data analysis and algorithmic stability. [sent-298, score-0.21]

60 For L, the leverage score of node i is ||X i ||2 , the length of the ith row of the matrix containing the top K eigenvectors. [sent-299, score-0.405]

61 4 is the ﬁrst result that explicitly relates the leverage scores to the statistical performance of spectral clustering. [sent-301, score-0.418]

62 Recall that m2 is the minimum of the squared row lengths in Xτ and Xτ , that is the minimum leverage score in both Lτ and Lτ . [sent-302, score-0.262]

63 The τ θi leverage scores in Lτ have an explicit form ||Xτi ||2 = 2 θ τ δz ,z . [sent-304, score-0.21]

64 So, if node i has small expected j j j i τ degree, then θi is small, rendering ||Xτi ||2 small. [sent-305, score-0.199]

65 i The problem arises from projecting Xτ onto the unit sphere for a node i with small leverage; it ampliﬁes a noisy measurement. [sent-308, score-0.255]

66 Motivated by this intuition, the next corollary focuses on the high leverage nodes. [sent-309, score-0.165]

67 Deﬁne S to be a subset of nodes i whose leverage scores in Lτ and Xτ , ||Xτi || and ||Xτ || exceed the threshold m∗ : i S = {i : ||Xτi || ≥ m∗ , ||Xτ || ≥ m∗ }. [sent-311, score-0.368]

68 Let N1 = |S| denote the number of nodes in S and deﬁne M1 = M ∩ S as the set of mis-clustered nodes restricted in S. [sent-316, score-0.316]

69 Since we do not make a minimum degree assumption, this value potentially approaches zero, making the bound useless. [sent-322, score-0.193]

70 The above thresholding procedure only clusters the nodes in S. [sent-327, score-0.202]

71 ∗ ∗ (c) For each node i ∈ S, ﬁnd the centroid Cs such that ||[Xτ ]i − Cs ||2 = min1≤t≤K ||[Xτ ]i − / Ct ||2 . [sent-337, score-0.214]

72 Deﬁne the four parameter Stochastic Blockmodel SBM (p, r, s, K) as follows: p is the probability of an edge occurring between two nodes from the same block, r is the probability of an out-block linkage, s is the number of nodes within each block, and K is the number of blocks. [sent-347, score-0.364]

73 Because the SBM lacks degree heterogeneity within blocks, the rows of X within the same block already share the same length. [sent-348, score-0.399]

74 4, with p and r ﬁxed and p > r, and applying k-means to the rows of X, we have K 2 ln N |M |/N = Op . [sent-353, score-0.172]

75 Moreover, it makes the results for spectral clustering comparable to the results for the MLE in Choi et al. [sent-357, score-0.373]

76 5 Simulation and Analysis of Political Blogs This section compares ﬁve different methods of spectral clustering. [sent-359, score-0.208]

77 Experiment 1 generates networks from the DC-SBM with a power-law degree distribution. [sent-360, score-0.195]

78 Finally, the beneﬁts of regularization are illustrated on an empirical network from the political blogosphere during the 2004 presidential election (Adamic and Glance [17]). [sent-362, score-0.212]

79 The simulations compare (1) standard spectral clustering (SC), (2) RSC as deﬁned in section 2, (3) RSC without projecting Xτ onto unit sphere (RSC wp), (4) regularized SC with thresholding (tRSC), and (5) spectral clustering with perturbation (SCP) (Amini et al. [sent-363, score-0.874]

80 In addition, experiment 2 compares the performance of RSC on the subset of nodes with high leverage scores (RSC on S) with the other 5 methods. [sent-365, score-0.404]

81 This experiment examines how degree heterogeneity affects the performance of the spectral clustering algorithms. [sent-368, score-0.632]

82 In each sample, K = 3 and each block contains 300 nodes (N = 900). [sent-377, score-0.266]

83 Throughout the simulations, the SNR is set to three and the expected average degree is set to eight. [sent-379, score-0.19]

84 If a method assigns more than 95% of the nodes into one block, then we consider all nodes to be misclustered. [sent-383, score-0.316]

85 The experiment shows that (1) if the degrees are more heterogeneous (β ≤ 3. [sent-384, score-0.175]

86 This experiment compares SC, RSC, RSC wp, t-RSC and SCP under the SBM with no degree heterogeneity. [sent-387, score-0.196]

87 without degree heterogeneity) all spectral clustering methods perform comparably. [sent-395, score-0.498]

88 5 10 beta 15 20 25 30 expected average degree Figure 2: Left Panel: Comparison of Performance for SC, RSC, RSC wp, t-RSC, SCP and (RSC on S) under different degree heterogeneity. [sent-413, score-0.35]

89 This empirical network is comprised of political blogs during the 2004 US presidential election (Adamic and Glance [17]). [sent-417, score-0.173]

90 If RSC is applied to the 90% of nodes with the largest leverage scores (i. [sent-426, score-0.368]

91 excluding the nodes with the smallest leverage scores), then the misclustering rate among these high leverage nodes is 44/1100, which is almost 50% lower. [sent-428, score-0.648]

92 This illustrates how the leverage score corresponding to a node can gauge the strength of the clustering evidence for that node relative to the other nodes. [sent-429, score-0.607]

93 However, because there are several very small degree nodes in this data, the values computed in step 4 of the algorithm in [1] sometimes take negative values. [sent-431, score-0.318]

94 6 Discussion In this paper, we give theoretical, simulation, and empirical results that demonstrate how a simple adjustment to the standard spectral clustering algorithm can give dramatically better results for networks with heterogeneous degrees. [sent-433, score-0.44]

95 Our theoretical results add to the current results by studying the regularization step in a more canonical version of the spectral clustering algorithm. [sent-434, score-0.374]

96 Moreover, our main results require no assumptions on the minimum node degree. [sent-435, score-0.202]

97 This is crucial because it allows us to study situations where several nodes have small leverage scores; in these situations, regularization is most beneﬁcial. [sent-436, score-0.333]

98 Spectral clustering of graphs with general degrees in the extended planted partition model. [sent-445, score-0.349]

99 Finding planted partitions in random graphs with general e degree distributions. [sent-464, score-0.26]

100 A consistent adjacency spectral embedding for stochastic blockmodel graphs. [sent-484, score-0.465]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('rsc', 0.612), ('sbm', 0.246), ('spectral', 0.208), ('node', 0.169), ('sc', 0.162), ('degree', 0.16), ('nodes', 0.158), ('blockmodel', 0.146), ('scp', 0.144), ('leverage', 0.139), ('clustering', 0.13), ('ln', 0.112), ('dii', 0.11), ('block', 0.108), ('planted', 0.1), ('karrer', 0.091), ('panel', 0.087), ('wp', 0.086), ('zj', 0.084), ('chaudhuri', 0.083), ('zi', 0.08), ('rohe', 0.078), ('laplacian', 0.078), ('regularized', 0.077), ('amini', 0.075), ('adjacency', 0.072), ('degrees', 0.072), ('heterogeneity', 0.071), ('scores', 0.071), ('heterogeneous', 0.067), ('ci', 0.062), ('bst', 0.062), ('bzi', 0.062), ('rows', 0.06), ('eigenvalues', 0.058), ('row', 0.057), ('db', 0.057), ('eigenvectors', 0.056), ('mis', 0.054), ('misclustering', 0.054), ('adamic', 0.054), ('election', 0.054), ('sphere', 0.054), ('th', 0.054), ('rk', 0.053), ('membership', 0.051), ('political', 0.05), ('blocks', 0.048), ('rn', 0.048), ('edge', 0.048), ('bl', 0.047), ('partition', 0.047), ('graph', 0.045), ('chung', 0.045), ('centroid', 0.045), ('newman', 0.044), ('population', 0.044), ('clusters', 0.044), ('holland', 0.043), ('aij', 0.043), ('blockmodels', 0.041), ('bab', 0.041), ('leinhardt', 0.041), ('trsc', 0.041), ('zbl', 0.041), ('zbz', 0.041), ('matrix', 0.04), ('theorem', 0.039), ('stochastic', 0.039), ('regularization', 0.036), ('experiment', 0.036), ('qin', 0.036), ('blogosphere', 0.036), ('presidential', 0.036), ('procrustes', 0.036), ('sussman', 0.036), ('et', 0.035), ('networks', 0.035), ('ames', 0.033), ('blog', 0.033), ('blogs', 0.033), ('diagonal', 0.033), ('minimum', 0.033), ('projecting', 0.032), ('cluster', 0.032), ('cj', 0.032), ('aji', 0.031), ('clustered', 0.031), ('communities', 0.031), ('star', 0.031), ('xij', 0.031), ('community', 0.03), ('expected', 0.03), ('vk', 0.028), ('eigenvector', 0.028), ('snr', 0.027), ('examines', 0.027), ('orthogonal', 0.027), ('centroids', 0.027), ('corollary', 0.026)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999958 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

Author: Tai Qin, Karl Rohe

2 0.14633073 271 nips-2013-Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima

Author: Po-Ling Loh, Martin J. Wainwright

Abstract: We establish theoretical results concerning local optima of regularized M estimators, where both loss and penalty functions are allowed to be nonconvex. Our results show that as long as the loss satisﬁes restricted strong convexity and the penalty satisﬁes suitable regularity conditions, any local optimum of the composite objective lies within statistical precision of the true parameter vector. Our theory covers a broad class of nonconvex objective functions, including corrected versions of the Lasso for errors-in-variables linear models and regression in generalized linear models using nonconvex regularizers such as SCAD and MCP. On the optimization side, we show that a simple adaptation of composite gradient descent may be used to compute a global optimum up to the statistical precision stat in log(1/ stat ) iterations, the fastest possible rate for any ﬁrst-order method. We provide simulations to illustrate the sharpness of our theoretical predictions. 1

3 0.12759776 196 nips-2013-Modeling Overlapping Communities with Node Popularities

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

4 0.1140312 91 nips-2013-Dirty Statistical Models

Author: Eunho Yang, Pradeep Ravikumar

Abstract: We provide a uniﬁed framework for the high-dimensional analysis of “superposition-structured” or “dirty” statistical models: where the model parameters are a superposition of structurally constrained parameters. We allow for any number and types of structures, and any statistical model. We consider the general class of M -estimators that minimize the sum of any loss function, and an instance of what we call a “hybrid” regularization, that is the inﬁmal convolution of weighted regularization functions, one for each structural component. We provide corollaries showcasing our uniﬁed framework for varied statistical models such as linear regression, multiple regression and principal component analysis, over varied superposition structures. 1

5 0.09718968 7 nips-2013-A Gang of Bandits

Author: Nicolò Cesa-Bianchi, Claudio Gentile, Giovanni Zappella

Abstract: Multi-armed bandit problems formalize the exploration-exploitation trade-offs arising in several industrially relevant applications, such as online advertisement and, more generally, recommendation systems. In many cases, however, these applications have a strong social component, whose integration in the bandit algorithm could lead to a dramatic performance increase. For instance, content may be served to a group of users by taking advantage of an underlying network of social relationships among them. In this paper, we introduce novel algorithmic approaches to the solution of such networked bandit problems. More speciﬁcally, we design and analyze a global recommendation strategy which allocates a bandit algorithm to each network node (user) and allows it to “share” signals (contexts and payoffs) with the neghboring nodes. We then derive two more scalable variants of this strategy based on different ways of clustering the graph nodes. We experimentally compare the algorithm and its variants to state-of-the-art methods for contextual bandits that do not use the relational information. Our experiments, carried out on synthetic and real-world datasets, show a consistent increase in prediction performance obtained by exploiting the network structure. 1

6 0.092044488 66 nips-2013-Computing the Stationary Distribution Locally

7 0.085333288 206 nips-2013-Near-Optimal Entrywise Sampling for Data Matrices

8 0.085097976 289 nips-2013-Scalable kernels for graphs with continuous attributes

9 0.085097097 213 nips-2013-Nonparametric Multi-group Membership Model for Dynamic Networks

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

11 0.076325484 116 nips-2013-Fantope Projection and Selection: A near-optimal convex relaxation of sparse PCA

12 0.074150681 63 nips-2013-Cluster Trees on Manifolds

13 0.073604621 259 nips-2013-Provable Subspace Clustering: When LRR meets SSC

14 0.073012836 242 nips-2013-PAC-Bayes-Empirical-Bernstein Inequality

15 0.072715044 158 nips-2013-Learning Multiple Models via Regularized Weighting

16 0.072608382 192 nips-2013-Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation

17 0.072156861 359 nips-2013-Σ-Optimality for Active Learning on Gaussian Random Fields

18 0.072108425 146 nips-2013-Large Scale Distributed Sparse Precision Estimation

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

20 0.066088676 73 nips-2013-Convex Relaxations for Permutation Problems

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.18), (1, 0.071), (2, 0.043), (3, 0.043), (4, 0.032), (5, 0.071), (6, 0.036), (7, -0.059), (8, -0.052), (9, 0.036), (10, 0.074), (11, -0.003), (12, 0.192), (13, -0.03), (14, 0.0), (15, -0.006), (16, -0.004), (17, 0.027), (18, -0.002), (19, -0.033), (20, 0.132), (21, -0.048), (22, 0.007), (23, -0.094), (24, -0.022), (25, -0.022), (26, -0.03), (27, 0.049), (28, -0.047), (29, -0.074), (30, -0.085), (31, -0.051), (32, 0.053), (33, -0.084), (34, -0.055), (35, 0.079), (36, -0.026), (37, -0.027), (38, 0.068), (39, -0.011), (40, 0.069), (41, 0.009), (42, 0.056), (43, 0.061), (44, -0.004), (45, 0.018), (46, 0.002), (47, -0.011), (48, 0.059), (49, -0.065)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96333587 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

Author: Tai Qin, Karl Rohe

2 0.65948069 316 nips-2013-Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

Author: Edoardo M. Airoldi, Thiago B. Costa, Stanley H. Chan

Abstract: Non-parametric approaches for analyzing network data based on exchangeable graph models (ExGM) have recently gained interest. The key object that deﬁnes an ExGM is often referred to as a graphon. This non-parametric perspective on network modeling poses challenging questions on how to make inference on the graphon underlying observed network data. In this paper, we propose a computationally efﬁcient procedure to estimate a graphon from a set of observed networks generated from it. This procedure is based on a stochastic blockmodel approximation (SBA) of the graphon. We show that, by approximating the graphon with a stochastic block model, the graphon can be consistently estimated, that is, the estimation error vanishes as the size of the graph approaches inﬁnity.

3 0.63836879 196 nips-2013-Modeling Overlapping Communities with Node Popularities

Author: Prem Gopalan, Chong Wang, David Blei

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

Author: Myunghwan Kim, Jure Leskovec

Abstract: unkown-abstract

5 0.59162986 7 nips-2013-A Gang of Bandits

Author: Nicolò Cesa-Bianchi, Claudio Gentile, Giovanni Zappella

6 0.58649647 288 nips-2013-Scalable Influence Estimation in Continuous-Time Diffusion Networks

7 0.58033413 151 nips-2013-Learning Chordal Markov Networks by Constraint Satisfaction

8 0.57380229 104 nips-2013-Efficient Online Inference for Bayesian Nonparametric Relational Models

9 0.55018866 35 nips-2013-Analyzing the Harmonic Structure in Graph-Based Learning

10 0.54553074 259 nips-2013-Provable Subspace Clustering: When LRR meets SSC

11 0.54311299 182 nips-2013-Manifold-based Similarity Adaptation for Label Propagation

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

13 0.54033822 94 nips-2013-Distributed $k$-means and $k$-median Clustering on General Topologies

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

15 0.52561122 359 nips-2013-Σ-Optimality for Active Learning on Gaussian Random Fields

16 0.52348274 66 nips-2013-Computing the Stationary Distribution Locally

17 0.5168528 154 nips-2013-Learning Gaussian Graphical Models with Observed or Latent FVSs

18 0.50913388 47 nips-2013-Bayesian Hierarchical Community Discovery

19 0.50857198 207 nips-2013-Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic

20 0.5051018 58 nips-2013-Binary to Bushy: Bayesian Hierarchical Clustering with the Beta Coalescent

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(16, 0.037), (33, 0.111), (34, 0.07), (41, 0.023), (49, 0.012), (56, 0.083), (70, 0.023), (85, 0.478), (89, 0.027), (93, 0.041)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.88410288 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

Author: Tai Qin, Karl Rohe

2 0.84856713 7 nips-2013-A Gang of Bandits

Author: Nicolò Cesa-Bianchi, Claudio Gentile, Giovanni Zappella

3 0.79202259 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

4 0.76670825 332 nips-2013-Tracking Time-varying Graphical Structure

Author: Erich Kummerfeld, David Danks

Abstract: Structure learning algorithms for graphical models have focused almost exclusively on stable environments in which the underlying generative process does not change; that is, they assume that the generating model is globally stationary. In real-world environments, however, such changes often occur without warning or signal. Real-world data often come from generating models that are only locally stationary. In this paper, we present LoSST, a novel, heuristic structure learning algorithm that tracks changes in graphical model structure or parameters in a dynamic, real-time manner. We show by simulation that the algorithm performs comparably to batch-mode learning when the generating graphical structure is globally stationary, and signiﬁcantly better when it is only locally stationary. 1

5 0.74898928 140 nips-2013-Improved and Generalized Upper Bounds on the Complexity of Policy Iteration

Author: Bruno Scherrer

Abstract: Given a Markov Decision Process (MDP) with n states and m actions per state, we study the number of iterations needed by Policy Iteration (PI) algorithms to converge to the optimal “-discounted optimal policy. We consider two variations of PI: Howard’s PI that changes the actions in all states with a positive advantage, and Simplex-PI that only changes the action in the state with maximal Ï advantage. We show that Howard’s PI terminates 1 2Ì 1 1 22 1 1 nm 1 after at most n(m ≠ 1) 1≠“ log 1≠“ = O 1≠“ log 1≠“ iterations, improving by a factor O(log 1 a result by [3], while Simplex-PI terminates n) 1 22 1 2 1 22 2 1 1 2 after at most n (m ≠ 1) 1 + 1≠“ log 1≠“ = O n m log 1≠“ 1≠“ iterations, improving by a factor O(log n) a result by [11]. Under some structural assumptions of the MDP, we then consider bounds that are independent of the discount factor “: given a measure of the maximal transient time ·t and the maximal time ·r to revisit states in recurrent classes under all policies, we show that Simplex-PI terminates after at most n2 (m≠ # $ 1) (Á·r log(n·r )Ë + Á·r log(n·t )Ë) (m ≠ 1)Án·t log(n·t )Ë + Án·t log(n2 ·t )Ë = !

6 0.6370753 89 nips-2013-Dimension-Free Exponentiated Gradient

7 0.6198985 196 nips-2013-Modeling Overlapping Communities with Node Popularities

8 0.6197682 206 nips-2013-Near-Optimal Entrywise Sampling for Data Matrices

9 0.58726513 232 nips-2013-Online PCA for Contaminated Data

10 0.57896513 104 nips-2013-Efficient Online Inference for Bayesian Nonparametric Relational Models

11 0.57042778 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints

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

13 0.54493546 125 nips-2013-From Bandits to Experts: A Tale of Domination and Independence

14 0.51603764 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

15 0.51041996 189 nips-2013-Message Passing Inference with Chemical Reaction Networks

16 0.5061202 213 nips-2013-Nonparametric Multi-group Membership Model for Dynamic Networks

17 0.50207746 25 nips-2013-Adaptive Anonymity via $b$-Matching

18 0.50045758 316 nips-2013-Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

19 0.50029606 2 nips-2013-(Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings

20 0.50008345 35 nips-2013-Analyzing the Harmonic Structure in Graph-Based Learning