| 1. |
- Hermansson, Linus, 1989, et al.
(författare)
-
Entity disambiguation in anonymized graphs using graph kernels
- 2013
-
Ingår i: 22nd ACM International Conference on Information and Knowledge Management, CIKM 2013; San Francisco, CA; United States; 27 October 2013 through 1 November 2013. - New York, New York, USA : ACM Press. - 9781450322638 ; , s. 1037-1046
-
Konferensbidrag (refereegranskat)abstract
- This paper presents a novel method for entity disambiguation in anonymized graphs using local neighborhood structure. Most existing approaches leverage node information, which might not be available in several contexts due to privacy concerns, or information about the sources of the data. We consider this problem in the supervised setting where we are provided only with a base graph and a set of nodes labelled as ambiguous or unambiguous. We characterize the similarity between two nodes based on their local neighborhood structure using graph kernels; and solve the resulting classification task using SVMs. We give empirical evidence on two real-world datasets, comparing our approach to a state-of-the-art method, highlighting the advantages of our approach. We show that using less information, our method is significantly better in terms of either speed or accuracy or both. We also present extensions of two existing graphs kernels, namely, the direct product kernel and the shortest-path kernel, with significant improvements in accuracy. For the direct product kernel, our extension also provides significant computational benefits. Moreover, we design and implement the algorithms of our method to work in a distributed fashion using the GraphLab framework, ensuring high scalability.
|
|
| 2. |
- Jethava, Vinay, 1982, et al.
(författare)
-
Computational approaches for reconstruction of time-varying biological networks from omics data
- 2013
-
Ingår i: Systems Biology: Integrative Biology and Simulation Tools. - Dordrecht : Springer Netherlands. ; , s. 209-239
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- This chapter presents a survey of recent methods for reconstruction of time-varying biological networks such as gene interaction networks based on time series node observations (e.g. gene expressions) from a modeling perspective. Time series gene expression data has been extensively used for analysis of gene interaction networks, and studying the influence of regulatory relationships on different phenotypes. Traditional correlation and regression based methods have focussed on identifying a single interaction network based on time series data. However, interaction networks vary over time and in response to environmental and genetic stress during the course of the experiment. Identifying such time-varying networks promises new insight into transient interactions and their role in the biological process. A key challenge in inferring such networks is the problem of high-dimensional data i.e. the number of unknowns p is much larger than the number of observations n. We discuss the computational aspects of this problem and examine recent methods that have addressed this problem. These methods have modeled the relationship between the latent regulatory network and the observed time series data using the framework of probabilistic graphical models. A key advantage of this approach is natural interpretability of network reconstruction results; and easy incorporation of domain knowledge into the model. We also discuss methods that have addressed the problem of inferring such time-varying regulatory networks by integrating multiple sources or experiments including time series data from multiple perturbed networks. Finally, we mention software tools that implement some of the methods discussed in this chapter. With next generation sequencing promising yet further growth in publicly available -omics data, the potential of such methods is significant.
|
|
| 3. |
- Jethava, Vinay, 1982
(författare)
-
Integrative Analysis of Dynamic Networks
- 2014
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Networks play a central role in several disciplines such as computational biology, social network analysis, transportationplanning and many others; and consequently, several methods have been developed for network analysis. However, in many cases, the study of a single network is insufficient to discover patterns with multiple facets and subtlesignals. Integrative analysis is necessary in order to fuse weak informationpresent in multiple networks into a more confident prediction, especially in domains where there are diverse modes of data acquisition e.g.~with modernbiological technologies. This is further complicated by the fact that most real-world networks are inherentlydynamic in nature. Discerning how networks evolve over time iscrucial to unraveling the underlying phenomenon governing thesystem. Though network science has grown to include advances from diverse fields ranging from classical results in graph theory and approximation algorithms to newer methods focussed on study of real-world networks, integrative analysis of multiple dynamic networks is yet to be fully explored. This thesis makes two-fold contribution in this area. The first part of this thesis presents work aimed at integrative analysis of multiplenetworks reflecting the diverse relationshipsamong a common set of actors or nodes. We make the connection between Lovasz theta function, a celebrated result in graph theory, and Kernel methods inmachine learning. This allows us to develop new algorithms forclassical graph-theoretic problems like planted clique recovery, graphcoloring and max k-cut. We also present a new scalable method for discoveringcommon dense subgraphs from multiple networks, with significantcomputational advantage over previous state-of-the-art enumerativeapproaches. Motivated by the SVM-theta connection, we design two new ``global'' graph kernels which can be used for graph classification. The kernelscapture global graph properties like girth, while being competitivewith existing ``local'' graph kernels. The second part of this thesis investigates the problem of learning time-varying interactionsbased on node observation data using the framework of probabilisticgraphical models. We explore two facets of this problem: modelling the influenceof gene function on dynamic gene-gene interactions; and, capturinghigher-order time-varying networks in a transport application.
|
|
| 4. |
- Jethava, Vinay, 1982
(författare)
-
Learning time-varying interaction networks
- 2013
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Most biological systems consist of several subcomponents whichinteract with each other. These interactions govern the overall behaviourof the system; and in turn vary over time and in response to internaland external stress during the course of an experiment. Identifying such time-varying networks promises new insight into transient interactionsand their role in the biological process. Traditional methods havefocussed on identifying a single interaction network based on time series data, ignoring the dynamic rewiring ofthe underlying network.This thesis studies the problem of inferring time-varying interactionsin gene interaction networks based on gene microarray expressiondata. With the advent of next generation sequencing techologies,the amount of publicly available microarray expression data as well as other omicsdata has grown tremendously. Further, the microarray data is often generatedfrom different experimental conditions or under networkperturbations. One of the current challenges in systems biology isintegration of data generated from different experimental conditionsand under different stresses towards understanding of the dynamicinteractome. NETGEM, the first study included in this thesis describes a method for inference oftime-varying gene interaction network based on microarray expressiondata under network perturbation. The method presents a probabilistic generativemodel under the assumption that the changes in the interactionnetwork are caused by the changing functional roles of the interaction genesduring the course of a biological process. This is used to infertime-varying interactions for a perturbation study in {\emSaccharomyces cerevisiae\/}~(Baker's Yeast) under nutrient stress. Theinferred network agrees with experimental evidence aswell as identifying key transient interactions during the course of the experiment. In the subsequent study, we present a survey chapter describing current approaches forinference of time-varying biological networks based on nodeobservations. We give an overview of different methods in terms of theunderlying model assumptions and applicability under differentconditions. We also describe how recent advances in theory ofcompressed sensing have led to development of new network inference methods with mild assumptions on network dynamics.
|
|
| 5. |
- Jethava, Vinay, 1982, et al.
(författare)
-
Lovasz theta function, SVMs and Finding Dense Subgraphs
- 2013
-
Ingår i: Journal of machine learning research. - 1532-4435 .- 1533-7928. ; 14, s. 3495-3536
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we establish that the Lovasz theta function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM-theta graphs, on which Lovasz theta function can be approximated well by a Support vector machine (SVM). We show that Erdos-Renyi random G(n, p) graphs are SVM-theta graphs for log(4)n/n <= p < 1. Even if we embed a large clique of size Theta(root np/1-p) in a G(n, p) graph the resultant graph still remains a SVM-theta graph. This immediately suggests an SVM based algorithm for recovering a large planted clique in random graphs. Associated with the theta function is the notion of orthogonal labellings. We introduce common orthogonal labellings which extends the idea of orthogonal labellings to multiple graphs. This allows us to propose a Multiple Kernel learning (MKL) based solution which is capable of identifying a large common dense subgraph in multiple graphs. Both in the planted clique case and common subgraph detection problem the proposed solutions beat the state of the art by an order of magnitude.
|
|
| 6. |
- Jethava, Vinay, 1982, et al.
(författare)
-
Lovasz θ, SVMs and applications
- 2013
-
Ingår i: 2013 IEEE Information Theory Workshop - ITW 2013, Seville, Spain, 9-13 September 2013. - 9781479913237 ; , s. 1-5
-
Konferensbidrag (refereegranskat)abstract
- Lovász introduced the theta function in his seminal paper [23] giving his celebrated solution to the problem of computing the Shannon capacity of the pentagon. Since then, the Lovász theta function has come to play a central role in information theory, graph theory and combinatorial optimization [11, 10], indeed Goemans [10] was led to remark: “it seems all paths lead to ϑ!”. The definition of the theta function also gives an elegant geometrical representation of the graph via an embedding in a spherical cap on the unit sphere which has many applications in graph theory and machine learning, some of them perhaps not yet fully appreciated. It is one of the goals of this paper to highlight how the Lovász embedding is a powerful and unifying tool in diverse graph theory and data mining applications.
|
|
| 7. |
- Jethava, Vinay, 1982, et al.
(författare)
-
NETGEM: Network Embedded Temporal GEnerative Model for gene expression data
- 2011
-
Ingår i: BMC Bioinformatics. - : Springer Science and Business Media LLC. - 1471-2105. ; 12
-
Tidskriftsartikel (refereegranskat)abstract
- Background: Temporal analysis of gene expression data has been limited to identifying genes whose expression varies with time and/or correlation between genes that have similar temporal profiles. Often, the methods do not consider the underlying network constraints that connect the genes. It is becoming increasingly evident that interactions change substantially with time. Thus far, there is no systematic method to relate the temporal changes in gene expression to the dynamics of interactions between them. Information on interaction dynamics would open up possibilities for discovering new mechanisms of regulation by providing valuable insight into identifying time-sensitive interactions as well as permit studies on the effect of a genetic perturbation.Results: We present NETGEM, a tractable model rooted in Markov dynamics, for analyzing the dynamics of the interactions between proteins based on the dynamics of the expression changes of the genes that encode them. The model treats the interaction strengths as random variables which are modulated by suitable priors. This approach is necessitated by the extremely small sample size of the datasets, relative to the number of interactions. The model is amenable to a linear time algorithm for efficient inference. Using temporal gene expression data, NETGEM was successful in identifying (i) temporal interactions and determining their strength, (ii) functional categories of the actively interacting partners and (iii) dynamics of interactions in perturbed networks.Conclusions: NETGEM represents an optimal trade-off between model complexity and data requirement. It was able to deduce actively interacting genes and functional categories from temporal gene expression data. It permits inference by incorporating the information available in perturbed networks. Given that the inputs to NETGEM are only the network and the temporal variation of the nodes, this algorithm promises to have widespread applications, beyond biological systems.
|
|
| 8. |
- Jethava, Vinay, 1982, et al.
(författare)
-
Scalable multi-dimensional user intent identification using tree structured distributions
- 2011
-
Ingår i: SIGIR'11 - Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. - New York, NY, USA : ACM. - 9781450309349 ; , s. 395-404
-
Konferensbidrag (refereegranskat)abstract
- The problem of identifying user intent has received considerable attention in recent years, particularly in the context of improving the search experience via query contextualization. Intent can be characterized by multiple dimensions, which are often not observed from query words alone. Accurate identification of Intent from query words remains a challenging problem primarily because it is extremely difficult to discover these dimensions. The problem is often significantly compounded due to lack of representative training sample. We present a generic, extensible framework for learning the multi-dimensional representation of user intent from the query words. The approach models the latent relationships between facets using tree structured distribution which leads to an efficient and convergent algorithm, FastQ, for identifying the multi-faceted intent of users based on just the query words. We also incorporated WordNet to extend the system capabilities to queries which contain words that do not appear in the training data. Empirical results show that FastQ yields accurate identification of intent when compared to a gold standard.
|
|
| 9. |
- Jethava, Vinay, 1982, et al.
(författare)
-
The Lovász v function, SVMs and finding large dense subgraphs
- 2012
-
Ingår i: 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012, Lake Tahoe, United States, 3-6 December 2012. - 1049-5258. - 9781627480031 ; 2, s. 1160-1168
-
Konferensbidrag (refereegranskat)abstract
- The Lovász v function of a graph, a fundamental tool in combinatorial optimization and approximation algorithms, is computed by solving a SDP. In this paper we establish that the Lovász v function is equivalent to a kernel learning problem related to one class SVM. This interesting connection opens up many opportunities bridging graph theoretic algorithms and machine learning. We show that there exist graphs, which we call SVM - v graphs, on which the Lovász v function can be approximated well by a one-class SVM. This leads to novel use of SVM techniques for solving algorithmic problems in large graphs e.g. identifying a planted clique of size Θ( √n) in a random graph G(n; 1/2 ). A classic approach for this problem involves computing the v function, however it is not scalable due to SDP computation. We show that the random graph with a -planted clique is an example of SVM - v graph. As a consequence a SVM based approach easily identifies the clique in large graphs and is competitive with the state-of-the-art. We introduce the notion of common orthogonal labelling and show that it can be computed by solving a Multiple Kernel learning problem. It is further shown that such a labelling is extremely useful in identifying a large common dense subgraph in multiple graphs, which is known to be a computationally difficult problem. The proposed algorithm achieves an order of magnitude scalability compared to state of the art methods.
|
|
| 10. |
- Johansson, Fredrik, 1988, et al.
(författare)
-
DLOREAN: Dynamic Location-aware Reconstruction of multiway Networks
- 2013
-
Ingår i: 2013 13th IEEE International Conference on Data Mining Workshops, ICDMW 2013; Dallas, TX; United States; 7 December 2013 through 10 December 2013. ; , s. 1012-1019
-
Konferensbidrag (refereegranskat)abstract
- This paper presents a method for learning time-varying higher-order interactions based on node observations, with application to short-term traffic forecasting based on traffic flow sensor measurements. We incorporate domain knowledge into the design of a new damped periodic kernel which lever- ages traffic flow patterns towards better structure learning. We introduce location-based regularization for learning models with desirable geographical properties (short-range or long-range interactions). We show using experiments on synthetic and real data, that our approach performs better than static methods for reconstruction of multiway interactions, as well as time-varying methods which recover only pair-wise interactions. Further, we show on real traffic data that our model is useful for short-term traffic forecasting, improving over state-of-the-art.
|
|
