論文の概要: Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges

• arxiv url: http://arxiv.org/abs/2502.13000v1
• Date: Tue, 18 Feb 2025 16:20:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-19 14:05:20.865084
• Title: Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
• Title（参考訳）: ハイパーグラフにおけるエッジカラークラスタリング - 不満なエッジの最小化を超えて
• Authors: Alex Crane, Thomas Stanley, Blair D. Sullivan, Nate Veldt,
• Abstract要約: 我々は、エッジカラーのハイパーグラフをクラスタリングするためのフレームワークを検討し、そこでは、彼らが参加する主要なマルチウェイインタラクションのタイプに基づいてオブジェクトをクラスタリングすることを目的としている。 よく研究されている1つの目的は、満足できないハイパーエッジの数を最小限に抑えるためにノードを色付けすることである。 最適性は同じだが、近似するよりもはるかに難しい、満足度の高いエッジを最大化する新しいアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 8.499685241219366
• License:
• Abstract: We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster (equivalently, to color) objects based on the primary type of multiway interactions they participate in. One well-studied objective is to color nodes to minimize the number of unsatisfied hyperedges -- those containing one or more nodes whose color does not match the hyperedge color. We motivate and present advances for several directions that extend beyond this minimization problem. We first provide new algorithms for maximizing satisfied edges, which is the same at optimality but is much more challenging to approximate, with all prior work restricted to graphs. We develop the first approximation algorithm for hypergraphs, and then refine it to improve the best-known approximation factor for graphs. We then introduce new objective functions that incorporate notions of balance and fairness, and provide new hardness results, approximations, and fixed-parameter tractability results.
• Abstract（参考訳）: 我々は、エッジカラーのハイパーグラフをクラスタリングするためのフレームワークを検討し、そこでは、彼らが参加する主要なマルチウェイ相互作用のタイプに基づいて、オブジェクトをクラスタリングすること(ほぼ)が目的である。 よく研究されている1つの目的は、満足できないハイパーエッジの数を最小限にするためにノードを色付けすることである。 我々は、この最小化問題を超えて、いくつかの方向の進歩を動機付け、提示する。 まず、最適性は同じだが、グラフに制限された先行処理により近似がはるかに困難である、満足度のあるエッジを最大化するための新しいアルゴリズムを提案する。 ハイパーグラフの最初の近似アルゴリズムを開発し、それを改良し、グラフの最もよく知られた近似係数を改善する。 次に、バランスと公正の概念を取り入れた新たな客観的関数を導入し、新しい硬度結果、近似、固定パラメータのトラクタビリティー結果を提供する。

関連論文リスト

• Combining Optimal Transport and Embedding-Based Approaches for More Expressiveness in Unsupervised Graph Alignment [19.145556156889064]
  教師なしグラフアライメントは、グラフ構造とノード特徴のみを利用して、属性グラフのペア間の1対1ノード対応を見つける。 モデル表現性の理論的解析によって動機付けられたそれらの利点を組み合わせるための原理的アプローチを提案する。 我々は,問題を最大重み付けに還元することで,一対一のマッチング制約を最初に保証する。
  論文  参考訳（メタデータ） (2024-06-19T04:57:35Z)
• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。 まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。 補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
  論文  参考訳（メタデータ） (2024-04-24T18:39:18Z)
• Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling [6.599344783327054]
  グラフクラスタリングは、グラフの他の部分と疎結合なノードの集合を検出することを目的としている、ネットワーク分析における基本的なタスクである。 NPハードなパラメータ化クラスタリングフレームワークLambdaCCに対して,高速な近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-08T02:29:37Z)
• Refined Edge Usage of Graph Neural Networks for Edge Prediction [51.06557652109059]
  We propose a novel edge prediction paradigm named Edge-aware Message PassIng neuRal nEtworks (EMPIRE)。 まず,各エッジをトポロジや監督のためにのみ使用するエッジ分割手法を提案する。 監視エッジで接続されたペアと接続されていないペアの差を強調するために、さらにメッセージを重み付けして、その差を反映できる相対的なペアを強調します。
  論文  参考訳（メタデータ） (2022-12-25T23:19:56Z)
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race [4.416484585765029]
  Weisfeiler-Lemanアルゴリズムは、グラフ学習には基本的であり、グラフカーネルやグラフニューラルネットワークの成功には中心となる。 本研究では, 着色速度を緩やかに収束させることができる, 漸進的な地区改良のための枠組みを提案する。 提案手法は,既存のグラフカーネルの新しい変種を導出し,最適割り当てによるグラフ編集距離を近似するために用いられる。
  論文  参考訳（メタデータ） (2022-09-19T14:37:35Z)
• Learning Based Proximity Matrix Factorization for Node Embedding [33.18041180501025]
  ノード埋め込みの最近の進歩は、近接行列因数分解法は、数百万のノードを持つ大規模グラフに対して、非常に高い性能とスケールが得られることを示している。 トレーニング可能な近接測度を持つフレームワークである Em Lemane を提案する。 提案手法は,ほぼすべてのデータセットにおいて,リンク予測とノード分類タスクの両方において,既存のソリューションよりも優れている。
  論文  参考訳（メタデータ） (2021-06-10T03:29:15Z)
• Learning to Estimate Hidden Motions with Global Motion Aggregation [71.12650817490318]
  閉塞は、局所的な証拠に依存する光学フローアルゴリズムに重大な課題をもたらす。 最初の画像でピクセル間の長距離依存性を見つけるために,グローバルモーションアグリゲーションモジュールを導入する。 遮蔽領域における光流量推定が非遮蔽領域における性能を損なうことなく大幅に改善できることを実証した。
  論文  参考訳（メタデータ） (2021-04-06T10:32:03Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。 与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。 実験の結果,本手法は著しい改善をもたらすことがわかった。
  論文  参考訳（メタデータ） (2021-03-30T17:36:40Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)
• Interpretable Deep Graph Generation with Node-Edge Co-Disentanglement [55.2456981313287]
  本稿では,属性グラフの深部生成モデルのための新しいアンタングルメント拡張フレームワークを提案する。 ノードとエッジのデコンボリューションのための新しいアーキテクチャを用いて、上記の3種類の潜伏因子を解離する新しい変分的目的を提案する。 各タイプ内では、画像の既存のフレームワークの一般化が示され、個々の因子のゆがみがさらに強化される。
  論文  参考訳（メタデータ） (2020-06-09T16:33:49Z)

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

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