PaperlayerView exact revision on arXiv

Source-linked AI summary

Temporal Network Embedding with Micro- and Macro-dynamics

Yuanfu Lu, Xiao Wang, Chuan Shi, Philip S. Yu, Yanfang Ye

arXiv:1909.04246v1cs.LGcs.SIstat.ML

TL;DR

Temporal network embedding must capture both chronological edge formation and network-scale evolution, but existing approaches had not well studied their joint modeling. M2DNE combines a temporal attention point process with an embedding-parameterized dynamics equation, and the authors report that it outperforms state-of-the-art baselines across various tasks.

  • Problem

    Most network embedding methods focus on static networks, and temporal embedding has not well studied how to capture both edge-formation micro-dynamics and network-scale macro-dynamics.

    Source: §1 · pp. 1–2

  • Method

    M2DNE jointly learns node embeddings using a temporal attention point process for chronological edge formation and an embedding-parameterized dynamics equation for network-scale evolution.

    Source: §1 · p. 2

  • Results

    The authors report that M2DNE outperforms state-of-the-art baselines in various tasks, including network reconstruction and temporal link and scale prediction.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    The reported experiments support modeling both structural formation and network-scale evolution within temporal network embedding.

    Source: §6 · p. 10

Abstract

from arXiv · show

Network embedding aims to embed nodes into a low-dimensional space, while capturing the network structures and properties. Although quite a few promising network embedding methods have been proposed, most of them focus on static networks. In fact, temporal networks, which usually evolve over time in terms of microscopic and macroscopic dynamics, are ubiquitous. The micro-dynamics describe the formation process of network structures in a detailed manner, while the macro-dynamics refer to the evolution pattern of the network scale. Both micro- and macro-dynamics are the key factors to network evolution; however, how to elegantly capture both of them for temporal network embedding, especially macro-dynamics, has not yet been well studied. In this paper, we propose a novel temporal network embedding method with micro- and macro-dynamics, named $\rm{M^2DNE}$. Specifically, for micro-dynamics, we regard the establishments of edges as the occurrences of chronological events and propose a temporal attention point process to capture the formation process of network structures in a fine-grained manner. For macro-dynamics, we define a general dynamics equation parameterized with network embeddings to capture the inherent evolution pattern and impose constraints in a higher structural level on network embeddings. Mutual evolutions of micro- and macro-dynamics in a temporal network alternately affect the process of learning node embeddings. Extensive experiments on three real-world temporal networks demonstrate that $\rm{M^2DNE}$ significantly outperforms the state-of-the-arts not only in traditional tasks, e.g., network reconstruction, but also in temporal tendency-related tasks, e.g., scale prediction.

1 INTRODUCTION

Temporal network embedding must capture both how edges form over time and how network scale evolves, yet prior approaches largely focus on static networks or omit macro-dynamics. M2DNE combines temporal attention for edge formation with an embedding-parameterized dynamics equation for network-scale evolution.

1 INTRODUCTION

  • Most existing embedding methods focus on static networks, while prior temporal methods either simplify evolution into snapshots or miss fine-grained structural and temporal properties.The introduction also notes that existing temporal embedding methods had not incorporated macro-dynamics.Source: §1 · pp. 1–2
  • Micro-dynamics describe chronological edge establishments shaped by historical neighbors, while macro-dynamics describe patterned growth in the number of edges.The paper presents both as necessary aspects of temporal network evolution.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • Macro-dynamics constrain how many edges micro-dynamics generate over time, adding a higher-level structural constraint to temporal network embeddings.The paper argues that encoding this evolution pattern can strengthen embedding generalization.Source: §1 · p. 2
  • M2DNE combines a temporal attention point process for edge formation with an embedding-parameterized dynamics equation for network-scale evolution.The two dynamics are jointly optimized and alternately influence node-embedding learning.Source: §1 · p. 2
  • The authors report experiments on network reconstruction, temporal link prediction, and scale prediction to validate M2DNE.These include traditional network tasks and temporal tendency-related tasks.Source: §1 · p. 2

2 RELATED WORK

Prior network embedding work mainly addresses static networks, while temporal methods either embed snapshots or model temporal evolution. The review identifies the omission of both micro- and macro-dynamics as a gap.

2 RELATED WORK

  • Static embedding methods include random-walk, autoencoder, graph neural network, heterogeneous-network, and attribute-network approaches, but focus on static networks.The review also mentions methods designed to preserve properties such as high-order proximity.Source: §2 · p. 2
  • Temporal embedding methods broadly embed snapshots or model temporal evolution, with examples including DynamicTriad, HTNE, and deep representation learning for dynamic graphs.The review also identifies task-specific methods such as NetWalk for anomaly detection.Source: §2 · pp. 2–3
  • The reviewed methods either embed snapshots or model temporal processes with limited dynamics and structures; none integrates both micro- and macro-dynamics.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries define temporal networks as timestamped edge sequences and distinguish event-level formation from network-scale growth. They then introduce point-process context and frame embedding as learning low-dimensional node representations that capture both dynamics.

