ESSEN: Improving Evolution State Estimation for Temporal Networks using Von Neumann Entropy
Authors: Qiyao Huang
Yingyue Zhang
Zhihong Zhang
Edwin Hancock
Venue: NeurIPS 2023 poster (2023)
Keywords: Temporal Network
Graph Neural Network
Von Neumann Entropy
TL;DR: A novel temporal network representation framework aims to capture the evolution states adaptively by approximate von Neumann entropy.

Abstract: Temporal networks are widely used as abstract graph representations for real-world dynamic systems. Indeed, recognizing the network evolution states is crucial in understanding and analyzing temporal networks. For instance, social networks will generate the clustering and formation of tightly-knit groups or communities over time, relying on the triadic closure theory. However, the existing methods often struggle to account for the time-varying nature of these network structures, hindering their performance when applied to networks with complex evolution states. To mitigate this problem, we propose a novel framework called ESSEN, an Evolution StateS awarE Network, to measure temporal network evolution using von Neumann entropy and thermodynamic temperature. The developed framework utilizes a von Neumann entropy aware attention mechanism and network evolution state contrastive learning in the graph encoding. In addition, it employs a unique decoder the so-called Mixture of Thermodynamic Experts (MoTE) for decoding. ESSEN extracts local and global network evolution information using thermodynamic features and adaptively recognizes the network evolution states. Moreover, the proposed method is evaluated on link prediction tasks under both transductive and inductive settings, with the corresponding results demonstrating its effectiveness compared to various state-of-the-art baselines.

