检索结果-内蒙古大学图书馆

IVE: Accelerating Enumeration-Based Subgraph Matching via Exploring Isolated Vertices 40

学校读者我要写书评

暂无评论

IVE: Accelerating Enumeration-Based Subgraph Matching via Ex...

40th IEEE International Conference on data Engineering, ICDE 2024

作者： Jiang, Zite Zhang, Shuai Hou, Xingzhong Yuan, Mengting You, Haihang Institute of Computing Technology CAS State Key Lab of Processors Beijing China School of Computer Science and Technology University of Chinese Academy of Sciences Beijinz China Zhongguancun Laboratory Beijing China School of Computer Science Wuhan University Wuhan China

ISBN: (纸本)9798350317152

The performance of the enumeration-based sub-graph matching, which searches all isomorphic subgraphs in the data graph, is crucial to various applications. The upper bound of the complexity for the enumeration-based method is exponential to the number of query graph vertices, denoted as n. We propose a novel subgraph matching algorithm called the Isolated Vertices Exploration (IVE). The IVE leverages isolated vertices during the reordering and enumeration phases, thereby significantly accelerating the subgraph matching process. During the enumeration, the isolated vertices can be matched by using a quick bipartite graph matching algorithm. Consequently, the complexity of matching the remaining non-isolated vertices is exponential to the number of non-isolated vertices, denoted as n'. For the reordering, we designed the Maximum Deleted Edges (MDE) to minimize n'. MDE iteratively selects the query vertex with the maximum edges. According to the experimental results, n' is less than 0.8n for 99.8% of arbitrary graphs. Moreover, IVE outperforms the state-of-the-art algorithms in various scenarios with different sizes, sparsities and fields, achieving a performance speedup of up to 80.3x. © 2024 IEEE.

关键词： Iterative methods

Graph convolutional networks using heat kernel for semi-supervised learning

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Xu, Bingbing Shen, Huawei Cao, Qi Cen, Keting Cheng, Xueqi CAS Key Laboratory of Network Data Science and Technology Institute of Computing Technology Chinese Academy of Sciences School of Computer Science and Technology University of Chinese Academy of Sciences Beijing China

Graph convolutional networks gain remarkable success in semi-supervised learning on graph-structured data. The key to graph-based semi-supervised learning is capturing the smoothness of labels or features over nodes exerted by graph structure. Previous methods, spectral methods and spatial methods, devote to defining graph convolution as a weighted average over neighboring nodes, and then learn graph convolution kernels to leverage the smoothness to improve the performance of graph-based semi-supervised learning. One open challenge is how to determine appropriate neighborhood that reflects relevant information of smoothness manifested in graph structure. In this paper, we propose GraphHeat, leveraging heat kernel to enhance low-frequency filters and enforce smoothness in the signal variation on the graph. GraphHeat leverages the local structure of target node under heat diffusion to determine its neighboring nodes flexibly, without the constraint of order suffered by previous methods. GraphHeat achieves state-of-the-art results in the task of graph-based semi-supervised classification across three benchmark datasets: Cora, Citeseer and Pubmed. Copyright © 2020, The Authors. All rights reserved.

关键词： Graphic methods

Iterative Utility Judgment Framework via LLMs Inspired by Relevance in Philosophy

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhang, Hengran Bi, Keping Guo, Jiafeng Cheng, Xueqi CAS Key Laboratory of Network Data Science and Technology Institute of Computing Technology Chinese Academy of Sciences China School of Computer Science and Technology University of Chinese Academy of Sciences China

Utility and topical relevance are critical measures in information retrieval (IR), reflecting system and user perspectives, respectively. While topical relevance has long been emphasized, utility is a higher standard of relevance and is more useful for facilitating downstream tasks, e.g., in Retrieval-Augmented Generation (RAG). When we incorporate utility judgments into RAG, we realize that the topical relevance, utility, and answering in RAG are closely related to the three types of relevance that Schutz discussed from a philosophical perspective. They are topical relevance, interpretational relevance, and motivational relevance, respectively. Inspired by the dynamic iterations of the three types of relevance, we propose an Iterative utiliTy judgmEnt fraMework (ITEM) to promote each step of the cycle of RAG. We conducted extensive experiments on multigrade passage retrieval and factoid questionanswering datasets (i.e., TREC DL, WebAP, and NQ). Experimental results demonstrate significant improvements in utility judgments, ranking of topical relevance, and answer generation upon representative baselines, including multiple single-shot utility judging approaches. Our code and benchmark can be found at https://anonymous.4open. science/r/ITEM-B486/. Copyright © 2024, The Authors. All rights reserved.

