論文の概要: Neural Graduated Assignment for Maximum Common Edge Subgraphs

• arxiv url: http://arxiv.org/abs/2505.12325v1
• Date: Sun, 18 May 2025 09:43:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 14:57:11.165152
• Title: Neural Graduated Assignment for Maximum Common Edge Subgraphs
• Title（参考訳）: 最大コモンエッジ部分グラフのためのニューラルネットワークの逐次アサインメント
• Authors: Chaolong Ying, Yingqi Ruan, Xuemin Chen, Yaomin Wang, Tianshu Yu,
• Abstract要約: 本稿では,シンプルでスケーラブルで教師なし学習に基づくNGA(Neural Graduated Assignment)を提案する。 NGAは大規模インスタンスの計算時間とスケーラビリティを大幅に改善することを示す。 NGAの導入は、MCESの計算の大幅な進歩を示し、他の代入問題に対する洞察を提供する。
• 参考スコア（独自算出の注目度）: 11.555673504442755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Maximum Common Edge Subgraph (MCES) problem is a crucial challenge with significant implications in domains such as biology and chemistry. Traditional approaches, which include transformations into max-clique and search-based algorithms, suffer from scalability issues when dealing with larger instances. This paper introduces ``Neural Graduated Assignment'' (NGA), a simple, scalable, unsupervised-training-based method that addresses these limitations by drawing inspiration from the classical Graduated Assignment (GA) technique. Central to NGA is stacking of neural components that closely resemble the GA process, but with the reparameterization of learnable temperature into higher dimension. We further theoretically analyze the learning dynamics of NGA, showing its design leads to fast convergence, better exploration-exploitation tradeoff, and ability to escape local optima. Extensive experiments across MCES computation, graph similarity estimation, and graph retrieval tasks reveal that NGA not only significantly improves computation time and scalability on large instances but also enhances performance compared to existing methodologies. The introduction of NGA marks a significant advancement in the computation of MCES and offers insights into other assignment problems.
• Abstract（参考訳）: 最大共通エッジグラフ(MCES)問題は、生物学や化学などの領域において重要な意味を持つ重要な課題である。 最大斜めおよびサーチベースアルゴリズムへの変換を含む従来のアプローチは、より大きなインスタンスを扱う場合のスケーラビリティの問題に悩まされている。 本稿では,古典的学習課題(GA)技術からインスピレーションを得て,これらの制約に対処する,シンプルでスケーラブルで教師なし学習に基づく手法である「ニューラル・グラデッド・アサインメント(NGA)」を紹介する。 NGAの中心は、GAプロセスとよく似ているが、学習可能な温度をより高次元に再パラメータ化することで、ニューラルネットワークコンポーネントを積み重ねている。 さらに,NGAの学習力学を理論的に解析し,その設計が高速収束,探索・探索のトレードオフの改善,局所最適解を逃れる能力を示す。 MCES計算、グラフ類似度推定、グラフ検索タスクにわたる大規模な実験により、NGAは大規模インスタンスでの計算時間とスケーラビリティを著しく改善するだけでなく、既存の手法と比較してパフォーマンスも向上することが明らかとなった。 NGAの導入は、MCESの計算の大幅な進歩を示し、他の代入問題に対する洞察を提供する。

関連論文リスト

• Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model [0.0]
  グラフニューラルネットワーク(GNN)は、グラフに関連するデータを処理するように設計されている。 GNNは、繰り返し集約ステップによって遠く離れたノードから情報を集めるのに苦労する可能性がある。 我々は,GCNのアーキテクチャが過度なスムーシングを避けるために,深さとともにスケールしなければならないことを示す。
  論文  参考訳（メタデータ） (2025-03-03T09:55:10Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• $ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning [6.612096312467342]
  Directed A Graphs (DAGs) の構造を学ぶことは、ノード数に応じてスケールする可能なグラフの巨大な検索空間のため、大きな課題となる。 近年の進歩は、微分可能指数関数性制約を取り入れた連続最適化タスクとしてこの問題を再定義している。 本稿では,SGD(Gradient Descent)に基づく最適化手法と統合した近似手法を用いて,DAGを学習する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-31T12:13:11Z)
• FIT-GNN: Faster Inference Time for GNNs Using Coarsening [1.323700980948722]
  粗大化に基づく手法は、グラフをより小さなグラフに減らし、より高速な計算をもたらす。 従来の研究は、推論フェーズにおける計算コストに十分な対処を行っていなかった。 本稿では,GNNの学習と推論の両段階における計算負担を軽減することにより,GNNのスケーラビリティを向上させる新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-10-19T06:27:24Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• Quantum Maximum Entropy Inference and Hamiltonian Learning [4.9614587340495]
  この研究は、最大エントロピー推論とグラフィカルモデルの学習のためのアルゴリズムを量子領域に拡張する。 量子反復スケーリング(QIS)として知られる一般化は単純であるが、重要な課題は量子問題インスタンスの非可換性にある。 準ニュートン法によるQISとGDの性能向上について検討する。
  論文  参考訳（メタデータ） (2024-07-16T08:11:34Z)
• On the Generalization Capability of Temporal Graph Learning Algorithms: Theoretical Insights and a Simpler Method [59.52204415829695]
  テンポラルグラフ学習(TGL)は、様々な現実世界のアプリケーションにまたがる一般的なテクニックとなっている。 本稿では,異なるTGLアルゴリズムの一般化能力について検討する。 一般化誤差が小さく、全体的な性能が向上し、モデルの複雑さが低下する単純化されたTGLネットワークを提案する。
  論文  参考訳（メタデータ） (2024-02-26T08:22:22Z)
• Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation [80.227864832092]
  グラフニューラルネットワーク(GNN)は、様々なアプリケーションで例外的な効果を発揮している。 大規模グラフの重大化は,GNNによるリアルタイム推論において重要な課題となる。 本稿では,オンライン伝搬フレームワークと2つの新しいノード適応伝搬手法を提案する。
  論文  参考訳（メタデータ） (2023-10-17T05:03:00Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である 本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。 提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
  論文  参考訳（メタデータ） (2022-10-14T03:43:05Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• Tackling Oversmoothing of GNNs with Contrastive Learning [35.88575306925201]
  グラフニューラルネットワーク(GNN)は、グラフデータと表現学習能力の包括的な関係を統合する。 オーバースムーシングはノードの最終的な表現を識別不能にし、ノード分類とリンク予測性能を劣化させる。 本稿では,TGCL(Topology-Guided Graph Contrastive Layer)を提案する。
  論文  参考訳（メタデータ） (2021-10-26T15:56:16Z)
• Towards an Efficient and General Framework of Robust Training for Graph Neural Networks [96.93500886136532]
  グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。 GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。 我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-25T15:17:58Z)

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

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