論文の概要: Heterogeneous Graphlets

• arxiv url: http://arxiv.org/abs/2010.14058v1
• Date: Fri, 23 Oct 2020 22:22:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-04 00:29:51.300450
• Title: Heterogeneous Graphlets
• Title（参考訳）: 異種グラフレット
• Authors: Ryan A. Rossi, Nesreen K. Ahmed, Aldo Carranza, David Arbour, Anup Rao, Sungchul Kim, Eunyee Koh
• Abstract要約: 我々は、型付きグラフレットと呼ばれる異種ネットワークにグラフレットの一般化を導入する。 このような型付きグラフレットの発生をカウントするための一般的なフレームワークについて述べる。 提案アルゴリズムは,異なる型付きグラフレットに対して,複数の関係性を利用する。
• 参考スコア（独自算出の注目度）: 41.34173447056566
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce a generalization of graphlets to heterogeneous networks called typed graphlets. Informally, typed graphlets are small typed induced subgraphs. Typed graphlets generalize graphlets to rich heterogeneous networks as they explicitly capture the higher-order typed connectivity patterns in such networks. To address this problem, we describe a general framework for counting the occurrences of such typed graphlets. The proposed algorithms leverage a number of combinatorial relationships for different typed graphlets. For each edge, we count a few typed graphlets, and with these counts along with the combinatorial relationships, we obtain the exact counts of the other typed graphlets in o(1) constant time. Notably, the worst-case time complexity of the proposed approach matches the time complexity of the best known untyped algorithm. In addition, the approach lends itself to an efficient lock-free and asynchronous parallel implementation. While there are no existing methods for typed graphlets, there has been some work that focused on computing a different and much simpler notion called colored graphlet. The experiments confirm that our proposed approach is orders of magnitude faster and more space-efficient than methods for computing the simpler notion of colored graphlet. Unlike these methods that take hours on small networks, the proposed approach takes only seconds on large networks with millions of edges. Notably, since typed graphlet is more general than colored graphlet (and untyped graphlets), the counts of various typed graphlets can be combined to obtain the counts of the much simpler notion of colored graphlets. The proposed methods give rise to new opportunities and applications for typed graphlets.
• Abstract（参考訳）: 本稿では,型付きグラフレットと呼ばれる異種ネットワークへのグラフレットの一般化を提案する。 形式的には、型付きグラフレットは小さな型付き誘導サブグラフである。 型付きグラフレットは、そのようなネットワークの高次型付き接続パターンを明示的に捉えるため、豊富な異種ネットワークにグラフレットを一般化する。 この問題に対処するために,このような型付きグラフレットの発生をカウントする一般的なフレームワークについて述べる。 提案アルゴリズムは,異なる型付きグラフレットの組合せ関係を利用する。 各エッジに対して、いくつかの型付きグラフレットをカウントし、これらのカウントと組合せ関係を合わせて、o(1)定数時間で他の型付きグラフレットの正確なカウントを得る。 特に、提案手法の最悪の時間複雑性は、最もよく知られた非型付けアルゴリズムの時間複雑性と一致する。 さらにこのアプローチは,効率的なロックフリーかつ非同期並列実装を実現する。 型付きグラフレットには既存の方法はないが、色付きグラフレットと呼ばれる異なるより単純な概念を計算することに焦点を当てた研究がいくつかある。 実験により,提案手法はより単純な色付きグラフレットの概念の計算方法よりも桁違いに高速で空間効率が高いことを確認した。 小さなネットワークでは時間を要するこれらの方法とは異なり、提案手法は数百万のエッジを持つ大規模ネットワークでは数秒しかかからない。 特に、型付きグラフレットは色付きグラフレット(および型なしグラフレット)よりも一般的であるため、様々な型付きグラフレットのカウントを組み合わせることで、色付きグラフレットのより単純な概念のカウントを得ることができる。 提案手法は、型付きグラフレットの新しい機会と応用をもたらす。

