Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport

• URL: http://arxiv.org/abs/2305.04034v1
• Date: Sat, 6 May 2023 12:48:17 GMT
• Title: Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport
• Abstract summary: This work investigates the local and global trade-off with unbalanced optimal transport theory. We embed sets as bounded measures in $real$ with a scoring function motivated by the Wasserstein-Fisher-Rao metric. Results show that WFRE can outperform existing query embedding methods on standard datasets.
• Score: 33.283368906484746
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Answering complex queries on knowledge graphs is important but particularly challenging because of the data incompleteness. Query embedding methods address this issue by learning-based models and simulating logical reasoning with set operators. Previous works focus on specific forms of embeddings, but scoring functions between embeddings are underexplored. In contrast to existing scoring functions motivated by local comparison or global transport, this work investigates the local and global trade-off with unbalanced optimal transport theory. Specifically, we embed sets as bounded measures in $\real$ endowed with a scoring function motivated by the Wasserstein-Fisher-Rao metric. Such a design also facilitates closed-form set operators in the embedding space. Moreover, we introduce a convolution-based algorithm for linear time computation and a block-diagonal kernel to enforce the trade-off. Results show that WFRE can outperform existing query embedding methods on standard datasets, evaluation sets with combinatorially complex queries, and hierarchical knowledge graphs. Ablation study shows that finding a better local and global trade-off is essential for performance improvement.

Related papers

• Unifying Graph Neural Networks Through a Common Layer Equation [75.88127999406392]
  We introduce a common layer equation that represents covered architectures through seven components.<n>The central factorization separates where information moves, encoded by the propagation bank, from what moves, encoded by the message maps.<n>We make this unification explicit and checkable through worked reductions of canonical layers and component assignments.
  arXiv  Detail & Related papers  (2026-08-17T04:37:59Z)
• Pretraining on Call Graphs: When Binary Analysis Tasks Profit From Context [7.347989843033034]
  We conduct experiments using a range of graph-based models on the embeddings generated by two state-of-the-art binary function embedding models.<n>We find that optimizing for semantic similarity tasks correlates with worse performance on syntactic tasks.
  arXiv  Detail & Related papers  (2026-08-03T11:44:09Z)
• Beyond Query Memorization: Large Language Model Routing with Query Decomposition and Historical Matching [6.980897284458787]
  DecoR recasts the routing task as a matching process of sifting similar queries from historical logs.<n>To enhance matching accuracy, we introduce a query capability that decouples linguistic surface forms from task-intrinsic requirements.
  arXiv  Detail & Related papers  (2026-05-25T08:12:58Z)
• Coupled Hierarchical Search over Topology and Execution for Agentic Workflow Synthesis [64.2820121997882]
  We introduce HierFlow, a training-free, test-time hierarchical search architecture that automates agentic workflow design.<n> HierFlow maximizes efficiency through an intelligent gating module that selectively triggers execution-level searches based on contextual necessity.<n> Comprehensive testing across question answering, mathematical reasoning, and code generation benchmarks confirms that HierFlow consistently outperforms strong baselines.
  arXiv  Detail & Related papers  (2026-05-20T01:56:11Z)
• Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees [10.806910118253976]
  Graph-based Retrieval-Augmented Generation (RAG) systems leverage interconnected knowledge structures to capture complex relationships.<n>We propose Query-Aware Flow Diffusion RAG (QAFD-RAG), a training-free framework that dynamically adapts graph traversal to each query's holistic semantics.<n>QAFD-RAG recovers relevant subgraphs with high probability under mild signal-to-noise conditions.
  arXiv  Detail & Related papers  (2026-04-21T08:53:34Z)
• Efficient Causal Structure Learning via Modular Subgraph Integration [4.803851977437455]
  We introduce VISTA, a modular framework that decomposes the global causal structure learning problem into local subgraphs based on Blankets.<n>The framework is model-agnostic, imposing no assumptions on the inductive biases of base learners, is compatible with arbitrary data settings, and fully supports parallelization.<n>Extensive experiments on both synthetic and real datasets consistently demonstrate the effectiveness of VISTA.
  arXiv  Detail & Related papers  (2026-01-28T20:13:20Z)
• Leveraging Knowledge Graphs and LLM Reasoning to Identify Operational Bottlenecks for Warehouse Planning Assistance [1.2749527861829046]
  Our framework integrates Knowledge Graphs (KGs) and Large Language Model (LLM)-based agents.<n>It transforms raw DES data into a semantically rich KG, capturing relationships between simulation events and entities.<n>An LLM-based agent uses iterative reasoning, generating interdependent sub-questions. For each sub-question, it creates Cypher queries for KG interaction, extracts information, and self-reflects to correct errors.
  arXiv  Detail & Related papers  (2025-07-23T07:18:55Z)
• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAG is a multi-agent RAG framework that addresses the limitations with question-driven semantic graph partitioning and collaborative subgraph retrieval.<n>The innovative framework first create Semantic Partitioning of Linked Information, then use the Type-Specialized knowledge base to achieve Multi-Agent RAG.<n>The attribute-aware graph segmentation manages to divide knowledge graphs into semantically coherent subgraphs, ensuring subgraphs align with different query types.<n>A hierarchical merging module resolves inconsistencies across subgraph-derived answers through logical verifications.
  arXiv  Detail & Related papers  (2025-05-20T06:44:34Z)
• TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization [2.4783546111391215]
  Density-based clustering methods by mode-seeking usually achieve clustering by using local density estimation to mine structural information. We propose a new algorithm (TANGO) to establish local dependencies by exploiting a global-view emphtypicality of points. It achieves final clustering by employing graph-cut on sub-clusters, thus avoiding the challenging selection of cluster centers.
  arXiv  Detail & Related papers  (2024-08-19T15:26:25Z)
• A Framework for testing Federated Learning algorithms using an edge-like environment [0.0]
  Federated Learning (FL) is a machine learning paradigm in which many clients cooperatively train a single centralized model while keeping their data private and decentralized. It is non-trivial to accurately evaluate the contributions of local models in global centralized model aggregation. This is an example of a major challenge in FL, commonly known as data imbalance or class imbalance. In this work, a framework is proposed and implemented to assess FL algorithms in a more easy and scalable way.
  arXiv  Detail & Related papers  (2024-07-17T19:52:53Z)
• Implicitly Guided Design with PropEn: Match your Data to Follow the Gradient [52.2669490431145]
  PropEn is inspired by'matching', which enables implicit guidance without training a discriminator. We show that training with a matched dataset approximates the gradient of the property of interest while remaining within the data distribution.
  arXiv  Detail & Related papers  (2024-05-28T11:30:19Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  We propose a complex reasoning schema over KG upon large language models (LLMs) We augment the arbitrary first-order logical queries via binary tree decomposition to stimulate the reasoning capability of LLMs. Experiments across widely used datasets demonstrate that LACT has substantial improvements(brings an average +5.5% MRR score) over advanced methods.
  arXiv  Detail & Related papers  (2024-05-02T18:12:08Z)
• $\ ext{EFO}_{k}$-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation [36.77373013615789]
  We propose a framework for data generation, model training, and method evaluation. We construct a dataset, $textEFO_k$-CQA, with 741 types of query for empirical evaluation.
  arXiv  Detail & Related papers  (2023-07-15T13:18:20Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• Neural-Symbolic Entangled Framework for Complex Query Answering [22.663509971491138]
  We propose a Neural and Entangled framework (ENeSy) for complex query answering. It enables the neural and symbolic reasoning to enhance each other to alleviate the cascading error and KG incompleteness. ENeSy achieves the SOTA performance on several benchmarks, especially in the setting of the training model only with the link prediction task.
  arXiv  Detail & Related papers  (2022-09-19T06:07:10Z)
• Probabilistic Entity Representation Model for Chain Reasoning over Knowledge Graphs [18.92547855877845]
  We propose a Probabilistic Entity Representation Model (PERM) for logical reasoning over Knowledge Graphs. PERM encodes entities as a Multivariate Gaussian density with mean and covariance parameters to capture semantic position and smooth decision boundary. We demonstrate PERM's competence on a COVID-19 drug-repurposing case study and show that our proposed work is able to recommend drugs with substantially better F1 than current methods.
  arXiv  Detail & Related papers  (2021-10-26T09:26:10Z)
• Fewer is More: A Deep Graph Metric Learning Perspective Using Fewer Proxies [65.92826041406802]
  We propose a Proxy-based deep Graph Metric Learning approach from the perspective of graph classification. Multiple global proxies are leveraged to collectively approximate the original data points for each class. We design a novel reverse label propagation algorithm, by which the neighbor relationships are adjusted according to ground-truth labels.
  arXiv  Detail & Related papers  (2020-10-26T14:52:42Z)
• Locally induced Gaussian processes for large-scale simulation experiments [0.0]
  We show how placement of inducing points and their multitude can be thwarted by pathologies. Our proposed methodology hybridizes global inducing point and data subset-based local GP approximation. We show that local inducing points extend their global and data-subset component parts on the accuracy--computational efficiency frontier.
  arXiv  Detail & Related papers  (2020-08-28T21:37:46Z)
• A Trainable Optimal Transport Embedding for Feature Aggregation and its Relationship to Attention [96.77554122595578]
  We introduce a parametrized representation of fixed size, which embeds and then aggregates elements from a given input set according to the optimal transport plan between the set and a trainable reference. Our approach scales to large datasets and allows end-to-end training of the reference, while also providing a simple unsupervised learning mechanism with small computational cost.
  arXiv  Detail & Related papers  (2020-06-22T08:35:58Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.