The Group Steiner Tree Problem (GSTP) has been popularly used to formulate graph-based tasks on the Web where the number of groups (i.e., g), e.g., representing the number of keywords in knowledge graph search, is assumed to be small. This assumption never holds in emerging tasks such as the summarization of knowledge graphs, where g represents the number of distinct entity description patterns that increases with graph order (i.e., n) and reaches 105 in practice. Existing algorithms become impractical, since they are optimized for large n but not for large g. In this paper, we devise novel approximation algorithms for GSTP that exhibit scalability in relation to both n and g. When g is large, our algorithms outperform existing algorithms that have a comparable approximation ratio by orders of magnitude in running time, showing their unique ability to practically support such challenging Web applications.

The rapid growth of open and structured RDF data on the Web has promoted the development of dataset search as an important research topic. The core function of existing systems is ad hoc dataset retrieval (AHDR) based on the metadata of datasets, which contains limited information and often suffers from quality issues. To overcome the limitations, in this article, we systematically investigate content-based AHDR to exploit the actual RDF data in datasets. We address three main tasks of content-based AHDR with novel methods for handling the large size and complex structure of RDF data to facilitate dataset retrieval, deduplication, and snippet extraction. These methods are integrated into an online and open-source prototype called Caddie . The effectiveness and practicability of its components are evaluated on a public test collection and by a user study.

Combining semantic information with behavioral data is a crucial research area in recommender systems. A promising approach involves leveraging external knowledge to enrich behavioral-based recommender systems with abundant semantic information. However, this approach faces two primary challenges: (1) denoising raw external knowledge and (2) adapting semantic representations. To address these challenges, we propose exTernal knowledge-enhanced RecommendAtion With LLM assistance (TRAWL). This method utilizes large language models to extract relevant recommendation knowledge from raw external data and employs a contrastive learning strategy for adapter training. Experiments on public datasets and real-world online recommender systems validate the effectiveness of our approach.

The rapid growth of open source machine learning (ML) resources, such as models and datasets, has accelerated IR research. However, existing platforms like Hugging Face do not explicitly utilize structured representations, limiting advanced queries and analyses such as tracing model evolution and recommending relevant datasets. To fill the gap, we construct HuggingKG, the first large-scale knowledge graph built from the Hugging Face community for ML resource management. With 2.6 million nodes and 6.2 million edges, HuggingKG captures domain-specific relations and rich textual attributes. It enables us to further present HuggingBench, a multi-task benchmark with three novel test collections for IR tasks including resource recommendation, classification, and tracing. Our experiments reveal unique characteristics of HuggingKG and the derived tasks. Both resources are publicly available, expected to advance research in open source resource sharing and management.

With the continuous growth of open data on the Web, dataset search has become a prominent specialized retrieval problem to find datasets relevant to a query. Recent solutions rank datasets based on not only their metadata, but also data snippets extracted from their actual data. While the goodness of a data snippet has been studied from various aspects, in this paper we propose to, for the first time, jointly optimize compactness, relevance, representativeness, and cohesiveness in snippet extraction. To extract such multi-objective data snippets, we formulate a new combinatorial optimization problem and design an efficient algorithm with a proved worst-case approximation ratio. We evaluate the data snippets extracted by our algorithm intrinsically through a set of quality metrics and extrinsically by applying them to dataset search.

In light of the growing availability and significance of open data, the problem of dataset search has attracted great attention in the field of information retrieval. Nevertheless, current metadata-based approaches have revealed shortcomings due to the low quality and availability of dataset metadata, while the magnitude and heterogeneity of actual data hindered the development of content-based solutions. To address these challenges, we propose to convert different formats of structured data into a unified form, from which we extract a compact data snippet that indicates the relevance of the whole data. Thanks to its compactness, we feed it into a dense reranker to improve search accuracy. We also convert it back to the original format to be presented for assisting users in relevance judgment. The effectiveness of our approach has been demonstrated by extensive experiments on two test collections for dataset search.

