그래프 임베딩 개요: 노드, 에지, 그래프 임베딩 방법 및 Python 구현

그래프 기반 머신러닝은 최근 몇 년간 큰 발전을 이루었습니다. 그래프 기반 방법은 링크 예측, 커뮤니티 검색, 노드 분류 등과 같은 데이터 과학의 많은 일반적인 문제에 적용됩니다. 문제를 어떻게 정리하느냐, 가지고 있는 데이터에 따라 문제를 해결하는 방법은 여러 가지가 있습니다. 이 기사에서는 그래프 기반 임베딩 알고리즘에 대한 높은 수준의 개요를 제공합니다. 마지막으로 Python 라이브러리(예: node2vec)를 사용하여 그래프에 다양한 임베딩을 생성하는 방법도 소개합니다.

그래프 기반 머신러닝

인공지능은 추천 시스템, 시계열, 자연어 처리, 컴퓨터 비전, 그래프 머신러닝 등 다양한 분야가 있습니다. 그래프 기반 기계 학습의 일반적인 문제를 해결하는 방법에는 여러 가지가 있습니다. 커뮤니티 발견, 링크 예측, 노드 분류 등을 포함합니다.

그래프 머신러닝의 주요 문제점은 머신러닝 모델이 쉽게 활용할 수 있도록 그래프 구조를 표현(또는 인코딩)하는 방법을 찾는 것입니다[1]. 일반적으로 기계 학습에서 이 문제를 해결하려면 이전에 통계 측정이나 커널 기능을 통해 수행되었던 모델과 관련된 구조화된 표 형식 데이터를 통해 일종의 표현을 학습해야 합니다. 최근 몇 년간 기계 학습 모델 훈련을 위한 임베딩 벡터를 생성하기 위해 그래프를 인코딩하는 경향이 있었습니다.

기계 학습 모델의 목표는 대규모 데이터 세트에서 학습하고 패턴을 인식하도록 기계를 훈련시키는 것입니다. 그래프는 다른 형태의 데이터(예: 텍스트, 오디오 또는 이미지)에 없는 다양하고 복잡한 구조를 제공하므로 그래프 작업 시 이러한 현상이 증폭됩니다. 그래프 기반 기계 학습은 반복되는 기본 패턴을 감지하고 설명할 수 있습니다[2].

저희는 소셜 네트워크 사용자와 관련된 인구통계 정보를 파악하는 데 관심이 있을 수 있습니다. 인구통계학적 데이터에는 연령, 성별, 인종 등이 포함됩니다. Facebook이나 Twitter와 같은 회사의 소셜 미디어 네트워크는 수백만에서 수십억 명의 사용자와 수조 개의 측으로 구성됩니다. 이 네트워크에는 인간이나 알고리즘으로 쉽게 감지할 수 없는 사용자의 인구 통계와 관련된 몇 가지 패턴이 분명히 있지만 모델은 이를 학습할 수 있어야 합니다. 마찬가지로, 우리는 한 쌍의 사용자에게 친구가 되도록 추천하고 싶지만 아직 친구가 아닐 수도 있습니다. 이는 그래프 기반 기계 학습의 또 다른 응용 프로그램인 링크 예측을 위한 자료를 제공합니다.

이미지 임베딩이란 무엇인가요?

특성 엔지니어링은 입력 데이터를 처리하여 원본 데이터 세트를 간결하고 의미 있게 표현하는 특성 세트를 형성하는 일반적인 방법을 의미합니다. 기능 엔지니어링 단계의 결과는 기계 학습 모델에 대한 입력으로 사용됩니다. 이는 표 형식의 구조화된 데이터 세트로 작업할 때 필요한 프로세스이지만, 그래프 데이터로 작업할 때는 수행하기 어려운 접근 방식입니다. 모든 그래프 데이터와 관련된 적절한 표현을 생성하는 방법을 찾아야 하기 때문입니다.

