Overview of graph embedding: node, edge and graph embedding methods and Python implementation

Graph-based machine learning has made great progress in recent years. Graph-based methods have applications in many common problems in data science, such as link prediction, community discovery, node classification, etc. There are many ways to solve a problem depending on how you organize it and the data you have. This article will provide a high-level overview of graph-based embedding algorithms. Finally, we will also introduce how to use Python libraries (such as node2vec) to generate various embeddings on graphs.

Graph-based machine learning

Artificial intelligence has various branches, from recommendation systems, time series, natural Language processing, computer vision, graph machine learning, etc. There are several ways to solve common problems with graph-based machine learning. Including community discovery, link prediction, node classification, etc.

A major problem with machine learning on graphs is finding a way to represent (or encode) the structure of a graph so that machine learning models can easily exploit it [1]. Typically solving this problem in machine learning requires learning some kind of representation through structured tabular data associated with the model, which was previously done through statistical measurements or kernel functions. In recent years the trend has been towards encoding graphs to generate embedding vectors for training machine learning models.

The goal of machine learning models is to train machines to learn and recognize patterns at scale in data sets. This is amplified when working with graphs, as graphs provide different and complex structures that other forms of data (such as text, audio, or images) do not have. Graph-based machine learning can detect and explain recurring underlying patterns [2].

We may be interested in determining demographic information related to users on social networks. Demographic data includes age, gender, race, etc. Social media networks for companies like Facebook or Twitter range from millions to billions of users and trillions of sides. There will definitely be several patterns related to the demographics of the users in this network that are not easily detectable by humans or algorithms, but the model should be able to learn them. Similarly, we might want to recommend a pair of users to become friends, but they are not yet friends. This provides fodder for link prediction, another application of graph-based machine learning.

What is graph embedding?

Feature engineering refers to the common method of processing input data to form a set of features that provide a compact and meaningful representation of the original data set. The results of the feature engineering phase will serve as input to the machine learning model. This is a necessary process when working with tabular structured data sets, but is a difficult approach to perform when working with graph data, as a way needs to be found to generate a suitable representation associated with all graph data.

There are many ways to generate features representing structural information from graphs. The most common and straightforward method is to extract statistics from a graph. This can include recognition distribution, page rank, centrality metrics, jaccard score, etc. The required attributes are then incorporated into the model via a kernel function, but the problem with kernel functions is that the associated time complexity of generating the results is high.

Recent research trends have shifted towards finding meaningful graph representations and generating embedded representations for graphs. These embeddings learn graph representations that preserve the original structure of the network. We can think of it as a mapping function designed to transform a discrete graph into a continuous domain. Once a function is learned, it can be applied to a graph and the resulting mapping can be used as a feature set for machine learning algorithms.

Types of graph embedding

The analysis of graphs can be decomposed into 3 levels of granularity. Node level, edge level, and graph level (whole graph). Each level consists of a different process that generates embedding vectors, and the process chosen should depend on the problem and data being processed. Each of the granularity level embeddings presented below has accompanying figures to visually distinguish them from each other.

Node Embedding

At the node level, an embedding vector associated with each node in the graph is generated. This embedding vector can accommodate the representation and structure of the graph. Essentially nodes that are close to each other should also have vectors that are close to each other. This is one of the basic principles of popular node embedding models such as Node2Vec.

Edge Embedding

In the edge layer, an embedding vector is generated related to each edge in the graph. The link prediction problem is a common application using edge embedding. Link prediction refers to predicting the likelihood of whether an edge connects a pair of nodes. These embeddings can learn edge properties provided by the graph. For example, in a social network graph, you can have a multi-edge graph where nodes can be connected by edges based on age range, gender, etc. These edge properties can be learned by representing the correlation vector of the edge.

Graph embeddings

Graph-level embeddings are uncommon, they consist of generating an embedding vector representing each graph. For example, in a large graph with multiple subgraphs, each corresponding subgraph has an embedding vector that represents the graph structure. Classification problems are a common application where graph embeddings can be useful. These types of problems will involve classifying graphs into specific categories.

Python implementation

Using python code to implement the following libraries we need

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

If you do not have it installed node2vec package, please refer to its documentation. Install the karateclub package, which is also similar to

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

The above picture is the visual node embedding generated by barbell graph, there are There are many methods for computing node embeddings, such as node2vec, deep walk, random walks, etc. node2vec is used here.

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

View the visualization of edge embedding through barbell graph, the source code of Hammard Embedder can be found here (https ://github.com/eliorc/node2vec/blob/master/node2vec/edges.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()

This is a graph embedding visualization of a randomly generated graph. The source code of the graph2vec algorithm can be found at Found here. (https://karateclub.readthedocs.io/en/latest/_modules/karateclub/graph_embedding/graph2vec.html)

Summary

Embedding is a function that maps discrete graphs to vector representations . Various forms of embeddings can be generated from graph data, node embeddings, edge embeddings and graph embeddings. All three types of embeddings provide a vector representation that maps the initial structure and features of the graph to numerical values ​​in the X dimension.

The above is the detailed content of Overview of graph embedding: node, edge and graph embedding methods and Python implementation. For more information, please follow other related articles on the PHP Chinese website!