关键词： Search engines

Search from history and reason for future: Two-stage reasoning on temporal knowledge graphs

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Li, Zixuan Jin, Xiaolong Guan, Saiping Li, Wei Guo, Jiafeng Wang, Yuanzhuo Cheng, Xueqi School of Computer Science and Technology University of Chinese Academy of Sciences CAS Key Laboratory of Network Data Science and Technology Institute of Computing Technology Chinese Academy of Sciences Baidu Inc

Temporal Knowledge Graphs (TKGs) have been developed and used in many different areas. Reasoning on TKGs that predicts potential facts (events) in the future brings great challenges to existing models. When facing a prediction task, human beings usually search useful historical information (i.e., clues) in their memories and then reason for future meticulously. Inspired by this mechanism, we propose CluSTeR to predict future facts in a two-stage manner, Clue Searching and Temporal Reasoning, accordingly. Specifically, at the clue searching stage, CluSTeR learns a beam search policy via reinforcement learning (RL) to induce multiple clues from historical facts. At the temporal reasoning stage, it adopts a graph convolution network based sequence method to deduce answers from clues. Experiments on four datasets demonstrate the substantial advantages of CluSTeR compared with the state-of-the-art methods. Moreover, the clues found by CluSTeR further provide interpretability for the results. Copyright © 2021, The Authors. All rights reserved.

关键词： Knowledge graph

Semantic Structure Enhanced Event Causality Identification

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Hu, Zhilei Li, Zixuan Jin, Xiaolong Bai, Long Guan, Saiping Guo, Jiafeng Cheng, Xueqi School of Computer Science and Technology University of Chinese Academy of Sciences China CAS Key Laboratory of Network Data Science and Technology Institute of Computing Technology Chinese Academy of Sciences China

Event Causality Identification (ECI) aims to identify causal relations between events in unstructured texts. This is a very challenging task, because causal relations are usually expressed by implicit associations between events. Existing methods usually capture such associations by directly modeling the texts with pre-trained language models, which underestimate two kinds of semantic structures vital to the ECI task, namely, event-centric structure and event-associated structure. The former includes important semantic elements related to the events to describe them more precisely, while the latter contains semantic paths between two events to provide possible supports for ECI. In this paper, we study the implicit associations between events by modeling the above explicit semantic structures, and propose a Semantic Structure Integration model (SemSIn). It utilizes a GNN-based event aggregator to integrate the event-centric structure information, and employs an LSTM-based path aggregator to capture the event-associated structure information between two events. Experimental results on three widely used datasets show that SemSIn achieves significant improvements over baseline methods. Copyright © 2023, The Authors. All rights reserved.

关键词： Modeling languages

Robust Neural Information Retrieval: An Adversarial and Out-of-distribution Perspective

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Liu, Yu-An Zhang, Ruqing Guo, Jiafeng de Rijke, Maarten Fan, Yixing Cheng, Xueqi CAS Key Lab of Network Data Science and Technology Institute of Computing Technology Chinese Academy of Sciences University of Chinese Academy of Sciences No. 6 Kexueyuan South Road Haidian District Beijing100190 China University of Amsterdam Amsterdam Netherlands CAS Key Lab of Network Data Science and Technology Institute of Computing Technology Chinese Academy of Sciences University of Chinese Academy of Sciences Beijing China

Recent advances in neural information retrieval models have significantly enhanced these models’ effectiveness across various information retrieval tasks. The robustness of these models, which is essential for ensuring their reliability in practice, has also garnered significant attention. With a wide array of research on robust IR being published, we believe it is the opportune moment to consolidate the current status, glean insights from existing methodologies, and lay the groundwork for future development. We view the robustness of information retrieval to be a multifaceted concept, emphasizing its necessity against adversarial attacks, out-of-distribution scenarios, and performance variance. With a focus on adversarial and out-of-distribution robustness, we dissect robustness solutions for dense retrieval models and neural ranking models, respectively, recognizing them as pivotal components of the neural information retrieval pipeline. We provide an in-depth discussion of methods, datasets, and evaluation metrics, shedding light on challenges and future directions in the era of large language models. As side-products of this survey, we release three additional resources: (i) a curated list of publications related to robust IR,1 (ii) a tutorial based on this survey,2 and (iii) a heterogeneous benchmark for robust information retrieval, BestIR, that collects all known datasets for evaluation information retrieval systems for robustness.3 We hope that this study provides useful clues for future research on the robustness of IR models and helps to develop trustworthy search engines. Copyright © 2024, The Authors. All rights reserved.