ESSEN: Improving Evolution State Estimation for Temporal Networks using Von Neumann Entropy
Qiyao Huang', Yingyue Zhang', Zhihong Zhang"', Edwin Hancock
School of Informatics, Xiamen University, China Department of Computer Science, University of York, York YO10 5GH, UK. {30920211154155, 30920221154611
xmu edu. cn
zhihong@xmu, edu. en, edwin. hawcockkyork.cc.c
Abstract
Temporal networks are widely used as abstract graph representations for real-world dynamic systems. Indeed, recognizing the network evolution states is crucial in understanding and analyzing temporal networks. For instance, social networks will generate the clustering and formation of tightly-knit groups communities over time, relying on the triadic closure theory. However, the existing methods often struggle account for the time-varying nature of these network structures, hindering their performance when applied to networks with complex evolution states. To mitigate this problem, we propose novel framework called ESSEN, an Evolution StateS awarE Network, to measure temporal network evolution using von Neumann entropy and thermodynamic temperature. The developed framework utilizes a von Neumann entropy aware attention mechanism and network evolution state contrastive learning in the graph encoding. In addition, it employs a unique decoder the so-called Mixture of Thermodynamic Experts (MoTE) for decoding. ESSEN extracts local and global network evolution information using thermodynamic features and adaptively recognizes the network evolution states. Moreover, the proposed method is evaluated on link prediction tasks under both transductive and inductive settings, with the corresponding results demonstrating its effectiveness compared to various state-of-the. the-art baselines
Introduction
Recently, graph representation learning has demonstrated excellent performance for various types of statie graphs 14 28 [8]
Indeed, the success of static graph representation learning has led to a growing interest in continuous-time dynamic graph representation learning. Temporal network representation learning has emerged as an active research area focusing on learning low- dimensional representations that capture topological and temporal properties. However, learning effective representations is still a difficult task in many temporal networks, which are naturally generated in real-world systems such social networks [12] and citation networks. The evolving nature of these networks poses significant challenge for network analysis and modeling as the relationships between nodes and their properties evolve. The existing methods often struggle to account for the time-varying nature of these network structures, hindering their performance when applied to networks with complex time-evolving states. However, capturing the evolution states of temporal networks suffers from the following challenges: (1) Temporal networks have different types of evolution states, such periodic, linear, non non-linear changes in their structure over time. Moreover, the evolving patterns can change at different stages in the evolution of the network. As
"Corresponding author.
'Code available at http://ggttabbboom//lyoouuuggggg
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a) MathOverflow: 10th Day (b) MathOverflow: 20th Day (c) MathOverflow: 30th Day
(d) BitcoinOTC: 10th Day
(c) BitcoinOTC: 20th Day
(f) BitcoinOTC: 30th Day
Figure I: Network snapshots of the MathOverflow website and BitcoinOTC trading platform on the 10th, 20th, and 30th day. The black nodes represent the users who have connections, and the grey nodes represent the users with edges prior the snapshot time.
illustrated in Fig. [ the rate of evolution varies at different times in both datasets. The MathOverflow network evolves rapidly and has obvious central nodes, which means meaningful topics will receive long-term attention. By contrast, in the BitcoinOTC network, early active users may quickly become dormant. This phenomenon requires algorithms that can perform extensive and effective recognition of diverse evolution states. (2) As time passes, temporal networks tend to accumulate more nodes and edges, resulting in increasing number of possible connections and rapidly growing neighborhood size for each node. This growth in the neighborhood size can lead to significant computational challenges when analyzing and modeling evolving patterns. Besides, many connections quickly make structure recognition computationally intractable in large and complex networks, especially those recent methods based the anonymous walk [24 6 20) The time complexity is tightly related to the length and number of paths, so it challenging to balance time consumption and algorithm effectiveness.
To overcome these shortcomings, this paper, we use the von Neumann network entropy to improve evolution state estimation. Network entropy is macroscopic representation of network structures widely used to characterize the salient features of static and dynamic network systems in biology. physics, and social sciences. In particular, von Neumann entropy has been successfully used to describe the structural properties random, small-world, and scale-free networks [ 2), and thus plays crucial role in understanding the structural and topological complexity of network systems. Moreover, the ability of von Neumann entropy to capture structural information content aligns well with the time-evolving nature of temporal networks. This potentially allows us to adopt cnoomaation-thereele perspective to enhance our understanding of the laws of the network's evolution and their capacity both transmit and store information time.
Unfortunately, computing the required network entropies for temporal networks can be computa- tionally burdensome due to the required spectral decomposition. Hence, approximate the von Neumann entropy to render tractable in the context of temporal networks. Compared with alterna- tive graph entropies, by approximating von Neumann entropy with low time complexity can better adapt to the constantly evolving nature complex temporal networks. Moreover, we can compute an approximate thermodynamic temperature for the temporal network, which provides an important way to monitor changes in network structure with time. Measuring the thermodynamic temperature and the Neumann entropy provides better understanding of the state of network evolution with time.
On this basis, we propose an Evolution StateS awarE Network (ESSEN). As shown in Fig. ESSEN encodes node embeddings with state evolution information by utilizing two proposed techniques:

---

a) von Neumann entropy aware attention mechanism and b) virtual evolution node representation learning. In addition. ESSEN employs a unique mixture of thermodynamic experts (MoTE) for the purposes of decoding. Specifically, we project the global von Neumann network entropy into each edge. The proposed von Neumann entropy aware attention mechanism aggregates over neighborhoods in both a virtual evolution graph and the original graph based on the von Neumann projected edge entropy. In the virtual evolution graph, future edges are hypothesized based on a test pertaining to future instants in time. The MoTE decoder evaluates the evolution state based on both the thermodynamic temperature and von Neumann entropy over both graph representations, providing a combined result from multiple experts. The decoder adaptively recognizes the network under various evolution states. Our framework is evaluated on transductive and inductive link prediction tasks. The experimental results demonstrate our method's 's effectiveness compared to various state-of- oftte-of-the-arr baselines. The overall contributions of our work are summarized as follows:
To our best knowledge, we are the first to utilize the von Neumann entropy in temporal network representation learning. We provide method to expand the approximate von Neumann Entropy and approximate thermodynamic temperature to temporal networks.
We propose novel framework, namely ESSEN. evolution-aware node representations using the von Neumann entropy aware attention mechanism and virtual evolution node representation learning. Furthermore, the model uses novel decoder MoTE that adaptively recognizes temporal network evolution states.
The model introduces new perspective encode
We evaluate our framework on link prediction tasks with transductive and inductive settings. The results show the effectiveness of our proposed method compared to various statc-of-the-ar baselines.
2 Preliminaries
Temporal Network. Formally, the temporal network can be denoted as G = EV, where V represents the set of nodes, E C V V represents the set of links, and T represents the set of timestamps. Each link (u, v, t) signifies a connection between node u and node v at time t. The temporal network evolves networks can also include attributes associated with nodes or links, providing further information about the entities their interactions specific timestamps.
time, with links appearing at different timestamps. The temporal
Dynamic Link Prediction. In a temporal network = (V, E,T), the dynamic link prediction task aims to predict the presence or absence of a link at future timestamp based on the observed network evolution history. Given a time window Te. C T, which contains the observed link data, denoted as ET., S E, the goal is to learn function f EV. . + {0, 1} that assigns probability score to the existence link (u, v) at the future timestamp t. Mathematically, the function f can be defined as:
fl,, P(u, elt,, Er.),
(1)
where P((u, it,t Er..) represents the probability of the link (u, v) being present at the future timestamp given the observed network and the link data Er., within the time window Tw.
Evolution State. Eyolution state denotes the specific arrangements of nodes and edges at specific instants of time. These states can be characterized by network topology, reflecting the evolving nature of the network over time. For example, social networks at specific evolution states will generate the clustering and formation of tightly-knit groups communities over time via the tri- adic closure theory [29]. The theory is formally defined as 2u, w, w' E V (u, v), (v, w) E ET,, (u, w), (u, w'), (v, w') & ET_ + P(u, w ET_) > P(u, w w'\\ET)). Therefore, analyzing evolu- tion states helps in understanding the temporal behavior of the network, identifying recurring patterns, predicting future states, and studying the impact of temporal dynamics on network properties and phenomena. In this paper, we aim to capture evolution states using thermodynamic entropy.
Von Neumann Entropy. Von Neumann Entropy is the quantum counterpart of the Shannon entropy. For a quantum system with a density matrix p the von Neumann entropy is Syx = - Tr(pp p). The density matrix p describes system whose state is mixture of pure quantum states (x%), each with probability p:, and is defined as p = -i=1 Pc (4/s) (Wh,,, where T is the number of pure states. When defined in this way, the density matrix is Hermitian, i.c., p pt and p > 0, Tr[p] 1, where
3

---

Vituel or tttmmt
Evolution State Estimation F Fealure Extrectors (G
Virtual Evolution Graph 6
fove( fr (G Gi
parameter sharing
Querr Time Encoding
Expert
Expert
Expert
Attontion Methanism
Link probability P(u, (t)
Real Evolution Graph
G22
Evolution Graph Encoder
Mixture of Thermodynamic Experts Decoder
Figure 2:
The framework of ESSEN. It comprises two modules: (I) Evolution States Aware Graph Encoder. (2) Mixture of Thermodynamic Experts Decoder.
represents conjugate transpose. It plays important role in the quantum observation process, which can be used to calculate the expectation value of measurable quantities.
Severini et al. [17 show that density matrix for graph or network can be obtained by scaling the combinatorial Laplacian matrix = D A (where A is the adjacency matrix and D is the diagonal degree matrix) by the reciprocal of the number of nodes in the graph Vl. i.c. p MV The interpretation the scaled normalized Laplacian as a density operator opens up the possibility of characterizing graph using the von Neumann entropy. With the definition of the density matrix adopted, the von Neumann entropy [7 can be computed from the normalized Laplacian spectrum as follows:
L
|
A
A V
Svw(G) - Tr(ppor
log
where Ag...... Add are the eigenvalues combinatorial Laplacian matrix. This form of von Neumann entropy has been shown to be effective for static network characterization.
The Proposed Method
3.1 Evolution State Estimation
Von Neumann Entropy Computation in Temporal Network. The von Neumann entropy can be computed the static graph by Eq. However, the application to temporal networks two challenges: (1) The dynamic nature of the temporal network. Unlike static networks, where the structure remains constant, temporal networks capture time-evolving relationships and interactions. This dynamic nature introduces challenges in analyzing and modeling the network behavior, the network topology and connectivity patterns may vary at different times. (2) The computationally ex- pensive time complexity of obtaining the Laplacian eigenvalues. In Eq. computing the eigenvalues of the Laplacian matrix is a computationally intensive task, and the time complexity is cubic in the number of nodes. In temporal networks, where the network strueture changes over time, repeatedly calculating the Laplacian eigenvalues can become prohibitively expensive.
To address these challenges, we must simplify the network and efficiently approximate thermodynamic quantities. First, we select a specific time interval for the temporal network and aggregate edge weights frequencies over this interval. The number of occurrences within the chosen time frame

---

determines the strength of an edge. Following this process, the temporal network can be projected to the -ideeeddeendent 2-D plane, which provides a simplified representation of the underlying network structure at a specific time. Moreover, following [27, we use the approximate expression for the von Neumann entropy and reduce the computation to be quadratic in the number of nodes. The approximate von Neumann entropy is
GG) = 1
1 IV
Σ
1 dudd
(3)
(U,0)E
where V the node set of the temporal network, and du dy are the degree of node u and v time t. This approximation allows the von Neumann entropy to be computed without explicitly solving the eigensystem for the normalized Laplacian. Thus, the von Neumann entropy can be computed in quadratic time using the node degrees for pairs of nodes connected by edges. We introduce the details of the approximate method in Appendix
Thermodynamic Temperature. In thermodynamics, the thermodynamic state of a system can be fully described by an appropriate set of thermodynamic variables. We treat the von Neumann entropy as a thermodynamic network entropy and use the thermodynamic temperature to T measure fluctuations in network structure with time. Specifically, suppose that the graphs G1 and G2 represent the structure of a time-varying system at two consecutive epochs 1 and l2 respectively. For a thermodynamic system with fixed number of particles, the change in energy is de Tds P. where P. and V, denote the pressure and volume of the system respectively. It is important to stress that this equation holds and is valid for both reversible and irreversible processes for a closed system, since e, T. S. P. and Vo are all state functions and are independent of thermodynamic path. We assume the network evolves from time t to time f2 under constant-volume (isochoric process) as the time interval becomes small, i.e. At + 0. As result, for the path from G1 to G2 we have dV. = 0 and de Tds. The reciprocal of the temperature T is the rate of change of entropy with average energy, i.e.,
de e((2)
T T(1,,
ds - - S(G2)
where S(G1) is the graph entropy for the graph G1 and e(Gi) is the graph average energy. Moreover, the thermodynamic temperature can also be approximated when we represent the temporal network as a directed graph. The approximate computation method uses a low-order Taylor series that can be computed using the traces of powers of the normalized Laplacian matrix, avoiding explicit computation of the normalized Laplacian spectrum (26). In summary, the temperature associated with the evolutionary transition between the two networks can be approximated as
2 2. K(G1) K(G22)
T G2), = - 3k [(G)) J (G2)
(5)
where
Aur
J(G) Σ
(6)
dy
U.EV
Ave
X(G Σ
dy
W.
where & is the Boltzmann constant, and A is the adjacency matrix of the network. (G) and (G are network structure statistics that can be interpreted as the probabilities of a random walker traversing specific edges or cycles in the graph. The computation of temperature is quadratic in the number of nodes.
In summary, by simplifying the network representation and using efficient approximations, the von Neumann entropy and the thermodynamic temperature can be computed effectively in temporal networks. These measures provide insights into the evolving nature of the network and enable the estimation of its evolution state.
3.2 Evolution States Aware Graph Encoder
Von Neumann Entropy Aware Attention Mechanism. In graph encoding, we utilize the von Neumann entropy to explore a more diverse and balanced distribution of attention weights with the
5

---

attention mechanism in the input neighborhood. This strategy helps us to learn network evolution states adaptively. According to Eq. E] the global network entropy is a sum of contributions from individual edges. The von Neumann entropy of the edge connecting nodes u and v is
1
SWN (G.) =
(8)
E V
E d.
To encode entropy features into attention layers, we use the von Neumann edge entropy bias term
in an attention [20) Moreover, we use a time position encoding module to supplement the continuous time information for edges using the simplified von Neumann entropy. For target node u at time t, the attention weight dg for the neighboring node u in the 1th layer is
T
(K!)
SWE (Ge);
(9)
Vdn
- = (1o0~"1eeolo@001) (
(10)
KD = M.l:Wn.
(11)
M = (h. 11 (1e0:-)leewo,:l000 -1) 1)) WM::
(12)
where "Il" is the concatenation operation. WK E R(da+d+dd)xdd and We E Rldxtd+d.)xx. the projection matrices to obtain the query matrices and key matrices, where dn. de and de are the dimensions of the node representation, the time code, and the entropy bias, respectively, ep is an all-zero vector to keep the same dimension as K and V, and o (*) is the generic time position encoding module from 255,, which encodes the difference between the edge timestamp and the query timestamp. M is the message representation at time / from node to u, where 1, 115-1) is node v's hidden representation on the (1 1 layer, Cuv,e Rd is the edge feature, and f, is the query time. Next, the model combines values with the attention weight aware of generating hidden representation zu (t) for node Finally, an MIP is used to combine the node representation of the previous layer with the neighborhood information:
(1LP(0-"1111) (1))
(13)
(t)
Σ VE
softmax, (t) Vo(t),
(14)
ViUh (0) Wv: uo,t
(15)
where Vi(0) is the value vector of neighbor node and No is neighbor node set that connects with node u before time t.
Virtual Evolution Node Representation Learning. Temporal networks follow time-dependent evolution laws. The emergence of nodes and edges different times can often predicted, i.e., future network states can be predicted from their past states and together with the evolutionary laws. Virtual evolution node representation learning utilizes historical evolution information together with the future potential evolution path to generate virtual node representations. Specifically, the dynamic link prediction task aims to predict the probability the link between two nodes appearing at future instant in time. We assume the link has been generated at the query instant and further construct a virtual evolution graph belonging to the query node pair based on this assumption. For example, given node pair (u, v)) and the query time t, there is virtual edge at time t that connects the nodes u and the virtual evolution graph G'u-- The approach makes the two node neighborhoods interconnected. We denote as li and hi the virtual future node embeddings of nodes u and w. Moreover, the thermodynanin temperature of the virtual evolution path can be computed because the instantaneous virtual evolution process is also an isochoric process we introduced in Section 3.1. Based on this, the decoding process estimate the evolution states more comprehensively.

---

3.3 Mixture of Thermodynamic Experts Decoder
Evolution State Feature Extractor. We use the von Neuman entropy of the original graph, the von Neuman entropy of the virtual evolution graph, and the thermodynamic temperature between the two networks to construct unique vector for evolution state estimation. The vector represents the network evolution states in 3-D thermodynamic space, which is spanned by the von Neumann entropy at the two instants time together with the thermodynamic temperature. The approximate von Neumann graph entropy for the original and virtual evolution graphs are computed by Eq. [ and the approximate thermodynamic temperature computed by Eq. 5 Furthermore, to control evolution-awe aware time intervals, which is important for large temporal networks, we compute these approximate thermodynamic quantities the node neighborhood and set the sampled neighborhood size N.
Expert Decoding Process. The mixture thermodynamic experts decoder dynamically selects the appropriate thermodynamic expert model based on the input expert assessment feature vectors. For each expert, we use a two-layer MI.P model to represent. Then the MoTE decoder combines the output embedding of each expert model using respective expert weights to produce the final target score as follows:
score(u, u,t)
Σ a (W: Be, R1 h hi h. ma i=1
(16)
n. soflmar, (TGG
(17)
where Y is the total number of experts, n; is the mixing coefficient of expert i. Additionally, W₁ 144xx is the weight matrices for expert and Wa e R the weight matrix of the gate unit. Finally, h, and h2 are the embeddings of node in the original graph and the virtual time-evolved graph generated by the encoder.
3.4 Optimization
During training, we evaluated the convergence behavior of our model by monitoring the training and validation loss, ensuring that the model was underfitting or overfitting. The loss function is:
Σ
log P(us, By (4g)) - 2 EE-P(()) log P(e,, T (iy).
(18)
where (vi, Uj (ij) is an observed edge on the temporal network, denotes the number of negative samples, and P(0) is the negative sampling distribution over the node space E.
3.5 Computational Complexity Analysis
This section highlights the efficiency of our approach in calculating approximate thermodynamic quantities of temporal networks. Based on Eq and Eq. 55 the time complexity of computing approximate von Neumann entropy and the approximate temperature is O(IVI), where |V] the number of nodes in the network. Moreover, we compute the approximate thermodynamic quantities in the neighborhood for the large networks and set the sampled neighborhood size N. The computational complexity can be reduced to O(N2) in this setting. Therefore, the time complexity demonstrates scalability and establishes the feasibility of our method for moderate or large networks. Since the time complexity is controllable this means we can achieve efficient computation.
4 Experiments
Table 2: Statistics of the datasets.
Dataset
Nodes
Edges
Timespan
4.1 Experimental Setup
MathOverflow
21,688
107,581
2350 days
Datasets. The temporal network datasets used in our experiments are divided into three cat- egories: (a) QA: The "answers to questions"
BitcoinOTC
5,881
35,592
1903 days
BitcoinAlpha
3,783
24,186
1901 days
Wikipedia
9,227
157,474
30 days

---

Table 1: Performance of A for link prediction. The best results in each column are highlighted in bold font and the second- bestt results are underlined. We report the AP results Appendix
Task
Methods
MathOverflow
BitcoinAlpha
BitcoinOTC
Wikipedia
JODIE
86.07 #0.48
91.14 #0.18
92.29 #0.11
93.58 +2.00
DyRep
80.77 #0.65
79.39 #3.17
79.21 +4.10
94.22 #0.27
TGN
80.47 =3.24
86.71 #1.00
86.78 #2.29
98.46 #0.10
TGAT
10.91
78.99 #0.50
79.53 #0.67
95.34 =0.10
Transductive
CAW
53.82 +0.28
64.70 #0.93
73.95 #1.22
98.96 10.10
TDLG
84.02 #0.16
92.83 #0.22
93.48 #0.22
88.9 #0.09
NeurTWs
92.56 +0.51
93,95 #0.41
95.75 #0.01
94.54 #0.87
ESSEN
98.60 +0.40
99.10 #0.16
98.88 #0.42
99.03 +0.33
JODIE
$7.06.00.4
74.47 #0.16
76.21 #0.47
91.44 #1.99
DyRep
63.50+0066
66.27 #0.73
65.09 #0.86
91.03 #0.34
TGN
64.50
69.36 40.94
21.22
97.70 #0.18
TGAT
60.02
6..12
61.99
93.99 #0.30
Inductive
CAW
37.67+0.33
64.38 #1.01
72.99 #0.46
98.75 #0.14
TDLG
74.31 #1.58
83.85 #1.65
85.22 #3.89
45.77 #3.06
NeurTW's
91.83 #0.13
94.20 #0.26
96.08 #0.38
94.63 #0.47
ESSEN
98.33 +0.28
98.07 #0.64
98.67 #0.31
98.80 #0.10
dataset of MathOverflow. (b) Bitcoin trading data: BitcoinAlpha Dataset and BitcoinOTC Dataset
2 [) (c) Social networks: Wikipedia Dataset[10]. Table 2 gives more details concerning the
properties these datasets.
Baselines. In addition to reporting the performance of our ESSEN method, we report results for several popular dynamic graph learning methods, namely a) JODIE [IO] DyRep [I]] c) TGAT [25]: d) TGN [19]; e) CAW (24): f) TDLG[]: and NeurTWs]G) We give more details concerming these baselines in Appendix C.
Link Prediction Task Settings. We evaluate our model on the link prediction task with two different settings:
Transductive Setting. The model under the transductive setting is trained the available nodes and their connections to predict future links between the nodes. The setting assumes that the network will not add unseen nodes at future testing times. This mainly evaluates the transductive ability of the model.
Inductive Setting. The inductive setting predicts missing links for existing nodes together with potential new nodes that may be added future times. This generalizes link prediction beyond the known nodes, considering the possibility of the addition of new nodes. In this way, it learns network patterns and characteristics to make predictions applicable both known and unknown nodes.
Implementation Training Details. For each dataset, we used the training time points Ter = 70%
to split the dataset results in approximately 70%-15%-155% of the total edges 255 The principal hyperparameters are set as follows: a) the number of attention heads 44 = {2, 3}. b) the number of the GNN layers L
the maximum number of aggregated neighbors E {60, 80, 100). d) the total number of experts in MoTE Y (4, 6, 8, 10}. and e) the dimension of the node embedding d, = 172. We use the ADAM optimization algorithm for model training with learning rate 1e-3 and batch size of 128. All the models are implemented in Py PoToc and evaluated on single Tesla A100 GPU.
4.2 Results and Discussion
Table reports the transductive and inductive link prediction task results on four datasets, demonstrat- ing the state-of-the-art performance of our method on link prediction tasks. Our method significantly outperforms all baselines on all datasets. In particular, in the MathOverflow dataset, compared with NeurTWWs, the second strongest baseline, ESSEN improved the AUC(%) by 5.04% and 6. 6.50% on average in the transductive and inductive setting. The results demonstrate that method has

