Lap_norm in deepwalk

Chengbin · November 17, 2020, 5:41pm

Hi everyone,

What is the purpose of lap_norm in deepwalk model? Specifically, why do we need the second term of
score * emb_pos_v + self.lap_norm * (emb_pos_v - emb_pos_u)
while updaing grad_u_pos?

Please see

github.com

dmlc/dgl/blob/master/examples/pytorch/ogb/deepwalk/model.py#L361



pos_score = torch.sum(torch.mul(emb_pos_u, emb_pos_v), dim=1)
pos_score = torch.clamp(pos_score, max=6, min=-6)
# [batch_size * num_pos, 1]
score = (1 - self.fast_sigmoid(pos_score)).unsqueeze(1)
if self.record_loss:
    self.loss.append(torch.mean(self.fast_logsigmoid(pos_score)).item())

# [batch_size * num_pos, dim]
if self.lap_norm > 0:
    grad_u_pos = score * emb_pos_v + self.lap_norm * (emb_pos_v - emb_pos_u)
    grad_v_pos = score * emb_pos_u + self.lap_norm * (emb_pos_u - emb_pos_v)
else:
    grad_u_pos = score * emb_pos_v
    grad_v_pos = score * emb_pos_u

if self.use_context_weight:
    if bs < self.batch_size:
        context_weight = init_weight(
            self.walk_length,
            self.window_size,

Thanks.

classicsong · November 18, 2020, 4:38am

Lap norm refer to laplacian normalization.

github.com

dmlc/dgl/blob/061c2a364e26b39350fc178319bf94ae92ce7206/examples/pytorch/ogb/deepwalk/model.py#L164


emb_dimension int : embedding dimension
walk_length int : number of nodes in a sequence
window_size int : context window size
batch_size int : number of node sequences in each batch
only_cpu bool : training with CPU
only_gpu bool : training with GPU
mix bool : mixed training with CPU and GPU
negative int : negative samples for each positve node pair
neg_weight float : negative weight
lr float : initial learning rate
lap_norm float : weight of laplacian normalization
fast_neg bool : do negative sampling inside a batch
record_loss bool : print the loss during training
norm bool : do normalizatin on the embedding after training
use_context_weight : give different weights to the nodes in a context window
async_update : asynchronous training
"""
super(SkipGramModel, self).__init__()
self.emb_size = emb_size
self.emb_dimension = emb_dimension
self.walk_length = walk_length

This is one optimization we used for DeepWalk by introducing laplacian normalization.

Chengbin · November 18, 2020, 5:35am

Thank you very much for you reply.
Could you please further explain this?
What does the Laplacian normalization here really mean? Why do we need to introduce Laplacian normalization here, and what is the benefit of doing this?

Chengbin · November 23, 2020, 8:39am

Can anyone help explain this?

Shaw · November 23, 2020, 11:49am

Intuitively, by adopting Laplacian Normalization as a regularizer, the embeddings of nodes in positive samples will be pushed together by minimizing the distance of ||x_i - x_j||. There are also some other benefits by doing this like:

accelerating convergence
guaranteeing the performance of proximity preservation
improving the skip-gram’s performance in preserving non-linear structures
…

Though the theoretical proofs have not been published yet (still under review), similar usage of Laplacian Normalization can be found in this paper:

H. Xiong and J. Yan, “BTWalk: Branching Tree Random Walk for Multi-order Structured Network Embedding” in IEEE Transactions on Knowledge & Data Engineering, vol. , no. 01, pp. 1-1, 5555. doi: 10.1109/TKDE.2020.3029061
paper link: https://www.computer.org/csdl/journal/tk/5555/01/09214904/1nHNDTGti6I
code: https://github.com/ShawXh/BTWalk

Chengbin · November 24, 2020, 3:11am

Thank you very much for your reply and the reference.

system · December 24, 2020, 3:11am

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.