Online knowledge libraries refer to the online data warehouses that systematically organize and categorize the knowledge-based information about different kinds of concepts and entities. In the era of big data, the setup of online knowledge libraries is an extremely challenging and laborious task, in terms of efforts, time and expense required in the completion of knowledge entities. Especially nowadays, a large number of new knowledge entities, like movies, are keeping on being produced and coming out at a continuously accelerating speed, which renders the knowledge library setup and completion problem more difficult to resolve manually. In this paper, we will take the online movie knowledge libraries as an example, and study the "Multiple aligned ISomeric Online Knowledge LIbraries Completion problem" (Miso-Klic) problem across multiple online knowledge libraries. Miso-Klic aims at identifying the missing entities for multiple knowledge libraries synergistically and ranking them for editing based on certain ranking criteria. To solve the problem, a thorough investigation of two isomeric online knowledge libraries, Douban and IMDB, have been carried out in this paper. Based on analyses results, a novel deep online knowledge library completion framework "Integrated Deep alignEd Auto-encoder" (IDEA) is introduced to solve the problem. By projecting the entities from multiple isomeric knowledge libraries to a shared feature space, IDEA solves the Miso-Klic problem via three steps: (1) entity feature space unification via embedding, (2) knowledge library fusion based missing entity identification, and (3) missing entity ranking. Extensive experiments done on the real-world online knowledge library dataset have demonstrated the effectiveness of IDEA in addressing the problem.
Other closely related problems to the task studied in this paper include network alignment and network matching. Network alignment problem has also been studied by many works, which was mostly applied to address many applications in bioinformatics, e.g., protein-protein interaction (PPI) network alignment @cite_2 @cite_10 @cite_27 @cite_20 @cite_3 @cite_4 . Most network alignment approaches focus on finding approximate isomorphism between two graphs under unsupervised settings, e.g., @cite_8 @cite_20 @cite_3 . Because the intractability of the problem, existing methods usually rely on practical heuristics to solve the alignment problem @cite_14 @cite_4 . Different from these works, @cite_15 proposed to use belief propagation to solve sparse network alignment problems and Todor proposes a probabilistic biological network alignment algorithm in @cite_22 . Biological networks can be of very large sizes and many scalable alignment methods have been proposed in @cite_23 @cite_17 @cite_5 @cite_12 .
@cite_14 @cite_4 @cite_22 @cite_8 @cite_3 @cite_27 @cite_23 @cite_2 @cite_5 @cite_15 @cite_10 @cite_12 @cite_20 @cite_17
2107427454 2056903220 1518994209 2077237875 2104690989
Background: In addition to component-based comparative approaches, network alignments provide the means to study conserved network topology such as common pathways and more complex network motifs. Yet, unlike in classical sequence alignment, the comparison of networks becomes computationally more challenging, as most meaningful assumptions instantly lead to NPhard problems. Most previous algorithmic work on network alignments is heuristic in nature. Results: We introduce the graph-based maximum structural matching formulation for pairwise global network alignment. We relate the formulation to previous work and prove NP-hardness of the problem. Based on the new formulation we build upon recent results in computational structural biology and present a novel Lagrangian relaxation approach that, in combination with a branch-and-bound method, computes provably optimal network alignments. The Lagrangian algorithm alone is a powerful heuristic method, which produces solutions that are often near-optimal and – unlike those computed by pure heuristics – come with a quality guarantee. Conclusion: Computational experiments on the alignment of protein-protein interaction networks and on the classification of metabolic subnetworks demonstrate that the new method is reasonably fast and has advantages over pure heuristics. Our software tool is freely available as part of the LISA library. Interactions between molecules are probabilistic events. An interaction may or may not happen with some probability, depending on a variety of factors such as the size, abundance, or proximity of the interacting molecules. In this paper, we consider the problem of aligning two biological networks. Unlike existing methods, we allow one of the two networks to contain probabilistic interactions. Allowing interaction probabilities makes the alignment more biologically relevant at the expense of explosive growth in the number of alternative topologies that may arise from different subsets of interactions that take place. We develop a novel method that efficiently and precisely characterizes this massive search space. We represent the topological similarity between pairs of aligned molecules (i.e., proteins) with the help of random variables and compute their expected values. We validate our method showing that, without sacrificing the running time performance, it can produce novel alignments. Our results also demonstrate that our method identifies biologically meaningful mappings under a comprehensive set of criteria used in the literature as well as the statistical coherence measure that we developed to analyze the statistical significance of the similarity of the functions of the aligned protein pairs. We describe an algorithm, IsoRank, for global alignment of two protein-protein interaction (PPI) networks. IsoRank aims to maximize the overall match between the two networks; in contrast, much of previous work has focused on the local alignment problem-- identifying many possible alignments, each corresponding to a local region of similarity. IsoRank is guided by the intuition that a protein should be matched with a protein in the other network if and only if the neighbors of the two proteins can also be well matched. We encode this intuition as an eigenvalue problem, in a manner analogous to Google's PageRank method. We use IsoRank to compute the first known global alignment between the S. cerevisiae and D. melanogaster PPI networks. The common subgraph has 1420 edges and describes conserved functional components between the two species. Comparisons of our results with those of a well-known algorithm for local network alignment indicate that the globally optimized alignment resolves ambiguity introduced by multiple local alignments. Finally, we interpret the results of global alignment to identify functional orthologs between yeast and fly; our functional ortholog prediction method is much simpler than a recently proposed approach and yet provides results that are more comprehensive. Advances in high-throughput technology has led to an increased amount of available data on protein-protein interaction (PPI) data. Detecting and extracting functional modules that are common across multiple networks is an important step towards understanding the role of functional modules and how they have evolved across species. A global protein-protein interaction network alignment algorithm attempts to find such functional orthologs across multiple networks. In this article, we propose a scalable global network alignment algorithm based on clustering methods and graph matching techniques in order to detect conserved interactions while simultaneously attempting to maximize the sequence similarity of nodes involved in the alignment. We present an algorithm for multiple alignments, in which several protein-protein interaction networks are aligned. We empirically evaluated our algorithm on several real biological datasets. We find that our approach offers a significant benefit both in terms of quality as well as speed over the state-of-the-art. We propose a new distributed algorithm for sparse variants of the network alignment problem, which occurs in a variety of data mining areas including systems biology, database matching, and computer vision. Our algorithm uses a belief propagation heuristic and provides near optimal solutions for this NP-hard combinatorial optimization problem. We show that our algorithm is faster and outperforms or ties existing algorithms on synthetic problems, a problem in bioinformatics, and a problem in ontology matching. We also provide a unified framework for studying and comparing all network alignment solvers.