3.1 Dynamics in Temporal Networks

  • A temporal network is a sequence of timestamped edges, with each edge joining two nodes at a particular time.Repeated links between the same nodes at different timestamps count as distinct temporal edges, unlike a static edge.Source: §3.1 · p. 3
  • Micro-dynamics are the time-ordered events of edge formation, whereas macro-dynamics track cumulative edge growth over time.The paper focuses macro-dynamics on edge growth because new nodes inevitably lead to new edges; micro-dynamics determine which edges form, while macro-dynamics constrain the scale of change.Source: §3.1 · p. 3

3.2 Temporal Point Process

  • A temporal point process models an event's occurrence in a short interval using a conditional probability given historical events.The passage introduces the Hawkes process as a well-known temporal point process.Source: §3.2 · p. 3

3.3 Problem Definition

  • Temporal network embedding learns a low-dimensional mapping from nodes to vectors to model the network's evolution, including both micro- and macro-dynamics.The stated objective is to capture edge formation and network-scale evolution.Source: §3.3 · p. 3

4.1 Model Overview

M2DNE combines edge-event modeling with a higher-level constraint on network-scale evolution. Its micro- and macro-dynamics mutually shape the learned node embeddings.

4.1 Model Overview

  • The micro-level component treats edge establishments as chronological events and uses hierarchical temporal attention to represent influences from the endpoints' historical neighbors.Source: §4.1 · p. 3
  • The macro-level component uses a dynamics equation parameterized by node embeddings and time to constrain network structure according to its scale-evolution pattern.Source: §4.1 · p. 3
  • In the overview example, micro-level prediction indicates three new edges, while the macro-dynamics constraint limits the number to two.The example illustrates how both dynamics contribute to the learned representation.Source: §4.1 · p. 3

4.2 Micro-dynamics Preserved Embedding

M2DNE models edge establishments as chronological events and uses temporal attention to capture how endpoint similarity and historical neighbors shape them. Its hierarchical attention and micro-prediction objective incorporate changing neighbor influence into edge probabilities.

4.2 Micro-dynamics Preserved Embedding

  • Edge establishments are modeled as events whose intensity combines endpoint similarity with influence from both nodes’ historical neighbors.The intensity includes a base contribution from the nodes themselves and two-way neighbor influence that decays over time.Source: §4.2 · pp. 3–4

4.2.1 Hierarchical Temporal Attention.

  • Hierarchical temporal attention weights neighbors locally and collectively, applies time decay, and evolves with neighborhood structure to couple structural and temporal properties.Local influence varies by neighbor; global influence aggregates neighbors and their average time decay.Source: §4.2.1 · pp. 4–5

4.2.2 Micro Prediction.

  • Micro-prediction defines edge-establishment probabilities from event intensities and minimizes their log probability to capture micro-dynamics.Source: §4.2.2 · p. 5

4.3 Macro-dynamics Preserved Embedding

M2DNE represents macro-dynamics with a network-embedding-parameterized equation that constrains network structure according to the evolution of its scale. The model parameterizes linking rate with temporal and structural information and fits predicted edge-count changes to observed changes.

4.3 Macro-dynamics Preserved Embedding

  • A dynamics equation parameterized by network embeddings constrains the network’s internal structure by specifying how many edges should have formed.The paper presents this higher-level constraint as a way to strengthen the capability of network embeddings.Source: §4.3 · p. 5
  • The macro-dynamics equation models new edges using node count, learnable sparsity parameters, and a linking rate.The stated average accessible-neighbor count is ζ(n(t) − 1)^γ; ζ and γ are learned during optimization.Source: §4.3 · p. 5

4.3.1 Linking Rate.

  • The linking rate depends on time and network structure, with an embedding-based term that decays over time.The paper uses a temporal fizzling term and node embeddings to parameterize the rate.Source: §4.3.1 · p. 5

4.3.2 Macro Constraint.

  • The macro constraint fits predicted edge-count changes by minimizing squared errors against observed changes.The predicted quantity is the number of new edges at time t.Source: §4.3.2 · p. 5

4.4 The Unified Model

The unified objective couples edge-formation modeling with constraints on network-scale evolution, so both dynamics shape embedding learning.

4.4 The Unified Model

  • The model captures, in a unified manner, the formation of topological structures and the evolution of network scale, whose micro- and macro-dynamics mutually drive network evolution and influence embedding learning.The macro-dynamics constraint weight ϵ is in [0, 1].Source: §4.4 · p. 5
  • The micro-dynamics objective is optimized approximately with negative sampling, while the macro-dynamics least-squares term uses gradient descent.Edges are sampled proportional to their weights, followed by K negative node pairs.Source: §4.4 · p. 5
  • The implementation uses mini-batch gradient descent to minimize the loss, retaining the most recent historical neighbors up to h.The sigmoid function is used in the rewritten loss.Source: §4.4 · p. 6

