DGL 0.5 ユーザガイド : 1 章 グラフ : 1.1 〜 1.3 基本定義と特徴 (翻訳/解説)
翻訳 : (株)クラスキャット セールスインフォメーション
作成日時 : 09/14/2020 (0.5.1)
* 本ページは、DGL の以下のドキュメントを翻訳した上で適宜、補足説明したものです：
- Chapter 1: Graph
- 1.1 Some Basic Definitions about Graphs (Graphs 101)
- 1.2 Graphs, Nodes, and Edges
- 1.3 Node and Edge Features
* サンプルコードの動作確認はしておりますが、必要な場合には適宜、追加改変しています。
* ご自由にリンクを張って頂いてかまいませんが、sales-info@classcat.com までご一報いただけると嬉しいです。
ユーザガイド : 1 章 グラフ
グラフは実在 (ノード) をそれらの関係 (エッジ) とともに表現します、そしてノードとエッジの両者は型付けられます (e.g., 「ユーザ」と「項目」はノードの 2 つの異なる型です。)。DGL は中核のデータ構造 – DGLGraph を持つグラフ中心なプログラミング抽象を提供します。DGLGraph はグラフの構造、ノード/エッジ特徴、そしてこれらのコンポーネントを使用して遂行できる結果としての計算を処理するためのインターフェイスを提供します。
1.1 グラフに関する幾つかの基本的な定義 (グラフ 101)
グラフ \(G=(V, E)\) は実在と関係を表すために使用される構造です。それは 2 つのセットから成ります – ノードのセット \(V\) (頂点とも呼称) とエッジのセット \(E\) (arc とも呼称) です。ノード \(u\) と \(v\) のペアに接続するエッジ \((u, v) \in E\) はそれらの間に関係があることを示します。この関係は無向, e.g. ノード間の対称関係を捕捉するか、非対称な関係を捕捉する有向のいずれかであり得ます。例えば、グラフがソーシャルネットワークの人々の交友関係をモデル化するために使用されるのであれば、交友関係は相互的ですのでエッジは無向です ; けれども、グラフが Twitter 上で人々がどのように互いをフォローするかをモデル化するために使用される場合は、エッジは有向です。エッジの方向性に依拠して、グラフは 有向 か 無向 かであり得ます。
グラフは重み付けられても、重み付けられなくても構いません。重み付きグラフでは、各エッジはスカラー重みと関連付けられます。例えば、そのような重みは長さや接続強度を表すかもしれません。
グラフはまた均質的 (= homogeneous) でも異質的 (= heterogeneous) でもあり得ます。均質的グラフでは、総てのノードは同じタイプのインスタンスを表しそして総てのエッジは同じタイプの関係を表します。例えば、ソーシャルネットワークは人々と彼ら・彼女らの接続から成るグラフで、同じ実在タイプを表しています。
対称的に、異質的グラフでは、ノードとエッジは異なるタイプであり得ます。例えば、マーケットプレイスをエンコードするグラフは買い手 (= buyer)、売り手 (= seller) と製品ノードを持ち、これらは wants-to-buy, has-bought, is-customer-of そして is-selling エッジを通して接続されます。2 部 (= bipartite) グラフは異質的グラフの特別な、一般に利用されるタイプで、そこではエッジは 2 つの異なるタイプのノード間に存在します。例えば、レコメンダシステムでは、ユーザと項目の間の相互作用を表す 2 部グラフを利用できます。DGL で異質的グラフで作業するためには、1.5 Heterogeneous Graphs を見てください。
マルチグラフは、自己ループ (= self loop) を含む、ノードの同じペアの間に複数の (有向) エッジを持てるグラフです。例えば、2 人の著者は異なる年々でペーパーを共同執筆できて、これは異なる特徴を持つエッジという結果になります。
1.2 グラフ、ノードとエッジ
DGL は各ノードをノード ID と呼ばれる一意の整数で、そして各エッジをエンドノードの ID に対応する整数のペアにより表します。DGL はグラフに追加された順序に基づいて、各エッジに エッジ ID と呼ばれる一意の整数を割当てます。ノードとエッジ ID の番号付けは 0 から始まります。DGL では、総てのエッジは有向で、エッジ \((u, v)\) は方向がノード $u$ からノード $v$ に進むことを示しています。
マルチノードを指定するために、DGL はノード ID の 1-D 整数 tensor (i.e., PyTorch の tensor, TensorFlow の Tensor または MXNet の ndarray) を使用します。DGL はこの形式を「ノード-tensor」と呼びます。マルチエッジを指定するためには、それはノード-tensor \((U, V)\) のタプルを使用します。\((U[i], V[i])\) は \(U[i]\) から \(V[i]\) へのエッジを決定します。
DGLGraph を作成する一つの方法は dgl.graph() メソッドを使用することで、これは入力としてエッジのセットを取ります。DGL はまた他のデータソースからグラフを作成することもサポートします、1.4 Creating Graphs from External Sources を見てください。
次のコードスニペットは下で示される 4-ノード・グラフに対応するDGLGraph を作成するために dgl.graph() メソッドを使用し、グラフの構造を問い合わせるためにその API の幾つかを例示しています。
>>> import dgl
>>> import torch as th
>>> # edges 0->1, 0->2, 0->3, 1->3
>>> u, v = th.tensor([0, 0, 0, 1]), th.tensor([1, 2, 3, 3])
>>> g = dgl.graph((u, v))
>>> print(g) # number of nodes are inferred from the max node IDs in the given edges
Graph(num_nodes=4, num_edges=4,
ndata_schemes={}
edata_schemes={})
>>> # Node IDs
>>> print(g.nodes())
tensor([0, 1, 2, 3])
>>> # Edge end nodes
>>> print(g.edges())
(tensor([0, 0, 0, 1]), tensor([1, 2, 3, 3]))
>>> # Edge end nodes and edge IDs
>>> print(g.edges(form='all'))
(tensor([0, 0, 0, 1]), tensor([1, 2, 3, 3]), tensor([0, 1, 2, 3]))
>>> # If the node with the largest ID is isolated (meaning no edges),
>>> # then one needs to explicitly set the number of nodes
>>> g = dgl.graph((u, v), num_nodes=8)
無向グラフについては、両者の方向に対してエッジを作成する必要があります。この場合 dgl.to_bidirected() は有用であり得ます、これはグラフを両者の方向のためのエッジを持つ新しいものに変換します。
>>> bg = dgl.to_bidirected(g) >>> bg.edges() (tensor([0, 0, 0, 1, 1, 2, 3, 3]), tensor([1, 2, 3, 0, 3, 0, 0, 1]))
Note: Tensor 型は C の効率的な内部ストレージと明示的なデータ型とデバイスコンテキスト情報により DGL API を通して一般に選択されます。けれども、殆どの DGL API は素早いプロトタイピングのために引数として python iterable (e.g., リスト) や numpy.ndarray をサポートします。
DGL はノードとエッジ ID をストアするために $32$- または $64$- ビット整数のいずれかを利用できます。ノードとエッジ ID のためのデータ型は同じであるべきです。$64$ ビットを使用することにより、DGL は \(2^{63} – 1\) ノードかエッジまでを持つグラフを扱うことができます。けれども、グラフが \(2^{31} – 1\) 未満のノードかエッジを含む場合には、$32$-ビット整数を使用するべきです、何故ならばそれはより良い速度に繋がり少ないメモリだけを必要とするからです。DGL はそのような変換を行なうためのメソッドを提供します。例として下を見てください。
>>> edges = th.tensor([2, 5, 3]), th.tensor([3, 5, 0]) # edges 2->3, 5->5, 3->0 >>> g64 = dgl.graph(edges) # DGL uses int64 by default >>> print(g64.idtype) torch.int64 >>> g32 = dgl.graph(edges, idtype=th.int32) # create a int32 graph >>> g32.idtype torch.int32 >>> g64_2 = g32.long() # convert to int64 >>> g64_2.idtype torch.int64 >>> g32_2 = g64.int() # convert to int32 >>> g32_2.idtype torch.int32
API 参照: dgl.graph(), dgl.DGLGraph.nodes(), dgl.DGLGraph.edges(), dgl.to_bidirected(), dgl.DGLGraph.int(), dgl.DGLGraph.long() そして dgl.DGLGraph.idtype。
1.3 ノードとエッジ特徴
DGLGraph のノードとエッジは、ノードとエッジのグラフ固有のプロパティをストアするために幾つかのユーザ定義の名前付き特徴を持つことができます。これらの特徴は ndata と edata インターフェイスを通してアクセスできます。例えば、次のコードは (行 5 と 9 の ‘x’ と ‘y’ と命名された) 2 つのノード特徴と (行 6 の’x’ と命名された) 1 つのエッジ特徴を作成します。
01. >>> import dgl
02. >>> import torch as th
03. >>> g = dgl.graph(([0, 0, 1, 5], [1, 2, 2, 0])) # 6 nodes, 4 edges
04. >>> g
Graph(num_nodes=6, num_edges=4,
ndata_schemes={}
edata_schemes={})
05. >>> g.ndata['x'] = th.ones(g.num_nodes(), 3) # node feature of length 3
06. >>> g.edata['x'] = th.ones(g.num_edges(), dtype=th.int32) # scalar integer feature
07. >>> g
Graph(num_nodes=6, num_edges=4,
ndata_schemes={'x' : Scheme(shape=(3,), dtype=torch.float32)}
edata_schemes={'x' : Scheme(shape=(,), dtype=torch.int32)})
08. >>> # different names can have different shapes
09. >>> g.ndata['y'] = th.randn(g.num_nodes(), 5)
10. >>> g.ndata['x'][1] # get node 1's feature
tensor([1., 1., 1.])
11. >>> g.edata['x'][th.tensor([0, 3])] # get features of edge 0 and 3
tensor([1, 1], dtype=torch.int32)
ndata/edata インターフェイスの重要な事実は :
- 数値型 (e.g., float, double と int) の特徴だけが許容されます。それらはスカラー、ベクトルや多次元 tensor であり得ます。
- 各ノード特徴は一意な名前を持ちそして各エッジ特徴は一意な名前を持ちます。ノードとエッジの特徴は同じ名前を持つことができます (e.g., 上のサンプルの ‘x’)。
- 特徴は tensor 割当てを通して作成されます、これは特徴をグラフの各ノード/エッジに割当てます。その tensor の最初の (= leading) 次元はグラフのノード/エッジの数に等しくなければなりません。特徴をグラフのノード/エッジのサブセットに割り当てることはできません。
- 同じ名前の特徴は同じ次元性とデータ型を持たなければなりません。特徴 tensor は行優先レイアウトにあります – 各行スライスは一つのノードかエッジの特徴をストアします (e.g., 上のサンプルの行 10-11 参照)。
重み付きグラフについては、下のように重みをエッジ特徴としてストアできます。
>>> # edges 0->1, 0->2, 0->3, 1->3
>>> edges = th.tensor([0, 0, 0, 1]), th.tensor([1, 2, 3, 3])
>>> weights = th.tensor([0.1, 0.6, 0.9, 0.7]) # weight of each edge
>>> g = dgl.graph(edges)
>>> g.edata['w'] = weights # give it a name 'w'
>>> g
Graph(num_nodes=4, num_edges=4,
ndata_schemes={}
edata_schemes={'w' : Scheme(shape=(,), dtype=torch.float32)})
以上