nips nips2012 nips2012-346 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Marcelo Fiori, Pablo Musé, Guillermo Sapiro
Abstract: Graphical models are a very useful tool to describe and understand natural phenomena, from gene expression to climate change and social interactions. The topological structure of these graphs/networks is a fundamental part of the analysis, and in many cases the main goal of the study. However, little work has been done on incorporating prior topological knowledge onto the estimation of the underlying graphical models from sample data. In this work we propose extensions to the basic joint regression model for network estimation, which explicitly incorporate graph-topological constraints into the corresponding optimization approach. The first proposed extension includes an eigenvector centrality constraint, thereby promoting this important prior topological property. The second developed extension promotes the formation of certain motifs, triangle-shaped ones in particular, which are known to exist for example in genetic regulatory networks. The presentation of the underlying formulations, which serve as examples of the introduction of topological constraints in network estimation, is complemented with examples in diverse datasets demonstrating the importance of incorporating such critical prior knowledge. 1
Reference: text
sentIndex sentText sentNum sentScore
1 However, little work has been done on incorporating prior topological knowledge onto the estimation of the underlying graphical models from sample data. [sent-9, score-0.303]
2 In this work we propose extensions to the basic joint regression model for network estimation, which explicitly incorporate graph-topological constraints into the corresponding optimization approach. [sent-10, score-0.302]
3 The first proposed extension includes an eigenvector centrality constraint, thereby promoting this important prior topological property. [sent-11, score-1.027]
4 The second developed extension promotes the formation of certain motifs, triangle-shaped ones in particular, which are known to exist for example in genetic regulatory networks. [sent-12, score-0.202]
5 The presentation of the underlying formulations, which serve as examples of the introduction of topological constraints in network estimation, is complemented with examples in diverse datasets demonstrating the importance of incorporating such critical prior knowledge. [sent-13, score-0.335]
6 Therefore, the estimation of this graph G from k random samples of X is equivalent to the covariance selection problem. [sent-23, score-0.2]
7 One of the most studied examples, and indeed with great impact, is the inference of genetic regulatory networks (GRN) from DNA microarray data, where typically the number p of genes is much larger than the number k of experiments. [sent-27, score-0.296]
8 Like in the vast majority of applications, these networks have some very well known topological properties, such as sparsity (each node is connected with only a few other nodes), scale-free behavior, and the presence of hubs (nodes connected with many other vertices). [sent-28, score-0.365]
9 All these properties are shared with many other real life networks like Internet, citation networks, and social networks (Newman, 2010). [sent-29, score-0.224]
10 1 Genetic regulatory networks also contain a small set of recurring patterns called motifs. [sent-30, score-0.211]
11 The systematic presence of these motifs has been first discovered in Escherichia coli (Shen-Orr et al. [sent-31, score-0.529]
12 The topological analysis of networks is fundamental, and often the essence of the study. [sent-33, score-0.266]
13 For example, the proper identification of hubs or motifs in GRN is crucial. [sent-34, score-0.43]
14 Incorporating such topological knowledge in network estimation is the main goal of this work. [sent-37, score-0.349]
15 Eigenvector centrality (see Section 3 for the precise definition) is a well-known measure of the importance and the connectivity of each node, and typical centrality distributions are known (or can be estimated) for several types of networks. [sent-38, score-1.389]
16 Therefore, we first propose to incorporate this structural information into the optimization procedure for network estimation in order to control the topology of the resulting network. [sent-39, score-0.28]
17 As mentioned, it has been observed that genetic regulatory networks are conformed by a few geometric patterns, repeated several times. [sent-41, score-0.303]
18 One of these motifs is the so-called feedforward loop, which is manifested as a triangle in the graph. [sent-42, score-0.457]
19 Although it is thought that these important motifs may help to understand more complex organisms, no effort has been made to include this prior information in the network estimation problem. [sent-43, score-0.581]
20 As a second example of the introduction of topological constraints, we propose a simple modification to the 1 penalty, weighting the edges according to their local structure, in order to favor the appearance of these motifs in the estimated network. [sent-44, score-0.66]
21 In Section 2 we describe the basic precision matrix estimation models used in this work. [sent-49, score-0.176]
22 In Section 3 we introduce the eigenvector centrality and describe how to impose it in graph estimation. [sent-50, score-0.912]
23 We propose the weighting method for motifs estimation in Section 4. [sent-51, score-0.465]
24 This regression of the form X ≈ XB, with B sparse, symmetric, and with null diagonal, allows to control the topology of the graph defined by the non-zero pattern of B, as it will be later exploited in this work. [sent-60, score-0.266]
25 A completely different technique for network estimation is the use of the PC-Algorithm to infer acyclic graphs (Kalisch & B¨ hlmann, 2007). [sent-68, score-0.261]
26 In this work, we use this technique to estimate the graph eigenvector centrality. [sent-70, score-0.243]
27 In this work, we consider the eigenvector centrality, defined as the dominant eigenvector (the one corresponding to the largest eigenvalue) of the corresponding network connectivity matrix. [sent-73, score-0.457]
28 The coordinates of this vector (which are all non-negatives) are the corresponding centrality of each node, and provide a measure of the influence of the node in the network (Google’s PageRank is a variant of this centrality measure). [sent-74, score-1.523]
29 Distributions of the eigenvector centrality values are well known for a number of graphs, including scale-free networks as the Internet and GRN (Newman, 2010). [sent-75, score-0.899]
30 In certain situations, we may have at our disposal an estimate of the centrality vector of the network to infer. [sent-76, score-0.785]
31 This may happen, for instance, because we already had preliminary data, or we know a network expected to be similar, or simply someone provided us with some partial information about the graph structure. [sent-77, score-0.227]
32 In those cases, we would like to make use of this important side information, both to improve the overall network estimation and to guarantee that the inferred graph is consistent with our prior topological knowledge. [sent-78, score-0.5]
33 In what follows we propose an extension of the joint regression model which is capable of controlling this topological property of the estimated graph. [sent-79, score-0.35]
34 Therefore for precision and graph connectivity matrices it holds that max||v||=1 | Av, v | = max||v||=1 Av, v , and moreover, the eigenvector centrality is c = arg max||v||=1 Av, v . [sent-82, score-1.006]
35 Suppose that we know an estimate of the centrality c ∈ Rp , and want the inferred network to have centrality close to it. [sent-83, score-1.494]
36 B symmetric, Bii = 0 ∀ i (2) B 1 and add the centrality penalty, B where || · ||F is the Frobenius norm and ||B|| 1 = i,j |Bij |. [sent-88, score-0.669]
37 Note that we are imposing the dominant eigenvector of the graph connectivity matrix A to a nonbinary matrix B. [sent-93, score-0.433]
38 We have exhaustive empirical evidence that the leading eigenvector of the matrix 3 B obtained by solving (2), and the leading eigenvector corresponding to the resulting connectivity matrix (the binarization of B) are very similar (see Section 5. [sent-94, score-0.403]
39 As shown in Section 5, when the correct centrality is imposed, our proposed model outperforms the joint regression model, both in correct reconstructed edge rates and topology. [sent-97, score-0.922]
40 Even if we do not have prior information at all, and we estimate the centrality from the data with a pre-run of the PC-Algorithm, we obtain improved results. [sent-99, score-0.669]
41 Favoring Motifs in Graphical Models One of the biggest challenges in bioinformatics is the estimation and understanding of genetic regulatory networks. [sent-117, score-0.234]
42 It has been observed that the structure of these graphs is far from being random: the transcription networks seem to be conformed by a small set of regulation patterns that appear much more often than in random graphs. [sent-118, score-0.279]
43 Three basic types of motifs are defined (ShenOrr et al. [sent-120, score-0.424]
44 As these models do not consider any topological structure, and the total number of reconstructed triangles is usually much lower than in transcription networks, it seems reasonable to help in the formation of these motifs by favoring the presence of triangles. [sent-125, score-0.741]
45 In order to move towards a better motif detection, we propose an iterative procedure based on the joint regression model (1). [sent-126, score-0.275]
46 This way, if (B 2 )ij = 0 the weight does not affect the penalty, and if (B 2 )ij = 0, it favors motifs detection. [sent-133, score-0.431]
47 Namely, we start from a random graph with 4 nodes and add one node at a time, randomly connected to one of the existing nodes. [sent-140, score-0.227]
48 The probability of connecting the new node to the node i is proportional to the current degree of node i. [sent-141, score-0.207]
49 Given a graph with adjacency matrix A, we simulate the data X as follows (Liu & Ihler, 2011): let D be a diagonal matrix containing the degree of node i in the entry Dii , and consider the matrix L = ηD − A with η > 1 so that L is positive definite. [sent-142, score-0.372]
50 1 Including Actual Centrality In this first experiment we show how our model (2) is able to correctly incorporate the prior centrality information, resulting in a more accurate inferred graph, both in detected edges and in topology. [sent-149, score-0.852]
51 We generated 10 samples and inferred the graph with the joint regression model and with the proposed model (2) using the correct centrality. [sent-151, score-0.263]
52 Figure 1: Comparison of networks estimated with the simple joint model (1) (middle) and with model (2) (right) using the eigenvector centrality. [sent-152, score-0.323]
53 The following more comprehensive test shows the improvement with respect to the basic joint model (1) when the correct centrality is included. [sent-154, score-0.749]
54 From these data we estimated the network with the joint regression model with and without the centrality prior. [sent-156, score-0.934]
55 The TP edge rates in Figure 2(a) are averaged over the 50 runs, and count the correctly detected edges over the (fixed) total number of edges in the network. [sent-157, score-0.283]
56 As expected, the incorporation of the known topological property helps in the correct estimation of the graph. [sent-160, score-0.233]
57 025 (b) Edge detection ROC curve for networks with p = 80 nodes and k = 50. [sent-177, score-0.176]
58 In blue (dashed), the standard joint model (1), and in black the proposed model with centrality (2). [sent-179, score-0.725]
59 5 Following the previous discussion, Figure 3 shows the inner product vB , vC for several runs of model (2), where vB is the leading eigenvector of the obtained matrix B, C is the resulting connectivity matrix (the binarized version of B), and vC its leading eigenvector. [sent-181, score-0.271]
60 6 40 80 120 160 Run number 30 40 k 50 60 70 Figure 4: True positive edge rates for different sample sizes on a network with 100 nodes. [sent-185, score-0.201]
61 Dashed, the joint model (1), dotted, the PC-Algorithm, and solid the model (2) with centrality estimated from data. [sent-186, score-0.762]
62 7 Imposing Centrality Estimated from Data The previous section shows how the performance of the joint regression model (1) can be improved by incorporating the centrality, when this topology information is available. [sent-195, score-0.237]
63 We use the PC-Algorithm to estimate the centrality (by computing the dominant eigenvector of the resulting graph), and then we impose it as the vector c in model (2). [sent-197, score-0.827]
64 It turns out that even with a technique not specialized for centrality estimation, this combination outperforms both the joint model (1) and the PC-Algorithm. [sent-198, score-0.725]
65 We then reconstructed the graph using the three techniques and averaged the edge rate over the ten runs. [sent-201, score-0.294]
66 Figure 4 shows how the model imposing centrality can improve the other ones without any external information. [sent-203, score-0.694]
67 3 Transferring Centrality In several situations, one may have some information about the topology of the graph to infer, mainly based on other data/graphs known to be similar. [sent-205, score-0.21]
68 For instance, dynamic networks are a good example where one may have some (maybe abundant) old data from the network at a past time T1 , some (maybe scarce) new data at time T2 , and know that the network topology is similar at the different times. [sent-206, score-0.429]
69 We would like to transfer our inferred centrality-based topological knowledge from the first network into the second one, and by that improving the network estimation from limited data. [sent-209, score-0.505]
70 For these examples, we have an unknown graph G1 corresponding to a k1 ×p data matrix X1 , which we assume is enough to reasonably estimate G1 , and an unknown graph G2 with a k2 ×p data matrix X2 (with k2 k1 ). [sent-210, score-0.31]
71 , just the underlying centrality of G1 is transferred to G2 . [sent-214, score-0.669]
72 In what follows, we show the comparison of inferring the network G2 using only the data X2 in the joint model (1); the concatenation of X1 and X2 in the joint model (1); and finally the centrality estimated from X1 , imposed in model (2), along with data X2 . [sent-215, score-0.961]
73 Given a graph G1 , we construct G2 by randomly changing a certain number of edges (32 and 36 edges in Figure 5). [sent-217, score-0.221]
74 As it can be observed in Figure 5, the performance of the model including the centrality estimated from X1 is better than the performance of the classical model, both when using just the data X2 and the concatenated data X1 |X2 . [sent-220, score-0.706]
75 55 35 40 45 k2 50 55 60 35 40 45 k2 50 55 60 Figure 5: True positive edge rate when estimating the network G2 vs amount of data. [sent-228, score-0.243]
76 In blue, the basic joint model using only X2 , in red using the concatenation of X1 and X2 , and in black the model (2) using only X2 with centrality estimated from X1 as prior. [sent-229, score-0.813]
77 In this example we show how the centrality constraint can help to understand these relationships with limited data on times of crisis and times of stability. [sent-236, score-0.717]
78 UK US IR FN CA SW FR LS Model (1) Model (2) GE SP GR IT BE PO NE AT HK JP AU Figure 6: Countries network learned with the centrality model. [sent-249, score-0.785]
79 Motif Detection in Escherichia Coli Along this section and the following one, we use as base graph the actual genetic regulation network of the E. [sent-262, score-0.345]
80 For the number of samples k varying from 30 to 120, we simulated data X from GE and reconstructed the graph using the joint model (1) and the iterative method (3). [sent-266, score-0.251]
81 We then compared the resulting networks to the original one, both in true positive edge rate (recall that this analysis is sufficient since the total number of edges is made constant), and number of motifs correctly detected. [sent-267, score-0.717]
82 The numerical results are shown in Figure 7, where it can be seen that model (3) correctly detect more motifs, with better TP vs FP motif rate, and without detriment of the true positive edge rate. [sent-268, score-0.285]
83 3 Centrality + Motif Detection The simplicity of the proposed models allows to combine them with other existing network estimation extensions. [sent-271, score-0.181]
84 We now show the performance of the two models here presented combined (centrality and motifs constraints), tested on the Escherichia coli network. [sent-272, score-0.529]
85 Middle: TP motif rate (motifs correctly detected over the total number of motifs in GE ). [sent-288, score-0.693]
86 Right: Positive predictive value (motifs correctly detected over the total number of motifs in the inferred graph). [sent-289, score-0.528]
87 We first estimate the centrality from the data, as in Section 5. [sent-290, score-0.669]
88 1 This information can be used to modify the centrality value for these two nodes, by replacing them by the two highest centrality values typical of scalefree networks (Newman, 2010). [sent-293, score-1.436]
89 For the fixed network GE , we simulated data of different sizes k and reconstructed the graph with the model (1) and with the combination of models (2) and (3). [sent-294, score-0.311]
90 Again, we compared the TP edge rates, the percentage of motifs detected, and the TP/FP motifs rate. [sent-295, score-0.885]
91 Numerical results are shown in Figure 8, where it can be seen that, in addition to the motif detection improvement, now the edge rate is also better. [sent-296, score-0.321]
92 The combination of the proposed extensions is capable of detecting more motifs while also improving the accuracy of the detected edges. [sent-312, score-0.476]
93 The first one incorporates topological information to the optimization, allowing to control the graph centrality. [sent-322, score-0.279]
94 We showed how this model is able to capture the imposed structure when the centrality is provided as prior information, and we also showed how it can improve the performance of the basic joint regression model even when there is no such external information. [sent-323, score-0.805]
95 The second extension favors the appearance of triangles, allowing to better detect motifs in genetic regulatory networks. [sent-324, score-0.633]
96 We combined both models for a better estimation of the Escherichia coli GRN. [sent-325, score-0.194]
97 An algorithm for estimating with high precision the centrality directly from the data would be a great complement to the methods here presented. [sent-327, score-0.712]
98 It is also important to find a model which exploits all the prior information about GRN, including other motifs not explored in this work. [sent-328, score-0.4]
99 Network motifs in the transcriptional regulation network of Escherichia coli. [sent-383, score-0.554]
100 Model selection and estimation in regression with grouped variables. [sent-400, score-0.169]
wordName wordTfidf (topN-words)
[('centrality', 0.669), ('motifs', 0.4), ('topological', 0.168), ('tp', 0.168), ('motif', 0.163), ('eigenvector', 0.132), ('coli', 0.129), ('network', 0.116), ('graph', 0.111), ('topology', 0.099), ('networks', 0.098), ('escherichia', 0.091), ('grn', 0.091), ('regulatory', 0.089), ('edge', 0.085), ('genetic', 0.08), ('node', 0.069), ('hlmann', 0.066), ('xb', 0.066), ('estimation', 0.065), ('bc', 0.063), ('regression', 0.056), ('reconstructed', 0.056), ('joint', 0.056), ('edges', 0.055), ('uruguay', 0.055), ('graphs', 0.053), ('connectivity', 0.051), ('detected', 0.051), ('ge', 0.05), ('favoring', 0.049), ('crisis', 0.048), ('nodes', 0.047), ('newman', 0.044), ('graphical', 0.044), ('matrix', 0.044), ('yuan', 0.043), ('peng', 0.043), ('precision', 0.043), ('rate', 0.042), ('ct', 0.042), ('inferred', 0.04), ('ihler', 0.04), ('meinshausen', 0.04), ('friedman', 0.039), ('regulation', 0.038), ('triangles', 0.038), ('estimated', 0.037), ('correctly', 0.037), ('av', 0.037), ('blica', 0.036), ('conformed', 0.036), ('kalisch', 0.036), ('shashua', 0.036), ('zeitouni', 0.036), ('tibshirani', 0.035), ('adjacency', 0.035), ('penalty', 0.034), ('extension', 0.033), ('stock', 0.032), ('vb', 0.032), ('lin', 0.032), ('barab', 0.032), ('detection', 0.031), ('feedforward', 0.031), ('favors', 0.031), ('universidad', 0.03), ('bii', 0.03), ('hubs', 0.03), ('rep', 0.03), ('transcription', 0.03), ('roc', 0.03), ('market', 0.03), ('genes', 0.029), ('vc', 0.029), ('life', 0.028), ('simulated', 0.028), ('climate', 0.028), ('xtest', 0.028), ('lauritzen', 0.028), ('maybe', 0.028), ('banerjee', 0.027), ('concatenation', 0.027), ('infer', 0.027), ('organisms', 0.026), ('dominant', 0.026), ('triangle', 0.026), ('incorporating', 0.026), ('dashed', 0.026), ('extensions', 0.025), ('promoting', 0.025), ('lots', 0.025), ('fp', 0.025), ('imposing', 0.025), ('constraints', 0.025), ('diagonal', 0.025), ('grouped', 0.024), ('selection', 0.024), ('basic', 0.024), ('patterns', 0.024)]
simIndex simValue paperId paperTitle
same-paper 1 1.0 346 nips-2012-Topology Constraints in Graphical Models
Author: Marcelo Fiori, Pablo Musé, Guillermo Sapiro
Abstract: Graphical models are a very useful tool to describe and understand natural phenomena, from gene expression to climate change and social interactions. The topological structure of these graphs/networks is a fundamental part of the analysis, and in many cases the main goal of the study. However, little work has been done on incorporating prior topological knowledge onto the estimation of the underlying graphical models from sample data. In this work we propose extensions to the basic joint regression model for network estimation, which explicitly incorporate graph-topological constraints into the corresponding optimization approach. The first proposed extension includes an eigenvector centrality constraint, thereby promoting this important prior topological property. The second developed extension promotes the formation of certain motifs, triangle-shaped ones in particular, which are known to exist for example in genetic regulatory networks. The presentation of the underlying formulations, which serve as examples of the introduction of topological constraints in network estimation, is complemented with examples in diverse datasets demonstrating the importance of incorporating such critical prior knowledge. 1
2 0.16215727 253 nips-2012-On Triangular versus Edge Representations --- Towards Scalable Modeling of Networks
Author: Qirong Ho, Junming Yin, Eric P. Xing
Abstract: In this paper, we argue for representing networks as a bag of triangular motifs, particularly for important network problems that current model-based approaches handle poorly due to computational bottlenecks incurred by using edge representations. Such approaches require both 1-edges and 0-edges (missing edges) to be provided as input, and as a consequence, approximate inference algorithms for these models usually require Ω(N 2 ) time per iteration, precluding their application to larger real-world networks. In contrast, triangular modeling requires less computation, while providing equivalent or better inference quality. A triangular motif is a vertex triple containing 2 or 3 edges, and the number of such motifs is 2 Θ( i Di ) (where Di is the degree of vertex i), which is much smaller than N 2 for low-maximum-degree networks. Using this representation, we develop a novel mixed-membership network model and approximate inference algorithm suitable for large networks with low max-degree. For networks with high maximum degree, the triangular motifs can be naturally subsampled in a node-centric fashion, allowing for much faster inference at a small cost in accuracy. Empirically, we demonstrate that our approach, when compared to that of an edge-based model, has faster runtime and improved accuracy for mixed-membership community detection. We conclude with a large-scale demonstration on an N ≈ 280, 000-node network, which is infeasible for network models with Ω(N 2 ) inference cost. 1
3 0.12335485 165 nips-2012-Iterative ranking from pair-wise comparisons
Author: Sahand Negahban, Sewoong Oh, Devavrat Shah
Abstract: The question of aggregating pairwise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g. MSR’s TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining ranking, finding ‘scores’ for each object (e.g. player’s rating) is of interest to understanding the intensity of the preferences. In this paper, we propose a novel iterative rank aggregation algorithm for discovering scores for objects from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with edges present between two objects if they are compared; the scores turn out to be the stationary probability of this random walk. The algorithm is model independent. To establish the efficacy of our method, however, we consider the popular Bradley-Terry-Luce (BTL) model in which each object has an associated score which determines the probabilistic outcomes of pairwise comparisons between objects. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. This, in essence, leads to order-optimal dependence on the number of samples required to learn the scores well by our algorithm. Indeed, the experimental evaluation shows that our (model independent) algorithm performs as well as the Maximum Likelihood Estimator of the BTL model and outperforms a recently proposed algorithm by Ammar and Shah [1]. 1
4 0.10487586 326 nips-2012-Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses
Author: Po-ling Loh, Martin J. Wainwright
Abstract: We investigate a curious relationship between the structure of a discrete graphical model and the support of the inverse of a generalized covariance matrix. We show that for certain graph structures, the support of the inverse covariance matrix of indicator variables on the vertices of a graph reflects the conditional independence structure of the graph. Our work extends results that have previously been established only in the context of multivariate Gaussian graphical models, thereby addressing an open question about the significance of the inverse covariance matrix of a non-Gaussian distribution. Based on our population-level results, we show how the graphical Lasso may be used to recover the edge structure of certain classes of discrete graphical models, and present simulations to verify our theoretical results. 1
5 0.094390005 6 nips-2012-A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation
Author: Aaron Defazio, Tibério S. Caetano
Abstract: A key problem in statistics and machine learning is the determination of network structure from data. We consider the case where the structure of the graph to be reconstructed is known to be scale-free. We show that in such cases it is natural to formulate structured sparsity inducing priors using submodular functions, and we use their Lov´ sz extension to obtain a convex relaxation. For tractable classes a such as Gaussian graphical models, this leads to a convex optimization problem that can be efficiently solved. We show that our method results in an improvement in the accuracy of reconstructed networks for synthetic data. We also show how our prior encourages scale-free reconstructions on a bioinfomatics dataset.
6 0.086999975 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs
7 0.086641558 327 nips-2012-Structured Learning of Gaussian Graphical Models
8 0.080989346 199 nips-2012-Link Prediction in Graphs with Autoregressive Features
9 0.076503813 269 nips-2012-Persistent Homology for Learning Densities with Bounded Support
10 0.07353504 147 nips-2012-Graphical Models via Generalized Linear Models
11 0.068108313 180 nips-2012-Learning Mixtures of Tree Graphical Models
12 0.066784546 69 nips-2012-Clustering Sparse Graphs
13 0.066298008 317 nips-2012-Smooth-projected Neighborhood Pursuit for High-dimensional Nonparanormal Graph Estimation
14 0.062735595 186 nips-2012-Learning as MAP Inference in Discrete Graphical Models
15 0.061935458 298 nips-2012-Scalable Inference of Overlapping Communities
16 0.061433796 164 nips-2012-Iterative Thresholding Algorithm for Sparse Inverse Covariance Estimation
17 0.061111394 312 nips-2012-Simultaneously Leveraging Output and Task Structures for Multiple-Output Regression
18 0.060122706 7 nips-2012-A Divide-and-Conquer Method for Sparse Inverse Covariance Estimation
19 0.056638673 10 nips-2012-A Linear Time Active Learning Algorithm for Link Classification
20 0.056247711 156 nips-2012-Identifiability and Unmixing of Latent Parse Trees
topicId topicWeight
[(0, 0.157), (1, 0.057), (2, 0.011), (3, -0.044), (4, -0.034), (5, 0.018), (6, -0.017), (7, -0.088), (8, -0.147), (9, 0.064), (10, -0.037), (11, -0.024), (12, 0.012), (13, 0.018), (14, 0.02), (15, 0.016), (16, 0.075), (17, 0.015), (18, -0.03), (19, -0.027), (20, -0.011), (21, -0.006), (22, 0.034), (23, -0.017), (24, 0.001), (25, -0.083), (26, 0.044), (27, 0.071), (28, -0.055), (29, -0.118), (30, -0.058), (31, 0.018), (32, -0.085), (33, -0.013), (34, 0.093), (35, -0.094), (36, 0.058), (37, 0.035), (38, 0.062), (39, -0.032), (40, -0.06), (41, -0.016), (42, -0.06), (43, -0.137), (44, -0.034), (45, 0.079), (46, 0.124), (47, -0.002), (48, -0.008), (49, -0.056)]
simIndex simValue paperId paperTitle
same-paper 1 0.92841244 346 nips-2012-Topology Constraints in Graphical Models
Author: Marcelo Fiori, Pablo Musé, Guillermo Sapiro
Abstract: Graphical models are a very useful tool to describe and understand natural phenomena, from gene expression to climate change and social interactions. The topological structure of these graphs/networks is a fundamental part of the analysis, and in many cases the main goal of the study. However, little work has been done on incorporating prior topological knowledge onto the estimation of the underlying graphical models from sample data. In this work we propose extensions to the basic joint regression model for network estimation, which explicitly incorporate graph-topological constraints into the corresponding optimization approach. The first proposed extension includes an eigenvector centrality constraint, thereby promoting this important prior topological property. The second developed extension promotes the formation of certain motifs, triangle-shaped ones in particular, which are known to exist for example in genetic regulatory networks. The presentation of the underlying formulations, which serve as examples of the introduction of topological constraints in network estimation, is complemented with examples in diverse datasets demonstrating the importance of incorporating such critical prior knowledge. 1
2 0.82615793 253 nips-2012-On Triangular versus Edge Representations --- Towards Scalable Modeling of Networks
Author: Qirong Ho, Junming Yin, Eric P. Xing
Abstract: In this paper, we argue for representing networks as a bag of triangular motifs, particularly for important network problems that current model-based approaches handle poorly due to computational bottlenecks incurred by using edge representations. Such approaches require both 1-edges and 0-edges (missing edges) to be provided as input, and as a consequence, approximate inference algorithms for these models usually require Ω(N 2 ) time per iteration, precluding their application to larger real-world networks. In contrast, triangular modeling requires less computation, while providing equivalent or better inference quality. A triangular motif is a vertex triple containing 2 or 3 edges, and the number of such motifs is 2 Θ( i Di ) (where Di is the degree of vertex i), which is much smaller than N 2 for low-maximum-degree networks. Using this representation, we develop a novel mixed-membership network model and approximate inference algorithm suitable for large networks with low max-degree. For networks with high maximum degree, the triangular motifs can be naturally subsampled in a node-centric fashion, allowing for much faster inference at a small cost in accuracy. Empirically, we demonstrate that our approach, when compared to that of an edge-based model, has faster runtime and improved accuracy for mixed-membership community detection. We conclude with a large-scale demonstration on an N ≈ 280, 000-node network, which is infeasible for network models with Ω(N 2 ) inference cost. 1
3 0.80940157 132 nips-2012-Fiedler Random Fields: A Large-Scale Spectral Approach to Statistical Network Modeling
Author: Antonino Freno, Mikaela Keller, Marc Tommasi
Abstract: Statistical models for networks have been typically committed to strong prior assumptions concerning the form of the modeled distributions. Moreover, the vast majority of currently available models are explicitly designed for capturing some specific graph properties (such as power-law degree distributions), which makes them unsuitable for application to domains where the behavior of the target quantities is not known a priori. The key contribution of this paper is twofold. First, we introduce the Fiedler delta statistic, based on the Laplacian spectrum of graphs, which allows to dispense with any parametric assumption concerning the modeled network properties. Second, we use the defined statistic to develop the Fiedler random field model, which allows for efficient estimation of edge distributions over large-scale random networks. After analyzing the dependence structure involved in Fiedler random fields, we estimate them over several real-world networks, showing that they achieve a much higher modeling accuracy than other well-known statistical approaches.
4 0.70967174 327 nips-2012-Structured Learning of Gaussian Graphical Models
Author: Karthik Mohan, Mike Chung, Seungyeop Han, Daniela Witten, Su-in Lee, Maryam Fazel
Abstract: We consider estimation of multiple high-dimensional Gaussian graphical models corresponding to a single set of nodes under several distinct conditions. We assume that most aspects of the networks are shared, but that there are some structured differences between them. Specifically, the network differences are generated from node perturbations: a few nodes are perturbed across networks, and most or all edges stemming from such nodes differ between networks. This corresponds to a simple model for the mechanism underlying many cancers, in which the gene regulatory network is disrupted due to the aberrant activity of a few specific genes. We propose to solve this problem using the perturbed-node joint graphical lasso, a convex optimization problem that is based upon the use of a row-column overlap norm penalty. We then solve the convex problem using an alternating directions method of multipliers algorithm. Our proposal is illustrated on synthetic data and on an application to brain cancer gene expression data. 1
5 0.68944305 298 nips-2012-Scalable Inference of Overlapping Communities
Author: Prem Gopalan, Sean Gerrish, Michael Freedman, David M. Blei, David M. Mimno
Abstract: We develop a scalable algorithm for posterior inference of overlapping communities in large networks. Our algorithm is based on stochastic variational inference in the mixed-membership stochastic blockmodel (MMSB). It naturally interleaves subsampling the network with estimating its community structure. We apply our algorithm on ten large, real-world networks with up to 60,000 nodes. It converges several orders of magnitude faster than the state-of-the-art algorithm for MMSB, finds hundreds of communities in large real-world networks, and detects the true communities in 280 benchmark networks with equal or better accuracy compared to other scalable algorithms. 1
6 0.61351466 326 nips-2012-Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses
7 0.5767439 194 nips-2012-Learning to Discover Social Circles in Ego Networks
8 0.57564098 10 nips-2012-A Linear Time Active Learning Algorithm for Link Classification
9 0.56778926 309 nips-2012-Semi-supervised Eigenvectors for Locally-biased Learning
10 0.53201056 199 nips-2012-Link Prediction in Graphs with Autoregressive Features
11 0.52157366 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs
12 0.52104521 180 nips-2012-Learning Mixtures of Tree Graphical Models
13 0.51262969 337 nips-2012-The Lovász ϑ function, SVMs and finding large dense subgraphs
14 0.50038224 6 nips-2012-A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation
15 0.4986729 345 nips-2012-Topic-Partitioned Multinetwork Embeddings
16 0.4874129 165 nips-2012-Iterative ranking from pair-wise comparisons
17 0.48074791 157 nips-2012-Identification of Recurrent Patterns in the Activation of Brain Networks
18 0.47549841 182 nips-2012-Learning Networks of Heterogeneous Influence
19 0.47403023 317 nips-2012-Smooth-projected Neighborhood Pursuit for High-dimensional Nonparanormal Graph Estimation
20 0.47062781 103 nips-2012-Distributed Probabilistic Learning for Camera Networks with Missing Data
topicId topicWeight
[(0, 0.042), (9, 0.017), (11, 0.011), (14, 0.014), (17, 0.015), (21, 0.02), (38, 0.12), (39, 0.027), (42, 0.019), (54, 0.024), (55, 0.037), (62, 0.215), (74, 0.073), (76, 0.158), (80, 0.094), (92, 0.03)]
simIndex simValue paperId paperTitle
same-paper 1 0.81934279 346 nips-2012-Topology Constraints in Graphical Models
Author: Marcelo Fiori, Pablo Musé, Guillermo Sapiro
Abstract: Graphical models are a very useful tool to describe and understand natural phenomena, from gene expression to climate change and social interactions. The topological structure of these graphs/networks is a fundamental part of the analysis, and in many cases the main goal of the study. However, little work has been done on incorporating prior topological knowledge onto the estimation of the underlying graphical models from sample data. In this work we propose extensions to the basic joint regression model for network estimation, which explicitly incorporate graph-topological constraints into the corresponding optimization approach. The first proposed extension includes an eigenvector centrality constraint, thereby promoting this important prior topological property. The second developed extension promotes the formation of certain motifs, triangle-shaped ones in particular, which are known to exist for example in genetic regulatory networks. The presentation of the underlying formulations, which serve as examples of the introduction of topological constraints in network estimation, is complemented with examples in diverse datasets demonstrating the importance of incorporating such critical prior knowledge. 1
2 0.79183996 160 nips-2012-Imitation Learning by Coaching
Author: He He, Jason Eisner, Hal Daume
Abstract: Imitation Learning has been shown to be successful in solving many challenging real-world problems. Some recent approaches give strong performance guarantees by training the policy iteratively. However, it is important to note that these guarantees depend on how well the policy we found can imitate the oracle on the training data. When there is a substantial difference between the oracle’s ability and the learner’s policy space, we may fail to find a policy that has low error on the training set. In such cases, we propose to use a coach that demonstrates easy-to-learn actions for the learner and gradually approaches the oracle. By a reduction of learning by demonstration to online learning, we prove that coaching can yield a lower regret bound than using the oracle. We apply our algorithm to cost-sensitive dynamic feature selection, a hard decision problem that considers a user-specified accuracy-cost trade-off. Experimental results on UCI datasets show that our method outperforms state-of-the-art imitation learning methods in dynamic feature selection and two static feature selection methods. 1
3 0.7904526 38 nips-2012-Algorithms for Learning Markov Field Policies
Author: Abdeslam Boularias, Jan R. Peters, Oliver B. Kroemer
Abstract: We use a graphical model for representing policies in Markov Decision Processes. This new representation can easily incorporate domain knowledge in the form of a state similarity graph that loosely indicates which states are supposed to have similar optimal actions. A bias is then introduced into the policy search process by sampling policies from a distribution that assigns high probabilities to policies that agree with the provided state similarity graph, i.e. smoother policies. This distribution corresponds to a Markov Random Field. We also present forward and inverse reinforcement learning algorithms for learning such policy distributions. We illustrate the advantage of the proposed approach on two problems: cart-balancing with swing-up, and teaching a robot to grasp unknown objects. 1
4 0.73267728 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs
Author: Anima Anandkumar, Ragupathyraj Valluvan
Abstract: Graphical model selection refers to the problem of estimating the unknown graph structure given observations at the nodes in the model. We consider a challenging instance of this problem when some of the nodes are latent or hidden. We characterize conditions for tractable graph estimation and develop efficient methods with provable guarantees. We consider the class of Ising models Markov on locally tree-like graphs, which are in the regime of correlation decay. We propose an efficient method for graph estimation, and establish its structural consistency −δη(η+1)−2 when the number of samples n scales as n = Ω(θmin log p), where θmin is the minimum edge potential, δ is the depth (i.e., distance from a hidden node to the nearest observed nodes), and η is a parameter which depends on the minimum and maximum node and edge potentials in the Ising model. The proposed method is practical to implement and provides flexibility to control the number of latent variables and the cycle lengths in the output graph. We also present necessary conditions for graph estimation by any method and show that our method nearly matches the lower bound on sample requirements. Keywords: Graphical model selection, latent variables, quartet methods, locally tree-like graphs. 1
5 0.72929794 188 nips-2012-Learning from Distributions via Support Measure Machines
Author: Krikamol Muandet, Kenji Fukumizu, Francesco Dinuzzo, Bernhard Schölkopf
Abstract: This paper presents a kernel-based discriminative learning framework on probability measures. Rather than relying on large collections of vectorial training examples, our framework learns using a collection of probability distributions that have been constructed to meaningfully represent training data. By representing these probability distributions as mean embeddings in the reproducing kernel Hilbert space (RKHS), we are able to apply many standard kernel-based learning techniques in straightforward fashion. To accomplish this, we construct a generalization of the support vector machine (SVM) called a support measure machine (SMM). Our analyses of SMMs provides several insights into their relationship to traditional SVMs. Based on such insights, we propose a flexible SVM (FlexSVM) that places different kernel functions on each training example. Experimental results on both synthetic and real-world data demonstrate the effectiveness of our proposed framework. 1
6 0.72875357 355 nips-2012-Truncation-free Online Variational Inference for Bayesian Nonparametric Models
7 0.72768313 354 nips-2012-Truly Nonparametric Online Variational Inference for Hierarchical Dirichlet Processes
8 0.7273683 111 nips-2012-Efficient Sampling for Bipartite Matching Problems
9 0.72707933 168 nips-2012-Kernel Latent SVM for Visual Recognition
10 0.72682488 209 nips-2012-Max-Margin Structured Output Regression for Spatio-Temporal Action Localization
11 0.72652531 232 nips-2012-Multiplicative Forests for Continuous-Time Processes
12 0.72628391 210 nips-2012-Memorability of Image Regions
13 0.72622782 274 nips-2012-Priors for Diversity in Generative Latent Variable Models
14 0.72521329 83 nips-2012-Controlled Recognition Bounds for Visual Learning and Exploration
15 0.72506249 277 nips-2012-Probabilistic Low-Rank Subspace Clustering
16 0.72463036 316 nips-2012-Small-Variance Asymptotics for Exponential Family Dirichlet Process Mixture Models
17 0.72450995 197 nips-2012-Learning with Recursive Perceptual Representations
18 0.72325516 144 nips-2012-Gradient-based kernel method for feature extraction and variable selection
19 0.72307146 180 nips-2012-Learning Mixtures of Tree Graphical Models
20 0.72224766 284 nips-2012-Q-MKL: Matrix-induced Regularization in Multi-Kernel Learning with Applications to Neuroimaging