그래프에서 구조 정보를 나타내는 특징을 생성하는 방법에는 여러 가지가 있습니다. 가장 일반적이고 간단한 방법은 그래프에서 통계를 추출하는 것입니다. 여기에는 인식 분포, 페이지 순위, 중심성 측정항목, Jaccard 점수 등이 포함될 수 있습니다. 그런 다음 필요한 속성은 커널 기능을 통해 모델에 통합되지만 커널 기능의 문제는 결과 생성과 관련된 시간 복잡성이 높다는 것입니다.

최근 연구 동향은 의미 있는 그래프 표현을 찾고 그래프에 포함된 표현을 생성하는 것으로 바뀌었습니다. 이러한 임베딩은 네트워크의 원래 구조를 유지하는 그래프 표현을 학습합니다. 이산 그래프를 연속 영역으로 변환하도록 설계된 매핑 함수라고 생각할 수 있습니다. 함수가 학습되면 그래프에 적용할 수 있으며 결과 매핑은 기계 학습 알고리즘의 기능 세트로 사용될 수 있습니다.

그래프 임베딩 유형

그래프 분석은 3가지 수준의 세분화로 분해될 수 있습니다. 노드 수준, 간선 수준, 그래프 수준(전체 그래프) 각 레벨은 임베딩 벡터를 생성하는 다양한 프로세스로 구성되며, 선택되는 프로세스는 처리 중인 문제와 데이터에 따라 달라집니다. 아래에 제시된 각 세분성 수준 임베딩에는 시각적으로 서로 구별할 수 있는 다이어그램이 함께 제공됩니다.

노드 임베딩

노드 수준에서는 그래프의 각 노드와 연관된 임베딩 벡터가 생성됩니다. 이 임베딩 벡터는 그래프의 표현과 구조를 수용할 수 있습니다. 기본적으로 서로 가까운 노드에는 서로 가까운 벡터도 있어야 합니다. 이는 Node2Vec과 같은 인기 있는 노드 임베딩 모델의 기본 원칙 중 하나입니다.

Edge Embedding

Edge 레이어에서는 그래프의 각 Edge와 관련된 임베딩 벡터가 생성됩니다. 링크 예측 문제는 에지 임베딩을 사용하는 일반적인 응용 프로그램입니다. 링크 예측은 에지가 노드 쌍을 연결하는지 여부를 예측하는 것을 의미합니다. 이러한 임베딩은 그래프에서 제공하는 간선 속성을 학습할 수 있습니다. 예를 들어, 소셜 네트워크 그래프에서는 연령 범위, 성별 등에 따라 노드가 가장자리로 연결될 수 있는 다중 가장자리 그래프가 있을 수 있습니다. 이러한 간선 속성은 간선의 상관 벡터를 표현하여 학습할 수 있습니다.

그래프 임베딩

그래프 수준 임베딩은 일반적이지 않으며 각 그래프를 나타내는 임베딩 벡터를 생성하는 것으로 구성됩니다. 예를 들어, 여러 하위 그래프가 있는 큰 그래프에서 각 해당 하위 그래프에는 그래프 구조를 나타내는 임베딩 벡터가 있습니다. 분류 문제는 그래프 임베딩이 유용할 수 있는 일반적인 응용 분야입니다. 이러한 유형의 문제에는 그래프를 특정 범주로 분류하는 것이 포함됩니다.

Python 구현

Python 코드를 사용하여 필요한 다음 라이브러리를 구현합니다.

Pythnotallow=3.9
 networkx>=2.5
 pandas>=1.2.4
 numpy>=1.20.1
 node2vec>=0.4.4
 karateclub>=1.3.3
 matplotlib>=3.3.4

node2vec 패키지를 설치하지 않은 경우 해당 설명서를 참조하세요. karateclub 패키지 설치는

Node embedding