Dataset search, or more specifically, ad hoc dataset retrieval which is a trending specialized IR task, has received increasing attention in both academia and industry. While methods and systems continue evolving, existing test collections for this task exhibit shortcomings, particularly suffering from lexical bias in pooling and limited to keyword-style queries for evaluation. To address these limitations, in this paper, we construct ACORDAR 2.0, a new test collection for this task which is also the largest to date. To reduce lexical bias in pooling, we adapt dense retrieval models to large structured data, using them to find an extended set of semantically relevant datasets to be annotated. To diversify query forms, we employ a large language model to rewrite keyword queries into high-quality question-style queries. We use the test collection to evaluate popular sparse and dense retrieval models to establish a baseline for future studies. The test collection and source code are publicly available.

Knowledge Graph (KG) exploration helps Web users understand the contents of a large and unfamiliar KG and extract relevant insights. The task has recently been formulated as a Quadratic Group Steiner Tree Problem (QGSTP) to search for a semantically cohesive subgraph connecting entities that match query keywords. However, on large graphs, existing algorithms for this NP-hard problem cannot meet the performance need. In this paper, we propose a novel approximation algorithm for QGSTP called HB. It finds and merges an optimal set of paths according to a Hop-Biased objective function, which not only leads to a guaranteed approximation ratio but is also decomposable by paths to enable efficient dynamic programming based search. Accompanied by a set of pruning heuristics, HB outperformed the state of the art by 1-2 orders of magnitude, empirically reducing the average time for answering a query on a million-scale graph from about one minute to one second.

Many questions should be answered by not a single answer but a set of multiple answers. This emerging Multi-Span Reading Comprehension (MSRC) task requires extracting multiple non-contiguous spans from a given context to answer a question. Existing methods extend conventional single-span models to predict the positions of the start and end tokens of answer spans, or predict the beginning-inside-outside tag of each token. Such token-centric paradigms can hardly capture dependencies among span-level answers which are critical to MSRC. In this paper, we propose SpanQualifier, a span-centric scheme where spans, as opposed to tokens, are directly represented and scored to qualify as answers. Explicit span representations enable their interaction which exploits their dependencies to enhance representations. Experiments on three MSRC datasets demonstrate the effectiveness of our span-centric scheme and show that SpanQualifier achieves state-of-the-art results.

Distance computation is a bottleneck that limits the performance of many applications based on knowledge graphs (KGs). One common approach to improving online distance computation is to offline precompute certain information to be stored in an index called distance oracle. However, its effectiveness remains under-studied in the setting where edges are methodologically weighted to capture the structure and semantics of edge types in a KG. To fill the gap, in this paper, we present the first evaluation of representative distance oracles on KGs with commonly used edge weighting schemes. Our negative results and empirical justifications provide insights and a motivation for future studies of this unique setting.

Relevance search over knowledge graphs seeks top-ranked answer entities that are most relevant to a query entity. Since the semantics of relevance varies with the user need and its formalization is difficult for non-experts, existing methods infer semantics from user-provided example answer entities. However, a user may provide very few examples, even none at the beginning of interaction, thereby limiting the effectiveness of such methods. In this paper, we vision a more practical scenario called labeling-based iterative relevance search: instead of effortfully inputting example answer entities, the user effortlessly (e.g., implicitly) labels current answer entities, and is rewarded with improved answer entities in the next iteration. To realize the scenario, our approach TRAVERS incorporates two rankers: a diversity-oriented ranker for supporting cold start and avoiding converging to sub-optimum caused by noisy labels, and a relevance-oriented ranker capable of handling unbalanced labels. Moreover, the two rankers and their combination dynamically evolve over iterations. TRAVERS outperformed a variety of baselines in experiments with simulated and real user behavior.

The Diameter-bounded max-Coverage Group Steiner Tree (DCGST) problem has recently been proposed as an expressive way of formulating keyword-based search and exploration of knowledge graphs. It aims at finding a diameter-bounded tree which covers the most given groups of vertices and has the minimum weight. In contrast to its specialization—the classic Group Steiner Tree (GST) problem which has been extensively studied, the emerging DCGST problem still lacks an efficient algorithm. In this paper, we propose Cba, the first approximation algorithm for the DCGST problem, and we prove its worst-case approximation ratio. Furthermore, we incorporate a best-first search strategy with two pruning methods into PrunedCBA, an improved approximation algorithm. Our extensive experiments on real and synthetic graphs demonstrate the effectiveness and efficiency of PrunedCBA.

