論文の概要: FastGFDs: Efficient Validation of Graph Functional Dependencies with Desbordante
- arxiv url: http://arxiv.org/abs/2608.02321v1
- Date: Mon, 03 Aug 2026 14:46:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-04 15:07:25.605957
- Title: FastGFDs: Efficient Validation of Graph Functional Dependencies with Desbordante
- Title（参考訳）: FastGFD: Desbordanteによるグラフ関数依存の効率的な検証
- Abstract要約: グラフ関数依存(GFD)は、最近開発された概念であり、グラフ内のトポロジ構造と属性間の関数依存の両方をキャプチャすることを目的としている。
本研究の目的は、GFD検証を一般向けに開放し、コンシューマークラスPC上で実行できるようにすることである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Graph functional dependencies (GFD) are a recently-developed concept aimed at capturing both topological structures in graphs and functional dependencies between attributes. The process of verifying whether a given GFD holds over a particular graph is referred to as GFD validation. In this very computationally expensive problem, locating suitable subgraphs accounts for about 99% of the total run time. The concept's authors originally proposed a parallel scheme (algorithm), targeting specifically clusters of high-performance servers. The goal of this study is to open GFD validation to a broader public by making it possible to run it on a consumer class PC. Our initial experiments demonstrated that the existing algorithm may not be optimal for these purposes. Therefore, we propose FastGFDs - a GFD validation algorithm that employs a recently developed graph matching technique. In contrast to the parallel scheme, it is sequential and operates on the entire graph. Its novelty lies in the use of Core-First Decomposition and the Compact Path Index (CPI). We compare it with the naive sequential algorithm and the parallel scheme, evaluating run times and memory consumption. The current study is the first step towards designing an efficient algorithm for GFD validation in low-end single-node environments. We also provide an open-source implementation of GFD validation over large data graphs. To the best of our knowledge, this is the only publicly available implementation of an algorithm for this problem. It is developed in Desbordante - an open-source high-performance data profiler aimed at science-intensive tasks. Finally, our experiments on a real-life graph demonstrated up to three times performance (2.6x on average) improvement over the parallel scheme. Employing the new subgraph matching algorithm also reduced memory consumption by five times.
- Abstract（参考訳）: グラフ関数依存(GFD)は、最近開発された概念であり、グラフ内のトポロジ構造と属性間の関数依存の両方をキャプチャすることを目的としている。
与えられたGFDが特定のグラフの上に保持するかどうかを検証する過程をGFD検証(GFD Validation)と呼ぶ。
この非常に計算に費用がかかる問題では、適切な部分グラフの配置は総実行時間の約99%を占める。
この概念の著者はもともと、特に高性能サーバのクラスタをターゲットにした並列スキーム(algorithm)を提案した。
本研究の目的は、GFD検証を一般向けに開放し、コンシューマークラスPC上で実行できるようにすることである。
最初の実験では、既存のアルゴリズムがこれらの目的に最適でないことを示した。
そこで本研究では,最近開発されたグラフマッチング手法を用いたGFD検証アルゴリズムであるFastGFDを提案する。
並列スキームとは対照的に、シーケンシャルであり、グラフ全体で動作する。
その斬新さは、Core-First DecompositionとCompact Path Index (CPI)の使用にある。
本手法は,実行時間とメモリ使用量を評価することで,素性のある逐次アルゴリズムと並列スキームと比較する。
この研究は、ローエンド単一ノード環境におけるGFDバリデーションのための効率的なアルゴリズムを設計するための最初のステップである。
また,大規模データグラフ上でのGFD検証のオープンソース実装も提供する。
我々の知る限りでは、この問題に対するアルゴリズムの実装はこれが唯一の公開である。
Desbordante - 科学集約的なタスクを対象としたオープンソースの高性能データプロファイラ。
最後に,実生活グラフを用いた実験により,並列方式よりも3倍の性能(平均2.6倍)向上を示した。
新しいサブグラフマッチングアルゴリズムを使用することで、メモリ消費も5倍削減された。
関連論文リスト
- Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
粗大化における近隣住民の集団干渉を優先する非利己的原則を提案する。
局所等方性仮定に基づいて、O(dot d)干渉評価をO(d)に還元する高速なNOPE*を導出する。
粗いグラフの学習は、元のグラフに匹敵する性能を示し、LLMベースのグラフ推論よりも優れた性能を示すことができる。
論文 参考訳（メタデータ） (2026-05-13T05:24:35Z) - AutoGraph-R1: End-to-End Reinforcement Learning for Knowledge Graph Construction [60.51319139563509]
強化学習(RL)を用いたタスクパフォーマンスのKG構築を直接最適化する最初のフレームワークであるAutoGraph-R1を紹介する。
我々は2つの新しいタスク対応報酬関数を設計し、1つは知識担体としてのグラフと、もう1つは知識指標としてのグラフを設計する。
私たちの研究は、構築とアプリケーションの間のループを閉じることが可能であることを示している。
論文 参考訳（メタデータ） (2025-10-17T06:03:36Z) - Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMs [15.558119182035995]
検索型拡張フレームワーク(GRRAF)を用いた新しい学習不要なグラフ推論手法を提案する。
GRRAFは、大規模な言語モデル(LLM)のコード生成機能とともに、検索拡張生成(RAG)を活用して、幅広いグラフ推論タスクに対処する。
GraphInstructデータセットの実験的評価により、ほとんどのグラフ推論タスクにおいて、GRRAFが100%の精度を達成することが明らかになった。
論文 参考訳（メタデータ） (2025-09-16T06:58:58Z) - Align-GRAG: Reasoning-Guided Dual Alignment for Graph Retrieval-Augmented Generation [79.75818239774952]
大きな言語モデル(LLM)は目覚ましい能力を示しているが、幻覚や時代遅れの情報といった問題に苦戦している。
Retrieval-augmented Generation (RAG) は、情報検索システム(IR)を用いて、外部知識のLLM出力を基底にすることで、これらの問題に対処する。
本稿では、検索後句における新しい推論誘導二重アライメントフレームワークであるAlign-GRAGを提案する。
論文 参考訳（メタデータ） (2025-05-22T05:15:27Z) - PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms [14.601622103700516]
グラフのクラスタリングノードは、グラフ解析の土台である。
いくつかの一般的な方法は、非常に大きなグラフには適さない。
この研究は、クラスタリングアルゴリズムを高速化するオーバーレイであるPASCOを導入している。
論文 参考訳（メタデータ） (2024-12-18T08:15:55Z) - Amplify Graph Learning for Recommendation via Sparsity Completion [16.32861024767423]
グラフ学習モデルは、協調フィルタリング(CF)ベースのレコメンデーションシステムに広くデプロイされている。
データ疎度の問題により、元の入力のグラフ構造は潜在的な肯定的な嗜好エッジを欠いている。
AGL-SC(Amplify Graph Learning framework)を提案する。
論文 参考訳（メタデータ） (2024-06-27T08:26:20Z) - SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
テキストグラフ学習におけるフラストレーションに富んだアプローチであるSimTeGを提案する。
まず、下流タスクで予め訓練されたLM上で、教師付きパラメータ効率の微調整(PEFT)を行う。
次に、微調整されたLMの最後の隠れ状態を用いてノード埋め込みを生成する。
論文 参考訳（メタデータ） (2023-08-03T07:00:04Z) - NAS-Bench-Graph: Benchmarking Graph Neural Architecture Search [55.75621026447599]
NAS-Bench-Graphは、GraphNASの統一的、再現可能、効率的な評価をサポートする調整されたベンチマークである。
具体的には,26,206のユニークなグラフニューラルネットワーク(GNN)アーキテクチャを網羅した,統一的で表現力のあるコンパクトな検索空間を構築する。
提案したベンチマークに基づいて,GNNアーキテクチャの性能を検索テーブルから直接取得できるが,それ以上の計算は行わない。
論文 参考訳（メタデータ） (2022-06-18T10:17:15Z) - Source Free Unsupervised Graph Domain Adaptation [60.901775859601685]
Unsupervised Graph Domain Adaptation (UGDA) はノード分類のラベル付けコストを削減するための実用的価値を示している。
既存のUGDAメソッドの多くは、ソースドメインのラベル付きグラフに大きく依存している。
現実のシナリオでは、ソースグラフはプライバシーの問題のためにアクセスできない。
我々は、Source Free Unsupervised Graph Domain Adaptation (SFUGDA) という新しいシナリオを提案する。
論文 参考訳（メタデータ） (2021-12-02T03:18:18Z) - CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
グラフニューラルネットワーク(GNN)はこのタスクにデータ駆動型ソリューションを提供する。
既存のGNNベースの手法は、それぞれ2つのグラフを埋め込んだり、グラフ全体のクロスグラフインタラクションをデプロイしたりするが、まだ競合する結果が得られない。
このフレームワークは,まず適応的なプーリング操作で大きなグラフを埋め込んで粗くし,最後に類似点を求めるために粗いグラフにきめ細かな相互作用を展開させる。
論文 参考訳（メタデータ） (2020-05-14T16:33:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。