---

clear advantage for temporal networks. Specifically, our method performs well on both long and short-evolution time networks, while the effectiveness of baseline models varies significantly. CAW and TGAT have significant gaps in performance with MathOverflow and Wikipedia for all tasks. This indicates that our framework better represents networks with ever-changing evolution states. This superiority in performance can be attributed to a) our von Neumann entropy aware mechanism, b) the virtual evolution node representation learning, and c) the MoTE decoder. In addition, our method is effective under both transductive and inductive settings. By contrast, the baseline JODIE method cannot predict interactions well between unseen nodes because pays more attention to node identities rather than the evolution states of temporal networks.
4.3 Ablation Study
To validate the effectiveness of the novel elements comprising ESSEN, we conduct series of ablation studies and report the AUC results. We investigate the performance of the proposed modules with three ablated models on the MathOverflow and BitcoinAApha dataset: a) ESSEN-E E,, here we remove the von Neumann edge entropy bias in the attention mechanism of ESSEN. b) ESSEN-V, here we remove the virtual evolution node representation and only use the node embeddings of the original graph for decoding. c) ESSEN-D, here we replace the MoTE decoder with simple MLP decoder. In Fig. 3 we can that the performance degrades without considering the von
675-
00.
67.
DO2DLY
003
Figure 3: Ablation Study
Neumann entropy information for edges. This demonstrates the effectiveness of the proposed von Neumann entropy aware attention mechanism. Disabling the virtual evolution node representation also degrades performance. Furthermore, when the MoTE decoder is removed, the MathOverflow and BitcoinAApha datasets exhibit more severe drops in performance, demonstrating that the MoTE decoder excels on temporal networks with a long time span and a greater number of evolution states.
4.4 Qualitative Analysis of Evolution States
In Fig. we show curves of the von Neumann entropy change for different networks over the same time interval. Compared with the BitcoinOTC dataset, the MathOverflow leads to the generation of more nodes with high degrees, and these have higher entropy. The von Neumann entropy increases at varying rates, depending on the evolution states of the network in question. This reveals the potential relationship between von Neumann entropy and evolution states. Moreover, we can further understand network structure using von Neumann entropy. For evolution states with low entropy, networks tend to be tree-like or string-like and have more low-degree nodes. For networks with evolution states with high entropy there are more high-degree nodes and the networks tend to be fully connected.
140
0405
Figure 4: Von Neumann en- tropy changes on temporal net- works.
4.5 Parametric Sensitivity
We investigate the sensitivity of our ESSEN to various parameters and evaluate their impact on model performance. In Fig. 5 we report the results of this study and draw the following observations: a) By exploring different training time split points, we evaluate ESSEN's performance with lower training samples and more testing samples. Our model sustains excellent performance even when the number of samples in the training set is reduced. The results clearly show the robustness of ESSEN for complex evolution states. b) Considering the number of experts Y. both datasets have "sweet spots". This finding indicates that different datasets exhibit preference for specific numbers of experts in the MoTE decoder. This can be attributed the varying complexity of evolution states in the temporal network. c) We observe strong correlation between the evolution-awan neighborhood size N and the number of nodes in the temporal networks. The link prediction performance decreases when N & [V]. For example, the total number of nodes in the MathOverflow dataset is 2 21688, which is also the maximum value of [V] because nodes will added and deleted over time. The AUC results for the MathOverflow dataset reduced from 98.56% to 95.43% when varying N from 200 to 50. This

