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 2137648512 2949708310 2245073910
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. Motivation: High-throughput methods for detecting molecular interactions have produced large sets of biological network data with much more yet to come. Analogous to sequence alignment, efficient and reliable network alignment methods are expected to improve our understanding of biological systems. Unlike sequence alignment, network alignment is computationally intractable. Hence, devising efficient network alignment heuristics is currently a foremost challenge in computational biology. Results: We introduce a novel network alignment algorithm, called Matching-based Integrative GRAph ALigner (MI-GRAAL), which can integrate any number and type of similarity measures between network nodes (e.g. proteins), including, but not limited to, any topological network similarity measure, sequence similarity, functional similarity and structural similarity. Hence, we resolve the ties in similarity measures and find a combination of similarity measures yielding the largest contiguous (i.e. connected) and biologically sound alignments. MI-GRAAL exposes the largest functional, connected regions of protein–protein interaction (PPI) network similarity to date: surprisingly, it reveals that 77.7 of proteins in the baker's yeast high-confidence PPI network participate in such a subnetwork that is fully contained in the human high-confidence PPI network. This is the first demonstration that species as diverse as yeast and human contain so large, continuous regions of global network similarity. We apply MI-GRAAL's alignments to predict functions of un-annotated proteins in yeast, human and bacteria validating our predictions in the literature. Furthermore, using network alignment scores for PPI networks of different herpes viruses, we reconstruct their phylogenetic relationship. This is the first time that phylogeny is exactly reconstructed from purely topological alignments of PPI networks. Availability: Supplementary files and MI-GRAAL executables: http: bio-nets.doc.ic.ac.uk MI-GRAAL . Contact: natasha@imperial.ac.uk Supplementary information:Supplementary data are available at Bioinformatics online. Network alignment is the problem of matching the nodes of two graphs, maximizing the similarity of the matched nodes and the edges between them. This problem is encountered in a wide array of applications - from biological networks to social networks to ontologies - where multiple networked data sources need to be integrated. Due to the difficulty of the task, an accurate alignment can rarely be found without human assistance. Thus, it is of great practical importance to develop network alignment algorithms that can optimally leverage experts who are able to provide the correct alignment for a small number of nodes. Yet, only a handful of existing works address this active network alignment setting. The majority of the existing active methods focus on absolute queries ("are nodes @math and @math the same or not?"), whereas we argue that it is generally easier for a human expert to answer relative queries ("which node in the set @math is the most similar to node @math ?"). This paper introduces a novel relative-query strategy, TopMatchings, which can be applied on top of any network alignment method that constructs and solves a bipartite matching problem. Our method identifies the most informative nodes to query based on the top- @math matchings of a bipartite graph. We compare the proposed approach to several commonly-used query strategies and perform experiments on both synthetic and real-world datasets. Our matching-based strategy yields the highest overall performance, outperforming all the baseline methods by more than 15 percentage points in some cases. Network alignment refers to the problem of matching the vertex sets of two unlabeled graphs, which can be viewed as a generalization of the classic graph isomorphism problem. Network alignment has applications in several fields, including social network analysis, privacy, pattern recognition, computer vision, and computational biology. A number of heuristic algorithms have been proposed in these fields. Recent progress in the analysis of network alignment over stochastic models sheds light on the interplay between network parameters and matchability. In this paper, we consider the alignment problem when the two networks overlap only partially, i.e., there exist vertices in one network that have no counterpart in the other. We define a random bigraph model that generates two correlated graphs G1,2; it is parameterized by the expected node overlap t2 and by the expected edge overlap s2. We define a cost function for structural mismatch under a particular alignment, and we identify a threshold for perfect matchability: if the average node degrees of G1,2 grow as ω((s−2t−1 log(n)), then minimization of the proposed cost function results in an alignment which (i) is over exactly the set of shared nodes between G1 and G2, and (ii) agrees with the true matching between these shared nodes. Our result shows that network alignment is fundamentally robust to partial edge and node overlaps.