Search

Matching tabular data to a knowledge graph (KG) is critical for understanding the semantic column types, column relationships, and entities of a table. Existing matching approaches rely heavily on core columns that represent primary subject entities on which other columns in the table depend. However, discovering these core columns before understanding the table's semantics is challenging. Most prior works use heuristic rules, such as the leftmost column, to discover a single core column, while an insightful discovery of the core column set that accurately captures the dependencies between columns is often overlooked. To address these challenges, we introduce Dependency-aware Core Column Set Discovery (DaCo), an iterative method that uses a novel rough matching strategy to identify both inter-column dependencies and the core column set. Additionally, DaCo can be seamlessly integrated with pre-trained language models, as proposed in the optimization module. Unlike other methods, DaCo does not require labeled data or contextual information, making it suitable for real-world scenarios. In addition, it can identify multiple core columns within a table, which is common in real-world tables. We conduct experiments on six datasets, including five datasets with single core columns and one dataset with multiple core columns. Our experimental results show that DaCo outperforms existing core column set detection methods, further improving the effectiveness of table understanding tasks. [ABSTRACT FROM AUTHOR]

In natural language processing (NLP), zero-shot topic classification requires machines to understand the contextual meanings of texts in a downstream task without using the corresponding labeled texts for training, which is highly desirable for various applications. In this article, we propose a novel approach to construct a zero-shot task-specific model called WC-SBERT with satisfactory performance. The proposed approach is highly efficient since it uses light self-training requiring target labels (target class names of downstream tasks) only, which is distinct from other research that uses both the target labels and the unlabeled texts for training. In particular, during the pre-training stage, WC-SBERT uses contrastive learning with multiple negative ranking losses to construct the pre-trained model based on the similarity between Wiki categories. For the self-training stage, online contrastive loss is utilized to reduce the distance between a target label and Wiki categories of similar Wiki pages to the label. Experimental results indicate that compared to existing self-training models, WC-SBERT achieves rapid inference on approximately 6.45 million Wiki text entries by utilizing pre-stored Wikipedia text embeddings, significantly reducing inference time per sample by a factor of 2,746 to 16,746. During the fine-tuning step, the time required for each sample is reduced by a factor of 23–67. Overall, the total training time shows a maximum reduction of 27.5 times across different datasets. Most importantly, our model has achieved state-of-the-art (SOTA) accuracy on two of the three commonly used datasets for evaluating zero-shot classification, namely the AG News (0.84) and Yahoo! Answers (0.64) datasets. The code for WC-SBERT is publicly available on GitHub,1 and the dataset can also be accessed on Hugging Face.2 [ABSTRACT FROM AUTHOR]

The growing adoption of electric vehicles (EVs) has resulted in an increased demand for public EV charging infrastructure. Currently, the collaboration between these stations has become vital for efficient charging scheduling and cost reduction. However, most existing scheduling methods primarily focus on recommending charging stations without considering users' charging preferences. Adopting these strategies may require considerable modifications to how people charge their EVs, which could lead to a reluctance to follow the scheduling plan from charging services in real-world situations. To address these challenges, we propose the POSKID framework in this article. It focuses on spatial-temporal charging scheduling, aiming to recommend a feasible charging arrangement, including a charging station and a charging time slot, to each EV user while minimizing overall operating costs and ensuring users' charging satisfaction. The framework adopts an online charging mechanism that provides recommendations without prior knowledge of future electricity information or charging requests. To enhance users' willingness to accept the recommendations, POSKID incorporates an incentive strategy and a novel embedding method combined with Bayesian personalized analysis. These techniques reveal users' implicit charging preferences, enhancing the success probability of the charging scheduling task. Furthermore, POSKID integrates an online candidate arrangement selection and an explore-exploit strategy to improve the charging arrangement recommendations based on users' feedback. Experimental results using real-world datasets validate the effectiveness of POSKID in optimizing charging management, surpassing other strategies. The results demonstrate that POSKID benefits each charging station while ensuring user charging satisfaction. [ABSTRACT FROM AUTHOR]

The profound digitization of public administration over recent decades has not eliminated information exchange via paper or electronic documents and certificates. We argue that a paradigm shift from document-centric to data-centric public service provision is needed and is feasible today with the exploitation of emerging technologies. We explore frameworks, architectures, benefits, and challenges in transforming document-centric administration processes into integrated, granular data exchange. A conceptual architecture for public service provision is proposed to extract preconditions from legislation, map the needed evidence to the service requirements, standardize evidence types, and integrate authoritative data sources. While promoting efficiency, privacy, and innovation, this shift faces technical and organizational challenges as the analysis of the "National Registry of Administrative Public Services" in Greece reveals. Further research on aligning policies, upholding trust, and coordinating institutional processes is warranted. [ABSTRACT FROM AUTHOR]

Graph embedding converts a graph data into a low dimensional space to preserve the original graph information. However, graph data can be reconstructed by malicious adversaries to train machine learning models from graph embeddings. This paper studies to what extent an adversary (without the original graph data) can recover the original graph data from graph embeddings. To quantify the original graph information leakage from graph embeddings, we develop a deep neural network model InferNet that can be used by adversaries to infer the original graph information from an adversary-accessible graph embedding database. More specifically, we propose the data-free reversed knowledge distillation technique to support the InferNet training even if the original graph dataset is absent. To ensure the performance of InferNet, we design two cycle-consistency loss functions to have an interactive training of InferNet over three series of datasets. To further enhance the performance of InferNet, we provide a joint training algorithm that simultaneously trains the pseudo-sample generator and InferNet, which significantly reduces the storage space. We evaluate the performance of InferNet on three datasets, and the intensive experiments demonstrate that InferNet can infer the original graph information from the graph embedding dataset with high accuracy. [ABSTRACT FROM AUTHOR]

The knowledge graph (KG) is an efficient form of knowledge organization and expression, providing prior knowledge support for various downstream tasks, and has received extensive attention in natural language processing. However, existing large-scale KGs have many hidden facts that need to be discovered. How to effectively use the structure information of KG is an important research direction of knowledge reasoning. Structure-Information-based reasoning over the KG is a technique used to find the missing facts by the structure information of KG. This survey summarizes the methods and applications of Structure-Information-based reasoning and hopes to be helpful to the research in this field. First, we introduced the definition of knowledge reasoning and the conceptual description of related tasks. Then, we reviewed the methods of Structure-Information-based reasoning. Specifically, we categorized them into four representative classes: PRA-based reasoning, Path-Embedding-based reasoning, RL-based reasoning, and GNN-based reasoning. We compared the motivations and details between practices in the same category. After that, we described the application of Structure-Information-based knowledge reasoning in the KG Completion, Question Answering System, Recommendation System, and other fields. Finally, we discussed the future research directions of Structure-Information-based reasoning. [ABSTRACT FROM AUTHOR]