Graph-structured data describing entities and their properties has become a notable component of the Web. With the increasing size of data graphs, an entity is often associated with too many property values to be entirely shown to the user, thereby requiring a compact but characteristic summary to present its most distinguishing features. This paper aims to automatically generate such characteristic entity summaries for human users. To achieve it, we exploit the informativeness of property values by analyzing the data graph using information theory. To improve the utility of information carried by a summary, we learn it from a text corpus. To reduce the information redundancy of a summary, we perform logical reasoning and measure similarity with statistical support. We formalize the entity summarization problem considering these factors as combinatorial optimization problems to solve. Experiments based on a real data graph and hand-crafted gold standards show that our approach improves on two state-of-the-art approaches in F-measure by 20.63%-38.79%.

The large volume of open data on the Web is expected to be reused and create value. Finding the right data to reuse is a non-trivial task addressed by the recent dataset search systems, which retrieve datasets relevant to a keyword query. An important component of such systems is snippet generation, extracting data from a retrieved dataset to exemplify its content and explain its relevance to the query. Snippet generation algorithms have emerged but were mainly evaluated by user studies. More efficient and reproducible evaluation methods are needed. To meet this challenge, in this article, we present a set of quality metrics for assessing the usefulness of a snippet from different perspectives, and we select and aggregate them into quality profiles for different stages of a dataset search process. Furthermore, we create a benchmark from thousands of collected real-world data needs and datasets, on which we apply the presented quality metrics and profiles to evaluate snippets generated by two existing algorithms and three adapted algorithms. The results, which are reproducible as they are automatically computed without human interaction, show the pros and cons of the tested algorithms and highlight directions for future research. The benchmark data is publicly available.

Ad hoc dataset retrieval is a trending topic in IR research. Methods and systems are evolving from metadata-based to content-based ones which exploit the data itself for improving retrieval accuracy but thus far lack a specialized test collection. In this paper, we build and release the first test collection for ad hoc content-based dataset retrieval, where content-oriented dataset queries and content-based relevance judgments are annotated by human experts who are assisted with a dashboard designed specifically for comprehensively and conveniently browsing both the metadata and data of a dataset. We conduct extensive experiments on the test collection to analyze its difficulty and provide insights into the underlying task.

A knowledge graph (KG) represents a set of entities and their relations. To explore the content of a large and complex KG, a convenient way is keyword-based querying. Traditional methods assign small weights to salient entities or relations, and answer an exploratory keyword query by computing a group Steiner tree (GST), which is a minimum-weight subgraph that connects all the keywords in the query. Recent studies have suggested improving the semantic cohesiveness of a query answer by minimizing the pairwise semantic distances between the entities in a subgraph, but it remains unclear how to efficiently compute such a semantically cohesive subgraph. In this paper, we formulate it as a quadratic group Steiner tree problem (QGSTP) by extending the classical minimum-weight GST problem which is NP-hard. We design two approximation algorithms for QGSTP and prove their approximation ratios. Furthermore, to improve their practical performance, we present heuristics including pruning and ranking strategies.

Given a large graph representing relations between entities, searching for complex relationships (called semantic associations, or SAs for short) between a set of entities is a common type of information needs in many domains. Further, numerous SAs are often abstracted into a few frequent high-level conceptual graph patterns (called SA patterns, or SAPs for short), which organize SAs into interpretable subgroups. Whereas the quality and usefulness of SAs and SAPs have been extensively studied in the literature, in this article we aim to develop faster algorithms for SA search and frequent SAP mining. For the former problem, we leverage distances to prune the search space, and implement a distance oracle to balance the time and space for distance calculation. For the latter problem, we exploit both graph structure and labels to induce fine-grained skeleton-based partitions of SAs, which may be pruned to reduce SAP enumeration. Besides, we generate canonical codes for SAs, which not only enable result deduplication but also are reused in SAP mining to improve the overall performance. We extensively evaluate the efficiency of our algorithms on four large graphs, using both random queries and simulated queries which reproduce the extreme case of finding numerous SAs.

