The task of searching over large keyword graphs aims to identify a subgraph where the nodes collectively cover the input query keywords. Although finding an exact solution to this problem is NP-hard, we address it by proposing a novel graph neural network representation learning technique specifically tailored for graphs with missing information. We propose a novel keyword graph representation learning method that incorporates complementary aspects of graphs: global, local, adjusted, and feature semantics. Considering these multiple aspects, our approach remains robust and resilient to missing information. We adopt and fine-tune a transformer-based model to aggregate the various features of a graph to generate rich representations, recognizing the pivotal role of keywords in this task. We show through experiments on real-world data that our method outperforms the state-of-the-art approaches and is particularly robust in the face of missing values, underscoring its ability to effectively handle incomplete graphs.

Team formation is concerned with the identification of a group of experts who have a high likelihood of effectively collaborating with each other to satisfy a collection of input skills. Solutions to this task have mainly adopted graph operations and at least have the following limitations: (1) they are computationally demanding, as they require finding shortest paths on large collaboration networks; (2) they use various types of heuristics to reduce the exploration space over the collaboration network to become practically feasible; therefore, their results are not necessarily optimal; and (3) they are not well-suited for collaboration network structures given the sparsity of these networks. Our work proposes a variational Bayesian neural network architecture that learns representations for teams whose members have collaborated with each other in the past. The learned representations allow our proposed approach to mine teams that have a past collaborative history and collectively cover the requested desirable set of skills. Through our experiments, we demonstrate that our approach shows stronger performance compared to a range of strong team formation techniques from both quantitative and qualitative perspectives.

In this demonstration paper, we describe iORDER, a tool that identifies implicit domain orders in data, such as Small Medium Large. iORDER extends the machinery of order dependency discovery to identify and rank interesting orders. Using real-world data, we showcase how implicit orders help users interpret the semantics of ordered data, how to interactively validate implicit orders to aid in the discovery process, and how to apply implicit orders to applications including data profiling, data mining and knowledge bases.

Towards better explainability in the field of information retrieval, we present CREDENCE, an interactive tool capable of generating counterfactual explanations for document rankers. Embracing the unique properties of the ranking problem, we present counterfactual explanations in terms of document perturbations, query perturbations, and even other documents. Additionally, users may build and test their own perturbations, and extract insights about their query, documents, and ranker.

Climate-related catastrophes leave people in dire need of aid. A major obstacle in providing help to people is the lack of trust in the aid process. Charity organizations want to ensure that funds and materials reach the intended destinations. Blockchain technology injects trust into business transactions through impeccable record keeping and can alleviate the trust problems in aid delivery. Another major problem in disaster recovery is broken infrastructure (e.g., broken bridges and unavailable roads). Unmanned aerial vehicles (UAV), generally referred to as drones, can address this access problem. In this paper, the authors design a system that uses drone technology for delivery of aid and blockchain technology for the assurance of such delivery. This system records and shares data on the interaction of various participants involved in a disaster aid delivery scenario. The simulation studies validate the applicability of this proposed system showing high throughput and satisfactory performance are attainable with integration of blockchain in large-scale aid delivery.

Most real-world data come with explicitly defined domain orders; e.g., lexicographic for strings, numeric for integers, and chronological for time. Our goal is to discover implicit domain orders that we do not already know; for instance, that the order of months in the Chinese Lunar calendar is Corner$<$Apricot$<$Peach. To do so, we enhance data profiling methods by discovering implicit domain orders in data through order dependencies. We enumerate tractable special cases and show that the general case is NP-complete but can be effectively handled by a SAT solver. We also devise an interestingness measure to rank the discovered implicit domain orders. Based on an extensive suite of experiments with real-world data, we establish the efficacy of our algorithms.

Real graphs often contain edge and node weights, representing, for instance, penalty, distance or uncertainty. We study the problem of keyword search over weighted node-labeled graphs, in which a query consists of a set of keywords and an answer is a subgraph whose nodes contain the keywords. We evaluate answers using three ranking strategies: optimizing edge weights, optimizing node weights, and a bi-objective combination of both node and edge weights. We prove that optimizing node weights and the bi-objective function are NP-hard. We propose an algorithm that optimizes edge weights and has an approximation ratio of two for the unique node enumeration paradigm. To optimize node weights and the bi-objective function, we propose transformations that distribute node weights onto the edges. We then prove that our transformations allow our algorithm to also optimize node weights and the bi-objective function with the same approximation ratio of two. Notably, the proposed transformations are compatible with existing algorithms that only optimize edge weights. We empirically show that in many natural examples, incorporating node weights (both keyword holders and middle nodes) produces more relevant answers than ranking methods based only on edge weights. Extensive experiments over real-life datasets verify the effectiveness and efficiency of our solution.

