[CS224W GraphML] 1. GraphMLの概要

Graph Representation Learning BookのChapter 1を翻訳して要約した.
Graphは、点と点を接続することで関係を表すことができます.たとえば、ソーシャルネットワークでは、1人をポイントノードとして、2人の友人関係をEdgeとして表すことができます.生物学では、タンパク質はノードであり、タンパク質間の生物学的相互関係はEdgeである.これらの点のプロパティに比べて、Graphはポイント間の関係に重点を置いています.
最近多くのグラフィックデータが開示され,これらのデータに存在する潜在的な情報を明らかにするための研究が行われている.その一つの研究方法は「機械学習」を用いることである.

1.1 Graphとは?

Graph Dataは、ノードセットNNNおよびEdgeセットEEEを用いてG=(N,E)G=(N,E)G=(N,E)G=(N,E)を表す.1つのパターンに属するノード数は「N∣N∣N∣」、Edgeは「∣E∣E∣」と表される.Edge(u,v)∈E(u,v)in E(u,v)∈EはNode u∈Nuin Nu∈NからNode v∈NvNv∈Nに接続する意味を持つ.
隣接行列隣接行列A∈R∣V∣×∣V∣A\in R^{|V|\times|V|}A∈R∣V∣×∣V∣は図形を表すことができる.すべてのノードがColumnとRowにリストされ、接続されている場合は1、接続されていない場合は0と表示されます.次の図に示すように、右側のグラフィックは左側のマトリクスとして表示できます.

import networkx as nx
import numpy as np

adjacency = np.array([
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0],
])

labels={0: "A", 1: "B", 2: "C", 3: "D"}

G = nx.DiGraph(adjacency)
nx.draw(G, labels=labels, node_size=500)

図のエッジが無方向である場合、制御スライダ列AAAは対称行列Symmetric Matrixである.Directedが開始ノードと到着ノードを区別している場合は、対称性は必要ありません.Weighted Edgeの場合、行列値は0と1ではなく実数です.2つのノードの接続強度を表します.

1.1.1 Multi-Relational Graphs

Edgeには、Undirected、Directed、Weighted Edgeと区別するのとは異なるさまざまなタイプがあります.たとえば、2つの薬物間の副作用関係を発現すると、嘔吐、下痢、高熱など、さまざまなパイプを発現することができます.この場合をマルチリレーションシップグラフィックと呼ぶ.多関係グラフィックの一部として、「異機種グラフィック」と「多重グラフィック」があります.
Heterogeneous Graphはノードが複数のタイプに分かれている場合である.例えば、Graphは、タンパク質ノード、薬物ノード、および疾患ノードとして表される.薬物ノードと疾患ノードは、「治療」関係のエッジを有し、薬物ノード間に副作用関係がある可能性がある.
異機種グラフィックの一部として、複数のグラフィックが存在する.マルチパーティショングラフィックはBiparteグラフィックの拡張です.Bipartite Graphは、2つのタイプのノードからなる、同類のノードとは関係のないGraphである.例えば、「ユーザが見る映画」関係図形には、ユーザと映画との間にのみEdgeがあり、映画と映画、またはユーザとユーザのEdgeが接続されていない.ノードに3つ以上のタイプがある場合は、マルチパーティショングラフィックと呼ばれます.
グラフィックが複数のレイヤに分解できる場合、複数のグラフィック.例えば、公共交通の図形を考えてみましょう.出発地と目的地となる位置ノードがあります位置ノードの間には、バスや地下鉄などのエッジがある場合があります.これを接続位置のバスエッジ層と地下鉄エッジ層に分けることができ、この場合を多重パターンと呼ぶ.

1.1.2 Feature Information

グラフィックに関連するプロパティプロパティプロパティ/フィーチャー情報を取得できます.「約ノード」の場合は、主成分などが属性情報である可能性があります.Heterogeneous Graphの場合、タイプが異なるノードの場合、異なるタイプの属性値がある可能性があります.

1.2 Machine Learning on Graphs

機械学習のパターンは、解決したい問題に依存します.デフォルトでは、サポート・タスクは、入力データに基づいてターゲット結果を予測するなど、データを検索するクラスタと区別できます.
GraphMLも従来の方法と似ていますが、サポートが許可されていないかは重要ではありません.主に問題をサポートしていますが、従来の方法の境界はあいまいです.
GraphMLのTaskは大きく4段階に分けられる.

Node Level

Edge Level

Subgraph/Community Level

Graph Level

ここではClassic Graph ML Taskについて説明します.

1.2.1 Node Classification

Node ClassificationはNodeレベルの一種であり、その目標はNodeのLabelを予測することである.Labelはどんなタイプ、カテゴリ、属性などですか.例えば、100万人のユーザーがいるソーシャルネットワークでは、実際のユーザーではなくBotをどのように分類するかという問題があります.一部のユーザーデータに対してLabelingを行い、これらのデータを学習して、ユーザー全体を予測することができます.
AlphaFoldは,Protein Foldling問題を解決するために深い思考で開発された別の例である.タンパク質中のアミノ酸は、ノードとノードとの間の近接度を表す.次いで,各ノードの新しい位置を予測し,それを用いて三次元形態のタンパク質構造を予測した.
標準的なサポート学習とは異なります.最も重要な違いは、グラフィック内のノードが互いに独立していないことです.iidセットを仮定してモデリングするのではなく、ノード間の相互接続をモデリングします.もう1つの違いは,モデルを学習する際に,タグ付けされていないテストノードを半監督ノードとして使用できることである.しかし,既存の半監督手法でもSampleごとにiid仮定が行われているため,相違がある.

1.2.2 Relation Prediction

Edge Levelの1つのタイプはRelation Predictionです.「関係予測」(Relation Prediction)は、失われた関係情報を予測します.もう1つの言い方は、リンク予測、グラフィック埋め込み、および関係情報です.いくつかのタンパク質の関係しか知らない場合、欠失の関係を予測するために使用することができます.また、友人間の友情の「程度」は、嘔吐、嘔吐、高熱を含む薬物間の副作用が「どこに属するか」を予測することができる.

1.2.3 Clustering and Community Detection

クラスタおよび統一性検出は、Subgraphレベルの不正なクラスタメソッドです.入力パターンG=(N,E)G=(N,E)G=(N,E)G=(N,E)が与えられると、内部から複数のSubgraphにクラスタ化される.例えば、遺伝的役割ネットワークでモジュールを機能別に分割したり、金融ネットワークで詐欺組織を検索したりします.
もう1つのSubgraphレベルの例は、Traffice Preditionです.交通状況全体で、始点から目的地までをSubgraphと見なすことができます.これは目的地到着までの所要時間ETAを予測するタスクです.

1.2.4 Graph Classification, Regression, and Clustering

各コンポーネントを1つのグラフィックで予測するのではなく、各グラフィック予測とは独立したグラフィックレベルがあります.グラフィック分類とリカバリは、単一のグラフィックのターゲット値を予測します.グラフィッククラスタは、グラフィックペア間の類似度を計算することによってグループ化されます.グラフィックレベルでは、各グラフィックは独立しているため、標準MLに似ています.