import random
 import networkx as nx
 import matplotlib.pyplot as plt
 
 from node2vec import Node2Vec
 from node2vec.edges import HadamardEmbedder
 from karateclub import Graph2Vec
 
 plt.style.use("seaborn")
 
 # generate barbell network
 G = nx.barbell_graph(
m1 = 13,
m2 = 7
 )
 
 # node embeddings
 def run_n2v(G, dimensions=64, walk_length=80, num_walks=10, p=1, q=1, window=10):
"""
Given a graph G, this method will run the Node2Vec algorithm trained with the
appropriate parameters passed in.
 
Args:
G (Graph) : The network you want to run node2vec on
 
Returns:
This method will return a model
 
Example:
G = np.barbell_graph(m1=5, m2=3)
mdl = run_n2v(G)
"""
 
mdl = Node2Vec(
G,
dimensions=dimensions,
walk_length=walk_length,
num_walks=num_walks,
p=p,
q=q
)
mdl = mdl.fit(window=window)
return mdl
 
 mdl = run_n2v(G)
 
 # visualize node embeddings
 x_coord = [mdl.wv.get_vector(str(x))[0] for x in G.nodes()]
 y_coord = [mdl.wv.get_vector(str(x))[1] for x in G.nodes()]
 
 plt.clf()
 plt.scatter(x_coord, y_coord)
 plt.xlabel("Dimension 1")
 plt.ylabel("Dimension 2")
 plt.title("2 Dimensional Representation of Node2Vec Algorithm on Barbell Network")
 plt.show()

과 유사합니다. 위 그림은 바벨 그래프로 생성된 시각적 노드 임베딩입니다. node2vec, 딥 워크, 랜덤 워크 등 노드 임베딩을 계산하는 방법이 많이 있습니다. , 등. 여기서는 node2vec가 사용됩니다.

Edge Embedding

edges_embs = HadamardEmbedder(
keyed_vectors=mdl.wv
 )
 
 # visualize embeddings
 coordinates = [
edges_embs[(str(x[0]), str(x[1]))] for x in G.edges()
 ]
 
 plt.clf()
 plt.scatter(coordinates[0], coordinates[1])
 plt.xlabel("Dimension 1")
 plt.ylabel("Dimension 2")
 plt.title("2 Dimensional Representation of Edge Embeddings on Barbell Network")
 plt.show()

바벨 그래프를 통해 엣지 임베딩 시각화를 확인하세요. Hammard Embedder의 소스코드는 여기(https://github.com/eliorc/node2vec/blob/master/node2vec)에서 확인하실 수 있습니다. /가장자리 .py#L91).

Graph embedding

n_graphs = 10
 Graphs = [
nx.fast_gnp_random_graph(
n = random.randint(5,15),
p = random.uniform(0,1)
) for x in range(n_graphs)
 ]
 
 g_mdl = Graph2Vec(dimensions=2)
 g_mdl.fit(Graphs)
 g_emb = g_mdl.get_embedding()
 
 x_coord = [vec[0] for vec in g_emb]
 y_coord = [vec[1] for vec in g_emb]
 
 plt.clf()
 plt.scatter(x_coord, y_coord)
 plt.xlabel("Dimension 1")
 plt.ylabel("Dimension 2")
 plt.title("2 Dimensional Representation of Graph Embeddings on Randomly Generated Networks")
 plt.show()

이것은 무작위로 생성된 그래프의 그래프 임베딩 시각화이며, graph2vec 알고리즘의 소스 코드는 여기에서 찾을 수 있습니다. (https://karateclub.readthedocs.io/en/latest/_modules/karateclub/graph_embedding/graph2vec.html)

Summary

Embedding은 개별 그래프를 벡터 표현으로 매핑하는 기능입니다. 그래프 데이터, 노드 임베딩, 에지 임베딩 및 그래프 임베딩에서 다양한 형태의 임베딩을 생성할 수 있습니다. 세 가지 임베딩 유형 모두 그래프의 초기 구조와 특징을 X 차원의 수치 값에 매핑하는 벡터 표현을 제공합니다.

위 내용은 그래프 임베딩 개요: 노드, 에지, 그래프 임베딩 방법 및 Python 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!