論文の概要: ReLU Networks for Exact Generation of Similar Graphs

• arxiv url: http://arxiv.org/abs/2604.05929v1
• Date: Tue, 07 Apr 2026 14:31:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-08 17:42:09.878382
• Title: ReLU Networks for Exact Generation of Similar Graphs
• Title（参考訳）: 類似グラフ作成のためのReLUネットワーク
• Authors: Mamoona Ghafoor, Tatsuya Akutsu,
• Abstract要約: 我々は、与えられた入力グラフから n 個の頂点を持つ編集距離 d 内のグラフを決定的に生成する定数深さと O(n2 d) サイズ ReLU ネットワークの存在を示す。 結果は、有効性を保証するコンパクトな生成モデルを構築するための理論的基盤を提供する。
• 参考スコア（独自算出の注目度）: 3.746431245783676
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Generation of graphs constrained by a specified graph edit distance from a source graph is important in applications such as cheminformatics, network anomaly synthesis, and structured data augmentation. Despite the growing demand for such constrained generative models in areas including molecule design and network perturbation analysis, the neural architectures required to provably generate graphs within a bounded graph edit distance remain largely unexplored. In addition, existing graph generative models are predominantly data-driven and depend heavily on the availability and quality of training data, which may result in generated graphs that do not satisfy the desired edit distance constraints. In this paper, we address these challenges by theoretically characterizing ReLU neural networks capable of generating graphs within a prescribed graph edit distance from a given graph. In particular, we show the existence of constant depth and O(n^2 d) size ReLU networks that deterministically generate graphs within edit distance d from a given input graph with n vertices, eliminating reliance on training data while guaranteeing validity of the generated graphs. Experimental evaluations demonstrate that the proposed network successfully generates valid graphs for instances with up to 1400 vertices and edit distance bounds up to 140, whereas baseline generative models fail to generate graphs with the desired edit distance. These results provide a theoretical foundation for constructing compact generative models with guaranteed validity.
• Abstract（参考訳）: 特定のグラフ編集距離で制約されたグラフの生成は、ケミノフォマティクス、ネットワーク異常合成、構造化データ拡張などの応用において重要である。 分子設計やネットワーク摂動解析などの領域におけるそのような制約付き生成モデルに対する需要が高まっているにもかかわらず、有界グラフ編集距離内でグラフを確実に生成するために必要なニューラルネットワークは、ほとんど探索されていないままである。 さらに、既存のグラフ生成モデルは、主にデータ駆動であり、トレーニングデータの可用性と品質に大きく依存する。 本稿では,与えられたグラフから所定のグラフ編集距離内でグラフを生成することができるReLUニューラルネットワークを理論的に特徴付けることにより,これらの課題に対処する。 特に,n頂点の入力グラフから編集距離d内のグラフを決定的に生成する定数深さとO(n^2 d)サイズReLUネットワークの存在を示し,生成したグラフの妥当性を保証しながら,トレーニングデータへの依存を排除した。 実験により,提案ネットワークは最大1400の頂点を持つインスタンスに対して有効なグラフを生成し,編集距離を最大140まで制限する一方,ベースライン生成モデルは所望の編集距離でグラフを生成することができないことがわかった。 これらの結果は、有効性を保証するコンパクトな生成モデルを構築するための理論的基盤を提供する。

関連論文リスト

• Generating Large Semi-Synthetic Graphs of Any Size [0.4419843514606336]
  グラフ生成はネットワーク科学において重要な領域である。 近年のディープラーニングの進歩により、データ駆動型手法によるグラフの学習と生成が可能になった。 本稿では,遅延グラフサンプリング生成(LGSG)を提案する。
  論文  参考訳（メタデータ） (2025-07-02T21:46:28Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  グラフレベルグラフニューラルネットワーク(GNN)のための統一評価フレームワークを提案する。 このフレームワークは、さまざまなデータセットにわたるGNNを評価するための標準化された設定を提供する。 また,表現性の向上と一般化機能を備えた新しいGNNモデルを提案する。
  論文  参考訳（メタデータ） (2025-01-01T08:48:53Z)
• Self-Supervised Graph Neural Networks for Enhanced Feature Extraction in Heterogeneous Information Networks [16.12856816023414]
  本稿では,インターネットの急速な発展に伴う複雑なグラフデータ処理におけるグラフニューラルネットワーク(GNN)の適用と課題について考察する。 自己監督機構を導入することにより、グラフデータの多様性と複雑さに対する既存モデルの適合性を向上させることが期待されている。
  論文  参考訳（メタデータ） (2024-10-23T07:14:37Z)
• Data Augmentation in Graph Neural Networks: The Role of Generated Synthetic Graphs [0.24999074238880487]
  本研究では,データ拡張のための生成グラフについて検討する。 生成したグラフを実グラフと組み合わせることのパフォーマンスを比較し、生成したグラフの量が異なることがグラフ分類タスクに与える影響を調べる。 その結果,グラフデータの拡張,一貫性のあるラベルの確保,分類性能の向上など,新たなアプローチが導入された。
  論文  参考訳（メタデータ） (2024-07-20T06:05:26Z)
• GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks [72.01829954658889]
  本稿では,この新たな問題設定の数学的定義を紹介する。 一つのグラフ共有構造学習者と複数のグラフ固有GNNを協調する一般的なフレームワークを考案する。 十分に訓練された構造学習者は、微調整なしで、目に見えない対象グラフの適応的な構造を直接生成することができる。
  論文  参考訳（メタデータ） (2023-06-20T03:33:22Z)
• Graph Generation with Diffusion Mixture [57.78958552860948]
  グラフの生成は、非ユークリッド構造の複雑な性質を理解する必要がある実世界のタスクにとって大きな課題である。 本稿では,拡散過程の最終グラフ構造を明示的に学習することにより,グラフのトポロジーをモデル化する生成フレームワークを提案する。
  論文  参考訳（メタデータ） (2023-02-07T17:07:46Z)
• SCGG: A Deep Structure-Conditioned Graph Generative Model [9.046174529859524]
  SCGGと呼ばれる条件付きディープグラフ生成法は、特定のタイプの構造条件を考える。 SCGGのアーキテクチャは、グラフ表現学習ネットワークと、エンドツーエンドで訓練された自己回帰生成モデルで構成されている。 合成と実世界の両方のデータセットに対する実験結果は,最先端のベースラインと比較して,本手法の優位性を示している。
  論文  参考訳（メタデータ） (2022-09-20T12:33:50Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  本稿では,元のグラフを表す小さなグラフの作成に焦点をあてる。 我々は、元のグラフを受容体の分布とみなし、受容体が同様の分布を持つ小さなグラフを合成することを目的としている。
  論文  参考訳（メタデータ） (2022-06-28T02:10:05Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。 固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。 GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
  論文  参考訳（メタデータ） (2022-05-19T14:08:15Z)

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

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