論文の概要: Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations

• arxiv url: http://arxiv.org/abs/2210.16963v1
• Date: Sun, 30 Oct 2022 22:04:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-01 19:34:12.033715
• Title: Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations
• Title（参考訳）: 低次元表現を用いた最大クランク列挙問題の学習ヒューリスティックス
• Authors: Ali Baran Ta\c{s}demir, Tuna Karacan, Emir Kaan K{\i}rmac{\i} and Lale \"Ozkahya
• Abstract要約: 本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。 本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。 分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximate solutions to various NP-hard combinatorial optimization problems have been found by learned heuristics using complex learning models. In particular, vertex (node) classification in graphs has been a helpful method towards finding the decision boundary to distinguish vertices in an optimal set from the rest. By following this approach, we use a learning framework for a pruning process of the input graph towards reducing the runtime of the maximum clique enumeration problem. We extensively study the role of using different vertex representations on the performance of this heuristic method, using graph embedding algorithms, such as Node2vec and DeepWalk, and representations using higher-order graph features comprising local subgraph counts. Our results show that Node2Vec and DeepWalk are promising embedding methods in representing nodes towards classification purposes. We observe that using local graph features in the classification process produce more accurate results when combined with a feature elimination process. Finally, we provide tests on random graphs to show the robustness and scalability of our method.
• Abstract（参考訳）: np-ハードコンビネート最適化問題に対する近似解は、複素学習モデルを用いた学習ヒューリスティックスによって発見されている。 特に、グラフにおける頂点(ノード)分類は、他の部分から最適な集合における頂点を識別するための決定境界を見つけるための有用な方法である。 このアプローチに従えば,入力グラフのプルーニングプロセスのための学習フレームワークを用いて,最大クランク列挙問題のランタイムを削減できる。 node2vecやdeepwalkといったグラフ埋め込みアルゴリズムや,局所サブグラフ数を含む高次グラフ特徴を用いた表現を用いて,このヒューリスティック手法の性能に異なる頂点表現を用いる役割を広く研究した。 この結果から,Node2VecとDeepWalkは,ノードを分類目的に表現するための埋め込み手法を約束していることがわかった。 分類プロセスにおける局所グラフ機能の使用は,特徴除去プロセスと組み合わせると,より正確な結果が得られることを観察する。 最後に,提案手法の堅牢性と拡張性を示すために,ランダムグラフの試験を行う。

関連論文リスト

• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。 まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。 補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
  論文  参考訳（メタデータ） (2024-04-24T18:39:18Z)
• Differentiable Mathematical Programming for Object-Centric Representation Learning [32.76702197616919]
  本稿では,線形プログラムとして表現される分割法として最小$s$-$t$グラフカットを提案する。 このグラフを解くために、我々の解は効率的でスケーラブルで微分可能な二次プログラミング近似に依存する。 以上の結果から,我々の手法はスケーラブルであり,テクスチャ化されたシーンやオブジェクトを用いたオブジェクト発見タスクにおいて,既存の手法よりも優れていたことが示唆された。
  論文  参考訳（メタデータ） (2022-10-05T11:36:45Z)
• Deep Manifold Learning with Graph Mining [80.84145791017968]
  グラフマイニングのための非段階的決定層を持つ新しいグラフ深層モデルを提案する。 提案モデルでは,現行モデルと比較して最先端性能を実現している。
  論文  参考訳（メタデータ） (2022-07-18T04:34:08Z)
• Effective and efficient structure learning with pruning and model averaging strategies [9.023722579074734]
  本稿では,2つの新しい手法と丘登り探索を組み合わせたBN構造学習アルゴリズムについて述べる。 アルゴリズムは探索空間グラフをプルーニングすることから始まり、プルーニング戦略をプルーニング戦略のアグレッシブバージョンと見なすことができる。 そして、ヒルクライミング探索プロセスで平均化を行い、目的関数を最大化する近隣グラフに移動する。
  論文  参考訳（メタデータ） (2021-12-01T10:35:34Z)
• Graphon based Clustering and Testing of Networks: Algorithms and Theory [11.3700474413248]
  ネットワークに価値のあるデータは、幅広いアプリケーションで遭遇し、学習の課題を提起する。 本稿では,2つのクラスタリングアルゴリズムについて述べる。 さらに、グラフ2サンプルテスト問題に対する提案した距離の適用性について検討する。
  論文  参考訳（メタデータ） (2021-10-06T13:14:44Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Graph embedding using multi-layer adjacent point merging model [23.706877029336415]
  本稿では, 隣接した多層マージ点モデルを用いたグラフ埋め込み手法を提案する。 この埋め込み手法により、列車データから異なるサブグラフパターンを抽出できる。 数値解析により,提案手法が多くの最先端手法より優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-28T05:35:04Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

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

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