Software vulnerabilities, also known as flaws, bugs or weaknesses, are common in modern information systems, putting critical data of organizations and individuals at cyber risk. Due to the scarcity of resources, initial risk assessment is becoming a necessary step to prioritize vulnerabilities and make better decisions on remediation, mitigation, and patching. Datasets containing historical vulnerability information are crucial digital assets to enable AI-based risk assessments. However, existing datasets focus on collecting information on individual vulnerabilities while simply storing them in relational databases, disregarding their structural connections. This article constructs a compact vulnerability knowledge graph, VulKG, containing over 276 K nodes and 1 M relationships to represent the connections between vulnerabilities, exploits, affected products, vendors, referred domain names, and more. We provide a detailed analysis of VulKG modeling and construction, demonstrating VulKG-based query and reasoning, and providing a use case of applying VulKG to a vulnerability risk assessment task, i.e., co-exploitation behavior discovery. Experimental results demonstrate the value of graph connections in vulnerability risk assessment tasks. VulKG offers exciting opportunities for more novel and significant research in areas related to vulnerability risk assessment. The data and codes of this article are available at https://github.com/happyResearcher/VulKG.git. [ABSTRACT FROM AUTHOR]

With ever-increasing dataset size and data storage capacity, there is a strong need to build systems that can effectively utilize these vast datasets to extract valuable information. Large datasets often exhibit sparsity and pose cold start problems, necessitating the development of responsible recommender systems. Knowledge graphs have utility in responsibly representing information related to recommendation scenarios. However, many studies overlook explicitly encoding contextual information, which is crucial for reducing the bias of multi-layer propagation. Additionally, existing methods stack multiple layers to encode high-order neighbor information while disregarding the relational information between items and entities. This oversight hampers their ability to capture the collaborative signal latent in user-item interactions. This is particularly important in health informatics, where knowledge graphs consist of various entities connected to items through different relations. Ignoring the relational information renders them insufficient for modeling user preferences. This work presents an end-to-end recommendation framework named KGCAN (Knowledge Graph Enhanced Contextualized Attention-Based Network), which explicitly encodes both relational and contextual information of entities to preserve the original entity information. Furthermore, a user-specific attention mechanism is employed to capture personalized recommendations. The proposed model is validated on three benchmark datasets through extensive experiments. The experimental results demonstrate that KGCAN outperforms existing knowledge graph based recommendation models. Additionally, a case study from the healthcare domain is discussed, highlighting the importance of attention mechanisms and high-order connectivity in the responsible recommendation system for health informatics. [ABSTRACT FROM AUTHOR]

Recommender systems are one of the most successful applications of using AI for providing personalized e-services to customers. However, data sparsity is presenting enormous challenges that are hindering the further development of advanced recommender systems. Although cross-domain recommendation partly overcomes data sparsity by transferring knowledge from a source domain with relatively dense data to augment data in the target domain, the current methods do not handle heterogeneous data very well. For example, using today's cross-domain transfer learning schemes with data comprising clicks, ratings, user reviews, item metadata, and knowledge graphs will likely result in a poorly performing model. User preferences will not be comprehensively profiled, and accurate recommendations will not be generated. To solve these three challenges—handling heterogeneous data, avoiding negative transfer, and dealing with data sparsity—we designed a new end-to-end deep Adversarial Multi-channel Transfer network for Cross-Domain Recommendation named AMT-CDR. Heterogeneous data is handled by constructing a cross-domain graph based on real-world knowledge graphs—we used Freebase and YAGO. Negative transfer is prevented through an adversarial learning strategy that maintains consistency across the different data channels. Data sparsity is addressed with an end-to-end neural network that considers data across multiple channels and generates accurate recommendations by leveraging knowledge from both the source and target domains. Extensive experiments on three dual-target cross-domain recommendation tasks demonstrate the superiority of AMT-CDR compared to eight state-of-the-art methods. All source code is available at https://github.com/bjtu-lucas-nlp/AMT-CDR. [ABSTRACT FROM AUTHOR]

Traditional recommender systems estimate user preference on items purely based on historical interaction records, thus failing to capture fine-grained yet dynamic user interests and letting users receive recommendation only passively. Recent conversational recommender systems (CRSs) tackle those limitations by enabling recommender systems to interact with the user to obtain her/his current preference through a sequence of clarifying questions. Recently, there has been a rise of using knowledge graphs (KGs) for CRSs, where the core motivation is to incorporate the abundant side information carried by a KG into both the recommendation and conversation processes. However, existing KG-based CRSs are subject to two defects: (1) there is a semantic gap between the learned representations of utterances and KG entities, hindering the retrieval of relevant KG information; (2) the reasoning over KG is mostly performed with the implicitly learned user interests, overlooking the explicit signals from the entities actually mentioned in the conversation. To address these drawbacks, we propose a new CRS framework, namely, the Knowledge Enhanced Conversational Reasoning (KECR) model. As a user can reflect her/his preferences via both attribute- and item-level expressions, KECR jointly embeds the structured knowledge from two levels in the KG. A mutual information maximization constraint is further proposed for semantic alignment between the embedding spaces of utterances and KG entities. Meanwhile, KECR utilizes the connectivity within the KG to conduct explicit reasoning of the user demand, making the model less dependent on the user's feedback to clarifying questions. As such, the semantic alignment and explicit KG reasoning can jointly facilitate accurate recommendation and quality dialogue generation. By comparing with strong baselines on two real-world datasets, we demonstrate that KECR obtains state-of-the-art recommendation effectiveness, as well as competitive dialogue generation performance. [ABSTRACT FROM AUTHOR]

Recent years have witnessed the successful application of knowledge graph techniques in structured data processing, while how to incorporate knowledge from visual and textual modalities into knowledge graphs has been given less attention. To better organize them, Multimodal Knowledge Graphs (MKGs), comprising the structural triplets of traditional Knowledge Graphs (KGs) together with entity-related multimodal data (e.g., images and texts), have been introduced consecutively. However, it is still a great challenge to explore MKGs due to their inherent incompleteness. Although most existing Multimodal Knowledge Graph Completion (MKGC) approaches can infer missing triplets based on available factual triplets and multimodal information, they almost ignore the modal conflicts and supervisory effect, failing to achieve a more comprehensive understanding of entities. To address these issues, we propose a novel Hierarchical Knowledge Alignment (HKA) framework for MKGC. Specifically, a macro-knowledge alignment module is proposed to capture global semantic relevance between modalities for dealing with modal conflicts in MKG. Furthermore, a micro-knowledge alignment module is also developed to reveal the local consistency information through inter- and intra-modality supervisory effects more effectively. By integrating different modal predictions, a final decision can be made. Experimental results on three benchmark MKGC tasks have demonstrated the effectiveness of the proposed HKA framework. [ABSTRACT FROM AUTHOR]

