論文の概要: Sublinear-Time Clustering Oracle for Signed Graphs
- arxiv url: http://arxiv.org/abs/2206.13813v1
- Date: Tue, 28 Jun 2022 08:05:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-29 14:30:26.621858
- Title: Sublinear-Time Clustering Oracle for Signed Graphs
- Title（参考訳）: 署名付きグラフのためのサブ線形時間クラスタリングOracle
- Authors: Stefan Neumann, Pan Peng
- Abstract要約: 署名付きグラフに対して,コミュニティ構造を明確にした局所クラスタリングオラクルを提供する。
我々は,このようなオラクルの構築と,合成および実世界のデータセット上での会員クエリ応答のアルゴリズムを評価した。
- 参考スコア（独自算出の注目度）: 13.312908995596306
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Social networks are often modeled using signed graphs, where vertices
correspond to users and edges have a sign that indicates whether an interaction
between users was positive or negative. The arising signed graphs typically
contain a clear community structure in the sense that the graph can be
partitioned into a small number of polarized communities, each defining a
sparse cut and indivisible into smaller polarized sub-communities. We provide a
local clustering oracle for signed graphs with such a clear community
structure, that can answer membership queries, i.e., "Given a vertex $v$, which
community does $v$ belong to?", in sublinear time by reading only a small
portion of the graph. Formally, when the graph has bounded maximum degree and
the number of communities is at most $O(\log n)$, then with
$\tilde{O}(\sqrt{n}\operatorname{poly}(1/\varepsilon))$ preprocessing time, our
oracle can answer each membership query in
$\tilde{O}(\sqrt{n}\operatorname{poly}(1/\varepsilon))$ time, and it correctly
classifies a $(1-\varepsilon)$-fraction of vertices w.r.t. a set of hidden
planted ground-truth communities. Our oracle is desirable in applications where
the clustering information is needed for only a small number of vertices.
Previously, such local clustering oracles were only known for unsigned graphs;
our generalization to signed graphs requires a number of new ideas and gives a
novel spectral analysis of the behavior of random walks with signs. We evaluate
our algorithm for constructing such an oracle and answering membership queries
on both synthetic and real-world datasets, validating its performance in
practice.
- Abstract（参考訳）: ソーシャルネットワークはしばしば署名付きグラフを使用してモデル化され、頂点はユーザに対応し、エッジはユーザ間のインタラクションが肯定的か否定的かを示すサインを持っている。
符号付きグラフは、典型的には、グラフを少数の分極されたコミュニティに分割できるという意味で明確なコミュニティ構造を含み、それぞれがスパースカットを定義し、より小さな分極されたサブコミュニティに分割できる。
このような明確なコミュニティ構造を持つ符号付きグラフに対して局所的なクラスタリングのオラクルを提供し、そのグラフのごく一部だけを読み取ることで、サブ線形時間で、"vertex $v$, which community do $v$ belong?" というようなメンバシップクエリに答えることができる。
正式には、グラフが最大値が有界であり、コミュニティ数が最大で$o(\log n)$であるとき、$\tilde{o}(\sqrt{n}\operatorname{poly}(1/\varepsilon))$ 前処理時間で、オラクルは各メンバシップクエリに$\tilde{o}(\sqrt{n}\operatorname{poly}(1/\varepsilon)$ timeで答えることができ、$(1-\varepsilon)$-fraction of vertices w.r.t. a hidden planted ground-truth communities を正しく分類する。
私たちのオラクルは、少数の頂点に対してのみクラスタリング情報を必要とするアプリケーションで望ましいです。
これまでは、このような局所的なクラスタリングオラクルは、符号付きグラフでしか知られていなかった; 符号付きグラフへの我々の一般化には、多くの新しいアイデアが必要であり、符号付きランダムウォークの振る舞いの新しいスペクトル分析を与える。
このようなoracleを構築し、合成データと実世界のデータセットの両方でメンバシップクエリに応答するアルゴリズムを評価し、実際のパフォーマンスを検証する。
関連論文リスト
- Self-Directed Learning of Convex Labelings on Graphs [11.286983359775512]
本研究では,自己指向型学習システムにおいて,与えられたグラフのクラスタを学習する問題について検討する。
グラフ上の自己指向ノード分類に関して、これまでは成果は存在しなかった。
論文 参考訳（メタデータ） (2024-09-02T19:13:26Z) - Learning on Large Graphs using Intersecting Communities [13.053266613831447]
MPNNは、各ノードの隣人からのメッセージを集約することで、入力グラフ内の各ノードの表現を反復的に更新する。
MPNNは、あまりスパースではないため、すぐに大きなグラフの禁止になるかもしれない。
本稿では,入力グラフを交差するコミュニティグラフ (ICG) として近似することを提案する。
論文 参考訳（メタデータ） (2024-05-31T09:26:26Z) - A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing
Time [6.961946145048321]
本稿では,クラスタ性が強いグラフに対して,サブ線形時間スペクトルクラスタリングオラクルを設計する問題に対処する。
アルゴリズムは仮定を緩和するが、誤分類比はわずかに高い。
私たちのクラスタリングオラクルは、いくつかのランダムなエッジ削除に対して堅牢です。
論文 参考訳（メタデータ） (2023-10-27T03:40:37Z) - Multi-Granularity Graph Pooling for Video-based Person Re-Identification [14.943835935921296]
ビデオサンプルの時間的特徴と空間的特徴を集約するためにグラフニューラルネットワーク(GNN)が導入された。
STGCNのような既存のグラフベースのモデルは、グラフ表現を得るためにノード機能でtextitmean/textitmaxプールを実行する。
ビデオ検索のための多粒度グラフ表現を学習するためのグラフプーリングネットワーク(GPNet)を提案する。
論文 参考訳（メタデータ） (2022-09-23T13:26:05Z) - Higher-order Clustering and Pooling for Graph Neural Networks [77.47617360812023]
グラフニューラルネットワークは、多数のグラフ分類タスクにおいて最先端のパフォーマンスを達成する。
HoscPoolはクラスタリングベースのグラフプーリング演算子で、階層的に高階情報をキャプチャする。
グラフ分類タスクにおいてHoscPoolを評価し,そのクラスタリングコンポーネントを地層構造を持つグラフ上で評価する。
論文 参考訳（メタデータ） (2022-09-02T09:17:10Z) - Semi-Supervised Hierarchical Graph Classification [54.25165160435073]
ノードがグラフのインスタンスである階層グラフにおけるノード分類問題について検討する。
本稿では階層グラフ相互情報(HGMI)を提案し,理論的保証をもってHGMIを計算する方法を提案する。
本稿では,この階層グラフモデリングとSEAL-CI法がテキストおよびソーシャルネットワークデータに与える影響を実証する。
論文 参考訳（メタデータ） (2022-06-11T04:05:29Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Topology-Aware Graph Pooling Networks [51.9008939769679]
ポーリング操作はコンピュータビジョンや自然言語処理タスクに有効である。
グラフデータ上でプーリング操作を実行する上での課題のひとつは、グラフ上で明確に定義されていない局所性の欠如である。
本稿では,グラフトポロジを明示的に考慮したトポロジ対応プーリング(TAP)層を提案する。
論文 参考訳（メタデータ） (2020-10-19T20:14:30Z) - Inverse Graph Identification: Can We Identify Node Labels Given Graph
Labels? [89.13567439679709]
グラフ識別(GI)は、グラフ学習において長い間研究されており、特定の応用において不可欠である。
本稿では,逆グラフ識別(Inverse Graph Identification, IGI)と呼ばれる新しい問題を定義する。
本稿では,グラフアテンションネットワーク(GAT)を用いたノードレベルのメッセージパッシング処理を,GIのプロトコルの下でシンプルかつ効果的に行う方法を提案する。
論文 参考訳（メタデータ） (2020-07-12T12:06:17Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。
その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
論文 参考訳（メタデータ） (2020-06-19T13:09:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。