nips nips2013 nips2013-213 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Myunghwan Kim, Jure Leskovec
Abstract: unkown-abstract
Reference: text
sentIndex sentText sentNum sentScore
1 Here we build on the intuition that changes in the network structure are driven by dynamics at the level of groups of nodes. [sent-6, score-0.552]
2 Our model contains three main components: We model the birth and death of individual groups with respect to the dynamics of the network structure via a distance dependent Indian Buffet Process. [sent-8, score-0.876]
3 We capture the evolution of individual node group memberships via a Factorial Hidden Markov model. [sent-9, score-0.714]
4 We demonstrate our model’s capability of identifying the dynamics of latent groups in a number of different types of network data. [sent-11, score-0.634]
5 Experimental results show that our model provides improved predictive performance over existing dynamic network models on future network forecasting and missing link prediction. [sent-12, score-0.786]
6 A fundamental problem in the analysis of such dynamic network data is to extract a summary of the common structure and the dynamics of the underlying relations between entities. [sent-15, score-0.438]
7 They allow us to predict missing relationships [20, 21, 23], recommend potential new relations [2], identify clusters and groups of nodes [1, 29], forecast future links [4, 9, 11, 24], and even predict group growth and longevity [15]. [sent-17, score-0.885]
8 Here we present a new approach to modeling network dynamics by considering time-evolving interactions between groups of nodes as well as the arrival and departure dynamics of individual nodes to these groups. [sent-18, score-0.803]
9 We develop a dynamic network model, Dynamic Multi-group Membership Graph Model, that identifies the birth and death of individual groups as well as the dynamics of node joining and leaving groups in order to explain changes in the underlying network linking structure. [sent-19, score-1.684]
10 Our nonparametric model considers an infinite number of latent groups, where each node can belong to multiple groups simultaneously. [sent-20, score-0.568]
11 We capture the evolution of individual node group memberships via a Factorial Hidden Markov model. [sent-21, score-0.714]
12 However, in contrast to recent works on dynamic network modeling [4, 5, 11, 12, 14], we explicitly model the birth and death dynamics of individual groups by using a distance-dependent Indian Buffet Process [7]. [sent-22, score-1.025]
13 Under our model only active/alive groups influence relationships in a network at a given time. [sent-23, score-0.443]
14 Further innovation of our approach is that we not only model relations between the members of the same group but also account for links between members and non-members. [sent-24, score-0.642]
15 By explicitly modeling group lifespan and group connectivity structure we achieve greater modeling flexibility, which leads to improved performance on link prediction and network forecasting tasks as well as to increased interpretability of obtained results. [sent-25, score-1.096]
16 So, each Y (t) is a N × N binary matrix where Yij = 1 if a link from node i to j exists (t) at time t and Yij = 0 otherwise. [sent-34, score-0.4]
17 Each node i of the network is associated with a number of latent binary features that govern the interaction dynamics with other nodes of the network. [sent-35, score-0.578]
18 We denote the binary value of feature k of (t) node i at time t by zik ∈ {0, 1}. [sent-36, score-0.435]
19 Such latent features can be viewed as assigning nodes to multiple overlapping, latent clusters or groups [1, 21]. [sent-37, score-0.528]
20 In our work, we interpret these latent features as memberships to latent groups such as social communities of people with the same interests or hobbies. [sent-38, score-0.798]
21 We allow each node to belong to multiple groups simultaneously. [sent-39, score-0.486]
22 This is in contrast to mixedmembership models where the distribution over individual node’s group memberships is modeled using a multinomial distribution [1, 5, 12]. [sent-41, score-0.548]
23 , multinomial distribution over group memberships) essentially assume that by increasing the amount of node’s membership to some group k, the same node’s membership to some other group k ′ has to decrease (due to the condition that the probabilities normalize to 1). [sent-45, score-1.426]
24 Furthermore, we consider a nonparametric model of groups which does not restrict the number of latent groups ahead of time. [sent-47, score-0.668]
25 Hence, our model adaptively learns the appropriate number of latent groups for a given network at a given time. [sent-48, score-0.525]
26 In dynamic network models, one also specifies a process by which nodes dynamically join and leave groups. [sent-49, score-0.412]
27 We assume that each node i can join or leave a given group k according to a Markov model. [sent-50, score-0.542]
28 However, since each node can join multiple groups independently, we naturally consider factorial hidden Markov models (FHMM) [8], where latent group membership of each node independently (t) evolves over time. [sent-51, score-1.369]
29 To be concrete, each membership zik evolves through a 2-by-2 Markov transition (t) (t) (t) (t−1) probability matrix Qk where each entry Qk [r, s] corresponds to P (zik = s|zik = r), where r, s ∈ {0 = non-member, 1 = member}. [sent-52, score-0.481]
30 (t) Now, given node group memberships zik at time t one also needs to specify the process of link generation. [sent-53, score-1.217]
31 Links of the network realize according to a link function f (·). [sent-54, score-0.384]
32 A link from node i to (t) (t) node j at time t occurs with probability determined by the link function f (zi· , zj· ). [sent-55, score-0.8]
33 In our model, we develop a link function that not only accounts for links between group members but also models links between the members and non-members of a given group. [sent-56, score-0.944]
34 In our model, we pay close attention to the three processes governing network dynamics: (1) birth and death dynamics of individual groups, (2) evolution of memberships of nodes to groups, and (3) the structure of network interactions between group members as well as non-members. [sent-58, score-1.442]
35 Links of the network are influenced not only by nodes changing memberships to groups but also by the birth and death of groups themselves. [sent-61, score-1.345]
36 However, without explicitly modeling group birth and death there exists ambiguity 2 between group membership change and the birth/death of groups. [sent-63, score-1.204]
37 For example, consider two disjoint groups k and l such that their lifetimes and members do not overlap. [sent-64, score-0.383]
38 In other words, group l is born after group k dies out. [sent-65, score-0.805]
39 However, if group birth and death dynamics is not explicitly modeled, then the model could interpret that the two groups correspond to a single latent group where all the members of k leave the group before the members of l join the group. [sent-66, score-2.032]
40 To resolve this ambiguity we devise an explicit model of birth/death dynamics of groups by introducing a notion of active groups. [sent-67, score-0.498]
41 Under our model, a group can be in one of two states: it can be either active (alive) or inactive (not yet born or dead). [sent-68, score-0.576]
42 However, once a group becomes inactive, it can never be active again. [sent-69, score-0.43]
43 We regard each time step t as a ‘customer’ that samples a set of active groups Kt . [sent-75, score-0.389]
44 To account for death of groups we then consider that each active group at time t − 1 can become inactive at the next time step t with probability γ. [sent-79, score-0.954]
45 On the other hand, P oisson(γλ) new groups are also born at time t. [sent-80, score-0.383]
46 Thus, at each time currently active groups can die, while new ones can also be born. [sent-81, score-0.389]
47 For instance, there will be almost no newborn or dead groups if γ ≈ 1, while there would be no temporal group coherence and practically all the groups would die between consecutive time steps if γ = 0. [sent-83, score-0.98]
48 Black circles indicate active groups and white circles denote inactive (not yet born or dead) groups. [sent-85, score-0.593]
49 Without our group activity model, Group 3 could have been reused with a completely new set of members and Group 4 would have never been born. [sent-88, score-0.424]
50 Formally, we denote the number of active groups at time t by Kt = |Kt |. [sent-90, score-0.389]
51 For convenience, we also define a set (t) (t′ ) + of newly active groups at time t be Kt = {k|Wk = 1, Wk + + = 0 ∀t′ < t} and Kt = |Kt |. [sent-92, score-0.389]
52 Putting it all together we can now fully describe the process of group birth/death as follows: P oisson (λ) , for t = 1 P oisson (γλ) , for t > 1 (t−1) Bernoulli(1 − γ) if Wk =1 t−1 + ∼ 1, if t′ =1 Kt′ < k ≤ 0, otherwise . [sent-93, score-0.492]
53 + Kt ∼ (t) Wk t t′ =1 + Kt′ (1) Note that under this model an infinite number of active groups can exist. [sent-94, score-0.389]
54 This means our model automatically determines the right number of active groups and each node can belong to many groups simultaneously. [sent-95, score-0.875]
55 We now proceed by describing the model of node group membership dynamics. [sent-96, score-0.712]
56 We capture the dynamics of nodes joining and leaving groups by assuming that latent node group memberships form a Markov chain. [sent-98, score-1.269]
57 Thus, the transition of node’s i membership to active group k can be defined as follows: (t) (t−1) 1−zik (t) ak , bk ∼ Beta(α, β), zik ∼ Wk · Bernoulli ak (t−1) zik (1 − bk ) . [sent-100, score-1.382]
58 3 (2) (a) Group activity model (b) Link function model Figure 1: (a) Birth and death of groups: Black circles represent active and white circles represent inactive (t) (unborn or dead) groups. [sent-102, score-0.385]
59 (b) Link function: zi denotes binary node group memberships. [sent-104, score-0.5]
60 Relationship between node group memberships and links of the network. [sent-107, score-0.812]
61 Last, we describe the part of the model that establishes the connection between node’s memberships to groups and the links of the network. [sent-108, score-0.605]
62 We achieve this by defining a link function f (i, j), which for given a pair of (t) nodes i, j determines their interaction probability pij based on their group memberships. [sent-109, score-0.732]
63 We build on the Multiplicative Attribute Graph model [16, 18], where each group k is associated with a link affinity matrix Θk ∈ R2×2 . [sent-110, score-0.568]
64 While traditionally link affinities were considered to be probabilities, we relax this assumption by allowing affinities to be arbitrary real numbers and then combine them through a logistic function to obtain a final link probability. [sent-112, score-0.468]
65 Given group memberships zik and zjk of nodes i and j at (t) (t) time t the binary indicators “select” an entry Θk [zik , zjk ] of matrix Θk . [sent-114, score-0.99]
66 This way linking tendency from node i to node j is reflected based on their membership to group k. [sent-115, score-0.928]
67 We then determine the (t) overall link probability pij by combining the link affinities via a logistic function g(·)1 . [sent-116, score-0.561]
68 Thus, ∞ (t) (t) (t) (t) (t) (t) Θk [zik , zjk ] , Yij ∼ Bernoulli(pij ) pij = f (zi· , zj· ) = g ǫt + (3) k=1 where ǫt is a density parameter that reflects the varying link density of network over time. [sent-117, score-0.528]
69 Note that due to potentially infinite number of groups the sum of an infinite number of link affinities may not be tractable. [sent-118, score-0.527]
70 Group’s (t) (t) state Wk is determined by the dd-IBP process and each node-group membership zik is defined as the FHMM over active groups. [sent-123, score-0.577]
71 Then, the link between nodes i and j is determined based on the groups they belong to and the corresponding group link affinity matrices Θ. [sent-124, score-1.193]
72 Network Y depends on each node’s group memberships Z and active groups W . [sent-129, score-0.937]
73 Related to our work are dynamic mixed-membership models where a node is probabilistically allocated to a set of latent features. [sent-133, score-0.397]
74 However, the critical difference here is that our model uses multimemberships where node’s membership to one group does not limit its membership to other groups. [sent-135, score-0.758]
75 DRIFT uses the infinite factorial HMM [6], while LFP adds “social propagation” to the Markov processes so that network links of each node at a given time directly influence group memberships of the corresponding node at the next time. [sent-138, score-1.202]
76 Compared to these models, we uniquely incorporate the model of group birth and death and present a novel and powerful linking function. [sent-139, score-0.708]
77 More specifically, there are five types (t) of variables that we need to sample: node group memberships Z = {zik }, group states W = (t) {Wk }, group membership transitions Q = {Qk }, link affinities Θ = {Θk }, and density parameters ǫ = {ǫt }. [sent-141, score-1.828]
78 To sample node group membership zik , we use the forward-backward recursion algorithm [26]. [sent-145, score-0.981]
79 In our case, we only need to sample zik k k where Tk and Tk indicate the birth time and the death time of group k. [sent-148, score-0.927]
80 To update active groups, we use the Metropolis-Hastings algorithm with the following proposal distribution P (W → W ′ ): We add a new group, remove an existing group, or update the life time of an active group with the same probability 1/3. [sent-151, score-0.526]
81 When adding a new B D group k ′ we select the birth and death time of the group at random such that 1 ≤ Tk′ ≤ Tk′ ≤ T . [sent-152, score-0.992]
82 (t) For removing groups we randomly pick one of existing groups k ′′ and remove it by setting Wk′′ = 0 for all t. [sent-153, score-0.586]
83 Finally, to update the birth and death time of an existing group, we select an existing group and propose new birth and death time of the group at random. [sent-154, score-1.316]
84 Once node group memberships Z are determined, we update the entries of link affinity matrices Θk . [sent-160, score-0.948]
85 Because links Yij are generated independently given group memberships Z, the gradient with respect to Θk [x, y] can be computed by − 1 2 (t) (t) (t) (t) Y − pij 1{zik = x, zjk = y} . [sent-165, score-0.79]
86 Similarly, we can use the Beta conjugate prior for the group death process (i. [sent-173, score-0.509]
87 Each sample zik requires computation of (t) link probability pij for all j = i. [sent-179, score-0.596]
88 Since the expected number of active groups at each time is λ, (t) this requires O(λN 2 T ) computations of pij . [sent-180, score-0.482]
89 For quantitative evaluation, we perform missing link prediction as well as future network forecasting and show our model gives favorable performance when compared to current dynamic and static network models. [sent-189, score-0.786]
90 We also analyze the dynamics of groups in a dynamic social network of characters in a movie “The Lord of the Rings: The Two Towers. [sent-190, score-0.88]
91 Thus, for a given pair of nodes, the link probability at each time equals to the expected probability from the posterior distribution given network data. [sent-231, score-0.384]
92 For missing link prediction, we independently fit LFRM to each snapshot of dynamic networks. [sent-233, score-0.476]
93 To generate the datasets for the task of missing link prediction, we randomly hold out 20% of node pairs (i. [sent-244, score-0.459]
94 Each sample gives a link probability for a given missing entry, so the final link probability of a missing entry is computed by averaging the corresponding link probability over all the samples. [sent-248, score-0.82]
95 Intuitively this makes sense because due to the network sparsity we can obtain more information from the temporal trajectory of each link than from each snapshot of network. [sent-256, score-0.418]
96 Here we are given a dynamic network up to time Tobs and the goal is to predict the network at the next time Tobs + 1. [sent-268, score-0.449]
97 Dark areas in the plots correspond to a give node’s (y-axis) membership to each group over time (x-axis) . [sent-304, score-0.546]
98 Last, we also investigate groups identified by our model on a dynamic social network of characters in a movie, The Lord of the Rings: The Two Towers. [sent-311, score-0.74]
99 Based on the transcript of the movie we created a dynamic social network on 21 characters and T =5 time epochs, where we connect a pair of characters if they co-appear inside some time window. [sent-312, score-0.531]
100 The life and death of online groups: Predicting group growth and longevity. [sent-437, score-0.509]
wordName wordTfidf (topN-words)
[('group', 0.334), ('groups', 0.293), ('zik', 0.269), ('dmmg', 0.252), ('link', 0.234), ('memberships', 0.214), ('membership', 0.212), ('death', 0.175), ('node', 0.166), ('network', 0.15), ('birth', 0.149), ('dynamic', 0.149), ('nities', 0.139), ('infocom', 0.115), ('lfrm', 0.111), ('dynamics', 0.109), ('links', 0.098), ('active', 0.096), ('social', 0.095), ('lord', 0.094), ('testll', 0.094), ('pij', 0.093), ('auc', 0.09), ('members', 0.09), ('born', 0.09), ('dblp', 0.084), ('latent', 0.082), ('merry', 0.079), ('oisson', 0.079), ('pippin', 0.079), ('tobs', 0.079), ('kt', 0.076), ('af', 0.075), ('factorial', 0.074), ('relational', 0.073), ('nodes', 0.071), ('lfp', 0.069), ('drift', 0.068), ('aragorn', 0.063), ('faramir', 0.063), ('frodo', 0.063), ('gimli', 0.063), ('gollum', 0.063), ('legolas', 0.063), ('rings', 0.063), ('saruman', 0.063), ('dead', 0.06), ('wk', 0.059), ('missing', 0.059), ('inactive', 0.056), ('bk', 0.053), ('characters', 0.053), ('qk', 0.052), ('zjk', 0.051), ('linking', 0.05), ('ak', 0.048), ('arwen', 0.047), ('dies', 0.047), ('elrond', 0.047), ('eomer', 0.047), ('eowyn', 0.047), ('galadriel', 0.047), ('gandalf', 0.047), ('ght', 0.047), ('grima', 0.047), ('haldir', 0.047), ('hama', 0.047), ('madril', 0.047), ('theoden', 0.047), ('forecasting', 0.044), ('join', 0.042), ('sam', 0.041), ('beta', 0.04), ('markov', 0.04), ('bernoulli', 0.038), ('networks', 0.037), ('yij', 0.037), ('buffet', 0.036), ('nity', 0.036), ('snapshot', 0.034), ('tk', 0.033), ('indian', 0.033), ('people', 0.032), ('alive', 0.031), ('fhmm', 0.031), ('heaukulani', 0.031), ('rohan', 0.031), ('movie', 0.031), ('kim', 0.031), ('relations', 0.03), ('naive', 0.03), ('circles', 0.029), ('attribute', 0.029), ('nips', 0.029), ('mcmc', 0.029), ('fu', 0.029), ('graph', 0.029), ('zj', 0.029), ('evolving', 0.027), ('belong', 0.027)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000008 213 nips-2013-Nonparametric Multi-group Membership Model for Dynamic Networks
Author: Myunghwan Kim, Jure Leskovec
Abstract: unkown-abstract
2 0.16838242 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 significantly better than the MMSB. 1
3 0.14556846 277 nips-2013-Restricting exchangeable nonparametric distributions
Author: Sinead A. Williamson, Steve N. MacEachern, Eric Xing
Abstract: Distributions over matrices with exchangeable rows and infinitely many columns are useful in constructing nonparametric latent variable models. However, the distribution implied by such models over the number of features exhibited by each data point may be poorly-suited for many modeling tasks. In this paper, we propose a class of exchangeable nonparametric priors obtained by restricting the domain of existing models. Such models allow us to specify the distribution over the number of features per data point, and can achieve better performance on data sets where the number of features is not well-modeled by the original distribution. 1
4 0.10261957 303 nips-2013-Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis
Author: Nikhil Rao, Christopher Cox, Rob Nowak, Timothy T. Rogers
Abstract: Multitask learning can be effective when features useful in one task are also useful for other tasks, and the group lasso is a standard method for selecting a common subset of features. In this paper, we are interested in a less restrictive form of multitask learning, wherein (1) the available features can be organized into subsets according to a notion of similarity and (2) features useful in one task are similar, but not necessarily identical, to the features best suited for other tasks. The main contribution of this paper is a new procedure called Sparse Overlapping Sets (SOS) lasso, a convex optimization that automatically selects similar features for related learning tasks. Error bounds are derived for SOSlasso and its consistency is established for squared error loss. In particular, SOSlasso is motivated by multisubject fMRI studies in which functional activity is classified using brain voxels as features. Experiments with real and synthetic data demonstrate the advantages of SOSlasso compared to the lasso and group lasso. 1
5 0.096043907 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 efficient structured mean field 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 significantly 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
6 0.093021743 46 nips-2013-Bayesian Estimation of Latently-grouped Parameters in Undirected Graphical Models
7 0.092320211 100 nips-2013-Dynamic Clustering via Asymptotics of the Dependent Dirichlet Process Mixture
8 0.085097097 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
9 0.084725291 7 nips-2013-A Gang of Bandits
10 0.084512152 66 nips-2013-Computing the Stationary Distribution Locally
11 0.082484581 288 nips-2013-Scalable Influence Estimation in Continuous-Time Diffusion Networks
12 0.07723555 149 nips-2013-Latent Structured Active Learning
13 0.075079963 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching
14 0.071747683 13 nips-2013-A Scalable Approach to Probabilistic Latent Space Inference of Large-Scale Networks
15 0.071018539 267 nips-2013-Recurrent networks of coupled Winner-Take-All oscillators for solving constraint satisfaction problems
16 0.070090987 359 nips-2013-Σ-Optimality for Active Learning on Gaussian Random Fields
17 0.06949091 48 nips-2013-Bayesian Inference and Learning in Gaussian Process State-Space Models with Particle MCMC
18 0.069076128 228 nips-2013-Online Learning of Dynamic Parameters in Social Networks
19 0.068572409 75 nips-2013-Convex Two-Layer Modeling
20 0.067170501 206 nips-2013-Near-Optimal Entrywise Sampling for Data Matrices
topicId topicWeight
[(0, 0.168), (1, 0.052), (2, -0.061), (3, 0.004), (4, 0.015), (5, 0.036), (6, 0.091), (7, -0.03), (8, 0.086), (9, -0.009), (10, 0.043), (11, -0.056), (12, 0.128), (13, -0.061), (14, -0.086), (15, -0.044), (16, -0.017), (17, 0.041), (18, 0.018), (19, -0.113), (20, 0.141), (21, -0.091), (22, 0.016), (23, -0.088), (24, 0.146), (25, 0.003), (26, 0.029), (27, 0.027), (28, 0.009), (29, -0.02), (30, -0.071), (31, -0.065), (32, 0.057), (33, -0.158), (34, -0.146), (35, -0.02), (36, -0.089), (37, 0.072), (38, 0.058), (39, 0.068), (40, -0.031), (41, 0.012), (42, 0.014), (43, -0.018), (44, 0.02), (45, -0.069), (46, 0.093), (47, -0.05), (48, 0.099), (49, -0.06)]
simIndex simValue paperId paperTitle
same-paper 1 0.9660272 213 nips-2013-Nonparametric Multi-group Membership Model for Dynamic Networks
Author: Myunghwan Kim, Jure Leskovec
Abstract: unkown-abstract
2 0.74500293 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 significantly better than the MMSB. 1
3 0.74495536 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 efficient structured mean field 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 significantly 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
4 0.69218111 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 efficient 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
5 0.60327929 288 nips-2013-Scalable Influence Estimation in Continuous-Time Diffusion Networks
Author: Nan Du, Le Song, Manuel Gomez-Rodriguez, Hongyuan Zha
Abstract: If a piece of information is released from a media site, can we predict whether it may spread to one million web pages, in a month ? This influence estimation problem is very challenging since both the time-sensitive nature of the task and the requirement of scalability need to be addressed simultaneously. In this paper, we propose a randomized algorithm for influence estimation in continuous-time diffusion networks. Our algorithm can estimate the influence of every node in a network with |V| nodes and |E| edges to an accuracy of using n = O(1/ 2 ) randomizations and up to logarithmic factors O(n|E|+n|V|) computations. When used as a subroutine in a greedy influence maximization approach, our proposed algorithm is guaranteed to find a set of C nodes with the influence of at least (1 − 1/e) OPT −2C , where OPT is the optimal value. Experiments on both synthetic and real-world data show that the proposed algorithm can easily scale up to networks of millions of nodes while significantly improves over previous state-of-the-arts in terms of the accuracy of the estimated influence and the quality of the selected nodes in maximizing the influence. 1
6 0.57520944 272 nips-2013-Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
7 0.51850557 3 nips-2013-A* Lasso for Learning a Sparse Bayesian Network Structure for Continuous Variables
8 0.51666039 47 nips-2013-Bayesian Hierarchical Community Discovery
9 0.51271683 92 nips-2013-Discovering Hidden Variables in Noisy-Or Networks using Quartet Tests
10 0.5008502 294 nips-2013-Similarity Component Analysis
11 0.49657914 316 nips-2013-Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
12 0.48901689 277 nips-2013-Restricting exchangeable nonparametric distributions
13 0.47112387 343 nips-2013-Unsupervised Structure Learning of Stochastic And-Or Grammars
14 0.46301621 151 nips-2013-Learning Chordal Markov Networks by Constraint Satisfaction
15 0.44530386 61 nips-2013-Capacity of strong attractor patterns to model behavioural and cognitive prototypes
16 0.4399398 7 nips-2013-A Gang of Bandits
17 0.43834478 58 nips-2013-Binary to Bushy: Bayesian Hierarchical Clustering with the Beta Coalescent
18 0.42852825 115 nips-2013-Factorized Asymptotic Bayesian Inference for Latent Feature Models
19 0.4224346 66 nips-2013-Computing the Stationary Distribution Locally
20 0.41796583 359 nips-2013-Σ-Optimality for Active Learning on Gaussian Random Fields
topicId topicWeight
[(2, 0.027), (16, 0.028), (33, 0.126), (34, 0.081), (41, 0.021), (49, 0.071), (56, 0.074), (59, 0.274), (70, 0.05), (85, 0.081), (89, 0.018), (93, 0.024), (95, 0.025)]
simIndex simValue paperId paperTitle
same-paper 1 0.76305962 213 nips-2013-Nonparametric Multi-group Membership Model for Dynamic Networks
Author: Myunghwan Kim, Jure Leskovec
Abstract: unkown-abstract
2 0.7595458 134 nips-2013-Graphical Models for Inference with Missing Data
Author: Karthika Mohan, Judea Pearl, Jin Tian
Abstract: We address the problem of recoverability i.e. deciding whether there exists a consistent estimator of a given relation Q, when data are missing not at random. We employ a formal representation called ‘Missingness Graphs’ to explicitly portray the causal mechanisms responsible for missingness and to encode dependencies between these mechanisms and the variables being measured. Using this representation, we derive conditions that the graph should satisfy to ensure recoverability and devise algorithms to detect the presence of these conditions in the graph. 1
3 0.66265815 40 nips-2013-Approximate Inference in Continuous Determinantal Processes
Author: Raja Hafiz Affandi, Emily Fox, Ben Taskar
Abstract: Determinantal point processes (DPPs) are random point processes well-suited for modeling repulsion. In machine learning, the focus of DPP-based models has been on diverse subset selection from a discrete and finite base set. This discrete setting admits an efficient sampling algorithm based on the eigendecomposition of the defining kernel matrix. Recently, there has been growing interest in using DPPs defined on continuous spaces. While the discrete-DPP sampler extends formally to the continuous case, computationally, the steps required are not tractable in general. In this paper, we present two efficient DPP sampling schemes that apply to a wide range of kernel functions: one based on low rank approximations via Nystr¨ m o and random Fourier feature techniques and another based on Gibbs sampling. We demonstrate the utility of continuous DPPs in repulsive mixture modeling and synthesizing human poses spanning activity spaces. 1
4 0.58077031 330 nips-2013-Thompson Sampling for 1-Dimensional Exponential Family Bandits
Author: Nathaniel Korda, Emilie Kaufmann, Remi Munos
Abstract: Thompson Sampling has been demonstrated in many complex bandit models, however the theoretical guarantees available for the parametric multi-armed bandit are still limited to the Bernoulli case. Here we extend them by proving asymptotic optimality of the algorithm using the Jeffreys prior for 1-dimensional exponential family bandits. Our proof builds on previous work, but also makes extensive use of closed forms for Kullback-Leibler divergence and Fisher information (through the Jeffreys prior) available in an exponential family. This allow us to give a finite time exponential concentration inequality for posterior distributions on exponential families that may be of interest in its own right. Moreover our analysis covers some distributions for which no optimistic algorithm has yet been proposed, including heavy-tailed exponential families. 1
5 0.57306725 262 nips-2013-Real-Time Inference for a Gamma Process Model of Neural Spiking
Author: David Carlson, Vinayak Rao, Joshua T. Vogelstein, Lawrence Carin
Abstract: With simultaneous measurements from ever increasing populations of neurons, there is a growing need for sophisticated tools to recover signals from individual neurons. In electrophysiology experiments, this classically proceeds in a two-step process: (i) threshold the waveforms to detect putative spikes and (ii) cluster the waveforms into single units (neurons). We extend previous Bayesian nonparametric models of neural spiking to jointly detect and cluster neurons using a Gamma process model. Importantly, we develop an online approximate inference scheme enabling real-time analysis, with performance exceeding the previous state-of-theart. Via exploratory data analysis—using data with partial ground truth as well as two novel data sets—we find several features of our model collectively contribute to our improved performance including: (i) accounting for colored noise, (ii) detecting overlapping spikes, (iii) tracking waveform dynamics, and (iv) using multiple channels. We hope to enable novel experiments simultaneously measuring many thousands of neurons and possibly adapting stimuli dynamically to probe ever deeper into the mysteries of the brain. 1
6 0.57254869 121 nips-2013-Firing rate predictions in optimal balanced networks
7 0.563546 104 nips-2013-Efficient Online Inference for Bayesian Nonparametric Relational Models
8 0.56258368 168 nips-2013-Learning to Pass Expectation Propagation Messages
9 0.56181383 196 nips-2013-Modeling Overlapping Communities with Node Popularities
10 0.56177974 303 nips-2013-Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis
11 0.56081396 221 nips-2013-On the Expressive Power of Restricted Boltzmann Machines
12 0.56047243 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints
13 0.55848724 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching
14 0.55766171 141 nips-2013-Inferring neural population dynamics from multiple partial recordings of the same neural circuit
15 0.55713177 304 nips-2013-Sparse nonnegative deconvolution for compressive calcium imaging: algorithms and phase transitions
16 0.55694437 49 nips-2013-Bayesian Inference and Online Experimental Design for Mapping Neural Microcircuits
17 0.55555218 173 nips-2013-Least Informative Dimensions
19 0.55397189 329 nips-2013-Third-Order Edge Statistics: Contour Continuation, Curvature, and Cortical Connections
20 0.55374783 64 nips-2013-Compete to Compute