論文の概要: Digraphwave: Scalable Extraction of Structural Node Embeddings via
Diffusion on Directed Graphs
- arxiv url: http://arxiv.org/abs/2207.10149v1
- Date: Wed, 20 Jul 2022 19:03:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-22 13:43:32.423186
- Title: Digraphwave: Scalable Extraction of Structural Node Embeddings via
Diffusion on Directed Graphs
- Title（参考訳）: Digraphwave:方向グラフ上の拡散による構造ノード埋め込みのスケーラブル抽出
- Authors: Ciwan Ceylan, Kambiz Ghoorchian and Danica Kragic
- Abstract要約: Digraphwaveは、有向グラフ上の構造ノード埋め込みを抽出するスケーラブルなアルゴリズムである。
この2つの組込み強化は、自己同型アイデンティティの分類において、マクロF1スコアの顕著な増加につながることが示されている。
- 参考スコア（独自算出の注目度）: 20.432261314154804
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Structural node embeddings, vectors capturing local connectivity information
for each node in a graph, have many applications in data mining and machine
learning, e.g., network alignment and node classification, clustering and
anomaly detection. For the analysis of directed graphs, e.g., transactions
graphs, communication networks and social networks, the capability to capture
directional information in the structural node embeddings is highly desirable,
as is scalability of the embedding extraction method. Most existing methods are
nevertheless only designed for undirected graph. Therefore, we present
Digraphwave -- a scalable algorithm for extracting structural node embeddings
on directed graphs. The Digraphwave embeddings consist of compressed diffusion
pattern signatures, which are twice enhanced to increase their discriminate
capacity. By proving a lower bound on the heat contained in the local vicinity
of a diffusion initialization node, theoretically justified diffusion timescale
values are established, and Digraphwave is left with only two easy-to-interpret
hyperparameters: the embedding dimension and a neighbourhood resolution
specifier. In our experiments, the two embedding enhancements, named
transposition and aggregation, are shown to lead to a significant increase in
macro F1 score for classifying automorphic identities, with Digraphwave
outperforming all other structural embedding baselines. Moreover, Digraphwave
either outperforms or matches the performance of all baselines on real graph
datasets, displaying a particularly large performance gain in a network
alignment task, while also being scalable to graphs with millions of nodes and
edges, running up to 30x faster than a previous diffusion pattern based method
and with a fraction of the memory consumption.
- Abstract（参考訳）: 構造ノードの埋め込み、グラフ内の各ノードのローカル接続情報をキャプチャするベクトルは、データマイニングや機械学習、例えばネットワークアライメントやノード分類、クラスタリング、異常検出に多くの応用がある。
例えば、トランザクショングラフ、通信ネットワーク、ソーシャルネットワークなどの有向グラフの分析には、組込み抽出法のスケーラビリティと同様に、構造ノード埋め込みにおける方向情報をキャプチャする能力が非常に望ましい。
既存の手法の多くは無向グラフに対してのみ設計されている。
そこで我々は,有向グラフ上の構造ノード埋め込みを抽出するスケーラブルなアルゴリズムである digraphwave を提案する。
Digraphwaveの埋め込みは圧縮拡散パターンシグネチャで構成されており、識別能力を高めるために2回拡張されている。
拡散初期化ノードの局所近傍に含まれる熱の下限を証明し、理論的に正当化された拡散時間スケール値を確立し、埋め込み次元と近傍分解能指定器との2つの解釈容易な超パラメータしか残さない。
実験では,2つの埋め込み拡張,すなわちトランスポジションとアグリゲーションが,自己同型アイデンティティを分類するためのマクロF1スコアを著しく増加させ,Digraphwaveは他のすべての構造的埋め込みベースラインよりも優れていた。
さらに、Digraphwaveは、実際のグラフデータセット上のすべてのベースラインのパフォーマンスを上回り、ネットワークアライメントタスクにおいて特に大きなパフォーマンス向上を示すと同時に、数百万のノードとエッジを持つグラフに対してスケーラブルで、以前の拡散パターンベースのメソッドよりも最大30倍高速で、メモリ消費のごく一部で実行されています。
関連論文リスト
- Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳（メタデータ） (2024-01-12T17:57:07Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Spectral Graph Convolutional Networks With Lifting-based Adaptive Graph
Wavelets [81.63035727821145]
スペクトルグラフ畳み込みネットワーク(SGCN)はグラフ表現学習において注目を集めている。
本稿では,適応グラフウェーブレットを用いたグラフ畳み込みを実装した新しいスペクトルグラフ畳み込みネットワークを提案する。
論文 参考訳（メタデータ） (2021-08-03T17:57:53Z) - Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
本稿では,その構造的依存関係に応じてノード間の相互作用をキャプチャするグラフマルチセットトランス (GMT) を提案する。
実験の結果,GMTはグラフ分類ベンチマークにおいて,最先端のグラフプーリング法を著しく上回っていることがわかった。
論文 参考訳（メタデータ） (2021-02-23T07:45:58Z) - Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
グラフ埋め込みは、高次元および非ユークリッド特徴空間でデータ構造を変換しエンコードする方法である。
CensNetは一般的なグラフ埋め込みフレームワークで、ノードとエッジの両方を潜在機能空間に埋め込む。
提案手法は,4つのグラフ学習課題における最先端のパフォーマンスを達成または一致させる。
論文 参考訳（メタデータ） (2020-10-25T22:39:31Z) - Anisotropic Graph Convolutional Network for Semi-supervised Learning [7.843067454030999]
グラフ畳み込みネットワークは、高精度な予測結果を達成するのに有用であることが証明された効率的なノード埋め込みを学習する。
これらのネットワークはグラフの過度な平滑化と縮小効果の問題に悩まされており、それはグラフの端に線形ラプラシア流を用いて拡散するからである。
本稿では,ノードからの情報的特徴を捉える非線形関数を導入し,過度なスムーシングを防止し,半教師付きノード分類のための異方性グラフ畳み込みネットワークを提案する。
論文 参考訳（メタデータ） (2020-10-20T13:56:03Z) - Spectral Embedding of Graph Networks [76.27138343125985]
ローカルノードの類似性と接続性、グローバル構造をトレードオフする教師なしグラフ埋め込みを導入する。
埋め込みは一般化されたグラフ Laplacian に基づいており、固有ベクトルは1つの表現においてネットワーク構造と近傍近傍の両方をコンパクトにキャプチャする。
論文 参考訳（メタデータ） (2020-09-30T04:59:10Z) - Representation Learning of Graphs Using Graph Convolutional Multilayer
Networks Based on Motifs [17.823543937167848]
mGCMNはノードの特徴情報とグラフの高階局所構造を利用する新しいフレームワークである。
グラフニューラルネットワークの学習効率を大幅に改善し、新たな学習モードの確立を促進する。
論文 参考訳（メタデータ） (2020-07-31T04:18:20Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。
その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
論文 参考訳（メタデータ） (2020-06-19T13:09:44Z) - Structural Temporal Graph Neural Networks for Anomaly Detection in
Dynamic Graphs [54.13919050090926]
本稿では,動的グラフの異常エッジを検出するために,エンドツーエンドの時間構造グラフニューラルネットワークモデルを提案する。
特に,まずターゲットエッジを中心にした$h$ホップ囲むサブグラフを抽出し,各ノードの役割を識別するノードラベル機能を提案する。
抽出した特徴に基づき,GRU(Gated Recurrent Unit)を用いて,異常検出のための時間的情報を取得する。
論文 参考訳（メタデータ） (2020-05-15T09:17:08Z) - Fast Sequence-Based Embedding with Diffusion Graphs [8.147652597876862]
ネットワーク埋め込みのためのシーケンスを高速に生成する手法として拡散グラフを提案する。
その計算効率は、より単純なシーケンス生成のため、従来の方法よりも優れている。
コミュニティ検出タスクでは、埋め込み空間内のクラスタリングノードは、他のシーケンスベースの埋め込み方法よりも優れた結果をもたらす。
論文 参考訳（メタデータ） (2020-01-21T12:04:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。