関連論文リスト

• Learning on Large Graphs using Intersecting Communities [13.053266613831447]
  MPNNは、各ノードの隣人からのメッセージを集約することで、入力グラフ内の各ノードの表現を反復的に更新する。 MPNNは、あまりスパースではないため、すぐに大きなグラフの禁止になるかもしれない。 本稿では,入力グラフを交差するコミュニティグラフ (ICG) として近似することを提案する。
  論文  参考訳（メタデータ） (2024-05-31T09:26:26Z)
• HeteroMILE: a Multi-Level Graph Representation Learning Framework for Heterogeneous Graphs [13.01983932286923]
  異種グラフ上のノードのマルチレベル埋め込みフレームワーク(HeteroMILE)を提案する。 HeteroMILEは、グラフを埋め込む前に、グラフのバックボーン構造を保ちながら、大きなグラフを小さなサイズに繰り返し調整する。 その後、ヘテロジニアスグラフ畳み込みニューラルネットワークを用いて、元のグラフへの粗い埋め込みを洗練する。
  論文  参考訳（メタデータ） (2024-03-31T22:22:10Z)
• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  学習対応は、不均一な対応分布と低い不整合率で設定された初期対応から正しい対応を見つけることを目的としている。 最近の進歩は、通常、グラフニューラルネットワーク(GNN)を使用して単一のタイプのグラフを構築したり、グローバルなグラフに局所グラフをスタックしてタスクを完了させる。 本稿では,複数の補完グラフを効果的に組み合わせるためのMGNetを提案する。
  論文  参考訳（メタデータ） (2024-01-10T07:58:44Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• ClusterFuG: Clustering Fully connected Graphs by Multicut [20.254912065749956]
  密マルチカットでは、クラスタリングの目的はノード特徴ベクトルの内部積として分解形式で与えられる。 我々は、密集した環境でのマルチカットのための古典的欲求アルゴリズムの書き直し方法と、より効率とソリューションの品質を高めるためにそれらをどう修正するかを示す。
  論文  参考訳（メタデータ） (2023-01-28T11:10:50Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  自己教師付きグラフ類似性学習のためのコントラストグラフマッチングネットワーク(CGMN)を提案する。 我々は,効率的なノード表現学習のために,クロスビューインタラクションとクロスグラフインタラクションという2つの戦略を用いる。 我々はノード表現をグラフ類似性計算のためのプール演算によりグラフレベル表現に変換する。
  論文  参考訳（メタデータ） (2022-05-30T13:20:26Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  本稿では,グラフマッチングを向上するための信頼度の高いグラフ構造を探索するために,GLAMという共用電子グラフ学習とマッチングネットワークを提案する。 提案手法は,3つの人気ビジュアルマッチングベンチマーク (Pascal VOC, Willow Object, SPair-71k) で評価される。 すべてのベンチマークにおいて、従来の最先端のグラフマッチング手法よりも大きなマージンを達成している。
  論文  参考訳（メタデータ） (2021-09-01T08:24:02Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。 AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。 本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
  論文  参考訳（メタデータ） (2021-05-22T07:05:48Z)
• NetVec: A Scalable Hypergraph Embedding System [1.8979377273990425]
  スケーラブルな非監視ハイパーグラフ埋め込みのための新しいフレームワークであるNetVecを紹介します。 我々は、NetVecがグラフ埋め込みアルゴリズムと結合して、数百万のノードとハイパーエッジを数分で埋め込むことができることを示す。
  論文  参考訳（メタデータ） (2021-03-09T18:06:56Z)
• Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
  本稿では,その構造的依存関係に応じてノード間の相互作用をキャプチャするグラフマルチセットトランス (GMT) を提案する。 実験の結果,GMTはグラフ分類ベンチマークにおいて,最先端のグラフプーリング法を著しく上回っていることがわかった。
  論文  参考訳（メタデータ） (2021-02-23T07:45:58Z)

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

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