論文の概要: Classic Graph Structural Features Outperform Factorization-Based Graph
Embedding Methods on Community Labeling
- arxiv url: http://arxiv.org/abs/2201.08481v1
- Date: Thu, 20 Jan 2022 22:43:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-24 21:04:51.481495
- Title: Classic Graph Structural Features Outperform Factorization-Based Graph
Embedding Methods on Community Labeling
- Title（参考訳）: コミュニティラベリングにおけるファクトリゼーションに基づくグラフ埋め込み手法の古典的グラフ構造
- Authors: Andrew Stolman and Caleb Levy and C. Seshadhri and Aneesh Sharma
- Abstract要約: グラフ表現学習(グラフ埋め込みとも呼ばれる)は、ネットワーク構造を機械学習モデルに組み込む一般的な手法である。
そこで我々は,ペアワイズコミュニティラベリングの共通課題に対する埋め込みのクラスの性能に関する実証的,理論的解析を行った。
一般の低次元分解法は,コミュニティ構造を創出できないか,不安定なコミュニティしか創出できないことを実証する。
- 参考スコア（独自算出の注目度）: 8.931361895613646
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph representation learning (also called graph embeddings) is a popular
technique for incorporating network structure into machine learning models.
Unsupervised graph embedding methods aim to capture graph structure by learning
a low-dimensional vector representation (the embedding) for each node. Despite
the widespread use of these embeddings for a variety of downstream transductive
machine learning tasks, there is little principled analysis of the
effectiveness of this approach for common tasks. In this work, we provide an
empirical and theoretical analysis for the performance of a class of embeddings
on the common task of pairwise community labeling. This is a binary variant of
the classic community detection problem, which seeks to build a classifier to
determine whether a pair of vertices participate in a community. In line with
our goal of foundational understanding, we focus on a popular class of
unsupervised embedding techniques that learn low rank factorizations of a
vertex proximity matrix (this class includes methods like GraRep, DeepWalk,
node2vec, NetMF). We perform detailed empirical analysis for community labeling
over a variety of real and synthetic graphs with ground truth. In all cases we
studied, the models trained from embedding features perform poorly on community
labeling. In constrast, a simple logistic model with classic graph structural
features handily outperforms the embedding models. For a more principled
understanding, we provide a theoretical analysis for the (in)effectiveness of
these embeddings in capturing the community structure. We formally prove that
popular low-dimensional factorization methods either cannot produce community
structure, or can only produce ``unstable" communities. These communities are
inherently unstable under small perturbations.
- Abstract（参考訳）: グラフ表現学習(グラフ埋め込みとも呼ばれる)は、ネットワーク構造を機械学習モデルに組み込む一般的な手法である。
教師なしグラフ埋め込み手法は、各ノードの低次元ベクトル表現(埋め込み)を学習することでグラフ構造をキャプチャすることを目的としている。
これらの埋め込みは、様々なダウンストリームトランスダクティブ機械学習タスクに広く使われているが、一般的なタスクに対するこのアプローチの有効性の原則的な分析はほとんどない。
本研究では,2つのコミュニティラベリングの共通課題に対する埋め込みのクラスの性能について,実証的および理論的解析を行った。
これは、一対の頂点がコミュニティに参加するかどうかを判断する分類器を構築しようとする古典的なコミュニティ検出問題のバイナリ変種である。
基礎的理解の目的に合わせて、頂点近接行列の低階分解を学習する教師なし埋め込み技術(このクラスはGraRep、DeepWalk、node2vec、NetMFのようなメソッドを含む)の一般的なクラスに焦点を当てる。
我々は,様々な実数グラフと合成グラフを用いたコミュニティラベリングの詳細な実験分析を行った。
あらゆるケースで、埋め込み機能から訓練されたモデルは、コミュニティのラベル付けにはあまり役立ちません。
constrastでは、古典的なグラフ構造を持つ単純なロジスティックモデルが埋め込みモデルよりも巧みに優れている。
より原理的な理解のために、我々はこれらの埋め込みがコミュニティ構造を捉える上で有効であることを示す理論的分析を提供する。
一般の低次元因数分解法は,コミュニティ構造を生成できないか,あるいは「不安定」なコミュニティしか生成できないことを正式に証明する。
これらのコミュニティは、小さな摂動下で本質的に不安定である。
関連論文リスト
- Curvature-based Clustering on Graphs [14.136746708037402]
グラフの幾何学を利用して、クラスタやコミュニティを形成する密接な連結部分構造を同定するアルゴリズムについて研究する。
本手法は, 離散リッチ曲率とそのそれに付随する幾何フローを実装し, グラフのエッジ重みを進化させて, そのコミュニティ構造を明らかにする。
論文 参考訳（メタデータ） (2023-07-19T17:35:08Z) - Bures-Wasserstein Means of Graphs [60.42414991820453]
本研究では,スムーズなグラフ信号分布の空間への埋め込みを通じて,グラフ平均を定義する新しいフレームワークを提案する。
この埋め込み空間において平均を求めることにより、構造情報を保存する平均グラフを復元することができる。
我々は,新しいグラフの意味の存在と特異性を確立し,それを計算するための反復アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-05-31T11:04:53Z) - State of the Art and Potentialities of Graph-level Learning [54.68482109186052]
グラフレベルの学習は、比較、回帰、分類など、多くのタスクに適用されている。
グラフの集合を学習する伝統的なアプローチは、サブストラクチャのような手作りの特徴に依存している。
ディープラーニングは、機能を自動的に抽出し、グラフを低次元表現に符号化することで、グラフレベルの学習をグラフの規模に適応させるのに役立っている。
論文 参考訳（メタデータ） (2023-01-14T09:15:49Z) - Graph-wise Common Latent Factor Extraction for Unsupervised Graph
Representation Learning [40.70562886682939]
我々は、教師なしグラフ表現学習のための新しい原則を提案する:グラフワイド共通潜在因子抽出(GCFX)
GCFXは入力グラフから一般的な潜伏因子を明示的に抽出し、現在の最先端のタスクで改善された結果を達成する。
広範囲な実験と分析により,GCFXは個々のノードや周辺地域の局所的な変動による障害を軽減するため,グラフレベルのタスクに有用であることを示す。
論文 参考訳（メタデータ） (2021-12-16T12:22:49Z) - A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。
AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。
本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
論文 参考訳（メタデータ） (2021-05-22T07:05:48Z) - CommPOOL: An Interpretable Graph Pooling Framework for Hierarchical
Graph Representation Learning [74.90535111881358]
新しい解釈可能なグラフプーリングフレームワークである CommPOOL を提案します。
グラフ表現学習プロセスにおいて、グラフの階層的なコミュニティ構造をキャプチャし、保存することができる。
CommPOOLは階層グラフ表現学習のための汎用的で柔軟なフレームワークです。
論文 参考訳（メタデータ） (2020-12-10T21:14:18Z) - On the Impact of Communities on Semi-supervised Classification Using
Graph Neural Networks [0.5872014229110213]
半教師付きノード分類におけるGNNの性能に対するコミュニティ構造の影響をグラフ上で体系的に研究する。
その結果,コミュニティは学習過程や分類性能に大きな影響を与えることが示唆された。
論文 参考訳（メタデータ） (2020-10-30T13:17:38Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。
本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。
我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
論文 参考訳（メタデータ） (2020-08-31T08:41:20Z) - Goal-directed graph construction using reinforcement learning [3.291429094499946]
我々は、中央エージェントが試行錯誤によってトポロジを生成する決定過程としてグラフの構築を定式化する。
グラフ構築と改善戦略を学習するための強化学習とグラフニューラルネットワークに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-30T12:11:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。