論文の概要: Exploring Representation of Horn Clauses using GNNs

• arxiv url: http://arxiv.org/abs/2206.06986v1
• Date: Tue, 14 Jun 2022 17:02:17 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-15 14:17:58.193076
• Title: Exploring Representation of Horn Clauses using GNNs
• Title（参考訳）: GNNを用いたホーンクロース表現の探索
• Authors: Chencheng Liang, Philipp R\"ummer, Marc Brockschmidt
• Abstract要約: Constrained Horn Clauses (CHC) は、プログラム検証問題の標準的な表現である。 プログラムの特徴を学習するための新しいハイパーグラフニューラルネットワーク(R-HyGNN)アーキテクチャを提案する。 R-HyGNNは、検証問題を導くための複雑なプログラム機能をキャプチャできる。
• 参考スコア（独自算出の注目度）: 18.95744547473234
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning program semantics from raw source code is challenging due to the complexity of real-world programming language syntax and due to the difficulty of reconstructing long-distance relational information implicitly represented in programs using identifiers. Addressing the first point, we consider Constrained Horn Clauses (CHCs) as a standard representation of program verification problems, providing a simple and programming language-independent syntax. For the second challenge, we explore graph representations of CHCs, and propose a new Relational Hypergraph Neural Network (R-HyGNN) architecture to learn program features. We introduce two different graph representations of CHCs. One is called constraint graph (CG), and emphasizes syntactic information of CHCs by translating the symbols and their relations in CHCs as typed nodes and binary edges, respectively, and constructing the constraints as abstract syntax trees. The second one is called control- and data-flow hypergraph (CDHG), and emphasizes semantic information of CHCs by representing the control and data flow through ternary hyperedges. We then propose a new GNN architecture, R-HyGNN, extending Relational Graph Convolutional Networks, to handle hypergraphs. To evaluate the ability of R-HyGNN to extract semantic information from programs, we use R-HyGNNs to train models on the two graph representations, and on five proxy tasks with increasing difficulty, using benchmarks from CHC-COMP 2021 as training data. The most difficult proxy task requires the model to predict the occurrence of clauses in counter-examples, which subsumes satisfiability of CHCs. CDHG achieves 90.59% accuracy in this task. Furthermore, R-HyGNN has perfect predictions on one of the graphs consisting of more than 290 clauses. Overall, our experiments indicate that R-HyGNN can capture intricate program features for guiding verification problems.
• Abstract（参考訳）: ソースコードからプログラムの意味を学習することは、現実世界のプログラミング言語構文の複雑さと、識別子を使ってプログラムに暗黙的に表現された長距離関係情報の再構築が難しいため難しい。 まず,制約付きホーンクロース(CHC)をプログラム検証問題の標準的な表現とみなし,単純でプログラム言語に依存しない構文を提供する。 第2の課題として,CHCのグラフ表現について検討し,プログラムの特徴を学習するためのリレーショナルハイパーグラフニューラルネットワーク(R-HyGNN)アーキテクチャを提案する。 我々はCHCの2つの異なるグラフ表現を導入する。 1つは制約グラフ(CG)と呼ばれ、CHCの記号とそれらの関係をそれぞれ型付きノードとバイナリエッジとして翻訳し、抽象構文木として制約を構築することでCHCの構文情報を強調する。 2つ目は制御とデータフローハイパーグラフ(CDHG)と呼ばれ、3次ハイパーエッジを通しての制御とデータフローを表現することでCHCの意味情報を強調する。 次に、ハイパーグラフを扱うためにRelational Graph Convolutional Networksを拡張した新しいGNNアーキテクチャR-HyGNNを提案する。 プログラムから意味情報を抽出するR-HyGNNの能力を評価するために,R-HyGNNを用いて2つのグラフ表現と5つのプロキシタスクにおいて,CHC-COMP 2021のベンチマークをトレーニングデータとして用いた。 最も難しいプロキシタスクは、CHCの満足度を仮定した反例における節の発生を予測する必要がある。 CDHGは90.59%の精度を達成している。 さらに、R-HyGNNは290以上の節からなるグラフの1つについて完璧に予測できる。 実験の結果,R-HyGNNは複雑なプログラム特徴を捉え,検証問題を導くことができることがわかった。

