Gambaran keseluruhan pembenaman graf: kaedah benam nod, tepi dan graf serta pelaksanaan Python

Pembelajaran mesin berasaskan graf telah mencapai kemajuan yang besar dalam beberapa tahun kebelakangan ini. Kaedah berasaskan graf mempunyai aplikasi dalam banyak masalah biasa dalam sains data, seperti ramalan pautan, penemuan komuniti, klasifikasi nod, dsb. Terdapat banyak cara untuk menyelesaikan masalah bergantung pada cara anda menyusunnya dan data yang anda miliki. Artikel ini akan memberikan gambaran keseluruhan peringkat tinggi bagi algoritma benam berasaskan graf. Akhir sekali, kami juga akan memperkenalkan cara menggunakan perpustakaan Python (seperti node2vec) untuk menjana pelbagai benam pada graf.

Pembelajaran mesin berasaskan graf

Kecerdasan buatan mempunyai pelbagai cabang, daripada sistem pengesyoran, siri masa, Bahasa semula jadi pemprosesan, penglihatan komputer, pembelajaran mesin graf, dsb. Terdapat pelbagai cara untuk menyelesaikan masalah biasa dengan pembelajaran mesin berasaskan graf. Termasuk penemuan komuniti, ramalan pautan, klasifikasi nod, dsb.

Masalah utama dalam pembelajaran mesin dengan graf ialah mencari cara untuk mewakili (atau mengekod) struktur graf supaya model pembelajaran mesin boleh mengeksploitasinya dengan mudah [1]. Biasanya menyelesaikan masalah ini dalam pembelajaran mesin memerlukan pembelajaran beberapa jenis perwakilan melalui data jadual berstruktur yang dikaitkan dengan model, yang sebelum ini dilakukan melalui pengukuran statistik atau fungsi kernel. Dalam beberapa tahun kebelakangan ini, trend adalah ke arah pengekodan graf untuk menjana vektor benam untuk melatih model pembelajaran mesin.

Matlamat model pembelajaran mesin adalah untuk melatih mesin untuk belajar dan pengecaman corak pada skala dalam set data. Ini diperkuatkan apabila bekerja dengan graf, kerana graf menyediakan struktur yang berbeza dan kompleks yang tidak dimiliki oleh bentuk data lain (seperti teks, audio atau imej). Pembelajaran mesin berasaskan graf boleh mengesan dan menerangkan corak asas yang berulang [2].

Kami mungkin berminat untuk menentukan maklumat demografi yang berkaitan dengan pengguna di rangkaian sosial. Data demografi termasuk umur, jantina, bangsa, dsb. Rangkaian media sosial untuk syarikat seperti Facebook atau Twitter terdiri daripada berjuta-juta hingga berbilion-bilion pengguna dan trilion pihak. Pasti akan ada beberapa corak yang berkaitan dengan demografi pengguna dalam rangkaian ini yang tidak mudah dikesan oleh manusia atau algoritma, tetapi model itu sepatutnya dapat mempelajarinya. Begitu juga, kami mungkin ingin mengesyorkan sepasang pengguna untuk menjadi rakan, tetapi mereka belum lagi berkawan. Ini menyediakan makanan untuk ramalan pautan, satu lagi aplikasi pembelajaran mesin berasaskan graf.

Apakah pembenaman imej?

Kejuruteraan ciri merujuk kepada kaedah biasa memproses data input untuk membentuk satu set ciri yang memberikan perwakilan yang padat dan bermakna bagi set data asal. Keputusan fasa kejuruteraan ciri akan berfungsi sebagai input kepada model pembelajaran mesin. Ini adalah proses yang perlu apabila bekerja dengan set data berstruktur jadual, tetapi merupakan pendekatan yang sukar untuk dilakukan apabila bekerja dengan data graf, kerana cara perlu dicari untuk menjana perwakilan yang sesuai yang dikaitkan dengan semua data graf.

Terdapat beberapa cara untuk menjana ciri yang mewakili maklumat struktur daripada graf. Kaedah yang paling biasa dan mudah ialah mengekstrak statistik daripada graf. Ini boleh termasuk pengedaran pengiktirafan, kedudukan halaman, metrik pusat, skor jaccard, dsb. Atribut yang diperlukan kemudiannya dimasukkan ke dalam model melalui fungsi kernel, tetapi masalah dengan fungsi kernel ialah kerumitan masa yang berkaitan untuk menghasilkan keputusan adalah tinggi.

