論文の概要: Triadic First-Order Logic Queries in Temporal Networks

• arxiv url: http://arxiv.org/abs/2507.17215v1
• Date: Wed, 23 Jul 2025 05:12:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-24 22:33:14.865546
• Title: Triadic First-Order Logic Queries in Temporal Networks
• Title（参考訳）: テンポラルネットワークにおける三進一階論理クエリ
• Authors: Omkar Bhalerao, Yunjie Pan, C. Seshadhri, Nishil Talati,
• Abstract要約: 本稿では,大規模時間ネットワークのための「閾値一階論理(FOL)モチーフ解析」について紹介する。 FOLTYは,70万近いエッジを持つグラフ上で,コモディティハードウェア上で1時間以内の3進的なFOLクエリに答えることができることを示す。 我々の研究は、モチーフ分析の古典的な研究課題において、新たな研究の方向性を始める可能性を秘めている。
• 参考スコア（独自算出の注目度）: 5.114632024458956
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Motif counting is a fundamental problem in network analysis, and there is a rich literature of theoretical and applied algorithms for this problem. Given a large input network $G$, a motif $H$ is a small "pattern" graph indicative of special local structure. Motif/pattern mining involves finding all matches of this pattern in the input $G$. The simplest, yet challenging, case of motif counting is when $H$ has three vertices, often called a "triadic" query. Recent work has focused on "temporal graph mining", where the network $G$ has edges with timestamps (and directions) and $H$ has time constraints. Inspired by concepts in logic and database theory, we introduce the study of "thresholded First Order Logic (FOL) Motif Analysis" for massive temporal networks. A typical triadic motif query asks for the existence of three vertices that form a desired temporal pattern. An "FOL" motif query is obtained by having both existential and thresholded universal quantifiers. This allows for query semantics that can mine richer information from networks. A typical triadic query would be "find all triples of vertices $u,v,w$ such that they form a triangle within one hour". A thresholded FOL query can express "find all pairs $u,v$ such that for half of $w$ where $(u,w)$ formed an edge, $(v,w)$ also formed an edge within an hour". We design the first algorithm, FOLTY, for mining thresholded FOL triadic queries. The theoretical running time of FOLTY matches the best known running time for temporal triangle counting in sparse graphs. We give an efficient implementation of FOLTY using specialized temporal data structures. FOLTY has excellent empirical behavior, and can answer triadic FOL queries on graphs with nearly 70M edges is less than hour on commodity hardware. Our work has the potential to start a new research direction in the classic well-studied problem of motif analysis.
• Abstract（参考訳）: モティフカウントはネットワーク解析の基本的な問題であり、この問題には理論と応用アルゴリズムの豊富な文献がある。 大きな入力ネットワークが$G$を与えられたとき、モチーフ$H$は特別な局所構造を示す小さな「パターン」グラフである。 モチーフ/パターンマイニングは、入力$G$内のこのパターンのすべてのマッチを見つけることを伴う。 最も単純だが難しいモチーフカウントのケースは、$H$が3つの頂点を持つ場合である。 最近の研究は「時間グラフマイニング」に焦点を当てており、ネットワーク$G$はタイムスタンプ(と方向)を持つエッジを持ち、$H$は時間制約を持つ。 論理学とデータベース理論の概念に着想を得て,大規模時間ネットワークのための「一階論理(FOL)モチーフ解析」の研究を紹介する。 典型的な三進モチーフクエリは、望ましい時間パターンを形成する3つの頂点の存在を要求する。 FOL」モチーフクエリは、存在量と閾値付き普遍量化器の両方を有することにより得られる。 これにより、よりリッチな情報をネットワークからマイニングできるクエリセマンティクスが可能になる。 典型的な三進的クエリは、"1時間以内に三角形を形成するように、頂点のすべての三重を$u,v,w$とする"。 閾値付き FOL クエリは "find all pairs $u,v$ that for half of $w$ where $(u,w)$ formed a edge, $(v,w)$ also formed a edge within a hour" と表現できる。 我々は、しきい値付きFOL3進クエリをマイニングするための最初のアルゴリズムFOLTYを設計する。 FOLTYの理論的実行時間は、スパースグラフにおける時間的三角形計数における最もよく知られた実行時間と一致する。 特殊な時間的データ構造を用いたFOLTYの効率的な実装を提案する。 FOLTYは優れた経験的振る舞いを持ち、70万近いエッジを持つグラフ上の3進的なFOLクエリは、コモディティハードウェア上で1時間未満である。 我々の研究は、モチーフ分析の古典的な研究課題において、新たな研究の方向性を始める可能性を秘めている。

関連論文リスト

• TIMEST: Temporal Information Motif Estimator Using Sampling Trees [5.114632024458956]
  本稿では,時間的ネットワークにおける任意の大きさの時間的モチーフをカウントする汎用的,高速,高精度な推定アルゴリズムTIMESTを提案する。 TIMESTは,従来のアルゴリズムよりも高速かつ高精度であることを示す。 例えば、TIMESTは4分間の時間的モチーフのインスタンス数を0.6%エラーでカウントでき、正確なメソッドは2日以上かかる。
  論文  参考訳（メタデータ） (2025-07-27T23:31:55Z)
