論文の概要: On Sparse Graph Limits for Neural Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2611.01069v1
- Date: Sat, 31 Oct 2026 16:08:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-13 08:12:58.569988
- Title: On Sparse Graph Limits for Neural Combinatorial Optimization
- Title(参考訳): ニューラルコンビネーション最適化のためのスパースグラフ限界について
- Abstract要約: グラフニューラルネットワークは、しばしば小さなグラフでトレーニングされ、より大きなグラフにデプロイされる。
有限個のエネルギー特徴集合を用いた正規化グラフ最適化値のサイズ変換保証を確立する。
正確な解法と訓練されたモデルによる実験は、結果として生じる転送保証をテストする。
- 参考スコア(独自算出の注目度): 11.645059926678082
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph neural networks are often trained on small graphs and deployed on larger ones, raising the question of which graph information must be preserved for combinatorial optimization values to transfer across sizes. We establish size-transfer guarantees for normalized graph optimization values using finite collections of energy features. For affine objectives, including MAX-CUT, coloring defect, and independent-set density, differences in task value are controlled by discrepancies in normalized scalar energy probes on all bounded-degree graphs. For general Lipschitz objectives, such as those with balance penalties, an additional representation error appears; this error vanishes on hyperfinite graph families but can remain bounded away from zero on expanders. Thus, at fixed degree bound, state space, Lipschitz constant, and target accuracy, a finite energy representation independent of graph size suffices universally for affine tasks and asymptotically for general Lipschitz tasks on hyperfinite families. These results yield prediction guarantees under explicit conditions on encoder accuracy, readout stability, and representation coverage, together with statistical generalization bounds. Theoretically, we prove Shapley-Folkman bounds with sharp parameter dependence, including a dimension-free $\ell_2$ regime, and realize the resulting energy features with a fixed-weight message-passing network using random node initialization on bounded-treewidth graphs. Experiments with exact solvers and trained models test the resulting transfer guarantees.
- Abstract(参考訳): グラフニューラルネットワークは、しばしば小さなグラフでトレーニングされ、より大きなグラフにデプロイされる。
有限個のエネルギー特徴集合を用いた正規化グラフ最適化値のサイズ変換保証を確立する。
MAX-CUT、着色欠陥、独立セット密度などのアフィン目的に対しては、すべての有界グラフ上の正規化スカラーエネルギープローブにおいて、タスク値の違いは相違によって制御される。
一般のリプシッツの目的(例えば、バランスの取れたペナルティを持つもの)には、追加の表現誤差が現れる: この誤差は超有限グラフ族で消えるが、拡大子上でゼロから外れる。
したがって、有限次有界、状態空間、リプシッツ定数、および目標精度において、グラフサイズに依存しない有限エネルギー表現は、アフィンタスクに対して普遍的に十分であり、超有限族上の一般リプシッツタスクに対して漸近的に成り立つ。
これらの結果は、エンコーダの精度、読み出し安定性、表現カバレッジに関する明示的な条件の下で、統計的一般化境界とともに予測を保証する。
理論的には、Shapley-Folkman境界は、次元自由な$\ell_2$レジームを含む鋭いパラメータ依存を持つことを証明し、有界木幅グラフ上のランダムノード初期化を用いて固定重メッセージパスネットワークで得られたエネルギー特性を実現する。
正確な解法と訓練されたモデルによる実験は、結果として生じる転送保証をテストする。
関連論文リスト
- Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
最小内部積グリーディ選択規則に基づく,単純かつ効率的なカラム選択グラフサンプリングアルゴリズムを提案する。
ブロックモデルに基づいてアルゴリズムを解析し,次数分布がノード間で均衡している場合,クラスタサイズに対する比例サンプリングを実現する。
論文 参考訳(メタデータ) (2026-07-30T02:45:31Z) - Generative Diffusion Models of Stochastic Graph Signals [74.4097723209053]
本稿では,条件付きグラフ信号生成モデルの問題に取り組み,単一の拡散フレームワークを用いてそれらに取り組む。
グラフトポロジとノード機能側情報に基づいて直接条件付きグラフ信号を描画するグラフニューラルネットワーク(GNN)によりパラメータ化された逆拡散過程を学習する。
本稿では,株価予測と最適無線リソース割り当てという2つの生成課題について,両領域で広範囲に数値計算を行った。
論文 参考訳(メタデータ) (2026-07-07T22:02:13Z) - Scalable Graph Compressed Convolutions [68.85227170390864]
ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。
グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
論文 参考訳(メタデータ) (2024-07-26T03:14:13Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Limitless stability for Graph Convolutional Networks [8.1585306387285]
この研究は、グラフ畳み込みネットワークに対する厳密で斬新で広く適用可能な安定性保証と転送可能性境界を確立する。
グラフ畳み込みネットワークは、GSOがグラフラプラシアンであり、フィルタが無限大で正則である場合、グラフ粗粒化法の下で安定であることを示す。
論文 参考訳(メタデータ) (2023-01-26T22:17:00Z) - Residual Correlation in Graph Neural Network Regression [39.54530450932135]
我々は条件付き独立仮定が予測力を著しく制限していることを示します。
この問題を解釈可能かつ効率的なフレームワークで解決する。
我々のフレームワークは、競合するベースラインよりもかなり高い精度を実現している。
論文 参考訳(メタデータ) (2020-02-19T16:32:54Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。