PaperlayerView exact revision on arXiv

Source-linked AI summary

dynnode2vec: Scalable Dynamic Network Embedding

Sedigheh Mahdavi, Shima Khoshraftar, Aijun An

arXiv:1812.02356v2cs.LGcs.SIstat.ML

TL;DR

Real-world networks evolve, but static embedding methods learn separate timestamp spaces and spend time generating walks anew. dynnode2vec updates node2vec with previous embedding vectors and walks for evolving nodes. The paper reports faster running time than node2vec and its all-node-walk variant, while concluding that it obtains embeddings in less time without sacrificing accuracy.

  • Problem

    Static embedding methods do not capture dynamic-network evolution, and separate timestamp learning produces different vector spaces and takes time.

    Source: §I · p. 1

  • Method

    dynnode2vec adapts node2vec by initializing each current Skip-gram model with previous embeddings and generating walks only for evolving nodes.

    Source: §I · p. 1, 1) Evolving Walk generation · p. 2

  • Results

    dynnode2vec was faster than node2vec and dynnod2vec-all on three datasets, and the paper reports less running time without sacrificing accuracy.

    Source: F. Effects of evolving walk generation · p. 3, §IV · p. 4

  • Takeaways & Limitations

    The experiments support using evolving walks and prior embeddings to learn representations for changing networks with less time and no reported accuracy sacrifice.

    Source: §IV · p. 4

Abstract

from arXiv · show

Network representation learning in low dimensional vector space has attracted considerable attention in both academic and industrial domains. Most real-world networks are dynamic with addition/deletion of nodes and edges. The existing graph embedding methods are designed for static networks and they cannot capture evolving patterns in a large dynamic network. In this paper, we propose a dynamic embedding method, dynnode2vec, based on the well-known graph embedding method node2vec. Node2vec is a random walk based embedding method for static networks. Applying static network embedding in dynamic settings has two crucial problems: 1) Generating random walks for every time step is time consuming 2) Embedding vector spaces in each timestamp are different. In order to tackle these challenges, dynnode2vec uses evolving random walks and initializes the current graph embedding with previous embedding vectors. We demonstrate the advantages of the proposed dynamic network embedding by conducting empirical evaluations on several large dynamic network datasets.

I. INTRODUCTION

Static graph embeddings represent nodes in low-dimensional vectors that preserve neighborhood information, but real-world networks evolve over time and independently learned timestamp embeddings occupy different spaces. dynnode2vec adapts node2vec with previous embeddings and evolving random walks, and the paper evaluates it on dynamic-network tasks.

  • Static graph embeddings represent graph nodes in low-dimensional vectors that preserve neighborhood information and support tasks including visualization, classification, link prediction, and recommendation.Source: §I · p. 1
  • Dynamic networks add, delete, or change nodes and edges, while independently learned timestamp embeddings occupy different spaces and take time to train.Source: §I · p. 1
  • dynnode2vec initializes the current Skip-gram model with previous embedding vectors and generates evolving random walks only for nodes changed between consecutive timestamps.Source: §I · p. 1
  • The authors characterize dynnode2vec as a fast and accurate method that captures evolving patterns in large dynamic networks.Source: §I · p. 1
  • The paper evaluates dynnode2vec on link prediction, node classification, and anomaly detection in large real-world graphs.Source: §I · p. 1

II. Dynnode2vec: SCALABLE DYNAMIC NETWORK EMBEDDING

The method adapts node2vec, which combines flexible random walks with Skip-gram learning, to represent a dynamic network as a timestamped sequence of graphs. Its static node2vec foundation samples neighborhoods using breadth-first and depth-first strategies.

  • A dynamic network is represented as a sequence of timestamped graphs, and dynnode2vec modifies static node2vec to learn its representations.Source: §II · p. 1
  • Static node2vec generates a corpus of random walks of length t from each vertex, with γ walks sampled per vertex.Source: §II · p. 1
  • Skip-gram learns node representations from the walks, while node2vec samples neighborhoods using breadth-first and depth-first strategies.Source: §II · p. 1

A. Description of dynnode2vec steps

dynnode2vec runs static node2vec on the first graph, then updates embeddings across consecutive timestamps. It generates walks for evolving nodes rather than all nodes, with the efficiency advantage depending on changes being limited to part of the graph.

A. Description of dynnode2vec steps

1) Evolving Walk generation:

2) Dynamic Skip-gram model:

dynnode2vec adapts dynamic Skip-gram approaches by updating the vocabulary and training on walks from evolving nodes. Its algorithm starts with static node2vec on the first graph, then repeats changed-node walk sampling and Skip-gram training at later timestamps.

