論文の概要: Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering

• arxiv url: http://arxiv.org/abs/2006.08569v2
• Date: Fri, 23 Oct 2020 20:28:38 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-21 05:10:31.417700
• Title: Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering
• Title（参考訳）: 半教師付き学習と局所グラフクラスタリングのための強局所pノルムカットアルゴリズム
• Authors: Meng Liu and David F. Gleich
• Abstract要約: グラフベースの半教師付き学習は、しばしばシードと呼ばれるいくつかのサンプルノードが与えられたグラフノードのラベル付け関数を学習する問題である。 これは、特定のシードの周りにあるクラスタやノードのコミュニティを見つけるという、局所的なグラフクラスタリングやコミュニティ検出の問題と密接に関係している。 本稿では, ランダムウォーキング, 拡散, あるいはスムーズな関数法を凸p-ノルム切断関数に一般化する手法を提案する。
• 参考スコア（独自算出の注目度）: 17.30575432375032
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph based semi-supervised learning is the problem of learning a labeling function for the graph nodes given a few example nodes, often called seeds, usually under the assumption that the graph's edges indicate similarity of labels. This is closely related to the local graph clustering or community detection problem of finding a cluster or community of nodes around a given seed. For this problem, we propose a novel generalization of random walk, diffusion, or smooth function methods in the literature to a convex p-norm cut function. The need for our p-norm methods is that, in our study of existing methods, we find those principled methods based on eigenvector, spectral, random walk, or linear system often have difficulty capturing the correct boundary of a target label or target cluster. In contrast, 1-norm or maxflow-mincut based methods capture the boundary, but cannot grow from small seed set; hybrid procedures that use both have many hard to set parameters. In this paper, we propose a generalization of the objective function behind these methods involving p-norms. To solve the p-norm cut problem we give a strongly local algorithm -- one whose runtime depends on the size of the output rather than the size of the graph. Our method can be thought as a nonlinear generalization of the Anderson-Chung-Lang push procedure to approximate a personalized PageRank vector efficiently. Our procedure is general and can solve other types of nonlinear objective functions, such as p-norm variants of Huber losses. We provide a theoretical analysis of finding planted target clusters with our method and show that the p-norm cut functions improve on the standard Cheeger inequalities for random walk and spectral methods. Finally, we demonstrate the speed and accuracy of our new method in synthetic and real world datasets. Our code is available at http://github.com/MengLiuPurdue/SLQ.
• Abstract（参考訳）: グラフに基づく半教師付き学習は、グラフのエッジがラベルの類似性を示すという仮定の下で、しばしば種と呼ばれるいくつかの例ノードが与えられたグラフノードのラベル付け関数を学習する問題である。 これは、特定の種周辺のクラスタまたはノードのコミュニティを見つけるローカルグラフクラスタリングまたはコミュニティ検出問題と密接に関連している。 そこで本研究では, ランダムウォーキング, 拡散, あるいはスムーズな関数法を凸p-ノルム切断関数に一般化する手法を提案する。 p-ノルム法の必要性は、既存の手法の研究において、固有ベクトル、スペクトル、ランダムウォーク、あるいは線形系に基づく原理的手法が、しばしばターゲットラベルやターゲットクラスタの正確な境界を捉えるのに困難であることである。 対照的に、1-norm または maxflow-mincut ベースの手法は境界を捉えているが、小さなシードセットから成長することはできない。 本稿では, p-ノルムを含むこれらの手法の背後にある目的関数の一般化を提案する。 p-ノルムカット問題を解決するために、強く局所的なアルゴリズムを与える -- 実行時にグラフのサイズよりも出力のサイズに依存するアルゴリズム。 提案手法は, パーソナライズされたPageRankベクトルを効率的に近似するために, Anderson-Chung-Langプッシュ手順の非線形一般化と考えることができる。 本手法は汎用的であり,フーバー損失のp-ノルム変種など他の非線形目的関数を解くことができる。 本手法を用いて植込み対象クラスタを探索する理論的解析を行い,ランダムウォークとスペクトル法の標準的なチーガー不等式によりpノルム切断関数が改善することを示す。 最後に,合成および実世界のデータセットにおける新しい手法の速度と精度を示す。 私たちのコードはhttp://github.com/mengliupurdue/slqで利用可能です。

関連論文リスト

• MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity and Degree Descent Criterion [0.6906005491572401]
  スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。 我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。 本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
  論文  参考訳（メタデータ） (2023-12-07T06:19:39Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• NeuralGF: Unsupervised Point Normal Estimation by Learning Neural Gradient Function [55.86697795177619]
  3次元点雲の正規推定は3次元幾何処理の基本的な課題である。 我々は,ニューラルネットワークが入力点雲に適合することを奨励する,ニューラルグラデーション関数の学習のための新しいパラダイムを導入する。 広範に使用されているベンチマークの優れた結果から,本手法は非指向性および指向性正常推定タスクにおいて,より正確な正規性を学習できることが示されている。
  論文  参考訳（メタデータ） (2023-11-01T09:25:29Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
  論文  参考訳（メタデータ） (2023-08-12T02:47:57Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations [0.0]
  本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。 本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。 分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
  論文  参考訳（メタデータ） (2022-10-30T22:04:32Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• $\ell_2$-norm Flow Diffusion in Near-Linear Time [18.263667346853698]
  我々は$ell$-normフロー拡散問題に対して$widetildeO(m)$-timeランダム化アルゴリズムを提供する。 これは単純に双対解ベクトルを網羅することによって実現される。 Laplacianシステムソルバの高レベルなアルゴリズムフレームワークに適応するが、いくつかの新しいツールが必要である。
  論文  参考訳（メタデータ） (2021-05-30T21:27:58Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Factorized Graph Representations for Semi-Supervised Learning from Sparse Data [8.875598257768846]
  極端に粗いラベル付きグラフでも、遠隔互換性推定と呼ばれる手法が有効であることを示す。 我々の推定器は代替手法よりも桁違いに高速であり、エンドツーエンドの分類精度は金の標準適合性に匹敵するものである。
  論文  参考訳（メタデータ） (2020-03-05T18:57:45Z)

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

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