There is a growing need to find meaningful teams in expert networks such as DBLP and GitHub. However, existing team formation methods, such as those based on shortest paths between experts, may generate weakly-connected teams. We demonstrate RW-Team, a robust team formation framework based on a random walk with restart (RWR). We introduce a greedy algorithm to reduce the search space, and we use a Monte Carlo approximation of RWR to improve performance. To handle large graphs, we implement RW-Team in Apache Spark. The proposed demonstration will allow participants to form teams of researchers having various skill sets and explore connections among team members using several graph visualization techniques.

We present PyTFL, a library written in Python for the team formation task. In team formation task, the main objective is to form a team of experts given a set of skills. We demonstrate an efficient and well-structured open-source toolkit that can easily be imported into Python. Our toolkit incorporates state-of-the-art approaches for team formation, e.g., neural-based team formation, and supports team formation sub-tasks such as collaboration graph preparation, model training and validation, systematic evaluation based on qualitative and quantitative team metrics, and efficient team formation and prediction. While there are strong research papers on the team formation problem, PyTFL is the first toolkit to be publicly released for this purpose.

Order dependencies (ODs) capture relationships between ordered domains of attributes. Approximate ODs (AODs) capture such relationships even when there exist exceptions in the data. During automated discovery of ODs, validation is the process of verifying whether an OD holds. We present an algorithm for validating approximate ODs with significantly improved runtime performance over existing methods for AODs, and prove that it is correct and has optimal runtime. By replacing the validation step in a leading algorithm for approximate OD discovery with ours, we achieve orders-of-magnitude improvements in performance.

Real graphs contain edge and node weights, representing penalty, distance or cost. We study the problem of keyword search in weighted node-labeled graphs, in which a query consists of a set of keywords and an answer is a subgraph. We consider three ranking strategies for answer subgraphs: edge weights, node weights, and a bi-objective combination of both node and edge weights. We propose and experimentally evaluate algorithms that optimize these objectives with an approximation ratio of two.

Given a set of required skills, the objective of the team formation problem is to form a team of experts that cover the required skills. Most existing approaches are based on graph methods, such as minimum-cost spanning trees. These approaches, due to their limited view of the network, fail to capture complex interactions among experts and are computationally intractable. More recent approaches adopt neural architectures to learn a mapping between the skills and experts space. While they are more effective, these techniques face two main limitations: (1) they consider a fixed representation for both skills and experts, and (2) they overlook the significant amount of past collaboration network information. We learn dense representations for skills and experts based on previous collaborations and bootstrap the training process through transfer learning. We also propose to fine-tune the representation of skills and experts while learning the mapping function. Our experiments over the DBLP dataset verify that our proposed architecture is able to outperform the state-of-the-art graph and neural methods over both ranking and quality metrics.

We focus on the composition of teams of experts that collectively cover a set of required skills based on their historical collaboration network and expertise. Prior works are primarily based on the shortest path between experts on the expert collaboration network, and suffer from three major shortcomings: (1) they are computationally expensive due to the complexity of finding paths on large network structures; (2) they use a small portion of the entire historical collaboration network to reduce the search space; hence, may form sub-optimal teams; and, (3) they fall short in sparse networks where the majority of the experts have only participated in a few teams in the past. Instead of forming a large network of experts, we propose to learn relationships among experts and skills through a variational Bayes neural architecture wherein: i) we consider all past team compositions as training instances to predict future teams; ii) we bring scalability for large networks of experts due to the neural architecture; and, iii) we address sparsity by incorporating uncertainty on the neural network's parameters which yields a richer representation and more accurate team composition. We empirically demonstrate how our proposed model outperforms the state-of-the-art approaches in terms of effectiveness and efficiency based on a large DBLP dataset.

Predicting the future link between nodes is a significant problem in social network analysis, known as Link Prediction (LP). Recently, dynamic network link prediction has attracted many researchers due to its valuable real-world applications. However, most methods fail to perform satisfying prediction accuracy in various types of networks because the dynamic LP in evolving networks is struggling with spatial and nonlinear transitional patterns. Besides this, existing methods mostly involve the whole network and target link for the LP process. It leads to high computational costs. This paper aims to address these issues by proposing a novel framework named DLP-LES using deep learning methods. DLP-LES uses common neighbors based subgraph of a target link and learns the transitional pattern of it for a given dynamic network. We extract a set of heuristic features of the evolving subgraph to gather additional information about the target link. In this way, we avoid examining the entire network. Additionally, our model introduces new mechanisms to reduce computational costs. DLP- LES generates a lookup table to keep the required information of links of the network and uses a hashing method to store and fetch link information. We propose an algorithm to construct feature matrices of the evolving subgraph to learn transitional link patterns. Our model transforms the dynamic link prediction to a video classification problem, and uses Convolutional Neural Networks with Long Short-Term Memory neural networks. To verify the effectiveness of DLP-LES, extensive experiments are carried out on five real-world dynamic networks. We compare those results against four network embedding methods and basic heuristic methods.

We present the design of and a demonstration plan for FASTOD, a tool for efficiently discovering (approximate) order dependencies (ODs) from data. FASTOD converts ODs to a novel canonical form which makes it orders of magnitude faster than existing techniques. Using real datasets, we demonstrate how the discovered ODs can help users understand data semantics, identify potential data quality problems, and interactively clean the data. We also demonstrate the effectiveness of our system.

In this paper, a novel knowledge-based evolutionary algorithm is proposed to assemble a team of care providers for patients in community-oriented palliative care. The main objective of this research is to optimize the patient's care services and human resource allocation process. From a system perspective in palliative care, there exists a group of patients with needs who are not able to perform some of their ordinary life activities due to their limited capability, as a consequence of their disease or disorders. On the other hand, we have a group of care providers who are capable, skilled, and ready to provide a wide range of services to the patients to fulfill those needs. This poses the challenge of assigning members to a team of care providers in an optimal manner to help the patient satisfy their needs, while taking into consideration the communication, distance and contact costs. To deal with this problem, we propose a novel algorithm based on a cultural algorithm (CA) as the basis for our model for assembling an optimal team of care providers. The overall goals are to minimize the costs and increase the patient's satisfaction rate. We have evaluated our model using multiple synthetic networks and conducted comparative analysis with other existing methods. The results show that our proposed model can overcome the shortcomings posed by the existing approaches.

Integrity constraints (ICs) are useful for query optimization and for expressing and enforcing application semantics. However, formulating constraints manually requires domain expertise, is prone to human errors, and may be excessively time consuming, especially on large datasets. Hence, proposals for automatic discovery have been made for some classes of ICs, such as functional dependencies (FDs), and recently, order dependencies (ODs). ODs properly subsume FDs, as they can additionally express business rules involving order; e.g., an employee never has a higher salary while paying lower taxes than another employee. We present a new OD discovery algorithm enabled by a novel polynomial mapping to a canonical form of ODs, and a sound and complete set of axioms (inference rules) for canonical ODs. Our algorithm has exponential worst-case time complexity, O (2 | R | ), in the number of attributes | R | and linear complexity in the number of tuples. We prove that it produces a complete and minimal set of ODs. Using real and synthetic datasets, we experimentally show orders-of-magnitude performance improvements over the prior state-of-the-art.

In a node-labeled graph, keyword search finds subtrees of the graph whose nodes contain all of the query keywords. This provides a way to query graph databases that neither requires mastery of a query language such as SPARQL, nor a deep knowledge of the database schema. We demonstrate eGraphSearch, a new system for effective keyword search in graph databases. Previous work ranks answer trees using combinations of structural and content-based metrics, such as path length between keywords or relevance of the labels in the answer tree to the query keywords. However, different nodes in the graph might have different importance, which affects the utility of the answer. In the proposed system, we implemented two new ways to rank keyword search results over graphs: the first one takes node importance into account while the second one is a bi-objective optimization of edge weights and node importance. In the demonstration, participants will execute keyword queries against several popular graph datasets.

