論文の概要、ライセンス

# (参考訳) COLOGNE: Coordinated Local Graph Neighborhood Smpling [全文訳有]

COLOGNE: Coordinated Local Graph Neighborhood Sampling ( http://arxiv.org/abs/2102.04770v1 )

ライセンス: CC BY 4.0
Konstantin Kutzkov(参考訳) グラフの表現学習は、標準的な機械学習アルゴリズムとデータ分析ツールをグラフデータに適用することを可能にする。 グラフノードなどの離散非順序オブジェクトを実値ベクトルで置き換えることは、グラフデータから学ぶための多くのアプローチの中心です。 このようなベクトル表現や埋め込みは、ノードを高次元空間内のベクトルとして表現することで元のデータ内の離散的な関係を捉える。 ほとんどのアプリケーショングラフでは、実際のオブジェクトとノード間の関係をモデル化し、しばしば元のオブジェクトに関する貴重なメタ情報を含む。 強力な機械学習ツールである一方で、組み込みはそのようなノード属性を保存することはできない。 この欠点に対処し、ノードベクトル表現の座標がグラフノードであるような離散ノード埋め込みを学習する問題を考察する。 これにより、もともとノードに存在するすべての属性が保存されるため、グラフの解釈可能な機械学習アルゴリズムを設計するドアが開きます。 本稿では,各ノードが属性とともに固定数のグラフノードで表されるように,局所グラフ近傍サンプリング(COLOGNE)をコーディネートするためのフレームワークを提案する。 個々のサンプルは調整され、ノード近傍間の類似性を保持する。 我々はスケーラブルなアルゴリズムを設計するための類似性の異なる概念を考える。 提案されたアルゴリズムの理論的結果を示す。 ベンチマークグラフにおける実験は、設計した埋め込みの品質を評価し、グラフデータの解釈可能な機械学習アルゴリズムのトレーニングにどのように組み込むかを実証する。

Representation learning for graphs enables the application of standard machine learning algorithms and data analysis tools to graph data. Replacing discrete unordered objects such as graph nodes by real-valued vectors is at the heart of many approaches to learning from graph data. Such vector representations, or embeddings, capture the discrete relationships in the original data by representing nodes as vectors in a high-dimensional space. In most applications graphs model the relationship between real-life objects and often nodes contain valuable meta-information about the original objects. While being a powerful machine learning tool, embeddings are not able to preserve such node attributes. We address this shortcoming and consider the problem of learning discrete node embeddings such that the coordinates of the node vector representations are graph nodes. This opens the door to designing interpretable machine learning algorithms for graphs as all attributes originally present in the nodes are preserved. We present a framework for coordinated local graph neighborhood sampling (COLOGNE) such that each node is represented by a fixed number of graph nodes, together with their attributes. Individual samples are coordinated and they preserve the similarity between node neighborhoods. We consider different notions of similarity for which we design scalable algorithms. We show theoretical results for all proposed algorithms. Experiments on benchmark graphs evaluate the quality of the designed embeddings and demonstrate how the proposed embeddings can be used in training interpretable machine learning algorithms for graph data.
公開日: Tue, 9 Feb 2021 11:39:06 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
COLOGNE: Coordinated Local Graph Neighborhood Sampling COLOGNE: Coordinated Local Graph Neighborhood Smpling 0.81
Konstantin Kutzkov Konstantin Kutzkov 0.85
kutzkov@gmail.com kutzkov@gmail.com 0.78
Abstract 1 2 0 2 概要 1 2 0 2 0.65
b e F 9 ] b e F 9 ] 0.85
G L . s c [ 1 v 0 7 7 4 0 G L。 sc [ 1 v 0 7 7 4 0 0.70
. 2 0 1 2 : v i X r a . 2 0 1 2 : v i X r a 0.85
Representation learning for graphs enables the application of standard machine learning algorithms and data analysis tools to graph data. グラフの表現学習は、標準的な機械学習アルゴリズムとデータ分析ツールをグラフデータに適用することを可能にする。 0.76
Replacing discrete unordered objects such as graph nodes by real-valued vectors is at the heart of many approaches to learning from graph data. グラフノードなどの離散非順序オブジェクトを実値ベクトルで置き換えることは、グラフデータから学ぶための多くのアプローチの中心です。 0.77
Such vector representations, or embeddings, capture the discrete relationships in the original data by representing nodes as vectors in a high-dimensional space. このようなベクトル表現や埋め込みは、ノードを高次元空間内のベクトルとして表現することで元のデータ内の離散的な関係を捉える。 0.67
In most applications graphs model the relationship between real-life objects and often nodes contain valuable meta-information about the original objects. ほとんどのアプリケーショングラフでは、実際のオブジェクトとノード間の関係をモデル化し、しばしば元のオブジェクトに関する貴重なメタ情報を含む。 0.65
While being a powerful machine learning tool, embeddings are not able to preserve such node attributes. 強力な機械学習ツールである一方で、組み込みはそのようなノード属性を保存することはできない。 0.67
We address this shortcoming and consider the problem of learning discrete node embeddings such that the coordinates of the node vector representations are graph nodes. この欠点に対処し、ノードベクトル表現の座標がグラフノードであるような離散ノード埋め込みを学習する問題を考察する。 0.80
This opens the door to designing interpretable machine learning algorithms for graphs as all attributes originally present in the nodes are preserved. これにより、もともとノードに存在するすべての属性が保存されるため、グラフの解釈可能な機械学習アルゴリズムを設計するドアが開きます。 0.67
We present a framework for coordinated local graph neighborhood sampling (COLOGNE) such that each node is represented by a fixed number of graph nodes, together with their attributes. 本稿では,各ノードが属性とともに固定数のグラフノードで表されるように,局所グラフ近傍サンプリング(COLOGNE)をコーディネートするためのフレームワークを提案する。 0.85
Individual samples are coordinated and they preserve the similarity between node neighborhoods. 個々のサンプルは調整され、ノード近傍間の類似性を保持する。 0.63
We consider different notions of similarity for which we design scalable algorithms. 我々はスケーラブルなアルゴリズムを設計するための類似性の異なる概念を考える。 0.76
We show theoretical results for all proposed algorithms. 提案されたアルゴリズムの理論的結果を示す。 0.75
Experiments on benchmark graphs evaluate the quality of the designed embeddings and demonstrate how the proposed embeddings can be used in training interpretable machine learning algorithms for graph data. ベンチマークグラフにおける実験は、設計した埋め込みの品質を評価し、グラフデータの解釈可能な機械学習アルゴリズムのトレーニングにどのように組み込むかを実証する。 0.74
1 Introduction Graphs are ubiquitous representation for structured data. はじめに グラフは構造化データのユビキタス表現である。 0.65
They model naturally occurring relations between objects and, in a sense, generalize sequential data to more complex dependencies. オブジェクト間の自然な関係をモデル化し、ある意味、シーケンシャルデータをより複雑な依存関係に一般化する。 0.80
Not surprising, many algorithms originally designed for learning from sequential data are generalized to learning from graph data. 驚くことではないが、もともとシーケンシャルデータから学習するために設計された多くのアルゴリズムは、グラフデータから学習するために一般化されている。 0.55
Learning vector representations of individual graph nodes, or node embeddings, is such an example where approaches to learning word representations from natural language text have inspired learning from graph data. 個々のグラフノードまたはノード埋め込みのベクトル表現の学習は、自然言語のテキストから単語表現を学ぶアプローチがグラフデータから学習に触発された例です。 0.87
Node embeddings have become an integral part of the graph learning toolbox, with applications ranging from link prediction (Perozzi et al, 2014; Grover and Leskovec, 2016) to graph compression (Ahmed et al, 2017). ノードの埋め込みはグラフ学習ツールボックスの不可欠な部分となり、リンク予測(Perozzi et al, 2014; Grover and Leskovec, 2016)からグラフ圧縮(Ahmed et al, 2017)まで幅広いアプリケーションがある。 0.80
The first presented algorithm (Perozzi et al, 2014) for learning node embeddings works by generating random walks, starting from each node u in the given graph, and then feeding the sequences of visited nodes into a word embedding learning algorithm such as word2vec (Mikolov et al, 2013). ノード埋め込みを学習するための最初のアルゴリズム(Perozzi et al, 2014)は、与えられたグラフの各ノード u からランダムウォークを生成し、訪問したノード列を word2vec (Mikolov et al, 2013) のような単語埋め込み学習アルゴリズムに入力することで機能する。 0.87
Later, these approaches were extended to a more general setting where different neighborhood definitions are supported and one can sample from these neighborhoods (Tang et al, 2015b; Grover and Leskovec, 2016; Tsitsulin et al, 2018). その後、これらのアプローチは、異なる近所の定義をサポートし、これらの地区からサンプルを採取できるより一般的な設定に拡張された(tang et al, 2015b, grover and leskovec, 2016; tsitsulin et al, 2018)。 0.72
Algorithms based on random walks generate samples that are independent for different nodes, i.e., a random walk starting from a node u is likely to be very different from a random walk starting at another node v, even if u and v have very similar neighborhoods, for some intuitive notion of similarity. ランダムウォークに基づくアルゴリズムは、異なるノードに対して独立したサンプルを生成する。すなわち、ノードuから始まるランダムウォークは、uとvが非常に類似した近傍を持っている場合でも、他のノードvから始まるランダムウォークとは大きく異なる可能性が高い。 0.72
By generating a large number of random walks the sets of sampled nodes for u and v will eventually reflect the similarity between u and v but individual samples are much less likely to preserve the similarity. 多数のランダムウォークを生成することで、u と v のサンプルノードの集合は最終的に u と v の類似性を反映するが、個々のサンプルは類似性を保ちにくい。 0.79
As an illustration, consider a large social network such as twitter where nodes represent users and edges who-follows-whom relationships. 例示として、Twitterのような大きなソーシャルネットワークでは、ノードがユーザやエッジを表現し、その関係をフォローする。
訳抜け防止モード: 例示として、twitterのような大きなソーシャルネットワークを考えてみましょう。 ノードはユーザとエッジを表す。
0.71
Consider two nodes corresponding to the famous football managers J¨urgen Klopp and Pep 有名なサッカーマネージャーJ オーゲンKloppとPepに対応する2つのノードを検討してください。 0.59
1 1 0.85
英語(論文から抽出)日本語訳スコア
Guardiola. Maybe they don’t have so many followers in common as they represent football rivals. Guardiola おそらく彼らは、サッカーのライバルを代表するほど多くのフォロワーを抱えていないのだろう。 0.60
Let K and G be Klopp’s and Guardiola’s 2-hop neighborhood local graphs, respectively. K と G をそれぞれ Klopp's と Guardiola の 2 ホップ近傍の局所グラフとする。 0.77
We might expect that the nodes in these “friends of friends” graphs, V (K) and V (G), will have a large overlap as they likely capture the majority of English football fans. これらの「友人の友人」グラフ、V(K)とV(G)のノードは、英国のフットボールファンの大半をキャプチャする可能性が高いため、大きな重複があると予想されるかもしれません。 0.74
However, if we sample nodes at random from V (K) and V (G), then most likely the sampled nodes will be different. しかし、v (k) と v (g) からランダムにノードをサンプリングすると、サンプリングされたノードが異なる可能性が高い。
訳抜け防止モード: ただし、V(K)とV(G)からランダムにノードをサンプリングする場合。 そして、最も可能性の高いサンプルノードは異なります。
0.75
But assume we were able to randomly permute the nodes in V (K) ∪ V (G) and then return the first node from V (K) and V (G), according to the total order defined by the permutation, as samples for Klopp and Guardiola. しかし、Klopp と Guardiola のサンプルとして置換によって定義される全順序に従って、V (K) と V (G) のノードをランダムにパーミュートし、V (K) と V (G) から最初のノードを返すことができると仮定する。 0.81
Then it would be much more likely to get the |V (G)∩V (K)| |V (G)||V (K)| and in the case same node. このとき、|V (G) = V (K)| |V (G)||V (K)| を得る確率は、同じノードの場合よりもずっと高い。 0.80
In the case of random walks the probability for identical samples is |V (G)∩V (K)| of random permutations it is |V (G)∪V (K)| , i.e., the samples already capture that Klopp and Guardiola are similar twitter users. ランダムウォークの場合、同一のサンプルの確率は、ランダムな置換の |V (G) = V (K)| であり、つまり、既に Klopp と Guardiola がよく似た Twitter ユーザであることを示すサンプルが |V (G) = V (K)| である。 0.76
And if we also consider the profiles of the sampled nodes, say by analyzing the activity of the corresponding users, then we might be able to infer that Klopp and Guardiola are Premier League managers. そして、サンプルノードのプロファイルも考慮すれば、例えば対応するユーザーのアクティビティを分析することによって、KloppとGuardiolaがプレミアリーグのマネージャーであると推測できるかもしれません。 0.77
The main intuition behind coordinated sampling is that each sample is an independent estimator of the similarity between nodes and thus sampled nodes themselves can be coordinates of the embedding vectors. 座標サンプリングの背後にある主な直感は、各サンプルがノード間の類似性の独立な推定子であり、したがって標本化されたノード自体が埋め込みベクトルの座標となることである。 0.70
This has two major advantages over continuous embeddings. これは連続埋め込みよりも2つの大きな利点がある。 0.61
First, we avoid the need to train a model that computes continuous embeddings. まず、継続的な埋め込みを計算するモデルをトレーニングする必要性を避ける。 0.66
Thus, if the underlying sampling procedure is efficient, the approach can be highly scalable and simplify machine learning pipelines that work with node embeddings. したがって、基礎となるサンプリング手順が効率的であれば、このアプローチは高度にスケーラブルで、ノード埋め込みで動作する機械学習パイプラインを簡素化することができる。 0.63
Second, and probably more important, the samples are the original graph nodes. 第二に、おそらくもっと重要なのは、サンプルは元のグラフノードです。 0.74
Usually graphs model real-life problems and graph nodes contain various kinds of additional information, be it personal data of users of a social network or the weather conditions at railway stations. 通常、グラフは現実の問題をモデル化し、グラフノードには、ソーシャルネットワークの利用者の個人データや鉄道駅の気象状況など、さまざまな追加情報が含まれている。 0.74
By sampling, all this information is preserved which can lead to prediction models that are easier to interpret by a human expert. サンプリングすることで、すべての情報が保存され、人間の専門家が容易に解釈できる予測モデルにつながります。 0.76
The main contributions of the paper can be summarized as follows: 論文の主な貢献は、次のように要約することができます。 0.68
• Coordinated local neighborhood sampling. •調整されたローカル近所のサンプリング。 0.54
We formally define the problem of coordinated local sampling and present scalable algorithms with well understood theoretical properties. 協調局所サンプリングの問題を公式に定義し、よく理解された理論特性を持つスケーラブルなアルゴリズムを提示する。 0.60
The algorithms scale almost linearly with the graph size and yield samples that preserve the similarity between neighborhood nodes with respect to different objectives. アルゴリズムはグラフサイズとほぼ線形にスケールし、異なる目的に対して近傍ノード間の類似性を保持するサンプルを生成する。 0.83
• Interpretable embeddings. • 解釈可能な埋め込み。 0.66
The main motivation behind coordinated sampling is that it yields embeddings consisting of neighborhood nodes themselves. 協調サンプリングの背後にある主な動機は、近傍ノード自体からなる埋め込みを生成することである。 0.59
We show on real graphs how the information stored in nodes can be used to design interpretable machine learning models using embeddings consisting of coordinated samples. ノードに格納された情報を、協調したサンプルからなる埋め込みを用いて解釈可能な機械学習モデルの設計にどのように使用できるかを実グラフで示す。
訳抜け防止モード: ノードに格納された情報の使い方を実グラフで示します 協調サンプルからなる埋め込みを用いて解釈可能な機械学習モデルを設計する。
0.80
2 Organization of the paper In the next section we present notation and overview of techniques. 2紙の組織化 次の節では、テクニックの表記と概要を紹介する。 0.67
In Section 4 we first describe the overall structure of the proposed approach. 第4節ではまず,提案手法の全体構造について述べる。 0.74
We then present three algorithms for local neighborhood sampling according to different objectives. 次に,局所近傍サンプリングのための3つのアルゴリズムを提案する。 0.66
For each algorithm we also give theoretical results about the computational complexity of the approach and the properties of the returned samples. 各アルゴリズムに対して、アプローチの計算複雑性と返されたサンプルの特性に関する理論的結果を与える。 0.82
We discuss related work in Section 6. 第6節で関連する作業について論じる。 0.55
An experimental evaluation on real graphs is presented in Section 7. 実グラフに関する実験的評価を第7節に示します。 0.79
The paper is concluded in Section 8. 論文は第8節でまとめられている。 0.61
3 Notation and overview of techniques We assume the input is a graph G = (V, E) over n = |V | nodes and m = |E| edges. 3 技術の表記と概要 入力は n = |V | ノードと m = |E| エッジ上のグラフ G = (V, E) であると仮定する。 0.83
The distance d(u, v) between nodes u and v is the minimum number of edges that need to be traversed in order to reach u from v, i.e., the shortest path from u to v. We consider undirected graphs, thus d(u, v) = d(v, u). ノード u と v の間の距離 d(u, v) は、v から u に到達するために必要な最小の辺数、すなわち u から v への最短経路である。
訳抜け防止モード: ノード u と v の間の距離 d(u, v ) は、v から u に到達するために横切る必要のある辺の最小数である。 u から v への最も短い経路は、無向グラフを考えることである。 したがって、d(u , v ) = d(v , u ) である。
0.84
Also, we assume connected graphs, thus d(u, v) < ∞ for all u, v ∈ V . また、連結グラフを仮定すると、すべての u, v ∈ v に対して d(u, v) < ∞ となる。 0.79
These assumptions are however only for the ease of presentation, all algorithms work for directed graphs and graphs with more than one connected component. これらの仮定はプレゼンテーションの容易さのためだけに過ぎず、すべてのアルゴリズムは複数の連結コンポーネントを持つ有向グラフとグラフに対して動作する。 0.71
The k-hop neighbors of node u is the set of nodes Nk(u) = {v ∈ V : d(u, v) ≤ k}. ノード u の k-ホップ近傍は、ノード Nk(u) = {v ∈ V : d(u, v) ≤ k} の集合である。 0.81
The set of neighbors of neighbor (複数形 neighbors) 0.57
2 2 0.85
英語(論文から抽出)日本語訳スコア
node u is denoted as N (u). ノード u は N (u) と表記される。 0.85
We call the subgraph induced by Nk(u) the local k-hop neighborhood of u. u の局所 k-ホップ近傍の Nk(u) によって誘導される部分グラフを呼ぶ。 0.57
The degree of node u in graph G = (V, E) is deg(u) = |{(u, v) ∈ E}|. グラフ G = (V, E) におけるノード u の度合いは deg(u) = |{(u, v) ∈ E}| である。 0.88
An 1 ± ε-approximation of a quantity q is another quantity ˜q such that (1 − ε)q ≤ ˜q ≤ (1 + ε)q. 量 q の 1 ± ε-近似は (1 − ε)q ≤ εq ≤ (1 + ε)q となる別の量 εq である。 0.92
Coordinated sampling Given a universe of elements U , and a a set of sets {Si ⊆ U}, the goal is draw a number of samples from U such that each set Si is represented by a compact summary sketchSi such that sim(sketchSi, sketchSj ) ≈ sim(Si, Sj), i.e., the summaries approximately preserve the similarity between the original sets, for different similarity measures. コーディネートサンプリング(Coordinated sample) U の元の宇宙と集合 {Si > U} の集合が与えられたとき、ゴールは U から、各集合 Si がコンパクトな要約スケッチSi で表されるような多くのサンプルを描くことであり、sim(sketchSi, sketchSj ) > sim(Si, Sj) である。
訳抜け防止モード: 座標サンプリング 要素 U のユニバースと集合 { Si \ U } の集合を与える。 目標は、各セット Si が sim(sketchSi, ) のようなコンパクトな要約スケッチSi で表されるように、U から多数のサンプルを描画することです。 sketchSj ) y sim(Si, Sj ) すなわち、要約は元の集合間の類似性をほぼ維持する。 異なった類似度の測定のため。
0.81
As an example, for a graph G = (V, E) we can have U = V and the sets Si be the neighbors of individual nodes. 例えば、グラフ G = (V, E) に対しては、U = V を持ち、集合 Si は個々のノードの近傍である。
訳抜け防止モード: 例えば、グラフ G = ( V, E ) の場合、U = V を持つことができる。 そして、集合 Si は個々のノードの隣人である。
0.80
Lp sampling for graph nodes The p-norm of vector x ∈ Rn is (cid:107)x(cid:107)p = ((cid:80)n グラフノードのLpサンプリング ベクトル x ∈ Rn の p-ノルムは (cid:107)x(cid:107)p = ((cid:80)n である。 0.75
i )1/p for p ∈ N ∪ {0}. i )1/p は p ∈ n に対して {0} である。 0.69
1 We call Lp sampling a sampling procedure that returns each coordinate xi from vector x with probability |xi|p (cid:107)x(cid:107)p 1 ベクトル x から各座標 xi を確率 |xi|p (cid:107)x(cid:107)p で返すサンプリング手順をlp と呼ぶ。 0.82
i=1 xp . p i=1 xp . p 0.80
Coordinated local graph neighborhood sampling Let f k u be the k-hop frequency vectors of node u u [z] the number of unique paths of length at most k from u to z. 座標付き局所グラフ近傍サンプリング f k u をノード u [z] の k-ホップ周波数ベクトルとし、u から z までの最大 k における長さの唯一の経路の数とする。 0.80
Let su ∈ Nk(u) be the node such that f k returned by an algorithm A as a sample for node u. su ∈ Nk(u) を f k がアルゴリズム A によって返されるようなノードをノード u のサンプルとする。 0.82
We say that A is a coordinated sampling algorithm with respect to a similarity measure sim : V × V → [0, 1] iff a は類似度測度 sim : v × v → [0, 1] iff に関する座標サンプリングアルゴリズムであると言う。 0.73
Pr[su = sv] ∼ sim(f k Pr[su = sv] > sim(f k) 0.74
u , f k v ) for u, v ∈ V u , f k v ) u, v ∈ v に対して 0.88
The objective of the present work is the design of scalable algorithms for coordinated Lp sampling with rigorously understood properties. 本研究の目的は、厳密に理解された特性を持つ協調Lpサンプリングのためのスケーラブルアルゴリズムの設計である。 0.69
We can also phrase the problem in graph algebra terms. グラフ代数の用語で問題を記述することもできる。 0.72
Let A ∈ {0, 1}n×n be the adjacency matrix of the graph. A ∈ {0, 1}n×n をグラフの隣接行列とする。 0.65
The objective is to implement coordinated Lp sampling from each 目的は、それぞれから座標Lpサンプリングを実装することである。 0.63
i=0 Ai without explicitly generating Ai where A0 = I. i=0 Ai は A0 = I となる Ai を明示的に生成しない。 0.63
Note that it holds Mk[u, z] = f k Mk[u, z] = f k となることに注意。 0.87
u [z]. row of Mk =(cid:80)k u [z] です Mk =(cid:80)kの行 0.80
Sketch based coordinated sampling Our algorithms will build upon sketching techniques for sampling from data streams. スケッチベースのコーディネートサンプリング 我々のアルゴリズムは、データストリームからのサンプリングのためのスケッチ技術に基づいて構築する。 0.60
In a nutshell, sketching represents a massive input vector x ∈ Rn with a compact data structure sketchx ∈ Rd, d (cid:28) n, that approximately preserves many properties of the original x. 要するに、スケッチは、コンパクトデータ構造スケッチx ∈ Rd, d (cid:28) n を持つ巨大な入力ベクトル x ∈ Rn を表し、元の x の多くの性質をほぼ保存する。 0.79
We want to sample from sketchx, according to some distribution, such that the returned value is distributed as if we have sampled from x. ある分布によると、xからサンプルしたように返される値が分散されるように、スケッチxからサンプルをサンプリングしたい。 0.79
We will apply sketching to summarize the local k-hop neighborhood frequency vector of each node and this will allow us to design efficient algorithms. 各ノードの局所kホップ近傍周波数ベクトルを要約するためにスケッチを適用し、効率的なアルゴリズムを設計することができます。 0.71
The samples are coordinated by sharing the same random seed across neighborhoods. サンプルは、近所で同じランダムシードを共有することで調整される。 0.65
Denote by su ∈ V the node selected as a sample for a node u ∈ V . su ∈ V は、ノード u ∈ V のサンプルとして選択されたノードを表します。 0.76
Thus, for a node x ∈ Nk(u) ∩ Nk(v) the events x = su and x = sv are not independent. したがって、ノード x ∈ Nk(u) \ Nk(v) に対して、イベント x = su と x = sv は独立ではない。 0.87
If su = x, then it is more likely that we will also select x as a sample for v. This is in contrast to random walks which are independent of each other. su = x であれば、v のサンプルとして x を選択する可能性が高くなります。これは互いに独立しているランダムウォークとは対照的です。 0.76
4 COLOGNE sampling 4 コロンサンプリング 0.65
The general form of our approach is given in Figure 1. このアプローチの一般的な形式は図1に示されています。 0.66
We first initialize a sketch at each node u with the node u itself. まず、各ノードuのスケッチをノードu自身で初期化します。 0.68
Then for k iterations for each node we collect the sketches from its neighbor nodes and aggregate them into a single sketch. その後、各ノードのkイテレーションで隣のノードからスケッチを収集し、それらを1つのスケッチに集約します。
訳抜け防止モード: そして各ノードのk反復に対して、隣のノードからスケッチを収集します。 一つのスケッチにまとめます
0.77
At the end we sample from the sketch at each node. 最後に、各ノードのスケッチからサンプルを作成します。 0.71
In this way we have aggregated the sketches from the k-hop neighborhood Nk(u) for each node u ∈ V . このようにして、各ノード u ∈ V の k-ホップ近傍 Nk(u) からのスケッチをまとめた。 0.76
u such that f k u [v] counts how many times a node v occurs in Nk(u). u において f k u [v] は nk(u) においてノード v の回数を数える。 0.76
For each node u, sketchu is initialized by a sparse {0, 1}-valued vector fu such that fu[v] = 1 iff v = u, i.e., there is exactly one nonzero coordinate. 各ノード u に対して、スケッチは、fu[v] = 1 iff v = u, すなわち、ちょうど1つの非ゼロ座標が存在するようなスパース {0, 1}-値ベクトル fu によって初期化される。 0.78
The aggregation is entrywise vector addition of all neighborhood frequency vectors. アグリゲーションはすべての近傍周波数ベクトルのエントリワイズベクトル付加である。 0.81
The next lemma formally shows that after k iterations the value sketchu[v] is exactly the number of different paths from u to v of length at most k. 次の補題は、k の反復後、値 sketchu[v] は、u から v の長さの異なる経路の数を、ほとんどの k で正確に示している。 0.70
As a simple example assume that the sketch is a frequency vector f k 単純な例として、スケッチは周波数ベクトル f k であると仮定する 0.71
1The 0-norm, counting the number of nonzero coordinates in x, is not a norm in the strict mathematical sense but the 1 x の非零座標の数を数える 0-ノルムは厳密な数学的意味でのノルムではない。
訳抜け防止モード: 1 の 0-ノルムで、x の 0 でない座標の数を数える 厳密な数学的意味での規範ではなく
0.81
notation has become standard. 表記が標準になりました 0.66
3 3 0.85
英語(論文から抽出)日本語訳スコア
COLOGNE Sampling Input: Graph G = (V, E) 1: for each u ∈ V do コロンサンプリング 入力: グラフ G = (V, E) 1: 各 u ∈ V に対して行う。 0.73
Initialize sketchu with node u for each u ∈ V do 各 u ∈ V do に対してノード u でスケッチを初期化する 0.70
2: 3: for i = 1 to k do 4: 5: 2: 3: i = 1 から k への do 4: 5: 0.87
Update sketchu by merging the sketches sketchv for v ∈ N (u) into sketchu sketchv for v ∈ n (u) を sketchu にマージしてsketchuを更新する 0.81
6: for u ∈ V do 7: Return a sample from sketchu 6: u ∈ V do 7: sketchu からサンプルを返します。 0.83
Figure 1: The overall structure of the coordinated local neighborhood sampling approach. 図1:調整された地域のサンプリングアプローチの全体的な構造。 0.81
Lemma 1 Let G be a graph over n nodes. Lemma 1 G を n ノード上のグラフとする。 0.81
Let f k iterations of the COLOGNE algorithm. COLOGNEアルゴリズムのf k反復をしましょう。 0.77
Then f k most k. すると f k most k となる。 0.60
u ∈ Nn be the frequency vector collected at node u after k u [v] is the number of unique walks from u to v of length at u ∈ Nn は k u [v] の後にノード u で収集される周波数ベクトルであり、u から v の長さのユニークウォークの数である。 0.83
Proof: We show that the entry f k u [v] corresponds to the number unique walk of length at most k from u to v by induction on k. For k = 0 the statement is trivial. 証明: 入力 f k u [v] が k 上の帰納によって u から v までのほとんどの k における長さのユニークウォーク数に対応することを示した。 0.68
For k > 1 at each node u we add up the frequency vectors collected at nodes w ∈ Nk(u). 各ノード u の k > 1 に対して、w ∈ Nk(u) で集められた周波数ベクトルを追加する。 0.80
By the induction assumption for k − 1 the frequency vectors f k−1 w [v] record the number of unique walks starting at w and ending at v of length t ≤ k− 1. k − 1 の帰納仮定により、周波数ベクトル f k−1 w[v] は w から始まり、長さ t ≤ k− 1 の v で終わる一意の歩行の数を記録する。 0.83
Using that all neighbors of a node are distinct, by appending u as a new starting node of each of these walks we create a new unique walk from u to v of length t + 1 ≤ k. (cid:3) u(cid:107)1 thus corresponds to a random walk starting at u of length k. Of course, a sketch that stores the entire frequency vectors f k u is not very useful. 各ウォークの新たなスタートノードとしてuを追加することにより、ノードのすべての隣接ノードが別々になる(cid:3) u(cid:107)1は、長さkのuから始まるランダムウォークに対応するため、uから長さt + 1 ≤ kのvへの新たなユニークなウォークを作成する。
訳抜け防止モード: ノードのすべての隣人を使用すること それぞれのウォークの新しい開始ノードとして u を付加することで、u から v までの長さ t の新しいユニークなウォークを作る。 + 1 ≤ k. ( cid:3 ) u(cid:107)1 なので、長さ k の u から始まるランダムウォークに対応する。 周波数ベクトル f k u 全体を格納するスケッチは、あまり役に立たない。
0.71
Even for smaller values of k, we are likely to end up with dense vectors at each node as most real-life networks have a small diameter which would lead to a total space of O(n2). k の値が小さい場合でも、ほとんどの実物ネットワークの直径が小さく、全空間 o(n2) に繋がるので、各ノードの密度の高いベクトルになってしまう可能性が高い。 0.76
Also, sampling an index from each frequency vector does not yield coordinated samples. また、各周波数ベクトルからインデックスをサンプリングしても、調整されたサンプルは得られない。 0.60
Sampling at random a node v from Nk(u) with probability f k 確率 f k を持つ Nk(u) からのノード v をランダムにサンプリングする 0.86
u [v]/(cid:107)f k u [v]/(cid:107)f k 0.85
4.1 Lower bound If we have random access to each node’s neighbors, then a random walk that samples from Nk(u) can be implemented in time O(k). 4.1 下限 各ノードの隣人へのランダムなアクセスがある場合、Nk(u) からのサンプルを時間 O(k) で実装できるランダムウォークが成立する。 0.78
But what about more general distributions? しかし、もっと一般的な分布はどうだろう? 0.70
The following lemma gives a lower bound on the complexity of any algorithm that samples uniformly at random from a local neighborhood, i.e., for a node u each node in Nk(u) has equal chance of being sampled. 次の補題は、Nk(u) 内の各ノードがサンプリングされる確率が等しい、すなわちノード u に対して、局所的な近傍からランダムにサンプリングするアルゴリズムの複雑さに下限を与える。 0.74
Theorem 1 Any algorithm that queries less than deg(u)/2 edges in the local neighborhood of each u ∈ V , cannot obtain a 4/3-approximation of uniform sampling. 理論 1 各 u ∈ V の局所近傍の deg(u)/2 より小さいエッジをクエリするアルゴリズムは、一様サンプリングの 4/3-近似を得ることができない。 0.78
Proof: Consider a graph constructed as follows. 証明: 以下のグラフを考えてみよう。 0.67
Let K1 and K2 be two cliques, each on n nodes. K1 と K2 を n 個のノード上の2つのクリッドとする。 0.57
Choose at random n/2 nodes from both K1 and K2, call these the marked nodes and denote them as M1 and M2. ランダムな n/2 ノードを k1 と k2 から選び、マークされたノードを m1 と m2 と表記する。 0.75
For both K1 and K2 delete all edges between marked nodes and connect each node from M1 to all nodes in M2, thus creating a bipartite clique between marked nodes. K1とK2の両方がマークされたノード間のすべてのエッジを削除し、M1からM2のすべてのノードに各ノードを接続します。 0.80
Marked nodes have 2-hop neighborhood consisting of 2n − 1 nodes while unmarked nodes have a 2-hop neighborhood of 3n/2 − 1 nodes. マーク付きノードは2n − 1ノードからなる2ホップ近傍を持ち、マークなしノードは3n / 2 − 1ノードの2ホップ近傍を有する。 0.66
Consider two nodes uK, uM such that uK ∈ K1\M1, uM ∈ M1 and observe that by querying less than n/2 neighbors for uK and uM we can remain in K1. 2つのノード uK, uM を uK ∈ K1\M1, uM ∈ M1 とし、uK と uM に対して n/2 以下の近傍を問うことで、K1 に残ることができる。 0.74
By never reaching the nodes in K2 we cannot distinguish between the neighborhood sizes of marked and unmarked nodes, and thus we cannot obtain an approximation ratio (cid:3) better than 2n/(3n/2) = 4/3. K2のノードに決して到達しないと、マーク付きノードと未マークノードの近傍サイズを区別できないため、2n/(3n/2) = 4/3よりも近似比(cid:3)が得られない。 0.72
The above result formalizes the intuition that in order to achieve uniform sampling we need to consider the entire neighborhood of each node, or Θ(m) edges for all nodes. 上記の結果は、一様サンプリングを達成するためには各ノードの近傍全体、またはすべてのノードのθ(m)辺を考える必要があるという直観を定式化する。 0.76
Next we show that despite the lower bound we can still design scalable algorithms by computation sharing between nodes. 次に,ノード間の計算共有によってスケーラブルなアルゴリズムを設計できることを示す。 0.67
In fact, this is the key to coordinated sampling. 実際、これは調整されたサンプリングの鍵です。 0.61
4 4 0.85
英語(論文から抽出)日本語訳スコア
4.2 Uniform (L0) sampling 4.2 均一(L0)サンプリング 0.71
We first present a simple algorithm for sampling uniformly at random from the local neighborhood of each node. まず,各ノードの局所近傍からランダムにランダムにサンプリングする簡単なアルゴリズムを提案する。 0.77
The approach builds upon min-wise independent permutations (Broder et al, 2000), a powerful technique for estimating the Jaccard similarity between sets. このアプローチは、集合間のジャカード類似性を推定する強力なテクニックであるmin-wise independent permutations (Broder et al, 2000) に基づいている。 0.74
Assume we are given two sets A ⊆ U and |A∩B| B ⊆ U , where U is a universe of elements, for example all integers. ここで u は元空間であり、例えばすべての整数であるような 2 つの集合 a, u と |a,b| b , u が与えられると仮定する。
訳抜け防止モード: 2つの集合 a, u と |a,b| b, u が与えられると仮定する。 u は要素の宇宙、例えば全ての整数である。
0.78
We want to estimate the fraction |A∪B| . 分数 |a\b| を推定したい。 0.62
|A∩B| Let π : U → U be a random permutation of the elements in U . π : U → U を U の要素のランダムな置換とする。 0.60
With probability |A∪B| the smallest element in A ∪ B with respect to the total order defined by π is contained in A ∩ B and thus the indicator variable denoting whether the smallest elements in π(A) and π(B) are identical yields an unbiased estimator of the αε2 ) independent estimator is an 1 ± ε-approximation of Jaccard similarity J(A, B). したがって、π(A) と π(B) の最小元が αε2 ) の独立推定器の偏りのない推定器がジャカルド類似性 J(A, B) の 1 ± ε-近似であることを示す指標変数は、確率 |A\B| において π で定義される全位数に関して π の最小元が A に含まれ、したがって π(A) と π(B) の最小元が同じであることを示す。
訳抜け防止モード: 確率 |A.B| で π で定義される全位数に関して A . B| の最小元は A . B に含まれる。 したがって π(A ) の最小元が π(A ) のかどうかを示す指標変数は そして π(B ) は αε2 ) の独立推定器の非バイアス推定器が 1 ± ε のジャカード類似性 J(A,) の近似である同じ収率である。 B)。
0.74
The mean of t = O( 1 J(A, B) ≥ α with probability more than 1/2. t = o(1 j(a, b) ≥ α の確率は1/2以上である。 0.81
The success probability can be boosted to any 1− δ by taking the median of log 1/δ independent estimators. 成功確率は、log 1/δ 独立推定子の中央値を取ることによって任意の 1− δ に高めることができる。
訳抜け防止モード: 成功確率は任意の 1− δ に増やすことができる。 log 1 / δ 独立推定子の中央値を取る。
0.72
An algorithm for sampling uniformly from the k-hop neighborhood of node u easily follows. ノード u の k-ホップ近傍から一様にサンプリングするアルゴリズムが簡単に従う。 0.82
We implement a random permutation on the n nodes by generating a random number for each node r : V → {0, 1, . 各ノード r : V → {0, 1, の乱数を生成することにより、n ノードにランダムな置換を実装します。 0.80
. . , (cid:96)−1}. . . , (cid:96)−1。 0.84
For a sufficiently large (cid:96) with high probability r is a bijective function and thus it implements a random permutation2. 十分大きな (cid:96) に対して高い確率 r は単射関数であり、したがってランダムな置換2を実装している。 0.69
For each node u, sketchu is initialized with (r(u), u), i.e., the sketch is just a single (random number, node) pair. 各ノード u に対して、スケッチu は (r(u), u) で初期化される。
訳抜け防止モード: 各ノード u に対して、スケッチは ( r(u , u ) で初期化される。 つまり、スケッチはただ一つの(ランダム数、ノード )ペアです。
0.73
The aggregation after each iteration is storing the pair with the smallest random number from u’s neighbors, sketchu = min(rv,v):v∈N (u) sketchv. 各イテレーションの後のアグリゲーションは、u の隣人、sketchu = min(rv,v):vservletn (u) sketchv からの最小の乱数でペアを格納する。
訳抜け防止モード: 各イテレーションの後の集計は、u の隣人からの最小の乱数でペアを格納しています。 sketchu = min(rv , v):v∈N ( u ) sketchv 。
0.80
After k iterations at each node u we have stored the smallest number form the set {r(v) : v ∈ Nk(u)}, i.e., we have sampled a node from Nk(u) according to the permutation defined by the function r. Clearly, the samples for any two nodes u and w are coordinated as we work with the same permutation on the set Nk(u) ∪ Nk(w). 各ノード u における k 個の反復の後、最小の数を集合 {r(v) : v ∈ Nk(u)} として保存し、すなわち関数 r によって定義される置換に従って Nk(u) からノードをサンプリングした。
訳抜け防止モード: 各ノード u での k 反復の後、集合 { r(v ) : v ∈ Nk(u ) } の最小数を格納した。 すなわち、関数 r.Clearly によって定義された置換に従って Nk(u) からノードをサンプリングした。 2つのノード u と w のサンプルは 私達はセットNk(u )の同じpermutationを使用します。
0.76
The next theorem is a straightforward corollary from the main result on minwise-independent permutations (Broder et al, 2000): Theorem 2 For all nodes u ∈ V , we can sample su ∈ Nk(u) with probability 1/|Nk(u)| in time O(mk) and space O(n). 次の定理は minwise-independent permutation (Broder et al, 2000): Theorem 2 すべてのノード u ∈ V に対して、時間 O(mk) と空間 O(n) において確率 1/|Nk(u)| で su ∈ Nk(u) をサンプリングすることができる。 0.80
For any pair of nodes u, v it holds 任意の一対のノード u, v に対して 0.79
Pr[su = sv] = Pr[su = sv] = 0.85
|Nk(u) ∩ Nk(v)| |Nk(u) ∪ Nk(v)| Nk(u)|Nk(v)||Nk(u)|Nk(v)| 0.83
Note that for constant k we match the lower bound from Theorem 1 and the space usage is O(n) and not O(m) because we need k passes over the edges but they do not need to be stored in memory, but instead can be read from a secondary source or generated on the fly in arbitrary order. 定数 k に対して、我々は Theorem 1 から下界にマッチし、空間使用率は O(n) であり、O(m) ではないことに注意してください。
訳抜け防止モード: 定数 k に対して、定理 1 から下界に一致することに注意。 空間の利用は O(n ) であり、O(m ) ではない。 エッジを渡るにはKパスが必要です 記憶に保存する必要はありません 代わりに、セカンダリソースから読み取るか、任意の順序でフライで生成される。
0.68
be the the adjacency matrix of G. Permute the columns of Mk =(cid:80)k G の隣接行列である。Mk = (cid:80)k の列をパーミュートする 0.64
In terms of linear algebra, the algorithm is an efficient implementation of the following approach: Let A i=0 Ai, and for each row in Mk select the first nonzero coordinate. 線形代数の観点では、アルゴリズムは以下のアプローチの効率的な実装である: A i=0 Ai, and for each row in Mk select the first nonzero coordinate。 0.86
But we avoid the explicit generation of the powers Ai which, as discussed in Section 6.2, could be dense matrices even for small values of i. しかし、第6.2節で述べられているように、i の小さな値であっても密度行列となるような Ai の明示的な生成は避ける。 0.61
Thus, the algorithm implements coordinated L0 sampling from each row of Mk. したがって、アルゴリズムはMkの各行からの座標L0サンプリングを実装している。 0.63
4.3 Lp sampling 4.3 Lpサンプリング 0.73
The solution for uniform sampling is simple and elegant but it does not fully consider the graph structure. 一様サンプリングの解は単純かつエレガントであるが、グラフ構造を完全に考慮していない。 0.76
We are only interested if there is a path between two nodes u and v but, unlike in random walks, not how many paths are there between u and v. We might need a sampling probability that is proportional to the probability that a node is accessed by a random walk but in the same time guarantees that sampling is coordinated, i.e., for a node x ∈ Nk(u) ∩ Nk(v) we want ノードがランダムウォークによってアクセスされる確率に比例するサンプリング確率を必要とするかもしれないが、同時にサンプリングが調整されることが保証される。つまり、ノード x ∈ Nk(u) \ Nk(v) が欲しい。
訳抜け防止モード: 2つのノード u と v の間にパスがある場合にのみ興味があります。 しかし、ランダムウォークとは異なり、uの間にどれだけのパスがあるかは ノードがランダムウォークによってアクセスされる確率に比例するサンプリング確率が必要な場合があります。 しかし同時に、サンプリングが調整されることを保証します。 ノード x ∈ Nk(u ) は Nk(v ) です。
0.75
Pr[su = x and sv = x] (cid:29) Pr[su = x] Pr[sv = x] Pr[su = x と sv = x] (cid:29) Pr[su = x] Pr[sv = x] 0.91
Let us first present an approach to Lp sampling from data streams for p ∈ (0, 2] (Jowhari et al, 2011; Cormode and Jowhari, 2019). まず、p ∈ (0, 2] (Jowhari et al, 2011; Cormode and Jowhari, 2019) のデータストリームからの Lp サンプリングのアプローチを紹介します。 0.77
Let S be a data stream of pairs i, wi where i is the item and wi ∈ R the weight update for item i, for i ∈ [n]. S を i がアイテムであるようなペア i, wi と、i ∈ [n] の項目 i に対するウェイト更新 wi ∈ R のデータストリームとする。 0.77
The objective is to return each item i with probability roughly 目的は、確率的に各項目 i を返すことです。 0.68
2For example, for (cid:96) = n2/δ with probability at least 1 − δ the function is bijective. 2例えば (cid:96) = n2/δ の場合、確率は少なくとも 1 − δ である。 0.82
5 5 0.85
英語(論文から抽出)日本語訳スコア
p, where f [i] =(cid:80) p, ここで f[i] =(cid:80) 0.87
|f [i]|p/(cid:107)f(cid:107 )p (i,wi)∈S wi. f [i]|p/(cid:107)f(cid:107 )p(i,wi)∈S wi。 0.87
(Note that items are supposed to occur multiple times in the stream.) (アイテムはストリーム内で複数回発生することになっていることに注意) 0.77
The problem is trivial if we can afford to store the entire frequency vector f but for larger n this can be prohibitively expensive. 周波数ベクトル f 全体を格納できるなら問題は自明だが、より大きな n の場合、これは制限的に高価である。 0.79
The idea is to reweight each item by scaling it by a random number 1/r1/p for a uniformly sampled ri ∈ (0, 1]. このアイデアは、一様にサンプリングされた ri ∈ (0, 1] に対して、各アイテムを乱数 1/r1/p でスケーリングすることで、各アイテムを再重み付けする。 0.60
Let zi = f [i]/r1/p be the reweighted weight of item i. zi = f [i]/r1/p をアイテム i の再重み付け重量とする。 0.85
The crucial observation is that i i 重要な観察は 私は 私は 0.56
Pr[zi ≥ (cid:107)f(cid:107)p ] = Pr[ri ≤ f [i]p/(cid:107)f(cid:107 )p Pr[zi (cid:107)f(cid:107)p ] = Pr[ri ≤ f [i]p/(cid:107)f(cid:107 )p 0.93
p] = f [i]p (cid:107)f(cid:107)p p] = f [i]p (cid:107)f(cid:107)p 0.88
p Thus, we need to detect a reweighted item whose weight exceeds (cid:107)f(cid:107)p . The solution in (Jowhari et al, 2011; Cormode and Jowhari, 2019) is to show that with constant probability there exists a unique item whose weight exceeds (cid:107)f(cid:107)p and the total weight of all other items is bounded. p したがって、重量が (cid:107)f(cid:107)p を超える再加重アイテムを検出する必要がある。 (Jowhari et al, 2011; Cormode and Jowhari, 2019) の解は、一定の確率で重量が (cid:107)f(cid:107)p を超えるユニークなアイテムが存在し、他の全ての項目の総重量が有界であることを示すことである。 0.80
Thus, if we know the value of (cid:107)f(cid:107)p , a space-efficient solution is to keep a sketch data structure form which we can detect the heavy hitter that will be the sampled item. したがって、(cid:107)f(cid:107)p の値を知っている場合、空間効率のよい解決策はスケッチデータ構造を保ち、サンプル項目となる重いヒットターを検出することである。 0.78
Estimating the norm of a frequency vector is a fundamental problem with known solutions (Alon et al, 1999; Charikar et al, 2004), therefore the approach yields a space-efficient solution to Lp sampling from data streams. 周波数ベクトルのノルムを推定することは既知の解(Alon et al, 1999; Charikar et al, 2004)の基本的な問題であるため、この手法はデータストリームからのLpサンプリングに対する空間効率のよい解をもたらす。 0.78
O((cid:80)k O((cid:80)k 0.92
We will follow the above approach but there are several challenges we need to address when applying it to local neighborhood graph sampling. 上記のアプローチに従いますが、ローカルのグラフサンプリングに適用する際に対処すべき課題はいくつかあります。 0.66
The main difference is that we cannot afford to explicitly generate all entries in the frequency vector of the local neighborhood as this would result in time complexity of i=0 Ai), A being the graph adjacency matrix. 主な違いは、これはi=0 Aiの時間の複雑さをもたらすので、ローカル近所の周波数ベクトル内のすべてのエントリを明示的に生成する余裕がないということです)、Aはグラフの隣接行列です。 0.73
Also, estimating the norm of the frequency vectors has to u , the k-hop frequency vectors また、周波数ベクトルのノルムを推定するには、u、kホップ周波数ベクトルが必要です。 0.67
be done in a new way because we cannot explicitly generate all updates to f k of node u. ノードuのf kに対するすべての更新を明示的に生成できないので、新しい方法で実行してください。 0.74
Our solution is based on the idea of mergeable sketches (Agarwal et al, 2013). 私たちのソリューションはマージ可能なスケッチ(agarwal et al, 2013)のアイデアに基づいています。 0.71
Following the COLOGNE sampling template from Figure 1, we iteratively generate sketches at each node. 図1からケルンサンプリングテンプレートに従い、各ノードで反復的にスケッチを生成します。 0.73
The sketch collected in the i-th iteration will summarize the i-hop neighborhood of each node. i-thイテレーションで収集されたスケッチは、各ノードのi-hop近傍を要約する。 0.58
In (Jowhari et al, 2011) the authors use the Count-Sketch data structure (Charikar et al, 2004). Jowhari et al, 2011)では、著者はCount-Sketchデータ構造(Charikar et al, 2004)を使用します。 0.84
This would fit perfectly into the COLOGNE framework as CountSketch is a linear projections of the data. これは、CountSketchがデータの線形プロジェクションであるため、COLOGNEフレームワークに完全に適合します。 0.73
Namely, an input vector x ∈ Rn is projected onto an m-dimensional subspace, m (cid:28) n, as P x for P ∈ Rm×n where the projection matrix P is implicitly defined using advanced hash functions. すなわち、入力ベクトル x ∈ Rn は、高度なハッシュ関数を用いて射影行列 P を暗黙的に定義した P ∈ Rm×n の P x として m-次元部分空間 m (cid:28) n に投影される。 0.82
This means that for two vectors x and y we have sketch(x + y) = sketch(x) + sketch(y) and we can iteratively sketch the k-hop frequency vector from the local neighborhood of each node. つまり、2つのベクトル x と y に対してsketch(x + y) = sketch(x) + sketch(y) があり、各ノードの局所近傍から k-ホップ周波数ベクトルを反復的にスケッチすることができる。 0.85
The result will be identical to first computing the frequency vector and then sketching it. 結果は、最初に周波数ベクトルを計算し、それからスケッチしたものと同じです。 0.62
Unfortunately, we cannot use Count-Sketch because we cannot efficiently retrieve the heavy hitter from the sketch. 残念ながら、スケッチから重いヒットターを効率的に回収できないため、Count-Sketchは使用できません。 0.63
In the setting in (Jowhari et al, 2011) a single vector is being updated in a streaming fashion. 設定(Jowhari et al, 2011)では、単一のベクターがストリーミング方式で更新されています。 0.72
Thus after preprocessing the stream we can afford to query the sketch for each vector index i ∈ [n] as this wouldn’t increase the asymptotic complexity of the algorithm. したがって、ストリームを前処理した後、アルゴリズムの漸近的な複雑さを増大させないため、各ベクトルインデックス i ∈ [n] のスケッチを問い合わせる余裕がある。 0.76
But in our case this would mean we need to know all nodes in the local neighborhood of each node. しかし、私たちの場合、これは各ノードのローカル近傍のすべてのノードを知る必要があることを意味します。 0.76
And even if we knew those nodes, we would need そして、たとえそのノードを知っていても、必要なのです。 0.56
O((cid:80)k O((cid:80)k 0.92
i=0 nnz(Ai)) queries in total which is likely to be of order O(n2). i=0 nnz(Ai)) のクエリは合計で O(n2) の順序である可能性が高い。 0.71
Fortunately, the solution lies in applying another kind of summarization algorithms for frequent items mining, the so called counter based algorithms (Karp et al, 2003; Metwally et al, 2005). 幸いなことに、このソリューションは、頻繁なアイテムマイニングのための別の種類の要約アルゴリズム、いわゆるカウンターベースアルゴリズム(Karp et al, 2003; Metwally et al, 2005)を適用することにあります。 0.69
In this family of algorithms the sketch consists of an explicitly maintained list of frequent items candidates. このアルゴリズム群では、スケッチは頻繁なアイテム候補のリストから成り立っている。 0.58
For a sufficiently large yet compact sketch the heavy hitter is guaranteed to be detected. 十分に大きくてコンパクトなスケッチでは、重いヒットターを検出することが保証される。 0.66
Next we obtain theoretical results for the approach. 次に、このアプローチの理論的結果を得る。 0.59
L1 sampling u at node u with a randomly weighted vector wk L1サンプリング ランダムに重み付けされたベクトル wk を持つノード u の u 0.75
In a nutshell, the algorithm works as follows. 要するに、アルゴリズムは次のように機能します。 0.73
We adapt the approach from Lemma 1 but replace the frequency vector f k u [v]/rv. Lemma 1 からのアプローチを適応させるが、周波数ベクトル f k u [v]/rv を置き換える。 0.78
For each node u we generate a random number ru ∈ (0, 1], initialize wk u[v] = 0 for all v (cid:54)= u. where ⊕ denotes We iterate over the neighbor nodes and update the vector wk entrywise vector addition. 各ノード u に対して、ランダム数 ru ∈ (0, 1] を生成し、すべての v (cid:54) = u に対して wk u[v] = 0 を初期化する。
訳抜け防止モード: 各ノード u に対して、乱数 ru ∈ (0, 1 ] を生成する。 すべての v ( cid:54) = u に対して wk u[v ] = 0 を初期化する。 ベクトルwkエントリワイドベクトル加算を更新する。
0.71
We sample a node v iff wu[v] ≥ t for some t. Instead of explicitly maintaining the reweighted frequency wk u, we keep a sketch from which we detect a heavy hitter that is then returned as a sample su. ある t に対してノード v iff wu[v] ≥ t をサンプリングする。 再重み付けされた周波数 wk u を明示的に維持する代わりに、我々は重いヒットを検知し、サンプル su として返されるスケッチを保持する。 0.80
u ⊕(cid:80) u (複数形 us) 0.25
v u such that wk v ウッ あんな wk 0.58
u[u] = 1/ru and set wk u = wk−1 u[u] = 1/ru と set wk u = wk−1 0.89
u[v] = f k v∈N (u) wk−1 u[v] = f k v∈N (u) wk−1 0.90
6 6 0.85
英語(論文から抽出)日本語訳スコア
Let us provide some intuition before formally showing that the above approach yields coordinated sampling and preserves the connectivity properties of each node’s neighborhood. 上述のアプローチが各ノードの近傍の接続特性を協調的に収集し保存することを示す前に、直観を与える。 0.71
First note that each node v ∈ Nk(u) has a chance for being selected as u’s sample, i.e., su = v, because the numbers rv are chosen at random. まず、各ノード v ∈ Nk(u) は u のサンプル、すなわち su = v として選択される可能性があることに注意してください。
訳抜け防止モード: まず、各ノード v ∈ nk(u ) が確率を持つことに注意する。 u のサンプルとして選択される、すなわち su = v である。 rvはランダムに選択されるからです
0.84
Second, if there are many paths from u to v then Pr[su = v] is larger as fu[v] is larger, in the same way as in random walks. 第二に、u から v への経路が多ければ、pr[su = v] は、ランダムウォークと同様に、fu[v] が大きいほど大きい。 0.68
And third, sampling is coordinated as for each v ∈ Nk(u) ∩ Nk(w), v has a better chance to be the sample for u and w, su = sw = v, if rv is small which is in contrast to independent random walks. そして第三に、サンプリングは各 v ∈ Nk(u) が Nk(w) に対して調整され、v は u と w, su = sw = v のサンプルになる可能性が高く、rv が小さい場合、独立したランダムウォークとは対照的である。 0.80
What remains to consider is the computational complexity. 考慮すべきことは計算の複雑さです。 0.71
As discussed, explicitly storing and updating the weighted vectors wk u for each node u is not feasible because even for small k this might lead to memory usage of O(n2). 前述のように、各ノード u に対して重み付きベクトル wk u を明示的に保存・更新することは、小さな k であっても o(n2) のメモリ使用につながる可能性があるため、実現不可能である。 0.62
Instead, we will efficiently detect a node x from a sketch of u’s k-hop weighted neighborhood u[x] ≥ t. In this case the sketch will be realized using a frequent frequency vector wk items mining algorithm such as (Karp et al, 2003) which detects heavy hitters in streams of weighted items without explicitly storing all items. その代わりに、u の k-ホップ重み付き近傍 u[x] ≥ t のスケッチからノード x を効率的に検出する。この場合、このスケッチは、すべての項目を明示的に保存することなく重み付きアイテムのストリーム内の重いヒットターを検出する (Karp et al, 2003) のような頻繁な周波数ベクトル wk アイテムマイニングアルゴリズムを用いて実現される。 0.78
i=0 Ai · R where R ∈ Rn×n is a diagonal matrix with diagonal entries randomly selected from (0, 1]. i=0 Ai · R ここで R ∈ Rn×n は (0, 1] からランダムに選択された対角行列である。 0.85
Then from the i-th row we return as sample the index j for which it holds arg maxj Wi,j, i.e., the index with the maximum value in i=0 Ai is multiplied by the same その後、i行目からサンプルとして返されるインデックスjはarg maxj Wi,j、すなわちi=0 Aiの最大値を持つインデックスを同じで乗算する。 0.74
We can phrase the algorithm again in terms of the adjacency matrix A of G. Let W =(cid:80)k the row. アルゴリズムを G の隣接行列 A の言葉で言い換えることができる。 W = (cid:80)k を行とする。 0.69
Sampling in this way is coordinated because the j-th column of(cid:80)k このようなサンプリングは、(cid:80)k の j 番目の列によって調整される 0.55
u for which it holds wk UはWKを保持します 0.32
random value rj. Theorem 3 Let G be a graph over n nodes and m edges, and let f k neighborhood of node u ∈ V . ランダム値 rj。 定理3 G を n 個のノードと m 個のエッジ上のグラフとし、fk をノード u ∈ V の近傍とする。 0.74
For all u ∈ V , we can sample a node su ∈ Nk(u) with probability f k u [su] (cid:107)f k u(cid:107)1 O(mk log n) and space O(n log n). すべての u ∈ V に対して、確率 f k u [su] (cid:107)f k u(cid:107)1 O(mk log n) と空間 O(n log n) を持つノード su ∈ Nk(u) をサンプリングすることができる。 0.90
For each pair of nodes u, v ∈ V それぞれのノード u, v ∈ V に対して 0.84
u be the frequency vector of the k-hop in time u は k-hop の周波数ベクトルです。 0.81
Pr[su = sv] ∼ (cid:88) Pr[su = sv] > (cid:88) 0.94
min( min (複数形 mins) 0.42
f k u [x] (cid:107)f k u(cid:107)1 f k u [x] (cid:107)f k u(cid:107)1 0.95
, f k v [x] (cid:107)f k v (cid:107)1 , f k v [x] (cid:107)f k v (cid:107)1 0.90
) x∈V Proof: We will show that with constant probability there exists exactly one node x ∈ Nk(u) that satisfies the sampling condition for node u, i.e., wk u is the reweighted frequency vector u . ) x∈V 証明: 一定の確率で、ノード u のサンプリング条件を満たすちょうど1つのノード x ∈ Nk(u) が存在し、すなわち、wk u は再重み付き周波数ベクトル u であることを示す。 0.74
Denote this event by E1. このイベントをE1で示します。 0.67
Consider a fixed node x ∈ Nk(u). 固定ノード x ∈ Nk(u) を考える。 0.71
First, node x is reweighted by rx ∼ U (0, 1), f k therefore the probability that node x satisfies the sampling condition is まず、ノード x は rx > U (0, 1) で再重み付けされるので、ノード x がサンプリング条件を満たす確率は f k である。 0.82
u[x] ≥ t for t = (cid:107)f k u[x] ≥ t for t = (cid:107)f k 0.96
u(cid:107)1 where wk u(cid:107)1 wk 0.73
Pr[f k u [x]/rx ≥ t] = Pr[f k] u[x]/rx ≥ t] = 0.88
f k u [x] (cid:107)f k u(cid:107)1 f k u [x] (cid:107)f k u(cid:107)1 0.95
For fixed x ∈ Nk(u), let E u for all other nodes v (cid:54)= x it holds wk 固定 x ∈ Nk(u) に対して、他のすべてのノード v (cid:54)= x に対して E u を wk とする。 0.77
x be the event that x is the only node that satisfies the sampling condition and x は、サンプリング条件を満たす唯一のノードであるイベントです。 0.61
u[x] ≤ t/2. u[x] ≤ t/2。 0.91
We lower bound the probability for E u (cid:89) E u (cid:89) の確率を低くします。 0.74
(1 − 2f k u [v] t (1 − 2f k u [v] t 0.93
f k u [x] u(cid:107)1 (cid:107)f k f k u [x] u(cid:107)1 (cid:107)f k 0.95
α(1 − 2/t)f k α(1 − 2/t)f k 0.96
u [v] ≥ (for α ∈ (0, 1]) u [v] (α ∈ (0, 1] の場合) 0.77
Pr[E u x ] = Pr[E u] x ] = 0.88
v∈Nk(u),v(cid:54)=x v∈Nk(u),v(cid:54)=x 0.86
(cid:89) f k u [x] (cid:107)f k u(cid:107)1 (cid:89) f k u [x] (cid:107)f k u(cid:107)1 0.87
v∈Nk(u),v(cid:54)=x v∈Nk(u),v(cid:54)=x 0.86
x as follows: xは以下の通りです。 0.61
) ≥ f k u [x] (cid:107)f k u(cid:107)1 ) ≥ f k u [x] (cid:107)f k u(cid:107)1 0.90
α(1 − 2/t)(cid:107)f k α(1 − 2/t)(cid:107)f k 0.88
u(cid:107)1 = u(cid:107)1 = 0.92
f k u [x] (cid:107)f k u(cid:107)1 f k u [x] (cid:107)f k u(cid:107)1 0.95
e−2(cid:107)f k e−2(cid:107)f k 0.75
u(cid:107)1/t = u(cid:107)1/t = 0.75
e−2 f k u [x] (cid:107)f k u(cid:107)1 e−2 f k u [x] (cid:107)f k u(cid:107)1 0.88
The first inequality follows by observing that (1− k/n)n → e−k and (1− 1/n)kn → e−k for large n, and since (cid:80) (cid:80) both 1 − k/n and 1 − 1/n are in (0,1), for any fixed n and k < n there must exist a constant α ∈ (0, 1) such v∈V wv for a ∈ (0, 1) that 1 − k/n ≥ α(1 − 1/n)k. The second inequality holds because a 1 − k/n)n → e−k と (1 − 1/n)kn → e−k が大きな n に対して成り立つこと、そして (cid:80) (cid:80) (cid:80) は 1 − k/n と 1 − 1/n の両方が (0,1) 内にあるので、任意の固定 n と k < n に対して、ある定数 α ∈ (0, 1) が存在しなければならない。 0.80
v∈V :v(cid:54)=x wv > a v∈V :v(cid:54)=x wv > a 0.81
7 7 0.85
英語(論文から抽出)日本語訳スコア
and wv > 0. For E1 we observe that the events E u Pr[E1] = およびwv>0。 E1 の場合、イベント E u Pr[E1] = が観測される。 0.73
(cid:88) x , x ∈ Nk(u) are pairwise disjoint. (cid:88) x , x ∈ Nk(u) は対同型である。 0.80
f k u [x] e2(cid:107)f k u(cid:107)1 f k u [x] e2(cid:107)f k u(cid:107)1 0.92
x ] ≥ (cid:88) x ] ≥ (cid:88) 0.92
Pr[E u x∈Nk(u) Pr[E u] x∈Nk(u) 0.88
x∈Nk(u) = Ω(1) x∈Nk(u) = Ω(1) 0.77
(cid:90) n2 (cid:90)n2 0.70
u(cid:107)1. u(cid:107)1。 0.82
With Next we show how to efficiently detect the unique element x for which it holds f k probability at least 1 − 1/n it holds rx ∈ [1/n2, 1] for all x ∈ V . 次に、f k 確率を少なくとも 1 − 1/n で保持し、すべての x ∈ V に対して rx ∈ [1/n2, 1] を保持する一意の要素 x を効率的に検出する方法を示します。 0.74
We obtain for the expected value of u[x] = f k wk u[x] = f k wk の期待値を取得します。 0.73
u [x]/rx ≥ (cid:107)f k u [x]/rx ≥ (cid:107)f k 0.99
u [x]/rx: 1 t u [x]/rx: 1t 0.78
1 u [x] log n) 1 u [x] log n) 0.85
dt) = O(f k dt) = O(f k) 0.93
u [x]/rx] = O(f k u(cid:107)1] = O((cid:107)f k u [x]/rx] = O(f k u(cid:107)1] = O((cid:107)f k 0.98
E[f k u [x] u(cid:107) log n). E[f k u [x] u(cid:107) log n) 0.82
Since the random numbers rx are independent by By linearity of expectation E[(cid:107)wk u(cid:107)1 can be u(cid:107)1 = O((cid:107)f k Hoeffdings’s inequality we obtain that (cid:107)wk u(cid:107)1 computed exactly at each node. 確率数 rx は期待の線型性 e[(cid:107)wk u(cid:107)1 が u(cid:107)1 = o((cid:107)f k hoeffdings の不等式であることから、各ノードで正確に計算された (cid:107)wk u(cid:107)1 が得られる。 0.80
Thus, we have shown that there exists a unique node x with weight (cid:107)f k and the total weight of the nodes in Nk(u) is bounded by O((cid:107)f k u(cid:107)1 log n). したがって、重量(cid:107)f k を持つ一意のノード x が存在し、Nk(u) のノードの総重量は O((cid:107)f k u(cid:107)1 log n) で有界であることを示した。 0.81
Using a deterministic frequent items mining algorithm like Frequent (Karp et al, 2003) we can detect this unique heavy hitter using space O(log n). Frequent (Karp et al, 2003) のような決定論的頻繁なアイテムマイニングアルゴリズムを用いて、空間 O(log n) を用いてこのユニークな重いヒッタを検出することができる。 0.75
Since for all other nodes v (cid:54)= x it holds wk u(cid:107)1/2, by the main result from (Karp et al, 2003) it follows that for a summary size of > 2 log n the heavy hitter will be the only node whose u(cid:107)1/2. 他のすべてのノード v (cid:54)= x に対して wk u(cid:107)1/2 を保持するので、(Karp et al, 2003) からの主な結果によって、< 2 log n の要約サイズは u(cid:107)1/2 を持つ唯一のノードとなる。 0.86
Note that the summaries generated by Frequent are weight in the summary will be at least (cid:107)f k mergeable (Agarwal et al, 2013), and can be merged in time proportional to the number of elements stored in the summary. Frequentによって生成される要約は、要約において少なくとも (cid:107)f k mergeable (Agarwal et al, 2013) であり、要約に格納されている要素の数に比例する時間でマージ可能であることに注意されたい。 0.68
In each iteration we need to perform exactly m such summary merges, thus each iteration over all nodes takes O(m log n) and needs space O(n log n) To complete the proof consider the probability that x ∈ Nk(u) ∩ Nk(v) is sampled for both nodes u and v, i.e., su = sv = x. 各イテレーションでは、そのような要約マージを正確に m を実行する必要があるので、すべてのノード上の各イテレーションは O(m log n) を取り、空間 O(n log n) を完了するには、x ∈ Nk(u) ・ Nk(v) が両方のノード u と v に対してサンプリングされる確率を考慮する。 0.87
As shown above, the probability v ∈ Nk(u) are not sampled for all v (cid:54)= x can be lower bounded by Ω(1). 上記のように、確率 v ∈ Nk(u) はすべての v (cid:54) = x に対して Ω(1) で下界することができない。 0.77
Observe that x = su if rx ≤ f k rx ≤ f k のとき x = su を観測する 0.89
u(cid:107) log n) almost surely. u(cid:107) log n) ほぼ確実に。 0.85
Note that (cid:107)wk 注意: (cid:107)wk 0.77
u[x] ≤ (cid:107)f k u[x] ≤ (cid:107)f k 1.00
u [x]/(cid:107)f k u [x]/(cid:107)f k 0.85
Θ(1) Pr[rx ≤ f k θ(1) pr[rx ≤ f k である。 0.78
u [x]/(cid:107)f k u [x]/(cid:107)f k 0.85
Pr[x = su ∧ x = sv] = Pr[E u Pr[x = su > x = sv] = Pr[E u] 0.77
u(cid:107)1, thus we have x ∧ E v x ] = v (cid:107)1] ∼ v [x]/(cid:107)f k u(cid:107)1 ∧ rx ≤ f k f k f k u [x] v [x] (cid:107)f k (cid:107)f k u(cid:107)1 v (cid:107)1 u(cid:107)1 なので、x の E v x ] = v (cid:107)1] の v [x]/(cid:107)f k u(cid:107)1 の rx ≤ f k f k k u [x] v [x] (cid:107)f k (cid:107)f k u(cid:107)1 v (cid:107)1v (cid:107) 0.89
min( min (複数形 mins) 0.42
) , x events are disjoint for x ∈ Nk(u). ) , x のイベントは x ∈ Nk(u) に対して不一致である。 0.80
Also, nodes x /∈ Nk(u) ∩ Nk(v) contribute 0 to the similarity as The E u they are not reachable by at least one of u or v. Thus, summing over x ∈ Nk(u)∩ Nk(v) completes the proof. また、ノード x /ftp nk(u) である nk(v) は、e u が u または v の少なくとも一方で到達できないため、x ∈ nk(u) 上の和は証明を完結させる。
訳抜け防止モード: また、ノード x /∈ Nk(u ) \ Nk(v ) は、U または v の少なくとも 1 つでは到達できない E u の類似性に 0 に貢献する。 x ∈ Nk(u)\ Nk(v) 上の和 )は証明を完了します。
0.79
(cid:3) L2 sampling (cid:3) L2サンプリング 0.79
u [v] in advance, v ∈ Nk(u), but we need to know the values f k u[v] を事前に v ∈ Nk(u) とするが、値 f k を知る必要がある。 0.84
The only obstacle that prevents us from applying the L1 sampling algorithm to the L2 case is that we u(cid:107)1 without knowing cannot compute exactly the 2-norm of the weighted vector (cid:107)wk the values f k u [v]2 in order to compute the 2-norm of the weighted frequency vector. L2 の場合への L1 サンプリングアルゴリズムの適用を妨げる唯一の障害は、重み付きベクトルの 2-ノルム (cid:107)wk の値 f k u [v]2 を正確に計算することができず、重み付き周波数ベクトルの 2-ノルムを計算することである。 0.78
However, we can efficiently approximate the 2-norm of a vector revealed in a streaming fashion, this is a fundamental algorithmic problem for which algorithms with optimal computational complexity have been designed (Alon et al, 1999; Charikar et al, 2004). しかし、ストリーミング方式で明らかにされたベクトルの2ノルムを効率的に近似することは可能であり、これは最適な計算複雑性を持つアルゴリズムが設計された基本的なアルゴリズム問題である(Alon et al, 1999; Charikar et al, 2004)。 0.80
These algorithms can be adapted to the local graph neighborhood setting which yields the following result. これらのアルゴリズムは、以下の結果をもたらす局所グラフ近傍の設定に適応することができる。 0.78
u(cid:107)2. u(cid:107)2。 0.87
We can compute (cid:107)wk 計算できる(cid:107)wk 0.75
Theorem 4 Let G be a graph over n nodes and m edges, and let f k u be the frequency vector of the k-hop neighborhood of node u ∈ V . 定理4 G を n 個のノードと m 個のエッジ上のグラフとし、f k u をノード u ∈ V の k-ホップ近傍の周波数ベクトルとする。 0.80
For all u ∈ V , we can sample a node su ∈ Nk(u) with probability (1 ± ε) f k u [su]2 (cid:107)f k u(cid:107)2 in time O(mk(1/ε2 + log n)) and space O(n(1/ε2 + log n)), for a user-defined ε ∈ (0, 1). すべての u ∈ V に対して、ユーザ定義の ε ∈ (0, 1) に対して、確率 (1 ± ε) f k u [su]2 (cid:107)f k u(cid:107)2 のノード su ∈ Nk(u) を時間 O(mk(1/ε2 + log n)) および空間 O(n(1/ε2 + log n)) でサンプリングすることができる。 0.91
For each pair of nodes u, v ∈ V それぞれのノード u, v ∈ V に対して 0.84
2 Pr[su = sv] ∼ (1 ± ε) 2 Pr[su = sv] ^ (1 ± ε) 0.83
min( min (複数形 mins) 0.42
f k u [x]2 u(cid:107)2 (cid:107)f k f k u [x]2 u(cid:107)2 (cid:107)f k 0.96
2 , f k v [x]2 v (cid:107)2 (cid:107)f k 2 , f k v [x]2 v (cid:107)2 (cid:107)f k 0.89
2 ) (cid:88) 2 ) (cid:88) 0.83
x∈V 8 x∈V 8 0.72
英語(論文から抽出)日本語訳スコア
Proof: The same proof as for L1 sampling holds except for computing exactly the norm (cid:107)wk u(cid:107)2. 証明: L1サンプリングと同じ証明は、標準 (cid:107)wk u(cid:107)2 の計算を除いて成り立つ。 0.77
Instead we will estimate it using CountSketch (Charikar et al, 2004). 代わりにCountSketch(Charikar et al, 2004)を使って見積もります。 0.72
This is a linear data structure that maintains an array with counters. これは、カウンタを持つ配列を保持する線形データ構造である。 0.83
The critical property of linear sketches is that for each node it holds 線形スケッチの重要な特性は、各ノードが保持するということです。 0.72
(cid:88) (cid:88) (cid:88) (cid:88) 0.78
sketch( sketch (複数形 sketchs) 0.40
fv) = sketch(fv) fv) = sketch(fv) 0.85
v∈Nk(u) v∈Nk(u) v∈Nk(u) v∈Nk(u) 0.84
Using a sketch with O(1/ε2) counters we obtain a 1± ε approximation of (cid:107)wk u(cid:107)2 for a user-defined ε ∈ (0, 1). O(1/ε2)カウンタを持つスケッチを用いて、ユーザ定義ε ∈ (0, 1) に対して (cid:107)wk u(cid:107)2 の 1± ε近似を得る。 0.79
Thus, we can recover the heavy hitters in the local neighborhood of each node using the approach from the 1±ε ∈ [1−c·ε, 1+c·ε], proof of Theorem 3. したがって、1±ε ∈ [1−c·ε, 1+c·ε] からのアプローチを用いて各ノードの局所近傍の重ヒットターを回復することができる。 0.65
Observing that for any ε ∈ (0, 1) there exists a constant c such that (cid:3) we obtain the stated bounds on the sampling probability. 任意の ε ∈ (0, 1) に対して (cid:3) がサンプリング確率の有界であるような定数 c が存在することを観測する。 0.86
1 4.4 Discussion Let us provide some intuition for the similarity measures approximated by the samples in Theorem 3 and Theorem 4. 1 4.4 議論 Theorem 3 と Theorem 4 のサンプルによって近似された類似度尺度の直観について述べる。 0.76
In L0 sampling we treat all nodes in the local neighborhood equally, while in L1 sampling the sampling probability is proportional to the probability that we reach a local neighbor by a random walk. L0サンプリングでは、局所近傍の全てのノードを等しく扱う一方、L1サンプリングでは、サンプリング確率は、ランダムウォークによって局所近傍に到達する確率に比例する。 0.75
L2 sampling is biased towards high-degree local neighbors, i.e., if a node is reachable by many paths in the local neighborhood then it is even more likely to be sampled. l2サンプリングは高次局所近傍に偏りがあり、例えば、ノードが局所近傍の多くの経路に到達可能であれば、サンプリングされる可能性がさらに高い。 0.72
The similarity function approximated by L0 sampling is the Jaccard similarity between node sets in the local neighborhood. L0サンプリングによって近似される類似度関数は、局所近傍のノードセット間のJaccard類似度である。 0.66
But the similarity for L1 and L2 sampling is less intuitive. しかし、L1とL2の類似性は直感的ではない。 0.58
Consider two vectors x, y ∈ Rn. 2つのベクトル x, y ∈ Rn を考える。 0.82
It holds min( 保持する min (複数形 mins) 0.46
x[i]2 (cid:107)x(cid:107)2 x[i]2 (cid:107)x(cid:107)2 0.92
2 , y[i]2 (cid:107)y|2 2 , y[i]2 (cid:107)y|2 0.85
2 x[i]2 2(cid:107)x(cid:107) 2 2 x[i]2 2(cid:107)x(cid:107) 2 0.89
2 + y[i]2 2(cid:107)y|2 2 + y[i]2 (cid:107)y|2 0.87
2 = 1 ) ≤ n(cid:88) 2 = 1 ≤ n(cid:88) 0.88
i=1 n(cid:88) i=1 n(cid:88) 0.71
i=1 have identical frequency vectors the similarity is 1. i=1 同じ周波数ベクトルを持ち、類似度は1である。 0.63
In particular, if two nodes share no nodes in their k-hop neighborhoods the similarity is 0 and if they Also, for a ≥ 0, b ≥ 0 it holds min(a2, b2) ≤ ab, thus we have that 特に、2つのノードがk-ホップ近傍でノードを共有していない場合、類似性は 0 であり、a ≥ 0 に対して b ≥ 0 であれば min(a2, b2) ≤ ab となる。 0.84
min( min (複数形 mins) 0.42
x[i]2 (cid:107)x(cid:107)2 x[i]2 (cid:107)x(cid:107)2 0.92
2 , y[i]2 (cid:107)y|2 2 , y[i]2 (cid:107)y|2 0.85
2 x[i]y[i] (cid:107)x(cid:107)2 (cid:107)y(cid:107)2 2 x[i]y[i] (cid:107)x(cid:107)2 (cid:107)y(cid:107)2 0.87
= cos(x, y) = cos(x, y) 0.85
On the other hand, assume that (cid:107)x(cid:107)2 ≤ (cid:107)y(cid:107)2 and for all i it holds x[i] ≤ y[i] ≤ cx[i] for some c > 1 and ≤ y[i](cid:107)y(cid:107)2 一方、 (cid:107)x(cid:107)2 ≤ (cid:107)y(cid:107)2 とすると、すべての i に対して x[i] ≤ y[i] ≤ cx[i] を c > 1 と ≤ y[i] (cid:107)y(cid:107)2 と仮定する。 0.93
. Then x[i](cid:107)x(cid:107)2 . その後 x[i](cid:107)x(cid:107)2 0.84
min( min (複数形 mins) 0.42
x[i]2 (cid:107)x(cid:107)2 x[i]2 (cid:107)x(cid:107)2 0.92
2 , y[i]2 (cid:107)y|2 2 , y[i]2 (cid:107)y|2 0.85
2 x[i]y[i]/c (cid:107)x(cid:107)2 (cid:107)y(cid:107)2 2 x[i]y[i]/c (cid:107)x(cid:107)2 (cid:107)y(cid:107)2 0.87
= cos(x, y)/c = cos(x, y)/c 0.94
Thus, the measure in a sense approximates cosine similarity. したがって、ある意味での測度はコサイン類似性を近似する。 0.67
And for L1 sampling we obtain that the そして、L1サンプリングのために取得します。 0.61
related measure is the so called sqrt-cosine similarity (Sohangir and Wang, 2017) 関連測定はいわゆるsqrt-cosine類似度(Sohangir and Wang, 2017)です。 0.87
0 ≤ n(cid:88) 0 ≤ n(cid:88) 0.92
i=1 n(cid:88) i=1 n(cid:88) 0.71
i=1 n(cid:88) i=1 n(cid:88) 0.71
i=1 ) ≤ n(cid:88) i=1 ≤ n(cid:88) 0.77
i=1 ) ≥ n(cid:88) i=1 ) ≥ n(cid:88) 0.75
i=1 5 Extensions i=1 i=1 5つの拡張 i=1 0.60
sqrt-cos(x, y) = sqrt-cos(x, y) = 0.94
n(cid:88) (cid:112)(cid:107)x( cid:107)1 n(cid:88) (cid:112)(cid:107)x( cid:107)1 0.81
(cid:112)(cid:107)y( cid:107)1 (cid:112)(cid:107)y( cid:107)1 0.78
x[i]y[i] Sampling from graph streams. x[i]y[i] グラフストリームからのサンプリング。 0.82
For massive graphs, or graphs where the edges can only be implicitly generated and not persistently stored, the algorithm needs k passes over the edges and the edges can be provided in arbitrary order. エッジが暗黙的に生成され、永続的に保存されない巨大なグラフやグラフの場合、アルゴリズムはエッジをkパスし、エッジを任意の順序で提供する必要がある。 0.70
The memory usage is bounded by O(n log n), thus the algorithm works in the semistreaming model of computation (Feigenbaum et al, 2005) where the space usage must be O(n polylog n). メモリ使用量は O(n log n) によって制限されるため、アルゴリズムは計算の半ストリーミングモデル(Feigenbaum et al, 2005)で動作し、空間利用は O(n polylog n) でなければならない。 0.91
9 9 0.85
英語(論文から抽出)日本語訳スコア
to rows of(cid:80) to rows of (cid:80) 0.90
If we consider nearby nodes more significant, Exponential weight decay for nodes of larger distance. 近傍のノードがより重要な場合、より大きな距離のノードの指数重みは減衰する。 0.72
then we could implement exponential weight decay. 指数関数的な重量減少を実現できます 0.49
Namely, the sampling probability will decrease by λi, for some λ < 1, for nodes v ∈ Nk(u) of distance i from su. すなわち、サンプリング確率は、ある λ < 1 に対して、Su からの距離 i のノード v ∈ Nk(u) に対して λi で減少する。 0.79
In linear algebraic terms we want to apply Lp sampling i=0 λiAi, where are A is the adjacency matrix. 線形代数的用語では、A が隣接行列である Lp サンプリング i=0 λiAi を適用したい。 0.76
Adding exponential decay is straightforward for in each next iteration we multiply the weight of the neighborhood nodes by λ. 指数的減衰を加えることは、次の反復ごとに λ で近傍ノードの重みを乗算するのに簡単である。 0.66
For L1 and L2 sampling: L0 sampling one can design heuristics that increase the weight of the nodes over each iteration in order to decrease its odds to be sampled. l1 と l2 サンプリング: l0サンプリングでは、各イテレーションでノードの重みを増加させるヒューリスティックを設計でき、サンプルのオッズを減らすことができる。 0.79
Node and edge weights. ノードとエッジの重み。 0.75
The L1 and L2 sampling algorithms also naturally handle nonnegative node and edge weights. L1およびL2サンプリングアルゴリズムは、非負のノードとエッジの重みも自然に扱う。 0.68
This is obvious for node weights as we simply reweight the original weight by the random weights. これはノード重みに対して明らかであり、元の重みをランダム重みで再重み付けするだけである。
訳抜け防止モード: これはノードの重みに対して明らかです。 元々の重量を ランダムな重量で再重み付けします
0.72
For edge weights, when collecting the neighborhood nodes, we will multiply node weights by the corresponding edge weight. エッジ重みについては、近傍ノードを収集する場合、対応するエッジ重みでノード重みを乗算する。 0.67
However, the algorithms would fail if we allow negative weights. しかし、負の重みを許すとアルゴリズムは失敗します。 0.67
It is crucial that we summarize the frequency vectors using counter based frequent items mining algorithms and these algorithms do not work in the so called turnstile model (Muthukrishnan, 2005) where both positive and negative updates are allowed. 周波数ベクトルをカウンタベースの頻繁なアイテムマイニングアルゴリズムを用いて要約することは重要であり、これらのアルゴリズムは、正と負の両方のアップデートが許容される、いわゆるターンタイルモデル(muthukrishnan, 2005)では動作しない。 0.77
Considering node or edge weights in the case of uniform sampling case is in a sense contradicting to the very purpose of the approach, namely to treat all local neighbors equally. 均一なサンプリングケースの場合のノードまたはエッジウェイトを考えることは、アプローチの目的、すなわちすべての地元の隣人を等しく扱うことに矛盾する意味です。 0.71
However, in case one wants to disregard the graph structure but still take into account node weights, then algorithms for the estimation of weighted Jaccard similarity (Shrivastava, 2016) can be adapted. しかし、グラフ構造を無視しつつ、ノード重みを考慮に入れたい場合には、重み付きJaccard類似性(Shrivastava、2016)の推定のためのアルゴリズムを適用することができます。 0.76
6 Previous work 6.1 Coordinated sampling from graphs 前作6件 6.1 グラフからの協調サンプリング 0.58
Coordinated sampling (Cohen, 2016) is a widely used algorithmic technique for efficient similarity estimation. Coordinated sample (Cohen, 2016) は効率的な類似度推定のためのアルゴリズム手法である。 0.87
It has applications in areas ranging from genome-wide association studies (Achlioptas et al, 2011) to recommendation systems (Shrivastava and Li, 2014). ゲノム全体の関連研究(Achlioptas et al, 2011)からレコメンデーションシステム(Shrivastava and Li, 2014)まで幅広く適用されています。 0.70
It has been applied to summarizing massive graphs, examples include problems such as triangle counting in graph streams (Becchetti et al, 2010), estimation of local and global clustering coefficients (Kutzkov and Pagh, 2013), graph minor counting, etc. グラフストリームにおける三角形のカウント(becchetti et al, 2010)、局所的および大域的クラスタリング係数の推定(kutzkov and pagh, 2013)、グラフのマイナーカウントなどである。
訳抜け防止モード: 巨大なグラフの要約に応用され、例えばグラフストリームにおける三角形の数え上げ(Becchetti et al, 2010)のような問題を含む。 局所的および大域的クラスタリング係数の推定(Kutzkov, Pagh, 2013) graph minor counting など。
0.85
We refer to the survey (McGregor, 2014) for an overview of problems and algorithmic techniques for graph stream mining, many of which are based on ideas for coordinated sampling. グラフストリームマイニングの問題やアルゴリズム技術の概要については,この調査(mcgregor, 2014)を参照し,その多くが協調サンプリングのアイデアに基づいている。 0.76
6.2 Continuous node embeddings 6.2 連続ノード埋め込み 0.80
Random walk based embeddings Representing words by real valued vectors, the so called word embeddings learnt from natural language corpora, has become ubiquitous and is a natural first step in many problems that require working with natural language. ランダムウォークに基づく埋め込み 実数値ベクトルによる単語表現、いわゆる自然言語コーポラから学習された単語埋め込みは、ユビキタスになり、自然言語で作業する必要がある多くの問題の自然な第一歩です。 0.76
Not surprisingly, pioneering approaches in the area such as word2vec (Mikolov et al, 2013) and GloVe (Pennington et al, 2014) received a lot of attention and have become indispensable tools in natural language understanding. 驚くべきことに、Word2vec (Mikolov et al, 2013) やGloVe (Pennington et al, 2014) のようなこの分野の先駆的なアプローチは多くの注目を集め、自然言語理解において欠かせないツールとなった。 0.75
Given the wide range of applications involving graph data, word embedding learning has been extended to node embedding learning where the objective is for a given graph G = (V, E) to learn a function f : V → Rd, i.e., a d-dimensional vector that represents a discrete object like a graph node by continuous features. グラフデータを含む幅広いアプリケーションを考えると、単語埋め込み学習は、与えられたグラフ g = (v, e) に対して関数 f : v → rd、すなわち連続的な特徴によってグラフノードのような離散オブジェクトを表す d-次元ベクトルを学ぶための、ノード埋め込み学習へと拡張されている。 0.89
Such node embeddings capture the structure of the underlying graph and enable to apply machine learning algorithms to graph data in a straightforward way. このようなノード埋め込みは、基盤となるグラフの構造をキャプチャし、機械学習アルゴリズムを直接的な方法でグラフに応用することができる。 0.75
The first presented approach is based on random walks (Perozzi et al, 2014). 最初の提示されたアプローチはランダムウォークに基づいている(Perozzi et al, 2014)。 0.74
The main idea behind the algorithm is that for each graph node u, we learn how to predict u’s occurrence from its context. このアルゴリズムの主な考え方は、各グラフノード u に対して、u の発生をそのコンテキストから予測する方法を学ぶことである。 0.87
In natural language the context of each word is the set of surrounding words in a sequence, and for graph nodes the context is the set of local neighbors. 自然言語では、各単語のコンテキストはシーケンス内の周辺単語の集合であり、グラフノードの場合、コンテキストは局所的な隣人の集合である。 0.80
Various algorithms have been proposed that allow some flexibility in selecting local neighbors according to different criteria, such as LINE (Tang et al, 2015b), PTE (Tang et al, 2015a), node2vec (Grover and Leskovec, 2016), APP (Zhou et al, 2017) and VERSE (Tsitsulin et al, 2018). LINE(Tang et al, 2015b)、PTE(Tang et al, 2015a)、node2vec(Grover and Leskovec, 2016)、APP(Zhou et al, 2017)、VERSE(Tsitsulin et al, 2018)など、さまざまな基準に従って、近隣住民を選択するための柔軟性が提案されている。 0.74
10 10 0.85
英語(論文から抽出)日本語訳スコア
Matrix factorization A branch of node embeddings algorithms work by factorization of (powers of) the adjacency matrix of the graph (Ou et al, 2016; Zhang et al, 2018; Cao et al, 2015; Wang et al, 2017). 行列因子化 ノード埋め込みアルゴリズムのブランチは、グラフの隣接行列(Ou et al, 2016; Zhang et al, 2018; Cao et al, 2015; Wang et al, 2017)の分解によって機能する。 0.62
These algorithms have well-understood properties but can be inefficient as even if the adjacency matrix is usually sparse, its powers can be dense (Watts and Strogatz, 1998), e.g., the average distance between any two users in the Facebook graph is only 4 (Backstrom et al, 2012). これらのアルゴリズムはよく理解された特性を持つが、たとえ隣接行列が通常疎いとしても、そのパワーは高密度である(Watts and Strogatz, 1998)。例えば、Facebookグラフの2つのユーザー間の平均距離はわずか4(Backstrom et al, 2012)。 0.79
The computational complexity is improved using advanced techniques from linear algebra. 計算複雑性は線形代数の高度な技術を用いて改善される。 0.71
However, these algorithms do not yield interpretable embeddings. しかし、これらのアルゴリズムは解釈可能な埋め込みを与えない。 0.59
Inspired by works that show that the word2vec model for learning word embeddings from natural text can be phrased as a matrix factorization problem, it has been shown that most of the random walk based approaches can be expressed as matrix factorization for implicitly defined matrices based on powers of the adjacency matrix of the original graph (Qiu et al, 2018). 自然文からの単語埋め込みを学習するための2vecモデルが行列分解問題として表現できることを示す研究から着想を得て、ランダムウォークに基づくアプローチのほとんどは、元のグラフの隣接行列の力に基づいて暗黙的に定義された行列に対する行列分解として表現できることが示されている(Qiu et al, 2018)。 0.70
Deep learning Finally, it is worth noting that node embeddings can be also learned using graph neural networks (Hamilton et al, 2017). 最後に、ノード埋め込みはグラフニューラルネットワーク(Hamilton et al, 2017)を使用して学習できることに注意してください。
訳抜け防止モード: 最後に、深層学習は注目に値する。 ノードの埋め込みはグラフニューラルネットワークを使って学ぶこともできる( Hamilton et al, 2017)。
0.77
The intermittent layer of a neural network whose input are individual nodes in fact trains embedding vectors per node. 入力が個々のノードであるニューラルネットワークの断続層は、実際にはノード毎の埋め込みベクトルを訓練する。 0.72
The main advantage of GNNs is that they are inductive and can be applied to previously unseen nodes, while the above discussed approaches are transductive and work only for a fixed graph. GNNsの主な利点は、インダクティブであり、これまで見つからなかったノードに適用できることであり、上記の議論されたアプローチはトランスダクティブであり、固定グラフでのみ機能する。 0.66
The disadvantage is that these are deep learning architectures that can be slow to train and might require careful hyperparameter tuning. 欠点は、これらがトレーニングが遅く、注意深いハイパーパラメータチューニングを必要とする、ディープラーニングアーキテクチャであることだ。 0.59
6.3 Coordinated local sampling for interpretable embeddings 6.3 解釈可能な埋め込みのためのコーディネート局所サンプリング 0.56
Approaches close to COLOGNE are NetHash (Wu et al, 2018) and NodeSketch (Yang et al, 2019). COLOGNEに近いアプローチはNetHash(Wu et al, 2018)とNodeSketch(Yang et al, 2019)である。 0.82
NetHash uses similarity preserving hashing to generate embeddings for attributed graphs using minwise independent permutations. NetHashは、属性付きグラフの埋め込みを生成するために、類似性保持ハッシュを使用する。
訳抜け防止モード: NetHashは類似性保存ハッシュを使用する 属性付きグラフの埋め込みを生成します。
0.77
The algorithm however generates individual rooted trees of depth k for each node and its complexity scales as O(nt(m/n)k) where t is the maximum number of attributes per node. しかし、アルゴリズムは各ノードの深さkの個々の根付き木を生成し、その複雑性はo(nt(m/n)k)でスケールし、tはノードごとの属性の最大数である。 0.77
Our L0 sampling algorithm is much more efficient as there is no need for the generation of separate trees for each node, thus we avoid the factor (m/n)k. Also, COLOGNE does not need to assume, but can still handle, node attributes. 私たちのL0サンプリングアルゴリズムは、ノードごとに別々のツリーを生成する必要がないため、より効率的です。そのため、ファクタ(m/n)kを避けます。また、COLOGNEは、ノード属性を想定する必要はありませんが、それでも処理できます。 0.72
NodeSketch is a heuristic for coordinated sampling from local neighborhoods. NodeSketchは、ローカル地区からの協調サンプリングのためのヒューリスティックだ。 0.59
It builds upon algorithms for the estimation of the normalized min-max similarity between vectors u, v ∈ R+n, (cid:107)u(cid:107)1 = (cid:107)v(cid:107)1 = 1: これはベクトル u, v ∈ r+n, (cid:107)u(cid:107)1 = (cid:107)v(cid:107)1 = 1: の間の正規化されたmin-max類似度の推定アルゴリズムに基づいている。 0.70
(cid:80)n (cid:80)n (cid:80)n (cid:80)n 0.81
i=1 min(u[i], v[i]) i=1 max(u[i], v[i]) i=1 min(u[i], v[i]) i=1 max(u[i], v[i]) 0.85
The original NodeSketch approach does not consider interpretability but it is essentially a sampling based approach. オリジナルのNodeSketchアプローチは解釈可能性を考慮していないが、基本的にサンプリングベースのアプローチである。
訳抜け防止モード: オリジナルのNodeSketchアプローチは解釈可能性を考慮しない 基本的にはサンプリングベースのアプローチです
0.74
It works by recursively sketching the neighborhood at each node until recursion depth k is reached. 再帰深さkに達するまで各ノードの近傍を再帰的にスケッチする。 0.68
It builds upon an algorithm for min-max similarity estimation (Ioffe, 2010). 最小最大類似度推定のためのアルゴリズムに基づいて構築される(Ioffe, 2010)。 0.70
The approach is conceptually similar to our Lp sampling algorithm but no theoretical guarantee for the quality of the returned samples can be provided. 提案手法はLpサンプリングアルゴリズムと概念的に似ているが, 得られたサンプルの品質に関する理論的保証は得られない。 0.84
To understand the main difference, the main goal of COLOGNE is to detect a node that satisfies a predefined sampling condition. 主な違いを理解するために、COLOGNEの主な目標は、事前に定義されたサンプリング条件を満たすノードを検出することです。
訳抜け防止モード: 主な違いを理解するために。 COLOGNEの主な目標は 事前に定義されたサンプリング条件を満たすノードを検出する。
0.77
The sampling condition is the key to showing the stated sampling probability and the similarity function that pairs of sampled nodes approximate. サンプリング条件は、前述のサンプリング確率と、サンプルノードのペアが近似した類似度関数を示す鍵である。 0.86
NodeSketch assigns first random weights to nodes using the Ioffe algorithm, similarly to what we do in L1 and L2 sampling. NodeSketchは、Ioffeアルゴリズムを使用して最初のランダムウェイトをノードに割り当てます。
訳抜け防止モード: NodeSketchはIoffeアルゴリズムを使用して、最初のランダムウェイトをノードに割り当てる。 L1 と L2 のサンプリングと同様です。
0.73
In the i-th recursive call of NodeSketch for each node u we collect samples from N (u) and add up the corresponding weights in case two nodes appear more than once as samples in N (u). 各ノード u の NodeSketch の i-th 再帰呼び出しでは、N (u) からサンプルを収集し、2 つのノードが N (u) のサンプルとして一度以上現れる場合に対応する重みを追加します。 0.83
For node u we select the node with the smallest weight from N (u) and this is the crucial difference to COLOGNE. ノード u では、N (u) から最小のウェイトを持つノードを選択し、これは COLOGNE との重要な違いです。 0.77
Working with a single node is subject to random effects that could make the behavior of the algorithm difficult to explain. 単一ノードで作業するにはランダムな効果が伴うため、アルゴリズムの動作を説明するのが難しくなる。 0.77
Consider the graph in Figure 2. 図2のグラフを考えてみましょう。 0.73
There are many paths from node u to node z in N2(u). N2(u) では、ノード u からノード z へのパスが多数あります。 0.76
In the first iteration of NodeSketch it is very possible that most of u’s immediate neighbors, the yellow nodes v1 to v12, will sample a blue node as each v is connected with several blue w nodes, i.e., svi = wj. NodeSketchの最初のイテレーションでは、uのすぐ隣のほとんどの黄色いノード v1 から v12 が、各 v が複数の青い w ノード、すなわち svi = wj に接続されているときに、青いノードをサンプリングする可能性が非常に高い。 0.82
Thus, in the second iteration it is likely that u ends up with a sample for u different from z. したがって、第2の反復では、u は z とは異なる u のサンプルで終わる可能性が高い。 0.83
In contrast, by keeping a sketch for L1 and L2 sampling COLOGNE will provably preserve the information that node z is reachable from u by many different paths. 対照的に、L1 と L2 サンプリングのスケッチを保持することで、COLOGNE はノード z が u から到達可能な情報を多くの異なる経路で確実に保存する。
訳抜け防止モード: 対照的に L1 と L2 サンプリング COLOGNE のスケッチを保持する 確実に情報を保存し ノード z は多くの異なる経路で u から到達可能である。
0.79
And we can control the importance we assign to sampling easily reachable nodes by weighting the items with r1/p そして、r1/pでアイテムを重み付けすることで、簡単に到達可能なノードのサンプリングに割り当てる重要性を制御できます。
訳抜け防止モード: そして我々はその重要性をコントロールできる アイテムを r1 / p で重み付けすることで 容易に到達可能なノードをサンプリングする
0.68
, ri ∈ (0, 1] such in L2 sampling we are more likely to have su = z. , ri ∈ (0, 1]) であり、l2 サンプリングでは su = z である可能性が高い。 0.72
i 11 私は 11 0.69
英語(論文から抽出)日本語訳スコア
w1 v1 z u w19 w1 v1 z ウ W19 0.73
v12 Figure 2: NodeSketch (Yang et al, 2019) might miss that there are many path from u to z of length at most 2. v12 図2: NodeSketch (Yang et al, 2019) は u から z までのパスが少なくとも 2 つあることを見逃してしまうかもしれない。 0.77
Best viewed in color. 色が一番よく見える。 0.75
7 Experiments Dataset 実験7 データセット 0.69
Cora Citeseer Pubmed Wikipedia コラ Citeseer Pubmed Wikipedia 0.66
PPI BlogCatalog PPI BlogCatalog 0.85
edges nodes 5.4K 2.7K 3.3K 4.7K 19.7K 44.3K 92.5K 4.8K 3.9K 38.7K 10.3K 333.9K エッジノード 5.4K 2.7K 3.3K 4.7K 19.7K 44.3K 92.5K 4.8K 38.7K 333.9K 0.39
labels multilabel features weights ラベルマルチラベル 重量を特徴付ける 0.65
diameter 7 6 3 40 50 40 直径 7 6 3 40 50 40 0.82
no no no yes yes yes いやいやいやいやいや はい はいはい 0.40
1.4K 3.7K 500 0 0 0 1.4K 3.7K 500 0 0 0.68
no no yes no no no いやいやいやいやいやいやいや 0.14
19 28 18 3 8 5 19 28 18 3 8 5 0.85
Table 1: Information on datasets. 表1:データセットに関する情報。 0.81
The column labels denotes the total number of node labels, multilabel shows if a node can be assigned more than one class label, features is the total number of features that can be assigned to nodes, weights shows if node features are weighted. 列ラベルはノードのラベルの総数を表し、マルチラベルはノードが複数のクラスラベルを割り当てられるかどうかを示し、特徴はノードに割り当てられる特徴の総数であり、重み付けはノードの特徴が重み付けされているかどうかを示す。 0.81
The last parameter is the graph diameter, i.e., the maximum distance between any two nodes. 最後のパラメータはグラフの直径、すなわち任意の2つのノード間の最大距離である。 0.87
Datasets We evaluated COLOGNE sampling against known approaches to local neighborhood sampling on six publicly available graph datasets, summarized in Table 1. 表1で要約した6つのグラフデータセット上で,ローカル近傍サンプリングに対する既知のアプローチに対するケルンサンプリングを評価した。 0.70
The first three datasets Cora, Citeseer, Pubmed (Sen et al, 2008) are citation networks where nodes correspond to papers and edges to citations. Cora, Citeseer, Pubmed (Sen et al, 2008) の最初の3つのデータセットは引用ネットワークであり、ノードは論文と引用に対応する。 0.79
Each node is assigned a unique class label, and nodes are described by a list of attributes, for example key words that appear in the article. 各ノードは一意のクラスラベルを割り当てられ、ノードは属性のリスト、例えば記事に表示されるキーワードによって記述されます。 0.84
In Pubmed the attributes for each node are key words with tf-idf scores, in Cora and Citeseer they are unweighted. pubmedでは各ノードの属性はtf-idfスコアのキーワードであり、coraとciteseerでは重み付けされない。 0.68
The next three datasets, Wikipedia (Mahoney, 2011), PPI (Breitkreutz et al, 2008) and BlogCatalog (Zafarani and Liu, 2009), are so called multiclass multilabel problems, i.e., each node is assigned several class labels. 次の3つのデータセット、Wikipedia (Mahoney, 2011)、PPI (Breitkreutz et al, 2008)、BlogCatalog (Zafarani and Liu, 2009) は、いわゆるマルチクラスマルチラベル問題と呼ばれる。
訳抜け防止モード: 次の3つのデータセットはWikipedia(Mahoney, 2011)である。 PPI (Britkreutz et al, 2008)とBlogCatalog (Zafarani and Liu, 2009)。 いわゆる「マルチクラス・マルチラベル問題」です 各ノードにはいくつかのクラスラベルが割り当てられます。
0.79
The Wikipedia graph represents word co-occurrences and the labels are part-of-speech (POS) tags. Wikipediaのグラフは単語共起を表し、ラベルは話の一部(POS)タグです。 0.75
PPI is a protein-protein interaction network where labels represent biological states. PPIは、ラベルが生物学的状態を表すタンパク質とタンパク質の相互作用ネットワークです。 0.57
BlogCatalog is the graph of bloggers, edges represent relations between bloggers and labels the interest tags used by the bloggers. BlogCatalogはブロガーのグラフであり、エッジはブロガーとブロガーが使用する興味タグをラベルの関係を表しています。 0.69
Experimental setting The algorithms were implemented in Python 3 and experiments were performed on a Linux machine with a 3.9 GHz Intel CPU and 16 GB main memory3. 実験的な設定 アルゴリズムはPython 3で実装され、3.9GHzのIntel CPUと16GBのメインメモリを持つLinuxマシンで実験が行われた。 0.80
We generated samples from the k-hop neighborhood of each node for k ∈ {1, 2, 3, 4}. それぞれのノードの k-ホップ近傍から k ∈ {1, 2, 3, 4} のサンプルを生成した。 0.84
We used following methods: 私たちは以下の方法を用いた。 0.54
1. Random walks (RW). 1. ランダムウォーク(RW)。 0.74
For a node u ∈ V , we select at random a neighbor v ∈ N (u), then sample one of v’s neighbors w ∈ N (v), and so on. ノード u ∈ V に対しては、隣接する v ∈ N (u) をランダムに選択し、v の隣接する w ∈ N (v) の 1 つをサンプリングする。 0.71
After k iterations we return the last selected node. k反復の後、最後に選択したノードを返します。 0.60
There are many random walk variations with different objectives but since no of them consider coordinated sampling, we only compare with the standard random walk approach. 目的の異なるランダムウォークのバリエーションは数多く存在するが、協調サンプリングを考慮しないため、標準的なランダムウォークアプローチとしか比較できない。 0.71
2. NodeSketch (NS). 2. NodeSketch (NS)。 0.80
We select a node using the approach from (Yang et al, 2019), see the original paper 私たちは(Yang et al, 2019)のアプローチを使用してノードを選択し、元の論文を参照してください。
訳抜け防止モード: アプローチを使用してノードを選択します(Yang et al, 2019)。 オリジナルの論文を見てください
0.77
for details. 3The implementation can be found in https://github.com/k ingkonk81/cologne 詳細は? 3 実装は https://github.com/k ingkonk81/cologne で確認できる。 0.47
12 12 0.85
英語(論文から抽出)日本語訳スコア
3. Uniform sampling (L0). 3. 均一サンプリング(L0)。 0.80
The minwise sampling approach described in Section 4.3. 第4.3節で説明した最小サンプリングアプローチ。 0.62
4. L1 sampling (L1). 4. L1サンプリング (L1。 0.84
We somewhat simplified the algorithm in Section 4.3 and return as a sample the heaviest element in the reweighted neighborhood frequency vector, as detected by the frequent items mining algorithm. 本稿では,第4.3節でアルゴリズムをやや単純化し,頻繁なアイテムマイニングアルゴリズムによって検出された再重み付き近傍周波数ベクトルの最も重い要素をサンプルとして返却する。 0.71
We used a sketch with 10 nodes. 10ノードのスケッチを使いました。 0.68
Note that in order to obtain the bounds in Theorem 3 we allowed a node to be sampled if certain constraints are satisfied but these techniques are only of theoretical interest such that we can mathematically analyze the algorithm. 定理3における境界を得るためには、特定の制約が満たされた場合にノードをサンプリングすることを許したが、これらのテクニックは数学的にアルゴリズムを解析できる理論上の関心のみである。 0.74
5. L2 sampling (L2). 5. L2サンプリング(L2)。 0.81
We return as a sample the heaviest node in the reweighted frequency vector as 重み付けされた周波数ベクトルで最も重いノードをサンプルとして返します。 0.71
described in Section 4.3. 第4.3段落に記載。 0.55
We used again a sketch with 10 nodes. 10ノードのスケッチを再度使用しました。 0.73
Dataset Cora Citeseer データセット コラ シテシーア 0.50
Pubmed PPI Wikipedia 出版 PPI Wikipedia 0.72
BlogCatalog BlogCatalog 0.85
d 10 25 50 10 25 50 10 25 50 10 25 50 10 25 50 10 25 50 d 10 25 50 10 25 50 10 25 50 10 25 50 10 25 50 10 25 50 0.85
RW NS 3.1 0.8 2.2 7.9 18.2 4.2 6.3 1.1 15.7 2.4 6.9 36.6 67.1 6.8 161.2 19.1 322.4 38.3 1.6 1.9 4.5 3.9 11.8 9.1 3.4 3.4 11.2 10.1 19.7 17.0 14.5 10.5 38.7 30.5 58.3 74.7 RW NS 3.1 0.8 2.2 7.9 18.2 4.2 6.3 1.1 15.7 2.4 6.9 36.6 67.1 6.8 161.2 19.1 322.4 38.3 1.6 1.9 4.5 3.9 11.8 9.1 3.4 3.4 11.2 10.1 19.7 17.0 14.5 10.5 38.7 30.5 58.3 74.7 0.41
L0 2.8 7.2 16.3 5.7 17.0 33.9 61.5 157.1 304.2 1.2 3.1 7.0 2.3 6.7 12.9 8.2 22.4 50.5 L0 2.8 7.2 16.3 5.7 17.0 33.9 61.5 157.1 304.2 1.2 3.1 7.0 2.3 6.7 12.9 8.2 22.4 50.5 0.41
L1 7.2 21.6 44.5 11.5 30.4 61.3 104.4 295.6 528.6 14.6 41.6 84.0 30.0 69.6 148.2 91.0 227.6 458.8 L1 7.2 21.6 44.5 11.5 30.4 61.3 104.4 295.6 528.6 14.6 41.6 84.0 30.0 69.6 148.2 91.0 227.6 458.8 0.41
L2 7.4 21.9 44.9 11.8 31.1 62.3 104.9 296.5 535.9 16.1 42.8 83.8 30.1 72.1 157.5 92.9 229.2 464.6 L2 7.4 21.9 44.9 11.8 31.1 62.3 104.9 296.5 535.9 16.1 42.8 83.8 30.1 72.1 157.5 92.9 229.2 464.6 0.41
Table 2: Running time (in seconds) for feature generation from the 4-hop neighborhood for the five methods and different embeddings sizes, denoted as d. 表2: 5つのメソッドと異なる埋め込みサイズに対して、4ホップ近所の機能生成のための時間(秒単位で)を実行する。 0.78
Running time In Table 2 we list the time needed to generate all node samples for varying number d of samples per node. 実行時間 テーブル2では、ノード毎のサンプル数dの異なるすべてのノードサンプルを生成するのに必要な時間をリストします。 0.79
We observe that random walks, NodeSketch and uniform (L0) sampling are very efficient. ランダムウォーク,ノードケッチ,均一(l0)サンプリングが非常に効率的である。 0.66
This is because we keep a single sample per node during the k iterations. kイテレーションの間、ノード毎に1つのサンプルを保持するためです。 0.61
L1 and L2 sampling are slower as we need to keep a summary of neighborhood nodes in order to detect a heavy hitter (the logarithmic factor in the running time in the theoretical analysis). L1とL2のサンプリングは、重いヒッタ(理論解析における実行時間の対数係数)を検出するために、近傍ノードのサマリを保持する必要があるため遅い。 0.79
Observe that the running time grows linearly with the embedding size, especially between 25 and 50 we have almost perfect doubling. ランニング時間は埋め込みサイズとともに線形に成長するが、特に25から50の間は、ほぼ完全に倍増する。 0.71
Note that these are results obtained from a single-core implementation and since sample generation is easily parallelizable the approach can be significantly sped up by designing an advanced parallel architecture. これらはシングルコア実装から得られた結果であり、サンプル生成は容易に並列化できるため、高度な並列アーキテクチャを設計することで、アプローチを大幅に加速することができる。 0.70
7.1 Link prediction The first set of experiments is for link prediction. 7.1 リンク予測 最初の実験セットはリンク予測です。 0.67
We design a setting similar to the one in (Grover and Leskovec, 2016). 我々は、Grover と Leskovec, 2016) に類似した設定を設計します。 0.82
We removed 20% of the edges selected at random but such that the graph remains connected, and held them out as a test set. ランダムに選択したエッジの20%を取り除いたが、グラフが接続されたままであり、テストセットとして保持した。 0.78
The rest of the edges together with four times more negative examples, i.e., pairs of nodes not connected by an edge, yield an imbalanced dataset with 20% positive examples. エッジの残りの部分と4倍の負の例、すなわちエッジで接続されていないノードのペアは、20%の正の例を持つ不均衡データセットを生成する。 0.75
Each node u is represented by a d-dimensional vector of discrete features u ∈ Kd where K is the set of attributes 各ノード u は離散的特徴 u ∈ Kd の d-次元ベクトルで表され、K は属性の集合である。 0.88
13 13 0.85
英語(論文から抽出)日本語訳スコア
Figure 3: F1 scores for link prediction. 図3: F1はリンク予測のスコアです。 0.73
Best viewed in color. 色が一番よく見える。 0.75
describing nodes. We set d = 25. ノードを記述する。 d = 25 を設定します。 0.69
For the citation networks the attributes are words describing the articles, and for PPI, Wikipedia and BlogCatalog we set the attribute to be the node itself, i.e. 引用ネットワークでは、属性は記事を記述する単語であり、ppi、wikipedia、blogcatalogでは属性をノード自身、すなわちノード自身と設定します。 0.71
K = V . For a pair of nodes u and v the input to a classification model is a 2d-dimensional vector z such that the entries in the i-coordinates in u and v are mapped to “twin” coordinates in z, i.e., the i-th coordinate in u is mapped to the 2i-th coordinate in z, and the i-th coordinate in v is mapped to (2i + 1)-th coordinate in z. K = V。 一対のノード u と v に対して、分類モデルへの入力は、u と v の i-座標のエントリが z の "twin" 座標にマッピングされるような二次元ベクトル z であり、すなわち u の i-座標は z の 2i-座標にマッピングされ、v の i-座標は z の (2i + 1)-座標にマッピングされる。 0.79
For random walks we sampled an attribute at random, while for NodeSketch and COLOGNE we sampled an attribute in a coordinated way using the corresponding basic sampling algorithm where attributes share a random seed. ランダムウォークでは、属性をランダムにサンプリングし、NodeSketchとCOLOGNEでは、属性がランダムなシードを共有する基本サンプリングアルゴリズムを使用して、属性を協調的にサンプリングした。 0.66
For example, in Pubmed nodes are described by a list of weighted features which are reweighted according to the algorithm used in COLOGNE or NodeSketch. 例えば、Pubmedノードでは、COLOGNEまたはNodeSketchで使用されるアルゴリズムに従って重み付けされた機能のリストによって記述される。 0.71
We trained a Decision Tree classifier as it yields an explainable model. 説明可能なモデルが得られるように、決定木分類器を訓練した。 0.62
The splitting criterion is Gini index and the tree depth is unlimited. 分割基準はGiniインデックスであり、ツリーの深さは無制限です。 0.74
The results in Figure 3 show the F1 scores for the six datasets for features collected at different neighborhood depths. 図3の結果は、さまざまな近隣の深さで収集された6つのデータセットのF1スコアを示しています。 0.63
Here are our observations: • In general all coordinated sampling approaches yield comparable results. • 一般に、すべての協調サンプリングアプローチは、同等の結果をもたらす。 0.59
In Table 3 we show that for some datasets COLOGNE is better than NodeSketch, so in downstream applications an optimal sampling approach might be considered a hyperparameter. 表3では、いくつかのデータセットでは、COLOGNEがNodeSketchより優れているため、下流アプリケーションでは、最適なサンプリングアプローチがハイパーパラメータと見なされる可能性がある。 0.60
• For networks of small diameter L0 sampling yields very bad results for k > 2. •小径L0サンプリングのネットワークの場合、k > 2の非常に悪い結果が得られます。 0.68
The reason is that all nodes end up with the same sample, namely the node with the smallest random seed since we disregard 理由は、すべてのノードが同じサンプル、すなわち私たちが無視するので最小のランダムシードを持つノードで終わるからです。 0.80
14 14 0.85
英語(論文から抽出)日本語訳スコア
Cora Citeseer Pubmed コラ シテシーア 出版 0.44
k COLOGNE NodeSketch COLOGNE NodeSketch COLOGNE NodeSketch 1 2 3 4 k COLOGNE NodeSketch CoLOGNE NodeSketch CoLOGNE NodeSketch 1 2 3 4 0.75
0.508 (L1) 0.521 (L0) 0.512 (L1) 0.553 (L2) 0.508 (L1) 0.521 (L0) 0.512 (L1) 0.553 (L2) 0.69
0.359 (L2) 0.399 (L0) 0.445 (L0) 0.451 (L0) 0.359 (L2) 0.399 (L0) 0.445 (L0) 0.451 (L0) 0.69
0.39 (L0) 0.454 (L0) 0.527 (L0) 0.578 (L0) 0.39 (L0) 0.454 (L0) 0.527 (L0) 0.578 (L0) 0.69
0.41 0.428 0.514 0.558 0.41 0.428 0.514 0.558 0.45
0.331 0.387 0.442 0.458 0.331 0.387 0.442 0.458 0.45
0.338 0.419 0.499 0.532 0.338 0.419 0.499 0.532 0.45
PPI Wikipedia PPI Wikipedia 0.85
BlogCatalog BlogCatalog 0.85
k COLOGNE NodeSketch COLOGNE NodeSketch COLOGNE NodeSketch 1 2 3 4 k COLOGNE NodeSketch CoLOGNE NodeSketch CoLOGNE NodeSketch 1 2 3 4 0.75
0.472 (L2) 0.501 (L1) 0.507 (L0) 0.488 (L2) 0.472 (L2) 0.501 (L1) 0.507 (L0) 0.488 (L2) 0.69
0.635 (L2) 0.649 (L2) 0.693 (L2) 0.739 (L2) 0.635 (L2) 0.649 (L2) 0.693 (L2) 0.739 (L2) 0.69
0.585 0.578 0.627 0.473 0.585 0.578 0.627 0.473 0.45
0.466 0.497 0.498 0.425 0.466 0.497 0.498 0.425 0.45
0.626 0.62 0.715 0.721 0.626 0.62 0.715 0.721 0.45
0.658 (L2) 0.648 (L2) 0.658 (L2) 0.648 (L2) 0.71
0.588 (L1) 0.6 (L2) 0.588 (L1) 0.6 (L2) 0.71
Table 3: Comparison of COLOGNE and NodeSketch for F1. 表3: F1のCOLOGNEとNodeSketchの比較。 0.76
In bold font we give the best result for each dataset for COLOGNE and NodeSketch. 大胆なフォントでは、COLOGNEとNodeSketchの各データセットに最高の結果を与えます。 0.70
the graph structure. In contrast, L1 and L2 sampling are much less affected by the small diameter as we sample easily reachable neighborhood nodes. グラフ構造。 対照的に、L1 と L2 のサンプリングは、我々が容易に到達可能な近傍ノードをサンプリングするため、小さな直径の影響を受けない。 0.59
• While NodeSketch yields overall good results its performance on BlogCatalog appears strange. • NodeSketchは全体的な良い結果をもたらすが、BlogCatalogのパフォーマンスは奇妙に思える。 0.66
We observe a sudden decrease of the predictive power of NodeSketch’s embeddings when we increase the k-hop neighborhood from 3 to 4. 我々は、3から4にkホップ近所を増やすときにNodeSketchの埋め込みの予測力の突然の減少を観察します。 0.74
Looking at the sampled values we observe that most nodes end up with identical samples. サンプル値を見ると、ほとんどのノードが同一のサンプルで終わるのが分かります。
訳抜け防止モード: サンプル値を見て ほとんどのノードが 同一のサンプルで終わるのを観察します
0.86
We can explain the behavior of L0 sampling with the small diameter size but given the heuristic nature of NodeSketch it is challenging to make an educated guess why this happens for BlogCatalog but not for the Wikipedia graph which also has a small diameter. 直径の小さいL0サンプリングの振る舞いを説明することができますが、NodeSketchのヒューリスティックな性質を考えると、これがなぜBlogCatalogで起こるのかを教育的な推測にすることは困難です。
訳抜け防止モード: 小径のL0サンプリングの挙動を説明することができる。 しかしNodeSketchのヒューリスティックな性質を考えると、なぜなのかを学識ある推理することは難しい。 これはBlogCatalogでも起こるが、小さめのWikipediaグラフには当てはまらない。
0.76
Interpretability A major advantage of coordinated sampling is that it yields interpretable node embeddings. 解釈可能性 協調サンプリングの大きな利点は、解釈可能なノード埋め込みをもたらすことである。 0.58
First of all note that in all experiments the Decision tree models performed their first two splits on twin coordinates in the input vector, i.e., the indices at position 2i and 2i + 1 which represent the i-th samples for two nodes and are likely to contain identical samples for nodes with similar neighborhoods. まず第一に、すべての実験において、決定木モデルは入力ベクトルの双対座標、すなわち2つのノードのi-thサンプルを表す位置2iと2i + 1のインデックスの最初の2つの分割を実行し、類似の近傍を持つノードの同じサンプルを含む可能性が高いことに注意してください。 0.77
In Figure 4 we plot the distribution of sampled words in the L2 embeddings for the most significant position according to the decision tree model. 図4では、決定木モデルに従って、l2埋め込みにおけるサンプル単語の分布を最も重要な位置にプロットする。 0.78
On the left is the distribution for positive examples, and on the right is the distribution for negative examples. 左側は正の例の分布であり、右側は負の例の分布である。 0.69
(Note that the distribution of the twin position is almost identical.) (ツインポジションの分布はほぼ同一であることに注意。) 0.79
We observe clear differences between positive and negative examples which can help human experts to understand better the data. ポジティブな例とネガティブな例の明確な違いを観察し、人間の専門家がデータをよりよく理解できるようにします。 0.58
In Figure 5 we show the decision path for a positive and a negative example. 図5では、ポジティブな例とネガティブな例の決定パスを示します。 0.78
(Note that the numeric values come from integer encoding of the word indices as computed by sklearn’s LabelEncoder. (注意すべきは、数値はsklearnの labelencoder によって計算された単語インデックスの整数符号化である。 0.82
Each leaf in the decision tree thus contains a small number of words.) 決定木の各葉は、それゆえ、わずかな単語を含む。 0.64
We observe that in the positive example the two words in the top twin positions are identical while this is not the case for the negative examples. 正の例では、トップツインの位置にある2つの単語は同一であるが、負の例ではそうではない。 0.75
This is repeated at several deeper branches in the tree. これは木のいくつかの深い枝で繰り返されます。 0.73
7.2 Node classification We next consider the problem of node classification using the provided node labels as described in Table 1. 7.2 ノード分類 次に、表1に示すように、提供されたノードラベルを用いたノード分類の問題を考える。 0.69
Using the same setting as for link prediction, each node is represented by a 50-dimensional vector such that the i-th coordinate is the attribute of a sampled node. リンク予測と同じ設定を用いて、各ノードは、i座標がサンプリングノードの属性となるように、50次元ベクトルで表現される。 0.73
We again train a decision tree classifier. 私たちは再び決定木分類器を訓練します。 0.54
We trained a one-vs-rest classifier on top of the decision tree model. 我々は決定木モデル上で1-vs-rest分類器を訓練した。 0.63
We split the data into 80% for training and 20% トレーニングのためにデータを80%と20%に分割し 0.83
15 15 0.85
英語(論文から抽出)日本語訳スコア
Figure 4: Distribution of words in the most significant position according to the decision tree for L2 sampling. 図4: l2サンプリングのための決定木に従って最も重要な位置にある単語の分布。 0.80
On the left is the distribution for positive examples, i.e., nodes connected by an edge, in the right column is the distribution for negative examples. 左側は正の例、すなわちエッジで接続されたノードの分布であり、右側の列は負の例の分布である。 0.80
for testing and report average micro-F1 and macro-F1 scores for 10 independent runs of the algorithm in Figures 6. 図6のアルゴリズムの10の独立した実行のための平均マイクロF1およびマクロF1スコアをテストし、報告するため。 0.70
As expected, random walks never achieve better results than coordinated sampling. 予想通り、ランダムウォークは協調サンプリングよりも良い結果を得ることはない。 0.53
Analyzing the results we make similar observations as for link prediction. 結果を分析して,リンク予測と同様の観測を行う。 0.77
For graphs of small diameter L0 sampling is only useful up to k = 2. 小さな直径の L0 サンプリンググラフは k = 2 までしか役に立たない。 0.82
The results of COLOGNE and NodeSketch are in general comparable but there is again an example where NodeSketch’s behavior is confusing. COLOGNEとNodeSketchの結果は一般的に同等ですが、NodeSketchの振る舞いが混乱している例が再びあります。 0.78
On the Wikipedia graph NodeSketch’s micro-F1 score suddenly drops when adding one more iteration for sampling. wikipediaのグラフでnodesketchのmicro-f1スコアは、サンプリングのためにもう1回追加すると突然低下する。 0.60
The label distribution on Wikipedia is highly skewed. ウィキペディアのラベルの配布は非常にスキューです。 0.71
We can argue that L1 and L2 sampling generate embeddings that enable us to learn the most common labels and become better with increasing k as they sample more representative nodes, hence the micro-F1 scores improve but the macro-F1 become worse. L1とL2サンプリングは、最も一般的なラベルを学習し、kを増やしてより代表的なノードをサンプリングすることができる埋め込みを生成するため、マイクロF1スコアは改善されるが、マクロF1は悪化する。 0.71
But we don’t know how to explain the sudden decrease in both micro-F1 and macro-F1 values obtained when using NodeSketch’s embeddings. しかし、NodeSketchの埋め込みを使用して得られたmicro-F1値とマクロ-F1値の両方の突然の減少を説明する方法はわかりません。 0.70
The result are again interpretable for a human expert. 結果は、人間の専門家にとって再び解釈できる。 0.72
In Figure 7 we show how the different distribution of node attributes for the three node classes, for one coordinate of the embedding vector. 図7では、3つのノードクラス、埋め込みベクトルの1つの座標に対するノード属性の異なる分布を示しています。 0.86
Note that there is no such skew in the random walks embeddings. ランダムウォーク埋め込みにはそのようなスキューは存在しないことに注意。 0.55
7.3 Comparison with continuous node embeddings 7.3 連続ノード埋め込みとの比較 0.78
We do not compare against continuous embeddings as these are not interpretable and the focus of the paper is to present and evaluate approaches to coordinated sampling. これらが解釈不可能であり,協調サンプリングへのアプローチの提示と評価が本論文の焦点であるため,継続的埋め込みとの比較は行わない。 0.73
Such a comparison can be found in (Yang et al, 2019) where NodeSketch is compared against different approaches to the generation of continuous embeddings. このような比較は、(Yang et al, 2019)NodeSketchが継続的埋め込みの生成に対するさまざまなアプローチと比較されている。 0.78
However, we would like to mention that the results in (Yang et al, 2019) are obtained by training an SVM model with custom kernel where the kernel is a precomputed Gram matrix with the Hamming distance between node pairs. しかし、この結果(Yang et al, 2019)は、カーネルがノードペア間のハミング距離を持つ事前計算されたグラム行列であるカスタムカーネルでSVMモデルをトレーニングすることで得られることを述べておきたい。 0.67
In our opinion it is questionable if such an approach is really feasible for dealing with large graphs. 私たちの意見では、そのようなアプローチが大きなグラフを扱うのに本当に可能なのか疑問です。 0.67
It is likely that one would need to consider Ω(n) nodes in order to train a good model. 良いモデルを訓練するためにΩ(n)ノードを考える必要がある可能性が高い。 0.71
A Gram matrix with O(n2) entries can easily become a computational bottleneck. o(n2) エントリを持つグラム行列は容易に計算ボトルネックとなる。 0.75
As evident from the theoretical analysis, the main effort in our design of COLOGNE is to guarantee that samples can be generated in time linear in the graph size. 理論的解析から明らかなように、COLOGNEの設計における主な取り組みは、サンプルがグラフサイズで線形に時間内で生成できることを保証することである。 0.81
We chose such a basic prediction model as decision trees are the textbook example for interpretable machine learning. このような基本的な予測モデルを選択した。決定木は解釈可能な機械学習の教科書の例である。 0.65
It is worth noting that more accurate models can be obtained by using more advanced classification models. より高度な分類モデルを使用することで、より正確なモデルが得られることは注目に値する。 0.72
For example, using LightGBM (Ke et al, 2017), a highy efficient framework for Gradient Tree Boosting. 例えば、LightGBM (Ke et al, 2017)は、Gradient Tree Boostingのための高効率なフレームワークである。 0.78
However, such results can be highly dependent on hyperparameter tuning and it becomes challenging to guarantee a fair comparison between the different sampling approaches. しかし、このような結果はハイパーパラメータチューニングに大きく依存し、異なるサンプリングアプローチ間の公正な比較を保証することが困難になります。 0.72
Moreover, the models become much more difficult to interpret as in order to achieve good results one needs hundreds and sometimes thousands of trees for an optimal model. さらに、良い結果を得るためには、最適なモデルのために数百から数千の木が必要であると解釈することがより困難になる。 0.76
16 16 0.85
英語(論文から抽出)日本語訳スコア
Rules used to predict sample 1 with class 1: クラス1でサンプル1を予測するために使われるルール: 0.78
16 decision node 0 : (X_test[1, 16] = [’w-t’]) > 460.5) 17 decision node 9938 : (X_test[1, 17] = [’w-t’]) > 460.5) 36 decision node 10958 : (X_test[1, 36] = [’w-young’]) > 455.5) 37 decision node 11540 : (X_test[1, 37] = [’w-young’]) > 496.5) 46 decision node 11938 : (X_test[1, 46] = [’w-bb’]) <= 101.0) 35 decision node 11939 : (X_test[1, 35] = [’w-mous’]) > 266.5) 47 decision node 11955 : (X_test[1, 47] = [’w-bb’]) <= 85.0) 22 decision node 11956 : (X_test[1, 22] = [’w-inject’]) > 235.0) 32 decision node 11978 : (X_test[1, 32] = [’w-experiment’]) <= 341.5) 30 decision node 11979 : (X_test[1, 30] = [’w-observ’]) > 62.0) 24 decision node 11985 : (X_test[1, 24] = [’w-cell’]) <= 474.5) 11 decision node 11986 : (X_test[1, 11] = [’w-antigen’]) <= 426.0) ... prediction [1] 16 decision node 0 : (X_test[1, 16] = [’w-t’]) > 460.5) 17 decision node 9938 : (X_test[1, 17] = [’w-t’]) > 460.5) 36 decision node 10958 : (X_test[1, 36] = [’w-young’]) > 455.5) 37 decision node 11540 : (X_test[1, 37] = [’w-young’]) > 496.5) 46 decision node 11938 : (X_test[1, 46] = [’w-bb’]) <= 101.0) 35 decision node 11939 : (X_test[1, 35] = [’w-mous’]) > 266.5) 47 decision node 11955 : (X_test[1, 47] = [’w-bb’]) <= 85.0) 22 decision node 11956 : (X_test[1, 22] = [’w-inject’]) > 235.0) 32 decision node 11978 : (X_test[1, 32] = [’w-experiment’]) <= 341.5) 30 decision node 11979 : (X_test[1, 30] = [’w-observ’]) > 62.0) 24 decision node 11985 : (X_test[1, 24] = [’w-cell’]) <= 474.5) 11 decision node 11986 : (X_test[1, 11] = [’w-antigen’]) <= 426.0) ... prediction [1] 1.00
******************** ******************** ****** ******************** ******************** ****** 0.42
Rules used to predict sample 10000 with class 0: クラス 0 のサンプル 10000 の予測に使用されるルール: 0.83
16 decision node 0 : (X_test[10000, 16] = [’w-express’]) <= 460.5) 17 decision node 1 : (X_test[10000, 17] = [’w-nerv’]) <= 460.5) 30 decision node 2 : (X_test[10000, 30] = [’w-express’]) > 62.0) 32 decision node 856 : (X_test[10000, 32] = [’w-beta’]) > 56.0) 33 decision node 3178 : (X_test[10000, 33] = [’w-db’]) > 67.5) 4 decision node 4358 : (X_test[10000, 4] = [’w-revers’]) > 421.0) 5 decision node 6768 : (X_test[10000, 5] = [’w-revers’]) > 421.0) 31 decision node 7462 : (X_test[10000, 31] = [’w-express’]) > 62.0) 8 decision node 7530 : (X_test[10000, 8] = [’w-express’]) <= 444.0) 9 decision node 7531 : (X_test[10000, 9] = [’w-progress’]) <= 430.0) 44 decision node 7532 : (X_test[10000, 44] = [’w-express’]) > 21.0) 45 decision node 7760 : (X_test[10000, 45] = [’w-femal’]) > 37.5) ... prediction [0] 16 decision node 0 : (X_test[10000, 16] = [’w-express’]) <= 460.5) 17 decision node 1 : (X_test[10000, 17] = [’w-nerv’]) <= 460.5) 30 decision node 2 : (X_test[10000, 30] = [’w-express’]) > 62.0) 32 decision node 856 : (X_test[10000, 32] = [’w-beta’]) > 56.0) 33 decision node 3178 : (X_test[10000, 33] = [’w-db’]) > 67.5) 4 decision node 4358 : (X_test[10000, 4] = [’w-revers’]) > 421.0) 5 decision node 6768 : (X_test[10000, 5] = [’w-revers’]) > 421.0) 31 decision node 7462 : (X_test[10000, 31] = [’w-express’]) > 62.0) 8 decision node 7530 : (X_test[10000, 8] = [’w-express’]) <= 444.0) 9 decision node 7531 : (X_test[10000, 9] = [’w-progress’]) <= 430.0) 44 decision node 7532 : (X_test[10000, 44] = [’w-express’]) > 21.0) 45 decision node 7760 : (X_test[10000, 45] = [’w-femal’]) > 37.5) ... prediction [0] 0.99
Figure 5: The decision rules for a positive and a negative example. 図5: 肯定的かつ否定的な例に対する決定ルール。 0.71
17 17 0.85
英語(論文から抽出)日本語訳スコア
Figure 6: Micro and Macro F1 scores for node classification. 図6: ノード分類のためのマイクロおよびマクロF1スコア。 0.86
Best viewed in color. 色が一番よく見える。 0.75
18 18 0.85
英語(論文から抽出)日本語訳スコア
Figure 7: Distribution of words for a coordinate of the embedding vectors for each of the three node classes of Pubmed. 図7: Pubmedの3つのノードクラスのそれぞれに対する埋め込みベクトルの座標のための単語の分布。 0.84
7.4 Unsupervised learning 7.4 教師なし学習 0.53
Finally, we would like to provide an example how coordinated sampling can be used in an unsupervised setting. 最後に、監視されていない設定でコーディネートされたサンプリングをどのように使用できるかの例を示します。 0.52
For each node in Pubmed we sampled 100 such words using L1 sampling and random walks and, as there are 500 unique words (see Table 1), converted them to sparse binary vectors of dimensionality 50000. Pubmedの各ノードに対して、L1サンプリングとランダムウォークを用いて100個の単語をサンプリングし、500個のユニークな単語があるので(表1参照)、次元50000の疎二項ベクトルに変換した。 0.70
These vectors were clustered using scikit-learn’s K-means into 4 clusters using “k-means++” for initialization. これらのベクターはscikit-learnのk-meansを使用して4つのクラスタにクラスター化され、初期化には"k-means++"を使用する。 0.50
We collected the 6 most frequently appearing words in the node descriptions in each cluster and plot the normalized word frequencies in Figure 8. 各クラスタのノード記述において最も頻繁に現れる単語を6つ集め、図8の正規化単語頻度をプロットした。 0.83
Using L1 sampling in 3 of the 4 clusters we have clearly dominating words while this is not the case for random walk based vectors. 4つのクラスタのうち3つでl1サンプリングを使用することで、明確に単語を支配できるが、ランダムウォークベースのベクトルではそうではない。 0.59
(Note that the x-axis is on a logarithmic scale.) (X軸は対数スケールであることに注意。) 0.75
8 Conclusions and future work 8 結論と今後の課題 0.79
The paper lays the theoretical foundations for coordinated local graph sampling and argues that the approach can find practical applications by presenting experiments on real-life graphs. 本論文は局所グラフサンプリングの理論的基礎を概説し,本手法が実生活グラフの実験によって実用的応用を見出すことができることを論じる。 0.71
A deeper look into the graph structure can yield more insights into graph representation learning. グラフ構造をより深く調べると、グラフ表現学習により多くの洞察が得られます。 0.73
We made certain observations about the graph diameter and the performance of the different sampling strategies, yet more advanced concepts from graph theory will likely lead to a better understanding of the performance of the algorithms. 我々は、グラフの直径と異なるサンプリング戦略のパフォーマンスについて一定の観察を行ったが、グラフ理論のより高度な概念は、アルゴリズムのパフォーマンスをよりよく理解することになるだろう。 0.81
We would like to pose two open questions: 2つの疑問を提起したいと思います 0.64
1. Can we design interpretable node embeddings for known similarity measures between the local neighborhood frequency vectors? 1. 局所近傍周波数ベクトル間の既知の類似性測度に対する解釈可能なノード埋め込みを設計できるか? 0.78
For example, we can design a sketching algorithm to approximate the cosine similarity between k-hop frequency vectors of node pairs. 例えば、ノード対のkホップ周波数ベクトル間のコサイン類似性を近似するスケッチアルゴリズムを設計することができる。 0.84
Such an approach would build on the techniques we used in the proofs of Theorem 3 and Theorem 4. このようなアプローチは、Theorem 3 と Theorem 4 の証明で使用したテクニックに基づいて構築される。 0.85
But sketches will consist of counters, not of sampled nodes, so they won’t be interpretable. しかしスケッチは、サンプルノードではなくカウンタで構成されているので、解釈はできない。 0.70
2. Can we learn structural roles (Rossi et al, 2020) by assigning appropriate node attributes? 2. 適切なノード属性を割り当てることで、構造的役割(Rossi et al, 2020)を学べますか? 0.82
In particular, can we combine the sampling procedure with approaches for graph labeling such that we compute more informative node representations? 特に、より情報的なノード表現を計算できるように、サンプリング手順とグラフラベリングのアプローチを組み合わせられるか? 0.73
References Achlioptas P, Sch¨olkopf B, Borgwardt KM (2011) Two-locus association mapping in subquadratic time. 参考文献 Achlioptas P, Sch solkopf B, Borgwardt KM (2011) 準次時間における2点相関写像。 0.71
In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011, pp 726–734 第17回ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011, pp 726–734 に参加して 0.88
Agarwal PK, Cormode G, Huang Z, Phillips JM, Wei Z, Yi K (2013) Mergeable summaries. Agarwal PK, Cormode G, Huang Z, Phillips JM, Wei Z, Yi K (2013) Mergeable summaries。 0.80
ACM Trans Database Syst 38(4):26:1–26:28 ACMトランス Database Syst 38(4):26:1–26:28 0.69
Ahmed NK, Duffield NG, Willke TL, Rossi RA (2017) On sampling from massive graph streams. Ahmed NK, Duffield NG, Willke TL, Rossi RA (2017) 巨大なグラフストリームからのサンプリングについて。 0.91
Proc VLDB Endow 10(11):1430–1441 Proc VLDB 在位10(11)1430-1441 0.74
19 19 0.85
英語(論文から抽出)日本語訳スコア
Figure 8: Relative weight of the most significant words per cluster using vectors generated by random walk sampling (top) and L1 sampling (bottom) on a logarithmic scale. 図8: ランダムウォークサンプリング(トップ)とL1サンプリング(ボットム)を対数スケールで生成したベクトルを用いたクラスタ毎の最も重要な単語の相対重み。 0.85
20 20 0.85
英語(論文から抽出)日本語訳スコア
Alon N, Matias Y, Szegedy M (1999) The space complexity of approximating the frequency moments. Alon N, Matias Y, Szegedy M (1999) 周波数モーメントを近似する空間の複雑さ。 0.81
J Comput Syst Sci 58(1):137–147 J Comput Syst Sci 58(1):137–147 0.87
Backstrom L, Boldi P, Rosa M, Ugander J, Vigna S (2012) Four degrees of separation. Backstrom L, Boldi P, Rosa M, Ugander J, Vigna S (2012) 4次分離。 0.77
In: Web Science 2012, In: Web Science 2012に登場。 0.78
WebSci ’12, pp 33–42 WebSci ’12, pp 33–42 0.92
Becchetti L, Boldi P, Castillo C, Gionis A (2010) Efficient algorithms for large-scale local triangle counting. Becchetti L, Boldi P, Castillo C, Gionis A (2010) 大規模局所三角形カウントのための効率的なアルゴリズム。 0.86
ACM Trans Knowl Discov Data 4(3):13:1–13:28 ACM Trans Knowl Discov Data 4(3):13:1–13:28 0.72
Breitkreutz BJ, Stark C, Reguly T, et al (2008) The biogrid interaction database. Breitkreutz BJ, Stark C, Reguly T, et al (2008) バイオグリッド相互作用データベース。 0.77
Nucleic acids research pp 637–640 核酸の研究 pp 637–640 0.67
Broder AZ, Charikar M, Frieze AM, Mitzenmacher M (2000) Min-wise independent permutations. Broder AZ, Charikar M, Frieze AM, Mitzenmacher M (2000) Min-wise independent permutations。 0.90
J Comput Syst Sci 60(3):630–659 Jコンピュート Syst Sci 60(3):630–659 0.75
Cao S, Lu W, Xu Q (2015) Grarep: Learning graph representations with global structural information. Cao S, Lu W, Xu Q (2015) Grarep: グローバルな構造情報を用いたグラフ表現の学習。 0.90
In: Proceedings of the 24th ACM International Conference on Information and Knowledge Management, CIKM 2015, pp 891–900 第24回 ACM International Conference on Information and Knowledge Management, CIKM 2015, pp 891-900 に参加して 0.89
Charikar M, Chen KC, Farach-Colton M (2004) Finding frequent items in data streams. Charikar M, Chen KC, Farach-Colton M (2004) データストリームの頻繁な項目を見つける。 0.83
Theor Comput Sci Theor Comput Sci 0.85
312(1):3–15 312(1):3–15 0.78
Cohen E (2016) Coordinated sampling. Cohen E (2016) Coordinated sample。 0.80
In: Encyclopedia of Algorithms, pp 449–454 In: Encyclopedia of Algorithms, pp 449–454 0.96
Cormode G, Jowhari H (2019) Lp samplers and their applications: A survey. Cormode G, Jowhari H (2019) Lpサンプラーとその応用:調査。 0.67
ACM Comput Surv 52(1):16:1– ACM Comput Surv 52(1):16:1– 0.81
16:31 Feigenbaum J, Kannan S, McGregor A, Suri S, Zhang J (2005) On graph problems in a semi-streaming 16:31 Feigenbaum J, Kannan S, McGregor A, Suri S, Zhang J (2005) 半ストリーミングにおけるグラフ問題について 0.76
model. Theor Comput Sci 348(2-3):207–216 モデル。 Theor Comput Sci 348(2-3):207–216 0.76
Grover A, Leskovec J (2016) node2vec: Scalable feature learning for networks. Grover A, Leskovec J (2016) node2vec: ネットワークのためのスケーラブルな機能学習。 0.83
In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2016, pp 855–864 院:第22条の手続 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2016 pp 855–864 0.82
Hamilton WL, Ying Z, Leskovec J (2017) Inductive representation learning on large graphs. Hamilton WL, Ying Z, Leskovec J (2017) 大きなグラフ上の帰納的表現学習。 0.81
In: Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pp 1024–1034 In: Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pp 1024–1034 0.93
Ioffe S (2010) Improved consistent sampling, weighted minhash and L1 sketching. Ioffe S (2010) 一貫したサンプリング、重み付きminhash、L1スケッチを改善しました。 0.52
In: ICDM 2010, The 10th 内: ICDM 2010 第10回。 0.81
IEEE International Conference on Data Mining, IEEE Computer Society, pp 246–255 IEEE International Conference on Data Mining, IEEE Computer Society, pp 246–255 0.97
Jowhari H, Saglam M, Tardos G (2011) Tight bounds for lp samplers, finding duplicates in streams, and related problems. Jowhari H, Saglam M, Tardos G (2011) tight bounds for lp samplers, find copys in stream, and related problem。 0.71
In: Lenzerini M, Schwentick T (eds) Proceedings of the 30th ACM SIGMOD-SIGACTSIGART Symposium on Principles of Database Systems, PODS 2011, ACM, pp 49–58 Renzerini M, Schwentick T (eds) Proceedings of the 30th ACM SIGMOD-SIGACTSIGART Symposium on Principles of Database Systems, PODS 2011, ACM, pp 49-58 0.84
Karp RM, Shenker S, Papadimitriou CH (2003) A simple algorithm for finding frequent elements in streams Karp RM, Shenker S, Papadimitriou CH (2003) ストリーム中の頻繁な要素を見つけるための簡単なアルゴリズム 0.92
and bags. ACM Trans Database Syst 28:51–55 バッグも ACM Trans Database Syst 28:51–55 0.54
Ke G, Meng Q, Finley T, Wang T, Chen W, Ma W, Ye Q, Liu T (2017) Lightgbm: A highly efficient gradient Ke G, Meng Q, Finley T, Wang T, Chen W, Ma W, Ye Q, Liu T (2017) Lightgbm: 高効率グラデーション。 0.81
boosting decision tree. In: NIPS 2017, pp 3146–3154 決定木を高める。 内: NIPS 2017 pp 3146-3154 0.73
Kutzkov K, Pagh R (2013) On the streaming complexity of computing local clustering coefficients. Kutzkov K, Pagh R (2013) ローカルクラスタリング係数の計算のストリーミングの複雑さについて。 0.85
In: Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013, ACM, pp 677–686 院(6代) ACM International Conference on Web Search and Data Mining, WSDM 2013, ACM, pp 677–686 0.65
Mahoney M (2011) Large text compression benchmark. mahoney m (2011) 大規模テキスト圧縮ベンチマーク。 0.82
URL http://www.mattmahon ey.net/dc/textdata URL http://www.mattmahon ey.net/dc/textdata 0.39
McGregor A (2014) Graph stream algorithms: a survey. mcgregor a (2014) graph stream algorithm: a survey。 0.74
SIGMOD Rec 43(1):9–20 SIGMOD Rec 43(1):9–20 0.86
21 21 0.85
英語(論文から抽出)日本語訳スコア
Metwally A, Agrawal D, Abbadi AE (2005) Efficient computation of frequent and top-k elements in data streams. Metwally A, Agrawal D, Abbadi AE (2005) データストリームにおける頻繁かつ上位の要素の効率的な計算。 0.89
In: Database Theory - ICDT 2005, 10th International Conference, Springer, Lecture Notes in Computer Science, vol 3363, pp 398–412 In: Database Theory - ICDT 2005, 10th International Conference, Springer, Lecture Notes in Computer Science, vol 3363, pp 398–412 0.95
Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J (2013) Distributed representations of words and phrases and their compositionality. Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J (2013) 単語とフレーズの分散表現とその構成性。 0.74
In: Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013., pp 3111–3119 In: Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013., pp 3111–3119 0.96
Muthukrishnan S (2005) Data streams: Algorithms and applications. Muthukrishnan S (2005) データストリーム:アルゴリズムとアプリケーション。 0.77
Found Trends Theor Comput Sci 1(2) 発見トレンド theor comput sci 1(2) 0.76
Ou M, Cui P, Pei J, Zhang Z, Zhu W (2016) Asymmetric transitivity preserving graph embedding. Ou M, Cui P, Pei J, Zhang Z, Zhu W (2016) 非対称な過渡性保存グラフ埋め込み。 0.81
In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp 1105–1114 In: Proceings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016 pp 1105–1114 0.89
Pennington J, Socher R, Manning CD (2014) Glove: Global vectors for word representation. Pennington J, Socher R, Manning CD (2014) Glove: 単語表現のためのグローバルベクター。 0.84
In: Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, pp 1532– 1543 In: Proceings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014 pp 1532–1543 0.81
Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: online learning of social representations. Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: ソーシャル表現のオンライン学習。 0.87
In: The 20th ACM イン:第20回ACM 0.86
SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014, pp 701–710 SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014 pp 701–710 0.88
Qiu J, Dong Y, Ma H, Li J, Wang K, Tang J (2018) Network embedding as matrix factorization: Unifying DeepWalk, LINE, PTE, and node2vec. Qiu J, Dong Y, Ma H, Li J, Wang K, Tang J (2018) Network embedding as matrix factorization: Unifying DeepWalk, LINE, PTE, and node2vec。 0.85
In: Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, pp 459–467 In: Proceings of the 11th ACM International Conference on Web Search and Data Mining, WSDM 2018, pp 459–467 0.89
Rossi RA, Jin D, Kim S, Ahmed NK, Koutra D, Lee JB (2020) On proximity and structural role-based embeddings in networks: Misconceptions, techniques, and applications. Rossi RA, Jin D, Kim S, Ahmed NK, Koutra D, Lee JB (2020) ネットワーク内の近接および構造的役割ベースの埋め込みについて:誤解、テクニック、アプリケーション。 0.84
ACM Trans Knowl Discov Data 14(5):63:1–63:37 ACM Trans Knowl Discov Data 14(5):63:1–63:37 0.72
Sen P, Namata G, Bilgic M, Getoor L, Gallagher B, Eliassi-Rad T (2008) Collective classification in network Sen P, Namata G, Bilgic M, Getoor L, Gallagher B, Eliassi-Rad T (2008) ネットワークにおける集合分類 0.95
data. AI Mag 29(3):93–106 データだ AI Mag 29(3):93–106 0.78
Shrivastava A (2016) Simple and efficient weighted minwise hashing. shrivastava a (2016) simple and efficient weighted minwise hashing。 0.75
In: Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, pp 1498–1506 In: Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, pp 1498–1506 0.93
Shrivastava A, Li P (2014) Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). Shrivastava A, Li P (2014) Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS)。 0.78
In: Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, pp 2321–2329 In: Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014 pp 2321–2329 0.88
Sohangir S, Wang D (2017) Improved sqrt-cosine similarity measurement. Sohangir S, Wang D (2017) Sqrt-cosine類似度測定の改善。 0.79
J Big Data 4:25 J Big Data 4:25 0.84
Tang J, Qu M, Mei Q (2015a) PTE: predictive text embedding through large-scale heterogeneous text networks. Tang J, Qu M, Mei Q (2015a) PTE: 大規模な異種テキストネットワークによる予測テキスト埋め込み。 0.79
In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 1165–1174 第21回ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 1165–1174に参加して 0.91
Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q (2015b) LINE: large-scale information network embedding. Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q (2015b) LINE: 大規模情報ネットワークの組み込み。 0.86
In: Proceedings of the 24th International Conference on World Wide Web, WWW 2015, pp 1067–1077 In: Proceedings of the 24th International Conference on World Wide Web, WWW 2015 pp 1067–1077 0.92
Tsitsulin A, Mottin D, Karras P, M¨uller E (2018) VERSE: versatile graph embeddings from similarity measures. Tsitsulin A, Mottin D, Karras P, M suller E (2018) VERSE: 類似度尺度による汎用グラフ埋め込み。 0.84
In: Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, pp 539–548 In: 2018 World Wide Web Conference on World Wide Web, WWW 2018 pp 539–548の進捗状況 0.84
Wang X, Cui P, Wang J, Pei J, Zhu W, Yang S (2017) Community preserving network embedding. Wang X, Cui P, Wang J, Pei J, Zhu W, Yang S (2017) ネットワーク埋め込みを保存するコミュニティ。 0.82
In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017, pp 203–209 内 第30回AIAAI Conference on Artificial Intelligence, 2017, pp 203–209 に参加して 0.55
Watts D, Strogatz S (1998) Collective dynamics of ’small-world’ networks. watts d, strogatz s (1998) “small-world”ネットワークの集団ダイナミクス。 0.77
Nature (393):440–442 自然(393):440-442 0.72
22 22 0.85
英語(論文から抽出)日本語訳スコア
Wu W, Li B, Chen L, Zhang C (2018) Efficient attributed network embedding via recursive randomized hashing. Wu W, Li B, Chen L, Zhang C (2018) 帰納的ランダム化ハッシュによる効率的なネットワーク埋め込み。 0.82
In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, pp 2861–2867 第27回人工知能国際合同会議(ijcai 2018, pp 2861-2867)参加報告
訳抜け防止モード: 第20回-第7回人工知能国際会議報告 IJCAI 2018, pp 2861–2867
0.67
Yang D, Rosso P, Li B, Cudr´e-Mauroux P (2019) Nodesketch: Highly-efficient graph embeddings via recursive sketching. Yang D, Rosso P, Li B, Cudr ́e-Mauroux P (2019) Nodesketch: 再帰スケッチによる高効率グラフ埋め込み。 0.84
In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, pp 1162–1172 In:Proceings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, pp 1162–1172 0.95
Zafarani R, Liu H (2009) Connecting corresponding identities across communities. Zafarani R, Liu H (2009) コミュニティ間で対応するアイデンティティを接続する。 0.78
In: Proceedings of the In:Proceedings of the ~ 0.68
Third International Conference on Weblogs and Social Media, ICWSM 2009, The AAAI Press 第3回国際Weblogs and Social Media Conference, ICWSM 2009 AAAI Press 0.75
Zhang Z, Cui P, Wang X, Pei J, Yao X, Zhu W (2018) Arbitrary-order proximity preserved network embedding. Zhang Z, Cui P, Wang X, Pei J, Yao X, Zhu W (2018) 任意順序の近接保存ネットワーク埋め込み。 0.80
In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pp 2778–2786 第24回ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pp 2778-2786 に参加して 0.86
Zhou C, Liu Y, Liu X, Liu Z, Gao J (2017) Scalable graph embedding for asymmetric proximity. Zhou C, Liu Y, Liu X, Liu Z, Gao J (2017) 非対称近接のためのスケーラブルグラフ埋め込み。 0.85
In: Pro- ceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017, pp 2942–2948 In:Pro- 第30回AIAAI Conference on Artificial Intelligence, 2017, pp 2942-2948 に参加して 0.80
23 23 0.85
                                               ページの最初に戻る

翻訳にはFugu-Machine Translatorを利用しています。