2) Dynamic Skip-gram model:

  • Dynamic word embedding work and DynGEM provide precedents for initializing a timestamp's model with vectors learned at the previous timestamp.Source: 2) Dynamic Skip-gram model · p. 2
  • dynnode2vec updates the Skip-gram vocabulary using evolving walks, then trains the current model on walks generated for evolving nodes.Source: 2) Dynamic Skip-gram model · p. 2
  • The algorithm runs static node2vec on G1, then iterates over later timestamps to find evolving nodes, sample their walks, and train Skip-gram embeddings.Source: 2) Dynamic Skip-gram model · p. 2

III. EXPERIMENTS

The evaluation uses dynamic networks spanning coauthorship, communications, email, and online interactions, with dataset sizes and time spans varying substantially.

A. Datasets

  • Hep-th is a high-energy physics theory coauthorship network with 34k nodes, 421k edges, and 60 graphs.Source: A. Datasets · p. 2
  • The Autonomous Systems dataset, built from BGP logs, contains 6k nodes and 13k edges across 100 time steps.Source: A. Datasets · p. 2
  • Enron represents employee email communication and contains 87k nodes and 1.1M edges over 175 months.Source: A. Datasets · p. 2
  • StackOverflow data comes from Math Overflow interactions and contains 14k nodes and 195k edges over 2,350 days, divided into 58 graphs.Source: A. Datasets · p. 2
  • DBLP contains 90k nodes and 749k edges over 18 years, with nodes labeled in database/data mining or computer vision/pattern recognition research areas.The dataset covers researchers across the listed conferences in both fields.Source: A. Datasets · p. 2
  • The Darpa subset contains communications between source and destination IPs, including attacks, across 12k nodes and 22k edges over 100 hours.Source: A. Datasets · p. 2

B. Baselines

The comparison includes static random-walk embedding methods and DynGEM, an incremental dynamic embedding baseline whose memory demands restrict its evaluation.

B. Baselines

  • DeepWalk [4] learns graph neighborhoods using Skip-gram and uniform random walks.It is described as the first node embedding method based on random walks.Source: B. Baselines · p. 2
  • node2vec [3] learns node representations by exploring neighborhoods with DFS and BFS random walks.Source: B. Baselines · p. 2
  • DynGEM [17] incrementally builds embeddings from the previous time point, but its memory requirements prevented evaluation on Enron and DBLP.The paper reports running DynGEM only on AS, Hep-th, and St-Ov.Source: B. Baselines · p. 2
  • Table I covers link-prediction results using Weighted-L1, Weighted-L2, Hadamard, and average operators.Source: Table I · p. 3

C. Link Prediction

For link prediction, dynnode2vec outperforms baselines on almost all four evaluated datasets, with performance depending on the edge-embedding operator.

C. Link Prediction

  • dynnode2vec outperforms baselines on almost all four datasets, performs best with Hadamard, and performs worst with the average operator.Results are average AUC across AS, Hep-th, Enron, and St-Ov.Source: C. Link Prediction · p. 3
  • The task predicts edges at each future time point from edges observed at earlier time points, treating link prediction as classification.Source: C. Link Prediction · p. 3
  • Edge embeddings are formed from endpoint node vectors using Weighted-L1, Weighted-L2, Hadamard, or average operators; p and q are grid-searched over 0.5, 1, 2, and 4.Source: C. Link Prediction · p. 3

D. Node Classification

On DBLP node classification, the paper reports that dynnode2vec exceeds other baselines in Micro-F1.

D. Node Classification

E. Anomaly Detection

dynnode2vec identifies attack-related structural changes through embedding shifts and reduces runtime by generating walks only for changed nodes. Its link-prediction AUC is not significantly different from all-node sampling in most cases.

E. Anomaly Detection

  • Three peaks in dynnode2vec’s curve corresponded to time points when important attacks occurred in the DARPA dataset subset.The method signals structural change using the norm of embedding differences for common nodes at consecutive time points.Source: E. Anomaly Detection · p. 3

F. Effects of evolving walk generation

IV. CONCLUSION

dynnode2vec combines dynamic Skip-gram initialization from prior embeddings with evolving random walks to represent temporal network changes. Experiments report less time without sacrificing accuracy, and future work will investigate other dynamic Skip-gram models.

IV. CONCLUSION

  • dynnode2vec combines dynamic Skip-gram with evolving random walks to discover information changes in temporal networks.Prior-timestamp embedding vectors initialize the next timestamp, resulting in smoother embeddings over time.Source: §IV · p. 4
  • By considering only a subset of random walks, dynnode2vec obtains embeddings in notably less time without sacrificing accuracy.Source: §IV · p. 4
  • Future work will investigate other dynamic Skip-gram models for dynamic graph embedding.The conclusion also reports experimental superiority over state-of-the-art embedding methods across various tasks.Source: §IV · p. 4
Loading 1812.02356v2…