Keyword search over relational databases offers an alternative way to SQL to query and explore databases that is effective for lay users who may not be well versed in SQL or the database schema. This becomes more pertinent for databases with large and complex schemas. An answer in this context is a join tree spanning tuples containing the query's keywords. As there are potentially many answers to the query, and the user is often only interested in seeing the top-k answers, how to rank the answers based on their relevance is of paramount importance. We focus on the relevance of join as the fundamental means to rank answers. We devise means to measure relevance of relations and foreign keys in the schema over the information content of the database. This can be done offline with no need for external models. We compare the proposed measures against a gold standard we derive from a real workload over TPC-E and evaluate the effectiveness of our methods. Finally, we test the performance of our measures against existing techniques to demonstrate a marked improvement, and perform a user study to establish naturalness of the ranking of the answers.

Keyword search in relational databases was introduced in the last decade to assist users who are not familiar with a query language, the schema of the database, or the content of the data. An answer is a join tree of tuples that contains the query keywords. When searching a database with a complex schema, there are potentially many answers to the query. Therefore, ranking answers based on their relevance is crucial in this context. Prior work has addressed relevance based on the size of the answer or the IR scores of the tuples. However, this is not sufficient when searching a complex schema. We demonstrate MeanKS, a new system for meaningful keyword search over relational databases. The system first captures the user's interest by determining the roles of the keywords. Then, it uses schema-based ranking to rank join trees that cover the keyword roles. This uses the relevance of relations and foreign-key relationships in the schema over the information content of the database. In the demonstration, attendees can execute queries against the TPC-E warehouse and compare the proposed measures against a gold standard derived from a real workload over TPC-E to test the effectiveness of our methods.

Keyword search over a graph searches for a subgraph that contains a set of query keywords. A problem with most existing keyword search methods is that they may produce duplicate answers that contain the same set of content nodes (i.e., nodes containing a query keyword) although these nodes may be connected differently in different answers. Thus, users may be presented with many similar answers with trivial differences. In addition, some of the nodes in an answer may contain query keywords that are all covered by other nodes in the answer. Removing these nodes does not change the coverage of the answer but can make the answer more compact. The answers in which each content node contains at least one unique query keyword are called minimal answers in this paper. We define the problem of finding duplication-free and minimal answers, and propose algorithms for finding such answers efficiently. Extensive performance studies using two large real data sets confirm the efficiency and effectiveness of the proposed methods.

Given an expert network, we tackle the problem of finding a team of experts that covers a set of required skills and also minimizes the communication cost as well as the personnel cost of the team. Since two costs need to be minimized, this is a bicriteria optimization problem. We show that the problem of minimizing these objectives is NP-hard. We use two approaches to solve this bicriteria optimization problem. In the first approach, we propose several (α, β)-approximation algorithms that receive a budget on one objective and minimizes the other objective within the budget with guaranteed performance bounds. In the second approach, an approximation algorithm is proposed to find a set of Pareto-optimal teams, in which each team is not dominated by other feasible teams in terms of the personnel and communication costs. The proposed approximation algorithms have provable performance bounds. Extensive experiments on real datasets demonstrate the effectiveness and scalability of the proposed algorithms.

A system for efficient keyword search in graphs is demonstrated. The system has two components, a search through only the nodes containing the input keywords for a set of nodes that are close to each other and together cover the input keywords and an exploration for finding how these nodes are related to each other. The system generates all or top-k answers in polynomial delay. Answers are presented to the user according to a ranking criterion so that the answers with nodes closer to each other are presented before the ones with nodes farther away from each other. In addition, the set of answers produced by our system is duplication free. The system uses two methods for presenting the final answer to the user. The presentation methods reveal relationships among the nodes in an answer through a tree or a multi-center graph. We will show that each method has its own advantages and disadvantages. The system is demonstrated using two challenging datasets, very large DBLP and highly cyclic Mondial. Challenges and difficulties in implementing an efficient keyword search system are also demonstrated.

We study the problem of discovering a team of experts from a social network. Given a project whose completion requires a set of skills, our goal is to find a set of experts that together have all of the required skills and also have the minimal communication cost among them. We propose two communication cost functions designed for two types of communication structures. We show that the problem of finding the team of experts that minimizes one of the proposed cost functions is NP-hard. Thus, an approximation algorithm with an approximation ratio of two is designed. We introduce the problem of finding a team of experts with a leader. The leader is responsible for monitoring and coordinating the project, and thus a different communication cost function is used in this problem. To solve this problem, an exact polynomial algorithm is proposed. We show that the total number of teams may be exponential with respect to the number of required skills. Thus, two procedures that produce top-k teams of experts with or without a leader in polynomial delay are proposed. Extensive experiments on real datasets demonstrate the effectiveness and scalability of the proposed methods.