Monitoring of the state, performance, quality of operations and other parameters of equipment and production processes, which is typically referred to as condition monitoring, is an important common practice in many industries including manufacturing, oil and gas, chemical and process industry. In the age of Industry 4.0, where the aim is a deep degree of production automation, unprecedented amounts of data are generated by equipment and processes, and this enables adoption of Machine Learning (ML) approaches for condition monitoring. Development of such ML models is challenging. On the one hand, it requires collaborative work of experts from different areas, including data scientists, engineers, process experts, and managers with asymmetric backgrounds. On the other hand, there is high variety and diversity of data relevant for condition monitoring. Both factors hampers ML modelling for condition monitoring. In this work, we address these challenges by empowering ML-based condition monitoring with semantic technologies. To this end we propose a software system SemML that allows to reuse and generalise ML pipelines for conditions monitoring by relying on semantics. In particular, SemML has several novel components and relies on ontologies and ontology templates for ML task negotiation and for data and ML feature annotation. SemML also allows to instantiate parametrised ML pipelines by semantic annotation of industrial data. With SemML, users do not need to dive into data and ML scripts when new datasets of a studied application scenario arrive. They only need to annotate data and then ML models will be constructed through the combination of semantic reasoning and ML modules. We demonstrate the benefits of SemML on a Bosch use-case of electric resistance welding with very promising results.

Entity retrieval has received increasing research attention. The recent progress in deep and machine learning techniques provides powerful tools for developing effective entity-centered solutions. This workshop series provides a platform where interdisciplinary studies of entity retrieval and learning can be presented, and focused discussions can take place. We also organize a shared task related to entity retrieval. The 3rd International Workshop on EntitY Retrieval and lEarning (EYRE 2020) was a half-day workshop co-located with the 29th ACM International Conference on Information and Knowledge Management (CIKM 2020) as a virtual event in Ireland.

Relevance search is to find top-ranked entities in a knowledge graph (KG) that are relevant to a query entity. Relevance is ambiguous, particularly over a schema-rich KG like DBpedia which supports a wide range of different semantics of relevance based on numerous types of relations and attributes. As users may lack the expertise to formalize the desired semantics, supervised methods have emerged to learn the hidden user-defined relevance from user-provided examples. Along this line, in this paper we propose a novel generative model over KGs for relevance search, named GREASE. The model applies to meta-path based relevance where a meta-path characterizes a particular type of semantics of relating the query entity to answer entities. It is also extended to support properties that constrain answer entities. Extensive experiments on two large-scale KGs demonstrate that GREASE has advanced the state of the art in effectiveness, expressiveness, and efficiency.

Keyword search is a prominent approach to querying Web data. For graph-structured data, a widely accepted semantics for keywords is based on group Steiner trees. For this NP-hard problem, existing algorithms with provable quality guarantees have prohibitive run time on large graphs. In this paper, we propose practical approximation algorithms with a guaranteed quality of computed answers and very low run time. Our algorithms rely on Hub Labeling (HL), a structure that labels each vertex in a graph with a list of vertices reachable from it, which we use to compute distances and shortest paths. We devise two HLs: a conventional static HL that uses a new heuristic to improve pruned landmark labeling, and a novel dynamic HL that inverts and aggregates query-relevant static labels to more efficiently process vertex sets. Our approach allows to compute a reasonably good approximation of answers to keyword queries in milliseconds on million-scale knowledge graphs.

Reusing published datasets on the Web is of great interest to researchers and developers. Their data needs may be met by submitting queries to a dataset search engine to retrieve relevant datasets. In this ongoing work towards developing a more usable dataset search engine, we characterize real data needs by annotating the semantics of 1,947 queries using a novel fine-grained scheme, to provide implications for enhancing dataset search. Based on the findings, we present a query-centered framework for dataset search, and explore the implementation of snippet generation and evaluate it with a preliminary user study.

Entity retrieval has received increasing research attention from both the Information Retrieval (IR) and Semantic Web communities. This workshop series provides a platform where interdisciplinary studies of entity retrieval can be presented, and focused discussions can take place. We also organize two shared tasks related to entity retrieval. The 2nd International Workshop on EntitY REtrieval (EYRE 2019) was a half-day workshop co-located with the 28th ACM International Conference on Information and Knowledge Management (CIKM 2019) in Beijing, China.