Recent advances in Tiny Machine Learning (TinyML) empower low-footprint embedded devices for real-time on-device Machine Learning (ML). While many acknowledge the potential benefits of TinyML, its practical implementation presents unique challenges. This study aims to bridge the gap between prototyping single TinyML models and developing reliable TinyML systems in production: (1) Embedded devices operate in dynamically changing conditions. Existing TinyML solutions primarily focus on inference, with models trained offline on powerful machines and deployed as static objects. However, static models may underperform in the real world due to evolving input data distributions. We propose online learning to enable training on constrained devices, adapting local models toward the latest field conditions. (2) Nevertheless, current on-device learning methods struggle with heterogeneous deployment conditions and the scarcity of labeled data when applied across numerous devices. We introduce federated meta-learning incorporating online learning to enhance model generalization, facilitating rapid learning. This approach ensures optimal performance among distributed devices by knowledge sharing. (3) Moreover, TinyML's pivotal advantage is widespread adoption. Embedded devices and TinyML models prioritize extreme efficiency, leading to diverse characteristics ranging from memory and sensors to model architectures. Given their diversity and non-standardized representations, managing these resources becomes challenging as TinyML systems scale up. We present semantic management for the joint management of models and devices at scale. We demonstrate our methods through a basic regression example and then assess them in three real-world TinyML applications: handwritten character image classification, keyword audio classification, and smart building presence detection. The results confirm the effectiveness of our approaches from various perspectives, such as accuracy improvement, resource savings, and engineering effort reduction. [ABSTRACT FROM AUTHOR]

Recommender System provides users with online services in a personalized way. The performance of traditional recommender systems may deteriorate because of problems such as cold-start and data sparsity. Cross-domain Recommendation System utilizes the richer information from auxiliary domains to guide the task in the target domain. However, direct knowledge transfer may lead to a negative impact due to data heterogeneity and feature mismatch between domains. In this article, we innovatively explore the cross-domain correlation from the perspectives of content semanticity and structural connectivity to fully exploit the information of Knowledge Graph. First, we adopt domain adaptation that automatically extracts transferable features to capture cross-domain semantic relations. Second, we devise a knowledge-aware graph neural network to explicitly model the high-order connectivity across domains. Third, we develop feature fusion strategies to combine the advantages of semantic and structural information. By simulating the cold-start scenario on two real-world datasets, the experimental results show that our proposed method has superior performance in accuracy and diversity compared with the SOTA methods. It demonstrates that our method can accurately predict users' expressed preferences while exploring their potential diverse interests. [ABSTRACT FROM AUTHOR]

Knowledge Graph (KG) reasoning has been an interesting topic in recent decades. Most current researches focus on predicting the missing facts for incomplete KG. Nevertheless, Temporal KG (TKG) reasoning, which is to forecast future facts, still faces with a dilemma due to the complex interactions between entities over time. This article proposes a novel intricate Spatiotemporal Dependency learning Network (STDN) based on Graph Convolutional Network (GCN) to capture the underlying correlations of an entity at different timestamps. Specifically, we first learn an adaptive adjacency matrix to depict the direct dependencies from the temporally adjacent facts of an entity, obtaining its previous context embedding. Then, a Spatiotemporal feature Encoding GCN (STE-GCN) is proposed to capture the latent spatiotemporal dependencies of the entity, getting the spatiotemporal embedding. Finally, a time gate unit is used to integrate the previous context embedding and the spatiotemporal embedding at the current timestamp to update the entity evolutional embedding for predicting future facts. STDN could generate the more expressive embeddings for capturing the intricate spatiotemporal dependencies in TKG. Extensive experiments on WIKI, ICEWS14, and ICEWS18 datasets prove our STDN has the advantage over state-of-the-art baselines for the temporal reasoning task. [ABSTRACT FROM AUTHOR]

In recent years, Graph Neural Networks (GNNs) have achieved unprecedented success in handling graph-structured data, thereby driving the development of numerous GNN-oriented techniques for inductive knowledge graph completion (KGC). A key limitation of existing methods, however, is their dependence on pre-defined aggregation functions, which lack the adaptability to diverse data, resulting in suboptimal performance on established benchmarks. Another challenge arises from the exponential increase in irrelated entities as the reasoning path lengthens, introducing unwarranted noise and consequently diminishing the model's generalization capabilities. To surmount these obstacles, we design an innovative framework that synergizes Multi-Level Sampling with an Adaptive Aggregation mechanism (MLSAA). Distinctively, our model couples GNNs with enhanced set transformers, enabling dynamic selection of the most appropriate aggregation function tailored to specific datasets and tasks. This adaptability significantly boosts both the model's flexibility and its expressive capacity. Additionally, we unveil a unique sampling strategy designed to selectively filter irrelevant entities, while retaining potentially beneficial targets throughout the reasoning process. We undertake an exhaustive evaluation of our novel inductive KGC method across three pivotal benchmark datasets and the experimental results corroborate the efficacy of MLSAA. [ABSTRACT FROM AUTHOR]

