Fugu-MT 論文翻訳(概要): Unsupervised Ordering for Maximum Clique

論文の概要: Unsupervised Ordering for Maximum Clique

arxiv url: http://arxiv.org/abs/2503.21814v1
Date: Tue, 25 Mar 2025 18:28:49 GMT
ステータス: 翻訳完了
システム内更新日: 2025-03-31 18:44:02.575787
Title: Unsupervised Ordering for Maximum Clique
Title（参考訳）: 最大傾きの教師なし順序付け
Authors: Yimeng Min, Carla P. Gomes,
Abstract要約: 我々は制約を、頂点の順序がclique構造と整列するように幾何学的関係に変換する。この斜め方向の順序付けを分岐・分岐探索に統合することにより,探索効率を向上し,計算ステップの数を削減できる。
参考スコア（独自算出の注目度）: 30.652280460904375
License:
Abstract: We propose an unsupervised approach for learning vertex orderings for the maximum clique problem by framing it within a permutation-based framework. We transform the combinatorial constraints into geometric relationships such that the ordering of vertices aligns with the clique structures. By integrating this clique-oriented ordering into branch-and-bound search, we improve search efficiency and reduce the number of computational steps. Our results demonstrate how unsupervised learning of vertex ordering can enhance search efficiency across diverse graph instances. We further study the generalization across different sizes.
Abstract（参考訳）: 本稿では,最大傾き問題に対する頂点順序の学習を,置換に基づくフレームワーク内でフレーミングすることで,教師なしのアプローチを提案する。我々は組合せ的制約を、頂点の順序がclique構造と整列するように幾何学的関係に変換する。この斜め方向の順序付けを分岐・分岐探索に統合することにより、探索効率を改善し、計算ステップの数を削減できる。本研究は,頂点順序の教師なし学習が,多種多様なグラフインスタンス間の探索効率をいかに向上させるかを示す。さらに、異なるサイズにわたる一般化について研究する。

関連論文リスト

A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem [18.720357905876604]
未分岐グラフの$k$-defective cliqueは、$G$は、最大で$k$の欠損エッジを持つほぼ完全なグラフを誘導する。与えられたグラフから最大の$k$$-defective Cliqueを求める最大$k$-defective Clique問題は、社会的および生物学的ネットワーク分析のような多くのアプリケーションにおいて重要である。
論文参考訳（メタデータ） (2024-07-23T15:40:35Z)
Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
論文参考訳（メタデータ） (2024-04-24T18:39:18Z)
Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文参考訳（メタデータ） (2023-07-25T12:33:53Z)
Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations [0.0]
本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
論文参考訳（メタデータ） (2022-10-30T22:04:32Z)
Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
論文参考訳（メタデータ） (2022-09-27T17:51:31Z)
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文参考訳（メタデータ） (2022-03-28T21:34:16Z)
Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文参考訳（メタデータ） (2022-01-25T00:10:03Z)
Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
論文参考訳（メタデータ） (2021-06-08T00:57:59Z)
Computing Cliques and Cavities in Networks [19.17379757727846]
我々は、所定のネットワークの計算可能性を決定するためにkコア分解を用いる。計算可能なネットワークに対して,異なる順序のcliqueを見つけるための実装可能なアルゴリズムを用いた探索手法を設計する。このアルゴリズムをC. elegansの神経ネットワークに適用する。
論文参考訳（メタデータ） (2021-01-03T01:09:43Z)
Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文参考訳（メタデータ） (2020-01-18T09:14:16Z)

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