Knowledge graphs (KGs) have been extensively used to annotate text, e.g., news articles, in order to enhance its comprehension by readers. This requires to map entities occurring in the news to the target entities of the KG and to extract a so-called relationship sub-graph (RSG) that spans these entities. RSG extraction is computationally demanding and cannot scale to large KGs. Existing approximation algorithms that focus on structurally compact RSGs are not satisfactory since they often return no answers. We address this problem and develop an efficient algorithm to find approximations that connect the most salient subset of the target entities. Moreover, we propose a context-aware method to rank RSGs by their relevance to the news and their semantic cohesion. In the demo we will present our approach and the attendees will be able to experience how our system MiCRon helps to make sense of news article by computing and presenting RSGs relevant to these articles.

Relevance search over a knowledge graph (KG) has gained much research attention. Given a query entity in a KG, the problem is to find its most relevant entities. However, the relevance function is hidden and dynamic. Different users for different queries may consider relevance from different angles of semantics. The ambiguity in a query is more noticeable in the presence of thousands of types of entities and relations in a schema-rich KG, which has challenged the effectiveness and scalability of existing methods. To meet the challenge, our approach called RelSUE requests a user to provide a small number of answer entities as examples, and then automatically learns the most likely relevance function from these examples. Specifically, we assume the intent of a query can be characterized by a set of meta-paths at the schema level. RelSUE searches a KG for diversified significant meta-paths that best characterize the relevance of the user-provided examples to the query entity. It reduces the large search space of a schema-rich KG using distance and degree-based heuristics, and performs reasoning to deduplicate meta-paths that represent equivalent query-specific semantics. Finally, a linear model is learned to predict meta-path based relevance. Extensive experiments demonstrate that RelSUE outperforms several state-of-the-art methods.

Triple-structured open data creates value in many ways. However, the reuse of datasets is still challenging. Users feel difficult to assess the usefulness of a large dataset containing thousands or millions of triples. To satisfy the needs, existing abstractive methods produce a concise high-level abstraction of data. Complementary to that, we adopt the extractive strategy and aim to select the optimum small subset of data from a dataset as a snippet to compactly illustrate the content of the dataset. This has been formulated as a combinatorial optimization problem in our previous work. In this article, we design a new algorithm for the problem, which is an order of magnitude faster than the previous one but has the same approximation ratio. We also develop an anytime algorithm that can generate empirically better solutions using additional time. To suit datasets that are partially accessible via online query services (e.g., SPARQL endpoints for RDF data), we adapt our algorithms to trade off quality of snippet for feasibility and efficiency in the Web environment. We carry out extensive experiments based on real RDF datasets and SPARQL endpoints for evaluating quality and running time. The results demonstrate the effectiveness and practicality of our proposed algorithms.

Searching for associations between entities is needed in many domains. It has been facilitated by the emergence of graph-structured semantic data on the Web, which offers structured semantic associations more explicit than those hiding in unstructured text for computers to discover. The increasing volume of semantic data requires ranking techniques to identify the more important semantic associations for users. Considering a lack of comprehensive empirical evaluation of existing techniques, we carry out an extensive evaluation of eight techniques including two novel ones we propose. The practical effectiveness of these techniques is assessed based on 1,200 ground-truth rankings created by 30 human experts for real-life semantic associations and on the explanations given by the experts.

Knowlege graphs have become powerful assets for enhancing search and data integration and are now widely used in both academia and industry. Existing semantics of keyword search over knowledge graphs, especially in industrial context, has limitations. In this extended abstract we discuss these limitations and ingredients for alternative semantics.

To embrace the open data movement, increasingly many datasets have been published on the Web to be reused. Users, when assessing the usefulness of an unfamiliar dataset, need means to quickly inspect its contents. To satisfy the needs, we propose to automatically extract an optimal small portion from a dataset, called a snippet, to concisely illustrate the contents of the dataset. We consider the quality of a snippet from three aspects: coverage, familiarity, and cohesion, which are jointly formulated in a new combinatorial optimization problem called the maximum-weight-and-coverage connected graph problem (MwcCG). We give a constant-factor approximation algorithm for this NP-hard problem, and experiment with our solution on real-world datasets. Our quantitative analysis and user study show that our approach outperforms a baseline approach.