Object detection is a widely studied problem in existing works. However, in this paper, we turn to a more challenging problem of "Covered Object Reasoning", aimed at reasoning the category label of target object in the given image particularly when it has been totally covered (or invisible). To resolve this problem, we propose CoBjeason to seize the opportunity when visual reasoning meets the knowledge graph, where "empirical cognition" on common visual contexts have been incorporated as knowledge graph to conduct reinforced multi-hop reasoning via two collaborative agents. Such two agents, for one thing, stand at the covered object (or unknown entity) to observe the surrounding visual cues in the given image and gradually select entities and relations from the global gallery-level knowledge graph which contains entity-pairs frequently occurring across the entire image-collection, so as to infer the main structure of image-level knowledge graph forward expanded from the unknown entity. In turn, for another, based on the reasoned image-level knowledge graph, the semantic context among entities will be aggregated backward into unknown entity to select an appropriate entity from the global gallery-level knowledge graph as the reasoning result. Moreover, such two agents will collaborate with each other, securing that the above Forward & Backward Reasoning will step towards the same destination of the higher performance on covered object reasoning. To our best knowledge, this is the first work on Covered Object Reasoning with Knowledge Graphs and reinforced Multi-Agent collaboration. Particularly, our study on Covered Object Reasoning and the proposed model CoBjeason could offer novel insights into more basic Computer Vision (CV) tasks, such as Semantic Segmentation with better understanding on the current scene when some objects are blurred or covered, Visual Question Answering with enhancement on the inference in more complicated visual context when some objects are covered or invisible, and Image Caption Generation with the augmentation on the richness of visual context for images containing partially visible objects. The improvement on the above basic CV tasks can further refine more complicated ones involved with nuanced visual interpretation like Autonomous Driving, where the recognition and reasoning on partially visible or covered object are critical. According to the experimental results, our proposed CoBjeason can achieve the best overall ranking performance on covered object reasoning compared with other models, meanwhile enjoying the advantage of lower "exploration cost", with the insensitivity against the long-tail covered objects and the acceptable time complexity. [ABSTRACT FROM AUTHOR]

Accurately estimating packages' arrival time in e-commerce can enhance users' shopping experience and improve the placement rate of products. This problem is often formalized as an Origin-Destination (OD)-based ETA (i.e., estimated time of arrival) prediction task, where the delivery time is estimated mainly based on sender and receiver addresses and other context information. One inherent challenge of the OD-based ETA problem is that the delivery time highly depends on the actual delivery trajectory which is unknown at the time of prediction. In this article, we tackle this challenge by effectively exploiting historical delivery trajectories. We propose a novel Knowledge Distillation Graph neural network-based package ETA prediction (KDG-ETA) model, which uses knowledge distillation in the training phase to distill the knowledge of historical trajectories into OD pair embeddings. In KDG-ETA, a multi-level trajectory graph representation model is proposed to fully exploit trajectory information at the node-level, edge-level, and path-level. Then, the OD representations embedded with trajectory knowledge are combined with context embeddings from feature extraction module for delivery time prediction using an adaptive attention module. KDG-ETA consistently outperforms existing state-of-the-art OD-based ETA prediction methods on three real-world Alibaba datasets, reducing the Mean Absolute Error (MAE) by 3.0%–39.1% as demonstrated in our extensive empirical evaluation. [ABSTRACT FROM AUTHOR]

Modeling the dynamic interactions between users and items on knowledge graphs is crucial for improving the accuracy of recommendation. Although existing methods have made great progress in modeling the dynamic knowledge graphs for recommendation, they usually only consider the mutual influence between users and items involved in the interactions, and ignore the influence propagation from the interacting nodes (i.e., users and items) on dynamic knowledge graphs. In this article, we propose an influence propagation-enhanced deep co-evolutionary method for recommendation, which can capture not only the direct mutual influence between interacting users and items but also influence propagation from multiple interacting nodes to their high-order neighbors at the same time on the dynamic knowledge graph. Specifically, the proposed model consists of two main components: the direct mutual influence component and the influence propagation component. The former captures direct interaction influence between the interacting users and items to generate the effective representations for them. The latter refines their representations via aggregating the interaction influence propagated from multiple interacting nodes. In this process, a neighbor selection mechanism is designed for selecting more effective propagation influence, which can significantly reduce the computational cost and accelerate the training. Finally, the refined representations of users and items are used to predict which item the user is most likely to interact with. The experimental results on three real-world datasets illustrate that the effectiveness and robustness of PIDKG outperform all state-of-the-art baselines and the efficiency of it is faster than most comparative baselines. [ABSTRACT FROM AUTHOR]

The prosperity of knowledge graphs, as well as related downstream applications, has raised the urgent need for knowledge graph completion techniques that fully support knowledge graph reasoning tasks, especially under the circumstance of training data scarcity. Although large efforts have been made on solving this challenge via few-shot learning tools, they mainly focus on simply aggregating entity neighbors to represent few-shot references, whereas the enhancement from latent semantic correlation within neighbors has been largely ignored. To that end, in this article, we propose a novel few-shot learning solution named SIM, a Semantic Interaction Matching network that applies a Transformer framework to enhance the entity representation with capturing semantic interaction between entity neighbors. Specifically, we first design an entity-relation fusion module to adaptively encode neighbors with incorporating relation representation. Along this line, Transformer layers are integrated to capture latent correlation within neighbors, as well as the semantic diversification of the support set. Finally, a similarity score is attentively estimated with the attention mechanism. Extensive experiments on two public benchmark datasets demonstrate that our model outperforms a variety of state-of-the-art methods by a significant margin. [ABSTRACT FROM AUTHOR]

This article studies the problem of semi-supervised learning on graphs, which aims to incorporate ubiquitous unlabeled knowledge (e.g., graph topology, node attributes) with few-available labeled knowledge (e.g., node class) to alleviate the scarcity issue of supervised information on node classification. While promising results are achieved, existing works for this problem usually suffer from the poor balance of generalization and fitting ability due to the heavy reliance on labels or task-agnostic unsupervised information. To address the challenge, we propose a dual-channel framework for semi-supervised learning on Graphs via Knowledge Transfer between independent supervised and unsupervised embedding spaces, namely, GKT. Specifically, we devise a dual-channel framework including a supervised model for learning the label probability of nodes and an unsupervised model for extracting information from massive unlabeled graph data. A knowledge transfer head is proposed to bridge the gap between the generalization and fitting capability of the two models. We use the unsupervised information to reconstruct batch-graphs to smooth the label probability distribution on the graphs to improve the generalization of prediction. We also adaptively adjust the reconstructed graphs by encouraging the label-related connections to solidify the fitting ability. Since the optimization of the supervised channel with knowledge transfer contains that of the unsupervised channel as a constraint and vice versa, we then propose a meta-learning-based method to solve the bi-level optimization problem, which avoids the negative transfer and further improves the model's performance. Finally, extensive experiments validate the effectiveness of our proposed framework by comparing state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Knowledge graphs (KGs) play a vital role in enhancing search results and recommendation systems. With the rapid increase in the size of KGs, they are becoming inaccurate and incomplete. This problem can be solved by the KG completion methods, of which graph attention network (GAT)-based methods stand out because of their superior performance. However, existing GAT-based KG completion methods often suffer from overfitting issues when dealing with heterogeneous KGs, primarily due to the unbalanced number of samples. Additionally, these methods demonstrate poor performance in predicting the tail (head) entity that shares the same relation and head (tail) entity with others. To solve these problems, we propose GATH, a novel GAT-based method designed for Heterogeneous KGs. GATH incorporates two separate attention network modules that work synergistically to predict the missing entities. We also introduce novel encoding and feature transformation approaches, enabling the robust performance of GATH in scenarios with imbalanced samples. Comprehensive experiments are conducted to evaluate GATH's performance. Compared with the existing state-of-the-art GAT-based model on Hits@10 and MRR metrics, our model improves performance by 5.2% and 5.2% on the FB15K-237 dataset and by 4.5% and 14.6% on the WN18RR dataset, respectively. [ABSTRACT FROM AUTHOR]

