論文の概要、ライセンス

# (参考訳) メッセージパッシンググラフニューラルネットワークの限界を破る [全文訳有]

Breaking the Limits of Message Passing Graph Neural Networks ( http://arxiv.org/abs/2106.04319v1 )

ライセンス: CC BY 4.0
Muhammet Balcilar, Pierre H\'eroux, Benoit Ga\"uz\`ere, Pascal Vasseur, S\'ebastien Adam, Paul Honeine(参考訳) メッセージパッシング(Graph)ニューラルネットワーク(MPNN)は、スパースグラフに適用されたノード数に関して線形複雑であるため、理論表現力は第1次Weisfeiler-Lehmanテスト(1-WL)に限定されているにもかかわらず、広く実装され、多くの関心を集めている。 本稿では,固有値の非線形なカスタム関数を用いてスペクトル領域でグラフ畳み込みを設計し,任意の大きな受容場をマスキングした場合,MPNNは理論上は1-WLテストよりも強力であり,既存の3-WLモデルと同じくらい強力であり,空間的局所化を保ったままであることを示す。 さらに、カスタムフィルタ関数を設計することにより、コンボリューションプロセスが与えられた入力グラフ信号とその関連する特性の間の異なる関係を学習できる様々な周波数成分を出力に持つことができる。 今のところ、最高の3WL等価グラフニューラルネットワークは$\mathcal{O}(n^3)$の計算複雑性を持ち、$\mathcal{O}(n^2)$のメモリ使用量では非局所的な更新機構を考慮し、出力プロファイルのスペクトルリッチ性を提供しない。 提案手法は上記の問題を全て克服し,多くのダウンストリームタスクで最先端に到達する。

Since the Message Passing (Graph) Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs, they have been widely implemented and still raise a lot of interest even though their theoretical expressive power is limited to the first order Weisfeiler-Lehman test (1-WL). In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues and masked with an arbitrary large receptive field, the MPNN is theoretically more powerful than the 1-WL test and experimentally as powerful as a 3-WL existing models, while remaining spatially localized. Moreover, by designing custom filter functions, outputs can have various frequency components that allow the convolution process to learn different relationships between a given input graph signal and its associated properties. So far, the best 3-WL equivalent graph neural networks have a computational complexity in $\mathcal{O}(n^3)$ with memory usage in $\mathcal{O}(n^2)$, consider non-local update mechanism and do not provide the spectral richness of output profile. The proposed method overcomes all these aforementioned problems and reaches state-of-the-art results in many downstream tasks.
公開日: Tue, 8 Jun 2021 13:26:56 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
1 2 0 2 n u J 1 2 0 2 n u J 0.85
8 ] G L . 8 ] G L。 0.81
s c [ 1 v 9 1 3 4 0 sc [ 1 v 9 1 3 4 0 0.68
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Muhammet Balcilar 1 2 Pierre H´eroux 1 Benoit Ga¨uz`ere 3 Pascal Vasseur 1 4 S´ebastien Adam 1 Paul Honeine 1 Muhammet Balcilar 1 2 Pierre H ́eroux 1 Benoit Ga 'uz`ere 3 Pascal Vasseur 1 4 S ́ebastien Adam 1 Paul Honeine 1 0.93
Abstract Since the Message Passing (Graph) Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs, they have been widely implemented and still raise a lot of interest even though their theoretical expressive power is limited to the first order Weisfeiler-Lehman test (1-WL). 概要 メッセージパッシング(Graph)ニューラルネットワーク(MPNN)は、スパースグラフに適用されたノード数に関して線形複雑であるため、理論表現力は第1次Weisfeiler-Lehmanテスト(1-WL)に限定されているにもかかわらず、広く実装され、多くの関心を集めている。 0.63
In this paper, we show that if the graph convolution supports are designed in spectral-domain by a nonlinear custom function of eigenvalues and masked with an arbitrary large receptive field, the MPNN is theoretically more powerful than the 1-WL test and experimentally as powerful as a 3-WL existing models, while remaining spatially localized. 本稿では,固有値の非線形なカスタム関数によってグラフ畳み込みがスペクトル領域で設計され,任意の大きな受容場が隠蔽されている場合,MPNNは理論上は1-WLテストよりも強力であり,既存の3-WLモデルと同じくらい強力であり,空間的局所化が保たれていることを示す。 0.71
Moreover, by designing custom filter functions, outputs can have various frequency components that allow the convolution process to learn different relationships between a given input graph signal and its associated properties. さらに、カスタムフィルタ関数を設計することにより、コンボリューションプロセスが与えられた入力グラフ信号とその関連する特性の間の異なる関係を学習できる様々な周波数成分を出力に持つことができる。 0.79
So far, the best 3-WL equivalent graph neural networks have a computational complexity in O(n3) with memory usage in O(n2), consider non-local update mechanism and do not provide the spectral richness of output profile. これまでの3WL相当グラフニューラルネットワークは、O(n2)のメモリ使用量とO(n3)の計算複雑性を持ち、非局所的な更新機構を考慮し、出力プロファイルのスペクトルリッチ性を提供しない。 0.74
The proposed method overcomes all these aforementioned problems and reaches state-of-the-art results in many downstream tasks. 提案手法は上記の問題を全て克服し,多くのダウンストリームタスクで最先端に到達する。 0.58
1. Introduction In the past few years, finding the best inductive bias for relational data represented as graphs has gained a lot of interest in the machine learning community. 1. はじめに 過去数年間、グラフとして表現される関係データの最も帰納的バイアスを見つけることは、機械学習コミュニティに大きな関心を集めてきた。 0.78
Node-based message passing mechanisms relying on the graph structure have given rise to the first generation of Graph Neural Networks (GNNs) called Message Passing Neural Networks (MPNNs) (Gilmer et al , 2017). グラフ構造に依存するノードベースのメッセージパッシング機構は、メッセージパッシングニューラルネットワーク(MPNN)と呼ばれる第1世代のグラフニューラルネットワーク(GNN)を生み出した(Gilmer et al , 2017)。 0.84
These algorithms spread each node features to the neighborhood nodes using train- これらのアルゴリズムは、列車を用いて各ノードの特徴を近隣ノードに広める。 0.59
1LITIS Lab, University of Rouen Normandy, France 2InterDigital, France 3LITIS Lab, INSA Rouen Normandy, France 4MIS Lab, Universit´e de Picardie Jules Verne, France. 1Litis Lab, France 2InterDigital, France 3Litis Lab, INSA Rouen Normandy, France 4MIS Lab, Universit ́e de Picardie Jules Verne, France 0.78
Correspondence to: Muhammet Balcilar <muhammetbalcilar@gma il.com>. 対応文: muhammet balcilar <muhammetbalcilar@gma il.com> 0.76
Proceedings of the 38 th International Conference on Machine Learning, PMLR 139, 2021. 第38回機械学習国際会議(PMLR 139, 2021)の開催報告 0.68
Copyright 2021 by the author(s). 著作者による著作権2021。 0.53
able weights. These weights can be shared with respect to the distance between nodes (Chebnet GNN) (Defferrard et al , 2016), to the connected nodes features (GAT for graph attention network) (Veliˇckovi´c et al , 2018) and/or to edge features (Bresson & Laurent, 2018). 重量もできる これらの重みは、ノード間の距離 (chebnet gnn) (defferrard et al , 2016) と接続されたノード機能 (gat for graph attention network) (velisckovi ́c et al , 2018) とエッジ機能 (bresson & laurent, 2018) で共有することができる。 0.69
When considering sparse graphs, the memory and computational complexity of such approaches are linear with respect to the number of nodes. スパースグラフを考えると、そのようなアプローチのメモリと計算の複雑さはノードの数に対して線形である。 0.77
As a consequence, these algorithms are feasible for large sparse graphs and thus have been applied with success on many downstream tasks (Dwivedi et al , 2020). その結果、これらのアルゴリズムは大きなスパースグラフに対して実現可能であり、多くの下流タスク(Dwivedi et al , 2020)で成功している。 0.80
Despite these successes and these interesting computational properties, it has been shown that MPNNs are not powerful enough (Xu et al , 2019). これらの成功とこれらの興味深い計算特性にもかかわらず、MPNNは十分に強力ではないことが示されている(Xu et al , 2019)。 0.68
Considering two nonisomorphic graphs that are not distinguishable by the first order Weisfeiler-Lehman test (known as the 1-WL test), existing maximum powerful MPNNs embed them to the same point. ワイスフェイラー・リーマン検定(英語版)(Weisfeiler-Lehman test 1-WL test)によって区別できない2つの非同型グラフを考えると、既存の最大パワーMPNNはそれらを同じ点に埋め込む。
訳抜け防止モード: 第一次Weisfeiler-Lehman test (1-WL test として知られる)で区別できない2つの非同型グラフを考える。 既存の最大出力MPNNはそれらを同じポイントに埋め込む。
0.67
Thus, from a theoretical expressive power point of view, these algorithms are not more powerful than the 1-WL test. したがって、理論的な表現力の観点からすると、これらのアルゴリズムは1-WLテストほど強力ではない。 0.71
Beyond the graph isomorphism issue, it has also been shown that many other combinatorial problems on graph cannot be solved by MPNNs (Sato et al , 2019). グラフ同型問題以外にも、グラフ上の他の組合せ問題の多くがMPNNでは解決できないことが示されている(Sato et al , 2019)。 0.78
In (Maron et al , 2019b; Keriven & Peyr´e, 2019), it has been proven that in order to reach universal approximation, higher order relations are required. Maron et al , 2019b; Keriven & Peyr ́e, 2019)では、普遍近似に到達するためには高次関係が必要であることが証明されている。 0.83
In this context, some powerful models that are equivalent to the 3-WL test were proposed. この文脈では、3WLテストと同等の強力なモデルが提案されている。 0.67
For instance, (Maron et al , 2019a) proposed the model PPGN (Provably Powerful Graph Network) that mimics the second order Folklore WL test (2-FWL), which is equivalent to the 3-WL test. 例えば (Maron et al , 2019a) は、3-WL テストと同等の2階の Folklore WL テスト (2-FWL) を模倣する PPGN (Provably Powerful Graph Network) モデルを提案した。 0.82
In (Morris et al , 2019), they proposed to use message passing between 1, 2 and 3 order node tuples hierarchically, thus reaching the 3-WL expressive power. 2019年のmorris et alでは、1、2、3桁のノードタプルを階層的にメッセージパッシングを使用することを提案し、3wlの表現力に到達した。
訳抜け防止モード: Morris et al, 2019 では,メッセージパッシングを 1, 2 から 3 のノードタプルを階層的に使用することを提案した。 これにより3WL表現力に到達する。
0.66
However, using such relations makes both memory usage and computational complexities grown exponentially. しかし、そのような関係を用いることで、メモリ使用量と計算の複雑さが指数関数的に増大する。 0.55
Thus, it is not feasible to have universal approximation models in practice. したがって、実際には普遍近似モデルを持つことは不可能である。 0.67
In order to increase the theoretical expressive power of MPNNs by keeping the linear complexity mentioned above, some researchers proposed to partly randomize node features (Abboud et al , 2020; Sato et al , 2020) or to add a unique label (Murphy et al , 2019) in order to have the ability to distinguish two non-isomorphic graphs that are not distinguished by the 1-WL test. 上記の線形複雑性を保ち、MPNNの理論的表現力を高めるために、ある研究者は、ノードの特徴(Abboud et al , 2020; Sato et al , 2020)を部分的にランダム化するか、または1-WLテストで区別されない2つの非同型グラフを区別する能力を得るために、ユニークなラベル(Murphy et al , 2019)を追加することを提案した。 0.73
These solutions need massively training samples and involve slow convergence. これらの解はサンプルを大量に訓練し、収束を遅くする。 0.58
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
(Bouritsas et al , 2020; Dasoulas et al , 2020) proposed to use a preprocessing step to extract some features that cannot be extracted by MPNNs. (Bouritsas et al , 2020; Dasoulas et al , 2020) は,MPNNが抽出できないいくつかの特徴を抽出するために,事前処理ステップを使用することを提案した。 0.74
Thus, the expressive power of their GNN is improved. これにより、GNNの表現力が改善される。 0.76
However, these handcrafted features need domain expertise and a feature selection process among an infinite number of possibilities. しかし、これらの手作りの機能は、無限の可能性の中でドメインの専門知識と機能選択プロセスを必要とします。 0.53
All these studies target more theoretically powerful models, closer to universal approximation. これらの研究はすべて、普遍近似に近い理論上より強力なモデルをターゲットにしている。 0.58
However, this does not always induce a better generalization ability. しかし、これは必ずしもより良い一般化能力をもたらすとは限らない。 0.61
Since most of the realistic problems are given with many node/edge features (which can be either continuous or discrete), there is almost no pair of graphs that are not distinguishable by the 1-WL test in practice. 現実的な問題の多くは、多くのノード/エッジ機能(連続的あるいは離散的のいずれか)で与えられるため、実際には1-wlテストでは区別できないグラフのペアはほとんど存在しない。 0.78
In addition, theoretically more powerful methods use non-local updates, breaking one of the most important inductive bias in Euclidean learning named locality principle (Battaglia et al , 2018). さらに理論上、より強力な方法は非局所的な更新を使用し、ユークリッド学習において局所性原理(Battaglia et al , 2018)と呼ばれる最も重要な帰納バイアスを破る。 0.60
These may explain why theoretical powerful methods cannot outperform MPNNs on many downstream tasks, as reported in (Dwivedi et al , 2020). これは、理論的な強力な手法が多くの下流タスクでmpnnを上回らない理由を説明している(dwivedi et al , 2020)。 0.61
On the other hand, it is obvious that 1-WL equivalent GNNs are not expressive enough since they are not able to count some simple structural features such as cycles or triangles (Arvind et al , 2020; Chen et al , 2020; Bouritsas et al , 2020; Vignac et al , 2020), which are informative for some social or chemical graphs. 一方、1-WL相当のGNNは、循環や三角形(Arvind et al , 2020; Chen et al , 2020; Bouritsas et al , 2020; Vignac et al , 2020)のような単純な構造的特徴を数えることができないため、表現力に乏しいことは明らかである。
訳抜け防止モード: 一方、1-WL相当のGNNは、サイクルや三角形のような単純な構造的特徴(Arvind et al, 2020; Chen et al, 2020; Bouritsas et al)を数えることができないため、十分に表現できないことは明らかである。 2020 ; Vignac et al, 2020 )は、いくつかの社会的または化学的なグラフの情報を伝達する。
0.85
Finally, another important aspect mentioned by a recent paper (Balcilar et al , 2021) concerns the spectral ability of GNN models. 最後に、最近の論文(Balcilar et al , 2021)で言及されているもうひとつの重要な側面は、GNNモデルのスペクトル能力に関するものである。 0.62
It is shown that a vast majority of the MPNNs actually work as low-pass filters, thus reducing their expressive power. MPNNの大多数が実際にローパスフィルタとして機能し、表現力を減らすことが示されている。 0.74
In this paper, we propose to design graph convolution in the spectral domain with custom non-linear functions of eigenvalues and by masking the convolution support with desired length of receptive field. 本稿では,固有値の独自の非線形関数を持つスペクトル領域におけるグラフ畳み込みの設計と,所望の受容場長で畳み込み支援をマスキングすることを提案する。 0.75
In this way, we have (i) a spatially local updates process, (ii) linear memory and computational complexities (except the eigendecomposition in preprocessing step), (iii) enough spectral ability and (iv) a model that is theoretically more powerful than the 1-WL test, and experimentally as powerful as PPGN. この方法では、(i)空間的に局所的な更新プロセス、(ii)線形メモリと計算複雑性(前処理ステップにおける固有分解を除く)、(iii)十分なスペクトル能力、(iv)理論上1-WLテストよりも強力で実験的にPPGNと同じくらい強力であるモデルを持つ。 0.84
Experiments show that the proposed model can distinguish pairs of graphs that cannot be distinguished by 1-WL equivalent MPNNs. 実験の結果,提案モデルでは1-WL相当MPNNでは区別できないグラフのペアを区別できることがわかった。 0.70
It is also able to count some substructures that 1-WL equivalent MPNNs cannot. また、1-WL相当MPNNではできない部分構造を数えることもできる。 0.76
Its spectral ability enables to produce various kind of spectral components in the output, while the vast majority of the GNNs including higher order WL equivalent models do not. そのスペクトル能力は出力中に様々な種類のスペクトル成分を生成できるが、高次WL等価モデルを含むGNNの大部分はそうではない。 0.75
Finally, thanks to the sparse matrix multiplication, it has linear time complexity except the eigendecomposition in preprocessing step. 最後に、スパース行列乗法により、前処理ステップにおける固有分解を除いて線形時間複雑性を持つ。 0.71
The paper is structured as follows. 紙の構造は以下の通りである。 0.73
In Section 2, we set the notations and the general framework used in the following. 第2節では、下記の表記法と一般的な枠組みを定めている。 0.64
Section 3 is dedicated to the characterization of WL test, which is the backbone of our theoretical analysis. 第3節では, 理論解析のバックボーンであるWL試験の特徴について述べる。 0.72
It is followed by our findings in Section 4 on analysing the expressive power of MPNNs and our solutions to improve 第4節ではMPNNの表現力と改善のためのソリューションについて分析している。 0.68
expressive power of MPNNs in Section 5. 第5節におけるMPNNの表現力 0.80
The experimental results and conclusion are the last two section of this paper. 実験結果と結論は,本論文の最後の2節である。 0.80
2. Generalization of Spectral and Spatial 2. スペクトルと空間の一般化 0.82
MPNN Let G be a graph with n nodes and an arbitrary number of edges. MPNN G を n 個のノードと任意の数の辺を持つグラフとする。 0.84
Connectivity is given by the adjacency matrix A ∈ {0, 1}n×n and features are defined on nodes by X ∈ Rn×f0, with f0 the length of feature vectors. 連結性は隣接行列 a ∈ {0, 1}n×n によって与えられ、特徴は x ∈ rn×f0 で定義され、f0 は特徴ベクトルの長さである。 0.80
For any matrix X, we used Xi, X:j and Xi,j to refer to its i-th column vector, j-th row vector and (i, j)-th entry, respectively. 任意の行列 X に対して、Xi, X:j, Xi,j をそれぞれ i 番目の列ベクトル、j 番目の行ベクトル、および (i, j) 番目のエントリを参照するために用いた。
訳抜け防止モード: 任意の行列 X に対して、Xi, X : j および Xi, j を用いて、その i - th 列ベクトルを参照した。 j - th 行ベクトルと (i, j)-th エントリ。
0.83
A graph Laplacian is given by L = D − A (or L = I − D−1/2AD−1/2) where D ∈ Rn×n is the diagonal degree matrix and I is the identity. グラフラプラシアン (graph laplacian) は l = d − a (または l = i − d −1/2ad−1/2) によって与えられる。
訳抜け防止モード: グラフラプラシアンは L = D − A ( で与えられる。 または L = I − D−1/2AD−1/2 ) D ∈ Rn×n は対角次数行列であり、I は恒等式である。
0.73
Through an eigendecomposition, L can be written by L = U diag(λ)U T where each column of U ∈ Rn×n is an eigenvector of L, λ ∈ Rn gathers the eigenvalues of L and diag(·) creates a diagonal matrix whose diagonal elements are from a given vector. 固有分解を通して、L は L = U diag(λ)U T で書くことができ、U ∈ Rn×n の各列は L の固有ベクトルであり、λ ∈ Rn は L の固有値を集め、 diag(·) は対角要素が与えられたベクトルから得られる対角行列を生成する。 0.85
We use superscripts to refer to vectors or matrices evolving through iterations or layers. スーパースクリプトを使って、イテレーションやレイヤを通じて進化するベクトルや行列を指しています。 0.51
For instance, H (l) ∈ Rn×fl refers to the node representation on layer l whose feature dimension is fl. 例えば、H (l) ∈ Rn×fl は、特徴次元が fl である層 l 上のノード表現を指す。 0.71
GNN models rely on a set of layers where each layer takes the node representation of the previous layer H (l−1) as input and produces a new representation H (l), with H (0) = X. GNNモデルは、各層が前の層 H (l−1) のノード表現を入力として取り、H (0) = X で新しい表現 H (l) を生成するような一連の層に依存している。 0.82
According to the domain which is considered to design the layer computations, GNNs are generally classified as either spectral or spatial (Wu et al , 2019; Chami et al , 2020). 層計算を設計すると考えられる領域によると、GNNは一般にスペクトルまたは空間に分類される(Wu et al , 2019; Chami et al , 2020)。 0.78
Spectral GNNs rely on the spectral graph theory (Chung, 1997). スペクトルGNNはスペクトルグラフ理論に依存している(Chung, 1997)。 0.85
In this framework, signals on graphs are filtered using the eigendecomposition of the graph Laplacian (Shuman et al , 2013). この枠組みでは、グラフ上の信号はグラフラプラシアン(shuman et al , 2013)の固有分解を用いてフィルタリングされる。 0.82
By transposing the convolution theorem to graphs, the spectral filtering in the frequency domain can be defined by xf lt = U diag(Ω(λ))U(cid:62)x, where Ω(.) 畳み込み定理をグラフに変換することにより、周波数領域におけるスペクトルフィルタリングは xf lt = U diag(Ω(λ))U(cid:62)x で定義される。
訳抜け防止モード: 畳み込み定理をグラフに変換することにより、周波数領域におけるスペクトルフィルタリングは xf lt = U diag(Ω(λ))U(cid:62)x で定義される。 Ω ( )。
0.85
is the desired filter function which needs to be learnt by backpropagation. バックプロパゲーションによって学習する必要があるフィルタ関数です。 0.73
On the other hand, spatial GNNs, such as GCN (graph convolutional network) (Kipf & Welling, 2017) and GraphSage (Hamilton et al , 2017), consider two operators, one that aggregates the connected nodes messages and one that updates the concerned node representation. 一方、GCN (graph convolutional network) (Kipf & Welling, 2017) や GraphSage (Hamilton et al , 2017) のような空間的なGNNでは、接続されたノードのメッセージを集約する2つの演算子と、関連するノードの表現を更新する1つを考える。 0.82
In a recent paper (Balcilar et al , 2021), it was explicitly shown that both spatial and spectral GNNs are MPNN, taking the general form 最近の論文(Balcilar et al , 2021)では、空間的GNNとスペクトル的GNNの両方がMPNNであることが明らかに示されており、一般的な形を取っている。
訳抜け防止モード: 最近の論文(Balcilar et al, 2021)では、 明らかに 空間GNNとスペクトルGNNはどちらもMPNNであり、一般的な形をとります
0.84
(cid:16)(cid:88) (cid:16)(cid:88) 0.75
C (s)H (l)W (l,s)(cid:17) C(s)H(l)W(l,s)(cid:1 7) 0.92
H (l+1) = σ H (l+1) = σ 0.92
, (1) s where C (s) ∈ Rn×n is the s-th convolution support that defines how the node features are propagated to the neighboring nodes and W (l,s) ∈ Rfl×fl+1 is the trainable matrix for the l-th layer and s-th support. , (1) s c (s) ∈ rn×n は s-th 畳み込みサポートであり、ノードの特徴が隣接ノードにどのように伝播するかを定義し、w (l,s) ∈ rfl×fl+1 は l-th 層と s-th サポートの訓練可能な行列である。 0.82
Within this generalization, GNNs differ from each other by the design of the convolution supports C (s). この一般化の中で、GNNはC(s)をサポートする畳み込みの設計によって異なる。 0.65
If the supports are designed in the サポートが設計されている場合 0.83
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
spectral domain by Φs(λ), the convolution support needs to be written as C (s) = U diag(Φs(λ))U(cid:62). スペクトル領域は s(λ) で、畳み込みのサポートは C (s) = U diag(\s(λ))U(cid:62) と書く必要がある。 0.76
One can see that as long as C (s) matrices are sparse (number of edges is defined by some constant multiplied by the number of nodes), MPNN in Eq 1 has linear memory and computational complexities with respect to the number of nodes. C(s)行列がスパースである限り(エッジの数はノード数によって乗算される定数によって定義される)、Eq 1のMPNNはノード数に関して線形メモリと計算複雑性を持つ。 0.75
Because, the valid entries in C (s) that we need to keep is linear with respect to the number of nodes and thank to the sparse matrix multiplication C (s)H (l) takes linear time with respect to the number of edges thus nodes as well. なぜなら、私たちが維持する必要がある C (s) の有効なエントリは、ノード数に関して線型であり、スパース行列乗法 C (s)H (l) のおかげで、ノード数に関しても線形時間を要するからである。
訳抜け防止モード: なぜなら、私たちが維持する必要があるC ( s ) の有効なエントリは、ノードの数に関して線形であるからである。 そして、スパース行列乗法 C ( s)H ( l ) に感謝すると、ノードのエッジの数に関して線形時間を要する。
0.81
3. Characterization of Weisfeiler-Lehman The universality of a GNN is based on its ability to embed two non-isomorphic graphs to distinct points in the target feature space. 3. Weisfeiler-Lehman の特徴づけ GNN の普遍性は、2つの非同型グラフを対象特徴空間の異なる点に埋め込む能力に基づいている。 0.82
A model that can distinguish all pairs of nonisomorphic graphs is a universal approximator. 非同型グラフのすべての対を区別できるモデルは普遍近似である。 0.84
Since the graph isomorphism problem is NP-intermediate (Takapoui & Boyd, 2016), the Weisfeiler-Lehman Test (abbreviated WL-test), which gives sufficient but not enough evidence of graph isomorphism, is frequently used for characterizing GNN expressive power. グラフ同型問題はNP中間体 (Takapoui & Boyd, 2016) であるため、グラフ同型性の十分な証拠を与えるWeisfeiler-Lehman Test (WL-test) は、GNN表現力を特徴づけるために頻繁に用いられる。 0.79
The classical vertex coloring WL test can be extended by taking into account higher order of node tuple within the iterative process. 古典的な頂点カラー化WLテストは、反復過程におけるノードタプルの高次性を考慮して拡張することができる。 0.78
These extensions are denoted as k-WL test, where k is equals to the order of the tuple. これらの拡張は k-WL テストと呼ばれ、k はタプルの順序に等しい。 0.67
These tests are described in Appendix A. これらのテストは appendix a に記述される。 0.65
It is shown in (Arvind et al , 2020) that for k ≥ 2, (k + 1)WL > (k)-WL, i.e., higher order of tuple leads to a better ability to distinguish two non-isomorphic graphs. Arvind et al , 2020) では、k ≥ 2, (k + 1)WL > (k)-WL に対して、タプルの高次性は2つの非同型グラフを区別する能力を向上させることが示されている。 0.82
For k = 1, this statement is not true, and 2-WL is not more powerful than 1-WL (Maron et al , 2019a). k = 1 の場合、この主張は真ではなく、2-WL は 1-WL (Maron et al , 2019a) よりも強力ではない。 0.77
To clarify this point, the Folkore WL (FWL) test has been defined such that 1-WL=1-FWL, but for k ≥ 2, we have (k + 1)-WL ≈ (k)-FWL (Maron et al , 2019a). この点を明らかにするために、Folkore WL (FWL) テストは 1-WL=1-FWL と定義されるが、k ≥ 2 については (k + 1)-WL > (k)-FWL (Maron et al , 2019a) を持つ。 0.84
In literature, some confusions occur among the two versions. 文学では2つのバージョンの間に混乱が生じている。 0.65
Some papers use WL test order (Morris et al , 2019; Maron et al , 2019a), while others use FWL order under the name of WL such as in (Abboud et al , 2020; Arvind et al , 2020; Takapoui & Boyd, 2016). 一部の論文では、WLテストオーダー (Morris et al , 2019; Maron et al , 2019a) や、in (Abboud et al , 2020; Arvind et al , 2020; Takapoui & Boyd, 2016) といった WL の名で FWL のオーダーを使用している。 0.90
In this paper, we explicitly mention both WL and FWL equivalent. 本稿では,WLとFWLの両等価性について述べる。 0.79
In order to better understand the capability of WL tests, some papers attempt to characterize these tests using a first order logic (Immerman & Lander, 1990; Barcel´o et al , 2019). WLテストの能力をよりよく理解するために、一階述語論理を用いてこれらのテストを特徴づけようとする論文もある(Immerman & Lander, 1990; Barcel ́o et al , 2019)。 0.73
Consider two unlabeled and undirected graphs represented by their adjacency matrices AG and AH. 隣接行列 AG と AH で表されるラベルのない2つの無向グラフを考える。 0.66
These two graphs are said k-WL (or k-FWL) equivalent, and denoted AG ≡k−W L AH, if they are indistinguishable by a k-WL (or k-FWL) test. これら2つのグラフは k-WL (または k-FWL) と同値であり、もし k-WL (または k-FWL) テストで区別できないなら AG シュク-W L AH と表記される。 0.66
Recently (Brijder et al , 2019; Geerts, 2020) proposed a new Matrix Language called MATLANG. 最近(Brijder et al , 2019; Geerts, 2020)は、MATLANGと呼ばれる新しいマトリックス言語を提案した。 0.81
This language includes different operations on matrices and makes some この言語は行列の異なる操作を含み、いくつかのものを作る 0.59
explicit connections between specific dictionaries of operations and the 1-WL and 3-WL tests. 特定の操作辞書と1-WLおよび3-WLテストの間の明示的な接続。 0.65
Expressive power varies with the operations included in each dictionnary. 表現力は各辞書に含まれる操作によって異なる。 0.68
Definition 1. M L(L) is a matrix language with an allowed operation set L = {op1, . 定義1。 M L(L) は、許容演算集合 L = {op1, . を持つ行列言語である。 0.77
. . opn}, where opi ∈ {., +,(cid:62) , diag, tr, 1,(cid:12),×, f}. . . opi ∈ {., +,(cid:62) , diag, tr, 1,(cid:12),×, f} である。 0.79
The possible operations are matrices multiplication and addition, matrix transpose, vector diagonalization, matrix trace computation, column vector full of 1, element-wise matrix multiplication, matrix/scalar multiplication and element-wise custom function operating on scalars or vectors. 可能な操作は、行列乗算と加算、行列変換、ベクトル対角化、行列トレース計算、列ベクトルで満たされた1個の要素ワイド行列乗算、行列/スカラー乗算、スカラーまたはベクトルで動作する要素ワイドカスタム関数である。
訳抜け防止モード: 可能な操作は、行列乗法と加算、行列変換である。 ベクトル対角化、行列トレース計算、列ベクトル 1 要素-賢行列乗法 matrix / scalar multiplication and element - スカラーやベクトルで動作する賢明なカスタム関数。
0.79
Definition 2. e(X) ∈ R is a sentence in M L(L) if it consists of any possible consecutive operations in L, operating on a given matrix X and resulting in a scalar value. 定義 2. e(X) ∈ R が M L(L) の文であるとは、それが L における任意の連続的な操作からなり、与えられた行列 X 上で作用し、スカラー値をもたらすことである。 0.71
As an example, e(X) = 1(cid:62)X 21 is a sentence of M L(L) with L = {.,(cid:62) , 1}, computing the sum of all elements of square matrix X. 例えば、e(X) = 1(cid:62)X 21 は L = {.,(cid:62) , 1} の M L(L) の文で、平方行列 X のすべての元の和を計算する。 0.75
In the following, we are interested in languages L1,L2 and L3 that have been used for characterizing the WL-test in (Geerts, 2020). 以下に示すように、WLテストの特徴付けに使われている言語L1,L2,L3に興味を持っている(Geerts, 2020)。 0.69
These results are given next. 結果は次のようになる。 0.68
Remark 1. Two adjacency matrices are indistinguishable by the 1-WL test if and only if e(AG) = e(AH ) for all e ∈ L1 with L1 = {.,(cid:62) , 1, diag}. 備考1。 L1 = {.,(cid:62) , 1, diag} を持つすべての e ∈ L1 に対して e(AG) = e(AH ) が成り立つときのみである。
訳抜け防止モード: 備考1。 2つの隣接行列が 1-WL テストで区別できないのは、e(AG ) = e(AH ) が L1 = { .,(cid:62 ) を持つすべての e ∈ L1 に対してのみである。 1 , diag }。
0.62
Hence, all possible sentences in L1 are the same for 1-WL equivalent adjacency matrices. したがって、L1 のすべての可能な文は 1-WL 相当の隣接行列に対して同じである。 0.60
Thus, AG ≡1−W L AH ↔ AG ≡M L(L1) AH. したがって、AG は 1−W L AH は AG は L(L1) AH である。 0.63
(see Theorem 7.1 in (Geerts, 2020)) Remark 2. (Theorem 7.1 in (Geerts, 2020)を参照。 0.77
M L(L2) with L2 = {.,(cid:62) , 1, diag, tr} is strictly more powerful than L1, i.e., than the 1-WL test, but less powerful than the 3-WL test. L2 = {.,(cid:62) , 1, diag, tr} の M L(L2) は 1-WL テストよりも L1 よりも厳密に強力であるが、3-WL テストよりも強力ではない。 0.93
(see Theorem 7.2 and Example 7.3 in (Geerts, 2020)) Remark 3. (Theorem 7.2 および Example 7.3 in (Geerts, 2020) 参照。 0.86
Two adjacency matrices are indistinguishable by the 3-WL test if and only if they are indistinguishable by any sentence in M L(L3) with L3 = {.,(cid:62) , 1, diag, tr,(cid:12)}. 2つの隣接行列が3WLテストで区別不能であることと、L3 = {.,(cid:62) , 1, diag, tr,(cid:12)} で M L(L3) の任意の文で区別不能であることは同値である。 0.76
Thus, AG ≡3−W L AH ↔ AG ≡M L(L3) AH. したがって、AG は 3−W L AH は AG は L(L3) AH である。 0.63
(see Theorem 9.2 in (Geerts, 2020)) Remark 4. (定理9.2(geerts, 2020)参照)remark 4を参照。 0.75
Enriching the operation set to L+ = L ∪ {+,×, f} where L ∈ (L1,L2,L3) does not improve the expressive power of the language. L ∈ (L1,L2,L3) が言語表現力を向上しないとき、L+ = L > {+,×, f} に集合する演算を豊かにする。 0.85
Thus, AG ≡M L(L) AH ↔ AG ≡M L(L+) AH. これにより、AG >M L(L)AH > AG >M L(L+)AHとなる。 0.61
(see Proposition 7.5 in (Geerts, 2020)) (命題7.5 in(ゲルト、2020年)参照) 0.72
4. How Powerful are MPNNs? 4. MPNNはどのくらい強力か? 0.79
This section presents some results about the theoretical expressive power of state-of-the-art MPNNs. 本稿では,最先端MPNNの理論的表現力について述べる。 0.66
Those results are derived using the MATLANG language (Geerts, 2020) and more precisely the remarks of the preceding section. これらの結果は、MATLANG言語(Geerts, 2020)と、より正確には前節の発言を用いて導出される。 0.71
Proofs of the theorems are given in Appendix B. Theorem 1. 定理の証明は appendix b. theorem 1 で与えられる。 0.75
MPNNs such as GCN, GAT, GraphSage, GIN (defined in Appendix H) cannot go further than operations in L+ 1 . GCN、GAT、GraphSage、GIN(Appendix Hで定義されている)のようなMPNNは、L+1の操作以上には進めない。 0.69
Thus, they are not more powerful than the 1-WL test. したがって、それらは1-WLテストほど強力ではない。 0.72
This result has already been given in (Xu et al , 2019), which proposed GIN- (GIN for Graph Isomorphism Network) and この結果は (Xu et al , 2019) ですでに与えられており、GIN-\ (GIN for Graph Isomorphism Network) と提案されている。 0.81
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
showed that it is the unique MPNN which is provably exact the same powerful with the 1-WL test, while the rest of MPNNs are known to be less powerful than 1-WL test. 1-WLテストとまったく同じ強度を持つユニークなMPNNであることを示し、残りのMPNNは1-WLテストよりも強力ではないことが知られている。 0.86
Chebnet is also known to be not more powerful than the 1-WL test. Chebnetは1-WLテストほど強力ではないことも知られている。 0.79
However, the next theorem states that it is true if the maximum eigenvalues are the same for both graphs. しかし、次の定理は、最大固有値が両方のグラフに対して同じであるときに真であると述べる。 0.71
For a pair of graphs whose maximum eigenvalues are not equal, Chebnet is strictly more powerful than the 1-WL test. 最大固有値が等しくないグラフのペアに対して、Chebnetは1-WLテストよりも厳密に強力である。 0.75
Theorem 2. Chebnet is more powerful than the 1-WL test if the Laplacian maximum eigenvalues of the non-regular graphs to be compared are not the same. 定理2。 chebnetは、比較対象の非正則グラフのラプラシアン最大固有値が同じでない場合、1-wlテストよりも強力である。 0.68
Otherwise Chebnet is not more powerful than 1-WL. そうでなければ、Chebnetは1-WLほど強力ではない。 0.55
Figure 1. Decalin (G) and Bicyclopentyl (H) graphs are L1 and also 1-WL equivalent, but Chebnet can distinguish them. 図1。 Decalin (G) と Bicyclopentyl (H) のグラフは L1 で 1-WL と等価であるが、Chebnet はそれらを区別できる。 0.75
Figure 1 shows two graphs that are 1-WL equivalent and are generally used to show how MPNNs fail. 図1は1-WL相当の2つのグラフを示し、一般的にMPNNの失敗を示すために使用される。 0.69
However, their normalized Laplacian’s maximum eigenvalues are not the same. しかし、それらの正規化されたラプラシアンの最大固有値は同じではない。 0.55
Thus, Chebnet can project these two graphs to different points in feature space. したがって、Chebnetはこの2つのグラフを特徴空間の異なる点に投影することができる。 0.63
Details can be found in Appendix C. As stated in the introduction, comparison with the WL-test is not the only way to characterize the expressive power of GNNs. 紹介で述べたように、WL-testとの比較は、GNNの表現力を特徴づける唯一の方法ではない。
訳抜け防止モード: 詳細はAppendix Cで確認できる。 WLとの比較 - テストは、GNNの表現力を特徴づける唯一の方法ではない。
0.62
Powerful GNNs are also expected to be able to count relevant substructures in a given graph for specific problems. 強力なGNNはまた、特定の問題に対して特定のグラフ内の関連するサブ構造を数えることができると期待されている。
訳抜け防止モード: 強力なGNNも期待されている 特定の問題に対するグラフ内の関連する部分構造を数えることができる。
0.73
The following theorems describe the matrix language required to be able to count the graphlets illustrated in Figure 2, which are called 3-star, triangle, tailed triangle and 4-cycle. 以下の定理は、図2で示されるグラフレットを数えるために必要な行列言語を記述するもので、3つ星、三角形、尾三角形、および4サイクルと呼ばれる。 0.68
Figure 2. Sample of patterns: 3-star, triangle, tailed triangle and 4-cycle graphlets used in our analysis. 図2。 パターンのサンプル:3つ星、三角形、尾付き三角形、および分析に使用される4サイクルグラフレット。 0.72
Theorem 3. 3-star graphlets can be counted by sentences in L+ 1 . 理論3。 3つ星グラフレットはL+1の文で数えられる。 0.59
Theorem 4. Triangle and 4-cycle graphlets can be counted by sentences in L+ 2 . 理論4。 三角形と4サイクルグラフレットは l+ 2 の文で数えることができる。 0.64
Theorem 5. Tailed triangle graphlets can be counted by sentences in L+ 3 . 理論5。 テーラー三角形のグラフレットは L+ 3 の文で数えられる。 0.63
These theorems show that 1-WL equivalent MPNNs can only count 3-star patterns, while 3-WL equivalent MPNNs can count all graphlets shown in Figure 2. これらの定理は、1-WL相当MPNNが3つ星のパターンのみを数えることができる一方で、3-WL等価MPNNは図2に示す全てのグラフレットを数えることができることを示している。 0.52
(Dehmamy et al , 2019) has shown that a MPNN is not able to learn node degrees if the MPNN has not an appropriate convolution support (e g A). (Dehmamy et al , 2019)は、MPNNが適切な畳み込みサポート(例えばA)を受けていない場合、MPNNはノード学位を学習できないことを示した。 0.76
Therefore, to achieve a fair comparison, we assume that node degrees are included as a node feature. したがって、公平な比較を行うために、ノードの次数がノードの特徴として含まれていると仮定する。 0.63
Note however, that the number of 3-star graphlets centered on a node can be directly derived from its degrees (see Appendix B.3). ただし、ノード中心の3つ星グラフレットの数は、その次数から直接導出することができる(付録b.3を参照)。 0.69
Therefore, any graph agnostic MLP can count the number of 3-star graphlets given the node degree. したがって、任意のグラフに依存しない MLP は、ノード次数が与えられた3つ星グラフレットの数を数えることができる。 0.51
5. MPNN Beyond 1-WL In this section, we present two new MPNN models. 5. MPNN Beyond 1-WL この節では2つの新しいMPNNモデルを紹介します。 0.79
The first one, called GNNML1 is shown to be as powerful as the 1-WL test. GNNML1と呼ばれる最初のものは、1-WLテストと同じくらい強力である。 0.84
The second one, called GNNML3 exploits the theoretical results of (Geerts, 2020) to break the limits of 1WL and reach 3-WL equivalence experimentally. 2つめのgnnml3は(geerts, 2020)の理論結果を利用して1wlの限界を破り、実験的に3wl同値に達する。 0.63
GNNML1 relies on the node update schema given by : GNNML1は以下のノード更新スキーマに依存している。 0.74
H (l+1)=σ(H (l)W (l,1)+AH (l)W (l,2)+H (l)W (l,3)(cid:12)H (l)W (l,4)) H(l+1)=σ(H(l)W(l,1)+AH(l)W(l,2)+H(l)W(l,3)(cid:12)H( l)W(l,4)) 0.83
(2) where W (l,s) are trainable parameters. 2) W (l,s) はトレーニング可能なパラメータである。 0.75
Using this model, the new representation of a node consists of a sum of three terms : (i) a linear transformation of the previous layer representation of the node, (ii) a linear transformation of the sum of the previous layer representations of its connected nodes and (iii) the element-wise multiplication of two different linear transformations of the previous layer representation of the node. このモデルを用いて、ノードの新しい表現は、3つの項からなる: (i) ノードの前のレイヤ表現の線形変換、 (ii) 接続されたノードの前のレイヤ表現の合計の線形変換、および (iii) ノードの前のレイヤ表現の2つの異なる線形変換の要素ごとの乗算。 0.71
The expressive power of GNNML1 is defined by the following theorem. GNNML1の表現力は以下の定理によって定義される。 0.74
Its proof is given in Appendix B: Theorem 6. その証明は Appendix B: Theorem 6 で与えられる。 0.83
GNNML1 can produce every possible sentences in M L(L1) for undirected graph adjacency A with monochromatic edges and nodes. GNNML1 は単色エッジとノードを持つ無向グラフ隣接 A に対して M L(L1) で可能なすべての文を生成することができる。 0.65
Thus, GNNML1 is exactly as powerful as the 1-WL test. したがって、GNNML1は1-WLテストと同じくらい強力である。 0.74
Hence, this model has the same ability as the 1-WL test to distinguish two non-isomorphic graphs, i.e., the same as GIN. したがって、このモデルはGINと同一の2つの非同型グラフを区別する1-WLテストと同じ能力を持つ。 0.81
This is explained by the third term in the sum of Eq (2) since it can produce feature-wise multiplication on each layer. これは、eq (2) の和の3番目の項で説明される。
訳抜け防止モード: これは eq (2 ) の和の3番目の項で説明される。 各レイヤにフィーチャー - 賢明な乗算を生成できる。
0.72
Since node representation is richer, we also assume that it would be more powerful for counting substructures. ノード表現はよりリッチであるため、サブストラクチャを数えるのに強力であると仮定する。 0.63
This assumption is validated by experiments in Section 6. この仮定は第6節で実験によって検証される。 0.64
To reach more powerful models than 1-WL, theoretical results (see Remarks 1, 2 and 3 in Section 3) show that a model that can produce different outputs than L+ 1 language is needed. 1-WLよりも強力なモデルに到達するためには、理論的な結果(第3節第1、第2、第3節参照)は、L+1言語とは異なる出力を生成できるモデルが必要であることを示している。
訳抜け防止モード: 1-WLよりも強力なモデルに到達する 理論的結果(第3節第1、第2、第3節参照)は、 L+ 1言語とは異なる出力を生成できるモデルが必要になります。
0.79
More precisely, according to Remarks 2 and 3, trace (tr) and element-wise multiplication ((cid:12)) operations are required to go further than 1-WL. より正確には、Remarks 2 と 3 によれば、トレース (tr) と要素ワイド乗算 ((cid:12)) 演算は 1-WL を超えて進む必要がある。 0.66
In order to illustrate the impact of the trace operation, one can use 1-WL equivalent Decalin and Bicyclopentyl graphs in Figure 1. トレース演算の影響を説明するために、図1の1-WL相当のデカリングラフとビシクロペンチルグラフを使用することができる。 0.79
G) = 0 but H ) = 20, tr(A5) giving the number of 5-length closed tr(A5 g) = 0 but h ) = 20 tr(a5) 5 長閉じた tr(a5) の数を与える。 0.87
It is easy to show that tr(A5 tr(A5) は容易に示せる。 0.78
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
walks. Thus, if a model can apply a trace operator over some power of adjacency, it can easily distinguish these two graphs. 歩く。 したがって、モデルがいくつかの隣接の力に対してトレース演算子を適用できれば、これらの2つのグラフを容易に区別することができる。 0.65
Computational details concerning this example are given in Appendix C. この例に関する計算の詳細は、Appendix Cで述べられている。 0.67
Figure 3. Cospectral and 4-regular graphs from (Van Dam & Haemers, 2003) are L1 and L2 equivalent. 図3。 Van Dam & Haemers, 2003) と 4-正則グラフは L1 と L2 の同値である。 0.78
Despite this interesting property of the trace operator, it is not sufficient to distinguish cospectral graphs, since cospectral graphs (see Figure 3) have the same number of closed walks of any length (see Proposition 5.1 in (Geerts, 2020)). トレース作用素のこの興味深い性質にもかかわらず、コスペクトルグラフ(図3参照)は任意の長さのクローズドウォークの同じ数であるため、コスペクトルグラフを区別することは十分ではない(Proposition 5.1 in (Geerts, 2020) を参照)。 0.77
In such cases, element-wise multiplication is useful. そのような場合、要素の乗算は有用である。 0.66
As an example, the sentence e(A) = 1(cid:62)f ((A (cid:12) A2)21) where f (x) = x (cid:12) x for any vector x, gives e(AG) = 6032 and e(AH ) = 5872 for the graphs of Figure 3. 例えば、任意のベクトル x に対して f (x) = x (cid:12) x の文 e(A) = 1(cid:62)f ((A (cid:12) A2)21) は、図 3 のグラフに対して e(AG) = 6032 と e(AH ) = 5872 を与える。 0.94
Thus, elementwise multiplication helps distinguishing these two graphs. したがって、要素分解による乗算はこれらの2つのグラフの区別に役立つ。 0.49
The calculation details can be found in Appendix D. As shown by these examples, a model enriched by elementwise multiplication and trace operator can go further than the 1-WL test. これらの例で示すように、要素乗算とトレース演算子によってリッチ化されたモデルは、1-WLテストよりさらに進むことができる。 0.72
However, these operations need to keep the power of the adjacency matrix explicitly and to multiply these dense matrices to each other by matrix or element-wise multiplication. しかし、これらの演算は隣接行列のパワーを明示的に保ち、これらの密行列を行列や要素の乗算によって互いに乗算する必要がある。 0.61
Such a strategy is actually used by higher order GNNs such as (Maron et al , 2019a; Morris et al , 2019), which are provably more powerful than existing MPNNs. このような戦略は、既存のMPNNよりも確実に強力なGNN(Maron et al , 2019a; Morris et al , 2019)によって実際に使用されている。 0.89
However, MPNNs cannot calculate the power of a given adjacency explicitly. しかし、MPNNは与えられた隣接性の力を明示的に計算することはできない。 0.54
Indeed, a MPNN layer multiplies the previous representation of the nodes by sparse adjacency matrix or more generally sparse convolution supports C in Eq (1). 実際、MPNN層がノードの以前の表現をスパース隣接行列またはより一般にスパース畳み込みによって乗算し、Eq (1)でCをサポートする。 0.72
More precisely, if the given node features are H (0) = 1, a MPNN can calculate C 31 by 3 layered MPNN computing C(C(C1)) but not by (C 3)1. より正確には、与えられたノード特徴が H (0) = 1 であれば、MPNN は C 31 を C(C(C1)) で計算できるが、(C3)1 では計算できない。 0.78
Since a MPNN does not keep C 3 explicitly, it cannot take its trace or multiply element-wise to another power of support. MPNNはC3を明示的に保持しないため、そのトレースや乗算を他のサポートのパワーに持っていくことはできない。 0.70
This is a major disadvantage of MPNNs, but it explains why MPNNs need just linear time and memory complexity, making them useful in practice. MPNNにとってこれは大きな欠点であるが、MPNNが線形時間とメモリの複雑さだけを必要としている理由を説明している。 0.78
A solution to the problem mentioned above is to design graph convolution supports by the element-wise multiplication of the s-power of the adjacency matrix and a given receptive field, i.e., by C (s) = M (cid:12) As where M masks the components of the powered matrix and keeps the convolution support sparse. 上述の問題の解は、隣接行列のs-パワーと与えられた受容体、すなわちc (s) = m (cid:12) によって要素的に乗算されたグラフ畳み込みを、m がパワー付き行列の成分をマスクし、畳み込みサポートをスパースし続けるように設計することである。 0.72
M = A + I is an example of mask that gives a maximum 1-length receptive field. M = A + I は最大 1 長の受容体を与えるマスクの例である。 0.78
This model cannot calculate all possible element-wise multiplications between all possible matrices, but it can produce any sentence in a form of (M (cid:12) As)l where l ∈ [0, lmax] is the このモデルはすべての可能な行列の間のすべての要素ごとの乗算を計算することはできないが、任意の文を (m (cid:12) as)l の形に生成することができる。 0.77
layer number and s ∈ [0, smax] is the pre-computed power of convolution supports. 層数と s ∈ [0, smax] は畳み込みサポートの事前計算力である。 0.66
In this proposition, the receptive field mask and the number of power of adjacency should be computed in a pre-processing step. この提案では、受動的フィールドマスクと隣接のパワーの数を前処理ステップで計算する必要がある。 0.73
However, we cannot initially know which power of adjacency matrix is necessary for a given problem. しかし、与えられた問題に対して、随伴行列のどのパワーが必要かは、当初知ることができない。 0.54
One solution is to tune it as an hyperparameter of the model. 一つの解決策はモデルのハイパーパラメータとしてチューニングすることだ。 0.70
Another problem of this approach is that using powers of adjacency makes the convolution supports filled with high values that have to be normalized. このアプローチのもう1つの問題は、隣接性を利用して畳み込みを正規化しなければならない高い値で満たすことである。
訳抜け防止モード: このアプローチのもうひとつの問題は 隣り合う力を利用することで 畳み込みは 正規化すべき高い値で 支えられます
0.66
To overcome these problems, we propose through our GNNML3 model to design convolution supports in the spectral domain as functions of eigenvalues of the normalized Laplacian matrix or of the adjacency matrix. これらの問題を解決するため、GNNML3モデルを用いてスペクトル領域における畳み込み支援を正規化ラプラシア行列あるいは隣接行列の固有値の関数として設計する。 0.78
The following theorem, with proof given in Appendix B, shows that such supports can be written as power series of the graph Laplacian or the adjacency matrix. 下記の定理は、付録 b で示される証明とともに、そのようなサポートがグラフラプラシアンまたは隣接行列のパワー級数として書けることを示している。 0.74
Theorem 7. A convolution support given by C(cid:48)(s) = U diag(Φs(λ))U(cid:62), 理論7。 c(cid:48)(s) = u diag(φs(λ))u(cid:62) で与えられる畳み込み支援 0.69
(3) where Φs(λ) = exp(−b(λ − fs)2), fs ∈ [λmin, λmax] is a scalar design parameter of each convolution support and b > 0 is a general scalar design parameter, can be expressed as a linear combination of all powers of graph Laplacian (or adjacency) as follows, with αs,i = Φ(i) (3) φs(λ) = exp(−b(λ − fs)2), fs ∈ [λmin, λmax] は各畳み込みサポートのスカラー設計パラメータであり、b > 0 は一般的なスカラー設計パラメータであり、グラフラプラシアン(または隣接)のすべてのパワーの線形結合として、αs,i = φ(i) で表現できる。 0.82
: s (0) i! : s (0) i! 0.85
C(cid:48)(s) = αs,0L0 + αs,1L1 + αs,2L2 + . C(cid:48)(s) = αs,0L0 + αs,1L1 + αs,2L2 + 。 0.53
. . . (4) Since design parameters fs of each matrix are different, each C(cid:48)(s) in Eq (4) consists of different linear combinations of power series of the graph Laplacian (or adjacency). . . . (4) 各行列の設計パラメータfsは異なるので、eq (4) の各 c(cid:48)(s) はグラフラプラシアン(または隣接)のべき級数の異なる線形結合からなる。 0.82
Thus, necessary powers of the graph Laplacian (or adjacency) and its diagonal part (for trace operation) can be learned and their element-wise multiplication can be produced by: C = M (cid:12) mlp4 (mlp1(C(cid:48))|mlp2(C(cid:48)) (cid:12) mlp3(C(cid:48))) , (5) where C(cid:48) = [C(cid:48)(1)| . C = M (cid:12) mlp4 (mlp1(C(cid:48))|mlp2(C(cid:48)) (cid:12) mlp3(C(cid:48))) , (5) ここで C(cid:48) = [C(cid:48)(1)| である。
訳抜け防止モード: したがって、グラフラプラシアン(または隣接)に必要な力 そしてその対角部(トレース操作のために)は学べる c = m (cid:12 ) mlp4 (mlp1(c(cid:48))|mlp2(c(cid:48 ) ) (cid:12 ) mlp3(c(cid:48 ) ) ) (5 ) ここで c(cid:48 ) = [ c(cid:48)(1)| である。
0.80
. .|C(cid:48)(s)] ∈ Rn×n×S stacks initial convolution supports on the third dimension, mlpk(.) . .|C(cid:48)(s)] ∈ Rn×n×S スタック 初期畳み込みは3次元 mlpk(.) をサポートする。 0.85
is a trainable model performed on third dimension of a given tensor, C = [C (1)| . 与えられたテンソルの3次元上で実行される訓練可能なモデル C = [C (1)| である。 0.73
. .|C (S)] ∈ Rn×n×S sparsify convolution support by defined receptive field mask M. The forward (cid:17) calculation of one layer MPNN becomes: . .|C (S)] ∈ Rn×n×S sparsify convolution support by defined receptive field mask M. the forward (cid:17) calculation of one layer MPNN。 0.86
(C (s)H (l)W (l,s))|mlp5(H (l))(cid:12)mlp6(H (l)) (6) where we concatenate MPNN representation under learned convolution with element-wise product of node representations as in GNNML1. (C (s)H (l)W (l,s))|mlp5(H (l))(cid:12)mlp6(H (l)) (6) ここで、学習畳み込みの下でMPNN表現をGNNML1のようなノード表現の要素的積と結合する。 0.78
There is an infinite number of selections of Φs(λ) that make the convolution support written by power series of graph Laplacian (or adjacency). グラフラプラシアン (Laplacian) のパワー級数(または隣接性)によって記述された畳み込みサポートを成すような λs(λ) の選択は無限である。 0.67
However, we can design each convolution support to be sensitive on each band of spectrum しかし、各スペクトル帯に敏感な各畳み込みサポートを設計できる。
訳抜け防止モード: しかし、私たちはそれぞれの畳み込みサポートを設計できます。 それぞれのスペクトル帯に敏感であるさま
0.64
(cid:16)(cid:88) (cid:16)(cid:88) 0.75
H (l+1) = σ H (l+1) = σ 0.92
s s 0.85
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
Algorithm 1 GNNML3 Preprocessing Step アルゴリズム1 GNNML3 前処理ステップ 0.78
Input: adjacency A ∈ Rn×n, receptive field mask M ∈ {0, 1}n×n, number of supports S ∈ N, frequency responses function of each support Φ1(λ) . 入力:adjacency A ∈ Rn×n,ceptive field mask M ∈ {0, 1}n×n, number of support S ∈ N, frequency response function of each support s1(λ) 。 0.82
. . ΦS(λ) Output: extracted edge features C(cid:48) ∈ Rm×S Set basis matrix: B = I − D−1/2AD−1/2 or B = A. Eigendecomposition: U diag(λ)U(cid:62) = B for s = 1 to S do . . φs(λ) 出力: 抽出された辺特徴 c(cid:48) ∈ rm×s 基底行列: b = i − d−1/2ad−1/2 あるいは b = a. eigendecomposition: u diag(λ)u(cid:62) = b for s = 1 to s do 0.83
:s = sparse2vec(cid:0)M (cid:12) (U diag(Φs(λ))U(cid:62))(cid:1) :s = sparse2vec(cid:0)M (cid:12) (U diag(\s(λ))U(cid:62))(cid:1) 0.85
C(cid:48) end for c(cid:48) 終止符 0.72
Algorithm 2 GNNML3 Forward calculation アルゴリズム2 GNNML3 前向き計算 0.89
Input: extracted edge features C(cid:48) ∈ Rm×S, initial node feature H (0) ∈ Rn×f0, receptive field mask M ∈ {0, 1}n×n, number of layers L, number of supports S Output: new node representation H (L) for l = 0 to L − 1 do 入力:抽出エッジ特徴 C(cid:48) ∈ Rm×S, 初期ノード特徴 H(0) ∈ Rn×f0, 受容フィールドマスク M ∈ {0, 1}n×n, レイヤ数 L, サポート数 S 出力: l = 0 から L − 1 に対する新しいノード表現 H(L) 0.79
˜C=mlpl,4(mlpl,1(C(cid: 48))|mlpl,2(C(cid:48))(ci d:12)mlpl,3(C(cid:48 ))) for s = 1 to S do c=mlpl,4(mlpl,1(c(cid: 48))|mlpl,2(c(cid:48))(ci d:12)mlpl,3(c(cid:48 ))) s = 1 から s do 0.71
C(s)=vec2sparse( ˜C:s,M ) C(s)=vec2sparse( >C:s,M ) 0.87
end for H(l+1)=σ((cid:80) 終止符 H(l+1)=σ((cid:80) 0.70
end for s(C(s)H(l)W (l,s))|mlpl,5(H(l))(cid:12) mlpl,6(H(l))) 終止符 s(C(s)H(l)W(l,s))|mlpl,5(H(l))(cid:12) mlpl,6(H(l)) 0.80
(fs) by given bandwidth (b). (fs) 与えられた帯域幅(b) 0.80
Therefore, our model will be able to learn properties depending on the spectrum of graph signal. したがって、このモデルでは、グラフ信号のスペクトルに応じて特性を学習することができる。 0.79
Algorithm 1 calculates the initial convolution supports (C(cid:48)). アルゴリズム1は、初期畳み込み支援(C(cid:48))を算出する。 0.68
Since the supports are computed for valid indices in the receptive field mask (where Mi,j = 1), one can see C(cid:48) as extracted edge features where the edge indices are defined by M. In application, a function sparse2vec : Rn×n → Rm converts the sparse matrix to a vector by just keeping the components on valid indices of the mask. サポートは受容的フィールドマスク(mi,j = 1)で有効なインデックスとして計算されるので、c(cid:48) は、エッジインデックスが m で定義される抽出されたエッジ特徴として見ることができる。
訳抜け防止モード: 支持体は受容野マスク(mi,)の有効な指標として計算される。 j = 1 ) c(cid:48 ) を抽出されたエッジ特徴として見ることができる。 エッジインデックスはmによって定義されます。 関数 sparse2vec : rn×n → rm はスパース行列をベクトル by に変換する マスクの有効なインデックスに 部品を入れておくだけ
0.86
Algorithm 2 shows the forward calculation of the model for just one graph. アルゴリズム2は、1つのグラフに対するモデルの前方計算を示す。 0.86
To make the representation as simple as possible, we prefer to use tensor representation in Eq (5). 表現をできるだけ簡単にするために、eq (5) でテンソル表現を使うことを推奨する。 0.67
However, implementation of Algorithm 2 just apply mlpk(.) しかし、アルゴリズム2の実装はmlpk()を適用すればよい。 0.65
to the valid indices defined by receptive field mask M. Thus, C, C(cid:48) have the dimension of Rm×S, where m shows number of valid indices in M and mlpk(.) したがって、C, C(cid:48) は Rm×S の次元を持ち、m は M と mlpk() における有効な指標の数を示す。
訳抜け防止モード: 受容フィールドマスクMで定義された有効な指標に対して。 C, C(cid:48 ) は Rm×S の次元を持ち、m は M と mlpk ( ) における有効な指標の数を示す。
0.78
applies on columns of C(cid:48). Cの列に適用される(cid:48)。 0.69
Beside, we use a function vec2sparse : Rm → Rn×n that converts the vector to the sparse convolution support according to a given mask M. The limit of the proposed method is similar to the limit of 3-WL (or 2-FWL) test. また、与えられたマスクMに応じてベクトルをスパース畳み込み支援に変換する関数 vec2sparse : Rm → Rn×n を用いる。
訳抜け防止モード: また、与えられたマスク M に従ってベクトルをスパース畳み込み支援に変換する関数 vec2sparse : Rm → Rn×n を用いる。 提案手法の限界は3-WL(または2-FWL)試験の限界に類似している。
0.87
For instance, it fails to distinguish strongly regular graphs, that can be defined by 3 parameters: the degree of the nodes, the number of common neighbours of adjacent node pairs, and the number of common neighbours of non-adjacent node pairs. 例えば、ノードの次数、隣接ノードペアの共通近傍の数、非隣接ノードペアの共通近傍の数という3つのパラメータで定義されるような、強い正則グラフの区別に失敗する。 0.65
Such graphs are provably known to be 3-WL equivalent (Arvind et al , 2020). そのようなグラフは3-WL同値であることが証明できる(Arvind et al , 2020)。 0.73
In Appendix E, a strongly regular graphs pair and the result of a sample sentence in L3 are presented. Appendix Eでは、強い正則グラフ対とL3のサンプル文の結果が提示される。 0.70
6. Experimental Results This section presents the experimental results obtained by the proposed models GNNML1 and GNNML3. 6. 実験結果 提案したモデル GNNML1 と GNNML3 による実験結果について述べる。 0.83
All codes and datasets are available online 1. すべてのコードとデータセットがオンラインで利用可能だ。 0.58
We use GCN, GAT, GIN and Chebnet as 1-WL MPNN baselines and PPGN as 3-WL baseline (see Appendix H). 我々はGCN, GAT, GIN, Chebnetを1-WL MPNNベースラインとして, PPGNを3-WLベースラインとして使用しています(Appendix H参照)。 0.64
Experiments aim to answer four questions: Q1: How many pairs of non-isomorphic simple graphs that are either 1-WL or 3-WL equivalent are not distinguished by the models? q1: 1-wl または 3-wl同値である非同型な単純グラフのペアは、モデルによって区別されないだろうか? 0.71
Q2: Can the models generalize the counting of some substructures in a given graph? Q2: 与えられたグラフのいくつかの部分構造の数え上げを一般化できるか? 0.73
Q3: Can the models learn low-pass, high-pass and bandpass filtering effects and generalize the classification problem according to the frequency of the signal? Q3: 低域通過, 高域通過, 帯域通過フィルタの効果を学習し, 信号の周波数に応じて分類問題を一般化できるか? 0.81
Q4: Can the models generalize downstream graph classification and regression tasks? Q4: モデルは下流のグラフ分類と回帰タスクを一般化できますか? 0.73
In order to perform experimental expressive power tests, we use graph8c and sr25 datasets2. 実験的な表現力テストを行うには、Graph8cとsr25データセットを使用します。 0.66
Graph8c is composed of all the 11 117 possible connected non-isomorphic simple graphs with 8 nodes. Graph8cは8ノードを持つ117個の連結非同型単純グラフからなる。 0.72
We compare all possible pairs of graphs of this dataset, leading to more than 61M comparisons. このデータセットのすべての可能なグラフを比較し、6100万以上のグラフを比較します。 0.64
According to our test, we found that 312 pairs out of 61M are 1-WL equivalent and none of the pairs are 3-WL equivalent. 実験の結果,61Mのうち312組は1-WL同値であり,いずれも3-WL同値ではないことがわかった。 0.63
The sr25 dataset contains strongly regular graphs where each graph has 25 nodes, each node’s degree is 12, connected nodes share 5 common neighbours and nonconnected nodes share 6 common neighbors. sr25データセットは、各グラフに25のノードがあり、各ノードの次数は12であり、連結ノードは5つの共通隣人を共有し、非連結ノードは6つの共通隣人を共有する。 0.73
Sr25 consists of 15 graphs, leading to 105 different pairs for comparison. Sr25は15のグラフから構成され、105の異なるペアが比較される。 0.74
Moreover, we use the EXP dataset (Abboud et al , 2020), having 600 pairs of 1-WL equivalent graphs. さらに、600対の1-WL相当グラフを持つEXPデータセット(Abboud et al , 2020)を用いる。 0.79
This dataset also includes a binary classification task. このデータセットにはバイナリ分類タスクも含まれている。 0.60
Depending on graph features, each graph of a pair of 1-WL equivalent graphs is assigned to two different classes. グラフの特徴により、1-wl等価グラフのペアの各グラフは2つの異なるクラスに割り当てられる。 0.78
We split the dataset into 400, 100, and 100 pairs for train, validation and test sets respectively. データセットは、トレイン、バリデーション、テストセットのためにそれぞれ400、100、100のペアに分割しました。 0.68
The test set is used to measure the generalization ability: a model that fails to distinguish 1-WL equivalent graphs inevitably fails to learn this task. テストセットは一般化能力を測定するために使われる: 1-WL相当グラフの区別に失敗するモデルは、必然的にこのタスクを学習しない。 0.70
We use 3-layer graph convolution followed by sum readout layer, and then a linear layer to convert the readout layer representation into a 10-length feature vector. 我々は3層グラフの畳み込みに続いて和読み出し層を使用し、次に線形層を用いて読み出し層表現を10長の特徴ベクトルに変換する。 0.78
We keep the parameter budget around 30K for all methods. パラメータの予算は、すべてのメソッドで約30Kです。 0.67
For graph8c, sr25 and EXP tasks, there is no learning. Graph8c、sr25、EXPタスクでは、学習はありません。 0.68
Model weights are randomly initialized and 10-length graph representations are compared by the Manhattan distance. モデルウェイトはランダムに初期化され、10長グラフ表現はマンハッタン距離で比較される。 0.72
If the distance is less than 10−3 in all 100 independent runs, we assume the pairs are similar. もし距離が 100 個の独立ランで 10−3 未満であれば、ペアは類似していると仮定する。 0.70
For EXP-classification task, we train the model and pick the best one according to validation set performance and report its performance on test set. EXP分類タスクでは、モデルのトレーニングを行い、検証セットのパフォーマンスに応じて最適なモデルを選択し、テストセットにその性能を報告する。 0.76
1https://github.com/ balcilar/gnn-matlang 2http://users.cecs.a nu.edu.au/∼bdm/data/graphs.html 1https://github.com/ balcilar/gnn-matlang 2http://users.cecs.a nu.edu.au/\bdm/data/ graphs.html 0.22
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
Table 1. Number of undistinguished pairs of graphs in graph8c, sr25 and EXP datasets and binary classification accuracy on EXP dataset. 表1。 Graph8c、sr25、EXPデータセットにおける未確認グラフのペア数とEXPデータセット上のバイナリ分類精度。 0.71
An ideal method does not find any pair similar and classifies graphs with 100% accuracy. 理想的な方法は類似した対を見つけず、100%精度でグラフを分類する。 0.72
The number of pairs is 61M for graph8c, 105 pairs for sr25 and 600 for EXP. graph8cのペア数は61m、sr25の105ペア、expの600ペアである。 0.65
MODEL GRAPH8C モデル Graph8C 0.56
SR25 EXP EXP-CLASSIFY SR25 EXP EXP-CLASSIFY 0.74
MLP GCN GAT GIN CHEBNET PPGN GNNML1 GNNML3 MLPGCN GAT GINCHEBNET PPGN GNNML1 GNNML3 0.74
293K 4775 1828 386 44 0 333 0 293K 4775 1828 386 44 0 333 0 0.94
105 105 105 105 105 105 105 105 105 105 105 105 105 105 105 105 0.85
600 600 600 600 71 0 600 0 600 600 600 600 71 0 600 0 0.85
50% 50% 50% 50% 82% 100% 50% 100% 50% 50% 50% 50% 82% 100% 50% 100% 0.85
Table 1 presents the obtained results. 表1は、得られた結果を示す。 0.67
One can see that 99.5% of the graphs in graph8c dataset can be distinguished even by graph agnostic method MLP (293K out of 61M is not separable by MLP). Graph8cデータセットの99.5%のグラフは、グラフに依存しないMDP(61Mのうち293KはMPPでは分離できない)でも区別できる。 0.71
This can be explained by the fact that the node degrees has been added as node features. これはノードの次数がノードの特徴として追加されたという事実によって説明できる。 0.72
Hence, all methods initially know the result of first iteration of 1-WL test. したがって、全てのメソッドは最初は1-WLテストの最初のイテレーションの結果を知っている。 0.66
Thus, MLP (and also first iteration of 1-WL test) can distinguish pairs of graphs when multiset of node degrees are not same. したがって、MLP(および1-WLテストの最初のイテレーション)は、ノード次数の多重集合が同じでないときにグラフのペアを区別することができる。 0.67
GNNML1 and GIN’s result is very closed to the theoretical limit of 1-WL test which is 312 pairs for graph8c dataset. GNNML1とGINの結果は、Graph8cデータセットの312ペアである1-WLテストの理論的限界に非常に近い。 0.75
The difference can be explained by threshold value to make decision if the two representations are equal and/or the number of layers in the model. この違いはしきい値で説明でき、2つの表現が等しく、またはモデル内の層数であるかどうかを判断することができる。 0.71
It is possible that 1-WL test may need more than 3 iteration to distinguish some pairs. 1-WLテストは、いくつかのペアを区別するために3つ以上のイテレーションを必要とする可能性がある。 0.53
Due to having less expressive power of GCN and GAT compare to the 1-WL test, their performances are worse than 1-WL test. GCN と GAT の表現力が 1-WL よりも低いため、その性能は 1-WL よりも悪い。
訳抜け防止モード: GCNとGATの表現力が少ないため、1-WLテストと比較する。 性能は1-WLテストより悪い。
0.76
Since graph8c dataset has 1-WL equivalent non-regular graph pairs that have different maximum eigenvalue, Chebnet could detect these pairs and reaches better performance than theoretical limit of 1-WL test as stated by Theorem 2. Graph8cデータセットは最大固有値が異なる1-WL相当の非正則グラフペアを持つため、Chebnetはこれらのペアを検出でき、Theorem 2で述べられている1-WLテストの理論的限界よりも優れた性能が得られる。 0.63
On EXP dataset, composed of 1-WL equivalent graph pairs, MPNNs cannot distinguish any pair of graphs, except Chebnet which is able to distinguish all the pairs with different maximum eigenvalues. 1-WL相当グラフ対からなるEXPデータセットでは、MPNNは最大固有値の異なる全てのペアを区別できるChebnetを除いて、任意のグラフ対を区別できない。 0.77
In EXP there is no regular graphs and only 71 graph pairs have similar maximum eigenvalues. EXP には正則グラフはなく、71 個のグラフペアのみが同様の最大固有値を持つ。 0.74
Chebnet fails on these pairs but distinguishes the others, as stated by Theorem 2. Chebnetはこれらのペアで失敗するが、Theorem 2で述べられているように、他のペアを区別する。 0.55
One can note that using a fixed value for maximum eigenvalue (e g λmax = 2 as it is usually done in practice) reduces Chebnet performance to those of MPNNs. 最大固有値 (eg λmax = 2) に対して固定値を使用すると、Chebnet のパフォーマンスは MPNN の値に低下する。 0.66
Similarly to results on EXP, 1-WL equivalent MPNNs except Chebnet fail to predict of EXP classification task and do not perform better than random prediction. EXPの結果と同様に、Chebnet以外の1-WL相当MPNNはEXP分類タスクの予測に失敗し、ランダムな予測よりは良くない。 0.80
On the contrary, PPGN and GNNML3 have perfect results on graph8c, EXP and EXP-classify tasks thanks to their 3-WL equivalence. それとは対照的に、PGNとGNNML3は3WL同値性のおかげで、Graph8c、EXP、EXP分類タスクにおいて完全な結果が得られる。 0.54
However, since strongly regular graphs are 3-WL equivalent, no model less or as powerful as 3-WL test can distinguish the pairs in sr25 dataset. しかし、強い正則グラフは3WL同値であるため、3WLテストほど強力なモデルではsr25データセット内のペアを区別できない。 0.67
To obtain a better result on this これについてより良い結果を得る 0.81
Table 2. Median of test set MSE error for graphlet counting problem on random graph dataset over 10 random runs. 表2。 10回以上のランダムグラフデータセットにおけるグラフレットカウント問題に対するテストセットMSE誤差の媒介化 0.77
MODEL MLP GCN GAT GIN CHEBNET PPGN GNNML1 GNNML3 モデル MLPGCN GAT GINCHEBNET PPGN GNNML1 GNNML3 0.72
3-STARS 1.0E-4 1.0E-4 1.0E-4 1.0E-4 1.0E-4 1.0E-4 1.0E-4 1.0E-4 3-STARS 1.0E-4 1.0E-4 1.0E-4 1.0E-4 1.0E-4 1.0E-4 1.0E-4 0.26
CUSTOM TRIANGLE TAILED-TRI 官務 三角形 TAILED-TRI 0.49
4-CYCLES 4.58E-1 3.22E-3 4.57E-3 1.47E-3 7.68E-4 9.19E-4 2.75E-4 7.24E-4 4-CYCLES 4.58E-1 3.22E-3 4.57E-3 1.47E-3 7.68E-4 9.19E-4 2.75E-4 7.24E-4 0.40
3.13E-1 2.43E-1 2.47E-1 2.06E-1 2.01E-1 1.00E-4 2.45E-1 4.44E-4 3.13E-1 2.43E-1 2.47E-1 2.06E-1 2.01E-1 1.00E-4 2.45E-1 4.44E-4 0.22
2.22E-1 1.42E-1 1.44E-1 1.18E-1 1.15E-1 2.61E-4 1.32E-1 3.18E-4 2.22E-1 1.42E-1 1.44E-1 1.18E-1 1.15E-1 2.61E-4 1.32E-1 3.18E-4 0.22
1.73E-1 1.14E-1 1.12E-1 1.21E-1 9.60E-2 3.30E-4 1.14E-1 6.62E-4 1.73E-1 1.14E-1 1.12E-1 1.21E-1 9.60E-2 3.30E-4 1.14E-1 6.62E-4 0.22
dataset, we need to go further than 3-WL (see Appendix E). データセットは3WLを超える必要がある(Appendix E参照)。 0.69
These experiments reply to Q1. これらの実験はQ1に応答する。 0.58
To bring an answer to Q2, we propose to count 3-star, triangle, tailed-triangle and 4-cycle substructures (Fig. q2に答えるには、三つ星、三角形、尾長三角形、四サイクル部分構造(fig)を数えることを提案する。 0.59
2). In addition to these 4 graphlets, we also create another task (noted as CUSTOM in Table 2) that aims to approximate a custom 1 , ec(A) = 1(cid:62)A diag(exp(−A21))A1 sentence ec ∈ L+ with A the graph adjacency matrix. 2). これらの4つのグラフレットに加えて、カスタム 1 , ec(a) = 1(cid:62)a diag(exp(−a21))a1文 ec ∈ l+ をグラフの隣接行列で近似することを目的として、別のタスク(表 2 でカスタムと表記される)を作成する。
訳抜け防止モード: 2). これら4つのグラフレットに加えて、カスタム1を近似することを目的とした別のタスク(表2のCUSTOM)も作成します。 ec(A ) = 1(cid:62)A diag(exp(−A21))A1 sentence ec ∈ L+ with A the graph adjacency matrix 。
0.84
Since ec ∈ M L(L+ 1 ), it may be learnable by 1-WL equivalent MPNNs. ec ∈ M L(L+ 1 ) であるため、1-WL 相当MPNN で学習することができる。 0.81
We used the RandomGraph dataset (Chen et al , 2020) with same partitioning: 1500, 1000 and 2500 graphs for train, validation and test respectively. ランダムグラフデータセット(chen et al , 2020)を、それぞれ1500、1000、2500のグラフをトレイン、バリデーション、テストに使用しました。 0.62
To create the ground truth of number of graphlets, we count them according to theorem proofs in Appendix B.3, B.4, B.5 and normalized the number to a unitary standard deviations, to keep the errors in the same scale as in Table 2. グラフレットの数の基底的真理を作成するために、付録 b.3, b.4, b.5 の定理証明に従ってそれらを数え、これをユニタリ標準偏差に正規化し、誤差を表 2 と同じスケールに保つ。 0.73
We use 4 convolution layers, a graph readout layer computing a sum and followed by 2 fully connected layers. 4つの畳み込み層、合計を計算するグラフ読み出し層、そして2つの完全接続層を使用します。 0.75
All methods parameter budget is around 30K. すべてのメソッドパラメータの予算は約30Kです。 0.65
We keep the maximum number of iterations to 200 and we stop the algorithm if the error goes below 10−4. 最大反復回数を200に保ち、誤差が10-4以下であればアルゴリズムを停止する。
訳抜け防止モード: イテレーションの最大数は200に保ちます そして、エラーが10−4以下の場合はアルゴリズムを停止する。
0.76
The results in Table 2 are consistent with Theorems 3, 4, 5. 表2の結果は、Theorems 3, 4, 5と一致している。 0.88
3-WL models are able to count graphlets and approximate our custom function (result < 10−3), while 1-WL equivalent models can only count the 3-stars graphlet, as stated in Theorem 3. 3WLモデルはグラフレットをカウントし、我々のカスタム関数(result < 10−3)を近似することができるが、1-WL等価モデルは3つ星グラフレットのみをカウントできる。 0.76
Custom function approximation results also show that GNNML1 and Chebnet provide better approximation of the target other MPNNs, which is again consistent with our analysis. また,GNNML1とChebnetのカスタム関数近似結果から,他のMPNNのより優れた近似が得られた。 0.58
Question Q3 concerns the spectral expressive power of models. 質問 Q3 はモデルのスペクトル表現力に関するものである。 0.67
Such an analysis is important when input-output relations depend on the spectral properties of the graph signal such as in image/signal processing applications. このような分析は、入力出力関係が画像/信号処理などのグラフ信号のスペクトル特性に依存する場合に重要である。 0.84
As shown in (Balcilar et al , 2021), the vast majority of existing MPNNs operate as low-pass filters which limits their capacity. Balcilar et al , 2021)に示すように、既存のMPNNの大半は低域フィルタとして機能し、容量を制限している。 0.75
To lead this analysis, we use the datasets presented in (Balcilar et al , 2021). この分析を導くために、提示されたデータセット(Balcilar et al , 2021)を使用します。 0.74
First, we evaluate if the models can learn low-pass, high-pass and band-pass filtering effects, through a node regression problem. まず,モデルがノード回帰問題を通じて低パス,高パス,帯域通過フィルタの効果を学習できるかどうかを評価する。 0.72
Model performances are thus reported R2 using mean square error (MSE) loss. モデル性能は平均二乗誤差(MSE)損失を用いてR2を報告する。 0.75
The original data consists in a 2-d grid graph of size 100x100. 元のデータはサイズ100×100の2次元グリッドグラフで構成されている。 0.65
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
Table 3. Spectral expressive analysis results. 表3。 スペクトル表現型分析結果。 0.76
R2 for LowPass, HighPass and BandPass node regression tasks, accuracy on graph classification task. LowPass、HighPass、BandPassノード回帰タスク用のR2、グラフ分類タスクの精度。 0.81
Results are median of 10 different runs. 結果は10の異なるランの中央値である。 0.63
MODEL LOW-PASS HIGH-PASS モデル ローパス ハイパス 0.55
BAND-PASS CLASSIFY バンドパス CLASSIFY 0.69
MLP GCN GAT GIN CHEBNET PPGN GNNML1 GNNML3 MLPGCN GAT GINCHEBNET PPGN GNNML1 GNNML3 0.74
0.9749 0.9858 0.9811 0.9824 0.9995 0.9991 0.9994 0.9995 0.9749 0.9858 0.9811 0.9824 0.9995 0.9991 0.9994 0.9995 0.42
0.0167 0.0863 0.0879 0.2934 0.9901 0.9925 0.9833 0.9909 0.0167 0.0863 0.0879 0.2934 0.9901 0.9925 0.9833 0.9909 0.42
0.0027 0.0051 0.0044 0.0629 0.8217 0.1041 0.3802 0.8189 0.0027 0.0051 0.0044 0.0629 0.8217 0.1041 0.3802 0.8189 0.42
50.0% 77.9% 85.3% 87.6% 98.2% 91.2% 92.8% 97.8% 50.0% 77.9% 85.3% 87.6% 98.2% 91.2% 92.8% 97.8% 0.61
Since the PPGN’s memory and computational complexity is prohibitive with a reasonable computer, we select 3 different 30x30 regions of the original 2-d grid graph as training, validation and test sets. PPGNのメモリと計算の複雑さは、合理的なコンピュータでは禁じられているので、トレーニング、検証、テストセットとして、元の2次元グリッドグラフの30x30の3つの異なる領域を選択する。 0.62
A second dataset consists of 5K planar graphs, split into 3K, 1K and 1K sets for train, validation and test. 第2のデータセットは5K平面グラフで構成され、トレーニング、検証、テストのために3K、1Kと1Kに分割される。 0.66
They are used to evaluate if the models can classify graphs into binary classes where the ground truth labels were determined according to the frequency of the signal on the graph. それらは、モデルがグラフ上の信号の頻度に応じて基底真理ラベルが決定されたバイナリクラスに分類できるかどうかを評価するために使用される。 0.78
Since the problem is binary graph classification we use binary cross entropy loss. 問題は二進グラフ分類であるため、二進クロスエントロピー損失を用いる。 0.75
The results of spectral expressive power analysis are presented in Table 3. スペクトル表現力解析の結果を表3に示す。 0.66
Node regression results show that 1-WL equivalent existing MPNNs can mostly learn low-pass effects. ノード回帰結果から、1-WL相当の既存のMPNNは、主にローパス効果を学習できることが示された。 0.48
By applying different weights to self node and neighbourhood, GNNML1 can learn high pass effect relatively well. 自己ノードと近傍に異なる重みを適用することで、GNNML1は比較的高い通過効果を学習することができる。 0.65
PPGN also learns high-pass effect better than 1-WL equivalent methods. PPGNはまた、1-WL相当の手法よりも高い通過効果を学習する。 0.55
Band-pass can be generalized by Chebnet and GNNML3 thanks to the convolutions designed in spectral domain. スペクトル領域で設計された畳み込みのおかげで、バンドパスはChebnetとGNNML3によって一般化できる。 0.53
The reason why the band-pass regression results are worse than the low and high-pass results is that the ground truth band-pass effect is created by very stiff frequency function and Chebnet also GNNML3 need more convolution supports to learn it. 帯域通過回帰結果が低域および高域通過結果よりも悪い理由は、基底真理バンドパス効果が非常に硬い周波数関数によって生成され、ChebnetもまたGNNML3もそれを学ぶためにさらなる畳み込み支援を必要としているからである。 0.64
Because of non-local process in PPGN, it cannot learn the band-pass effect and provide no better result than 1-WL MPNNs in graph classification problem. PPGNの非局所的なプロセスのため、バンドパス効果を学習できず、グラフ分類問題における1-WL MPNNよりも良い結果を得ることができない。
訳抜け防止モード: PPGNの非局所過程のため、バンドを学習できない - 通過効果 グラフ分類問題における1-WL MPNNよりもよい結果を提供する。
0.81
Thus, Chebnet and GNNML3 give the best results on all spectral ability test, thanks to their spectral convolutions process. このように、ChebnetとGNNML3は、スペクトル畳み込みプロセスにより、全てのスペクトル能力試験において最良の結果を与える。 0.67
For answering the last question Q4, we apply the different models on some common benchmark tasks and datasets. 最後の質問Q4に答えるために、いくつかの一般的なベンチマークタスクとデータセットに異なるモデルを適用します。 0.57
Table 4 and Table 5 present the performance of both baseline models and the proposed ones on these benchmark datasets. 表4と表5は、これらのベンチマークデータセット上で、ベースラインモデルと提案モデルの両方のパフォーマンスを示す。 0.76
The results on Zinc12K and MNIST-75 datasets are very interesting because of the nature of these two problems. 亜鉛12kとmnist-75のデータセットの結果は、この2つの問題の性質から非常に興味深い。 0.65
The solution of the Zinc12K dataset mostly depends on structural features of the graph. Zinc12Kデータセットの解は主にグラフの構造的特徴に依存する。 0.87
For instance, a recent study reaches 0.14 MAE by using handcrafted features, which cannot be extracted by a 3-WL equivalent model (Bouritsas et al , 2020). 例えば、最近の研究では、3WL相当のモデル(Bouritsas et al , 2020)では抽出できない手作りの特徴を用いて0.14 MAEに達する。 0.77
Obtained results confirm that models that are able to count substructures, such as PPGN and GNNML3, 得られた結果から PPGN や GNNML3 などのサブ構造を数えることができるモデルが確認された。 0.72
Table 4. Results on Zinc12K and MNIST-75 datasets. 表4。 亜鉛12kおよびmnist-75データセットの結果 0.68
The values are the MSE for Zinc12K and the accuracy for MNIST-75. 値は Zinc12K の MSE と MNIST-75 の精度である。 0.86
Edge features are not used even if they are available in the datasets. エッジ機能は、データセットで利用可能であっても使用されない。 0.75
For Zinc12K, all models use node labels. Zinc12Kの場合、全てのモデルはノードラベルを使用する。 0.53
For MNIST-75, the model uses superpixel intensive values and node degree as node features. MNIST-75では、スーパーピクセル集約値とノード次数をノードの特徴として使用する。 0.66
MODEL MLP GCN GAT GIN CHEBNET PPGN GNNML1 GNNML3 モデル MLPGCN GAT GINCHEBNET PPGN GNNML1 GNNML3 0.72
ZINC12K 0.5869 ± 0.025 0.3322 ± 0.010 0.3977 ± 0.007 0.3044 ± 0.010 0.3569 ± 0.012 0.1589 ± 0.007 0.3140 ± 0.015 0.1612 ± 0.006 ZINC12K 0.5869 ± 0.025 0.3322 ± 0.010 0.3977 ± 0.007 0.3044 ± 0.010 0.3569 ± 0.012 0.1589 ± 0.007 0.3140 ± 0.015 0.1612 ± 0.006 0.55
MNIST-75 25.10% ± 0.12 52.80% ± 0.31 82.73% ± 0.21 75.23% ± 0.41 92.08% ± 0.22 90.04% ± 0.54 84.21% ± 1.75 91.98% ± 0.18 MNIST-75 25.10% ± 0.12 52.80% ± 0.31 82.73% ± 0.21 75.23% ± 0.41 92.08% ± 0.22 90.04% ± 0.54 84.21% ± 1.75 91.98% ± 0.18 0.59
perform better than others with a large margin. 他の人よりも大きなマージンでパフォーマンスが良くなる。 0.58
On the other hand, since MNIST-75 dataset is based on image analysis, it needs a model with a higher spectral ability. 一方、MNIST-75データセットは画像解析に基づくため、より高いスペクトル能力を持つモデルが必要である。 0.80
Therefore, Chebnet and GNNML3 perform significantly better than other models on this task. 従って、ChebnetとGNNML3は、このタスクの他のモデルよりも大幅にパフォーマンスが向上する。 0.59
Our proposal GNNML3 gives comparable results on other TU datasets in (Morris et al , 2020) such as MUTAG, ENZYMES, PROTEINS and PTC presented in Appendix F. 我々の提案したGNNML3は,MUTAG,ENZYMES, PROTEINS, PTCなど,他のTUデータセット(Morris et al , 2020)に匹敵する結果を与える。 0.72
7. Conclusion Despite a computational and memory efficiency, MPNN is known to have an expressive power limited to 1-WL test. 7. 結論 MPNN は計算とメモリ効率にもかかわらず 1-WL に制限された表現力を持つことが知られている。 0.74
MPNN is then unable to distinguish 1-WL equivalent graphs and cannot count some substructures of the graph. その後、MPNNは1-WLの等価グラフを識別できず、グラフのいくつかの部分構造をカウントできない。 0.64
In this paper, we have presented new models, by translating the insights of MATLANG to the GNN world. 本稿では,MATLANGの知見をGNNの世界に翻訳することで,新しいモデルを提案する。 0.75
This solution gives access to a new MPNN that is theoretically more powerful than the 1-WL test, and experimentally as powerful as 3-WL existing models for distinguishing non-isomorphic graphs and for counting substructures without feature engineering nor node permutations in the training phase. このソリューションは、理論上は1-WLテストよりも強力で、非同型グラフの識別や、トレーニングフェーズにおける機能工学やノード置換のないサブ構造をカウントするための3-WL既存モデルと同じくらい強力である。 0.76
The proposed MPNN is also powerful in terms of spectral expressive ability, going beyond low-pass filtering, which is another expressive perspective of GNNs. 提案したMPNNはスペクトル表現能力にも優れており、GNNのもうひとつの表現的視点である低域フィルタリングを超越している。 0.74
Experimental results confirm the theorems stated in the paper. 実験結果は論文に記載された定理を確認する。 0.69
The proposed method has a big advantage over all studied MPNN on graph isomorphism and substructure counting tasks. 提案手法は,グラフ同型およびサブストラクチャカウントタスクにおいて,すべてのMPNNに対して大きな優位性を有する。 0.71
With respect to the 3-WL equivalent baseline PPGN, the biggest advantage of our proposal is its complexity. 3WL相当のベースライン PPGN に関して、我々の提案の最大の利点は、その複雑さである。 0.62
Proposed GNNML3 needs linear memory and time complexity with respect to the number of nodes, while PPGN needs quadratic memory and cubic time complexity, making the model infeasible for large graphs. 提案するgnnml3はノード数に関して線形メモリと時間複雑性を必要とし、ppgnは二次メモリとキュービックタイムの複雑さを必要とする。 0.69
The second advantage over PPGN is that since it is created in the spectral domain, its convolution process takes care of signal frequencies, making it more efficient in terms of output signal frequency profile. PPGNの2つめの利点は、スペクトル領域で生成されるため、その畳み込みプロセスは信号周波数を処理し、出力信号周波数プロファイルの点でより効率的であることである。 0.85
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
Acknowledgments This work was partially supported by the Normandy Region (grant RiderNet), the French Agence National de Recherche (grant APi, ANR-18-CE23-0014) and the PAUSE Program of Coll`ege de France. この研究はノルマンディー地域(グランドライダーネット)、フランスのAgence National de Recherche(グラントAPi、ANR-18-CE23-0014)、コレージュ・ド・フランスPAUSEプログラムによって部分的に支援された。 0.67
References Abboud, R., Ceylan, ˙I. Abboud, R., Ceylan, .Iを参照。 0.76
˙I., Grohe, M., and Lukasiewicz, T. The surprising power of graph neural networks with random node initialization. grohe, m., lukasiewicz, t. ランダムノード初期化を伴うグラフニューラルネットワークの驚くべきパワー。 0.64
arXiv preprint arXiv:2010.01179, 2020. arXiv preprint arXiv:2010.01179, 2020 0.81
Arvind, V., Fuhlbr¨uck, F., K¨obler, J., and Verbitsky, O. Arvind, V., Fuhlbr suck, F., K sobler, J., Verbitsky, O。 0.75
On weisfeiler-leman invariance: subgraph counts and related graph properties. weisfeiler-leman invariance: subgraph counts and related graph properties について 0.80
Journal of Computer and System Sciences, 2020. Journal of Computer and System Sciences、2020年。 0.83
Balcilar, M., Renton, G., H´eroux, P., Ga¨uz`ere, B., Adam, S., and Honeine, P. Analyzing the expressive power of graph neural networks in a spectral perspective. Balcilar, M., Renton, G., H ́eroux, P., Ga suz`ere, B., Adam, S., Honeine, P. は、スペクトルの観点からグラフニューラルネットワークの表現力を分析する。 0.86
In International Conference on Learning Representations, 2021. 2021年、国際学習表現会議に参加。 0.78
URL https://openreview.n et/forum? URL https://openreview.n et/forum? 0.59
id=-qh0M9XWxnv. id=-qh0M9XWxnv。 0.37
Barcel´o, P., Kostylev, E. V., Monet, M., P´erez, J., Reutter, J., and Silva, J. P. The logical expressiveness of graph neural networks. Barcel ́o, P., Kostylev, E. V., Monet, M., P ́erez, J., Reutter, J., and Silva, J. P. グラフニューラルネットワークの論理的表現性。 0.90
In International Conference on Learning Representations, 2019. International Conference on Learning Representations, 2019に参加。 0.86
Battaglia, P. W., Hamrick, J. Battaglia, P. W., Hamrick, J。 0.91
B., Bapst, V., SanchezGonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., et al Relational inductive biases, deep learning, and graph networks. b., bapst, v., sanchezgonzalez, a., zambaldi, v., malinowski, m., tacchetti, a., raposo, d., santoro, a., faulkner, r., et al relational inductive biases, deep learning, graph networks 0.71
arXiv preprint arXiv:1806.01261, 2018. arXiv preprint arXiv:1806.01261, 2018 0.79
Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. Improving graph neural network expressivity via subgraph isomorphism counting. bouritsas, g., frasca, f., zafeiriou, s., bronstein, m. m. subgraph isomorphism counting によるグラフニューラルネットワークの表現性の向上。 0.88
arXiv preprint arXiv:2006.09252, 2020. arXiv preprint arXiv:2006.09252, 2020 0.81
Bresson, X. and Laurent, T. Residual gated graph convnets, 2018. Bresson, X. and Laurent, T. Residual gated graph convnets, 2018 0.87
URL https://openreview.n et/forum? URL https://openreview.n et/forum? 0.59
id=HyXBcYg0b. id=HyXBcYg0b。 0.48
Brijder, R., Geerts, F., Bussche, J. V. D., and Weerwag, T. On the expressive power of query languages for matrices. Brijder, R., Geerts, F., Bussche, J. V. D., Weerwag, T. 行列に対するクエリ言語の表現力について。 0.83
ACM Transactions on Database Systems (TODS), 44(4): 1–31, 2019. ACM Transactions on Database Systems (TODS), 44(4): 1-31, 2019 0.80
Chami, I., Abu-El-Haija, S., Perozzi, B., R´e, C., and Murphy, K. Machine learning on graphs: A model and comprehensive taxonomy. Chami, I., Abu-El-Haija, S., Perozzi, B., R ́e, C., K. Machine Learning on graphs: A model and comprehensive taxonomy。 0.90
arXiv preprint arXiv:2005.03675, 2020. arXiv preprint arXiv:2005.03675, 2020 0.81
Chung, F. Spectral graph theory. Chung, F. Spectral graph theory 0.81
American Mathematical American Mathematical 0.85
Society, 1997. Dasoulas, G., Dos Santos, L., Scaman, K., and Virmaux, A. Coloring graph neural networks for node disamIn Bessiere, C. 1997年、社会。 Dasoulas, G., Dos Santos, L., Scaman, K., Virmaux, A. Coloring graph Neural Network for node disamIn Bessiere, C。 0.81
(ed. ), Proceedings of the biguation. (エド) は、biguationの手続きである。 0.49
Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 第20回人工知能国際会議, IJCAI-20, pp. 0.79
2126–2132, 7 2020. doi: 10.24963/ijcai.2020/ 294. 2126–2132, 7 2020. doi: 10.24963/ijcai. 2020/294 0.54
URL https://doi.org/ 10.24963/ijcai.2020/ 294. URL https://doi.org/ 10.24963/ijcai.2020/ 294 0.43
Defferrard, M., Bresson, X., and Vandergheynst, P. Convolutional neural networks on graphs with fast localized In Advances in Neural Information spectral filtering. Defferrard, M., Bresson, X., Vandergheynst, P. Convolutional Neural Network on graphs with fast localized In Advances in Neural Information spectrum filtering 0.78
Processing Systems, pp. 3844–3852, 2016. 処理システム、p。 3844–3852, 2016. 0.76
Dehmamy, N., Barab´asi, A.-L., and Yu, R. Understanding the representation power of graph neural networks in learning graph topology. Dehmamy, N., Barab ́asi, A.-L., Yu, R. グラフトポロジー学習におけるグラフニューラルネットワークの表現力の理解 0.89
In NeurIPS, pp. NeurIPS, pp。 0.62
15387–15397, 2019. 15387–15397, 2019. 0.84
Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., Bresson, X. Benchmarking graph Neural Network。 0.87
arXiv preprint arXiv:2003.00982, 2020. arXiv preprint arXiv:2003.00982, 2020 0.81
Fey, M. and Lenssen, J. E. Fast graph representation learning with pytorch geometric. fey, m. and lenssen, j. e. fast graph representation learning with pytorch geometric。 0.88
arXiv preprint arXiv:1903.02428, 2019. arXiv preprint arXiv:1903.02428, 2019 0.81
Geerts, F. On the expressive power of linear alTheory of Computing Systems, gebra on graphs. ジェルツ、f。 計算機系の線形alTheoryの表現力について、gebra on graphs。 0.56
Oct 2020. 10.1007/ s00224-020-09990-9. 2020年10月。 10.1007/ s00224-020-09990-9。 0.50
URL https://doi.org/10. URL https://doi.org/10。 0.58
1007/s00224-020-0999 0-9. 1007/s00224-020-0999 0-9。 0.28
ISSN 1433-0490. ISSN 1433-0490。 0.74
doi: Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyal, O., and Dahl, G. E. Neural message passing from quantum chemistry. Doi: Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyal, O., Dahl, G. E. Neural message pass from quantum chemistry。 0.73
In Proceedings of the International Conference on Machine Learning, 2017. 2017年度の「機械学習に関する国際会議」の開催にあたって 0.72
Hamilton, W., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs. Hamilton, W., Ying, Z. and Leskovec, J. Inductive representation learning on large graphs 0.82
In Advances in Neural Information Processing Systems, pp. ニューラル・インフォメーション・プロセッシング・システムにおける進歩, pp. 0.59
1024–1034, 2017. 1024–1034, 2017. 0.84
Hammond, D. K., Vandergheynst, P., and Gribonval, R. Wavelets on graphs via spectral graph theory. Hammond, D. K., Vandergheynst, P., and Gribonval, R. Wavelets on graphs through spectrum graph theory。 0.89
Applied and Computational Harmonic Analysis, 30(2):129–150, 2011. 応用と計算調和解析, 30(2):129-150, 2011 0.72
Harary, F. and Manvel, B. Harary, F. and Manvel, B. 0.94
On the number of cycles in a a のサイクルの数について 0.75
graph. Matematick`y ˇcasopis, 21(1):55–63, 1971. グラフ。 Matematick`y scasopis, 21(1):55-63, 1971 0.82
Hornik, K., Stinchcombe, M., and White, H. Multilayer feedforward networks are universal approximators. Hornik, K., Stinchcombe, M. and White, H. Multilayer feedforward network is universal approximator。 0.85
Neural networks, 2(5):359–366, 1989. ニューラルネットワーク, 2(5):359–366, 1989。 0.82
Chen, Z., Chen, L., Villar, S., and Bruna, J. Chen, Z., Chen, L., Villar, S., Bruna, J. 0.79
Can graph arXiv preprint can graph arXiv preprint 0.83
neural networks count substructures? ニューラルネットワークのサブ構造数? 0.72
arXiv:2002.04025, 2020. arXiv:2002.04025, 2020。 0.63
Immerman, N. and Lander, E. Describing graphs: A firstIn Complexity Immerman, N. and Lander, E. Describing graphs: A firstIn Complexity 0.97
order approach to graph canonization. グラフの正準化への アプローチです 0.53
theory retrospective, pp. 理論の振り返り、p。 0.70
59–81. Springer, 1990. 59–81. 1990年、スプリンガー。 0.64
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
Keriven, N. and Peyr´e, G. Universal invariant and equivariant graph neural networks. Keriven, N. and Peyr ́e, G. Universal invariant and equivariant graph neural network。 0.90
In Advances in Neural Information Processing Systems 32, pp. 神経情報処理システム32, pp. の進歩 0.63
7092–7101. 7092–7101. 0.71
2019. Takapoui, R. and Boyd, S. Linear programming heuristics for the graph isomorphism problem. 2019. Takapoui, R. and Boyd, S. Linear programming heuristics for the graph isomorphism problem。 0.88
arXiv preprint arXiv:1611.00711, 2016. arXiv preprint arXiv:1611.00711, 2016 0.80
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional network。 0.84
In International Conference on Learning Representations (ICLR), 2017. 2017年、ICLR(International Conference on Learning Representations)に参加。 0.86
Van Dam, E. R. and Haemers, W. H. Which graphs are determined by their spectrum? Van Dam, E. R. and Haemers, W. H. どのグラフがスペクトルによって決定されるか? 0.76
Linear Algebra and its applications, 373:241–272, 2003. 線形代数とその応用, 373:241–272, 2003 0.75
Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. Provably powerful graph networks. maron, h., ben-hamu, h., serviansky, h., lipman, y. は強力なグラフネットワークを証明できる。 0.70
In Advances in Neural Information Processing Systems, pp. ニューラル・インフォメーション・プロセッシング・システムにおける進歩, pp. 0.59
2156–2167, 2019a. 2156-2167, 2019a。 0.60
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, s., Polosukhin, I。 0.83
Attention is all you need. 注意はあなたが必要とするすべてです。 0.63
In Advances in neural information processing systems, pp. In Advances in Neural Information Processing System, pp。 0.75
5998–6008, 2017. 5998–6008, 2017. 0.84
Veliˇckovi´c, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. ヴェリシュコヴィ ́c, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention network 0.85
In International Conference on Learning Representations (ICLR), 2018. International Conference on Learning Representations (ICLR) 2018に参加。 0.76
Vignac, C., Loukas, A., and Frossard, P. Building powerful and equivariant graph neural networks with structural message-passing. Vignac, C., Loukas, A. and Frossard, P. 構造的メッセージパッシングを用いた強力で同変のグラフニューラルネットワークの構築 0.78
In NeurIPS, 2020. 2020年、NeurIPS。 0.70
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P. S. A comprehensive survey on graph neural networks. Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., Yu, P. S. グラフニューラルネットワークに関する総合的な調査。 0.84
arXiv preprint arXiv:1901.00596, 2019. arXiv preprint arXiv:1901.00596, 2019 0.81
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? xu, k., hu, w., leskovec, j., jegelka, s. グラフニューラルネットワークはどの程度強力か? 0.71
In International Conference on Learning Representations, 2019. International Conference on Learning Representations, 2019に参加。 0.86
Maron, H., Fetaya, E., Segol, N., and Lipman, Y. Maron, H., Fetaya, E., Segol, N., Lipman, Y。 0.78
On the universality of invariant networks. 不変ネットワークの普遍性について 0.70
In Chaudhuri, K. and Salakhutdinov, R. Chaudhuri, K. and Salakhutdinov, R。 0.73
(eds. ), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. (eds)。 The 36th International Conference on Machine Learning, Volume 97 of Proceedings of Machine Learning Research, pp。 0.73
4363– 4371, Long Beach, California, USA, 09–15 Jun 2019b. 4363–4371, Long Beach, California, USA, 09–15 Jun 2019b 0.92
PMLR. Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. PMLR。 Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., Grohe, M. Weisfeiler, leman go Neural: Higher-order graph Neural Network。 0.83
Proceedings of the AAAI Conference on Artificial Intelligence, 33(01): 4602–4609, Jul. AAAI Conference on Artificial Intelligence, 33(01): 4602–4609, Jul 0.71
2019. Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: A collection of benchmark datasets for learning with graphs. 2019. Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., そして Neumann, M. Tudataset: グラフで学ぶためのベンチマークデータセットのコレクション。 0.83
arXiv preprint arXiv:2007.08663, 2020. arXiv preprint arXiv:2007.08663, 2020 0.80
Murphy, R., Srinivasan, B., Rao, V., and Ribeiro, B. Relational pooling for graph representations. Murphy, R., Srinivasan, B., Rao, V., Ribeiro, B. グラフ表現に対する関係プール 0.80
In Chaudhuri, K. and Salakhutdinov, R. Chaudhuri, K. and Salakhutdinov, R。 0.73
(eds. ), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. (eds)。 The 36th International Conference on Machine Learning, Volume 97 of Proceedings of Machine Learning Research, pp。 0.73
4663– 4673, Long Beach, California, USA, 09–15 Jun 2019. 4663–4673, Long Beach, California, USA, 09–15 Jun 2019 0.91
PMLR. Pinar, A., Seshadhri, C., and Vishal, V. Escape: Efficiently counting all 5-vertex subgraphs. PMLR。 Pinar, A., Seshadhri, C., Vishal, V. Escape: 全5頂点部分グラフを効率的にカウントする。 0.80
pp. 1431–1440, 2017. pp. 1431–1440, 2017. 0.85
Sato, R., Yamada, M., and Kashima, H. Approximation ratios of graph neural networks for combinatorial probIn Advances in Neural Information Processing lems. STO, R., Yamada, M. and Kashima, H. Approximation ratios of graph Neural Network for combinatorial probIn Advances in Neural Information Processing lems。 0.84
Systems, volume 32, pp. 第32巻、p.c.。 0.38
4081–4090. 4081–4090. 0.71
Curran Associates, Inc., 2019. Curran Associates, Inc., 2019 0.71
Sato, R., Yamada, M., and Kashima, H. Random features strengthen graph neural networks. 佐藤、R、山田、M、鹿島、H. Randomはグラフニューラルネットワークを強化している。 0.72
arXiv preprint arXiv:2002.03155, 2020. arXiv preprint arXiv:2002.03155, 2020 0.81
Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., and Vandergheynst, P. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., Vandergheynst, P. The emerging field of signal processing on graphs: Extending High-dimensional data analysis to network and other irregular domain。 0.90
IEEE signal processing magazine, 30(3):83–98, 2013. IEEE信号処理マガジン 30(3):83-98, 2013。 0.88
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
A. Weisfeiler-Lehman Test The universality of a GNN is based on its ability to embed two non-isomorphic graphs to distinct points in the target feature space. A. Weisfeiler-Lehmanテスト GNNの普遍性は、2つの非同型グラフを対象特徴空間の異なる点に埋め込む能力に基づいている。 0.82
A model which can distinguish all pairs of non-isomorphic graphs is a universal approximator. 非同型グラフのすべての対を区別できるモデルは普遍近似である。 0.84
Since it is not known if the graph isomorphism problem can be solved in polynomial time or not, this problem is neither NP-complete nor P, but NP-intermediate (Takapoui & Boyd, 2016). グラフ同型問題が多項式時間で解けるかどうかは不明であるので、この問題はNP完全でもPでもないが、NP中間体ではない(Takapoui & Boyd, 2016)。 0.72
One of the oldest but prominent polynomial approach is the Weisfeiler-Lehman Test (abbreviated WL-test) which gives sufficient but not enough evidence. 最も古いが顕著な多項式アプローチの一つにWeisfeiler-Lehman Test (WL-test)がある。 0.64
WL test can be extended by taking into account higher order of node tuple within the iterative process. WLテストは反復プロセス内のノードタプルの高次性を考慮して拡張することができる。 0.80
These extensions are denoted as k-WL test, where k is equal to the order of the tuple. これらの拡張は k-WL テストと呼ばれ、k はタプルの順序に等しい。 0.67
It is important to mention that an higher order of tuple leads to a better ability to distinguish two non-isomorphic graphs (with the exception for k = 2) (Arvind et al , 2020). 高階のタプルは、2つの非同型グラフ(k = 2 (arvind et al , 2020) を除いて)を区別するより良い能力をもたらすことは重要である。 0.70
The 1-WL test, known as vertex coloring, starts with the given initial color of nodes if available. 頂点色として知られる1-WLテストは、利用可能なノードの初期色から始まる。 0.81
Otherwise all nodes are colored with the same color (H (0) v = 1). それ以外のノードは同じ色(h (0) v = 1)で色付けされる。 0.77
Then, colors are updated by the following iteration: そして、次のイテレーションで色が更新される。 0.77
u : u ∈ N (v) H (t) u : u ∈ N (v) H (t) 0.85
, v v = σ H (t) , v v = σ H (t) 0.85
H (t+1) (7) is the color of vertex v at iteration t, N (v) is the where H (t) v set of neighbours of vertex v, | represents the concatenation operator and {.} H(t+1) (7) は反復 t における頂点 v の色であり、N (v) は頂点 v の近傍の H (t) v 集合であり、| は連結作用素と {} を表す。 0.83
is the order invariant multiset3. 順序不変の multiset3 です 0.67
In order to avoid the new color of vertex become bigger after each iteration due to the concatenation operation and to keep the color description simple, the recoloring σ(·) function is applied after each iteration. 連結操作により各イテレーションの後に頂点の新しい色が大きくなるのを避けるため、色記述をシンプルに保つために、各イテレーションの後に再色 σ(·) 関数を適用する。 0.85
It assigns a new simple color identifier to the any newly created color. 新しい単純な色識別子を新たに作成された色に割り当てる。 0.84
The test is performed in parallel for two graphs. テストは2つのグラフに対して並列に実行される。 0.69
The iterative process is stopped when the color histograms are kept unchanged between two consecutive iterations. カラーヒストグラムが2回連続して変化しない場合には、反復処理を停止する。 0.74
The color histograms associated to the compared graphs are examined. 比較グラフに関連する色ヒストグラムについて検討した。 0.75
If in any iteration the histograms are different, we can conclude that the graphs are not isomorphic. もしどのイテレーションでもヒストグラムが異なるなら、グラフは同型ではないと結論付けることができる。 0.68
However, the opposite conclusion can not be drawn if color histograms are equal as two same histograms may be computed even for non-isomorphic graphs. しかし、色のヒストグラムが2つの同じヒストグラムと等しければ、非同型グラフに対しても逆の結論を導くことはできない。 0.77
Higher order WL tests use the same algorithm while their color update schema is slightly different. 上位のWLテストは同じアルゴリズムを使用し、カラー更新スキーマは若干異なる。 0.73
The 2-WL test uses second order tuple of nodes (all ordered pairs of nodes), thus it needs H ∈ Rn×n matrix, where the initial color set has two more colors than initial vertex colors as defined by: 2-WLテストでは、ノードの2次タプル(全ての順序のペアノード)を使用するため、H ∈ Rn×n行列が必要である。
訳抜け防止モード: 2-WLテストでは、ノードの2次タプル(すべての順序のペアノード)を使用する。 したがって H ∈ Rn×n 行列が必要である。 初期色集合は、次のように定義されている初期頂点色よりも2つの色を持つ。
0.72
(cid:16) |(cid:110) (cid:16) |(cid:110) 0.81
(cid:111)(cid:17) (cid:111)(cid:17) 0.75
 H (0) v edge nonedge H (0)。 v エッジ・ノンエッジ 0.68
H(0) v,u = H(0) v,u = 0.85
if v = u if u ∈ N (v) if u (cid:54)∈ N (v) v = u が u ∈ N (v) が u (cid:54)∂ N (v) であるなら 0.88
(8) Then, the iteration process is applied through the following (8) そして、以下の手順でイテレーションプロセスを適用する。 0.75
3It is generally implemented by stacking all colors in the set 3 一般に、すべての色をセットに重ねて実装する。 0.71
and sorting them alphabetically アルファベット順にソートし 0.68
(cid:16) v,u |(cid:110) (cid:16) v,u |(cid:110) 0.86
(cid:111)|(cid:110) (cid:111)|(cid:110) 0.78
(cid:111)(cid:17) (cid:111)(cid:17) 0.75
, schema where [n] is the set of node identifiers. , schema where [n]はノード識別子のセットです。 0.81
H(t) H(t+1) H(t) H(t+1) 0.85
v,u = σ v,k : k ∈ [n] H(t) v,u = σ v,k : k ∈ [n] H(t) 0.85
k,u : k ∈ [n] H(t) (9) Although for k ≥ 2, (k + 1)-WL is more powerful than (k)-WL, it is not true for k = 1, thus 2-WL (Eq. k,u : k ∈ [n] H(t) (9) k ≥ 2 に対して (k + 1)-WL は (k)-WL よりも強いが、k = 1 ならば 2-WL (Eq) である。 0.81
(9)) is no more powerful than 1-WL (Eq. (9) は 1-wl (eq) よりも強力ではない。 0.73
(7)) (Maron et al , 2019a). (7)) (Maron et al , 2019a。 0.79
To clarify this point, Folkore WL (FWL) test is defined such that 1-WL=1-FWL, but for k ≥ 2, we have (k + 1)-WL ≈ (k)-FWL (Maron et al , 2019a). この点を明らかにするために、Folkore WL (FWL) テストは 1-WL=1-FWL と定義されるが、k ≥ 2 については (k + 1)-WL > (k)-FWL (Maron et al , 2019a) を持つ。 0.82
The iteration process of 2-FWL is given by the following equation; 2-FWLの反復過程は以下の式で与えられる。 0.76
H(t+1) v,u = σ H(t+1) v,u = σ 0.85
H(t) v,k|H(t) H(t) H(t) v,k|H(t) H(t) 0.92
k,u : k ∈ [n] k,u : k ∈ [n] 0.85
, (10) (cid:16) , (10) (cid:16) 0.83
v,u |(cid:110)(cid:16) v,u |(cid:110)(cid:16) 0.86
(cid:111)(cid:17) (cid:111)(cid:17) 0.75
(cid:17) In the literature, there are different interpretations of the order of the WL test. (cid:17) 文献では、WLテストの順序の解釈が異なる。 0.64
Some papers use WL test order to denote the iteration given by Eq (7) and Eq (9) (Morris et al , 2019; Maron et al , 2019a) but some others such as (Abboud et al , 2020; Arvind et al , 2020; Takapoui & Boyd, 2016) use FWL order under the name of WL. 一部の論文では、Eq (7) と Eq (9) (Morris et al , 2019; Maron et al , 2019a) の繰り返しを表すために WL テストオーダーを使用しているが、Abboud et al , 2020; Arvind et al , 2020; Takapoui & Boyd, 2016) のようないくつかの論文では、WL という名前で FWL オーダーを使用している。 0.83
In this paper, we explicitly mention both WL and FWL equivalent such as 3-WL (or 2-FWL) to alleviate ambiguities. 本稿では,3-WL(または2-FWL)のようなWLとFWLの両値について,あいまいさを軽減するために明示的に言及する。
訳抜け防止モード: 本稿では,3-WL(または2-FWL)のようなWLとFWLの等価性について述べる。 曖昧さを和らげるのです
0.64
B. Proofs of Theorems B.1. B。 定理の証明 b.1。 0.72
Theorem.1 Proof. Theorem.1 証明。 0.60
All these methods can be written in Eq (1) by different convolution matrices C. The main idea of the proof is that as long as convolution matrices C can be explained by operations from the enriched set L+ 1 (Remark 4), Eq (1) also can be explained by operations from L+ 1 as well. 証明の主な考え方は、畳み込み行列 C がリッチ集合 L+ 1 (Remark 4) からの演算で説明できる限り、Eq (1) もまた L+ 1 からの演算で説明できるということである。
訳抜け防止モード: これらの方法は全て、異なる畳み込み行列 c によって eq ( 1 ) で書くことができる。 畳み込み行列 c は、リッチ集合 l+ 1 (remark 4 ) からの演算によって説明できる。 eq (1 ) は l+ 1 の演算でも説明できる。
0.66
Thus these methods cannot produce any sentence out of L+ 1 . したがって、これらの方法は l+ 1 からいかなる文も生成できない。 0.63
As a consequence, their expressive power is not more than 1-WL test. その結果、その表現力は1-wlテスト以上のものとなる。 0.67
To provide a proof, the mentioned methods’ convolution matrices have to be expressed using operations from L+ 1 . 証明するために、上記の方法の畳み込み行列は L+ 1 からの演算を用いて表現する必要がある。 0.71
GCN uses C = (D + I)−0.5(A + I)(D + I)−0.5 where D is the diagonal degree matrix (Kipf & Welling, 2017) in Eq.(1). GCN は C = (D + I)−0.5(A + I)(D + I)−0.5 を用いるが、D は Eq.(1) の対角次数行列 (Kipf & Welling, 2017) である。 0.88
(D + I)−0.5 can be expressed as (D + I)−0.5 = diag(f (A1 + 1)), where f (x) = x−0.5 is element-wise operation on vector x. (D + I)−0.5 は (D + I)−0.5 = diag(f (A1 + 1)) と表すことができ、f (x) = x−0.5 はベクトル x 上の要素演算である。 0.83
A + I can also be written A + diag(1). A + I は A + diag(1) とも書くことができる。 0.92
When we merge these equations, we get C = diag(f (A1 + 1))(A + diag(1))diag(f (A1 + 1)). これらの方程式を合併すると、C = diag(f (A1 + 1))(A + diag(1))diag(f (A1 + 1)) が得られる。 0.87
The convolution support C is then written using operations from L+ 1 . 畳み込みサポートCはL+1からの操作を使って記述される。 0.65
In the literature, GraphSage method was proposed to sample neighborhood and aggregate the neighborhood contribution by the mean operator or LSTM in (Hamilton et al , 2017). 文献中では, 平均演算子(LSTM)を用いて, 近傍のサンプルを収集し, 近隣の貢献を集約するグラフサージ法が提案されている(Hamilton et al , 2017)。
訳抜け防止モード: 文献では、サンプル地区にグラフサージ法が提案された。 平均演算子またはLSTM(Hamilton et al, 2017)による近隣貢献を集約する。
0.73
Since we restrict the method using full sampling and mean aggregator, we can define GraphSage by the general framework given by Eq (1) with two convolution supports which are the identity matrix C (1) = I and the row normalized adjacency matrix C (2) = D−1A. 完全サンプリングと平均アグリゲータを用いてメソッドを制限するため、Eq (1) で与えられる一般的なフレームワークで GraphSage を定義できるが、2つの畳み込みサポートは恒等行列 C (1) = I と行正規化隣接行列 C (2) = D−1A である。 0.79
These convolution supports これらの畳み込みは 0.50
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
can also be expressed by operations from L+ 1 , by observing that C (1) = diag(1) and C (2) = diag(f (A1))A, where f (x) = x−1 elementwise operation on vector x. また、c(1) = diag(1) であり、c(2) = diag(f(a1))a であり、ここで f (x) = x−1 のベクトル x 上の要素演算である。
訳抜け防止モード: また、L+1からの操作によっても表現できる。 C ( 1 ) = diag(1 ) そして C ( 2 ) = diag(f ( A1))A , ここで f ( x ) = x−1 はベクトル x 上の要素演算である。
0.89
GIN (Xu et al , 2019) uses a convolution support C = A+I in Eq (1) which is followed by a custom number of MLP layers. GIN (Xu et al , 2019) では、Eq (1) の畳み込みサポート C = A+I を使用しており、その後にカスタム数の MLP 層が続く。 0.77
Each of these layers correspond to a convolution support that can by expressed as Cmlp = I in Eq (1). これらの各層は、eq (1) において cmlp = i で表現できる畳み込みサポートに対応している。 0.78
Finally, these convolution supports can be written thanks to operations from L+ 1 . 最後に、これらの畳み込みサポートはL+ 1の操作のおかげで記述できる。 0.61
C = A + × diag(1) and Cmlp = diag(1). c = a + × diag(1) および cmlp = diag(1) である。 0.88
GAT (Veliˇckovi´c et al , 2018) can be expressed in Eq. GAT (Veli'ckovi ́c et al , 2018) は Eq で表現できる。 0.74
(1) by the convolution support designed by Cv,u = k∈ ˜N (v) m(Hv, Hk), where ˜N (v) is the self-connection added neighborhood of v and m(.) 1) cv によって設計された畳み込み支援により、u = kjava sn (v) m(hv, hk) であり、ここで sn (v) は v と m(.) の自己連結付加近傍である。
訳抜け防止モード: (1 ) cv が設計した畳み込み支援により、u = kjava sn (v ) m(hv,) となる。 n ( v ) は自己-接続を付加した v と m ( .) の近傍である。
0.78
is any trainable model. 訓練可能なモデルです 0.57
If we write the trainable model m(.) トレーニング可能なモデル m(.) を書くと 0.65
as a sum of each node such as m(Hv, Hu) = f1(Hv) + f2(Hu), we can define an intermediate matrix B = diag(f1(H))(A + I) + (A + I)diag(f2(H)). m(Hv, Hu) = f1(Hv) + f2(Hu) のような各ノードの和として、中間行列 B = diag(f1(H))(A + I) + (A + I)diag(f2(H)) を定義することができる。 0.86
Finally the GAT convolution support can be written by C = diag((B1)−1)B using all operations included within the operation set L+ 1 . 最後に、gat畳み込みサポートは c = diag((b1)−1)b で書くことができる。
訳抜け防止モード: 最後に GAT の畳み込みサポートは C = diag((B1)−1)B で書くことができる。 操作セット L+ 1 に含まれるすべての操作を使用する。
0.69
m(Hv, Hu)/(cid:80) m(Hv, Hu)/(cid:80) 1.00
B.2. Theorem.2 B2。 Theorem.2 0.65
Proof. Chebnet (Defferrard et al , 2016) uses desired number k of convolution supports in Eq (1). 証明。 chebnet (defferrard et al , 2016) は eq (1) における畳み込みサポートの所望の数 k を用いる。 0.72
As long as these convolutions can be written by operations in L+ 1 , we can conclude that Chebnet is no more powerful than 1-WL test. これらの畳み込みが L+ 1 の演算によって記述できる限り、Chebnet は 1-WL テストほど強力ではないと結論付けることができる。 0.73
But if at least one convolution cannot be explained in L+ 1 , we can say it is more powerful than 1-WL test. しかし、少なくとも1つの畳み込みが L+ 1 で説明できないなら、1-WL テストよりも強力であると言える。 0.80
Chebnet’s convolution supports are C (1) = I, C (2) = 2L/λmax − I, C (k) = 2C (2)C (k−1) − C (k−2). C (1) = I, C (2) = 2L/λmax − I, C (k) = 2C (2)C (k−1) − C (k−2) である。 0.83
The first support can always be written thanks to an operation from L1 since C (1) = diag(1). C (1) = diag(1) であるので、最初のサポートは常に L1 からの操作によって記述できる。 0.77
Both normalized and combinatorial graph Laplacian can also be written as L = diag(A1)− A or L = diag(1) − diag(f (A1))Adiag(f (A1)) where f (x) = x−1/2 elementwise operation on vector x. L = diag(A1)− A あるいは L = diag(1) − diag(f(A1))Adiag(f(A 1)) と書くこともできる。 0.50
If λmax for both graphs are the same, we can use a constant α = 2/λmax. 両グラフの λmax が同じならば、定数 α = 2/λmax を用いることができる。 0.87
The second convolution support can then be written as C (2) = α × L − diag(1). 第二の畳み込みサポートは C (2) = α × L − diag(1) と書くことができる。 0.76
It is then expressed by means of operations from L+ 1 . すると l+ 1 からの演算によって表現される。 0.76
Other convolution supports C (k) = 2C (2)C (k−1) − C (k−2) are created by matrix multiplication and subtraction of previous supports which can all be expressed by mean of operations from L+ 1 . 他の畳み込みサポート c (k) = 2c (2)c (k−1) − c (k−2) は行列の乗算と以前のサポートの減算によって生成される。
訳抜け防止モード: 他の畳み込みサポート C ( k ) = 2C ( 2)C ( k−1 ) − C ( k−2 ) は行列乗算と以前の支持の減算によって生成される。 全ては L+ 1 からの演算で表せる。
0.80
Thus, if the maximum eigenvalues of tested graphs Laplacians are the same, Chebnet is not more powerful than 1-WL. したがって、テストグラフの最大固有値が同じであれば、Chebnet は 1-WL よりも強力ではない。 0.75
However, if the maximum eigenvalues are not the same, C (2) cannot be expressed with the help of the constant value α. しかし、最大固有値が同じでない場合、c (2) は定数値 α の助けを借りて表現できない。 0.69
It means that different coefficients should be used for each graph. これは、グラフごとに異なる係数を使う必要があることを意味する。 0.63
For two tested graphs G and H, we can write G = αG × LG − diag(1) second kernel of Chebnet as C (2) H = αH × LH − diag(1). 2つのテストグラフ G と H に対して、G = αG × LG − diag(1) のチェブネットの第2核を C (2) H = αH × LH − diag(1) と書くことができる。 0.89
If these two graphs are and C (2) 1-WL equivalent, any sentence build on L+ 1 applied on these これら2つのグラフと C (2) 1-WL が同値であれば、これらに適用される L+ 1 上の任意の文が作られる。 0.59
graph is equivalent as well. For instance, we can use the sentences of e(X) = 1(cid:62)X1 with operation in L+ 1 . グラフも同等です。 例えば、e(X) = 1(cid:62)X1 の文を L+ 1 で演算することができる。 0.69
The output of the sentence should be same such e(LG) = e(LH ) yields 1(cid:62)LG1 = 1(cid:62)LH 1. 文の出力は同じで、e(lg) = e(lh ) は 1(cid:62)lg1 = 1(cid:62)lh 1 となる。 0.73
If we assume that Chebnet cannot separate these two graphs, we can calculate one layer ChebNet’s output by second support with the same sentence and they should be the same such e(C (2) H ) yields αG1(cid:62)LG1 = αH 1(cid:62)LH 1. もしChebnetがこれらの2つのグラフを分離できないと仮定すれば、ChebNetの出力を同じ文で2番目のサポートで計算でき、同じ e(C (2) H ) で αG1(cid:62)LG1 = αH 1(cid:62)LH 1 が得られる。 0.84
Last equation has contradiction to the previous one as long as the maximum eigenvalues are not same (i.e αG (cid:54)= αH) and graphs are not regular (i.e 1(cid:62)LG1 > 0 and 1(cid:62)LH 1 > 0 for normalized laplacian). 最後の方程式は、最大固有値が同じでない限り(すなわち αg (cid:54)= αh)、グラフが正則でない(つまり 1(cid:62)lg1 > 0 と 1(cid:62)lh 1 > 0 である)。 0.77
This contradiction says that assumption is wrong, so one layer Chebnet’s second support can distinguish 1-WL equivalent graphs whose maximum eigenvalues are not same and graphs are not regular with the same degree. この矛盾は仮定が間違っていると言うので、チェブネットの第2層は最大固有値が同じでグラフが同じ次数で正規でない1-WL同値グラフを区別することができる。 0.77
G ) = e(C (2) G ) = e(C (2) 0.85
Since the graph laplacians are positive semi-definite, it always yields 1(cid:62)LG1 ≥ 0 and 1(cid:62)LH 1 ≥ 0 and they are zero as long as the graphs are regular with the same degree. グラフラプラシアンは正半定値であるため、常に 1(cid:62)LG1 ≥ 0 と 1(cid:62)LH 1 ≥ 0 を生成し、グラフが同じ次数で正規である限りは 0 である。 0.90
Thus, if we add smallest positive scalar value on the diagonal of the laplacian such L ← L + I, we get rid of the necessity that graphs must be non-regular. したがって、ラプラシアンの対角線上に最小の正のスカラー値(英語版)(scalar value)を加えると、グラフは非正則でなければならないという必要性を排除できる。
訳抜け防止モード: したがって、ラプラシアンの対角線上に最小の正のスカラー値を加えると、 L > L + >I である。 グラフが非正規でなければならない必要性を取り除く。
0.65
So Chebnet become more powerful and will be able to distinguish all 1-WL equivalent regular graphs whose maximum eigenvalues are different. したがって、Chebnetはより強力になり、最大固有値が異なる全ての1-WL同値正規グラフを区別することができる。 0.69
Considering the graph8c task, we have seen that classic ChebNet could not distinguish 44 pairs where there are 312 1-WL equivalent pairs. Graph8cタスクを考えると、従来のChebNetでは、312の1-WL相当のペアが存在する44のペアを区別できない。 0.65
If we use L ← L + 0.01I, the number of undistinguished pairs of graph decreased from 44 to 19, where 19 undistinguished pairs are all 1-WL equivalent and have exact the same maximum eigenvalues. L > L + 0.01I を使用すると、未識別グラフのペア数は 44 から 19 に減少し、19 個の未識別グラフはいずれも 1-WL 同値であり、全く同じ最大固有値を持つ。 0.73
On the other hand, original Chebnet was not able to distinguish 44-19=25 graphs pairs whose maximum eigenvalues are different but all of them are regular thus 1(cid:62)L1 = 0. 一方、オリジナルのChebnetは最大固有値が異なる44-19=25グラフ対を区別できなかったが、これらは全て正則であり、1(cid:62)L1 = 0である。 0.76
B.3. Theorem.3 B3。 Theorem.3 0.64
(cid:80) Proof. (cid:80) 証明。 0.70
The number of 3-star patterns can be determined by 3つ星のパターンの数は 0.55
(cid:1) where d(v) is the degree of vertex v for undi- (cid:1) d(v) がundi の頂点 v の次数である場合 0.72
(cid:0)d(v) (cid:0)d(v) 0.94
v 3 x! rected simple graphs (Pinar et al , 2017). v 3 x! rected simple graphs (pinar et al , 2017) を参照。 0.86
Using f (x) = (x−3)!3! f (x) = (x−3)! 0.74
as a function that operates on each element of a given vector x, we can calculate the number of 3-star patterns in a given adjacency matrix A by 1(cid:62)f (A1) using operations in L+ 1 . 与えられたベクトル x の各元で作用する関数として、L+ 1 の演算を用いて、与えられた隣接行列 A の3つ星パターンの数を 1(cid:62)f (A1) で計算できる。 0.78
According to the universal approximation theory of multi layer perceptron (Hornik et al , 1989), if we have enough layers, we can implement f (.) 多層パーセプトロンの普遍近似理論 (hornik et al, 1989) によれば、十分な層があれば f(.) を実装できる。 0.71
as an MLP in our model. 私たちのモデルにおけるMLPとして。 0.64
B.4. Theorem.4 B.4。 Theorem.4 0.63
Proof. The number of triangles can be determined by using trace operator as 1/6 × tr(A3) (Harary & Manvel, 1971) which can be written by means of operations from L+ 2 . 証明。 三角形の数はトレース演算子を 1/6 × tr(a3) (harary & manvel, 1971) とすることで決定できる。
訳抜け防止モード: 証明。 トライアングルの数はトレース演算子を用いて 1/6 × tr(a3 ) (harary & manvel, 1971 ) として決定できる。 l+ 2 からの操作で書くことができる。
0.68
Number of 4-cycles is determined by 1/8 × (tr(A4) + tr(A2) − 21(cid:62)A21) (Harary & Manvel, 1971) which can be 4サイクルの数は、1/8 × (tr(A4) + tr(A2) − 21(cid:62)A21) (Harary & Manvel, 1971) によって決定される。 0.82
英語(論文から抽出)日本語訳スコア
written by means of operations from L+ 2 . l+ 2 からの操作によって書かれる。 0.69
B.7. Theorem.7 B.7。 Theorem.7 0.62
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
B.5. Theorem.5 B.5。 Theorem.5 0.63
tailed triangles can be found by (cid:80) 尾の三角形は (cid:80) 0.77
Proof. If t(v) denotes the number triangles including vertex v and d(v) denotes the degree of vertex v, the number of v t(v). 証明。 t(v) が頂点 v を含む数三角形を表し、d(v) が頂点 v の次数を表すならば、v t(v) の数である。 0.72
(d(v) − 2) for simple undirected graphs (Pinar et al , 2017). (d(v) − 2 for simple undirected graphs (Pinar et al , 2017)。 0.79
Every node in a triangle has two closed walks of length 3. 三角形のすべてのノードは長さ3の2つの閉ウォークを持つ。 0.67
Thus, t(v) = (A3)v,v It yields the number of tailed triangles can be 2 × 1(cid:62)(A3 (cid:12) diag(A1 − 2))1. したがって、t(v) = (a3)v,v は尾三角形の数を 2 × 1 (cid:62)(a3 (cid:12) diag(a1 − 2))1 とすることができる。 0.81
The computation found by 1 of t(v) which involves the element-wise multiplication can be written with operations from L+ 3 . 要素ワイズ乗算を含む t(v) の 1 で見つかる計算は、L+ 3 からの演算で書くことができる。 0.80
. 2 B.6. Theorem.6 Proof. . 2 B.6。 Theorem.6 証明。 0.77
Since the sentences in M L(L1) produce a scalar value which can be reached in the graph readout layer as a sum thanks to 1(cid:62)H (lend), we need to show that the MPNN can produce all possible vectors in L1 on the last node representation layer. M L(L1) の文は 1(cid:62)H (lend) のおかげでグラフ読み出し層に到達可能なスカラー値を生成するので、MPNN が最後のノード表現層上で L1 の可能なベクトルを全て生成できることを示す必要がある。 0.83
Since H (0) = 1, the output of the first layer consists of linear combination of [1, A1] because, in this case, the third term of the sum is just 1 ◦ 1 = 1. H (0) = 1 であるため、第一層の出力は [1, A1] の線型結合からなる。
訳抜け防止モード: h ( 0 ) = 1 であるため、第一層の出力は [ 1, a1 ] の線形結合からなる。 この場合、和の3番目の項は 1 で 1 = 1 である。
0.77
On the second layer, the representation consists of a linear transformation of 4 different vectors [1, A1, A21, A1◦A1]. 第2の層では、表現は 4 つの異なるベクトル [1, A1, A21, A1, A1] の線型変換からなる。 0.78
We can notice that these 4 vectors are the all possible vectors that L1 can produce up to the second level. これら 4 つのベクトルが L1 が 2 階まで生成できるすべてのベクトルであることに気づく。 0.79
The diag operator can produce other outputs if we apply diag(A1).diag(A1)1 = A1 ◦ A1. diag(A1).diag(A1)1 = A1 > A1 を適用すれば、他の出力を生成することができる。 0.67
Because diag(1) = I cannot change anything if we use it any other expressions. diag(1) = なので、他の式を使っても何も変えられない。 0.69
Another selection would be A.diag(A1)1 = A21 and last option gives diag(A1)A1 = A1 ◦ A1. もう一つの選択は A.diag(A1)1 = A21 であり、最後の選択は diag(A1)A1 = A1 > A1 を与える。 0.69
So up to l = 2 the proof is true. したがって、 l = 2 までの証明は真である。 0.79
Then, we follow an inductive reasoning and assume that in the k-th layer, Eq (2) produces all possible vectors (h1, . そして帰納的推論に従い、k 層において Eq (2) がすべての可能なベクトル (h1, ) を生成すると仮定する。 0.77
. . hn) in L1 and we show that it is true for k + 1-th layer as well. . . hn) は L1 において、k + 1 層にも当てはまることを示す。 0.81
In the k + 1-th layer, the first term of the sum keeps h1, . k + 1 層において、和の最初の項は h1, である。 0.78
. . hn. The second term produces Ah1, . . . ん? 第二項は Ah1, である。 0.70
. . Ahn. Finally, the term of the sum produces all pairs of elementwise multiplication such as h1 ◦ h1, h1 ◦ h2, . . . Ahn 最後に、和の項は、h1 と h1 と h1 と h2 のすべての要素乗算を生成する。 0.73
. . hn ◦ hn. . . 略称は「hn」。 0.70
These are the all vectors that the language {., 1, diag} can produce using one extra A and/or diag operator. これらは言語 {., 1, diag} が1つの余分な A および/または diag 演算子を使って生成できる全てのベクトルである。 0.76
The transpose operator is neglected because the adjacency matrix is symmetric. 共役行列が対称であるため、転置演算子は無視される。 0.65
Furthermore, since at the readout layer these vectors are to be summed up, their order or the fact that they are transposed or not does not matter. さらに、読み出し層ではこれらのベクトルは要約されるので、それらの順序またはそれらが転置されるか否かは重要ではない。 0.74
Beside, it was also shown that diag(.) そのほか、diag(.)も示されている。 0.60
operator can be implemented by element-wise multiplication of vectors in (Geerts, 2020) in Proposition 8.1. 演算子は、(Geerts, 2020) におけるベクトルの要素ワイド乗法により、命題8.1で実装できる。 0.62
Proof. If the given function is Φ(λ), it can be written by power series using the Maclaurin expansion as follows: 証明。 与えられた函数が φ(λ) であれば、次のようなマクローリン展開を用いて級数で書くことができる。 0.69
Φ(λ) = Φ(0) Φ(λ) = Φ(0) 0.85
0! λ0 + Φ(cid:48)(0) 1! 0! λ0 + φ(cid:48)(0) 1! 0.84
λ1 + Φ(2)(0) λ1 + Φ(2)(0) 0.87
2! λ2 + . . 2! λ2 + . . 0.88
. . (11) Thus, the frequency response can be written by power series with coefficients αi = Φ(i)(0) . . . (11) したがって、周波数応答は係数 αi = φ(i)(0) を持つ級数で書くことができる。 0.82
Using these coefficients, the convolution support can be formulated as C = α0U IU(cid:62)+α1U diag(λ)U(cid:62)+α2U diag(λ)2U(cid:62)+. これらの係数を用いて、畳み込み支持はC = α0U IU(cid:62)+α1U diag(λ)U(cid:62)+α2U diag(λ)2U(cid:62)+と定式化できる。 0.67
. . . (12) Since U IU(cid:62) = I = L0 and U diag(λ)nU(cid:62) = Ln, we can reach the final expression: . . . (12) U IU(cid:62) = I = L0 かつ U diag(λ)nU(cid:62) = Ln なので、最後の式に到達できる。 0.85
i! C = α0L0 + α1L1 + α2L2 + . 私! C = α0L0 + α1L1 + α2L2 + 。 0.66
. . (13) The convolution support C is expressed as power series of graph laplacian L as long as all order derivation of frequency response is not zero (Φ(n)(0) (cid:54)= 0). . . (13) 畳み込み支持Cは、周波数応答のすべての順序導出がゼロでない限り、グラフラプラシアンLのパワー級数として表される(i(n)(0) (cid:54)= 0)。 0.82
Since the selection of the function is based on exp(.) 関数の選択は exp(.) に基づいているからである。 0.86
and its derivation is never null, we can conclude that designed convolution support can be written by power series of graph Laplacian. その導出は決してnullではなく、設計された畳み込みサポートはグラフラプラシアンの級数で書くことができると結論付けることができる。
訳抜け防止モード: そしてその導出は決して null ではない。 結論づけることができます 畳み込みのサポートはグラフラプラシアンのパワーシリーズで記述できる。
0.69
C. L1 Equivalent Graphs C. L1 等価グラフ 0.78
Figure 4. Decalin and Bicyclopentyl graphs are L1 equivalent and so 1-WL. 図4。 デカリンとビシクロペンチルグラフはL1同値であり、1-WLである。 0.65
Figure 4, shows Decalin and Bicyclopentyl graphs, with a proposed node enumeration. 図4はデカリンとビシクロペンチルグラフを示し、ノード列挙を提案する。 0.76
According to these enumerations, their adjacency matrices are AG and AH, respectively これらの列挙によれば、それらの隣接行列はそれぞれ AG と AH である。 0.59
 AG=  AG= 0.82
0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0.85
 and AH =  AH = AH = AH。 0.70
0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0.85
 Their normalized Laplacian can be calculated by L = I − D−1/2AD−1/2 and gives LG and LH as follows:  正規化されたラプラシアンは L = I − D−1/2AD−1/2 で計算でき、以下にLGとLHを与える。
訳抜け防止モード:  正規化ラプラシアンは L = I − D−1/2AD−1/2 で計算できる。 LG と LH を以下に示す。
0.74
1 −0.33 −0.41 1 −0.33 −0.41 0.47
0 −0.41  0 −0.41  0.72
−0.33 −0.41 −0.33 −0.41 0.39
1 0 0 0 0 0 0 1 0 0 0 0 0 0 0.85
0 0 0 −0.41 0 0 0 −0.41 0.74
−0.41 0 0 0 −0.41 −0.41 0 0 0 −0.41 0.60
LG= 0 0 −0.41 0 1 −0.5 LG= 0 0 −0.41 0 1 −0.5 0.71
0 0 −0.5 0 1 −0.5 0 −0.5 0 0 0 0 0 0 0 −0.5 0 1 −0.5 0 −0.5 0 0 0 0 0 0.69
0 0 1 −0.5 0 −0.5 0 0 0 0 0 0 1 −0.5 0 −0.5 0 0 0 0 0.76
0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0.85
0 0 0 0 0 0 1 −0.5 0 −0.5 0 0 0 0 0 0 0 1 −0.5 0 −0.5 0 0.81
0 0 0 0 0 0 1 −0.5 0 −0.5 0 0 0 0 0 0 1 −0.5 0 −0.5 0.76
0 0 −0.41 0 0 0 0 0 1 −0.5 0 0 −0.41 0 0 0 0 0 1 −0.5 0.76
0 0 0 0 0 0 0 0 0 0 0 0 0.85
1 −0.5  1 −0.5  0.72
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks 0 −0.41 0 0 1 −0.5 メッセージパッシンググラフニューラルネットワークの限界を破る 0 −0.41 0 0 1 −0.5 0.89
0 −0.41 0 0 0 −0.41 0 0 0.74
0 G) = tr(A2 0 G) = tr(A2) 0.87
G) = tr(A4 G) = tr(A4) 0.89
G) = tr(A3 G) = tr(A5 G) = tr(A3 G) = tr(A5) 0.94
H ) = 48, tr(A4 H ) = 920). H) = 48, tr(A4 H ) = 920。 0.80
graphs, the trace of any power of the adjacency matrix which gives the number of closed walks, is the same, we conclude that the trace operator does not help to distinguish these two graphs. 閉ウォークの数を与える隣接行列の任意のパワーのトレースであるグラフは同じであり、トレース演算子はこれら2つのグラフを区別するのに役立ちません。 0.72
For instance, it can be verified that the trace of the adjacency matrix up to its 5th power is equal: tr(A2 H ) = 40, tr(A3 H ) = 360, and tr(A5 However, the sentence e(X) = 1(cid:62)((X (cid:12) X 2)21)2 which implements the element-wise multiplication from L3 allows to distinguish both graphs. tr(A2 H ) = 40, tr(A3 H ) = 360, and tr(A5) しかし、e(X) = 1(cid:62)((X (cid:12) X 2)21)2 という文は L3 からの要素ワイド乗法を実装しているため、二つのグラフを区別することができる。
訳抜け防止モード: 例えば、隣接行列の5番目の力までの痕跡は tr(a2 h ) = 40 である。 tr(a3 h ) = 360, tr(a5) しかし、要素を実装する文 e(x ) = 1(cid:62)((x ( cid:12 ) x 2)21)2 は、l3 と賢明に乗算することで、両方のグラフを区別することができる。
0.79
Indeed, the computation of this sentences on AG and AH gives 1(cid:62)((AG (cid:12) A2 G)21)2 = 6032 and 1(cid:62)((AH (cid:12) A2 H )21)2 = 5872. 実際、AG および AH 上のこの文の計算は 1(cid:62)((AG (cid:12) A2 G)21)2 = 6032 と 1(cid:62)((AH (cid:12) A2 H )21)2 = 5872 を与える。 0.85
Thus, these two graphs are not L3 equivalent (it means not 3-WL or 2-FWL equivalent as well) because the sample sentence can be explained in L3. したがって、この2つのグラフは L3 と同値ではない(つまり 3-WL や 2-FWL も同値ではない)。 0.65
E. L3 Equivalent Graphs Strongly regular graphs are known to be 3-WL equivalent and L3 equivalent as well. E. L3 等価グラフ 強い正則グラフは 3 WL 等価かつ L3 等価であることが知られている。 0.76
Figure 6 shows sample nonisomorphic graphs that are L3 equivalent. 図6は L3 と同値な非同型グラフのサンプルを示す。 0.71
  0.85
0 0 0 −0.41 0 0 0 0 0 1 −0.5 0 0 0 −0.41 0 0 0 0 0 1 −0.5 0.81
0 0 0 0 0 0 0 0 0 0 0 0 0.85
1  1  0.85
1 −0.33 −0.41 1 −0.33 −0.41 0.47
0 0 0 0 0 0 0 0 0 0 0 0 0.85
1 0 0 0 0 LH = 1 0 0 0 0 LH= 0.84
−0.5 −0.41 −0.5 −0.41 0.47
−0.33 −0.41 −0.33 −0.41 0.39
1 0 0 −0.50 0 0 1 0 0 −0.50 0 0 0.82
0 0 0 −0.41 0 0 0 −0.41 0 0 0 −0.41 0 0 0 −0.41 0.71
0 1 −0.5 0 −0.5 0 0 0 0 0 0 1 −0.5 0 −0.5 0 0 0 0 0 0.76
0 0 0 0 −0.5 1 0 −0.50 0 0 0 0 0 −0.5 1 0 −0.50 0 0.74
0 0 1 −0.5 0 −0.5 0 0 0 0 0 0 1 −0.5 0 −0.5 0 0 0 0 0.76
G 1 = −9.9327 and yH = 1(cid:62)C (2) G1 = −9.9327 および yH = 1(cid:62)C (2) 0.86
0 0 0 0 0 0 1 −0.5 0 −0.5 Their second Chebnet convolution supports are C (2) G = H = 2/1.8418LH − I because their 2/2LG − I and C (2) maximum eigenvalues are 2.0 and 1.8418 respectively. 0 0 0 0 0 0 1 −0.5 0 −0.5 チェブネットの第二の畳み込みは C (2) G = H = 2/1.8418LH − I である。
訳抜け防止モード: 0 0 0 0 0 0 1 −0.5 0 −0.5 2番目のチェブネットの畳み込みは C ( 2 ) G = H = 2/1.8418LH − I である。 2/2LG − I と C ( 2 ) の最大固有値はそれぞれ 2.0 と 1.8418 である。
0.66
Finally, when computing the output of the first layer by linear activation function without any learning parameters, we obtain yG = 1(cid:62)C (2) H 1 = −9.9269. 最後に、線形活性化関数による第1層の出力を学習パラメータなしで計算すると、yG = 1(cid:62)C (2) H1 = −9.9269 が得られる。 0.80
We observe a slight difference between these two values, which means that Chebnet can project both graphs to the different points, thus it is able to distinguish them. この2つの値のわずかな違いを観察した。つまり、chebnetは両方のグラフを異なる点に投影できるため、それらを区別することができる。 0.79
Since the maximum eigenvalues of graphs Laplacians are different, they are not cospectral as well. ラプラシアングラフの最大固有値は異なるので、それらはコスペクトラルでもない。 0.69
It means that they can also be distinguished on the basis of the number closed walks for some lengths which can be determined by trace operator. これはまた、トレース演算子によって決定できる長さのクローズドウォークの数に基づいて区別することもできることを意味する。 0.74
Indeed, even if up to 4th power of the adjacency matrix, the trace operator gives the same values for both graphs, we can observe that tr(A5 G) = 0 whereas H ) = 20. 実際、隣接行列の4番目の力まで、トレース作用素は両方のグラフに対して同じ値を与えるが、 tr(a5 g) = 0 に対して h ) = 20 は観測できる。 0.78
This observation is sufficient to claim that tr(A5 both graphs are not L2 equivalent. この観察は、tr(a5) の両グラフが l2 等価でないと主張するには十分である。 0.57
D. L2 Equivalent Graphs Figure 5 shows two non-isomorphic but L2 equivalent graphs, where vertices are enumerated. D. L2 等価グラフ 図5は、頂点を列挙する2つの非同型であるが L2 等価グラフを示している。 0.62
Figure 5. Cospectral and 4-regular graphs from (Van Dam & Haemers, 2003) are L2 equivalent. 図5。 cospectral と 4-正則グラフ (van dam & haemers, 2003) は l2 等価である。 0.77
Figure 6. Strongly regular graph pair. 図6。 強正則グラフ対。 0.64
4 × 4-rook’s graph and the Shrikhande graph from (Arvind et al , 2020) are L3 equivalent. 4 × 4-rook のグラフと (Arvind et al , 2020) のシュリケンデグラフは、L3 と同値である。 0.86
According to these enumerations, their adjacency matrices are the following: これらの列挙によれば、隣接行列は以下の通りである。 0.56
 AG=  AG= 0.82
0 1 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0.85
  and AH = と AH = である。 0.80
0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0.85
 seen have eigenvalues  固有値があり 0.73
We cian [0, 0.44, 0.61, 0.75, 1.25, 1.25, 1.25, 1.25, 1.56, 1.64]. We cian [0, 0.44, 0.61, 0.75, 1.25, 1.25, 1.25, 1.25, 1.56, 1.64]. 0.70
Thus, they are cospectral. したがって、それらはコスペクラルである。 0.51
Considering that for cospectral コスペクショナルに考えると 0.61
normalized λH normalized λH 0.88
Lapla= their λG that are ラプラ= λgは それは 0.62
= When we enumerate the nodes from the top-left to the bottom-right according to their locations in the Figure 6, their adjacency matrices are the following: = 図6にある位置に応じて左上から右下へのノードを列挙すると、その隣接行列は以下のようになる。 0.76
  0.85
AG= 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 AG= 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 0.82
  0.85
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0.85
  0.85
  0.85
AH = G)21)2 = 1(cid:62)((AH (cid:12) A2 AH= G)21)2 = 1(cid:62)((AH (cid:12) A2 0.86
H )21)2 = 331776. H)21)2 = 331776。 0.79
The eigenvalues of the normalized Laplacian are equal (λG = λH). 正規化されたラプラシアンの固有値は等しい(λG = λH)。 0.65
Both normalized Laplacians have 3 distinct eigenvalues which are 0, 0.667 and 1.33 with the respective multiplicity of 1, 6 and 9. どちらの正規化ラプラシアンも0, 0.667, 1.33の3つの異なる固有値を持ち、それぞれ1, 6, 9である。 0.67
Thus the graphs are cospectral. したがって、グラフは余スペクトルである。 0.58
Since they are 3-WL equivalent, none of the sentences in L3 can distinguish these graphs. 3WL同値であるため、L3の文はいずれもこれらのグラフを区別できない。 0.72
For instance, we have seen that 1(cid:62)((AG (cid:12) A2 In order to distinguish these two graphs, we need to mimic the 3-FWL (or 4-WL) test which needs a 3-order relationship between nodes. 例えば、1(cid:62)((AG (cid:12) A2 これら2つのグラフを区別するために、ノード間の3次関係を必要とする3-FWL(または4-WL)テストを模倣する必要がある。 0.77
Thus, the adjacencies will be represented by AG, AH ∈ R16×16×16. したがって、隣接は AG, AH ∈ R16×16×16 で表される。 0.71
For any 3 nodes there are 3 different pairs and thus 23 = 8 different states representing how these 3 nodes are connected or not. 任意の3つのノードには3つの異なるペアがあり、23 = 8の異なる状態が3つのノードがどのように接続されているかを表す。 0.67
An additional state is used for the tensor diagonal. テンソル対角線には追加の状態が用いられる。 0.75
Thus, there is a total of 9 states. 合計で9つの州がある。 0.54
The node tuple is denoted by Ai,j,k ∈ {0, . ノードタプルは、ai,j,k ∈ {0, と表記される。 0.72
. . , 8}. 0 refers to the fact that none of three nodes are connected. . . , 8}. 0は3つのノードが接続されていないという事実を指す。 0.82
7 refers to the fact that all nodes are mutually connected (triangle). 7はすべてのノードが相互に連結であるという事実を指す。 0.68
8 is used for the tensor diagonal elements. 8はテンソル対角要素に使用される。 0.75
We can then define an equivariant 3 dimensional tensor square operator s(As,j,k.Ai,s,k.Ai,j ,s). すると、同変3次元テンソル平方作用素 s(As,j,k.Ai,s,k.Ai,j ,s) を定義できる。 0.71
By summing all elements of the 3-dimensional squared adjacency where the given adjacency is for instance 0, we can distinguish these G(cid:12)(AG= 0)) = 205632 whereas H (cid:12) (AH = 0)) = 208704. 例えば、与えられた隣接が 0 である3次元正方行列のすべての元を和ることにより、これらの G(cid:12)(AG= 0)) = 205632 と H (cid:12) (AH = 0)) = 208704 を区別することができる。 0.70
We can then conclude that と結論付けることができる。 0.41
by (A2)i,j,k =(cid:80) two graphs. a2)i,j,k =(cid:80) 2つのグラフによって。 0.75
Indeed,(cid:80)(A2 (cid:80)(A2 実際、(cid:80)(A2(cid:80)( A2) 0.71
these two graphs are not 3-FWL (or 4-WL) equivalent. これら2つのグラフは3-FWL(または4-WL)同値ではない。 0.58
F. Result of TU Datasets Table 5 shows the results of 10-fold cross validation over studied datasets named MUTAG, ENZYMES, PROTEINS and PTC. F. TU Datasets Table 5の結果は、MUTAG, ENZYMES, PROTEINS, PTCという研究データセットに対する10倍のクロス検証の結果を示している。 0.75
All these datasets consist of chemical molecules where nodes refer to atoms while edges refer to atomic bonds. これらのデータセットは、ノードが原子を、エッジが原子結合を、それぞれ参照する化学分子で構成されている。
訳抜け防止モード: これらのデータセットはすべて化学分子で構成されており ノードは原子、エッジは原子結合を参照。
0.74
For these molecular datasets, node features is a one hot coding of atom types and none of the model use any edge feature even if it exists for MUTAG. これらの分子データセットでは、ノード機能は原子型の1つのホットコーディングであり、MUTAGに存在してもどのモデルもエッジ機能を使用しない。 0.78
In addition to these results, we also provide results on the ENZYMES dataset using extra 18-length continuous features on atoms. これらの結果に加えて, ENZYMESデータセットにも, 原子上の18長連続的な特徴を付加した結果が得られた。 0.70
Using these continuous features, graph agnostic method MLP performance increases drastically from 30.8% to 70.6%, showing that these continuous features contain at least a part of the structural information. これらの連続的な特徴を用いることで、グラフに依存しないMLPの性能は30.8%から70.6%へと大幅に向上し、これらの連続的な特徴が構造情報の少なくとも一部を含んでいることを示す。 0.60
Models were ran for a fixed number of epochs on each fold and we select the epoch where the general accuracy is maximum on the validation set. モデルは各折りたたみに対して一定数のエポックで実行され、バリデーションセットで一般的な精度が最大となるエポックを選択する。 0.60
The test procedure and train/validation split was taken from (Xu et al , 2019). 試験手順と列車/バリデーションの分割は (xu et al , 2019) から取られた。 0.75
G. Datasets and Application Details Table 6 shows the summary of the dataset used in experimental evaluation. G.データセットとアプリケーション詳細表6は、実験評価で使用されるデータセットの概要を示す。 0.79
The evaluation has been performed on four differents tasks depending on the dataset. 評価はデータセットに応じて4つの異なるタスクで実施されている。 0.70
These are graph isomorphism (Iso), graph regression (Reg), node regression (NReg) and n-class graph classification task (#-Class). これらはグラフ同型(Iso)、グラフ回帰(Reg)、ノード回帰(NReg)、nクラスグラフ分類タスク(#-Class)である。
訳抜け防止モード: これらはグラフ同型(イソ)、グラフ回帰(Reg)である。 node regression ( NReg ) と n - class graph classification task (# -Class )。
0.89
We did not use any edge features even if some were available. たとえ利用可能であったとしても、エッジ機能は使用していません。 0.47
All features were defined on nodes. すべての機能はノード上で定義された。 0.58
These features were discrete node labels coded by one-hot vectors (#Label) and/or continuous features referred by numbers in Tab. これらの機能は1ホットベクトル(#Label)でコード化された離散ノードラベルであり、Tabの数値で参照される/または連続的な機能である。 0.51
6. We can notice that some graphs have no feature on nodes. 6. ノードに機能がないグラフもいくつかあります。 0.76
We get the Graph8c and Sr25 dataset from online sources4, EXP dataset from (Abboud et al , 2020), Random graph dataset from (Chen et al , 2020), 2D-Grid and Band-Pass dataset from (Balcilar et al , 2021), Zinc12K from (Dwivedi et al , 2020), Mnist-75 dataset from online source5 which was used in (Balcilar et al , 2021) with exactly the same procedure, PROTEINS, ENZYMES, MUTAG and PTC from TU dataset (Morris et al , 2020) downloaded from resources of (Xu et al , 2019). オンラインソース4からgraph8cおよびsr25データセット、(abboud et al , 2020)からexpデータセット、(chen et al , 2020)からランダムグラフデータセット、(balcilar et al , 2021)から2dグリッドおよびband-passデータセット、(dwivedi et al , 2020)から亜鉛12kデータセット、(balcilar et al , 2021)で使用されたオンラインソース5からmnist-75データセット、全く同じ手順で(balcilar et al , 2021)、tuデータセットからタンパク質、酵素、mutagおよびptcがダウンロードされた(morris et al , 2020)。 0.75
All dataset except for EXP, Random and 2-D grid graph were used on a single task. EXP、Random、および2次元グリッドグラフを除く全てのデータセットは、1つのタスクで使用された。 0.66
We used EXP for graph isomorphism test and binary classification task. グラフ同型テストと二分分類タスクにEXPを用いた。 0.74
2D-Grid graph was used for three different node regression tasks respectively on low-pass, band-pass and high-pass filtering effect prediction. 2D-Gridグラフは低域通過,帯域通過,高域通過フィルタ効果予測の3つの異なるノード回帰タスクに利用された。 0.62
Finally, Random graph is used on five different substructure counting tasks. 最後に、ランダムグラフは5つの異なる部分構造カウントタスクで使用される。 0.67
In all cases, we used roughly 30K trainable parameters for all problems and all models. すべてのケースでは、すべての問題とすべてのモデルに約30Kのトレーニング可能なパラメータを使用しました。 0.58
We tuned the number of layers from 2 to 5 and the number of convolution kernels in Chebnet from 3 to 5. 2から5までのレイヤー数と3から5までのChebnetの畳み込みカーネル数を調整した。 0.68
We used Adam optimization with learning rate in [10−2, 10−3] and a weight decay in [10−3, 10−4, 10−5]. 学習速度は [10−2, 10−3] で, [10−3, 10−4, 10−5] では重量減衰が見られた。 0.68
We also used dropout layer before all graph convolution layers under selection of [0, 0.1, 0.2] dropout rate. また,[0, 0.1, 0.2]ドロップアウト率の選択において,すべてのグラフ畳み込み層の前にドロップアウト層を用いた。 0.63
We used ReLU as non-linearity operation in all layers if it is not mentioned explicitly for any specific model. 特定のモデルに明示的に言及されていない場合、ReLUをすべてのレイヤで非線形操作として使用しました。 0.54
For classification problems, the loss function was implemented through cross-entropy. 分類問題に対しては,クロスエントロピーにより損失関数を実装した。 0.65
For regression problems, mean squared error was used as the loss function except on Zinc12K dataset where the loss function was mean absolute error. 回帰問題では、損失関数が絶対誤差である亜鉛12kデータセット以外の損失関数として平均二乗誤差が用いられた。 0.75
Unless otherwise specified, we used both sum and max readout layer after last layer of graph convolution. その他の指定がなければ、最後のグラフ畳み込みの後、sum層とmax層の両方を使用しました。 0.60
It is then followed by a fully connected layer which ended up with output layer. その後、完全に接続された層に続き、最終的に出力層となる。 0.74
In GNNML3, we use the eigendecomposition of normalized Laplacian to calculate the initial edge feature for all problems, except for Zinc12K and substructure counting problems where the eigen decomposition was performed on the adjacency. GNNML3では、正規化ラプラシアンの固有分解を用いて、Zinc12Kと、固有分解が隣接して行われる部分構造カウント問題を除いて、すべての問題に対する初期エッジ特徴を計算する。 0.58
Each initial convolution support is set such それぞれの初期畳み込みサポートが設定される。 0.61
4http://users.cecs.a nu.edu.au/∼bdm/data/graphs.html 5https://graphics.cs .tu-dortmund.de/fileadmin/ls7- 4http://users.cecs.a nu.edu.au/\bdm/data/ graphs.html 5https://graphics.cs .tu-dortmund.de/file admin/ls7- 0.19
www/misc/cvpr/mnist- superpixels.tar.gz www/misc/cvpr/mnist- superpixels.tar.gz 0.17
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
Table 5. Results on TU datasets. テーブル5。 TUデータセットの結果。 0.78
The values are the accuracy. Edge features are not used even if they are available in the datasets. 値は正確さです。 エッジ機能は、データセットで利用可能であっても使用されない。 0.75
The models use a one-hot encoding of node labels as node features, while the models also use extra 18 length continuous node features for ENZYMES-cont. モデルではノードの特徴としてノードラベルを1ホット符号化し、ENZYMES-contには追加で18の連続ノード機能を使用する。 0.74
MODEL MLP GCN GAT GIN CHEBNET PPGN GNNML1 GNNML3 モデル MLPGCN GAT GINCHEBNET PPGN GNNML1 GNNML3 0.72
MUTAG 86.6% ± 4.95 89.1% ± 5.81 90.1% ± 5.84 89.4% ± 5.60 89.7% ± 6.41 90.2% ± 6.62 90.0% ± 0.42 90.9% ± 5.46 ムタガ 86.6% ± 4.95 89.1% ± 5.81 90.1% ± 5.84 89.4% ± 5.60 89.7% ± 6.41 90.2% ± 6.62 90.0% ± 0.42 90.9% ± 5.46 0.45
ENZYMES 30.8% ± 4.26 49.0% ± 4.25 54.1% ± 5.15 55.8% ± 5.23 63.8% ± 7.92 55.2% ± 5.44 54.9% ± 5.97 63.6% ± 6.52 ENZYMES 30.8% ± 4.26 49.0% ± 4.25 54.1% ± 5.15 55.8% ± 5.23 63.8% ± 7.92 55.2% ± 5.44 54.9% ± 5.97 63.6% ± 6.52 0.61
ENZYMES-CONT 70.6% ± 5.22 74.2% ± 3.26 73.7% ± 4.47 73.3% ± 4.48 75.3% ± 4.63 72.9% ± 4.18 76.9% ± 5.14 78.1% ± 5.05 ENZYMES-CONT 70.6% ± 5.22 74.2% ± 3.26 73.7% ± 4.47 73.3% ± 4.48 75.3% ± 4.63 72.9% ± 4.18 76.9% ± 5.14 78.1% ± 5.05 0.59
PROTEINS 74.3% ± 4.88 75.2% ± 5.11 75.9% ± 4.26 76.1% ± 3.97 76.4% ± 5.34 77.2% ± 4.53 75.8% ± 4.93 76.4% ± 5.10 PROTEINS 74.3% ± 4.88 75.2% ± 5.11 75.9% ± 4.26 76.1% ± 3.97 76.4% ± 5.34 77.2% ± 4.53 75.8% ± 4.93 76.4% ± 5.10 0.61
PTC 62.9% ± 5.89 64.3% ± 8.35 65.7% ± 7.97 64.6% ± 7.00 65.5% ± 4.94 66.2% ± 6.54 63.9% ± 6.37 66.7% ± 6.49 PTC 62.9% ± 5.89 64.3% ± 8.35 65.7% ± 7.97 64.6% ± 7.00 65.5% ± 4.94 66.2% ± 6.54 63.9% ± 6.37 66.7% ± 6.49 0.72
TASK GRAPHS NODES EDGES FEATURE TRAIN VAL TEST タスクグラフ ノードエッジ 機能トレインvalテスト 0.36
GRAPH8C ISO Graph8C ISO 0.64
11117 8.0 28.82 MONO 11117 8.0 28.82 MONO 0.72
NA NA NA SR25 ISO 15 25.0 300.0 MONO NA NA NA SR25 ISO 15 25.0 300.0 MONO 0.77
NA NA NA Table 6. NA NA NA 表6。 0.79
Summary of the datasets used in our experiments. 実験で使用したデータセットの概要。 0.75
EXP 2D-GRID EXP 2dグリッド 0.63
RANDOM BAND-PASS RANDOM バンドパス 0.69
PROTEINS ENZYMES ISO&2CLASS タンパク質 酵素 ISO&2CLASS 0.58
1200 44.44 110.21 MONO 800 200 200 1200 44.44 110.21 MONO 800 200 200 0.78
NREG 900.0 3480.0 国鉄 900.0 3480.0 0.43
3 1 1 1 1 REG 5K 18.8 62.67 MONO 1500 1000 2500 3 1 1 1 1 REG 5K 18.8 62.67 MONO 1500 1000 2500 0.82
2CLASS 5K 200.0 1072.6 2CLASS 5K 200.0 1072.6 0.65
1 3K 1K 1K 1 3K 1K 1K 0.74
2CLASS 1113 39.06 72.82 3LABEL 9-FOLD 1-FOLD 2CLASS 1113 39.06 72.82 3LABEL 9-FOLD 1-FOLD 0.52
NA 6CLASS 600 32.63 62.14 NA 6CLASS 600 32.63 62.14 0.74
9-FOLD 1-FOLD 9-FOLD 1-FOLD 0.50
NA 3LABEL+18 NA 3LABEL+18 0.66
MUTAG 2CLASS MUTAG 2CLASS 0.88
188 17.93 39.58 7LABEL 9-FOLD 1-FOLD 188 17.93 39.58 7LABEL 9-FOLD 1-FOLD 0.51
NA PTC 2CLASS NA PTC 2CLASS 0.83
344 25.55 51.92 344 25.55 51.92 0.59
19LABEL 9-FOLD 1-FOLD 19LABEL 9-FOLD 1-FOLD 0.52
NA MNIST-75 10CLASS NA MNIST-75 10CLASS 0.72
70K 75.0 694.7 70K 75.0 694.7 0.52
1 55K 5K 10K 1 55K 5K 10K 0.76
ZINC12K REG 12K 23.15 49.83 ZINC12K REG 12K 23.15 49.83 0.59
10K 1K 1K 21LABEL 10K 1K 1K 21LABEL 0.73
that Φs(λ) = exp(−b(λ − fs)2), where the bandwidth parameter b is set to the value of 5. φs(λ) = exp(−b(λ − fs)2) ここで帯域幅パラメータbは5の値に設定される。 0.82
The spectrum has been uniformly sampled between minimum eigenvalue and the maximum eigenvalue with a selection of sn = [3, 5, 10] points in order to select the band specific parameter. スペクトルは、バンド固有パラメータを選択するために、sn = [3, 5, 10] 個の選択により、最小固有値と最大固有値の間で一様にサンプリングされている。 0.73
Thus, band specific parameter of each frequency profile can be written sn−1 (λmax − λmin) for s ∈ {1, . したがって、各周波数プロファイルのバンド固有パラメータは s ∈ {1, に対して sn−1 (λmax − λmin) と書くことができる。 0.67
. . , sn − 1}. . . sn − 1} である。 0.83
fs = λmin + s−1 For the convolution support s = 0, we used all-pass filtering named identity matrix whose frequency response is Φ0(λ) = 1. fs = λmin + s−1 畳み込みサポート s = 0 に対して、周波数応答が φ0(λ) = 1 である恒等行列と呼ばれる全パスフィルタリングを用いた。 0.74
Thus, we have a total of sn convolution supports. したがって、sn畳み込みサポートは合計で十分です。 0.56
The 1-hop distance is always used for receptive field which corresponds to M = A + I. 1ホップ距離は常に m = a + i に対応する受容体に使用される。 0.76
For the learning of convolution supports needed in Eq (5), we used a single layered MLP in each mlpk where mlp1, mlp2, mlp3 : RS → R2S with a sigmoid activation, and mlp4 : R4S → RS with ReLU activation as long as S is the number of initial convolutions extracted in the preprocessing step. eq (5) に必要な畳み込みサポートの学習には、mlp1, mlp2, mlp3 : rs → r2s でシグモイド活性化を行い、mlp4 : r4s → rs が前処理ステップで抽出された初期畳み込みの数である限り、reluアクティベーションを持つ mlpk の各 mlpk において1層 mlp を用いた。 0.74
In Eq (6), the size of the output of mlp5 and mlp6 is another hyperparameter where we used the same length with the first part of the Eq. eq (6) では、mlp5 と mlp6 の出力の大きさは、eq の最初の部分と同じ長さを用いた別のハイパーパラメータである。 0.86
(6) defined by dimension of W (l,s). (6)W(l,s)の次元で定義される。 0.75
Mentioned hyperparamters are optimzed for concerned model according to validation set performance if it is available. 前述のハイパーパラメッターは、利用可能であれば検証セットのパフォーマンスに従って、関連するモデルに最適化される。 0.62
For TU dataset, since the validation and test set is not available in public split, we first created a hyperparameter tuning task by dividing the dataset one time into pre-training (80%) and pre-validation (20%). TUデータセットでは、検証とテストセットがパブリック分割では利用できないため、データセットを事前トレーニング(80%)と事前検証(20%)に分割することで、まずハイパーパラメータチューニングタスクを作成しました。 0.74
The optimal value of the parameters is searched on the basis of the performance on the pre-validation set. パラメータの最適値は、プレバリデーションセットの性能に基づいて探索される。 0.65
Then, these hyperparameter values for the general test procedure as defined in (Xu et al , 2019). 次に、これらのテスト手順のハイパーパラメータ値を定義した(Xu et al , 2019)。 0.76
Our tests were conducted with implementations of Chebnet, GCN, GIN and GAT layer provided by pytorch-geometric 本試験はChebnet, GCN, GIN, GAT層をピトルチ幾何法で実装して行った。 0.62
(Fey & Lenssen, 2019). (Fey & Lenssen, 2019)。 0.82
Besides, PPGN, GNNML1 and GNNML3 layer were implemented as a class of pytorchgeometric and our models were tested on the basis of these implementation. さらに, PPGN, GNNML1, GNNML3層をピトルヒゲメトリックのクラスとして実装し, これらの実装に基づいて実験を行った。 0.82
By doing so, we integrate the PPGN into the widely used graph library pytorch-geometric and make it publicly available beside our own proposals. これにより、PPGNを広く使われているグラフライブラリpytorch-geometricに統合し、我々の提案とともに公開します。 0.81
H. Summary of the Baseline Models H.1. H. ベースラインモデルH.1の概要 0.83
MPNN Baselines MPNNベースライン 0.78
In this section of the appendix, we present the baseline methods which are GCN, GIN, Chebnet and GAT thanks to the general framework given by Eq (1). 本項では,Eq(1)の一般的な枠組みにより,GCN,GIN,Chebnet,GAT となる基本的手法について述べる。 0.62
Each model differs from others by selection of their convolution support C. GCN uses a single convolution support given by; C = (D + I)−0.5(A + I)(D + I)−0.5, gcnは、c = (d + i)−0.5(a + i)(d + i)−0.5 で与えられる単一の畳み込みサポートを使用する。 0.54
(14) where D is the diagonal degree matrix (Kipf & Welling, 2017) in Eq (1). (14) ここで D は Eq (1) の対角次数行列(Kipf & Welling, 2017)である。 0.81
Chebnet relies on the approximation of a spectral graph analysis proposed in (Hammond et al , 2011), based on the Chebyshev polynomial expansion of the scaled graph Laplacian. チェブネットは(Hammond et al , 2011)で提案されたスペクトルグラフ解析の近似に頼っており、スケールしたグラフラプラシアンのチェビシェフ多項式展開に基づいている。 0.88
The number of convolution supports C (k) can be chosen. C(k)を支持する畳み込みの数を選択することができる。 0.74
They are defined by (Defferrard et al , 2016) as follows: これらは (Defferrard et al , 2016) によって次のように定義される。 0.73
C (k) = 2C (2)C (k−1) − C (k−2), C (k) = 2C (2)C (k−1) − C (k−2) 0.97
C (1) = I, C (2) = 2L/λmax − I, ∀k ≥ 2. C (1) = I, C (2) = 2L/λmax − I, sk ≥ 2 0.91
(15) Graph Isomorphism Network (GIN) defined in (Xu et al , (15) Xu et al で定義されたグラフ同型ネットワーク(GIN) 0.79
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
2019) has a single convolution support defined as follows: 2019年) 単一の畳み込みサポートが次のように定義されている。 0.55
C = A + (1 + )I, C = A + (1 + s)I, 0.84
(16) where  is a parameter that makes the support trainable. (16) ここで s は、サポートをトレーニング可能にするパラメータである。 0.70
Another version named GIN-0 is also defined in the same paper where  = 0, which makes C = A + I. GIN-0 という別のバージョンも同じ論文で定義されているが、ここでは C = A + I となる。 0.74
GIN proposes to use a desired number of MLP after each graph convolution. GINは各グラフの畳み込み後に所望数のMLPを使用することを提案する。 0.69
In our implementation, we use one MLP (C = I) after each GIN graph convolution as described in (Xu et al , 2019). 実装では、GINグラフの畳み込み後に1つのMLP(C = I)を使用する(Xu et al , 2019)。 0.68
Graph attention networks (GATs) in (Veliˇckovi´c et al , 2018) proposes to transpose the attention mechanism from (Vaswani et al , 2017) into the graph world by the way of sparse attention instead of full attention in transformers. Veli ckovi ́c et al , 2018) のグラフアテンションネットワーク (GAT) は、(Vaswani et al , 2017) からのアテンションメカニズムを、トランスフォーマーの完全なアテンションではなく、スパースアテンションの方法でグラフの世界にトランスフォーメーションすることを提案する。 0.60
GAT convolution support can be seen as weighted, self loop added adjacency. GATの畳み込みサポートは、重み付けされた自己ループ追加の隣接と見なすことができる。 0.50
It can be represented in Eq (1) by defining its trainable convolution supports as follows: トレーニング可能な畳み込みサポートを定義することで、Eq (1)で表現することができる。 0.65
(cid:16) C (l,s)(cid:17) (cid:16)C(l,s)(cid:1 7) 0.89
ev,u(cid:80) where ev,u = exp(cid:0)σ(a(l,s)[H (l) ev,u(cid:80) ここで ev,u = exp(cid:0)σ(a(l,s)[H(l)) 0.96
v,u = , k∈ ˜N (v) ev,k :v W (l,s)||H (l) v,u = , k) ev,k :v W (l,s)||H (l) 0.81
(17) :u W (l,s)])(cid:1), (17) :u W (l,s)] (cid:1) 0.81
and a(l,s) is another trainable weight. a(l,s) もまたトレーニング可能な重みです。 0.61
Convolution support will be calculated from node v to each element of ˜N (v), which shows the self-connection added neighborhood. 畳み込みサポートは、ノードvから、自己連結付加近傍を示す sn (v) の各要素に計算される。 0.63
In application of GAT, we use concatenation instead of sum in Eq. GAT の応用では、Eq の和の代わりに連結を用いる。 0.72
(1) where the paper proposed both and there is slightly empirical advantage to use concatenation. 1) 論文の双方が提案され, 結合性を利用する上で, 若干の利点がある。 0.70
All MPNN baselines start with a given node features H (0) and provide the node representation of the next layer by Eq.(1). すべてのMPNNベースラインは、与えられたノードの特徴H(0)から始まり、Eq.(1)によって次のレイヤのノード表現を提供する。 0.76
After the last layer, we apply a graph readout function which summarizes the learned node representation. 最後のレイヤの後に、学習したノード表現を要約するグラフ読み取り機能を適用する。 0.74
Graph readout layer is followed by a desired number of fully connected layers ended with a number of neuron defined by targeted number of classes. グラフ読み出し層は、目的とするクラス数で定義されたニューロン数で終わる、所望の数の完全連結層に続きます。 0.74
H.2. PPGN Baseline H.2。 PPGNベースライン 0.71
PPGN (Maron et al , 2019a) starts the process with a 3dimensional input tensor where the adjacency, edge features (if it exists) and diagonalized node features are stacked on the 3rd dimension as: PPGN (Maron et al , 2019a) は、3次元入力テンソルでプロセスを開始する。
訳抜け防止モード: PPGN (Maron et al, 2019a ) は3次元入力テンソルでプロセスを開始する。 エッジの特徴(もし存在するなら) 対角化ノードの特徴は 3次元に積み重ねられます
0.75
H (0) = [A|E1|···|Ee|diag(X1)|···|diag(Xd)]. H (0) = [A|E1|···|Ee|diag(X1)|···|diag(Xd)] 0.61
(18) Here, X ∈ Rn×d gathers node features and Xi is its i-th column vector, E ∈ Rn×n×e is edge features and Ei ∈ Rn×n is its i-th edge feature matrix, thus initial feature tensor is H (0) ∈ Rn×n×(1+e+d). 18) ここで、X ∈ Rn×d はノード特徴を集め、Xi はその i 番目のカラムベクトル、E ∈ Rn×n×e はエッジ特徴、Ei ∈ Rn×n は i 番目のエッジ特徴行列であり、したがって初期特徴テンソルは H (0) ∈ Rn×n×(1+e+d) である。 0.78
One layer forward calculation of PPNN would be: PPNNの1層フォワード計算は次のとおりである。 0.65
(cid:16)(cid:2)m1(H (l)) ◦ m2(H (l))|H (l)(cid:3)(cid:17) (cid:16)(cid:2)m1(H( l)) >m2(H(l))|H(l)(cid:3)(cid:17) 0.85
H (l+1) = m3 H (l+1) = m3 0.82
(19) where m1, m2 : Rn×n×dinp → Rn×n×dmid and m3 : Rn×n×dmid+dinp → Rn×n×dout are trainable models that (19) m1, m2 : Rn×n×dinp → Rn×n×dmid, m3 : Rn×n×dmid+dinp → Rn×n×dout は訓練可能なモデルである。 0.83
can be implemented by a one layer MLP followed by nonlinearity. 一つの層 MLP で実装でき、非線形性が続く。 0.71
dinp is the feature length on the 3rd dimension. dinp は 3 次元の特徴長である。 0.72
dmid, dout are the feature lengths which can be seen as hyperparameters of the layer. dmid, doutは、層のハイパーパラメータとして見ることができる特徴長である。 0.76
Multiplication (◦) operates between matching features and means 2d matrix multiplication for each slice which has n × n dimensions. 乗法は一致する特徴の間で動作し、n×n次元のスライスごとに2次元行列乗算を行う。 0.60
| operator is just the concatenation of two tensor on the 3rd dimension. |演算子は、3次元上の2つのテンソルの連結である。 0.64
The output of the model would be: モデルの出力は次のようになる。 0.75
(cid:16)(cid:88) diag(H (l)) | (cid:88) offdiag(H (l)) (cid:16)(cid:88) diag(H (l)) | (cid:88) offdiag(H (l)) 0.95
(cid:88) (cid:17) (cid:88) (cid:17) 0.78
Y = mlpl . Y = mlpl . 0.85
l=1 (cid:80) l=1 (cid:80) 0.69
(cid:80) : Rd1×d2×d → Rd and a trainable model that may be im- (cid:80) : Rd1×d2×d → Rd および im となる訓練可能なモデル 0.78
(20) We assign a function which selects the diagonal of each 2d slices of tensor as diag : Rn×n×d → Rn×1×d and function for selection the element out of the diagonal as offdiag : Rn×n×d → Rn×(n−1)×d. (20) テンソルの各2dスライスの対角線を選択する関数を diag : Rn×n×d → Rn×1×d とし、対角線から元を選択する関数を offdiag : Rn×n×d → Rn×(n−1)×d とする。 0.85
We use the sum operator which performs sum over the first 2 dimensions as plemented by an MLP mlpl : R2d → Rdy, transforms the given vector into the targeted output representation length. MLP mlpl : R2d → Rdy で補足されたような最初の 2 次元の和演算子を使い、与えられたベクトルを対象の出力表現長に変換する。 0.74
The one can see that in each layer, PPNN keeps H (l) ∈ Rn×n×dl, thus its memory usage is in O(n2). 各層において、ppnn は h (l) ∈ rn×n×dl を保持するので、メモリ使用量は o(n2) である。
訳抜け防止モード: 各層において、PPNN は H ( l ) ∈ Rn×n×dl を保持することが分かる。 したがって、メモリ使用量は O(n2 ) である。
0.81
Since there is a matrix multiplication in Eq (19), its computation complexity is in O(n3) when using the naive matrix multiplication operations. eq (19) には行列乗算があるので、その計算複雑性はネーティブ行列乗算演算を使用する場合の o(n3) にある。 0.77
The PPNN paper mentioned that the computational complexity can be decreased by using effective matrix multiplication, but it is the same for all algorithms as well. PPNNの論文では、効率的な行列乗算を用いて計算複雑性を減少させることができるが、全てのアルゴリズムでも同様である。 0.81
For this reason, we think that taking the naive implementation into account makes more sense to do a fair comparison. この理由から、ナイーブな実装を考慮に入れることは、公正な比較を行う方がより理にかなっていると考えています。
訳抜け防止モード: そのため、我々はそう考える。 素直な実施を考慮に入れれば 公正な比較をする方が理にかなっている
0.65
In addition, again because of matrix multiplication, its update mechanism is not local. さらに、行列の乗算のため、更新メカニズムは局所的ではない。 0.61
Because of calculation of the u, v node pairs representation in Eq (19), it needs to perform k,v. u, v ノード対の eq (19) での表現の計算のため、k,v を実行する必要がある。 0.80
That means that for each pair of nodes, k should be all nodes in the graph regardless how far away the node k from the concerned nodes u, v. In other words, very far away nodes feature affect the concerned node. つまり、各ノードの対に対して、k は、関係ノード u, v からノード k がどこまで離れているかに関わらず、グラフ内のすべてのノードであるべきである。
訳抜け防止モード: つまり、各ノードのペアについて、k は関係ノード u からノード k までの距離に関わらず、グラフ内のすべてのノードであるべきである。 言い換えれば、非常に遠く離れたノード機能は、関連するノードに影響を与える。
0.79
Even though PPNN (Maron et al , 2019a) is a very straight forward algorithm and has provable 3-WL power, the experimental results reported in the papers are not at the state of the art (Maron et al , 2019a; Dwivedi et al , 2020). PPNN (Maron et al , 2019a) は非常にストレートな前進アルゴリズムであり、3WLの出力を証明できるが、論文で報告された実験結果は技術の現状には達していない(Maron et al , 2019a; Dwivedi et al , 2020)。 0.83
We believe that this can be at least partly explained by some implementation problems. これは少なくとも一部は実装の問題によって説明できると信じています。 0.61
Indeed, it was implemented by gathering same size graphs into batches in order to handle graphs of different size in a dataset. 実際、データセットで異なるサイズのグラフを扱うために、同じサイズのグラフをバッチに集めて実装した。 0.70
So the batches do not consist of randomly selected graphs in each epoch during the training phase. したがって、バッチはトレーニング期間中に各エポックでランダムに選択されたグラフで構成されない。 0.65
In our implementation, we first find the maximum size of the graph denoted as nmax. この実装では、まずnmax で表されるグラフの最大サイズを求める。 0.67
Then, we create an initial tensor in Eq (18) in dimension of Rnmax×nmax×1+e+d where left top n × n × 1 + e + d part of the tensor is valid, and the rest is zero. すると、eq (18) における初期テンソルを rnmax×nmax×1+e+d 次元で生成し、左トップ n × n × 1 + e + d の部分のテンソルは有効であり、残りは 0 である。 0.74
We also keep the valid part of the tensor diagonal and out of diagonal part mask in M0, M1 ∈ {0, 1}nmax×nmax that shows which element is valid in the diagonal and which element また、m0, m1 ∈ {0, 1}nmax×nmax の対角面と対角面の有効部分を保持し、どの要素が対角面において有効か、どの要素で有効かを示す。 0.71
u,k.H (l) k H (l) u,k.H(l) k (複数形 ks) 0.73
英語(論文から抽出)日本語訳スコア
Breaking the Limits of Message Passing Graph Neural Networks メッセージパッシンググラフニューラルネットワークの限界を破る 0.43
is valid out of the diagonal of the representation tensor. 表象テンソルの対角線外において有効である。 0.57
Since some part of the tensor H (l) are not valid, we need to prevent to assign value after application of trainable model mk in Eq (19), because it affects the matrix multiplication result. テンソル H (l) の一部が有効でないため、行列乗法の結果に影響を及ぼすため、Eq (19) でのトレーニング可能なモデル mk の適用後に値を割り当てることを防ぐ必要がある。 0.81
One solution may be to mask the MLP result by M0 + M1. 1つの解決策は、M0 + M1 で MLP 結果を隠すことである。 0.66
Finally, we implement Eq (20) by selection diagonal and off-diagonal element by previously 最後に、従来の対角・対角要素の選択によりeq(20)を実装する。 0.64
prepared mask matrices by(cid:80) diag(H (l)) =(cid:80) M0 (cid:12) H (l) and(cid:80) offdiag(H (l)) = (cid:80) M1 (cid:12) H (l). (cid:80) diag(h (l)) =(cid:80) m0 (cid:12) h (l) および(cid:80) offdiag(h (l)) = (cid:80) m1 (cid:12) h (l) によるマスク行列の作成 0.79
By doing so, we そうすることで、私たちは 0.64
can put any graph into same batch. グラフを同じバッチにまとめることができます 0.76
These principles have been implemented as a class of the widely used open-source pytorch geometric library. これらの原則は、広く使われているオープンソースのpytorch幾何ライブラリのクラスとして実装されている。 0.61
                                     ページの最初に戻る

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