Diffusion Based Network Embedding

Yong Shi, Minglong Lei, Peng Zhang, Lingfeng NiuarXiv 2018 · arXiv · OpenReview

Abstract

In network embedding, random walks play a fundamental role in preserving network structures. However, random walk based embedding methods have two limitations. First, random walk methods are fragile when the sampling frequency or the number of node sequences changes. Second, in disequilibrium networks such as highly biases networks, random walk methods often perform poorly due to the lack of global network information. In order to solve the limitations, we propose in this paper a network diffusion based embedding method. To solve the first limitation, our method employs a diffusion driven process to capture both depth information and breadth information. The time dimension is also attached to node sequences that can strengthen information preserving. To solve the second limitation, our method uses the network inference technique based on cascades to capture the global network information. To verify the performance, we conduct experiments on node classification tasks using the learned representations. Results show that compared with random walk based methods, diffusion based models are more robust when samplings under each node is rare. We also conduct experiments on a highly imbalanced network. Results shows that the proposed model are more robust under the biased network structure.

Introduction

Network embedding aims to map graph nodes into low-dimensional vectors while preserving their structural relationships. Most popular methods, like DeepWalk or node2vec, rely on random walks—essentially a single "walker" moving from node to node. However, these approaches face two major challenges: fragility and local bias. Random walks are highly sensitive to sampling frequency; insufficient walks lead to a failure in capturing the true network structure. Furthermore, in "disequilibrium" networks where degree distributions are highly skewed, random walks often get trapped in local neighborhoods or gravitate toward high-degree hubs, failing to capture global topology.

Methodology: From Random Walks to Diffusion

To address these limitations, we propose a novel framework consisting of a detecting step and a mapping step.

The Detecting Step: Diffusion and Cascades

Instead of a single-trace random walk, we simulate a diffusion process. Similar to a virus spreading, an active node can "infect" multiple neighbors simultaneously. We record "cascades," which capture not only the set of visited nodes but also the timestamp of when each node was first reached. This temporal dimension provides a unique signature of a node's position in the network.

Comparison of random walk and diffusion sequences.

As shown in the figure above, while a random walk (a) moves linearly through the graph, a diffusion process (b) can branch out, capturing both depth and breadth information more effectively.

The Mapping Step: Network Inference and SVD

Using the timestamps from these cascades, the model employs a network inference technique to calculate a weight matrix $A$. This matrix represents the transmission rate or connection strength between every pair of nodes across the entire network. Finally, we apply Singular Value Decomposition (SVD) to this weight matrix to generate the final low-dimensional embeddings. Unlike local "skip-gram" approaches, this inference-based method considers the global flow of information.

Experiments and Results

The model was evaluated on four standard graph datasets: Wiki Network, Citeseer, Cora, and DBLP.

Key Insights

  • Multiple-trace Advantage: By allowing a sampling process to branch out via diffusion, the model captures more information per sample than a linear random walk.
  • Temporal Features: The timing of an "infection" serves as a structural feature. Nodes infected at similar times across multiple cascades are likely to be structurally similar.
  • Global Context: By building a global weight matrix through network inference, the model avoids the "myopic" nature of models that only consider local windows.

Performance and Robustness

On the Wiki dataset, the diffusion method outperformed baselines like DeepWalk, LINE, and GraRep by over 30% in Micro-F1 and Macro-F1 scores. Notably, the diffusion model is far more robust to sparsity; it performs significantly better when the number of samples per node is very low. In a case study on a highly biased DBLP network, the diffusion model maintained high classification accuracy where DeepWalk’s performance dropped significantly due to its tendency to over-sample popular nodes.

Conclusion

This paper introduces a diffusion-based network embedding method that overcomes the limitations of traditional random walks. By leveraging diffusion cascades and network inference, the model captures global structural information and remains robust in imbalanced or sparsely sampled networks. Future work may explore applying this dynamic diffusion process to networks that evolve over time and optimizing the computational complexity of the network inference step.

Summary updated

Abstract

In network embedding, random walks play a fundamental role in preserving network structures. However, random walk based embedding methods have two limitations. First, random walk methods are fragile when the sampling frequency or the number of node sequences changes. Second, in disequilibrium networks such as highly biases networks, random walk methods often perform poorly due to the lack of global network information. In order to solve the limitations, we propose in this paper a network diffusion based embedding method. To solve the first limitation, our method employs a diffusion driven process to capture both depth information and breadth information. The time dimension is also attached to node sequences that can strengthen information preserving. To solve the second limitation, our method uses the network inference technique based on cascades to capture the global network information. To verify the performance, we conduct experiments on node classification tasks using the learned representations. Results show that compared with random walk based methods, diffusion based models are more robust when samplings under each node is rare. We also conduct experiments on a highly imbalanced network. Results shows that the proposed model are more robust under the biased network structure.
BibTeX
@misc{shi2018diffusion,
  author = {Yong Shi and Minglong Lei and Peng Zhang and Lingfeng Niu},
  title = {{Diffusion Based Network Embedding}},
  year = {2018},
  eprint = {1805.03504},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.03504},
}
Figure