Cross-lingual entity alignment (CLEA) aims to find equivalent entity pairs between knowledge graphs (KGs) in different languages. It is an important way to connect heterogeneous KGs and facilitate knowledge completion. Existing methods have found that incorporating relations into entities can effectively improve KG representation and benefit entity alignment, and these methods learn relation representation depending on entities, which cannot capture the diverse structures of relations. However, multiple relations in KG form diverse structures, such as adjacency structure and ring structure. This diversity of relation structures makes the relation representation challenging. Therefore, we propose to construct the weighted line graphs to model the diverse structures of relations and learn relation representation independently from entities. Especially, owing to the diversity of adjacency structures and ring structures, we propose to construct adjacency line graph and ring line graph, respectively, to model the structures of relations and to further improve entity representation. In addition, to alleviate the hubness problem in alignment, we introduce the optimal transport into alignment and compute the distance matrix in a different way. From a global perspective, we calculate the optimal 1-to-1 alignment bi-directionally to improve the alignment accuracy. Experimental results on two benchmark datasets show that our proposed method significantly outperforms state-of-the-art CLEA methods in both supervised and unsupervised manners. [ABSTRACT FROM AUTHOR]

The cross-domain recommender systems aim to alleviate the data sparsity problem in the target domain by transferring knowledge from the auxiliary domain. However, existing works ignore the fact that the data sparsity problem may also exist in the single auxiliary domain, and sharing user behavior data is restricted by the privacy policy. In addition, their cross-domain models lack interpretability. To address these concerns, we propose a novel multi-source cross-domain model based on knowledge graph. Specifically, to avoid the insufficiency of single auxiliary domain, we construct a knowledge graph comprehensively leveraging items from multiple auxiliary domains. To avoid the leakage of user privacy when user information is transferred to multiple domains, we construct graph for information transfer between items to effectively avoid the propagation of users' private information between different domains. We implicitly integrate the user–item interaction by transferring the learned item embeddings. To improve the interpretability of cross-domain knowledge transfer, we propose a knowledge graph-based retrieval and fusion method to transfer knowledge derived from multiple auxiliary domains. An attention-based fusion network is designed to enhance the representation of the targeted user and items with the transferred item embedding. We perform extensive experiments on three real-world datasets, demonstrating that our model outperforms the states of the art. [ABSTRACT FROM AUTHOR]

Domain knowledge is gradually renovating its attributes to exhibit distinct features in autonomy, propelled by the shift of modern transportation systems (TS) toward autonomous TS (ATS) comprising three progressive generations. The knowledge graph (KG) and its corresponding versions can help depict the evolving TS. Given that KG versions exhibit asymmetry primarily due to variations in evolved knowledge, it is imperative to harmonize the evolved knowledge embodied by the entity across disparate KG versions. Hence, this article proposes a siamese-based graph convolutional network (GCN) model, namely SiG, to address unresolved issues of low accuracy, efficiency, and effectiveness in aligning asymmetric KGs. SiG can optimize entity alignment in ATS and support the analysis of future-stage ATS development. Such a goal is attained through (a) generating unified KGs to enhance data quality, (b) defining graph split to facilitate entire-graph computation, (c) enhancing a GCN to extract intrinsic features, and (d) designing a siamese network to train asymmetric KGs. The evaluation results suggest that SiG surpasses other commonly employed models, resulting in average improvements of 23.90% and 37.89% in accuracy and efficiency, respectively. These findings have significant implications for TS evolution analysis and offer a novel perspective for research on complex systems limited by continuously updated knowledge. [ABSTRACT FROM AUTHOR]

The growing number of publications in the field of artificial intelligence highlights the need for researchers to enhance their efficiency in searching for relevant articles. Most paper recommendation models either rely on simplistic citation relationships among papers or focus on content-based approaches, both of which overlook interactions within academic networks. To address the aforementioned problem, knowledge graph embedding (KGE) methods have been used for citation recommendations because recent research proves that graph representations can effectively improve recommendation model accuracy. However, academic networks are dynamic, leading to changes in the representations of users and items over time. The majority of KGE-based citation recommendations are primarily designed for static graphs, thus failing to capture the evolution of dynamic knowledge graph (DKG) structures. To address these challenges, we introduced the evolving knowledge graph embedding (EKGE) method. In this methodology, evolving knowledge graphs are input into time-series models to learn the patterns of structural evolution. The model has the capability to generate embeddings for each entity at various time points, thereby overcoming limitation of static models that require retraining to acquire embeddings at each specific time point. To enhance the efficiency of feature extraction, we employed a multiple attention strategy. This helped the model find recommendation lists that are closely related to a user's needs, leading to improved recommendation accuracy. Various experiments conducted on a citation recommendation dataset revealed that the EKGE model exhibits a 1.13% increase in prediction accuracy compared to other KGE methods. Moreover, the model's accuracy can be further increased by an additional 0.84% through the incorporation of an attention mechanism. [ABSTRACT FROM AUTHOR]

Security assessment relies on public information about products, vulnerabilities, and weaknesses. So far, databases in these categories have rarely been analyzed in combination. Yet, doing so could help predict unreported vulnerabilities and identify common threat patterns. In this article, we propose a methodology for producing and optimizing a knowledge graph that aggregates knowledge from common threat databases (CVE, CWE, and CPE). We apply the threat knowledge graph to predict associations between threat databases, specifically between products, vulnerabilities, and weaknesses. We evaluate the prediction performance both in closed world with associations from the knowledge graph and in open world with associations revealed afterward. Using rank-based metrics (i.e., Mean Rank, Mean Reciprocal Rank, and Hits@N scores), we demonstrate the ability of the threat knowledge graph to uncover many associations that are currently unknown but will be revealed in the future, which remains useful over different time periods. We propose approaches to optimize the knowledge graph and show that they indeed help in further uncovering associations. We have made the artifacts of our work publicly available. [ABSTRACT FROM AUTHOR]

