論文の概要: Computing Graph Descriptors on Edge Streams

• arxiv url: http://arxiv.org/abs/2109.01494v1
• Date: Thu, 2 Sep 2021 06:21:47 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-06 14:03:55.405625
• Title: Computing Graph Descriptors on Edge Streams
• Title（参考訳）: エッジストリーム上のグラフ記述子
• Authors: Zohair Raza Hassan, Imdadullah Khan, Mudassir Shabbir, Waseem Abbas
• Abstract要約: グラフの構造的特徴を近似するために,シングルパスストリーミングアルゴリズムを提案する。 エッジストリームを操作することで、グラフ全体をメモリに保持するのを避けることができます。 大規模グラフに対する近似誤差,分類精度,スケーラビリティを解析することにより,記述子の有効性を実証する。
• 参考スコア（独自算出の注目度）: 4.664495510551647
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph feature extraction is a fundamental task in graphs analytics. Using feature vectors (graph descriptors) in tandem with data mining algorithms that operate on Euclidean data, one can solve problems such as classification, clustering, and anomaly detection on graph-structured data. This idea has proved fruitful in the past, with spectral-based graph descriptors providing state-of-the-art classification accuracy on benchmark datasets. However, these algorithms do not scale to large graphs since: 1) they require storing the entire graph in memory, and 2) the end-user has no control over the algorithm's runtime. In this paper, we present single-pass streaming algorithms to approximate structural features of graphs (counts of subgraphs of order $k \geq 4$). Operating on edge streams allows us to avoid keeping the entire graph in memory, and controlling the sample size enables us to control the time taken by the algorithm. We demonstrate the efficacy of our descriptors by analyzing the approximation error, classification accuracy, and scalability to massive graphs. Our experiments showcase the effect of the sample size on approximation error and predictive accuracy. The proposed descriptors are applicable on graphs with millions of edges within minutes and outperform the state-of-the-art descriptors in classification accuracy.
• Abstract（参考訳）: グラフ機能抽出は、グラフ分析の基本的なタスクである。 特徴ベクトル(グラフ記述子)とユークリッドデータを操作するデータマイニングアルゴリズムを組み合わせることで、グラフ構造化データにおける分類、クラスタリング、異常検出などの問題を解決することができる。 このアイデアは過去に実りあると証明され、スペクトルベースのグラフ記述子はベンチマークデータセットで最先端の分類精度を提供する。 しかし、これらのアルゴリズムは大きなグラフにスケールしない: 1) グラフ全体をメモリに保存する必要がある、2) エンドユーザはアルゴリズムのランタイムを制御できない。 本稿では,グラフの構造的特徴を近似するシングルパスストリーミングアルゴリズムを提案する(位数$k \geq 4$のサブグラフの数)。 エッジストリームを運用することで、グラフ全体のメモリ保持を回避することができ、サンプルサイズを制御することで、アルゴリズムが処理する時間を制御できます。 大規模グラフに対する近似誤差,分類精度,スケーラビリティを解析することにより,記述子の有効性を実証する。 実験では,サンプルサイズが近似誤差および予測精度に及ぼす影響を示した。 提案した記述子は、数分で数百万のエッジを持つグラフに適用でき、分類精度において最先端の記述子より優れている。

関連論文リスト

• Graph Parsing Networks [64.5041886737007]
  本稿では,効率的なグラフ解析アルゴリズムを提案する。 結果として得られるグラフパーシングネットワーク(GPN)は、個々のグラフに対してパーソナライズされたプーリング構造を適応的に学習する。
  論文  参考訳（メタデータ） (2024-02-22T09:08:36Z)
• Exploiting Edge Features in Graphs with Fused Network Gromov-Wasserstein Distance [18.522233517515975]
  ノードとエッジが特徴を持つグラフを比較するために,Gromov-Wasserstein距離の拡張を導入する。 入力空間または出力空間でグラフが発生する学習タスクにおいて、新しい距離の有効性を実証的に示す。
  論文  参考訳（メタデータ） (2023-09-28T17:05:03Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  本研究では,スムーズなグラフ信号分布の空間への埋め込みを通じて,グラフ平均を定義する新しいフレームワークを提案する。 この埋め込み空間において平均を求めることにより、構造情報を保存する平均グラフを復元することができる。 我々は,新しいグラフの意味の存在と特異性を確立し,それを計算するための反復アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-05-31T11:04:53Z)
• Towards Accurate Subgraph Similarity Computation via Neural Graph Pruning [22.307526272085024]
  本研究では,グラフプルーニングをノード遅延問題に変換し,それを微分可能な問題に緩和する。 このアイデアに基づいて、サブグラフ編集距離(SED)のタイプを近似する新しいニューラルネットワークを設計する。 モデルの設計では,クエリグラフに関する情報を活用し,対象グラフのプルーニングを誘導するアテンション機構を提案する。
  論文  参考訳（メタデータ） (2022-10-19T15:16:28Z)
• Malware Analysis with Symbolic Execution and Graph Kernel [2.1377923666134113]
  機械学習に基づく分類のためのオープンソースのツールチェーンを提案する。 グラフ間の局所的な類似性を捉えることができる1次元Weisfeiler-Lehmanカーネルに焦点を当てる。
  論文  参考訳（メタデータ） (2022-04-12T08:52:33Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか? 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
  論文  参考訳（メタデータ） (2021-06-08T16:10:36Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Faster Graph Embeddings via Coarsening [25.37181684580123]
  グラフ埋め込みは、グラフ構造化データ上のノード分類やリンク予測といった機械学習タスクのためのユビキタスツールである。 大規模グラフに対する埋め込みの計算は、関連する頂点の小さな部分集合のみに関心がある場合でも、非効率的である。 我々は、関連する頂点の埋め込みを計算するために、Schur補数に基づく効率的なグラフ粗大化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-06T15:22:25Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Wasserstein Embedding for Graph Learning [33.90471037116372]
  Wasserstein Embedding for Graph Learning (WEGL)は、グラフ全体をベクトル空間に埋め込むフレームワークである。 グラフ間の類似性をノード埋め込み分布間の類似性の関数として定義する上で,新たな知見を活用する。 各種ベンチマークグラフ固有性予測タスクにおける新しいグラフ埋め込み手法の評価を行った。
  論文  参考訳（メタデータ） (2020-06-16T18:23:00Z)

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

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