• Efficiently Constructing Sparse Navigable Graphs [11.317292211864013]
  我々は任意の距離関数の下で$O(log n)$-approximate sparsest navigable graphを構築するための$tildeO(n2)$ timeアルゴリズムを提案する。 また、本手法は、$alpha$-shortcut reachable と $tau$-monotonic graph を構築する際に、密接に関連し、実質的に重要な問題に対して立方体時間を超えることができることを示す。
  論文  参考訳（メタデータ） (2025-07-17T17:04:18Z)
• RaaS: Reasoning-Aware Attention Sparsity for Efficient LLM Reasoning [14.409253716114213]
  大規模言語モデル(LLM)は、様々な領域にまたがる強力な機能を示している。 これらのアルゴリズムは、正確さ、時間、記憶の「不可能なトリニティ」に苦しむ。 本稿では,マイルストーントークンを識別し,KVベクトルを不要になるまで保持するアルゴリズム RaaS を提案する。
  論文  参考訳（メタデータ） (2025-02-16T14:28:52Z)
• FLARE: Faithful Logic-Aided Reasoning and Exploration [50.9814063216852]
  タスク分解を用いて問題空間をトラバースする新しい手法を提案する。 我々はLarge Language Modelsを使ってソリューションを計画し、クエリを事実に軟式化し、論理プログラミングコードを使って述語する。 提案手法は,生成したコードに対する推論プロセスの忠実度を計算し,外部の解法に頼らずにマルチホップ探索のステップを解析する。
  論文  参考訳（メタデータ） (2024-10-14T19:39:11Z)
• Accurate and Fast Estimation of Temporal Motifs using Path Sampling [5.114632024458956]
  モチーフと呼ばれる小さな部分グラフの数を数えることは、ソーシャルネットワークの分析とグラフマイニングの根本的な問題である。 本稿では,時間的経路サンプリングの新しい手法を用いて,この問題に対処するアルゴリズムTEACUPSを提案する。 数十億のエッジを持つBitcoinグラフの場合、TEACUPSは1分以内で実行され、正確なカウントアルゴリズムは1日以上かかる。
  論文  参考訳（メタデータ） (2024-09-13T16:48:39Z)
• A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
  本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。 特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-28T21:23:40Z)
• Once Upon a $\textit{Time}$ in $\textit{Graph}$: Relative-Time Pretraining for Complex Temporal Reasoning [96.03608822291136]
  我々は時間の性質を生かし、時間軸に沿った事象の相対的な配置に基づくグラフ構造の構築を提案する。 グラフビューにインスパイアされたRemeMoを提案する。これは2つの文間の時間関係をモデル化することによって、時間的に観察されたすべての事実を明示的に接続する。 実験の結果、RemeMoは複数の時間的質問応答データセット上でベースラインT5よりも優れていた。
  論文  参考訳（メタデータ） (2023-10-23T08:49:00Z)
• Most Neural Networks Are Almost Learnable [52.40331776572531]
  固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。 このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。 シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
  論文  参考訳（メタデータ） (2023-05-25T22:27:42Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  時間グラフは連続時間を通してノード間の動的相互作用を示す。 本研究では,周辺地域全体と時間的グラフ畳み込みの新たな手法を提案する。 提案するTAP-GNNは,予測性能とオンライン推論遅延の両面で,既存の時間グラフ手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2023-04-15T08:17:18Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points [45.15780579276503]
  Wesfeiler--Lehman テストが完全距離グラフで表されるユークリッド点の雲に対して完備であるときの研究を行う。 $d$次元ユークリッド空間の任意の2つの非等尺点雲を区別するのに十分な次元はいくつあるか。 我々の主な結果は、$(d-1)$-dimensional WL テストが$d$-dimensional Euclidean 空間の点雲に対して完備であり、任意の$dge 2$ に対して完備であり、テストサッフィスを3回だけ繰り返すことである。
  論文  参考訳（メタデータ） (2023-03-22T18:23:24Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Temporal Graph Network Embedding with Causal Anonymous Walks Representations [54.05212871508062]
  本稿では,時間グラフネットワークに基づく動的ネットワーク表現学習のための新しいアプローチを提案する。 評価のために、時間的ネットワーク埋め込みの評価のためのベンチマークパイプラインを提供する。 欧州の大手銀行が提供した実世界のダウンストリームグラフ機械学習タスクにおいて、我々のモデルの適用性と優れた性能を示す。
  論文  参考訳（メタデータ） (2021-08-19T15:39:52Z)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。 我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。 トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
  論文  参考訳（メタデータ） (2020-06-28T04:37:57Z)
• Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis [7.99536002595393]
  本稿では,ネットワーク上あるいはそのモラル化されたグラフ上に制約を加える際に,最適なベイズネットワークの構造を学習する問題について検討する。 モラル化されたグラフに少なくとも$k$のエッジを持つ最適ネットワークを学習すると、おそらく$f(k)cdot |I|O(1)$-timeアルゴリズムが存在しない。
  論文  参考訳（メタデータ） (2020-04-30T12:31:13Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。