Vulnerable third-party libraries pose significant threats to software applications that reuse these libraries. At an industry scale of reuse, manual analysis of third-party library vulnerabilities can be easily overwhelmed by the sheer number of vulnerabilities continually collected from diverse sources for thousands of reused libraries. Our study of four large-scale, actively maintained vulnerability databases (NVD, IBM X-Force, ExploitDB, and Openwall) reveals the wide presence of information discrepancies, in terms of seven vulnerability aspects, i.e., product, version, component, vulnerability type, root cause, attack vector, and impact, between the reports for the same vulnerability from heterogeneous sources. It would be beneficial to integrate and cross-validate multi-source vulnerability information, but it demands automatic aspect extraction and aspect discrepancy detection. In this work, we experimented with a wide range of NLP methods to extract named entities (e.g., product) and free-form phrases (e.g., root cause) from textual vulnerability reports and to detect semantically different aspect mentions between the reports. Our experiments confirm the feasibility of applying NLP methods to automate aspect-level vulnerability analysis and identify the need for domain customization of general NLP methods. Based on our findings, we propose a discrepancy-aware, aspect-level vulnerability knowledge graph and a KG-based web portal that integrates diversified vulnerability key aspect information from heterogeneous vulnerability databases. Our conducted user study proves the usefulness of our web portal. Our study opens the door to new types of vulnerability integration and management, such as vulnerability portraits of a product and explainable prediction of silent vulnerabilities. [ABSTRACT FROM AUTHOR]

Nowadays, a large number of Knowledge Graph Completion (KGC) methods have been proposed by using embedding based manners, to overcome the incompleteness problem faced with knowledge graph (KG). One important recent innovation in Natural Language Processing (NLP) domain is the employ of deep neural models that make the most of pre-training, culminating in BERT, the most popular example of this line of approaches today. Recently, a series of new KGC methods introducing a pre-trained language model, such as KG-BERT, have been developed and released compelling performance. However, previous pre-training based KGC methods usually train the model by using simple training task and only utilize one-hop relational signals in KG, which leads that they cannot model high-order semantic contexts and multi-hop complex relatedness. To overcome this problem, this article presents a novel pre-training framework for KGC task, which especially consists of both one-hop relation level task (low-order) and multi-hop meta-graph level task (high-order). Hence, the proposed method can capture not only the elaborate sub-graph structure but also the subtle semantic information on the given KG. The empirical results show the efficiency of the proposed method on the widely used real-world datasets. [ABSTRACT FROM AUTHOR]

Graph neural networks have been widely used for learning representations of nodes for many downstream tasks on graph data. Existing models were designed for the nodes on a single graph, which would not be able to utilize information across multiple graphs. The real world does have multiple graphs where the nodes are often partially aligned. For examples, knowledge graphs share a number of named entities though they may have different relation schema; collaboration networks on publications and awarded projects share some researcher nodes who are authors and investigators, respectively; people use multiple web services, shopping, tweeting, rating movies, and some may register the same e-mail account across the platforms. In this article, we propose partially aligned graph convolutional networks to learn node representations across the models. We provide multiple methods such as model sharing, regularization, and alignment reconstruction, as well as theoretical analysis to positively transfer knowledge across the set of partially aligned nodes. Extensive experiments on real-world knowledge graphs, collaboration networks, and bipartite rating graphs showthe superior performance of our proposed methods on relation classification, link prediction, and item recommendation. [ABSTRACT FROM AUTHOR]

Stock prediction is a challenging task due to multiple influencing factors and complex market dependencies. Traditional solutions are based on a single type of information. With the success of multi-source information in different fields, the combination of different types of information such as numerical and textual information has become a promising option. Although multi-source information provides rich multi-view information, how to mine and construct structured relationships from them is a difficult problem. Specifically, most existing methods usually extract features from commonly used multi-source information as predictive information sources, without further pre-constructing stock relationship graphs with dependencies using broader information. More importantly, they typically treat each stock as an isolated forecasting, or employ stock market correlations based on a fixed predefined graph structure, but current methods are not sensitive enough to aggregate the attribute features extracted from multi-source information and stock relationship graph, to obtain the dynamic update of market relations and relationship strength. The stock market is highly temporally, and the attributes of nodes are affected by the time perception of other attributes, which is not fully considered. To address these problems, we propose a novel dynamic attributes-driven graph attention networks incorporating sentiment (DGATS) information, transaction data, and text data. Inspired by behavioral finance, we separately extract sentiment information as a factor of technical indicators, and further realize the early fusion of technical indicators and textual data through Kronecker product-based tensor fusion. In particular, by LSTM and temporal attention network, the short-term and long-term transition features are gradually grasped from the local composition of the fused stock trading sequence. Furthermore, real-time intra-market dependencies and key attributes information are captured with graph networks, enabling dynamic updates of relationships and relationship strengths in predefined graphs. Experiments on the real datasets show that the architecture can outperform the previous methods in prediction performance. [ABSTRACT FROM AUTHOR]

Nowadays, the explosive growth of personalized web applications and the rapid development of artificial intelligence technology have flourished the recent research on mobile user profiling, i.e., inferring the user profile from mobile behavioral data. Particularly, existing studies mainly follow the data-driven paradigm to develop feature engineering and representation learning on such data, which however suffer from the robustness issue, i.e., generalizing poorly across datasets and profiles without considering semantic knowledge therein. In comparison, the rising knowledge-driven paradigm built upon the knowledge graph (KG) offers a potential solution to mitigate such weakness. Therefore, in this article, we propose a Knowledge Graph aided framework for Mobile User Profiling (KG-MUP). Specifically, to distil semantic knowledge among data, we firstly construct an urban knowledge graph (UrbanKG) with domain entities like users, regions, point of interests (POIs), and so on. identified, as well as semantic relations for home, workplace, spatiality, and so on. extracted. Moreover, we leverage tensor decomposition and graph neural network to obtain knowledgeable user representations from UrbanKG. In addition, we introduce several customized features to quantify individual mobility characteristics for mobile user profiling. Extensive experiments on three real-world mobility datasets demonstrate that KG-MUP achieves state-of-the-art performance on user profile inference tasks. Moreover, further results also reveal the importance of various semantic knowledge to user profile inference, which provides meaningful insights on user modeling with mobile behavioral data. [ABSTRACT FROM AUTHOR]