関連論文リスト

• Efficient Graph Similarity Computation with Alignment Regularization [7.143879014059894]
  グラフ類似性計算(GSC)は、グラフニューラルネットワーク(GNN)を用いた学習に基づく予測タスクである。 適応正規化(AReg)と呼ばれる,シンプルながら強力な正規化技術によって,高品質な学習が達成可能であることを示す。 推論段階では、GNNエンコーダによって学習されたグラフレベル表現は、ARegを再度使用せずに直接類似度スコアを計算するために使用される。
  論文  参考訳（メタデータ） (2024-06-21T07:37:28Z)
• Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networks [0.10923877073891444]
  メッセージパッシングGNNの新たな代替手段として,Topology Coordinate Neural Network (TCNN) と Directional Virtual Coordinate Neural Network (DVCNN) を提案する。 TCNNとDVCNNは、メッセージパッシングGNNの競合や優れたパフォーマンスを達成する。 私たちの研究は、グラフベースの機械学習のためのテクニックのツールボックスを拡張します。
  論文  参考訳（メタデータ） (2023-12-03T10:14:10Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。 Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
  論文  参考訳（メタデータ） (2023-05-18T07:27:18Z)
• Heterogeneous Directed Hypergraph Neural Network over abstract syntax tree (AST) for Code Classification [9.01892294402701]
  我々は、ASTをヘテロジニアス指向ハイパーグラフ(HDHG)として表現し、コード分類のためのヘテロジニアス指向ハイパーグラフニューラルネットワーク(HDHGN)によるグラフ処理を提案する。 提案手法は, コード理解を改善し, 対の相互作用を超えた高次データ相関を表現できる。
  論文  参考訳（メタデータ） (2023-05-07T09:28:16Z)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。 これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。 4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
  論文  参考訳（メタデータ） (2022-05-31T10:38:04Z)
• Training Free Graph Neural Networks for Graph Matching [103.45755859119035]
  TFGMは、グラフニューラルネットワーク(GNN)ベースのグラフマッチングのパフォーマンスをトレーニングなしで向上するフレームワークである。 TFGMをさまざまなGNNに適用することは、ベースラインよりも有望な改善を示している。
  論文  参考訳（メタデータ） (2022-01-14T09:04:46Z)
• Hierarchical Message-Passing Graph Neural Networks [12.207978823927386]
  本稿では,新しい階層型メッセージパッシンググラフニューラルネットワークフレームワークを提案する。 鍵となるアイデアは、フラットグラフ内のすべてのノードをマルチレベルなスーパーグラフに再編成する階層構造を生成することである。 階層型コミュニティ対応グラフニューラルネットワーク(HC-GNN)と呼ばれる,このフレームワークを実装した最初のモデルを提案する。
  論文  参考訳（メタデータ） (2020-09-08T13:11:07Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Cross-GCN: Enhancing Graph Convolutional Network with $k$-Order Feature Interactions [153.6357310444093]
  Graph Convolutional Network(GCN)は,グラフデータの学習と推論を行う新興技術である。 我々は、GCNの既存の設計がクロスフィーチャをモデリングし、クロスフィーチャが重要であるタスクやデータに対してGCNの効率を損なうことを論じている。 我々は、任意の次交叉特徴を、特徴次元と順序サイズに線形に複雑にモデル化した、クロスフィーチャーグラフ畳み込みという新しい演算子を設計する。
  論文  参考訳（メタデータ） (2020-03-05T13:05:27Z)
• GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
  検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。 このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。 我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
  論文  参考訳（メタデータ） (2020-02-08T10:03:40Z)

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

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