論文の概要: Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices

• arxiv url: http://arxiv.org/abs/2509.21000v1
• Date: Thu, 25 Sep 2025 10:50:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-26 20:58:12.851634
• Title: Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices
• Title（参考訳）: ILP用GNNの特徴増強:局所的特異性
• Authors: Qingyu Han, Qian Li, Linxin Yang, Qian Chen, Qingjiang Shi, Ruoyu Sun,
• Abstract要約: そこで我々は,各ノードのd-hop近傍で識別子が一意であることを保証する,d-hopユニークな色付けに基づく類似のローカルUIDスキームを提案する。 我々は、D層ネットワークにおいて、ローカルUIDはより強力な一般化を提供しながら、グローバルUIDの表現力を達成することを証明した。
• 参考スコア（独自算出の注目度）: 30.141553854433138
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Integer Linear Programs (ILPs) are central to real-world optimizations but notoriously difficult to solve. Learning to Optimize (L2O) has emerged as a promising paradigm, with Graph Neural Networks (GNNs) serving as the standard backbone. However, standard anonymous GNNs are limited in expressiveness for ILPs, and the common enhancement of augmenting nodes with globally unique identifiers (UIDs) typically introduces spurious correlations that severely harm generalization. To address this tradeoff, we propose a parsimonious Local-UID scheme based on d-hop uniqueness coloring, which ensures identifiers are unique only within each node's d-hop neighborhood. Building on this scheme, we introduce ColorGNN, which incorporates color information via color-conditioned embeddings, and ColorUID, a lightweight feature-level variant. We prove that for d-layer networks, Local-UIDs achieve the expressive power of Global-UIDs while offering stronger generalization. Extensive experiments show that our approach (i) yields substantial gains on three ILP benchmarks, (ii) exhibits strong OOD generalization on linear programming datasets, and (iii) further improves a general graph-level task when paired with a state-of-the-art method.
• Abstract（参考訳）: Integer Linear Programs (ILP) は現実世界の最適化の中心であるが、解決が難しいことで知られている。 Learning to Optimize (L2O)は有望なパラダイムとして登場し、グラフニューラルネットワーク(GNN)が標準バックボーンとして機能している。 しかし、標準匿名GNNはIPPの表現性に制限があり、グローバルなユニークな識別子(UID)を持つ拡張ノードの共通的な拡張は、一般的に一般化を著しく損なう突発的な相関をもたらす。 このトレードオフに対処するため,各ノードのd-hop近傍でのみ識別子が一意であることを保証する,d-hop一意性着色に基づく類似のローカルUIDスキームを提案する。 このスキームに基づいて,カラーコンディショニングによるカラー情報を含むColorGNNと,軽量な機能レベル変種であるColorUIDを紹介する。 我々は、D層ネットワークにおいて、ローカルUIDはより強力な一般化を提供しながら、グローバルUIDの表現力を達成することを証明した。 広範囲にわたる実験から、我々のアプローチが明らかになる i)3つのILPベンチマークでかなりの利得を得る。 (II)線形プログラミングデータセットに強いOOD一般化を示し、 (iii) 最先端手法と組み合わせた場合の一般的なグラフレベルのタスクをさらに改善する。

関連論文リスト

• Graph Neural Networks Powered by Encoder Embedding for Improved Node Learning [17.31465642587528]
  グラフニューラルネットワーク(GNN)は、幅広いノードレベルのグラフ学習タスクのための強力なフレームワークとして登場した。 本稿では,1ホットグラフエンコーダ埋め込み (GEE) という統計的手法を用いて,高品質な初期ノード特徴を生成する。 本研究では,教師なし環境と教師なし環境の両方にまたがる広範囲なシミュレーションと実世界の実験を通して,その効果を実証する。
  論文  参考訳（メタデータ） (2025-07-15T21:01:54Z)
• ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
  スケーラブルで効果的なグラフ学習のためのマルチホップノード機能を適応的に融合する新しいフレームワークであるScaleGNNを提案する。 予測精度と計算効率の両面で,ScaleGNNは最先端のGNNよりも一貫して優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-22T14:05:11Z)
• TreeX: Generating Global Graphical GNN Explanations via Critical Subtree Extraction [38.99239532650183]
  メッセージパッシングの内部動作によって生じる重要なサブツリーを分析し,抽出することにより,GNNのアンボックス化を提案する。 埋め込み空間のサブツリーを効率的なアルゴリズムで集約することにより、ローカル、クラス、グローバルレベルでメッセージパッシングGNNの直感的なグラフィカルな説明を行うことができる。
  論文  参考訳（メタデータ） (2025-03-12T04:36:28Z)
• Graph as a feature: improving node classification with non-neural graph-aware logistic regression [2.952177779219163]
  Graph-aware Logistic Regression (GLR) はノード分類タスク用に設計された非神経モデルである。 GNNにアクセスできる情報のごく一部しか使わない従来のグラフアルゴリズムとは異なり、提案モデルではノードの特徴とエンティティ間の関係を同時に活用する。
  論文  参考訳（メタデータ） (2024-11-19T08:32:14Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• Local Augmentation for Graph Neural Networks [78.48812244668017]
  本稿では,局所的な部分グラフ構造によりノード特性を向上する局所拡張を提案する。 局所的な拡張に基づいて、プラグイン・アンド・プレイ方式で任意のGNNモデルに適用可能な、LA-GNNという新しいフレームワークをさらに設計する。
  論文  参考訳（メタデータ） (2021-09-08T18:10:08Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Policy-GNN: Aggregation Optimization for Graph Neural Networks [60.50932472042379]
  グラフニューラルネットワーク(GNN)は、局所的なグラフ構造をモデル化し、隣人からの情報を集約することで階層的なパターンを捉えることを目的としている。 複雑なグラフとスパースな特徴を与えられた各ノードに対して効果的なアグリゲーション戦略を開発することは難しい課題である。 本稿では,GNNのサンプリング手順とメッセージパッシングを複合学習プロセスにモデル化するメタ政治フレームワークであるPolicy-GNNを提案する。
  論文  参考訳（メタデータ） (2020-06-26T17:03:06Z)

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

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