In line with the general trend in artificial intelligence research to create intelligent systems that combine learning and symbolic components, a new sub-area has emerged that focuses on combining Machine Learning components with techniques developed by the SemanticWeb community--SemanticWebMachine Learning (SWeML). Due to its rapid growth and impact on several communities in thepast two decades, there is a need to better understand the space of these SWeML Systems, their characteristics, and trends. Yet, surveys that adopt principled and unbiased approaches are missing. To fill this gap, we performed a systematic study and analyzed nearly 500 papers published in the past decade in this area, where we focused on evaluating architectural and application-specific features. Our analysis identified a rapidly growing interest in SWeML Systems, with a high impact on several application domains and tasks. Catalysts for this rapid growth are the increased application of deep learning and knowledge graph technologies. By leveraging the in-depth understanding of this area acquired through this study, a further key contribution of this article is a classification system for SWeML Systems that we publish as ontology. [ABSTRACT FROM AUTHOR]

Programmers who work with smart contract development often encounter challenges in reusing code from repositories. This is due to the presence of two unknowns that can lead to non-functional and functional failures. These unknowns are implicit collaborations between functions and subtle differences among similar functions. Current code mining methods can extract syntax and semantic knowledge (known knowledge), but they cannot uncover these unknowns due to a significant gap between the known and the unknown. To address this issue, we formulate knowledge acquisition as a knowledge deduction task and propose an analytic flow that uses the function clone as a bridge to gradually deduce the known knowledge into the problem-solving knowledge that can reveal the unknowns. This flow comprises five methods: clone detection, co-occurrence probability calculation, function usage frequency accumulation, description propagation, and control flow graph annotation. This provides a systematic and coherent approach to knowledge deduction. We then structure all of the knowledge into a semantic-enriched code Knowledge Graph (KG) and integrate this KG into two software engineering tasks: code recommendation and crowd-scaled coding practice checking. As a proof of concept, we apply our approach to 5,140 smart contract files available on Etherscan.io and confirm high accuracy of our KG construction steps. In our experiments, our code KG effectively improved code recommendation accuracy by 6% to 45%, increased diversity by 61% to 102%, and enhanced NDCG by 1% to 21%. Furthermore, compared to traditional analysis tools and the debugging-with-the-crowd method, our KG improved time efficiency by 30 to 380 seconds, vulnerability determination accuracy by 20% to 33%, and vulnerability fixing accuracy by 24% to 40% for novice developers who identified and fixed vulnerable smart contract functions. [ABSTRACT FROM AUTHOR]

When searching code, developers may express additional constraints (e.g., functional constraints and nonfunctional constraints) on the implementations of desired functionalities in the queries. Existing code search tools treat the queries as a whole and ignore the different implications of different parts of the queries. Moreover, these tools usually return a ranked list of candidate code snippets without any explanations. Therefore, the developers often find it hard to choose the desired results and build confidence on them. In this article, we conduct a developer survey to better understand and address these issues and induct some insights from the survey results. Based on the insights, we propose XCoS, an explainable code search approach based on query scoping and knowledge graph. XCoS extracts a background knowledge graph from general knowledge bases like Wikidata and Wikipedia. Given a code search query, XCoS identifies different parts (i.e., functionalities, functional constraints, nonfunctional constraints) from it and use the expressions of functionalities and functional constraints to search the codebase. It then links both the query and the candidate code snippets to the concepts in the background knowledge graph and generates explanations based on the association paths between these two parts of concepts together with relevant descriptions. XCoS uses an interactive user interface that allows the user to better understand the associations between candidate code snippets and the query from different aspects and choose the desired results. Our evaluation shows that the quality of the extracted background knowledge and the concept linkings in codebase is generally high. Furthermore, the generated explanations are considered complete, concise, and readable, and the approach can help developers find the desired code snippets more accurately and confidently. [ABSTRACT FROM AUTHOR]

Recent years have seen an exponential growth (+98% in 2022 w.r.t. the previous year) of the number of research articles in the few-shot learning field, which aims at training machine learning models with extremely limited available data. The research interest toward few-shot learning systems for Named Entity Recognition (NER) is thus at the same time increasing. NER consists in identifying mentions of pre-defined entities from unstructured text, and serves as a fundamental step in many downstream tasks, such as the construction of Knowledge Graphs, or Question Answering. The need for a NER system able to be trained with few-annotated examples comes in all its urgency in domains where the annotation process requires time, knowledge and expertise (e.g., healthcare, finance, legal), and in low-resource languages. In this survey, starting from a clear definition and description of the few-shot NER (FS-NER) problem, we take stock of the current state-of-the-art and propose a taxonomy which divides algorithms in two macro-categories according to the underlying mechanisms: model-centric and data-centric. For each category, we line-up works as a story to show how the field is moving toward new research directions. Eventually, techniques, limitations, and key aspects are deeply analyzed to facilitate future studies. [ABSTRACT FROM AUTHOR]

Image-text retrieval aims to take the text (image) query to retrieve the semantically relevant images (texts), which is fundamental and critical in the search system, online shopping, and social network. Existing works have shown the effectiveness of visual-semantic embedding and unimodal knowledge exploiting (e.g., textual knowledge) in connecting the image and text. However, they neglect the implicit multimodal knowledge relations between these two modalities when the image contains information that is not directly described in the text, hindering the ability to connect the image and text with the implicit semantic relations. For instance, an image shows a person next to the "tap" but the pairing text description may only include the word "wash," missing the washing tool "tap." The implicit semantic relation between image object "tap" and text word "wash" can help to connect the above image and text. To sufficiently utilize the implicit multimodal knowledge relations, we propose a Multimodal Knowledge enhanced Visual-Semantic Embedding (MKVSE) approach building a multimodal knowledge graph to explicitly represent the implicit multimodal knowledge relations and injecting it to visual-semantic embedding for image-text retrieval task. The coNtributions in this article can be summarized as follows: (1) Multimodal Knowledge Graph (MKG) is proposed to explicitly represent the implicit multimodal knowledge relations between the image and text as intra-modal semantic relations and inter-modal co-occurrence relations. Intra-modal semantic relations provide synonymy information that is implicit in the unimodal data such as the text corpus. And inter-modal co-occurrence relations characterize the co-occurrence correlations (such as temporal, causal, and logical) that are implicit in image-text pairs. These two relations help establishing reliable image-text connections in the higher-level semantic space. (2) Multimodal Graph Convolution Networks (MGCN) is proposed to reason on the MKG in two steps to sufficiently utilize the implicit multimodal knowledge relations. In the first step, MGCN focuses on the intra-modal relations to distinguish other entities in the semantic space. In the second step, MGCN focuses on the inter-modal relations to connect multimodal entities based on co-occurrence correlations. The two-step reasoning manner can sufficiently utilize the implicit semantic relations between two modal entities to enhance the embeddings of the image and text. Extensive experiments are conducted on two widely used datasets, namely, Flickr30k and MSCOCO, to demonstrate the superiority of the proposed MKVSE approach in achieving state-of-the-art performances. The codes are available at https://github.com/PKU-ICST-MIPL/MKVSE-TOMM2023. [ABSTRACT FROM AUTHOR]