Searching for associations between entities is needed in many domains like national security and bioinformatics. In recent years, it has been facilitated by the emergence of graph-structured semantic data on the Web, which offers structured semantic associations more explicit than those hiding in unstructured text for computers to discover. The increasing volume of semantic data often produces excessively many semantic associations, and requires ranking techniques to identify the more important ones for users. Despite the fruitful theoretical research on innovative ranking techniques, there is a lack of comprehensive empirical evaluation of these techniques. In this article, we carry out an extensive evaluation of eight techniques for ranking semantic associations, including two novel ones we propose. The practical effectiveness of these techniques is assessed based on 1,200 ground-truth rankings created by 30 human experts for real-life semantic associations and the explanations given by the experts. Our findings also suggest a number of directions in improving existing techniques and developing novel techniques for future work.

Entity linking connects the Web of documents with knowledge bases. It is the task of linking an entity mention in text to its corresponding entity in a knowledge base. Whereas a large body of work has been devoted to automatically generating candidate entities, or ranking and choosing from them, manual efforts are still needed, e.g., for defining gold-standard links for evaluating automatic approaches, and for improving the quality of links in crowdsourcing approaches. However, structured descriptions of entities in knowledge bases are sometimes very long. To avoid overloading human users with too much information and help them more efficiently choose an entity from candidates, we aim to substitute entire entity descriptions with compact, equally effective structured summaries that are automatically generated. To achieve it, our approach analyzes entity descriptions in the knowledge base and the context of entity mention from multiple perspectives, including characterizing and differentiating power, information overlap, and relevance to context. Extrinsic evaluation (where human users carry out entity linking tasks) and intrinsic evaluation (where human users rate summaries) demonstrate that summaries generated by our approach help human users carry out entity linking tasks more efficiently (22-23% faster), without significantly affecting the quality of links obtained; and our approach outperforms existing approaches to summarizing entity descriptions.

Along with the rapid growth of the data Web, searching linked objects for information needs and for reusing become emergent for ordinary Web users and developers, respectively. To meet the challenge, we present Falcons Object Search, a keyword-based search engine for linked objects. To serve various keyword queries, for each object the system constructs a comprehensive virtual document including not only associated literals but also the textual descriptions of associated links and linked objects. The resulting objects are ranked by considering both their relevance to the query and their popularity. For each resulting object, a query-relevant structured snippet is provided to show the associated literals and linked objects matched with the query. Besides, Web-scale class-inclusion reasoning is performed to discover implicit typing information, and users could navigate class hierarchies for incremental class-based results filtering. The results of a task-based experiment show the promising features of the system.

As of today, the amount of data on the Semantic Web has grown considerably. The services for searching and browsing entities on the Semantic Web are in demand. To provide such services, we developed the Falcons system. In this poster, we present the features of the Falcons system.

Ontology summarization is very important to quick understanding and selection of ontologies. In this paper, we study extractive summarization of ontology. We propose a notion of RDF sentence as the basic unit of summarization. An RDF Sentence Graph is proposed to characterize the links between RDF sentences derived from a given ontology. The salience of each RDF sentence is assessed in terms of its "centrality" in the graph. We propose to summarize an ontology by extracting a set of salient RDF sentences according to a re-ranking strategy. We compare several measurements in assessing the salience of RDF sentences and give an overall evaluation of experiment results, which shows that our approach to ontology summarization is feasible.

On the investigation of linguistic techniques used in ontology matching, we propose a new idea of virtual documents to pursue a cost-effective approach to linguistic matching in this paper. Basically, as a collection of weighted words, the virtual document of a URIref declared in an ontology contains not only the local descriptions but also the neighboring information to reflect the intended meaning of the URIref. Document similarity can be computed by traditional vector space techniques, and then be used in the similaritybased approaches to ontology matching. In particular, the RDF graph structure is exploited to define the description formulations and the neighboring operations. Experimental results show that linguistic matching based on the virtual documents is dominant in average F-Measure as compared to other three approaches. It is also demonstrated by our experiments that the virtual documents approach is cost-effective as compared to other linguistic matching approaches.