nips nips2010 nips2010-190 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Seth Myers, Jure Leskovec
Abstract: In many real-world scenarios, it is nearly impossible to collect explicit social network data. In such cases, whole networks must be inferred from underlying observations. Here, we formulate the problem of inferring latent social networks based on network diffusion or disease propagation data. We consider contagions propagating over the edges of an unobserved social network, where we only observe the times when nodes became infected, but not who infected them. Given such node infection times, we then identify the optimal network that best explains the observed data. We present a maximum likelihood approach based on convex programming with a l1 -like penalty term that encourages sparsity. Experiments on real and synthetic data reveal that our method near-perfectly recovers the underlying network structure as well as the parameters of the contagion propagation model. Moreover, our approach scales well as it can infer optimal networks of thousands of nodes in a matter of minutes.
Reference: text
sentIndex sentText sentNum sentScore
1 edu Abstract In many real-world scenarios, it is nearly impossible to collect explicit social network data. [sent-5, score-0.353]
2 Here, we formulate the problem of inferring latent social networks based on network diffusion or disease propagation data. [sent-7, score-0.699]
3 We consider contagions propagating over the edges of an unobserved social network, where we only observe the times when nodes became infected, but not who infected them. [sent-8, score-0.985]
4 Given such node infection times, we then identify the optimal network that best explains the observed data. [sent-9, score-0.664]
5 Experiments on real and synthetic data reveal that our method near-perfectly recovers the underlying network structure as well as the parameters of the contagion propagation model. [sent-11, score-0.385]
6 As collecting such data is tedious and expensive, traditional social network studies typically involved a very limited number of people (usually less than 100). [sent-14, score-0.379]
7 The emergence of large scale social computing applications has made massive social network data [16] available, but there are important settings where network data is hard to obtain and thus the whole network must thus be inferred from the data. [sent-15, score-0.934]
8 Collecting social networks of such populations is near impossible, and thus whole networks have to be inferred from the observational data. [sent-17, score-0.409]
9 Even though inferring social networks has been attempted in the past, it usually assumes that the pairwise interaction data is already available [5]. [sent-18, score-0.358]
10 In this case, the problem of network inference reduces to deciding whether to include the interaction between a pair of nodes as an edge in the underlying network. [sent-19, score-0.369]
11 For example, inferring networks from pairwise interactions of cell-phone call [5] or email [4, 13] records simply reduces down to selecting the right threshold τ such that an edge (u, v) is included in the network if u and v interacted more than τ times in the dataset. [sent-20, score-0.521]
12 We address the problem of inferring the structure of unobserved social networks in a much more ambitious setting. [sent-22, score-0.39]
13 , disease, information, product adoption) spreads over the edges of the network, and all that we observe are the infection times of nodes, but not who infected whom i. [sent-25, score-1.01]
14 The goal then is to reconstruct the underlying social network along the edges of which the contagion diffused. [sent-28, score-0.565]
15 1 We think of a diffusion on a network as a process where neighboring nodes switch states from inactive to active. [sent-29, score-0.341]
16 Commonly, we only observe the times when particular nodes get “infected” but we do not observe who infected them. [sent-31, score-0.641]
17 Thus, we only observe the time when a blog gets “infected” but not where it got infected from. [sent-33, score-0.535]
18 Similarly, in disease spreading, we observe people getting sick without usually knowing who infected them [26]. [sent-34, score-0.568]
19 Thus, the question is, if we assume that the network is static over time, is it possible to reconstruct the unobserved social network over which diffusions took place? [sent-36, score-0.618]
20 We develop convex programming based approach for inferring the latent social networks from diffusion data. [sent-38, score-0.491]
21 We then write down the likelihood of observed diffusion data under a given network and diffusion model parameters. [sent-40, score-0.39]
22 Experiments reveal that we can near-perfectly recover the underlying network structure as well as the parameters of the propagation model. [sent-43, score-0.259]
23 Our work here is similar in a sense that we “regress” the infection times of a target node on infection times of other nodes. [sent-50, score-0.888]
24 The algorithm proposed (called NetInf) assumes that the weights of the edges in latent network are homogeneous, i. [sent-53, score-0.325]
25 all connected nodes in the network infect/influence their neighbors with the same probability. [sent-55, score-0.26]
26 2 Problem Formulation and the Proposed Method We now define the problem of inferring a latent social networks based on network diffusion data, where we only observe identities of infected nodes. [sent-58, score-1.153]
27 Thus, for each node we know the interval during which the node was infected, whereas the source of each node’s infection is unknown. [sent-59, score-0.659]
28 We assume only that an infected node was previously infected by some other previously infected node to which it is connected in the latent social network (which we are trying to infer). [sent-60, score-2.197]
29 We show that calculating the maximum likelihood estimator (MLE) of the latent network (under any of the above diffusion models) is equivalent to a convex problem that can be efficiently solved. [sent-62, score-0.342]
30 Each entry (i, j) of A models the conditional probability of infection transmission: Aij = P (node i infects node j | node i is infected). [sent-67, score-0.7]
31 2 The temporal properties of most types of cascades, especially disease spread, are governed by a transmission (or incubation) period. [sent-68, score-0.264]
32 The transmission time model w(t) specifies how long it takes for the infection to transmit from one node to another, and the recovery model r(t) models the time of how long a node is infected before it recovers. [sent-69, score-1.385]
33 Thus, whenever some node i, which was infected at time τi , infects another node j, the time separating two infection times is sampled from w(t), i. [sent-70, score-1.218]
34 , infection time of node j is τj = τi + t, where t is distributed by w(t). [sent-72, score-0.497]
35 Similarly, the duration of each node’s infection is sampled from r(t). [sent-73, score-0.335]
36 A cascade c is initiated by randomly selecting a node to become infected at time t = 0. [sent-75, score-0.777]
37 Specifically, if i becomes infected and j is susceptible, then j will become infected with probability Aij . [sent-78, score-0.98]
38 Once it has been determined which of i’s neighbors will be infected, the infection time of each newly infected neighbor will be the sum of τi and an interval of time sampled from w(t). [sent-79, score-0.825]
39 The transmission time for each new infection is sampled independently from w(t). [sent-80, score-0.571]
40 In the SIS model, node i will become susceptible to infection again at time τi + ri . [sent-82, score-0.551]
41 On the other hand, under the SIR model, node i will recover and can never be infected again. [sent-83, score-0.652]
42 Our work here mainly considers the SI model, where nodes remain infected forever, i. [sent-84, score-0.565]
43 For each cascade c, we then observe the node infection times τic as well as the duration of infection, but the source of each node’s infection remains hidden. [sent-88, score-1.009]
44 The goal then is to, based on observed set of cascade infection times D, infer the weighted adjacency matrix A, where Aij models the edge transmission probability. [sent-89, score-0.867]
45 For each cascade c, let τic be the time of infection for node i. [sent-92, score-0.622]
46 Note that if node i did not get infected in cascade c, then τic = ∞. [sent-93, score-0.777]
47 Also, let Xc (t) denote the set of all nodes that are in an infected state at time t in cascade c. [sent-94, score-0.69]
48 We know the infection of each node was the result of an unknown, previously infected node to which it is connected, so the component of the likelihood function for each infection will be dependent on all previously infected nodes. [sent-95, score-1.999]
49 Specifically, the likelihood function for a fixed given A is c∈D = c∈D P (i infected at τic |Xc (τic )) · L(A; D) = c i;τi <∞ c i;τi <∞ 1 − c i;τi =∞ P (i never infected|Xc (t) ∀ t) j;τj ≤τi c (1 − w(τic − τj )Aji ) · (1 − Aji ) . [sent-96, score-0.515]
50 First, for every node i that got infected at time τic we compute the probability that at least one other previously infected node could have infected it. [sent-99, score-1.815]
51 For every non-infected node, we compute probability that no other node ever infected it. [sent-100, score-0.652]
52 Moreover, in the case of the SIS model each node can be infected multiple times during a single cascade, so there will be multiple observed values for each τic and the likelihood function would have to include each infection time in the product sum. [sent-102, score-1.04]
53 We can, however, break this problem into N independent subproblems, each with only N − 1 variables by observing that the incoming edges to a node can be inferred independently of the incoming edges of any other node. [sent-107, score-0.556]
54 3 Let node i be the current node of interest for which we would like to infer its incoming connections. [sent-109, score-0.388]
55 Lastly, the number of variables can further be reduced by observing that if node j is never infected in the same cascade as node i, then the MLE of Aji = 0, and Aji can thus be excluded from the set of variables. [sent-111, score-0.939]
56 This dramatically reduces the number of variables as in practice the true A does not induce large cascades, causing the cascades to be sparse in the number of nodes they infect [14, 17]. [sent-112, score-0.245]
57 In general, social networks are sparse in a sense that on average nodes are connected to a constant number rather than a constant fraction of other nodes in the network. [sent-129, score-0.435]
58 We break the network inference down into a series of subproblems corresponding to the inference of the inbound edges of each node. [sent-136, score-0.356]
59 The presence of the l1 penalty function makes the method extremely effective at predicting the presence of edges in the network, but it has the effect of distorting the estimated edge transmission probabilities. [sent-138, score-0.481]
60 Of the resulting solution, the edge transmission probabilities that have been set zero are then restricted to remain at zero, and the problem is then relaxed with the sparsity parameter set to ρ = 0. [sent-140, score-0.36]
61 This preserves the precision and recall of the edge location prediction of the algorithm while still generating accurate edge transmission probability predictions. [sent-141, score-0.545]
62 Moreover, with the implementation described above, most 1000 node networks can be inferred inside of 10 minutes, running on a laptop. [sent-142, score-0.304]
63 3 Experiments In this section, we evaluate our network inference method, which we will refer to as ConNIe (Convex Network Inference) on a range of datasets and network topologies. [sent-146, score-0.334]
64 This includes both synthetically generated networks as well as real social networks, and both simulated and real diffusion data. [sent-147, score-0.423]
65 In each o e case, the networks were constructed as unweighted graphs, and then each edge (i, j) was assigned a uniformly random transmission probability Aij between 0. [sent-153, score-0.423]
66 In all of our experiments, we assume that the model w(t) of transmission times is known. [sent-156, score-0.264]
67 We generate cascades by first selecting a random starting node of the infection. [sent-162, score-0.305]
68 From there, the infection is propagated to other nodes until no new infections occur: an infected node i transmits the infection to uninfected j with probability Aij , and if transmission occurs then the propagation time t is sampled according to the distribution w(t). [sent-163, score-1.692]
69 (d)-(f): Mean square error of the edge transmission probability of the two algorithms. [sent-203, score-0.342]
70 Not to make the problem too easy we generate enough cascades so that 99% of all edges of the network transmitted at least one infection. [sent-206, score-0.419]
71 To assess the performance of ConNIe, we consider both the accuracy of the edge prediction, as well as the accuracy of edge transmission probability. [sent-210, score-0.448]
72 For large values of ρ inferred networks have high precision but low recall, while for low values of ρ the precision will be poor but the recall will be high. [sent-213, score-0.294]
73 To assess the accuracy of the estimated edge transmission probabilities Aij , we compute the meansquare error (MSE). [sent-214, score-0.36]
74 The MSE is taken over the union of potential edge positions (node pairs) where there is an edge in the latent network, and the edge positions in which the algorithm has predicted the presence of an edge. [sent-215, score-0.35]
75 NetInf first reconstructs the most likely structure of each cascade, and then based on this reconstruction, it selects the next most likely edge of the social network. [sent-219, score-0.309]
76 To apply this algorithm to the problem we are considering, we simply first use the NetInf to infer the network structure and then estimate the edge transmission probabilities Aij by simply counting the fraction of times it was predicted that a cascade propagated along the edge (i, j). [sent-223, score-0.84]
77 Figure 1 shows the precision-recall curves for the scale-free synthetic network with the three transmission models w(t). [sent-224, score-0.429]
78 Also in Figure 1 we plot the Mean Squared Error of the estimates of the edge transmission 6 1 0. [sent-229, score-0.342]
79 (e) PR Break-even point versus the perturbation size applied to the infection times. [sent-257, score-0.335]
80 The green vertical line indicates the point where the inferred network contains the same number of edges as the real network. [sent-259, score-0.355]
81 This, of course, is expected as NetInf assumes the network edge weights are homogeneous, which is not the case. [sent-262, score-0.29]
82 Figure 2 shows the accuracy (Precision-Recall break-even point as well as edge MSE) as a function of the number of observed diffusions, as well as the effect of noise in the infection times. [sent-264, score-0.441]
83 Noise was added to the cascades by adding independent normally distribution perturbations to each of the observed infection times, and the noise to signal ratio was calculated as the average perturbation over the average infection transmission time. [sent-265, score-1.066]
84 Second, we experiment on a real email social network of 593 nodes and 2824 edges that is based on the email communication in a small European research institute. [sent-272, score-0.685]
85 For the edges in the collaboration network we simply randomly assigned their edge transmission probabilities. [sent-273, score-0.655]
86 For the email network we generated cascades using the power-law transmission time model, while for the collaboration network we used the Weibull distribution for sampling transmission times. [sent-281, score-1.051]
87 Moreover, the edge transmission probability estimation error is less than 0. [sent-285, score-0.342]
88 This is ideal: our method is capable of near perfect recovery of the underlying social network over which a relatively small number of contagions diffused. [sent-287, score-0.415]
89 8 Recommendation network Figure 3: The precision-recall curve of the network estimation and the mean-square error (left) of predicted transmission probabilities as a function of number edges being predicted (middle). [sent-323, score-0.718]
90 (Right) Precision-recall curve on inferring a real recommendation network based on real product recommendation data. [sent-325, score-0.396]
91 People generate cascades as follows: a node (person) v buys product p at time t, and then recommends it to nodes {w1 , . [sent-328, score-0.38]
92 We consider a recommendation network of 275 users and 1522 edges and a set of 5,767 recommendations on 625 different products between a set of these users. [sent-334, score-0.342]
93 Since the edge transmission model is unknown we model it with a power-law distribution with parameter α = 2. [sent-335, score-0.342]
94 Our approach is able to recover the underlying social network surprisingly accurately. [sent-337, score-0.374]
95 Since there are no ground truth edge transmission probabilities for us to compare against, we can not compute the error of edge weight estimation. [sent-342, score-0.466]
96 4 Conclusion We have presented a general solution to the problem of inferring latent social networks from the network diffusion data. [sent-343, score-0.639]
97 We evaluated our algorithm on a wide set of synthetic and real-world networks with several different cascade propagation models. [sent-346, score-0.264]
98 Experiments reveal that our method near-perfectly recovers the underlying network structure as well as the parameters of the edge transmission model. [sent-348, score-0.569]
99 By inferring and modeling the structure of such latent social networks, we can gain insight into positions and roles various nodes play in the diffusion process and assess the range of influence of nodes in the network. [sent-352, score-0.558]
100 Recovering time-varying networks of dependencies in social and biological studies. [sent-358, score-0.267]
wordName wordTfidf (topN-words)
[('infected', 0.49), ('netinf', 0.341), ('infection', 0.335), ('connie', 0.3), ('transmission', 0.236), ('social', 0.186), ('network', 0.167), ('node', 0.162), ('bji', 0.156), ('aji', 0.144), ('cascades', 0.143), ('cascade', 0.125), ('mse', 0.121), ('edges', 0.109), ('edge', 0.106), ('diffusion', 0.099), ('ic', 0.092), ('contagion', 0.082), ('networks', 0.081), ('aij', 0.078), ('nodes', 0.075), ('inferring', 0.074), ('weibull', 0.068), ('leskovec', 0.066), ('diffusions', 0.066), ('email', 0.065), ('inferred', 0.061), ('break', 0.061), ('tc', 0.059), ('mle', 0.058), ('pr', 0.055), ('precision', 0.055), ('susceptible', 0.054), ('pl', 0.052), ('xc', 0.051), ('recommendation', 0.049), ('recall', 0.042), ('contagions', 0.041), ('infects', 0.041), ('rumor', 0.041), ('sis', 0.041), ('viral', 0.041), ('wb', 0.041), ('collaboration', 0.037), ('infer', 0.037), ('marketing', 0.036), ('propagation', 0.032), ('latent', 0.032), ('unobserved', 0.032), ('pnas', 0.031), ('penalty', 0.03), ('person', 0.03), ('disease', 0.028), ('times', 0.028), ('incoming', 0.027), ('epidemic', 0.027), ('infect', 0.027), ('infections', 0.027), ('jure', 0.027), ('outbreak', 0.027), ('sars', 0.027), ('wj', 0.027), ('people', 0.026), ('synthetic', 0.026), ('likelihood', 0.025), ('observe', 0.024), ('spreads', 0.024), ('convexify', 0.024), ('sir', 0.024), ('reveal', 0.022), ('emails', 0.022), ('adoption', 0.022), ('mina', 0.022), ('drosophila', 0.022), ('si', 0.022), ('underlying', 0.021), ('curve', 0.021), ('www', 0.021), ('men', 0.021), ('synthetically', 0.021), ('got', 0.021), ('spread', 0.02), ('erd', 0.02), ('convex', 0.019), ('exp', 0.019), ('subproblems', 0.019), ('connected', 0.018), ('million', 0.018), ('probabilities', 0.018), ('link', 0.018), ('real', 0.018), ('matter', 0.018), ('perturbations', 0.017), ('mij', 0.017), ('nyi', 0.017), ('li', 0.017), ('assumes', 0.017), ('structure', 0.017), ('products', 0.017), ('moreover', 0.016)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000005 190 nips-2010-On the Convexity of Latent Social Network Inference
Author: Seth Myers, Jure Leskovec
Abstract: In many real-world scenarios, it is nearly impossible to collect explicit social network data. In such cases, whole networks must be inferred from underlying observations. Here, we formulate the problem of inferring latent social networks based on network diffusion or disease propagation data. We consider contagions propagating over the edges of an unobserved social network, where we only observe the times when nodes became infected, but not who infected them. Given such node infection times, we then identify the optimal network that best explains the observed data. We present a maximum likelihood approach based on convex programming with a l1 -like penalty term that encourages sparsity. Experiments on real and synthetic data reveal that our method near-perfectly recovers the underlying network structure as well as the parameters of the contagion propagation model. Moreover, our approach scales well as it can infer optimal networks of thousands of nodes in a matter of minutes.
2 0.11440789 117 nips-2010-Identifying graph-structured activation patterns in networks
Author: James Sharpnack, Aarti Singh
Abstract: We consider the problem of identifying an activation pattern in a complex, largescale network that is embedded in very noisy measurements. This problem is relevant to several applications, such as identifying traces of a biochemical spread by a sensor network, expression levels of genes, and anomalous activity or congestion in the Internet. Extracting such patterns is a challenging task specially if the network is large (pattern is very high-dimensional) and the noise is so excessive that it masks the activity at any single node. However, typically there are statistical dependencies in the network activation process that can be leveraged to fuse the measurements of multiple nodes and enable reliable extraction of highdimensional noisy patterns. In this paper, we analyze an estimator based on the graph Laplacian eigenbasis, and establish the limits of mean square error recovery of noisy patterns arising from a probabilistic (Gaussian or Ising) model based on an arbitrary graph structure. We consider both deterministic and probabilistic network evolution models, and our results indicate that by leveraging the network interaction structure, it is possible to consistently recover high-dimensional patterns even when the noise variance increases with network size. 1
3 0.10471314 132 nips-2010-Joint Cascade Optimization Using A Product Of Boosted Classifiers
Author: Leonidas Lefakis, Francois Fleuret
Abstract: The standard strategy for efficient object detection consists of building a cascade composed of several binary classifiers. The detection process takes the form of a lazy evaluation of the conjunction of the responses of these classifiers, and concentrates the computation on difficult parts of the image which cannot be trivially rejected. We introduce a novel algorithm to construct jointly the classifiers of such a cascade, which interprets the response of a classifier as the probability of a positive prediction, and the overall response of the cascade as the probability that all the predictions are positive. From this noisy-AND model, we derive a consistent loss and a Boosting procedure to optimize that global probability on the training set. Such a joint learning allows the individual predictors to focus on a more restricted modeling problem, and improves the performance compared to a standard cascade. We demonstrate the efficiency of this approach on face and pedestrian detection with standard data-sets and comparisons with reference baselines. 1
4 0.099909388 239 nips-2010-Sidestepping Intractable Inference with Structured Ensemble Cascades
Author: David Weiss, Benjamin Sapp, Ben Taskar
Abstract: For many structured prediction problems, complex models often require adopting approximate inference techniques such as variational methods or sampling, which generally provide no satisfactory accuracy guarantees. In this work, we propose sidestepping intractable inference altogether by learning ensembles of tractable sub-models as part of a structured prediction cascade. We focus in particular on problems with high-treewidth and large state-spaces, which occur in many computer vision tasks. Unlike other variational methods, our ensembles do not enforce agreement between sub-models, but filter the space of possible outputs by simply adding and thresholding the max-marginals of each constituent model. Our framework jointly estimates parameters for all models in the ensemble for each level of the cascade by minimizing a novel, convex loss function, yet requires only a linear increase in computation over learning or inference in a single tractable sub-model. We provide a generalization bound on the filtering loss of the ensemble as a theoretical justification of our approach, and we evaluate our method on both synthetic data and the task of estimating articulated human pose from challenging videos. We find that our approach significantly outperforms loopy belief propagation on the synthetic data and a state-of-the-art model on the pose estimation/tracking problem. 1
5 0.082320273 276 nips-2010-Tree-Structured Stick Breaking for Hierarchical Data
Author: Zoubin Ghahramani, Michael I. Jordan, Ryan P. Adams
Abstract: Many data are naturally modeled by an unobserved hierarchical structure. In this paper we propose a flexible nonparametric prior over unknown data hierarchies. The approach uses nested stick-breaking processes to allow for trees of unbounded width and depth, where data can live at any node and are infinitely exchangeable. One can view our model as providing infinite mixtures where the components have a dependency structure corresponding to an evolutionary diffusion down a tree. By using a stick-breaking approach, we can apply Markov chain Monte Carlo methods based on slice sampling to perform Bayesian inference and simulate from the posterior distribution on trees. We apply our method to hierarchical clustering of images and topic modeling of text data. 1
6 0.078916751 63 nips-2010-Distributed Dual Averaging In Networks
7 0.076805636 42 nips-2010-Boosting Classifier Cascades
8 0.072867706 150 nips-2010-Learning concept graphs from text with stick-breaking priors
9 0.072813116 162 nips-2010-Link Discovery using Graph Feature Tracking
10 0.056654286 129 nips-2010-Inter-time segment information sharing for non-homogeneous dynamic Bayesian networks
11 0.054451264 48 nips-2010-Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
12 0.054207187 55 nips-2010-Cross Species Expression Analysis using a Dirichlet Process Mixture Model with Latent Matchings
13 0.052065343 85 nips-2010-Exact learning curves for Gaussian process regression on large random graphs
14 0.050364055 126 nips-2010-Inference with Multivariate Heavy-Tails in Linear Models
15 0.050315093 44 nips-2010-Brain covariance selection: better individual functional connectivity models using population prior
16 0.050104063 148 nips-2010-Learning Networks of Stochastic Differential Equations
17 0.048216157 127 nips-2010-Inferring Stimulus Selectivity from the Spatial Structure of Neural Network Dynamics
18 0.047081836 265 nips-2010-The LASSO risk: asymptotic results and real world examples
19 0.045116875 128 nips-2010-Infinite Relational Modeling of Functional Connectivity in Resting State fMRI
20 0.044481426 32 nips-2010-Approximate Inference by Compilation to Arithmetic Circuits
topicId topicWeight
[(0, 0.129), (1, 0.047), (2, -0.025), (3, 0.057), (4, -0.083), (5, -0.055), (6, -0.026), (7, 0.003), (8, 0.013), (9, 0.033), (10, -0.131), (11, 0.018), (12, 0.008), (13, 0.07), (14, -0.035), (15, -0.053), (16, 0.067), (17, -0.012), (18, -0.182), (19, 0.133), (20, -0.014), (21, 0.022), (22, -0.063), (23, -0.0), (24, -0.005), (25, 0.074), (26, -0.006), (27, 0.03), (28, -0.015), (29, -0.052), (30, -0.027), (31, 0.051), (32, 0.09), (33, -0.03), (34, -0.032), (35, -0.102), (36, -0.025), (37, 0.01), (38, -0.031), (39, -0.003), (40, -0.097), (41, 0.011), (42, 0.032), (43, 0.005), (44, 0.029), (45, 0.021), (46, 0.038), (47, -0.005), (48, 0.029), (49, 0.001)]
simIndex simValue paperId paperTitle
same-paper 1 0.92482597 190 nips-2010-On the Convexity of Latent Social Network Inference
Author: Seth Myers, Jure Leskovec
Abstract: In many real-world scenarios, it is nearly impossible to collect explicit social network data. In such cases, whole networks must be inferred from underlying observations. Here, we formulate the problem of inferring latent social networks based on network diffusion or disease propagation data. We consider contagions propagating over the edges of an unobserved social network, where we only observe the times when nodes became infected, but not who infected them. Given such node infection times, we then identify the optimal network that best explains the observed data. We present a maximum likelihood approach based on convex programming with a l1 -like penalty term that encourages sparsity. Experiments on real and synthetic data reveal that our method near-perfectly recovers the underlying network structure as well as the parameters of the contagion propagation model. Moreover, our approach scales well as it can infer optimal networks of thousands of nodes in a matter of minutes.
2 0.69443679 117 nips-2010-Identifying graph-structured activation patterns in networks
Author: James Sharpnack, Aarti Singh
Abstract: We consider the problem of identifying an activation pattern in a complex, largescale network that is embedded in very noisy measurements. This problem is relevant to several applications, such as identifying traces of a biochemical spread by a sensor network, expression levels of genes, and anomalous activity or congestion in the Internet. Extracting such patterns is a challenging task specially if the network is large (pattern is very high-dimensional) and the noise is so excessive that it masks the activity at any single node. However, typically there are statistical dependencies in the network activation process that can be leveraged to fuse the measurements of multiple nodes and enable reliable extraction of highdimensional noisy patterns. In this paper, we analyze an estimator based on the graph Laplacian eigenbasis, and establish the limits of mean square error recovery of noisy patterns arising from a probabilistic (Gaussian or Ising) model based on an arbitrary graph structure. We consider both deterministic and probabilistic network evolution models, and our results indicate that by leveraging the network interaction structure, it is possible to consistently recover high-dimensional patterns even when the noise variance increases with network size. 1
3 0.59656233 204 nips-2010-Penalized Principal Component Regression on Graphs for Analysis of Subnetworks
Author: Ali Shojaie, George Michailidis
Abstract: Network models are widely used to capture interactions among component of complex systems, such as social and biological. To understand their behavior, it is often necessary to analyze functionally related components of the system, corresponding to subsystems. Therefore, the analysis of subnetworks may provide additional insight into the behavior of the system, not evident from individual components. We propose a novel approach for incorporating available network information into the analysis of arbitrary subnetworks. The proposed method offers an efficient dimension reduction strategy using Laplacian eigenmaps with Neumann boundary conditions, and provides a flexible inference framework for analysis of subnetworks, based on a group-penalized principal component regression model on graphs. Asymptotic properties of the proposed inference method, as well as the choice of the tuning parameter for control of the false positive rate are discussed in high dimensional settings. The performance of the proposed methodology is illustrated using simulated and real data examples from biology. 1
4 0.55356836 259 nips-2010-Subgraph Detection Using Eigenvector L1 Norms
Author: Benjamin Miller, Nadya Bliss, Patrick J. Wolfe
Abstract: When working with network datasets, the theoretical framework of detection theory for Euclidean vector spaces no longer applies. Nevertheless, it is desirable to determine the detectability of small, anomalous graphs embedded into background networks with known statistical properties. Casting the problem of subgraph detection in a signal processing context, this article provides a framework and empirical results that elucidate a “detection theory” for graph-valued data. Its focus is the detection of anomalies in unweighted, undirected graphs through L1 properties of the eigenvectors of the graph’s so-called modularity matrix. This metric is observed to have relatively low variance for certain categories of randomly-generated graphs, and to reveal the presence of an anomalous subgraph with reasonable reliability when the anomaly is not well-correlated with stronger portions of the background graph. An analysis of subgraphs in real network datasets confirms the efficacy of this approach. 1
5 0.54549867 85 nips-2010-Exact learning curves for Gaussian process regression on large random graphs
Author: Matthew Urry, Peter Sollich
Abstract: We study learning curves for Gaussian process regression which characterise performance in terms of the Bayes error averaged over datasets of a given size. Whilst learning curves are in general very difficult to calculate we show that for discrete input domains, where similarity between input points is characterised in terms of a graph, accurate predictions can be obtained. These should in fact become exact for large graphs drawn from a broad range of random graph ensembles with arbitrary degree distributions where each input (node) is connected only to a finite number of others. Our approach is based on translating the appropriate belief propagation equations to the graph ensemble. We demonstrate the accuracy of the predictions for Poisson (Erdos-Renyi) and regular random graphs, and discuss when and why previous approximations of the learning curve fail. 1
6 0.52969807 42 nips-2010-Boosting Classifier Cascades
7 0.52529258 239 nips-2010-Sidestepping Intractable Inference with Structured Ensemble Cascades
8 0.52323407 129 nips-2010-Inter-time segment information sharing for non-homogeneous dynamic Bayesian networks
9 0.49178389 150 nips-2010-Learning concept graphs from text with stick-breaking priors
10 0.49090663 63 nips-2010-Distributed Dual Averaging In Networks
11 0.47588587 132 nips-2010-Joint Cascade Optimization Using A Product Of Boosted Classifiers
12 0.43126687 126 nips-2010-Inference with Multivariate Heavy-Tails in Linear Models
13 0.4274613 84 nips-2010-Exact inference and learning for cumulative distribution functions on loopy graphs
14 0.4223316 105 nips-2010-Getting lost in space: Large sample analysis of the resistance distance
15 0.42093533 34 nips-2010-Attractor Dynamics with Synaptic Depression
16 0.41325745 3 nips-2010-A Bayesian Framework for Figure-Ground Interpretation
17 0.412956 162 nips-2010-Link Discovery using Graph Feature Tracking
18 0.40098435 120 nips-2010-Improvements to the Sequence Memoizer
19 0.4008849 127 nips-2010-Inferring Stimulus Selectivity from the Spatial Structure of Neural Network Dynamics
20 0.39262009 254 nips-2010-Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models
topicId topicWeight
[(13, 0.067), (27, 0.058), (30, 0.04), (35, 0.018), (45, 0.168), (50, 0.097), (52, 0.028), (60, 0.029), (62, 0.285), (72, 0.01), (77, 0.059), (79, 0.013), (90, 0.019)]
simIndex simValue paperId paperTitle
same-paper 1 0.74706978 190 nips-2010-On the Convexity of Latent Social Network Inference
Author: Seth Myers, Jure Leskovec
Abstract: In many real-world scenarios, it is nearly impossible to collect explicit social network data. In such cases, whole networks must be inferred from underlying observations. Here, we formulate the problem of inferring latent social networks based on network diffusion or disease propagation data. We consider contagions propagating over the edges of an unobserved social network, where we only observe the times when nodes became infected, but not who infected them. Given such node infection times, we then identify the optimal network that best explains the observed data. We present a maximum likelihood approach based on convex programming with a l1 -like penalty term that encourages sparsity. Experiments on real and synthetic data reveal that our method near-perfectly recovers the underlying network structure as well as the parameters of the contagion propagation model. Moreover, our approach scales well as it can infer optimal networks of thousands of nodes in a matter of minutes.
Author: Li-jia Li, Hao Su, Li Fei-fei, Eric P. Xing
Abstract: Robust low-level image features have been proven to be effective representations for a variety of visual recognition tasks such as object recognition and scene classification; but pixels, or even local image patches, carry little semantic meanings. For high level visual tasks, such low-level image representations are potentially not enough. In this paper, we propose a high-level image representation, called the Object Bank, where an image is represented as a scale-invariant response map of a large number of pre-trained generic object detectors, blind to the testing dataset or visual task. Leveraging on the Object Bank representation, superior performances on high level visual recognition tasks can be achieved with simple off-the-shelf classifiers such as logistic regression and linear SVM. Sparsity algorithms make our representation more efficient and scalable for large scene datasets, and reveal semantically meaningful feature patterns.
3 0.60535514 238 nips-2010-Short-term memory in neuronal networks through dynamical compressed sensing
Author: Surya Ganguli, Haim Sompolinsky
Abstract: Recent proposals suggest that large, generic neuronal networks could store memory traces of past input sequences in their instantaneous state. Such a proposal raises important theoretical questions about the duration of these memory traces and their dependence on network size, connectivity and signal statistics. Prior work, in the case of gaussian input sequences and linear neuronal networks, shows that the duration of memory traces in a network cannot exceed the number of neurons (in units of the neuronal time constant), and that no network can out-perform an equivalent feedforward network. However a more ethologically relevant scenario is that of sparse input sequences. In this scenario, we show how linear neural networks can essentially perform compressed sensing (CS) of past inputs, thereby attaining a memory capacity that exceeds the number of neurons. This enhanced capacity is achieved by a class of “orthogonal” recurrent networks and not by feedforward networks or generic recurrent networks. We exploit techniques from the statistical physics of disordered systems to analytically compute the decay of memory traces in such networks as a function of network size, signal sparsity and integration time. Alternately, viewed purely from the perspective of CS, this work introduces a new ensemble of measurement matrices derived from dynamical systems, and provides a theoretical analysis of their asymptotic performance. 1
4 0.59781152 51 nips-2010-Construction of Dependent Dirichlet Processes based on Poisson Processes
Author: Dahua Lin, Eric Grimson, John W. Fisher
Abstract: We present a novel method for constructing dependent Dirichlet processes. The approach exploits the intrinsic relationship between Dirichlet and Poisson processes in order to create a Markov chain of Dirichlet processes suitable for use as a prior over evolving mixture models. The method allows for the creation, removal, and location variation of component models over time while maintaining the property that the random measures are marginally DP distributed. Additionally, we derive a Gibbs sampling algorithm for model inference and test it on both synthetic and real data. Empirical results demonstrate that the approach is effective in estimating dynamically varying mixture models. 1
5 0.596398 117 nips-2010-Identifying graph-structured activation patterns in networks
Author: James Sharpnack, Aarti Singh
Abstract: We consider the problem of identifying an activation pattern in a complex, largescale network that is embedded in very noisy measurements. This problem is relevant to several applications, such as identifying traces of a biochemical spread by a sensor network, expression levels of genes, and anomalous activity or congestion in the Internet. Extracting such patterns is a challenging task specially if the network is large (pattern is very high-dimensional) and the noise is so excessive that it masks the activity at any single node. However, typically there are statistical dependencies in the network activation process that can be leveraged to fuse the measurements of multiple nodes and enable reliable extraction of highdimensional noisy patterns. In this paper, we analyze an estimator based on the graph Laplacian eigenbasis, and establish the limits of mean square error recovery of noisy patterns arising from a probabilistic (Gaussian or Ising) model based on an arbitrary graph structure. We consider both deterministic and probabilistic network evolution models, and our results indicate that by leveraging the network interaction structure, it is possible to consistently recover high-dimensional patterns even when the noise variance increases with network size. 1
6 0.59514606 33 nips-2010-Approximate inference in continuous time Gaussian-Jump processes
7 0.59310359 49 nips-2010-Computing Marginal Distributions over Continuous Markov Networks for Statistical Relational Learning
8 0.59274697 109 nips-2010-Group Sparse Coding with a Laplacian Scale Mixture Prior
9 0.59234786 147 nips-2010-Learning Multiple Tasks with a Sparse Matrix-Normal Penalty
10 0.59087515 158 nips-2010-Learning via Gaussian Herding
11 0.58928776 30 nips-2010-An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA
12 0.58872294 148 nips-2010-Learning Networks of Stochastic Differential Equations
13 0.58863115 122 nips-2010-Improving the Asymptotic Performance of Markov Chain Monte-Carlo by Inserting Vortices
14 0.58812249 92 nips-2010-Fast global convergence rates of gradient methods for high-dimensional statistical recovery
15 0.58668166 63 nips-2010-Distributed Dual Averaging In Networks
16 0.5862093 217 nips-2010-Probabilistic Multi-Task Feature Selection
17 0.58520585 265 nips-2010-The LASSO risk: asymptotic results and real world examples
18 0.5840975 242 nips-2010-Slice sampling covariance hyperparameters of latent Gaussian models
19 0.58403403 42 nips-2010-Boosting Classifier Cascades
20 0.58375013 87 nips-2010-Extended Bayesian Information Criteria for Gaussian Graphical Models