5 EXPERIMENTS

Experiments on three datasets assess structural accuracy and temporal prediction, including forecasting network-scale tendency. The reported comparisons favor M2DNE and MDNE across several tasks, with recommendation gains over HTNE reported on Eucore and DBLP.

5.1 Experimental Setup

  • The experiments use Eucore email, DBLP co-authorship, and Tmall user-item purchase networks, with labels drawn from departments, research areas, and purchased categories.The study frames evaluation around accuracy, dynamics, and network-scale tendency.Source: §5.1.1 · p. 6, §5 · p. 6

5.1.2 Baselines.

  • Comparisons include static embedding methods, temporal methods, and MDNE, a variant that captures only micro-dynamics.The listed baselines include DeepWalk, node2vec, LINE, SDNE, TNE, DynamicTriad, and HTNE.Source: §5.1.2 · p. 6

5.1.3 Parameter Settings.

  • All methods use embedding dimension 128 and five negative samples; M2DNE uses dataset-specific historical-neighbor counts and balance factors.The neighbor counts are 2, 5, and 2, and the balance factors are 0.3, 0.4, and 0.3 for Eucore, DBLP, and Tmall, respectively.Source: §5.1.3 · p. 6

5.2.1 Network Reconstruction.

  • MDNE and M2DNE consistently outperform baselines on AUC; M2DNE improves Precision@1000 by 5.78% on Eucore and 4.73% on DBLP over the best competitors.The reported table evaluates network reconstruction.Source: §5.2.1 · p. 6, Table 2 · p. 7

5.2.2 Node Classification.

  • MDNE and M2DNE outperform all baselines in node classification except one case and perform best across training-set sizes in almost all cases.The reported metrics are Macro-F1 and Micro-F1.Source: Table 3 · p. 7, §5.2.2 · p. 7

5.3.1 Temporal Node Recommendation.

  • M2DNE improves Recall@10 by 10.88% and Precision@10 by 8.34% on Eucore, and by 6.05% and 11.69%, respectively, on DBLP, versus HTNE.MDNE and M2DNE outperform the baselines across the reported metrics.Source: Figure 3 · p. 8, §5.3.1 · p. 8

5.3.2 Temporal Link Prediction.

  • MDNE and M2DNE consistently outperform all baselines on both accuracy and F1 in temporal link prediction.The authors attribute weaker snapshot-based methods to their inability to reveal the temporal process of edge formation, and note that HTNE ignores network-size evolution.Source: Table 4 · p. 8, §5.3.2 · p. 8

5.4 Q3: Tendency

M2DNE is evaluated on scale prediction and trend forecasting, extending the paper’s tendency-related tasks beyond traditional network applications. The reported results show more accurate edge-count prediction, while forecast accuracy varies with training data and network.

5.4.1 Scale Prediction.

  • For scale prediction, embeddings are trained on early timestamps, and M2DNE predicts the cumulative edge count at the next time using its dynamics equation.The evaluation compares absolute error; static- and dynamic-network methods count different types of edges.Source: §5.4.1 · p. 8, Table 5 · p. 9
  • M2DNE predicts edge counts more accurately than comparison methods in scale prediction.The authors attribute the comparison methods’ larger errors to their focus on local evolution rather than the global trend.Source: §5.4.1 · p. 8, Table 5 · p. 9

5.4.2 Trend Forecast.

  • As training timestamps increase, forecast errors decrease; accuracy is slightly worse on Tmall, where short-term purchase behavior has a less significant evolutionary pattern.Figure 4 shows real edge-count data and M2DNE forecast curves.Source: §5.4.2 · p. 9, Figure 4 · p. 9

5.5.1 Number of Historical Neighbors.

  • On DBLP, M2DNE performs stably across historical-neighbor settings and reaches its highest F1 score at five neighbors.The authors choose a small neighbor count to balance performance and complexity.Source: §5.5.1 · pp. 9–10

5.5.2 Number of Negative Samples.

  • On DBLP, performance improves as the number of negative samples increases, then reaches its best level at around five; performance is reported as stable overall.The parameter analysis examines sensitivity to negative-sample count.Source: §5.5 · p. 9, §5.5.2 · p. 10

6 CONCLUSION

The conclusion presents M2DNE as a temporal embedding method that models micro- and macro-dynamics, reports gains over state-of-the-art baselines, and identifies shrinking network dynamics as future work.

  • M2DNE combines a temporal attention point process for fine-grained structural and temporal properties with an embedding-parameterized dynamics equation that constrains embeddings to encode inherent evolution patterns.Source: §6 · p. 10
  • Experiments show that M2DNE outperforms state-of-the-art baselines across various tasks.Source: §6 · p. 10
  • A stated future direction is generalizing M2DNE to incorporate shrinking dynamics in temporal networks.Source: §6 · p. 10
Loading 1909.04246v1…