Arah aliran penyelidikan terkini telah beralih ke arah mencari perwakilan graf yang bermakna dan menjana perwakilan terbenam untuk graf. Pembenaman ini mempelajari perwakilan graf yang mengekalkan struktur asal rangkaian. Kita boleh menganggapnya sebagai fungsi pemetaan yang direka untuk mengubah graf diskret kepada domain berterusan. Setelah fungsi dipelajari, ia boleh digunakan pada graf dan pemetaan yang terhasil boleh digunakan sebagai set ciri untuk algoritma pembelajaran mesin.

Jenis-jenis benam graf

Analisis graf boleh dipecahkan kepada 3 tahap kebutiran. Aras nod, aras tepi dan aras graf (graf keseluruhan). Setiap peringkat terdiri daripada proses berbeza yang menjana vektor benam, dan proses yang dipilih harus bergantung pada masalah dan data yang sedang diproses. Setiap pembenaman tahap butiran yang dibentangkan di bawah mempunyai gambar rajah yang disertakan untuk membezakannya secara visual antara satu sama lain.

Pembenaman Nod

Pada peringkat nod, hasilkan vektor pembenaman yang dikaitkan dengan setiap nod dalam graf. Vektor benam ini boleh menampung perwakilan dan struktur graf. Pada asasnya nod yang berdekatan antara satu sama lain juga harus mempunyai vektor yang berdekatan antara satu sama lain. Ini adalah salah satu prinsip asas model pembenaman nod yang popular seperti Node2Vec.

Pembenam Tepi

Dalam lapisan tepi, vektor pembenaman dijana dikaitkan dengan setiap tepi dalam graf. Masalah ramalan pautan ialah aplikasi biasa menggunakan pembenaman tepi. Ramalan pautan merujuk kepada meramalkan kemungkinan sama ada tepi menghubungkan sepasang nod. Pembenaman ini boleh mempelajari sifat kelebihan yang disediakan oleh graf. Contohnya, dalam graf rangkaian sosial, anda boleh mempunyai graf berbilang tepi yang mana nod boleh disambungkan dengan tepi berdasarkan julat umur, jantina, dsb. Sifat tepi ini boleh dipelajari dengan mewakili vektor korelasi tepi.

Pembenaman graf

Pembenaman peringkat graf adalah jarang berlaku dan ia terdiri daripada menghasilkan vektor pembenaman yang mewakili setiap graf. Contohnya, dalam graf besar dengan berbilang subgraf, setiap subgraf yang sepadan mempunyai vektor pembenaman yang mewakili struktur graf. Masalah klasifikasi ialah aplikasi biasa yang mana pembenaman graf boleh berguna. Jenis masalah ini akan melibatkan pengelasan graf ke dalam kategori tertentu.

Pelaksanaan Python

Menggunakan kod python untuk melaksanakan kami memerlukan perpustakaan berikut

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

Jika anda Pakej node2vec tidak dipasang, sila rujuk dokumentasinya. Pasang pakej karateclub, juga serupa dengan

Pembenam Nod

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()

Gambar di atas ialah visualisasi pembenaman nod yang dihasilkan oleh barbell graf , terdapat banyak kaedah untuk mengira benam nod, seperti node2vec, deep walk, rawak berjalan, dsb. node2vec digunakan di sini.

Pembenam Tepi

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()

Lihat visualisasi pembenaman tepi melalui graf barbel, kod sumber Hammard Embedder boleh didapati di sini (https://github.com/eliorc/node2vec/blob/master/node2vec/edges.py#L91).

Pembenaman graf

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()

Ini ialah visualisasi pembenaman graf bagi graf yang dijana secara rawak, kod sumber algoritma graph2vec Boleh didapati di sini. (https://karateclub.readthedocs.io/en/latest/_modules/karateclub/graph_embedding/graph2vec.html)

Ringkasan

Pembenaman ialah fungsi yang memetakan graf diskret kepada perwakilan vektor . Pelbagai bentuk benam boleh dihasilkan daripada data graf, benam nod, benam tepi dan benam graf. Ketiga-tiga jenis benam menyediakan perwakilan vektor yang memetakan struktur dan ciri awal graf kepada nilai berangka dalam dimensi X.

Atas ialah kandungan terperinci Gambaran keseluruhan pembenaman graf: kaedah benam nod, tepi dan graf serta pelaksanaan Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!