Change Password

Please enter the password.
Please enter the password. Between 8-64 characters. Not identical to your email address. Contain at least 3 of: uppercase, lowercase, numbers, and special characters.
Please enter the password.
Submit

Change Nickname

Current Nickname:
Submit

Apply New License

License Detail

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

The MAC address of the server you want to deploy.

Please complete this required field.

Please complete this required field.

Cancel
Apply
ID
Product
Status
Cores
Applied Validity Period(days)
Effective Date
Excpired Date
Mac Address
Apply Comment
Review Comment
Close
Profile
  • Full Name:
  • Phone:
  • Company:
  • Company Email:
  • Country:
  • Language:
Change Password
Apply

You have no license application record.

Apply
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

Product Created On ID Amount (USD) Invoice
Product Created On ID Amount (USD) Invoice

No Invoice

Search
    English

      Struc2Vec

      ✓ File Writeback ✓ Property Writeback ✓ Direct Return ✓ Stream Return ✕ Stats

      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.

      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 Rk(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 fk(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 fk(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(Rk(u)) and s(Rk(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 fk-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 |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 fk(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 uk), 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 vk is proportional to wk(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 uk+1 or uk-1 are proportional to wk(uk,uk+1) and wk(uk,uk-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:
      Name

      Type
      Spec
      Default
      Optional
      Description
      ids / uuids []_id / []_uuid / / Yes ID/UUID of nodes to start random walks; start from all nodes if not set
      walk_length int ≧1 1 Yes Depth of each walk, i.e., the number of nodes to visit
      walk_num int ≧1 1 Yes Number of walks to perform for each specified node
      k int [1, 10] / No Number of layers of the constructed multilayer weighted graph, which should not exceed the diameter of the original graph
      stay_probability float (0,1] / No The probability of walking in the current level
      window_size int ≥1 / No The maximum size of context
      dimension int ≥1 / No Dimensionality of the embeddings
      loop_num int ≥1 / No Number of training iterations
      learning_rate float (0,1) / No Learning rate used initially for training the model, which decreases after each training iteration until reaches min_learning_rate
      min_learning_rate float (0,learning_rate) / No Minimum threshold for the learning rate as it is gradually reduced during the training
      neg_num int ≥0 / No Number of negative samples to produce for each positive sample, it is suggested to set between 0 to 10
      resolution int ≥1 1 Yes The parameter used to enhance negative sampling efficiency; a higher value offers a better approximation to the original noise distribution; it is suggested to set as 10, 100, etc.
      sub_sample_alpha float / 0.001 Yes The factor affecting the probability of down-sampling frequent nodes; a higher value increases this probability; a value ≤0 means not to apply subsampling
      min_frequency int / / No Nodes that appear less times than this threshold in the training "corpus" will be excluded from the "vocabulary" and disregarded in the embedding training; a value ≤0 means to keep all nodes
      limit int ≥-1 -1 Yes Number of results to return, -1 to return all results

      Example

      File Writeback

      Spec Content
      filename _id,embedding_result
      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

      Spec Content Write to Data Type
      property embedding_result Node Property string
      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

      Alias Ordinal
      Type
      Description
      Columns
      0 []perNode Node and its embeddings _uuid, embedding_result
      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

      Alias Ordinal
      Type
      Description
      Columns
      0 []perNode Node and its embeddings _uuid, embedding_result
      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
      
      Please complete the following information to download this book
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写