Struc2Vec

Overview

Struc2Vec stands for "structure to vector". This algorithm revolutionizes graph embeddings by generating node vectors while retaining the inherent graph structure, focusing on preserving topological similarities.

• L. Ribeiro, P. Saverese, D. Figueiredo, struc2vec: Learning Node Representations from Structural Identity (2017)

While Node2Vec captures a certain degree of structural similarity among nodes, it is limited by the depth of random walks used during the generation process. On the other hand, Struc2Vec overcomes this limitation in its framework. It ensures that nodes with similar structural characteristics are represented close to each other in the embedding space.

The choice between Node2Vec and Struc2Vec depends on the nature of downstream tasks:

• Node2Vec suits tasks prioritizing node homophily, capturing similarity in attributes and connections.
• Struc2Vec excels when tasks demand a focus on local topology similarity, preserving the structural relationships among nodes.

Concepts

Structural Similarity

In various networks, nodes often possess distinct structural identities shaped by their specific functions or roles. Nodes performing similar functions are naturally belong to the same class, signifying their structural similarity. For instance, in a company's social network, all interns might exhibit similar roles.

Structural similarity among nodes implies that their neighborhood topologies are homogenous or symmetrical. This indicates that nodes with similar functions have analogous connections and relationships with their neighboring nodes.

As illustrated here, nodes u and v are structurally similar (degrees 5 and 4, connected to 3 and 2 triangles, connected to the rest of the network by 2 nodes). Although they lack a direct link or shared neighbor, and they can be very far apart in the network.

When the distance between nodes exceeds the depth of random walks, it becomes challenging to generate similar representations for them using methods like Node2Vec. This limitation is effectively addressed by the Struc2Vec algorithm.

Struc2Vec Framework

1. Measure structural similarity

Intuitively, two nodes that have the same degrees are considered structurally similar, but if their neighbors also have the same degree, then they are even more structurally similar.

Consider an undirected, unweighted graph G = (V, E), its diameter is denoted as k*. Let R_k(u) denote the set of nodes located at an exact distance (hop count) of k ∈ [0, k*] from node u within G. Let s(S) denote the ordered degree sequence of a node set S ⊂ V. Here is an example:

Let f_k(u,v) denote the structural distance between u and v when considering their k-hop neighborhoods (all nodes at distance less than or equal to k):

where function g() ≥ 0 measures the distance between two degree sequences. Note that f_k(u,v) is non-decreasing in k and is defined only when both u and v have neighbors at distance k.

To assess distance between sequences s(R_k(u)) and s(R_k(v)), which can be of different sizes, Dynamic Time Wrapping (DTW), or any other appliable function, can be adopted. Note that if the k-hop neighborhoods of node u and v are isomorphic, then f_k-1(u,v) = 0.

2. Construct a multilayer weighted graph

Struc2Vec constructs a multilayer weighted graph M that encodes the structural similarity between nodes, where layer k is defined using the k-hop neighborhoods of the nodes.

Each layer k is formed by a weighted undirected complete graph with node set V, and thus $\frac{\mathrm{|V|*(|V|-1)}}{2}$ edges. The edge weight between nodes u and v is inversely proportional to their structural distance, as given by:

Note that edges are defined only if f_k(u,v) is defined.

Layers are connected by directed edges. Every node is connected to its corresponding node in the layer above and below (layer permitting), and the edge weight between layers are as follows:

where Γ_k(u) is the number of edges incident to u that have weight larger than the average edge weight of the complete graph in layer k. Γ_k(u) actually measures the similarity of node u to other nodes in layer k. Note that if node u has many similar nodes in layer k, then it should change to higher layers to obtain a more refined context.

3. Generate context for nodes

Struc2Vec uses random walks to generate sequence of nodes to determine the context of a gievn node.

Consider a biased random walk that moves in graph M. Each node starts the walk in its corresponding node in layer 0, and when it reaches node u in layer k (denoted as u_k), the random walk first decides if it will (1) stay in the current layer, or (2) change layer:

(1) With probability q the random walk stays in the current layer: the probability of moving to v_k is proportional to w_k(u,v). Note that the random walk will prefer to step onto nodes that are structurally more similar to the current node.

(2) With probability 1 − q, the random walk changes layer: the probabilities of moving to u_k+1 or u_k-1 are proportional to w_k(u_k,u_k+1) and w_k(u_k,u_k-1). It's important to note that in this case, the node u is recorded only once in the random walk sequence.

The random walks have a fixed and relatively short depth (number of steps), and the process is repeated a certain number of times.

4. Train the model

The node sequences obtained from the random walks serve as input to the Skip-gram model. SGD is used to optimize the model's parameters based on the prediction error, and the model is optimized by techniques such as negative sampling and subsampling.

Considerations

• When considering the degree of a node, any self-loop is counted twice.
• The Struc2Vec algorithm ignores the direction of edges but calculates them as undirected edges.

Syntax

• Command：algo(struc2vec)
• Parameter:

Example

File Writeback

UQL
algo(struc2vec).params({
  walk_length: 10,
  walk_num: 20,
  k: 10,
  stay_probability: 0.4,
  window_size: 5,
  dimension: 20,
  loop_number: 10,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 9,
  resolution: 100,
  sub_sample_alpha: 0.001,
  min_frequency: 3
}).write({
  file:{
    filename: 'embeddings'
}})

Property Writeback

UQL
algo(struc2vec).params({
  walk_length: 10,
  walk_num: 20,
  k: 10,
  stay_probability: 0.4,
  window_size: 5,
  dimension: 20,
  loop_number: 10,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 9,
  resolution: 100,
  sub_sample_alpha: 0.001,
  min_frequency: 3
}).write({
  db:{
    property: 'vector'
}})

Direct Return

UQL
algo(struc2vec).params({
  walk_length: 10,
  walk_num: 20,
  k: 10,
  stay_probability: 0.4,
  window_size: 5,
  dimension: 20,
  loop_number: 10,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 9,
  resolution: 100,
  sub_sample_alpha: 0.001,
  min_frequency: 3
}) as embeddings
return embeddings

Stream Return

UQL
algo(struc2vec).params({
  walk_length: 10,
  walk_num: 20,
  k: 10,
  stay_probability: 0.4,
  window_size: 5,
  dimension: 20,
  loop_number: 10,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 9,
  resolution: 100,
  sub_sample_alpha: 0.001,
  min_frequency: 3
}).stream() as embeddings
return embeddings