---

(a) Training Time Point (%)
(b) Number Experts Y
(c) Sampled Neighborhood Size
Figure 5: Study on important settings. We report the results of the inductive link prediction.
result shows promising trade-off between computational efficiency and the loss of information due to sampling.
5 Related Work
Temporal Network Representation Learning. Network representation learning is often used to transform large networks into lower-dimensional vectors. For instance, CTDNE [5] learns node embedding from a continuous-tine dynamic network instead a sequence of snapshots. Besides, JODIE [10] uses recurrent neural networks (RNNs) to learn trajectories of users and items and updates the embedding when interaction occurs. Expanding on this, TGAT [25] utilizes self- attention mechanism and presents an encoding method learn inductively. Additionally, CAW (24 and NeuralTWss [6] learn temporal structure using random walk. Specifically, CAW proposes new anonymization strategy, and NeuralTWss considers structural and tree traversal properties. TDLG aims to model the edges in temporal networks directly instead of calculating from node embedding. Despite these advancements, capturing the global network evolution states within acceptable time complexities remains formidable challenge.
Von Neumann Entropy of Static Graph. Von Neumann graph entropy serves a pivotal descriptor of a network system's ' statistical state [ [6. 17). Researchers like De Domenico et al. [5] have employed von Neumann graph entropy for structural reduction in multiplex networks, showcasing its versatility. Li et al. [II] explored convergence using von Neumann entropy in the context of network- ensemble comparison, illuminating its potential applications. Moreover, Liu al. 13 delved into universal patterns of the dynamic genome through von Neumann graph entropy, broadening the scope of its utility. Wang (33 took different route by approximating von Neumann graph entropy with node degrees, effectively modeling network evolution. Despite these endeavors, the application of von Neumann entropy representing temporal structures has remained largely unexplored. To the best of our knowledge, our work pioneers the incorporation of von Neumann entropy in temporal network representation learning, opening new avenues for research and exploration in this domain.
Conclusion
In this paper, we propose ESSEN, evolution states network for recognizing and analyzing the evolution states in temporal networks. We addressed the limitations of existing methods in capturing the time-varying nature of network structures, especially in complex evolution states. Our framework incorporates a von Neumann entropy aware attention mechanism and network evolution state contrastive learning for graph encoding. The decoding stage utilizes unique decoder referred to as the Mixture of Thermodynamie Experts (MoTE). We evaluated ESSEN on link prediction tasks under transductive and inductive settings and compared experimental results demonstrate the effectiveness of our proposed method in capturing temporal dynamics where it outperforms existing approaches. Our work contributes to advancing the field of temporal network analysis and opens up possibilities for future research in both alternative domains and under additional network dynamics. In the future, we will focus on improving ESSEN's efficiency and scalability, allowing to handle larger datasets and real-time analysis.
state-of-the-art baselines. The
10

---

Acknowledgments
This work is supported by the National Natural Science Foundation of China (62176227, U2066213); the Fundamental Research Funds for the Central Universities (20720210047) We would like to thank the anonymous reviewers for their kind comments and valuable suggestions.
References
[1] Jeff' Alstott, Sinisa Pajevic, Ed Bullmore, and Dietmar Plenz. Opening bottlenecks on weighted networks by local adaptation to cascade failures. Journal of Complex Networks, 3(4):552-565, 2015.
[2] Kartik Anand, Dmitri Krioukov, and Ginestra Bianconi. Entropy distribution and condensation in random networks with given degree distribution. Physical Review E, 8966):028077, 2014.
[3] Samuel L Braunstein, Sibasish Ghosh, and Simone Severini. The laplacian of graph a density matrix: basic combinatorial approach to separability of mixed states. Annals of Combinatoricx, 10(3):991-317, 2006.
[4] Sudhanshu Champuriya, Ryan Rossi, Sungchul Kim, Tong Yu, Jane Hoffswell, Nedim Lipka, Shunan Guo, and Cameron Musco. Direct embedding temporal network edges via time-decayed line graphs. In ICLR, 2022.
[5] Manlio De Domenico, Vincenzo Nicosia, Alexandre Arenas, and Vito Latora. Structural reducibility of multilayer networks. Nature communications, 6(1):1-9, 2015.
[6] Ming Jin, Yuan-Fang Li, and Shirui Pan. Neural temporal walks: Motif-aware representation learning on continuous-time dynamic graphs. In NewrIPS, 2022.
[7] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2016.
[8] Srijan Kumar, Bryan Hooi, Disha Makhija, Mohit Kumar, Christos Faloutsos, and VS Subrahmanian. Rev2: Fraudulent user prediction in rating platforms. WSDM, pages 333-341. ACM, 2018.
Srijan Kumar, Francesca Spezzano, VS Subrahmanian, and Christos Faloutsos. Edge weight prediction in weighted signed networks. In ICDM, pages 221-230. IEEE, 2016.
[10] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. SIGKDD. ACM, 2019.
[11] Zichao Li, Peter Mucha, and Dane Taylor. Network-ensemble comparisons with stochastic rewiring and von neumann entropy. SIAM journal on applied mathematics, 78(2):897-920, 2018.
[12] David Liben-Nowell and Jon Kleinberg. The fink-prediction problem for social networks. Journal of the American society for information science and technology, 58())1019-1031, 2007.
[13] Sijia Liu, Pin- Yu Chen, Alfred Hero, and Indika Rajapakse. Dynamic network analysis of the 4d nucleome. bioRxiv, page 268318 18, 2018.
[14] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning graphs and manifolds using mixture model cnns. In CVPR, pages 5115-5124, 2017.
[15] Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-time dynamic network embeddings. In WWW, pages 969-976, 2018.
[16] Filippo Passerini Simone Severini. The von neumann entropy of networks. Availuble at SSRN 1382662. 2008.
[17] Filippo Passerini and Simone Severini. Quantifying complexity in networks: the von neumann entropy. International Journal of Agent Technologies and Systems (IJATS), 1(4):58-67, 2009.
[18] Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. In NewrlPS, volume 33, pages 19716-19726, 2020.
[19] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bron- stein. Temporal graph networks for deep learning dynamic graphs. In ICLR, 2020.

---

[20] Amauri Souza. Diego Mesquita, Samuel Kaski, and Vikas Garg. Provably expressive temporal graph networks. Advances in Neural Information Processing Systems, 35:32257-32269, 2022.
[21] Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representa- tions over dynamic graphs. In ICLR, 2019.
[22] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances neural information processing systems, 30, 2017.
[23] Jianjia Wang, Statistical Mechanics for Network Structure and Evolution. PhD thesis, University of York, 2018.
[24] Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In ICLR, 2021.
[25] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. ICLR, 2020.
[26] Cheng Ye. Entropic characterization and time evolution complex networks. PhD thesis, University of York, 2016.
[27] Cheng Ye, Richard Wilson, César H Comin, Luciano da F Costa, and Edwin Hancock. Approximate von neumann entropy directed graphs. Physical Review E, 89(5):052804, 2014.
[28] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances neural information processing systems, 31, 2018
[29] Lekui Zhou, Yang Yang. Xiang Ren, Fei Wu, and Yueting Zhuang. Dynamic network embedding by modeling triadic closure process. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
12

---

A Additional Algorithm Details
A.1 The Derivation of Approximate Von Neumann Entropy Temporal Network
In the following, We commence by summarizing the approximation of the undirected graph Neumann entropy presented by [27]. First, we introduce von Neumann entropy, which can computed from normalized Laplacian spectrum as follows:
Svx(G) - Tr(Plog P)
Σ
log
A [V
(19)
1=1
where AI,...., Al are the eigenvalues combinatorial Laplacian matrix. Scaling the normalized Laplacian The eigenvalues of the density matrix is
matrix by the reciprocal of its trace. we obtain density matrix A pM......
&
( (M.M......
X and thus the von Neumann entropy of density matrix associated with the normalized M
Laplacian matrix of the graph defined
I
Svv(G)
(20)
The Neumann entropy above relies the computation of the normalized Laplacian spectrum, therefore its computational complexity is cubic in the number of nodes. The Taylor expansion for In As
TVT is
3
+
(21)
we keep the first item expansion and discard remaining that contribute small amount, & In a is approximated using (M -1). Then the entropy Suv(G) can be replaced by the quadratic entropy
Σ, N (1 A²). then we obtain
R
Siv(G)
V
V
(22)
A1
1
Σ
x
V
Using the fact that Tr [ E, 25. the quadratic entropy can be rewritten
T:L
Tr
f.2
Swv(G)
(23)
V
IV
The normalized Laplacian matrix L has unit diagonal elements. For the trace of the normalized Laplacian matrix we have
Tr [ = [V].
(24)
Similarly, for the trace of the square of the normalized Laplacian, we have
Tr i2 ΣV
Σ
Luw ΣΣ>
(Lwe)
NEV
veV
v
VEV
(25)
Σ
(Lwv)
Σ (Lw))
= Σ
du
M VREE
U sight
(u,y)Ee
Substituting Eq
and Eq 25
into Eq
23
the entropy becomes
Sw(()
T
?
V
V VP
Σ (u.v)Ee
E
Σ
(26)
V.d,d,
V
(u.u)Ee d.d,,
We project the temporal network to the time-independent 2-D plane as an edge-weighted graph, resulting in a simplified depiction of the underlying network structure a given time. As result, The expression of the approximate entropy is quadratic the number of nodes.
13

---

Table 3: Performance of AP(%) for link prediction. The best results in each column are highlighted in bold font and the second-best results are underlined.
Task
Methods
MathOverflow
BitcoinAlpha
BitcoinOtc
Wikipedia
JODIE
84.95 =0.43
00.32=0.11
91.50 #0.19
92.95 #2.27
DyRep
80.97 #0.25
79.42
78.95 #2.76
94.63 #0.20
TGN
81.51 #1.73
86.47 #0.42
88.76
98.52 #0.09
TGAT
74.35 #0.29
79.18 #0.54
79.53 +0.84
93.18 #0.13
Transductive
CAW
61,40 #0.28
71.27 #0.87
79.29 #0.76
98.82 #0.12
TDLG
82.87 #0.16
#0.24
92.24 #0.25
87.25 #0.15
Ne
93.07 #0.54
94.14 #0.24
96.17 #0.08
96.01 #0.52
Ours
98.60 +0.26
99.06 +0.20
98.83 #0.47
99.04 +0.26
JODIE
68.58 #0.49
75.02.0022
77.44 #0.14
89.33
#5.04
DyRep
65.65 #0.44
66.54 #1.04
65.94 #0.86
91.94 #0.27
TGN
07.04+1.44
70.52
#1.21
97.83 #0.16
TGAT
62.77 40.64
40.88
68.32
94.18 #0.43
Inductive
CAW
64.79 #0.31
70.90
78.21 #0.29
99.11 #0.13
TDLG
70.18 #2.16
43.59
80.95 #6.88
53.47 #2.41
Ne
92.68 #0.40
90.16
96.44 #0.34
96.12 #0.22
Ours
98.41 #0.17
97.91 #0.69
98.55 +0.33
98.83 #0.10
B
Additional Experimental Results
B.1
Performances in Average Precision
Table reports the detailed transductive inductive link prediction results of AP.
B.2 Time Comparison
Fig. 6
compares the training times of ESSEN against the second-stronges baseline NeurTWs. For fairness,
the same batch size for both models and experiment in the same environment. Note that the running time of ESSEN down quickly because the approximate thermodyyamic quantities have been computed the first epoch and use cache after that.
50
Runving Tmeemv
15
Epectte
Figure 6: Time Comparison
C Experimental Setting
C.1 Datasets
We introduce datasets used in this paper as follows. Fig. 7 report degree distribution on the 30th Day and 270th Day in datasets BitcoinOTC and MathOvertlow. In order to align the timestamps, we shift the time that they begin with zero. Additionally, we renumber the nodes to optimize space usage. Further details regarding the preprocessing steps undertaken prepare these datasets for method are discussed below.
14

---

283
253
254
283-
180
549
27
(a) MathOverflow: 30th Day
(b) MathOverflow: 270th Day
30.-
790
118
192
599
290
39
Mode
Sane Dagin
(c) BitcoinOTC: 30th Day
(d) BitcoinOTC: 270th Day
Figure 7: Degree distribution at the 30th Day and 270th Day in different networks.
MathOverflow dataset It a temporal network of interactions on the stack exchange wehsite Math Overflow. The nodes represent users, and the edges represent the answers questions. For example, directed edge (u, v. represents node features are not provided, we use the all-zero vectors instead.
answered user v's question at time Since edge features and
BitcoinOTC dataset is who-trusts- whom network people trade using Bitcoin on coinOTC platform. Each line records trade from rater to rate and the rating ranges from -10 to +10 in step 1.
Bitcoin Alpha dataset It is similar network to the Bitcoin Alpha platform. Both of the datasets initialize them all-zero vectors.
have edge features node features,
month. We the top-edited pages and active users as nodes, each row our represents a user editing a page. This dataset records user editing of pages over the course a month. The timestamp indicates the time when the user edited the page. As with the Reddit datasct, the features of these nodes were processed through LIWC. The user labels indicate if users temporarily banned from editing.
Wikipedia dataset It is dataset of edited records from Wiki pages
C.2 Baselines
introduction baselines and their setting details are shown as follows. Baselines not specially mentioned use the default settings of the cited paper.
JODIE
recurrent neural networks (RNNs) to learn trajectories of users and items, and updates the embedding when interaction occurs. we set the number of epochs 50 and the dimensions of node and time embedding to 100.
DyRep is temporal point process model capturing both topological evolution and nodes' activities. set the number of epochs to 50 and the patience for early stopping to 5.
TGAT utilizes self-attention mechanism and presents novel encoding method to learn graph embedding inductively. The batch size is 200 and the number of epochs is 50. We the dimensions node and time embedding to 100 and neighbors are sampled aggregation.
3 "htps://ssapsstanniii http:pppssttaoo.ddddasaeeo www.afoor..du//aa////ss-spppeepp hww.:b/uwwwwansiiiiiiiitoooooooo wwt.ooiiotooo.tttiinei
https:///naapssaafoortro wwtp://aaatt/eeeiiinniiiiieeeeee wiw.ggg---itoiitallee attooin-llphahhe
http::/ssaap.. stanford.co stantoondedu/joddddiiiiiii edu/jodie/wikipeeia.co
15

---

TGN is generic and efficient framework for deep learning dynamic graphs for discrete representa- tion. We the number of runs 10 in experiments. The max number of sampling neighbors to and two heads are used in attention layer. The dropout probability is 0.1 and learning rate is 0.0001.
CAW utilizes anonymization strategy represent temporal network inductively. We the dimension the positional embedding 108, batch to 64, and bias 1e-5. The maximum number of neighbors when sampling is 64.
TDLG constructs line graphs to model edges directly instead of computing from node embedding. We discard the attributes of the Wikipedia dataset because the original module could process data with attributes.
NeurTWs improves the causal anonymous walks strategy in CAW and considers structural and tree traversal properties in the process of walking. The dimension of position embedding 108 and 32 neighbors are sampled for each node. The temporal bias, spatial bias, and ee bias are to 1e-5, and respectively.
16


Reviews:
[{"review_id": "IzfIwePWtq", "reviewer": "Reviewer_w7vF", "summary": "The authors propose a novel method on performing inference tasks on dynamic network structures. Differentiating from previous literature, the proposed method capitalizes on the Von Neumann entropy, which provides a set of indicators about the structural symmetries. \n\nIn combination with a quadratic approximation of the Von Neumann entropy, the authors utilize expressions of the thermodynamic temperature differences, in order to create representations of the evolution states of the temporal network. Given the computed representations, the authors propose a decoder based on a mixture of thermodynamic experts, specifically the Von Neumann entropy of the original graph, the Von Neumann entropy of the virtual node graph, and the thermodynamic difference between the two networks. \n\nThe experimental study showcases a very strong performance of the proposed ESSEN model, that outperforms (by a large margin in several tasks) the baselines. However, unfortunately I was not able to assess the reproducibility of the results, since no code has been provided until the time of the present review.", "questions": "- How the approximation of Von Neumann entropy impacts the exact entropy computation? How would be the representations of the dynamic networks would look like given the actual entropy terms?", "limitations": "No limitations of the proposed method are discussed. No discussion on potential negative societal impact is discussed. ", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The experimental results suggest a very strong performance of the ESSEN model.\n- The idea of combining Von Neumann entropy of original and virtual node graph in combination with the thermodynamic difference seems very interesting and can provide some insights on temporal networks.", "weaknesses": "- The authors do not provide any clear theoretical indication of the contribution of Von Neumann entropy for representations of dynamic networks.\n- It would be really helpful for the community, that by the time of rebuttal the code for the reported results is published.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the careful reading and helpful comments. Our anonymous code link is provided in the official comment for Area Chairs.\n\n**1)\tTheoretical indication of the contribution of Von Neumann entropy for representations of dynamic networks.**\n\nVon Neumann entropy has shown its efficacy for network characterization in the static graph [1]. Our work innovatively introduces von Neumann entropy as a framework for analyzing evolution states. Analyzing evolution states is crucial for the model to better fit network link development law. \n\nThe link prediction probability  $P(u,v|G(t))$  is influenced by the network evolution state at time $t$, and the evolution state can vary as the graph's structure changes over time. Von Neumann entropy measures the global uncertainty or randomness associated with a given network evolution state. In the context of link prediction, this uncertainty arises from the various factors that influence whether a link will be established, including past interactions and structural changes in the network. As the network evolves, new information is introduced through the formation of new connections, while existing connections may become obsolete or less relevant. Von Neumann entropy quantifies the information within the temporal network at different time points, shedding light on the information acquisition or loss rate by capturing $\\sum_{(u, v) \\in E} \\frac{1}{d_u d_v}$ in the approximate expression. In the revised manuscript, we will add more details about the theoretical indication of the von Neumann entropy's contribution and make it more straightforward.\n\n[1] : Passerini, F., Severini, S.: Quantifying complexity in networks: the von Neumann entropy. International Journal of Agent Technologies and Systems (IJATS) 1(4), 58–67 (2009)\n\n**2)\tHow the approximation of von Neumann entropy impacts the exact entropy computation?**\n\nFirst, the exact von Neumann entropy is defined as\n\n$$\nS_{\\textit{VN}}(G)=-\\sum_{j=1}^{|V|} \\frac{\\hat{\\lambda}_j}{|V|} \\ln \\frac{\\hat{\\lambda}_j}{|V|},\n$$\n\nwhere $\\hat{\\lambda}\\_{1}$, $\\ldots $, $\\hat{\\lambda}\\_{|V|}$ is eigenvalues from normalized Laplacian matrix. And the Taylor expansion for $\\ln \\frac{\\hat{\\lambda}_j}{|V|}$ is \n\n$$\n% \\begin{split}\n \\left(\\frac{\\hat{\\lambda}_j}{|V|}-1\\right)-\\frac{1}{2}\\left(\\frac{\\hat{\\lambda}_j}{|V|}-1\\right)^2+\\frac{1}{3}\\left(\\frac{\\hat{\\lambda}_j}{|V|}-1\\right)^3- \n \\frac{1}{4}\\left(\\frac{\\hat{\\lambda}_j}{|V|}-1\\right)^4+\\cdots .\n% \\end{split}\n$$\n\nThe key approximation step is keeping the first item of the Taylor expansion for $\\ln \\frac{\\hat{\\lambda}_j}{|V|}$ and discarding the remaining that contribute to a small amount. $\\ln \\hat{\\frac{\\lambda_j}{|V|}}$ is approximated using $\\left(\\frac{\\hat{\\lambda}_j}{|V|}-1\\right)$, which holds well when $ \\hat{ \\frac{\\lambda_j}{|V|}} $ is close to 0 or 1. Then we obtain\n\n$$\n\\begin{equation}\n\\begin{split}\n S_{\\textit{VN}}(G)&=-\\sum_j \\frac{\\hat{\\lambda}_j}{|V|} \\ln \\frac{\\hat{\\lambda}_j}{|V|} \\simeq \\sum_j \\frac{\\hat{\\lambda}_j}{|V|}\\left(1-\\frac{\\hat{\\lambda}_j}{|V|}\\right)\n =\\frac{1}{|V|} \\sum_j \\hat{\\lambda}_j-\\frac{1}{|V|^2} \\sum_j \\hat{\\lambda}_j^2 .\n\\end{split}\n\\end{equation}\n$$\n\nThe expression allows us to be expressed in terms of the node degree combinations on edges of the graph in the next steps and by computed with quadratic complexity. In the appendix, we provide the total derivation of approximate von Neumann entropy on the temporal network. \n\n**3)\tHow would be the representations of the dynamic networks would look like given the actual entropy terms?**\n\nGraphs with low entropy tend to be tree-like or string-like and have more low-degree nodes. Those with high entropy have high-degree nodes and tend to be fully connected. We provide analysis figures about von Neumann entropy and structure evolution process in the attachment PDF."}, {"review_id": "kP9wzIUgGa", "reviewer": "Reviewer_oGt7", "summary": "The paper presents a new framework called ESSEN (Evolution StateS awarE Network) to measure the evolution of temporal networks using von Neumann entropy and thermodynamic temperature difference. Existing methods struggle to handle the time-varying nature of these networks, hindering their performance on complex evolving states. ESSEN utilizes an entropy-aware attention mechanism, contrastive learning, and a unique decoder called MoTE to improve recognition of network evolution states, showing effectiveness in link prediction tasks compared to state-of-the-art methods.", "questions": "What is Von Neumann Entropy?\nWhy Von Neumann Entropy?\n", "limitations": "na", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Clear motivation and problem statement.\nInnovations by integrating domain knowledge in biological study to GNN.\n", "weaknesses": "Some core concepts required domain specific knowledge to fully understand, but these concepts are not clearly defined, such as Von Neumann Entropy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading, positive comments, and constructive feedback. \n\n**1)\tWhat is Von Neumann Entropy?**\n\nIn the revised manuscript, we will add more details about the definition of von Neumann entropy. Von Neumann entropy is a concept in quantum information theory. In the quantum context, Von Neumann Entropy quantifies the uncertainty associated with the state of a quantum system. This idea has been extended to the static graph domain. \n\nSpecifically, the von Neumann entropy is computed from the density matrix for the states of the system under study. the density matrix is used to describe systems whose state is a mixture of pure quantum states $\\left|\\psi_i\\right\\rangle$, each with probability $p_i$. The density matrix is defined as\n\n$$\n\\rho=\\sum_{i=1}^{|{V}|} p_i\\left|\\psi_i\\right\\rangle\\left\\langle\\psi_i\\right|,\n$$\n where $|{V}|$ is the number of node set. When defined in this way, the density matrix is Hermitian, i.e., $\\rho=\\rho \\dagger$, $\\rho \\geq 0$, and Tr[$\\rho$] = 1. $\\dagger$ represents conjugate transpose. It plays an important role in the quantum observation process, which can be used to calculate the expectation value of measurable quantities. The von Neumann entropy is given by $S_{\\textit{VN}}{(G)}=-\\operatorname{Tr}(\\rho \\log \\rho)$. \n\nFor the graph domain, a density matrix for a graph or network can be obtained by scaling the combinatorial Laplacian matrix $\\tilde{L}$ by the reciprocal of the number of nodes in the graph, i.e., $\\rho=\\frac{\\tilde{L}}{|{V}|}$.\n\nThe interpretation of the scaled normalized Laplacian as a density operator opens up the possibility of characterizing a graph using the von Neumann entropy. With the definition of the density matrix adopted by Severini et al., the von Neumann entropy can be computed from the normalized Laplacian spectrum as follows:\n$$\nS_{\\textit{VN}}{(G)}=-\\operatorname{Tr}(\\rho \\log \\rho)=-\\sum_{i=1}^{|{V}|} \\frac{\\hat{\\lambda}_i}{|{V}|} \\log \\frac{\\hat{\\lambda}_i}{|{V}|},\n$$\nwhere $\\hat{\\lambda}\\_1$, $\\ldots $, $\\hat{\\lambda}\\_{|V|} $ are the eigenvalues combinatorial Laplacian matrix. This form of von Neumann entropy has been shown to be effective for network characterization. \n\nThe approximation form of von Neumann entropy also has shown its efficacy for network characterization in the static graph.\n\n**2)\tWhy Von Neumann Entropy?**\n\nVon Neumann entropy is effective for network characterization. As we discussed in our manuscript, von Neumann entropy is applied to describe the quantum statistics [1] and measure network irregularity [2] in a network system. It offers a novel method to study the properties of pure states and mixed quantum states [3]. Von Neumann entropy measurements play a crucial role in understanding network systems' structural and topological complexity. The ability of von Neumann entropy to capture information content aligns well with the changing nature of temporal networks. This information-theoretic perspective enhances our understanding of the network's evolution laws and capacity to transmit and store information over time. \n\n[1] Passerini, F., Severini, S.: Quantifying complexity in networks: the von Neumann entropy. International Journal of Agent Technologies and Systems (IJATS) 1(4), 58–67 (2009)\n\n[2] Passerini, F., Severini, S.: The von Neumann entropy of networks. Available at SSRN 1382662 (2008)\n\n[3] Anand, K., Bianconi, G., Severini, S.: Shannon and von Neumann entropy of random networks with heterogeneous expected degree. Physical Review E 83(3), 036109 (2011)\n\n**3)\tSome Concepts like von Neumann Entropy need to be more clearly defined.**\n\nIn the revised manuscript, we will add more details about the entropy concepts and make it more straightforward."}, {"review_id": "YuKsaRSbiw", "reviewer": "Reviewer_jRZR", "summary": "The authors work on temporal graph representation learning that faces two challenges: (1) the diversity of the evolving patterns and their time-varying nature are hard to model; (2) high computational cost for structure recognization with increasing numbers of nodes and edges.\n\nThe authors propose to overcome the problems by incorporating the approximate von Neumann Entropy and approximate thermodynamic temperature difference into the design of temporal graph learning modules. The effectiveness of the proposed method is validated by the link prediction task on different datasets.\n\nUpdate after rebuttal:\nThe authors have addressed my concern through the rebuttal. The score remains unchanged.", "questions": "1. Can the authors provide some intuitive explanations for the quantities $\\mathcal{J}(G)$ and $\\mathcal{K}(G)$ defined in Eq. (6) and Eq. (7), respectively?\n2. In Line 259, the authors say that for large networks, the computational complexity can be reduced from $O(|V|^2)$ to $O(N^2)$, where $|V|$ is the number of nodes, and $N$ is a predefined number to control the budget. Will it make the approximation less meaningful when $N\\ll |V|$?\n3. In Line 329-331, the authors say that pre-computing some thermodynamic quantities can considerably reduce the computational overhead. However, the network evolves over time, and thus these quantities may be updated. Can the authors explain to what extent the pre-computation can reduce the computational cost?\n\nComments:\n1. Please make the colors of the barplot more distinguishable in Figure 3.\n2. It may be inappropriate to place Figure 4 after Figure 5.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is clearly written and easy to follow.\n2. This paper brings the thermodynamic view to temporal graph learning, which may inspire later research.\n3. The approximate von Neumann Entropy and approximate thermodynamic temperature difference are rigorously formulated and derived.\n4. The proposed method significantly promotes the performance of link prediction, and it is computationally efficient.", "weaknesses": "The von Neumann entropy and the graph entropy in the thermodynamic temperature difference are defined on undirected graphs. However, the temporal network can be generically directed. How can the proposed method address this issue?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your careful reading, encouraging remarks, and constructive feedback. \n\n**1)\tThe von Neumann entropy and the graph entropy in the thermodynamic temperature difference are defined on undirected graphs. However, the temporal network can be generically directed. How can the proposed method address this issue?**\n\nIt is a great idea.\n\nTemporal networks are abstract representations that are widely used for real-world dynamic systems. In fact, most research on temporal networks focuses on temporal dynamics and simplifies the networks as undirected ones including the state-of-the-art baseline methods (TGAT, TGN, CAW, and NTW). Following these methods, we preprocess the network as undirected for a fair comparison.\n\nOur network can feasibly be covered to a directed one. Specifically, if replacing the undirected degree matrix with an out-degree or in-degree matrix when computing the Laplacian matrix, the computation of von Neumann entropy and the thermodynamic temperature difference can be converted with directionality naturally. Thus, further inclusion of directionality in the study is reasonable and has excellent theoretical potential. We will investigate this deeply in the future.\n\n\n**2)\tCan the authors provide some intuitive explanations for the quantities $\\mathcal{J}(G)$ and $\\mathcal{K}(G)$ defined in Eq. (6) and Eq. (7), respectively?**\n\n  $\\mathcal{J}(G)$ and  $\\mathcal{K}(G)$ can be explained as the probabilities of a random walker traversing specific edges or cycles in the graph when starting a random walk on the graph. They are the statistics about network structures.\n\n**3)\t In Line 259, the authors say that for large networks, the computational complexity can be reduced from $O(|V|^2)$ to $O(N^2)$, where $|V|$ is the number of nodes, and $N$ is a predefined number to control the budget. Will it make the approximation less meaningful when $N\\ll |V|$?**\n\nThe link prediction performance decreases when $N\\ll |V|$. To quantify the extent of the impact, we provide a parameter sensitivity analysis of $N$ in the manuscript. The total node number of the MathOverflow dataset is 21688, which is also the max value of $|V|$ because the node will add and delete over time. We vary $N$ in the set of \\{50,100,150,200,250\\}. The AUC results of MathOverflow fluctuate between 95.43% and 98.56%. The result presents a promising trade-off between computational efficiency and the loss of information due to sampling in actual applications. \n\n**4)\t In Line 329-331, the authors say that pre-computing some thermodynamic quantities can considerably reduce the computational overhead. However, the network evolves over time, and thus these quantities may be updated. Can the authors explain to what extent the pre-computation can reduce the computational cost?**\n\nIn Line 329-331, the cost which can be reduced is the neighborhood search and the computation of von Neumann entropy in the first epoch of the training. The history structure of the temporal network is fixed. If the adjacency list is sorted by time, it costs $ O(logD)$ to search the neighbors of the node at time $t$, where $D$ is the degree of nodes. Given a test node pair $(u,v,t)$, neighbor search totally costs $O(K^l\\times logD)$, where $K$ is the number of neighbors in the neighborhood aggregation process and $l$ is the number of neighborhood aggregation layer. Moreover, it takes $O(N^2)$ in the computation overhead of von Neumann entropy and thermodynamic temperature difference. We hash the test node pair $(u,v,t)$ as key and its neighborhood tree and thermodynamic quantities as value and make these costs reduce to $O(1)$ after the first epoch. After training, the model stores the hash table. If pre-computing the thermodynamic quantities and saving the hash table as the cache files, the training will be faster when loading the hash table directly rather than building it in the first step. \n\n**5)  The comment for figures.**\n\nWe will follow the figure suggestion about the colors and position in the revised manuscript."}]

Author rebuttal:
We sincerely thank all the reviewers for dedicating their valuable time and providing insightful comments. We are greatly pleased to receive some positive reviews. Specifically, we appreciate that they find our work is novel (w7vF), well motivated (oGt7), inspiring (jRZR), well presented (jRZR), and with promising experimental results (w7vF, jRZR). We will incorporate the suggestions and address the concerns in the revision. 

To the best of our efforts, we have provided detailed responses to address the concerns raised by each reviewer. Specifically, the primary responses are outlined below:

- We provide the figures of the connection between network structure change and von Neumann entropy.

- We introduce the von Neumann entropy definition more comprehensively.

- We elaborate on the contributions of von Neumann entropy to network representation learning.

- We precisely explain how the approximation process impacts the computation of von Neumann entropy.

- We provide more details of our method, which include providing more insights into thermodynamic parameters $\mathcal{J}(G)$ and $\mathcal{K}(G)$, conducting an in-depth analysis of the relation between $|V|$ and $N$, elucidating the efficacy of pre-computation, and discussing the extensibility for the directed dynamic graph.

Moreover, we would like to emphasize our motivation:

- Von Neumann entropy measurements play a pivotal role in comprehending the structural and topological intricacies of network systems. Its efficacy in network characterization has been well-established. The ability of von Neumann entropy to capture information content aligns well with the changing nature of temporal networks. To the best of our knowledge, research has yet to explore the application of von Neumann entropy in the context of temporal networks. Our work pioneers the extension of approximate von Neumann entropy to temporal networks, aiming to stimulate future research in this area.

- The accurate and adaptive evolution state estimation is paramount for link prediction on temporal networks. By expanding von Neumann entropy to temporal networks, we aim to mitigate the following problems in evolution state estimation: a) Different networks exhibit substantial variations in their evolution laws. Moreover, the evolution states may change over time within the same network. b) Temporal networks accumulate increasing nodes and edges as time progresses, leading to a rapidly expanding neighborhood for each node.

Meta-review: Overall, all three reviewers provide a "Weak Accept" rating for the submission, indicating that it is technically solid with moderate-to-high impact but may have some concerns or areas for improvement. Reviewer w7vF expresses concerns about reproducibility and the theoretical underpinnings of the method, while Reviewer oGt7 notes the need for better clarification of core concepts. Reviewer jRZR raises specific questions about how the method handles directed graphs and computational efficiency, which the authors have addressed in their rebuttal.
Decision: Accept (poster)