Keyword search over a graph finds a substructure of the graph containing all or some of the input keywords. Most of previous methods in this area find connected minimal trees that cover all the query keywords. Recently, it has been shown that finding subgraphs rather than trees can be more useful and informative for the users. However, the current tree or graph based methods may produce answers in which some content nodes (i.e., nodes that contain input keywords) are not very close to each other. In addition, when searching for answers, these methods may explore the whole graph rather than only the content nodes. This may lead to poor performance in execution time. To address the above problems, we propose the problem of finding r -cliques in graphs. An r -clique is a group of content nodes that cover all the input keywords and the distance between each two nodes is less than or equal to r . An exact algorithm is proposed that finds all r -cliques in the input graph. In addition, an approximation algorithm that produces r -cliques with 2-approximation in polynomial delay is proposed. Extensive performance studies using two large real data sets confirm the efficiency and accuracy of finding r -cliques in graphs.

BACKGROUND: It has been previously shown that palindromic sequences are frequently observed in proteins. However, our knowledge about their evolutionary origin and their possible importance is incomplete. RESULTS: In this work, we tried to revisit this relatively neglected phenomenon. Several questions are addressed in this work. (1) It is known that there is a large chance of finding a palindrome in low complexity sequences (i.e. sequences with extreme amino acid usage bias). What is the role of sequence complexity in the evolution of palindromic sequences in proteins? (2) Do palindromes coincide with conserved protein sequences? If yes, what are the functions of these conserved segments? (3) In case of conserved palindromes, is it always the case that the whole conserved pattern is also symmetrical? (4) Do palindromic protein sequences form regular secondary structures? (5) Does sequence similarity of the two "sides" of a palindrome imply structural similarity? For the first question, we showed that the complexity of palindromic peptides is significantly lower than randomly generated palindromes. Therefore, one can say that palindromes occur frequently in low complexity protein segments, without necessarily having a defined function or forming a special structure. Nevertheless, this does not rule out the possibility of finding palindromes which play some roles in protein structure and function. In fact, we found several palindromes that overlap with conserved protein Blocks of different functions. However, in many cases we failed to find any symmetry in the conserved regions of corresponding Blocks. Furthermore, to answer the last two questions, the structural characteristics of palindromes were studied. It is shown that palindromes may have a great propensity to form alpha-helical structures. Finally, we demonstrated that the two sides of a palindrome generally do not show significant structural similarities. CONCLUSION: We suggest that the puzzling abundance of palindromic sequences in proteins is mainly due to their frequent concurrence with low-complexity protein regions, rather than a global role in the protein function. In addition, palindromic sequences show a relatively high tendency to form helices, which might play an important role in the evolution of proteins that contain palindromes. Moreover, reverse similarity in peptides does not necessarily imply significant structural similarity. This observation rules out the importance of palindromes for forming symmetrical structures. Although palindromes frequently overlap with conserved Blocks, we suggest that palindromes overlap with Blocks only by coincidence, rather than being involved with a certain structural fold or protein domain.

Today's software systems are more frequently composed from preexisting commercial or non-commercial components and connectors. These components provide complex and independent functionality and are engaged in complex interactions. Component-Based Software Engineering (CBSE) is concerned with composing, selecting and designing such components. As the popularity of this approach and hence number of commercially available software components grows, selecting a set of components to satisfy a set of requirements while minimizing cost is becoming more difficult. This problem necessitates the design of efficient algorithms to automate component selection for software developing organizations. We address this challenge through analysis of Component Selection, the NP-complete process of selecting a minimal cost set of components to satisfy a set of objectives. Due to the high order of computational complexity of this problem, we examine approximating solutions that make the component selection process practicable. We adapt a greedy approach and a genetic algorithm to approximate this problem. We examined the performance of studied algorithms on a set of selected ActiveX components. Comparing the results of these two algorithms with the choices made by a group of human experts shows that we obtain better results using these approximation algorithms.