<jupyter_start><jupyter_text>Node2Vec with weighted random walks  IntroductionThis notebook illustrates how `Node2Vec` [[1]](refs) can be applied to learn low dimensional node embeddings of an edge weighted graph through *__weighted biased random walks__* over the graph. Specifically, the notebook demonstrates:1. Learning node embeddings using  [Word2Vec](https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf) algorithm applied to a set of weighted biased random walks performed over a graph.2. Visualizing the node embeddings in 2-D using the [t-SNE](http://scikit-learn.org/stable/modules/generated/sklearn.manifold.TSNE.html) algorithm.3. Demonstrating how the node embeddings calculated using Word2Vec can be used as feature vectors in a downstream task such as node classification. 4. Comparing node embeddings learnt from "unweighted Node2Vec" with "weighted Node2Vec" visually as well as in terms of accuracy of node classification task over the same underlying graph. 5. Lastly, performing a quick check of equivalency of weighted biased random walks to unweighted biased random walks when all edge weights are identically 1.The example uses components from the `stellargraph`, `Gensim`, and `scikit-learn` libraries.**Note:** For clarity of exposition, this notebook forgoes the use of standard machine learning practices such as `Node2Vec` parameter tuning, node feature standarization, data splitting that handles class imbalance, classifier selection, and classifier tuning to maximize predictive accuracy. We leave such improvements to the reader. References[1] Node2Vec: Scalable Feature Learning for Networks. <NAME>, <NAME>. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016. ([link](https://snap.stanford.edu/node2vec/))[2] Distributed representations of words and phrases and their compositionality. <NAME>, <NAME>, <NAME>, <NAME>, and <NAME>.  In Advances in Neural Information Processing Systems (NIPS), pp. 3111-3119, 2013. ([link](https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf))[3] Gensim: Topic modelling for humans. ([link](https://radimrehurek.com/gensim/))[4] scikit-learn: Machine Learning in Python ([link](http://scikit-learn.org/stable/))<jupyter_code>from sklearn.manifold import TSNE
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegressionCV
from sklearn.metrics import accuracy_score
from sklearn.metrics.pairwise import pairwise_distances
from sklearn import preprocessing

import os
import networkx as nx
import numpy as np
import pandas as pd

from stellargraph.data import BiasedRandomWalk
from stellargraph import StellarGraph

from gensim.models import Word2Vec

import warnings 
import collections
import matplotlib.pyplot as plt

%matplotlib inline<jupyter_output>Using TensorFlow backend.<jupyter_text>DatasetThe dataset is the citation network Cora. It can be downloaded by clicking [here](https://linqs-data.soe.ucsc.edu/public/lbc/cora.tgz). The following is the description of the dataset from the publisher:> The Cora dataset consists of 2708 scientific publications classified into one of seven classes. The citation network consists of 5429 links. Each publication in the dataset is described by a 0/1-valued word vector indicating the absence/presence of the corresponding word from the dictionary. The dictionary consists of 1433 unique words. The README file in the dataset provides more details. For this demo, we ignore the word vectors associated with each paper. We are only interested in the network structure and the **subject** attribute of each paper.Download and unzip the cora.tgz file to a location on your computer. We assume that the dataset is stored in the directory`~/data/cora/`where the files `cora.cites` and `cora.content` can be located.We are going to load the data into a networkx object.<jupyter_code>data_dir = "~/data/cora"
# load edges in order 'cited-paper' <- 'citing-paper'
cora_location = os.path.expanduser(os.path.join(data_dir, "cora.cites"))
g_nx_wt = nx.read_weighted_edgelist(path=cora_location, create_using=nx.DiGraph()).reverse()

# convert to undirected graph
g_nx_wt = g_nx_wt.to_undirected()

# load the node attribute data
cora_data_location = os.path.expanduser(os.path.join(data_dir, "cora.content"))
node_attr = pd.read_csv(cora_data_location, sep='\t', header=None)
values = { str(row.tolist()[0]): row.tolist()[-1] for _, row in node_attr.iterrows()}
nx.set_node_attributes(g_nx_wt, values, 'subject')

# Select the largest connected component. For clarity we ignore isolated
# nodes and subgraphs; having these in the data does not prevent the
# algorithm from running and producing valid results.
g_nx_wt = max(nx.connected_component_subgraphs(g_nx_wt, copy=True), key=len)
print("Largest subgraph statistics: {} nodes, {} edges".format(
    g_nx_wt.number_of_nodes(), g_nx_wt.number_of_edges()))<jupyter_output>Largest subgraph statistics: 2485 nodes, 5069 edges<jupyter_text>Add weights to the edges For weighted biased random walks the underlying graph should have weights over the edges. Since the links in the Cora dataset are unweighted, we need to synthetically add weights to the links in the graph. One possibility is to weight each edge by the similarity of its end nodes. Here we assign the Jaccard similarity of the features of the pair of nodes as the weight of edge.<jupyter_code>df = node_attr.copy()
df.set_index(0, inplace = True)
papers = df.index
## calculating the paiwise jaccard similarity between each pair of nodes.
with warnings.catch_warnings():
    warnings.simplefilter("ignore")
    wts = pd.DataFrame(
        1- pairwise_distances(df.iloc[:,:-1].values, metric = 'jaccard'), 
        index = papers, columns = papers)
    wts.index = wts.index.map(str)
    wts.columns = wts.columns.map(str)<jupyter_output><empty_output><jupyter_text>Append the weight attribute to the edges. Note, here we use the word 'weight' to label the weight value over the edge but it can be any other user specified label.<jupyter_code>for u,v in g_nx_wt.edges():
    val = wts[u][v]
    g_nx_wt[u][v]['weight'] = val<jupyter_output><empty_output><jupyter_text>Just a quick look at the weights of the edges.<jupyter_code>wts = list()
for u,v in g_nx_wt.edges():
    wts.append(g_nx_wt[u][v]['weight'])
wts = sorted(wts, reverse = True)
edgeCount = collections.Counter(wts)
wt, cnt = zip(*edgeCount.items())

plt.figure(figsize=(10,8))
plt.bar(wt, cnt, width=0.005, color='b')
plt.title("Edge weights histogram")
plt.ylabel("Count")
plt.xlabel("edge weights")
plt.xticks(np.linspace(0,1,10))

plt.show()<jupyter_output><empty_output><jupyter_text>The above distribution of edge weights illustrates that majority of linked nodes are insignificantly similar in terms of their attributes.  The Node2Vec algorithmThe Node2Vec algorithm is a method for learning continuous feature respresentations for nodes in networks [[1]](refs). This approach can simply be described as a mapping of nodes to a low dimensional space of features that maximizes the likelihood of preservering neighborhood sgrtucture of the nodes. This approach is not tied to a fixed definition of neighborhood of a node but can be used in conjunction with different notions of node neighborhood, such as, homophily or structural equivalence, among other concepts.  The algorithm efficiently explores diverse neighborhoods of nodes through a biased random walk procedure that is parametrized to emulate a specific concept of the neighborhood of a node. Once a pre-defined number of walks, of fixed lengths, have been sampled, the low dimension embedding vectors of nodes can be learnt using `Word2vec` algorithm [[2]](refs). We use the Word2Vec implementation in the free Python library `Gensim` [[3]](refs) to learn representations for each node in the graph.  Corpus generation using random walksThe stellargraph library provides an implementation of random walks that can be unweighted or weighted as required by Node2Vec. The random walks have a pre-defined fixed maximum length and are controlled by three parameters `p`, `q`,  and `weight`. By default, the weight over the edges is assumed to be 1. See [[1]](refs) for a detailed description of these parameters.   Weighted random walksThe first step for the weighted biased random walk is to build a random walk object by passing it a Stellargraph object.<jupyter_code>rw = BiasedRandomWalk(StellarGraph(g_nx_wt))<jupyter_output><empty_output><jupyter_text>The next step is to sample a set of random walks of pre-defined length starting from each node of the graph. Parameters `p`, `q`, and `weighted` influence the type of random walks in the procedure. In this demo, we are going to start 10 random walks from each node in the graph with a length up to 100. We set parameter `p` to 0.5 and `q` to 2.0 and the weight parameter set to True. The `run` method in the random walk will check if the weights over the edges are available and resolve other issues, such as, whether the weights are numeric and that their is no ambiguity of edge traversal (i.e. each pair of node is connected by a unique mnumerically weighted edge).<jupyter_code>weighted_walks = rw.run(
    nodes=g_nx_wt.nodes(), # root nodes
    length=100,    # maximum length of a random walk
    n=10,          # number of random walks per root node 
    p=0.5,         # Defines (unormalised) probability, 1/p, of returning to source node
    q=2.0,         # Defines (unormalised) probability, 1/q, for moving away from source node
    weighted=True, #for weighted random walks
    seed=42        # random seed fixed for reproducibility
)
print("Number of random walks: {}".format(len(weighted_walks)))<jupyter_output>Number of random walks: 24850<jupyter_text>Representation Learning using Word2VecOnce we have a sample set of walks, we learn the low-dimensional embedding of nodes using Word2Vec approach.We set the dimensionality of the learned embedding vectors to 128 as in [[1]](refs).<jupyter_code>weighted_model = Word2Vec(weighted_walks, size=128, window=5, min_count=0, sg=1, workers=1, iter=1)
# The embedding vectors can be retrieved from model.wv using the node ID as key.
# E.g., for node id '19231', the embedding vector is retrieved as
emb = weighted_model.wv['19231']
emb.shape<jupyter_output><empty_output><jupyter_text>Visualise Node Embeddings generated by weighted  random walksWe retrieve the `Word2Vec` node embeddings that are 128-dimensional vectors and then we project them down to 2 dimensions using the [t-SNE](http://scikit-learn.org/stable/modules/generated/sklearn.manifold.TSNE.html) algorithm for visualization.<jupyter_code># Retrieve node embeddings and corresponding subjects
node_ids = weighted_model.wv.index2word  # list of node IDs
weighted_node_embeddings = weighted_model.wv.vectors  # numpy.ndarray of size number of nodes times embeddings dimensionality
node_targets = [ g_nx_wt.node[node_id]['subject'] for node_id in node_ids]
# Apply t-SNE transformation on node embeddings
tsne = TSNE(n_components=2 , random_state=42)
weighted_node_embeddings_2d = tsne.fit_transform(weighted_node_embeddings)<jupyter_output><empty_output><jupyter_text>Plot the embeddings generated from weighted random walks<jupyter_code># draw the points
alpha = 0.7
label_map = {l: i for i, l in enumerate(np.unique(node_targets))}
node_colours = [ label_map[target] for target in node_targets ]

plt.figure(figsize=(10,8))
plt.scatter(weighted_node_embeddings_2d[:,0], 
            weighted_node_embeddings_2d[:,1], 
            c=node_colours, cmap = "jet", alpha = 0.7)
plt.show()<jupyter_output><empty_output><jupyter_text>Downstream taskThe node embeddings calculated using `Word2Vec` can be used as feature vectors in a downstream task such as node classification. Here we give an example of training a logistic regression classifier using the node embeddings, learnt above, as features.<jupyter_code># X will hold the 128-dimensional input features
X = weighted_node_embeddings  
# y holds the corresponding target values
y = np.array(node_targets)<jupyter_output><empty_output><jupyter_text>Train and Test splitWe use 75% of the data for training and the remaining 25% for testing as a hold out test set.<jupyter_code>X_train, X_test, y_train, y_test = train_test_split(
    X, y, train_size=0.75, test_size=None, random_state = 42
)
print("Array shapes:\n X_train = {}\n y_train = {}\n X_test = {}\n y_test = {}" \
      .format(X_train.shape, y_train.shape, X_test.shape, y_test.shape))<jupyter_output>Array shapes:
 X_train = (1863, 128)
 y_train = (1863,)
 X_test = (622, 128)
 y_test = (622,)<jupyter_text>Classifier TrainingWe train a Logistic Regression classifier on the training data.<jupyter_code>clf = LogisticRegressionCV(
    Cs=10, 
    cv=10,
    tol=0.001,
    max_iter=1000,
    scoring="accuracy",
    verbose=False,
    multi_class='ovr',
    random_state=5434
)
clf.fit(X_train, y_train)<jupyter_output><empty_output><jupyter_text>Predict the hold out test set.<jupyter_code>y_pred = clf.predict(X_test)<jupyter_output><empty_output><jupyter_text>Calculate the accuracy of the classifier on the test set.<jupyter_code>accuracy_score(y_test, y_pred)<jupyter_output><empty_output><jupyter_text>Comparison to weighted and unnweighted biased random walks Lets compare weighted random walks with unweighted random walks. This simply requires toggling the weight parameter to False in the `run` method of the BiasedRandomWalk. Note, the weight parameter is by default set to False, hence, not specifying the weight parameter would result in the same action.  Step 1: performing unweighted walks<jupyter_code>walks = rw.run(
    nodes=g_nx_wt.nodes(), # root nodes
    length=100,     # maximum length of a random walk
    n=10,           # number of random walks per root node 
    p=0.5,          # Defines (unormalised) probability, 1/p, of returning to source node
    q=2.0,          # Defines (unormalised) probability, 1/q, for moving away from source node
    weighted=False, # since we are interested in unweighted walks
    seed=42         # for reproducibility
)
print("Number of random walks: {}".format(len(walks)))<jupyter_output>Number of random walks: 24850<jupyter_text>Step 2: learning node embeddings<jupyter_code>model = Word2Vec(walks, size=128, window=5, min_count=0, sg=1, workers=1, iter=1)<jupyter_output><empty_output><jupyter_text>Plot the embeddings generated from unweighted random walks.<jupyter_code># Retrieve node embeddings and corresponding subjects
node_ids = model.wv.index2word  # list of node IDs
node_embeddings = model.wv.vectors  # numpy.ndarray of size number of nodes times embeddings dimensionality
node_targets = [ g_nx_wt.node[node_id]['subject'] for node_id in node_ids]

# Apply t-SNE transformation on node embeddings
tsne = TSNE(n_components=2, random_state=42)
node_embeddings_2d = tsne.fit_transform(node_embeddings)

# draw the points
alpha = 0.7
label_map = { l: i for i, l in enumerate(np.unique(node_targets))}
node_colours = [ label_map[target] for target in node_targets]

plt.figure(figsize=(10,8))
plt.scatter(node_embeddings_2d[:,0], 
            node_embeddings_2d[:,1], 
            c=node_colours, cmap = "jet", alpha = 0.7)
plt.show()<jupyter_output><empty_output><jupyter_text>Visual comparison of node embedding plots for weighted and unweighted random walks illustrates the differences betweem the two.  Using unweighted random walks to train classifiers to predict the subject of a paper in Cora.<jupyter_code># X will hold the 128-dimensional input features
X = node_embeddings  
# y holds the corresponding target values
y = np.array(node_targets)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, train_size=0.75, test_size=None, random_state=42
)
print("Array shapes:\n X_train = {}\n y_train = {}\n X_test = {}\n y_test = {}" \
      .format(X_train.shape, y_train.shape, X_test.shape, y_test.shape))
clf = LogisticRegressionCV(
    Cs=10, 
    cv=10, 
    tol=0.01,
    max_iter=1000,
    scoring="accuracy",
    verbose=False,
    multi_class='ovr',
    random_state=5434
)
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
accuracy_score(y_test, y_pred)<jupyter_output><empty_output><jupyter_text>Generally, the node embeddings extracted from unweighted random walks are more representative of the underlying community structure of the `Cora` dataset than the embeddings learnt from weighted random walks over the artificially weighted Cora network.   Testing whether weights = 1 gives identical result to unweighted randomwalks Lastly, we perform a quick check of whether weighted biased random walks are identical to unweighted biased random walks when weights over the edges are identically 1. First, set weights of all edges in the graph to 1.<jupyter_code>for u,v in g_nx_wt.edges():
    g_nx_wt[u][v]['weight'] = 1<jupyter_output><empty_output><jupyter_text>Quick check to confirm if all edge weights are actually 1.<jupyter_code>wts = list()
for u,v in g_nx_wt.edges():
    wts.append(g_nx_wt[u][v]['weight'])
wts = sorted(wts, reverse = True)
edgeCount = collections.Counter(wts)
wt, cnt = zip(*edgeCount.items())

plt.figure(figsize=(10,8))
plt.bar(wt, cnt, width=0.005, color='b')
plt.title("Edge weights histogram")
plt.ylabel("Count")
plt.xlabel("edge weights")
plt.xticks(np.linspace(0,1,10))

plt.show()<jupyter_output><empty_output><jupyter_text>Step 1: create the biased random walk object<jupyter_code>rw = BiasedRandomWalk(StellarGraph(g_nx_wt))<jupyter_output><empty_output><jupyter_text>Step 2: sample random walks from the graph.<jupyter_code>weighted_walks = rw.run(
    nodes=g_nx_wt.nodes(), # root nodes
    length=100,    # maximum length of a random walk
    n=10,          # number of random walks per root node 
    p=0.5,         # Defines (unormalised) probability, 1/p, of returning to source node
    q=2.0,         # Defines (unormalised) probability, 1/q, for moving away from source node
    weighted=True, # indicates the walks are weighted
    seed=42        # seed fixed for reproducibility
)
print("Number of random walks: {}".format(len(weighted_walks)))<jupyter_output>Number of random walks: 24850<jupyter_text>Compare unweighted walks with weighted walks when all weights are uniformly set to 1. Note, the two sets should be identical given all other parameters and random seeds are fixed.<jupyter_code>assert walks == weighted_walks<jupyter_output><empty_output><jupyter_text>Step 3: learn node embeddings from the walks sampled above.<jupyter_code>weighted_model = Word2Vec(weighted_walks, size=128, window=5, min_count=0, sg=1, workers=1, iter=1)<jupyter_output><empty_output><jupyter_text>Plot the embeddings in 2-D using t-SNE tranformation for visual comparison to the embeddings learnt from unweighted walks.<jupyter_code># Retrieve node embeddings and corresponding subjects
node_ids = weighted_model.wv.index2word  # list of node IDs
weighted_node_embeddings = weighted_model.wv.vectors  # numpy.ndarray of size number of nodes times embeddings dimensionality
node_targets = [ g_nx_wt.node[node_id]['subject'] for node_id in node_ids]

# Apply t-SNE transformation on node embeddings
tsne = TSNE(n_components=2, random_state=42)
weighted_node_embeddings_2d = tsne.fit_transform(weighted_node_embeddings)

# draw the points
alpha = 0.7
label_map = { l: i for i, l in enumerate(np.unique(node_targets))}
node_colours = [ label_map[target] for target in node_targets]

plt.figure(figsize=(10,8))
plt.scatter(weighted_node_embeddings_2d[:,0], 
            weighted_node_embeddings_2d[:,1], 
            c=node_colours, cmap = "jet", alpha = 0.7)
plt.show()<jupyter_output><empty_output><jupyter_text>Comparing the accuracy of node classification for weighted (weight ==1) and unweighted random walks.Compare classification of nodes through logistic regression on embeddings learnt from weighted (weight == 1) walks to that of unweighted walks demonstrated above.<jupyter_code># X will hold the 128-dimensional input features
X = weighted_node_embeddings 
# y holds the corresponding target values
y = np.array(node_targets)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, train_size=0.75, test_size=None, random_state=42
)
print("Array shapes:\n X_train = {}\n y_train = {}\n X_test = {}\n y_test = {}" \
      .format(X_train.shape, y_train.shape, X_test.shape, y_test.shape))
clf = LogisticRegressionCV(
    Cs=10, 
    cv=10, 
    tol=0.001,
    max_iter=1000,
    scoring="accuracy",
    verbose=False,
    multi_class='ovr',
    random_state=5434
)
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
accuracy_score(y_test, y_pred)
np.array_equal(weighted_node_embeddings, node_embeddings)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08617628712633751, 'fraction_numerical': 0.01794539609423732, 'mean_word_length': 5.304295220810648, 'pattern_counts': {'":': 0, '<': 111, '<?xml version=': 0, '>': 111, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '27', 'dir': 'jupyter-structured-clean-dedup', 'id': '202134', 'license': 'Apache-2.0', 'n_tokens_mistral': 6669, 'n_tokens_neox': 6164, 'n_words': 2221, 'path': 'demos/node-classification/node2vec/stellargraph-node2vec-weighted-random-walks.ipynb', 'repo_name': 'cdawei/stellargraph', 'size': '20868'}