关键词： Adversarial machine learning

Challenges and Advances in Generative Information Retrieval 22

学校读者我要写书评

暂无评论

Challenges and Advances in Generative Information Retrieval

22nd Chinese National Conference on Computational Linguistics, CCL 2023

作者： Fan, Yixing Tang, Yubao Chen, Jiangui Zhang, Ruqing Guo, Jiafeng CAS Key Lab of Network Data Science and Technology Institute of Computing Technology Chinese Academy of Sciences Beijing100190 China University of Chinese Academy of Sciences Beijing100190 China

ISBN: (纸本)9781713889892

Information retrieval (IR) aims to seek relevant information in response to user queries. Existing IR systems mainly rely on the "index-retrieve-then-rank" framework, which models the complex retrieval tasks as a multi-stage search process. Such a decoupling process improves the efficiency of the system, making it possible for retrieval system to handle billions of documents. However, it also increase the complexity of the search architecture, making it difficult to achieve end-to-end optimization. To address this issue, researchers have begun to explore a new paradigm of generative information retrieval. This new paradigm encodes the entire corpus into the search model, enabling end-to-end optimization and eliminating the dependence on external indices. Currently, generative information retrieval has become a hot research direction in IR, and researchers have proposed different solutions to improve retrieval effectiveness. Given the rapid progress in this direction, this article provides a systematic review of generative information retrieval, including basic concepts, document identifiers, model architectures, and model capacity. In addition, we also discuss some unresolved challenges and promising research directions, hoping to inspire and promote future research on these topics. © 2023 China National Conference on Computational Linguistics.

关键词： Computational linguistics

Quantum-to-quantum Bernoulli factory problem

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Jiang, Jiaqing Zhang, Jialin Sun, Xiaoming Cas Key Lab of Network Data Science and Technology Institute of Computing Technology Chinese Academy of Sciences Beijing100190 China University of Chinese Academy of Sciences Beijing100049 China

Given a coin with unknown bias p ϵ [0,1], can we exactly simulate another coin with bias f(p)? The exact set of simulable functions has been well characterized 20 years ago. In this paper, we ask the quantum counterpart of this question: Given the quantum coin |p) = √p|0)+√1-p|1), can we exactly simulate another quantum coin |f(p)) =√f(p)|0)+√1-f(p)|1)? We give the full characterization of simulable quantum state k0(p)|0)+ k1(p)|1) from quantum coin |p) = √p|0)+ √1-p|1), and present an algorithm to transform it. Surprisingly, we show that simulable sets in the quantum-to-quantum case and classical-to-classical case have no inclusion relationship with each other. Copyright © 2017, The Authors. All rights reserved.

关键词：

LINKAGE: Listwise Ranking among Varied-Quality References for Non-Factoid QA Evaluation via LLMs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Yang, Sihui Bi, Keping Cui, Wanqing Guo, Jiafeng Cheng, Xueqi CAS Key Laboratory of Network Data Science and Technology Institute of Computing Technology Chinese Academy of Sciences China University of Chinese Academy of Sciences Beijing China

Non-Factoid (NF) Question Answering (QA) is challenging to evaluate due to diverse potential answers and no objective criterion. The commonly used automatic evaluation metrics like ROUGE or BERTScore cannot accurately measure semantic similarities or answers from different perspectives. Recently, Large Language Models (LLMs) have been resorted to for NFQA evaluation due to their compelling performance on various NLP tasks. Common approaches include pointwise scoring of each candidate answer and pairwise comparisons between answers. Inspired by the evolution from pointwise to pairwise to listwise in learning-to-rank methods, we propose a novel listwise NFQA evaluation approach, that utilizes LLMs to rank candidate answers in a list of reference answers sorted by descending quality. Moreover, for NF questions that do not have multi-grade or any golden answers, we leverage LLMs to generate the reference answer list of various quality to facilitate the listwise evaluation. Extensive experimental results on three NFQA datasets, i.e., ANTIQUE, the TREC-DL-NF, and WebGLM show that our method has significantly higher correlations with human annotations compared to automatic scores and common pointwise and pairwise approaches. Our code and dataset can be found at https://***/babyyang525/ LINKAGE-Listwise-NFQA-Evaluation. Copyright © 2024, The Authors. All rights reserved.

关键词： Semantics