Every day, our living city produces a tremendous amount of spatial-temporal data, involved with multiple sources from the individual scale to the city scale. Undoubtedly, such massive urban data can be explored for a better city and better life, as what the urban computing community has been dedicating in recent years. Nevertheless, existing studies are still facing the challenges of data fusion for the urban data as well as the knowledge distillation for specific applications. Moreover, there is a lack of full-featured and user-friendly platforms for both researchers and developers in the urban computing scenario. Therefore, in this article, we present UrbanKG, an urban knowledge graph system to incorporate a knowledge graph with urban computing. Specifically, the system introduces a complete scheme to construct a knowledge graph for urban data fusion. Built upon the data layer, the system further develops the multiple layers of construction, storage, algorithm, operation, and applications, which achieve knowledge distillation and support various functions to the users. We perform representative use cases and demonstrate the system capability of boosting performance in various downstream applications, indicating a promising research direction for knowledge-driven urban computing. [ABSTRACT FROM AUTHOR]

Recently, with the development of temporal knowledge graph technology, more and more Temporal Knowledge Graph Embedded (TKGE) models have been developed. The effectiveness of TKGE largely depends on the ability to model intrinsic relation patterns and capture specific information about entities and relations. However, existing approaches can capture only some of them with insufficient modeling capacity, and none has a “deep” architecture for modeling the entries in a quadruple at the same dimension. In this article, we propose a more powerful KGE framework named DuCape, which combines a dual quaternion and capsule network in modeling for the first time to make up for the defects of existing TKGE models. In dual quaternion vector space, the head entity learns a k-dimensional rigid transformation parametrized by relation and time, falling near its corresponding tail entity. Further, we employ the embeddings of entities, relations, and time trained from dual quaternion vector space as the input to capsule networks. Experimental results on several basic datasets show that the DuCape model constructed in this article is superior to existing state-of-the-art models. [ABSTRACT FROM AUTHOR]

Knowledge-enhanced dialogue systems aim at generating factually correct and coherent responses by reasoning over knowledge sources, which is a promising research trend. The truly harmonious human-agent dialogue systems need to conduct engaging conversations from three aspects as humans, namely (1) stating factual contents (e.g., records in Wikipedia), (2) conveying subjective and informative opinions about objects (e.g., user discussions on Twitter), and (3) impressing interlocutors with diverse expression styles (e.g., personalized expression habits). The existing knowledge base is a standardized and unified coding for factual knowledge, which could not portray the other two kinds of knowledge to make responses more informative and expressive diverse. To address this, we present CrowdDialog, a crowd intelligence knowledge-enhanced dialogue system, which takes advantage of “crowd intelligence knowledge” extracted from social media (with rich subjective descriptions and diversified expression styles) to promote the performance of dialogue systems. Firstly, to thoroughly mine and organize the crowd intelligence knowledge underlying large-scale and unstructured online contents, we elaborately design the Crowd Intelligence Knowledge Graph (CIKG) structure, including the domain commonsense subgraph, descriptive subgraph, and expressive subgraph. Secondly, to reasonably integrate heterogeneous crowd intelligence knowledge into responses while ensuring logicality and fluency, we propose the Gated Fusion with Dynamic Knowledge-Dependent (GFDD) model, which generates responses from the semantic and syntactic perspective with the context-aware knowledge gate and dynamic knowledge decoding. Finally, extensive experiments over both Chinese and English dialogue datasets demonstrate that our approach GFDD outperforms competitive baselines in terms of both automatic evaluation and human judgments. Besides, ablation studies indicate that the proposed CIKG has the potential to promote dialogue systems to generate fluent, informative, and diverse dialogue responses. [ABSTRACT FROM AUTHOR]

ICT platforms for news production, distribution, and consumption must exploit the ever-growing availability of digital data. These data originate from different sources and in different formats; they arrive at different velocities and in different volumes. Semantic knowledge graphs (KGs) is an established technique for integrating such heterogeneous information. It is therefore well-aligned with the needs of news producers and distributors, and it is likely to become increasingly important for the news industry. This article reviews the research on using semantic knowledge graphs for production, distribution, and consumption of news. The purpose is to present an overview of the field; to investigate what it means; and to suggest opportunities and needs for further research and development. [ABSTRACT FROM AUTHOR]

A mobile agent navigating along edges of a simple connected unweighted graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure, or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch et al. [3] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s. The size of the tank is B = 2(1 + a)r, for some positive real constant a, where r, called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most -B° edge traversals between two consecutive visits at node s. Let e (d) be the number of edges whose at least one endpoint is at distance less than d from s. Awerbuch et al. [3] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e (d). We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost O(e (d) logd) and then show how to modify this algorithm to work in the model from Awerbuch et al. [3] with the same complexity. Thus, we refute the preceding 20-year-old conjecture. We observe that no treasure hunt algorithm can beat cost T(e (d)) for all graphs, and thus our algorithms are also almost optimal. [ABSTRACT FROM AUTHOR]

As a crucial part of natural language processing, event-centered commonsense inference task has attracted increasing attention. With a given observed event, the intention and reaction of the people involved in the event are required to be inferred with artificial intelligent algorithms. To solve this problem, sequence-tosequence methods are widely studied, where the event is first encoded into a specific representation and then decoded to generate the results. However, all the existing methods learn the event representation only with the textual information, while the visual information is ignored, which is actually helpful for the commonsense reference. In this article, we first define a new task of multi-modal commonsense reference with both textual and visual information. A new event-centered multi-modal dataset is also provided. Then we propose a multi-source knowledge reasoning graph network to solve this task, where three kinds of relational knowledge are considered. Multi-modal correlations are learned to get the event's multi-modal representation from a global perspective. Intra-event object relations are explored to capture the fine-grained event feature with an object graph. Inter-event semantic relations are also explored through the external knowledge to understand the semantic associations among events with an event graph. We conduct extensive experiments on the new dataset, and the results show the effectiveness of our method. [ABSTRACT FROM AUTHOR]