LINE

Overview

LINE (Large-scale Information Network Embedding) is a network embedding model that preserves the local or global network structures. LINE is able to scale to very large, arbitrary types of networks, it was originally proposed in 2015:

• J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, Q. Zhu, LINE: Large-scale Information Network Embedding (2015)

Concepts

First-order Proximity and Second-order Proximity

First-order proximity in a network shows the local proximity between two nodes, and it is contingent upon connectivity. A link between two nodes—or a stronger (positive) link weight—indicates higher first-order proximity. If no link exists between them, their first-order proximity is considered 0.

On the other hand, second-order proximity measures the similarity between the neighborhood structures of two nodes, based on shared neighbors. If two nodes have no common neighbors, their second-order proximity is 0.

This is an illustrative example, where the edge thickness signifies its weight.

• A substantial weight on the edge between nodes 6 and 7 indicates a strong first-order proximity, meaning they should have similar representations in the embedding space.
• Although nodes 5 and 6 are not directly connected, their considerable common neighbors create a significant second-order proximity. As a result, they are also expected to be represented close to each other in the embedding space.

LINE Model

The LINE model is designed to embed nodes in graph G = (V,E) into low-dimensional vectors, while preserving either the first-order or second-order proximity between nodes.

LINE with First-order Proximity

To capture the first-order proximity, LINE defines the joint probability for each edge (i,j)∈E connecting nodes v_i and v_j as follows:

where u_i is the low-dimensional vector representation of node v_i. The joint probability p₁ ranges from 0 to 1: the closer the vectors (i.e., the higher their dot product), the higher the joint probability.

Empirically, the joint probability between node v_i and v_j can be defined as

where w_ij denotes the edge weight between nodes v_i and v_j, W is the sum of all edge weights in the graph.

The KL-divergence is adopted to measure the difference between two distributions:

This serves as the objective function that needs to be minimized during training when preserving the first-order proximity.

LINE with Second-order Proximity

To model the second-order proximity, LINE defines two roles for each node - one as the node itself, another as "context" for other nodes (this concept originates from the Skip-gram model). Accordingly, two vector representations are introduced for each node.

For each edge (i,j)∈E, LINE defines the probability of "context" v_j be observed by node v_i as

where u'_j is the representation of node v_j when it is regarded as the "context". Importantly, the denominator involves the whole "context" in the graph.

The corresponding empirical probability can be defined as

where w_ij is weight of edge (i,j), d_i is the weighted degree of node v_i.

Similarly, the KL-divergence is adopted to measure the difference between two distributions:

This serves as the objective function that needs to be minimized during training when preserving the second-order proximity.

Model Optimization

Negative Sampling

To improve computation efficiency, LINE uses negative sampling, drawing multiple negative edges from a noise distribution for each edge (i,j). Specifically, the two objective functions are adjusted as:

where σ is the sigmoid function, K is the number of negative edges drawn from the noise distribution P_n(v) ∝ d_v^3/4, d_v is the weighted degree of node v.

Edge-Sampling

Since edge weights are included in both objective functions, they are also applied to the gradients during optimization. This can cause gradient explosion and degrade model performance. To address this, LINE samples edges with probabilities proportional to their weights and treats the sampled edges as binary during model updates.

Considerations

• The LINE algorithm treats all edges as undirected, ignoring their original direction.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER EDGE default ADD PROPERTY {
  score float
};
INSERT (A:default {_id: "A"}),
       (B:default {_id: "B"}),
       (C:default {_id: "C"}),
       (D:default {_id: "D"}),
       (E:default {_id: "E"}),
       (F:default {_id: "F"}),
       (G:default {_id: "G"}),
       (H:default {_id: "H"}),
       (I:default {_id: "I"}),
       (J:default {_id: "J"}),
       (A)-[:default {score: 1}]->(B),
       (A)-[:default {score: 3}]->(C),
       (C)-[:default {score: 1.5}]->(D),
       (D)-[:default {score: 5}]->(F),
       (E)-[:default {score: 2.2}]->(C),
       (E)-[:default {score: 0.6}]->(F),
       (F)-[:default {score: 1.5}]->(G),
       (G)-[:default {score: 2}]->(J),
       (H)-[:default {score: 2.5}]->(G),
       (H)-[:default {score: 1}]->(I);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: line

File Writeback

UQL
algo(line).params({
  projection: "my_hdc_graph",
  return_id_uuid: "id",
  edge_schema_property: "score",
  dimension: 3,
  train_total_num: 10,
  train_order: 1,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 5,
  resolution: 100
}).write({
  file:{
    filename: 'embeddings'
  }
})

File: embeddings
_id,embedding_result
J,0.134156,0.147224,-0.127542,
D,-0.110004,0.0445883,0.101143,
F,0.0306388,0.00733918,-0.11945,
H,0.0739559,-0.145214,0.0416526,
B,-0.02514,-0.0317756,-0.110371,
A,-0.0629673,0.0857267,0.100926,
E,0.0989685,0.0532481,0.0514933,
C,-0.127659,-0.136062,0.166552,
I,0.126709,0.103002,-0.0201314,
G,0.134589,-0.0157018,0.0237946,

DB Writeback

Writes the embedding_result values from the results to the specified node property. The property type is float[].

UQL
algo(line).params({
  projection: "my_hdc_graph",
  return_id_uuid: "id",
  edge_schema_property: "score",
  dimension: 3,
  train_total_num: 10,
  train_order: 1,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 5,
  resolution: 100
}).write({
  db: {
      property: "vector"
    }
})

Full Return

UQL
exec{
  algo(line).params({
    return_id_uuid: "id",
    edge_schema_property: '@default.score',
    dimension: 4,
    train_total_num: 10,
    train_order: 1,
    learning_rate: 0.01,
    min_learning_rate: 0.0001
  }) as embeddings
  return embeddings
} on my_hdc_graph

Result:

Stream Return

UQL
exec{
  algo(line).params({
    return_id_uuid: "id",
    edge_schema_property: '@default.score',
    dimension: 3,
    train_total_num: 10,
    train_order: 1,
    learning_rate: 0.01,
    min_learning_rate: 0.0001
  }).stream() as embeddings
  return embeddings
} on my_hdc_graph

Result: