Quantum-Inspired Tensorized Embedding with Application to Node Representation Learning
Authors: Hao Xiong
Yehui Tang
Wei Tan
Yunlin He
Junchi Yan
Venue: Submitted to ICLR 2023 (2023)
Keywords: network embedding
node representation learning
quantum mechanics
tensorized embedding

Abstract: Node representation learning a.k.a. network embedding (NE) is an essential technique for network analysis by representing nodes as vectors, which also serves  downstream tasks or as initial input for GNN models. Most of existing NE algorithms require a space complexity linear to the multiplication of the number of nodes and embedding dimension to store embeddings. Such a conventional embedding paradigm has two defects: i) it brings challenge to the deployment of NE algorithms for large-scale networks on devices of limited memory/storage space; ii) model expressiveness is constrained due to the limited embedding dimension. Impressed and inspired by the large Hilbert space of quantum systems, we propose a brand new NE algorithm \emph{node2ket} by imitating behaviors of quantum systems. Theoretically, we give analysis on how it unifies existing embedding methods including both conventional ones and tensorized ones, and explore the ultimate compressive power of the embedding model on the space complexity compared with conventional ones. Experiments are conducted on five public real-world networks where methods are evaluated through tasks of network reconstruction and link prediction. On BlogCatalog, our method achieves to outperform all baselines with 1/32 training parameters and 1/16 running time on the same machine. On DBLP, the reconstruction precision of node2ket achieves to be 3 times higher than the best  baseline i.e. LouvainNE. Source code will be made publicly available. 

Under review as a conference paper at ICLR 2023
QUANTUM-INSPIRED TENSORIZED EMBEDDING WITH APPLICATION TO NODE REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Node representation learning a.k.a. network embedding (NE) is an essential tech- nique for network analysis by representing nodes as vectors. Most existing NE algorithms require a (p) space complexity for each node embedding (p is the final embedding vector size). Impressed and inspired by the large Hilbert space of quantum systems, we propose brand new NE algorithm node2ker and its vari- ant node2kek+ by imitating behaviors of quantum systems. Theoretically, we give analysis on how unifies existing embedding methods including both con- ventional ones and tensorized ones, and prove that our methods achieve to use (p In p) or even smaller space for each node embedding. We are the first to successfully conduct node embedding in the super large Hilbert space, Ex- periments are conducted on five public real-world networks where methods are evaluated through the tasks of network reconstruction, link prediction, and node classification. On BlogCatalog, with 1/32 training parameters and 1/16 running time on the same machine. On DBLP, the reconstruction precision of node2ket achieves be 3 times higher than the best baseline i.e. LouvainNE. The source code will be publicly available.
method achieves to outperform all baselines
Hilbert space is a big place!
Carlton Morris Caves.
INTRODUCTION
Node representation learning. also known as network embedding (NE), has been well-studied in decades. Borrowing idea from word embedding in NLP, deepwalk (Perozzi et al., 2014) first proposes to learn node embeddings for downstream tasks by feeding random walk sequences to word2vec (Mikolov et al., 2013). Afterward, numerous NE methods for different types of networks (e.g. beterrogeneoussmuliipeee networks) and for different purposes (e.g. preserving structural sim- ilarity) are proposed (see Sec. 2 for more). Despite the great success, the existing NE methods still suffer from the high space complexity for storing/training the embeddings whose size grows linearly to the multiplication of the number nodes and the embedding dimension (Xiong et al., 2022) (see memory-
Appendix A for details). As result, there is difficulty in deploying these methods limited devices for privacy-sensitive computing e.g. recommender systems in social networks on mobile phones. Meanwhile, the expressiveness of the embedding vectors can be restricted.
Recently, inspired by quantum mechanics, word2ket (Panahi et al., 2020) was proposed for com- pressive word embedding by imitating the behaviors of quantum bits in quantum systems. By tensor entanglement, word2ket achieves both a high compressive ratio and experimental results comparable to conventional embeddings. Though providing many insights generating embeddings, word2ket still faces difficulties transferring to embedding problems in other fields such as node representation learning (Hamilton al., 2017b). These difficulties include: i) Word2ket generates embeddings from a fixed complete binary tree, which neglects the latent structure of the input data and hence brings challenges to learning embeddings for data with explicit structures (e.g. networks). ii) Word2ket adopts deep neural networks to decode the embedding and is trained in supervised way, which rather different from many embedding methods (Tang et al., 2015; Grover Leskovec, 2016) that decode embeddings via simply inner product operation and train embeddings by optimiz- ing the objective based on Noise Contrastive Estimation (NCE) (Gutmann & Hyvärinen, 2010) in a self-supervised (contrastive learning) style.

---

Under review as a conference paper at ICLR 2023
In this paper, we propose novel network embedding paradigm with special treatments concern- ing the above two problems. For the embedding generation, we propose an embedding module named as Tensorized Embedding Blocks (TEBs) composed of columns of Tensor Units (TUs), each representing an embedding tensor. TEBs can unify the embedding layers in by making changes in the way of indexing TUs (see Sec. 4.1 and Sec. 4.5). A good strategy of ass signing TU indices to the embedded nodes will result in a model with both high expressiveness and space efficiency, which is proved by the experiments. For the embedding learning, we optimize the widely adopted NCE-based objective and succeed in learning node embeddings in a 2 -dimensional Hilbert space stably and robustly on single machine (details Sec. 4.2). Specifically, we propose two variants on different compressive levels, named as node2ket and node2ke(+. The former is preliminary baseline and the latter is more compressive by utilizing graph partition techniques. Fur- thermore, we give a complexity analysis of the embedding modules in TEBs, and theoretically prove an upper bound of the minimum of the required space to store/train embeddings for node2ket and node2ket+ in Sec. 4.3 and Sec. 4.4 respectively. Our contributions are listed as follows:
1) We are the first to formalize a general embedding architecture, Tensorized Embedding Blocks (TEBs), which generate embeddings in Hilbert space by tensor product and entanglement, imitating behaviors of quantum systems. In this way, high sigh-dimensional embeddings of high expressiveness in the Hilbert space can be obtained via small number of parameters. Our tensorized embedding architecture is a generalization of the recent method word2ket/wor22ketXS and also unifies conven- tional embedding methods.
2) We take an initiative (the first time to our best knowledge) to adopt tensorized node embedding in representation learning based on Noise Contrastive Estimation. Specifically, we propose two variants at different compressive levels, node2ket and node2ket+, with the bound of compressive power proved respectively. Compared with the preliminary baseline node2ket, node2ket+ further utilizes graph partition techniques in the design of TEBs, in which way features on different levels of granularity are preserved and the embedding model becomes more compressive.
3) Experiments on network reconstruction and link prediction show the overwhelming performance of node2ket. Notably, in the network reconstruction experiments, it becomes the top method on BlogCatalog with 1/32 training parameters and 1/16 running time, and the precision on DBLP is more than 3 times higher than the best one of baselines i.e. LouvainNE (Bhowmick et al., 2020).
2 RELATED WORKS
Network Embedding. Here we mainly discuss the NE methods based on the language model word2vec (Mikolov et al., 2013), which are often designed for different types of networks, e.g. homogeneous networks (Perozzi et al., 2014; Grover & Leskovec, 2016; Tang et al., 2015), hetero- geneous networks (Dong et al., 2017) and multiplex networks (Liu et al., 2017: Qu et al., 2017; Xiong et al., 2021). It also often aims to preserve specific types of information, egg. low-order proximity (Tang et al., 2015), structure similarity (Ribeiro et al., 2017), versatile similarity mea- sures (Tsitsulin et al., 2018), and cross-n alignment relations (Du et al., 2022). Apart from NE methods derived from word2vec, methods based on deep neural networks (Wang et al., 2016) especially graph neural networks (Hamilton et al., 2017a) are also influential in literature, which, however, are technically divergent this paper.
Tensorized Embedding Model. Tensors are a generalization of vectors and matrices. Thanks to the capability of representing and manipulating high-dimensional subjects, tensor has been success- fully applied to exploit complex physical systems (Nielsen & Chuang, 2002). The most crucial application understand the quantum many-body systems and to make an efficient description of quantum states residing in the exponential growth of the Hilbert space (Bridgeman & Chubb, 2017) 7).
In addition, tensor networks composed of multiple tensors can also be used to understand many of the foundational results in quantum information (Orús, 2019). Utilizing the tensor network structure makes it reasonably possible to simplify the concept like quantum teleportation, purification, and the church of the larger Hilbert space (Bridgeman & Chubb, 2017). Inspired by this, many tensorized embedding models try to take advantage of tensor operations like contraction and decomposition to handle large volumes of data and compress parameters, ranging from image classification (Stouden- mire & Schwab, 2016; Martyn et al., 2020; Selvan & Dam, 2020; Cheng et al., 2021) to natural language processing (Panahi et al., 2020; Ma et al., 2019; Liu al., 2020; Qiu & Huang, 2015). It
2

---

Under review as a conference paper at ICLR 2023
is anticipated that the tensor concept introduced by quantum physies will give us new perspectives on designing the structure of deep learning models and comprehending the learning capability of artificial neural networks (Levine al., 2017).
3 PRELIMINARIES AND BACKGROUND
3.1 NETWORK EMBEDDING BASED ON NOISE CONTRASTIVE ESTIMATION
Given a network described by the node set V and the edge set E, node representation learning or network embedding aims to represent each node fully explore network structures for different purposes, corpus D is usually created the imput data of embedding training. Typically, can be the edge set (Tang et al., 2015), random walk sequences (Perozzi et al., 2014; Ribeiro al., 2017; Du et al., 2022), etc.
as fixed-length vector x; R". To
Objective Function. Initially, the objective to maximize the following log softmax function:
exp(x x,)
Σ (U))
log
Σ L exp(x, xy.)
where the positive pairs (i,j) are sampled from D. However, Eq. is computationally intractable for a large V, and thus surrogate objectives are proposed, including Hierarchical Softmax and Negative Sampling (Mikolov et al., 2013). In this paper, we only discuss a typical objective based on the widely adopted Negative Sampling:
K
Σ (3)))D
(ogo(xx(x))+ x
Σ By. log o (- ].
A=
pusitive samples
K negative samples for each positive sample
where (Ix) = 1/(1 exp(-r)) is sigmoid function, K' is the number of negative samples for each positive sampled pair, F, is the distribution negative samples j' which is usually set proportional to node degrees.
3.2 QUANTUM MECHANICS AND TENSORIZED EMBEDDING
Quantum Mechanics. Quantum states are usually written in 'bra-ket' notation. In matrix rep- resentations, kets are column vectors denoted as (b) (where the name wordhodeekeet comes) and bras are the conjugate transpose of the kets denoted as (2b). The state of single quantum bit (qubit) (1b) defined in 2-dimensional Hilbert space C2 described by a superposition of two orthonormal basis states [0) = (1, O) and 1) (0, 1). (w)) = ax() + B[1), where 3 E C are probability amplitudes satisfying Ja|2 + 2 1. The state of an N -quubit quantum system is in the Hilbert space & , C2 where @ denotes tensor product. Considering two quantum systems A and B with corresponding Hilbert spaces HA and HB. the composite space of A and B is H = HA & HB- use (Ø) A and (Ø) B denote states of system A and B respectively, then state ()) E H that can be written as (Ø) = (Ø) @ (d) is called pure state, otherwise it is an entangled state.
Tensorized Embedding by Word2ket. Word2ket (Panahi al., 2020) conducts word embedding by imitating behaviors of quantum systems. Embedding of each word is represented as an entangled quantum state in the Hilbert space, which is the summation of several pure state embeddings. A pure state embedding is formed by tensor product between some dimer-dimensional tensors. During the embedding procedure, some simplifications are adopted: i) real vectors are used as embeddings instead of complex ones in the quantum states; ii) the tensor product between tensors is implemented as the Kronecker product between vectors (it does not affect the results mathematically. since vec- special tensor (Bridgeman & Chubb, 2016), and Kronecker product can be
tor can be deemed viewed as a form of vectorization of the tensor product); and iii) when imitating quantum entan- glements, it uses learned tensors but not orthonormal basis states for implementation convenience, which means that a generated entangled state embedding may not be a strictly entangled one. These simplifications are also adopted by this paper.
3

---

Under review as a conference paper at ICLR 2023
Tensor Embedding Blocks (TEBs)
Tensor units Tensor product
C
columns
c(i,c) look-up table
Ra
pure state embedding
block weights K0g1
r(),
B blocks
U 1
entangled state embodding (final
2(1,2)
U
r(4,3)
embedding)
10
X
WALD
((CVVI)
O(B(V)
Bd Re)
Figure I: A toy example to generate embedding from the given tensorized embedding blocks. To get the embedding x,, the first step is to look r(i, c) up from the table the left-hand side, and then pick the tensor units out from the TEBs and calculate the final embedding according to Eq. 3.
TENSORIZED NETWORK EMBEDDING
Sec. 4.1 first introduces how we obtain embeddings from the proposed architecture Tensorized Em- bedding Blocks (TEBs). In Sec. 4.2 we introduce how to train embeddings in TEBs efficiently. Then Sec. 4.3 and Sec. 4.4 we introduce the specific network embedding methods node2ket and node2ket+ respectively. Finally in Sec. 4.5 we discuss the relation of the framework to other embedding methods.
4.1 EMBEDDING VIA TENSORIZED EMBEDDING BLOCKS
Tensorized Embedding Blocks (TEBs). Before introducing how node2ket works, we first propose a novel embedding module named as Tensorized Embedding Blocks. A TEB composed of a certain number of Tensor Units (TUs), and each TU represents an embedding vector in Rd. A TEB has C columns where the e-th column has R. TUs. We denote the embedding vector of the TU located at the r-th row and the e-th column of the b-th block by u
Embeddings Generation. We use B TEBs for embedding generation. Though more freedom can be added to the number of rows {Re] for different TEBs, assume that they the same without losing generality. For node i, we obtain the embedding x, by:
B
X;
WAN
(Lceee
where xf is the pure state embedding in RRdd -dimensional Hilbert space given by the b-th TEB for node i, and was is the corresponding block weight of node on the b-th TEB. The r(i, c) in the subscription of TU embeddings ( indicates that the row index depends on the node and the column index c. For better understanding. we give a toy example of TEBs and how to generate x; according to the given rii,c) c) look-up table as shown in Fig. 1.
Complexity Analysis. There are three parts of parameters: i) the r(i, e) table has OCC))) param- eters, ii) the embeddings of TUs have (Bd Re) parameters, and iii) the block weights have O(B(V) parameters. The used parameters is totally O(Bd DC Re + CIVI + BJV)). For more detailed complexity analysis please refer to Sec. 4.3 and Sec. 4.4.
4.2 MODEL LEARNING
In this section, we show how to efficiently train the generated tensorized embedding by TEBs via updating embeddings directly according to computed gradients, without automatically for- ward/backward propagation most DL models did. In this way, save the computation time/space from ((d)) to Odd.). firstly making learning embeddings the high-ding high-dimensional Hilbert space feasible. Details are put in Appendix C.2, including gradient derivation and the complete algorithm.
4

---

Under review as a conference paper at ICLR 2023
Gradient. During the model optimization, do not need to caleulate the full node embeddings. Instead, we compute the gradient and update TU embeddings directly without complete procedure of forward propagation. Given two embeddings x; and Xz:
B W
x;
wib
r(,c))
xj
and the label I (1 1 for positive samples and I otherwise), have the gradients for TU embeddings according to the objective Eq. 2:
Ölog (2(1, (x.))xx,)))) uNo [1: a( x (i.c)
B 8
Σ
II Lupaerres (5)
c'sc
where 1, is indicator returning if = and otherwise. The gradients for block weights are:
a log o (2 0x,) x,)) [1, ((xi,
C
Σ d=11
Way
[I
(6)
For detailed derivation of the gradients, please see Appendix C.I.
Model Training. We optimize the objective via Asynchronous Stochastic Gradient Descent (Recht et al., 2011) on CPUs as most works in NCE-based embedding (Mikolov et al., 2013; Tang et al., 2015) and the famous open-source library gensim do. Technical details are given Appendix C.2.
4.3 NODE2KET: A PRELIMINARY BASELINE
For node2ket (or namely n2k), we set r(i, c) i constants, and Rí R2 = Rc V/. means we don't need space to store the r(i, c) table. We give a constraint over the embedding dimension d in Assumption 1, according to which we reach Theorem where the ultimate compressive power is analyzed. The proof and further comments are given in Appendix D.
Assumption 1. [Dimensional Assumption] If p-dimensional final embedding is required, the dimension of generaled embedding should not be smaller than i.e. dC 2 pi
Theorem 1. [Compressive Power of Node2ket) Given node set V and the the,final embedding dimen- sion p. when r(i,c) i are constants (indicating R. [VI, S as trainable parameters, the total number of parameters is #params = B(C [V]). Omitting the integer constraints of and C. we obtain the minimum number of used parameters of the whole embedding model as:
C) and use block weights
min #params BIV p la In + B(V.
When the block weights are set as constants, #params = BCIVld, and we have:
min #params = B/V Inp In...
4.4 NODE2KET+: COMPRESSIVE EMBEDDING UTILIZING GRAPH PARTITION
To further compress node2ket, we propose node2ket+ (n2k+) utilizing graph partition techniques. Specifically, we set r(i, c) = Par,(i (i) where (-r is the c-th partition algorithm and Par,(i) returns the index of the partition that node belongs to. In this way, R. equal to the number of partitions given by the function Par.- In the implementation. we use Louvain partition (Blondel et al., 2008) with different settings of resolution as the graph partition algorithm, which is a scalable algorithm aiming to maximize the modularity of the partitions. We control that Rú < Rs S ... Rc. hence the model can extract structure information on different levels of granularity. Theoretically, we further give Assumption 2 over the size of TEBs, and then give bound of the ultimate compressive power of node2ket+ in Theorem 2 based on Assumption and 2. The proof for the following Theorem is presented in Appendix by borrowing the tool of asymptotic analysis (Bender & Orszag, 2013), which is technically nontrivial and new to the network embedding community.
Assumption 2. [Combinatorial Assumption] A TEB should be capable to generate at least [
different pure state embeddings, which indicates IT R. 2 [P]
5

---

Under review as a conference paper at ICLR 2023
Table 1: Differences between word2ket(XS) and node2ket(+)) (no downstream tasks are involved).
Step 2: Embedding Generation
Step 3: Embedding Learning (Distributed Updating)
Step I: Prepare
Decoder
Objective
Scalable
Emb. Dim.
Input Data
word2ket word2ketXS
special case of node2ket
neural networks
supervised
X
80000
input sentences
(unstructured data)
node2ket
flexihly defined
inner
noise contrustive
2
imput links
node2ket+
product
estimation
(structured data)
The dimension 8000" reported in the offciaa paper.
Theorem 2. [Compressive Power of Node2ket+] Given the node set V and the final embedding dimension p. when node2ket utilizes both the r(i, c) table and block weights, the total number of Be parameters is #params Bd e=1 Rg + B[V| + CIV). We obtain the minimum number of used parameters of the whole embedding model:
min #params BBC (plV)) 1/ + +BVI +
where C* C*=
(1nn))))2 [ 1
/1V////+B//// 1). When the block weights are set as [InplV+ Mt
constants, we have:
min #params (D +C*l
4.5 RELATION TO OTHER EMBEDDING METHODS
Relation to Conventional Embedding. When B = - the embeddings of generated by node2ket become x; / where no tensor product or entanglement utilized and the embedding degrades to the conventional embedding. The embedding look-up step in traditional NE methods becomes special case in the corresponding step of node2ket though the training different.
Advantages over Word2ket. A complete network embedding procedure basically has three steps: prepare the input data, ii) generate embedding for the input data, and iii) learn the embeddings. We analyze the advantages of node2ket over word2ket from the three aspects (details in Appendix B.I and see summarization in Table 1).:
i) Node2ket can embed various explicitly structured data beyond sequence. It is achieved by defining r(i, c) to fit the structures input data utilizing graph partition techniques to encode struc- tures of data into TEBs (e.g. by setting ri, = r(j,a c) if node i and belong to the same community node2ket+)), while word2ket can not utilize inherent structures of input data.
ii) Node2ket has better space efficiency due to the flexible definition. Embedding generation modules wordZket/wordDkettXS are special cases of our proposed TEBs by setting Was constant and C 2". The simplification of word2ket reduces the representational ability of the embeddings and also limits the space efficiency of word2ket.
iii) Scalable learning by NCE without explicitly maintaining embedding x,. Node2ket is dis- tributed trained based on the NCE objective Eq. 2. During training, by iteratively updating the embedding uh (i.e)e the process avoids computing the embedding x; and achieves to conduct bedding in the super high-dimensional Hilbert space. In comparison, Word2ket/word2kettx train embeddings in supervised way with an NN decoder, which requires computing the full embedding of x; and hence fails do embedding in nigh-dimensional space. Experimentally node2ket achieves an embedding dimension of 32 (can be indeed more than 2 128 on our machine) while word2ket only reports an 8000 embedding dimension.
EXPERIMENTS
In experiments, investigate downstream tasks including network reconstruction (Sec. 5.2), link prediction (Sec. 5.3), and node classification (Appendix E.6). In Sec. 5.4, we conduct ablation studies investigate the roles of different parts in the model. In Sec.5.5, good parallelizability of the methods is shown. And in Appendix E.5, we further display the overwhelming performance of methods network reconstruction by visualization of the reconstructed results.

---

Under review as a conference paper at ICLR 2023
a) Precision w.r.t. TTriiinn Params
b) Precision w.r.t. Training Time # #pooch))
25
node2kett outpertorms code2vec with 1/64 #treiiing params
25
20
Precision (%)
Precision (%)
outperiatus nodeavec with 1/52 avaining paruma and 1/1 rylning time
15
15
10
10
5
5
0
1
3
4
5
0
50
100 Time (s)
150
Number of Training Parameters
1os
LINE
VERSE
0ode2vcc
sodoZact
ProNE LaunstnNi
Noe SMI
Figure 2: Comparison BC. n2k-8/128 denotes n2k by C=2, d=4 and C=8, d=16 respectively.
5.1 EXPERIMENTAL SETTINGS
All of the experiments are run on a single machine with Intel(R) Core(TM) 19-7920X CPU @ 2.90GHz with 24 logical cores and 128GB memory.
Datasets. We investigate five publicly available real-world datasets of different scales, different densities, and containing different types of information. All of the networks are processed as undi- rected ones. The detailed statistics of the networks are given in Table 7 in Appendix E.2. We give brief introduction of the datasets as follows: YouTube (Tang & Liu, 2009b) is social network with millions of users on youtube. com; BlogCatalog (Tang & Liu, 2009a) (BC) is a social network of bloggers who have social connections with each other; PPI (Breitkreutz et al., 2007) is a subgraph collaboration
of the PPI network for Homo Sapiens; Arxiv GR-QC (Leskovee al., 2007)
network from arXiv and covers scientific collaborations between authors with papers submitted to General Relativity and Quantum Cosmology category; DBLP (Ley, 2002) is a citation network of DBLP, where each node denotes publication, and each edge represents citation.
Baselines. The investigated NE methods include three based on NCE, two based on matrix factor- ization, and one based community detection. Here introduce them briefly: LINE (Tang al., 2015) models first-order proximity (connection strengths) and second-order proximity (similarity of neighborhoods) of given networks, and technically feed the adjacency matrix to two types of NCE- based objectives to learn node embeddings; node2vec (Grover & Leskovec, 2016) designs biased random walk algorithm to simultaneously preserve Bread-Fin First Search information and Depth Depth-First First Search information, and feed the random walk sequences to word2vec; VERSE (Tsitsulin et al., 2018) feeds node similarities (Personalized PageRank, Adajcency Similarity, and SimRank) the NCEEbased objective; NetSMF (Qiu et al., 2019) obtains node embeddings by sparse matrix fac- torization on a sparsified dense random walk matrix; ProNE (Zhang et al., 2019) initializes node embeddings by sparse matrix factorization, and then enhances the embeddings via spectral propaga- tion; LouvainNE (Bhowmick et al., 2020) first adopts Louvain graph partition algorithm (Blondel al., 2008) and then learn node embeddings from the partitions. HHNE (Zhang al., 2021) trains hyperbolic node embeddings for heterogenous networks because hyperbolic geometry can reflect some properties of complex networks.
Parameter Settings. For all methods that can set the number of threads (node2ket and baselines except ProNE and LouvainNE), 128 as the default. For node2ket, we set the number of blocks B = 1, number of negative samples K by default. For more details of parameter settings, please refer Appendix E.3,
8 threads the default. Embedding dimension is set to
5.2 EXPERIMENTS ON NETWORK RECONSTRUCTION
Network reconstruction is used to measure an embedding model's ability to preserve nodes' origin local structure. In line with (Wang et al., 2016), for baseline methods, we measure the score of a pair of node embeddings by negative Euclidean distance. While computing the Euclidean distance between two embeddings in the dc -dimensional Hilbert space is computationally intractable, we the inner product instead. During the reconstruction process, calculate the scores between

---

Under review as a conference paper at ICLR 2023
a)
Performance B and
b) Utilize block weights
Trade-oft between C' and
Improved Precision (%)
(percentage points)
B-2
B-1
GR-CC
BC
100
Precision (%)
3-
Precision (%)
70-
75-
60
2-
50-
B-1
50
B=2
25
Hw4
C-2
C-4
C-8
C-2
C-4
C-8
D-1
Ded
C-8
G-18
C-32
d-16
d-B
d-2
Figure: 3: Ablation studies on the number TEBS B, column number C, TU embedding dimension
d, and the adoption of block weights with different B and C. Tests of a) and b) run on GR-QC.
Network reconstruction precision on medium-scal networks. The value in brackets (e.g. 0.70 with superscript at the first row) is the ratio of used parameters by node2ket+ to store embed-
Table 2:
dings against traditional NE methods: d E Re/p Re/pN.
dataset
LINE
node2vec
VERSE
NetSM
ProNE
LouvainNE
HHNE
n2k
n2k+
GR-QC
54.19
66.38
56.08
30.26
56.37
43.47
50.50
97.31
92.43 (0.70*)
BC
4.80
21.16
10.96
7.64
10.10
6.79
0.69
26.07
25.06 (0.90)
DBLP
2,34
21.17
16.96
18.08
17.76
21.33
11.40
86.40
86.62 (0.77)
PP1
15.18
43.13
27.59
17.14
24.02
17.77
18.23
74.07
82.25 (1.00)
all possible pairs of the embeddings, namely [V[[))-1 1)/2 undirected node pairs. Then sort the scores and select the top- [&] node pairs, denoted as E", Then the precision is defined as Precision = |E / For large-scale networks, we use @ approximately measure the precision (for detailed explanation please see Appendix 1)
Evaluation on Medium-scale Networks: We set the embedding dimension as 128 for all the base- lines. For node2ket, we set B 1, C 8, and d = 16, which means that to store the embed- dings, the number of used parameters for each node is BCd = 128, the same as the baselines. For node2ket+, we also set B = 1, C 8, and d = 16. Note that node2ket+ decreases the number of TUs but brings space consumption of the r(i,e) e) table, so the average consumed space to store em- bedding for each node may not be equal to 128. The experimental results are given in Table 2, which shows that i) both node2ket and node2ket+ achieve the precision that conventional embedding methods hardly reach by efforts in feature engineering as most works do; ii) even after decreasing the number of TUs, node2ket+'s performance does not decrease significantly compared with node2ket, indicating that further compression without sacrificing performance is still possible.
Evaluation on Large-scale Network (YouTubbe): We only evaluate baselines that are scalable and could be run on our machine. We set the embedding dimension as 4 for baselines. Since node2ket fails to generate embeddings because it requires TU dimensions d 2 4 and C' 2 2, we only eval- uate node2kett, whose used space to store embeddings is little less than baselines (compressive ratio=0.99). Results are given in Table 3, showing that node2ket+ outperforms basclines mostly and also converges faster compared with other NCE-bbaed embedding methods.
Efficiency Evaluation and Scalability. We conduct the experiments on BlogCatalog. Two ques- tions are raised: to outperform baselines, how many training parameters does node2ket need? and ii) how much time does node2ket take? Answers are in Fig. 2 node2ket achieves to outperforms the best baselines with 1/64 training parameters in the evaluation of required training parame- ters, and with 1/32 training parameters and 1/16 running time in the evaluation of rumning time. The results show both the efficiency on space saving and time saving. The scalability has been proved in the experiments YouTube (Table 3), where it takes about minutes for the running of node2ket+ on a network of million nodes with CPU threads.
5.3 EXPERIMENTS ON LINK PREDICTION
We randomly mask 1% edges of the given network, and create the same amount of edges noise edges by randomly connecting nodes in the network. Then, we conduct network embedding on the network where masked edges are removed, and predict the masked edges from the mixture of masked edges and noise edges. The used metric is the same as network reconstruction (Sec. 5.2). Experimental results in Table 4 show that node2ket outperforms all the baselines consistently.
8

---

Under review as a conference paper at ICLR 2023
Table 3: Network reconstruction precision the large-scale network, YouTube..
Method
Prec@2
Prec@ 10
Prec@
Running Time (8)
OKhers NCEE-boso
LINE (Tang et al., 2015)
71.35
36.54
16.92
502.67
node2vec (Grover & Leskovec, 2016)
44.85
9.80
3.14
3979.52
VERSE (Tsitsulin et al., 2018)
53.68
34.20
25.08
435.03
ProNE (Zhang et al., 2019)
76.80
41.79
18.96
85.71
NouvainNE (Bhowmick et al., 2020)
85.74
70.89
63.12
8.63
node2ket+ (ours)
87.51
74.75
61.69
122.81
Table 4: Link prediction precision comparison on medium-scale networks.
dataset
LINE
node2vec
VERSE
NetSMF
ProNE
LouvainNE
HHNE
node2ket
GR-QC
95.86
91.72
93.79
87.59
93.79
86.90
93.10
97.24
BC
53.08
77.58
33.35
59.34
75.27
57.99
38.77
81.95
DBLP
75.45
82.09
68.81
82.09
85.31
73.44
85.92
91.95
PPI 55.15
77.58
51.55
72.16
73.97
57.99
65.72
79.12
5.4
ABLATION STUDY
We conduct ablation studies on node2ket, while the conclusions are the same for node2kett.
Number TEBs and Number of Columns C. Experiments of network reconstruction are conducted on GR-QC. We set Wis = 1/vBB as constants, d 4, and run node2ket with C 2, and B 1,2, 4. Results are shown in Fig. 3 a), which shows that model performance improved when or increases when small. However, we also observe that when larger, increasing B will have negative influence model performance.
Use Block Weights Wht as Trainable Parameters. Experiments network reconstruction are conducted GR-QC. We set d = 4, and run node2ket with C 2, 4, 8 and B 2, 4. In Fig. 3 b) we show the improved precision compared with setting Was as constants, which proves the positive roles of Wab in improving model's expressiveness when d is small. However, when d is larger, trainable Was is likely to make a negative influence on model performance.
The experimental results for the above two studies when d = are in Table 8 in Appendix E.4.
Experiments of net- work reconstruction conducted on all the medium-scale datasets. We fix Cd 64 and run node2ket with C = 2, 4, 8, 16, 32, and plot the results in Fig. c). We see that i) when C = 1, i.e. the tensorized embedding model is degraded the conventional embedding model, the model performance decreases, and ii) when d < 4, the performance is also negatively influenced.
Trade-off between Number of Columns and Embedding Dimension
5.5 PARALLELIZABILITTY
We evaluate node2ket on DBLP. We 8. and run the same number of SGD iterations with the thread number varying from to 16. We record the rumning time and precision shown in Fig. 4. The results show that i) the model performance is stable under the setting of different numbers of threads, and ii) the running time almost decrease linearly w.r.t. the number of threads when the number of threads is not larger than 16.
05
25:26
-00
Urecissoo
9.50
75
2
16
Figure 4: Parallelizability.
CONCLUSIONS AND FUTURE WORK
We have proposed the network embedding methods node2ket and node2kert, by training the embed- ding module Tensorized Embedding Blocks with an objective based on Noise Contrastive Estimation.
Limitation & future works. With the (possible) arrival of Noisy Intermediate Scale Quantum (NISQ) era (Preskill, 2018), the deployment of learning on quantum devices is becoming an ever- ubiquitous research topic (Cong al., 2019). Our method can be explored for its implementation in a more quantum-friendi] manner beyond the current quantum-inspired one, e.g. by variational quantum circuits (Cerezo et al., 2021), 1), so that it will be more feasible on quantum devices.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohammadreza Armandpour, Patrick Ding, Jianhua Huang, and Xia Hu. Robust negative sampling for network embedding. Proceedings of the AAAI Conference on Artificial Intelligence, 33:3191- 3198, 07 2019, doi: 116600/aai..33353 13331113331191.
Carl M Bender and Steven A Orszag, Advanced Mathematical Methods for Scientists and Engineers I: Asymptotic Methods and Perturbation Theory. Springer Science Business Media, 2013.
Ayan Kumar Bhowmick, Koushik Meneni, Maximilien Danisch, Jean-Loup Guillaume, and Bivas Mitra. Louvainne: Hierarchical louvain method for high quality and scalable network embedding. In Proceedings of the 13th International Conference on Web Search and Data Mining, 2020.
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10). 2008
Bobby-Joe Breitkreutz, Chris Stark, Teresa Reguly, Lorrie Boucher, Ashton Breitkreutz, Michael Livstone, Rose Oughtred, Daniel H Lackner, Jürg Bähler, Valerie Wood, et al. The biogrid inter- action database: 2008 update. Nucleic acids research, 36suppL_1))667-D664) 2007.
Jacob Bridgeman and Christopher Chubb. Hand-waving and interpretive dance: An introductory course on tensor networks. Journal of Physics A: Mathematical and Theoreticul, 50, 03 2016.
doi: 7a1e//11771-811/aaa//6
Jacob C Bridgeman and Christopher T Chubb, Hand-waving and interpretive dance: an introductory course tensor networks. Journal of physics A: Mathematical and theoretical, 50(22):223001, 2017.
Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fu- jii, Jarrod McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3(9):625-644) 2021.
Song Cheng, Lei Wang, and Pan Zhang. Supervised learning with projected entangled pair states. Physical Review B, 103(12):12511, 2021.
Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physics, 15(12)11233 2019.
Yuxiao Dong, Nitesh V. Chawla, and Ananthram Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In Proceedings the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017.
Xingbo Du Junchi Yan, Rui Zhang, and Hongyuan Zha. Cross-network skip-gram embedding for joint network alignment and link prediction. TKDE, 2022.
Rong-En En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rut Rui Wang, and Chih-Jen Lin. Liblinear: A library for large linear classification. JMLR, 1771111871111874 2008.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. KDD, pp. 855- 864. ACM, 2016.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, pp. 297-304, 2010.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 201
William I. Hamilton, Rex Ying, and Jure Leskovec. Representation learning graphs: Methods and applications. arXiv preprint
2017b.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2ess, 2007.
10

---

Under review as a conference paper at ICLR 2023
Yoav Levine, David Yakira, Nadav Cohen, and Amnon Shashua. Deep learning and quantum entanglement: Fundamental connections with implications to network design. arXiv preprint arXiv:1704.01552. 2017. 2017.
Michael Ley. The DBLP computer science bibliography: Evolution, research issues, perspectives. In Proc. Int. Symposium on String Processing and Information Retrieval, pp. 1-10, 2002.
Weiyi Liu, Pin-Yu Chen, Sailung Yeung, Toyotaro Suzumura, and Lingli Chen. Principled multi- layer network embedding. In 2017 IEEE International Conference on Data Mining Workshops (ICDMW), pp. 134-141, IEEE, 2017.
Xien Liu, Xinxin You. Xiao Zhang, Ji Wu, and Ping Lv. Tensor graph convolutional networks for text classification. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 8409-8416 2020.
Xindian Ma, Peng Zhang, Shuai Zhang, Nan Duan, Yuexian Hou, Ming Zhou, and Dawei Song. tensorized transformer for language modeling. Advances in neural information processing systems, 32, 2019.
John Martyn, Guifre Vidal, Chase Roberts, and Stefan Leichenauer. Entanglement and tensor net- works for supervised image classification. arXiv preprint urXiv:2007.06082 2020.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeff Dean. Distributed representa- tions of words and phrases and their compositionality. In NIPS, pp. 3111-3119, 2013.
Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
Román Orús. Tensor networks for complex quantum systems. Nature Reviews Physics, 1(9):538- 550, 2019.
Aliakbar Panahi, Seyran Sacedi, and Tom Arodz. word2ket: Space-efficient word embeddings inspired by quantum entanglement. In International Conference Learning Representations, 2020.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In KDD, pp. 701-710. ACM, 2014.
John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Chi Wang, Kuansan Wang, and Jie Tang. Netsmf: Large-scale network embedding as sparse matrix factorization. In The World Wide Web Confer- ence, pp. 1509-1520. ACM, 2019.
Xipeng Qiu and Xuanjing Huang. Convolutional neural tensor network architecture for community- based question answering. In Twenty-Fourth international joint conference on artificial intelli- gence, 2015.
Meng Qu, Jian Tang, Jingho Shang. Xiang Ren, Ming Zhang, and Jiawei Han. An attention-based collaboration framework for multi-view network representation learning. In CIKM, 2017.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. NIPS, pp. 693-701, 2011.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. strue2vec: Learning node representations from structural identity. In KDD, pp. 385-394. ACM, 2017.
Raghavendra Selvan and Erik B Dam. Tensor networks for medical image classification. In Medical Imaging with Deep Learning, pp. 721-732. PMLR, 2020.
Edwin Stoudenmire and David J Schwab. Supervised learning with tensor networks. Advances in Neural Information Processing Systems, 29, 2016.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Lcrle-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pp. 1067-1077. WWW, 2015.
11

---

Under review as a conference paper at ICLR 2023
Lei Tang and Huan Liu. Relational learning via latent social dimensions. In KDD, pp. 817-826.
ACM, 2009a.
Lei Tang and Huan Liu, Scalable learning of collective behavior based on sparse social dimensions. In CIKM, pp. 1107-1116. ACM, 2009b.
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. Verse: Versatile graph embeddings from similarity measures. In Proceedings of the 2018 World Wide Web Conference, pp. 539-5399909 548. International World Wide Web Conferences Steering Committee, 2018.
Daixin Wang. Peng Cui, and Wenwu Zhu, Structural deep network embedding. In KDD, pp. 1225- 1234. ACM, 2016.
Hao Xiong, Junchi Yan, and Li Pan. Contrastive multi-view multiplex network embedding with applications to robust network alignment. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery; Data Mining, 2021.
Hao Xiong, Junchi Yan, and Zengfeng Huang. Learning regularized noise contrastive estimation for robust network embedding. IEEE Transactions Knowledge and Data Engineering, pp. 1-1, 2022. doi: 10.1000300
Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding. Prone: Fast and scalable network representation learning. In IJCAI, 2019.
Yiding Zhang, Xiao Wang, Nian Liu, and Chuan Shi. Embedding heterogeneous information net- work in hyperbolic spaces, ACM Transactions on Knowledge Discovery from Data (TKDD), 16 (2):1-23, 2021.
12

---

Under review as a conference paper at ICLR 2023
A ANALYSIS OF SPACE TO STORE/TRAIN EMBEDDINGS
NCE-based NE methods. In general, there are two most widely adopted objectives used in network embedding (Armandpour et al., 2019; Xiong et al., 2022):
NCE-x:
Σ (i,))D
logo x2)
Σ
Bynp logo xyy)
(8)
k=1
and
K
NCE-h:
Σ (JIED
log o (x hy)
Σ k=1
By log (ogo(-x] hy)
(9)
The NCE-x objective tends to make positively sampled nodes close in the embedding space (when D is the edge set, it means first-order similarity (Tang al., 2015)), while the NCE-h objective tends to make nodes with common positive samples close in the embedding space (when 'D is the edge set, it means second-order similarity (Tang al., 2015)). One further utilizes hidden embedding compared with NCE-x, and hence NCE-h double the number of training parameters compared with NCE-x. We list the number of parameters of the baseline methods in Table 5.
that mathematically NCE-h
Table 5: Network embedding methods adopting different types of NCE-based objectives.
Methods
Objectives
Train Emb.
Store Emb.
VERSE (Tsitsulin et al., 2018)
NCE-x
VVp
LINE (Tang et al., 2015)
NCE-x + NCE-h NCE-h
L.5/VPp
V/p
node2vec (Grover & Leskovee, 2016)
2/V(p
Node2ket. In this paper, our proposed node2ket adopts NCE-x as the objective, which, however, can be easily substituted with NCE-h by simply doubling the number of TEBs. We list the used parameters of different parts of node2ket in Table 6. Because of its NCE-x core, the numbers of parameters used to train/store embeddings are the same.
Table 6: The number of parameters used to train/store embeddings are the same for node2ket and node2ket+. In the table, 'opt.' is short for 'optional'.
TU embeddings (TEBs)
Block weights (opt.)
r(i, c) table constants
trainable
trainable/constants
Node2ket Node2ket+
BdC
B|V
Bd Ri.
CIVI
B RELATIONS TO WORD2KET AND WORD2KETXS
B. UNIPYING WORD2KET AND WORD2KETXS BY TEBS
Here we provide detailed explanation on how to use the language of Tensorized Embedding Blocks describe word2ket and Word2ketXS.
Word2ket generates embedding x; by:
X
u
(10)
where r is the rank and n is the order. Comparing Eq. 10 with the embedding generated by Eq. 3, one that in the language of Tensorized Embedding Blocks, the rank is equal to the block number B, the order is equal to the column number C', with block weights wa = set as constants. TTougg very similar the way node2ket generates embeddings, it worth noting that word2ket
13

---

Under review as a conference paper at ICLR 2023
requires that 2 because the embeddings generated from leaf nodes of complete binary tree thus computation of final embeddings can be speeded up. while in comparison, the column number C' of node2ket can be any integer no less than 2.
Word2ketXS generates embedding from linear operators. The embeddings are written as:
X =
U
(11)
where n, has the same meaning as they in the word2ket, X is the word embedding linear operator which can be understood as the embedding matrix of shape p x [V]. We write = {x:)<0 11-1 where X; is i-th column of X and also the embedding of node i. U is also linear operator which can be understood as set of column vectors U = f p- We define X = fxf 1 = 0 U By the property of Kronecker product in Lemma whose proof is obvious and omitted, we can find that:
matrix of shape q x (q" p and t" [V], and we write
x u t0ye0 24 24
(12)
and by = Ek-1 X we have:
Xuytn 1 figtt
Bj =y=0, 0,
(13)
k=
So far we have achieved writing the embedding of word2ketXS in the language of TEBs. It is also worth noting that word2ketXS requires that n 2 The reason is the same as word2ket.
Lemma (Property of Kronecker Product). Given two matrix ADXa {aa a1. ... ....aa.glllll .. and
Bmx= {bo, bi.'.. bn-1), suppose C is the Kronecker product of A and B, i.e. C = A B, then Cpmxqg {Co: C1, C.m-1h. where Csm+t ag 8 by-
B.2 TECHNICAL DIFFERENCES BETWEEN NODE2XET/NOD2XETH AND WORD2KET/WORDZEET
imput data
ambodding learning
embedding generation
conventional NCE-
sentences, metapiths, elc.
low dimension
hidden
based embedding (word2ver, node2vec, elc.)
distributed
NCE-based based
NCE: objective
common part of node2ket and word2ket
training ASGD
scalahle
self self-supervised
block
Inner product decoder
weights
sensorized
flexible shape
embedding
Super high dimension
node2ket
NN decoder
by binary tree
word2ker
supervised
embeddiing
embedding learning
generation
data
Figure 5: Venn diagram where conventional NCE-based embeddings, node2ket and word2ket technically compared. We can see that node2ket and word2ket only share common things embed- ding generation. And indeed our proposed node2ket bridges the gap between conventional embed- ding methods and tensorized embedding.
The differences are summarized Table and Fig. 5, which are mainly from the following three aspects:
14

---

Under review as a conference paper at ICLR 2023
i) The embedding generation. We have shown that both the embedding generation modules of word2ket/word2ketSS are special cases of TEBs in Appendix B.I, and know that the differences of word2ket and word2ketXS lie in the shape of TEBs (B, C, and { and the definition of r(i, c) indices. Then we can find that the differences between the embedding generation models of word2ket/word2ket55 and node2ket/node2kee and whether the shape of TEBs is flexible to be re-designed by re-defining r(i, c). The adoption of block weights proved to improve model expressiveness when d small (Fig. 3 b)), and flexible shape of TEBs is promised to make the embedding model more compressive thus improving space efficiency.
are mainly whether block weights wib adopted
iii The embedding learning phase. Word2ke/wood2kettS train embeddings in supervised way with an NN decoder, while node2ket/nodee2ktt+ train embeddings by NCE (contrastive learn- ing) which mainly cares about the inner product between the embeddings. In this way, full em- beddings are required for word2ket/word2ket35 to feed into the decoder but are not must for node2ket/node2kktt: Therefore, node2ket/nodeekktt do not need further memory for the full em- bedding and manage to perform embedding in the Hilbert space very large dimension (242 in experiments, which can be indeed more than 2 on machine).
iii) The input data. Word2ket accepts sentences as the imput data, which is kind of unstructured data. In comparison, node2ket is designed process highly structured networks, with effort on reshaping TEBs to improve both model expressiveness and space efficiency.
C TECHNICAL DETAILS
C.I GRADIENT DERIVATION
provide detailed gradient derivation Eq. and Eq. 6 here. Given two embeddings:
B x, x;= =
X;
Wib
Σ Wib
(14)
have the inner product:
B
(x X2)
Σ
WaW
II
uu (1 u
(15)
b
8/
from which we have the partial derivative:
0(x,, x,)
B Σ
wibh
Wine
(i,c)e II (ubaeee o d'
(16)
Ou (ir.je
==
a(x,, Owsn
Σ way II
(u
o (hore)
(17)
When (i.j) is positive sample with label 1, the objective is log o (x,, x,), and when it is negative sample with label 0, the objective becomes log or - (x,, x,)). We define an indicator function 1, which takes value if and if 0, then the objective be written as
15

---

Under review as a conference paper at ICLR 2023
log (2(1 (2,, x,)). Then we have the following formula with Eq. 16:
i boo (2(1) 0.5)(x;,x,))
du (th,)0
Do (2 - 0.5) (x,, x,))
o 0.5) x3))
Ou (1,
1 [2 - (x4, x
=(1 (2((1, 0.5) x,)))
Su (t..le
(18)
=[1 ((xi, x,))] 0(x;,,)) x,)
Ou ((,c)e
=wh [1, o (x+ x,))|
Σ
Wir Wyr
II
(uaaeer uh Rieeeh
8=1
e'
which is the result of Eq. 5.
For the gradient derivation of block weights was. Then we have the following formula with Eq. 17: llg (2(11 (x;, (x),
[1, o((x;, x,3)| O(x,, x²)
Owi
Ows
(19)
[1, ((x,,
Σ 1gy
(u (i u (iseee)
which is the result of Eq. 6.
C.2 MODEL LEARNING
We give the pscudo-code thread of ASGD in Algorithm and give and illustration how distributed learning by ASGD is implemented in Fig. 6. The details of embedding regularization and normalization are in Appendix C.2.1.
updute emheddings:
Thread
Thread
Thread 2
Thread N
CPU Threads
write umbesddinge embeddings
Shared Memory
ME
%
Figure 6: Illustration of how distributed learning by ASGD is performed on embedding learning.
C.2.1 EMBEDDING REGULARIZATION AND NORMALIZATION
TENSOR UNITS
The multi-column architecture of the Tensorized Embedding Blocks brings difficulties to embedding training. Following unexpected results are likely to happen without proper normalization: i) embed- dings converge vectors vectors of infinite length, ii) embeddings converge the same
16

---

Under review as a conference paper at ICLR 2023
Algorithm 1: A thread of embedding learning via ASGD.
Input: TU embedding dimension d, number of negative samples (for each positive sample): K, node set V, corpus D, initial learning rate 7 (default 0.025);
1: Initialize TÚ embeddings and block weights.
2: for all sample positive sample (i, from do
3: Compute the gradients according to Eq. 5 and Eq. 6 (with regularization adopted) with label
=.
4: Update and normalize TU embeddings for node j.
5: for n 1, .., do
6:
Sample negative node j':
7: Compute the gradients according to Eq. 5 and Eq. with label = O. end for
8: Update and normalize TU embeddings for node j'.
9:
10: Update and normalize TU embeddings for node
11: end for
return TU embedding set {ukc} and block weights {wa)
vector. We adopts embedding regularization and normalization in the implementation improve the robustness of the algorithm, as shown in Fig. 7.
Regularization. (Fig. a)) Distance penalty terms can be added positive node pairs accelerate model convergence and improve the ability to preserve node proximities (Xiong et al., 2022). In the implementation, we adopt Wasserstein-3 distance regularizaton term over TU embeddings of positive node pairs.
(Fig. 7 b)) To increase the stability of embedding training, we make TU embed- dings constrained by ||ure|l = 1. In this way, TU embeddings won't converge to vectors of zero or infinite length.
Normalization-1.
Va Normalization- (Fig. c)) During training, we move the axis towards 1 1 for a step. In this
way, most of the pairs of embeddings the unit ball yield a positive inner product. We have known that the inner product two embeddings x; and xj is determined by the inner product of the TUs, i.c. X,) Σe ΣB= way Ie (u (i.e)er 4 "iieee in Eq. 15. By making most of inner products between embedding pairs positive, can mostly avoid the cases where two negative inner products of TUs finally yield a positive inner product of the node embeddings.
a) Regularization
b) Normalization-1
c) Normalization-2
Figure 7: Embedding regularization and normalization.
D PROOF TO THEOREMS
Theorem 1. Given node set V and the final embedding dimension when r(i,c) = i are constants (indicating R. = -V1 c. < C) and use block weights trainable parameters, the total number of parameters is #params B[C [V]). Omitting the integer constraints of d, we have:
min #params Bly // la In B|V
17

---

Under review as a conference paper at ICLR 2023
When the block weights constants, #params BC|V|d, and we have:
min #params B/V|p"/ In Inp.
Proof. The number of parameters for embeddings is Bd Ee R. = BCIV/d, dd for block weights is B Then the total number of training parameters is:
params BCI BIV| 2 BIVICP
(20)
where #params f(C) iff d = p//C. Then have the derivative:
df(c)
dC = BIVIp C logp).
(21)
When df(C) dc
0, we can reach the solution C" Inp And we have:
f(C*) = B/V 1n Inp + B|V| min f(C). Now we can reach the conclusion, when d = plc and C Inpr min #params B Vlp In Inp + BIV.
(22)
(23)
Following the above proof, it is easy to reach the conclusion min #params B V/pp lop In when the block weights are set as constants.
Comments: By Theorem 1, we prove that we can use O(p lap Inp) space for each node embed- ding in p-dimensional space with B 1. For example, when p [c2000] which is too large for classical algorithm to deal with, by node2ket, may C In p 1000 and d [pp//] [e], totally about 1000[e] or so parameters to train the embedding of dimension [e 1000 in the Hilbert space.
Before proving Theorem 2, we introduce the following lemma which obvious by Cauchy inequal- ity:
Lemma 2. ,,,R,
R. 2 Ro)2/C, when the equality holds, Rí = R2
Rc-
Theorem 2. Given the node set V and the final embedding dimension p. when node2ket utilizes both
the r(i,e) e) table and block weights, the total number of parameters is #params Bd E Rg +
BVV + CVV). We have:
min #parums BC (plv1) 1/0" + +BII+ CMM1
- - 1 IInllV] + + (121/BB 1). When the block weights are set as
where C* -==vV
constants, we have:
min #purams < BC +C*l
(24)
Proof. By Lemma 2, have:
#params 2 [ R 1/C -BV
c=
Bp R/C BIV CIVI
(25)
Bp BM + CPV
= =BC(pl1)) 1/C + +BV CIV := f(C),
where the inequality on the first line comes from Lemma 2, the second line comes from d 2 /C and the third line comes form [ R. 2 |.. Then we have the derivative:
df(C) dc = B(p VI (1 C
Inplvi) + [V].
(26)
18

---

Under review as a conference paper at ICLR 2023
for which it is very hard to solve Expansion for (p) ( as:
df(C) dc
0. To give approximate solution, we first do Taylor
(p (QDi"/==11 C bnpli + 20t
1
In [mmp/||
plV/ )
+0 + 03
(27)
according to which we have:
df(C) B 1 C 1npl1 + 20
[Inplv|+ + ) + +0 1
(3) (1 (1-
c (nlivl) 12
dC
(28)
= =B(I+ ल In
1 piv) (Iel/)) + { 1
We let df(C) dC
omitting the O(1/C*) term, then we get a solution:
0' -'= --
(Inp|i+ (Ippi)
I AIV / /(MIBB++1
(29)
by which dS(C)
0. Since C* is an approximate solution, we have /(C") > min S(C), and
aC'
C=
hence:
min params < <(()),
(30)
which is the first conclusion of the theorem. For the second one, we just need to remove the second B[V term in f(C), similar the proof of Theorem
impossible to find analytic solution of df(C) which gives the C' that makes aC #params minimum. We can only give upper bound of #params. The procedure to reach Theorem similar to Theorem 1.
Comments:
E EXPERIMENTS
E. DETAILED EXPLANATION ON THE METRIC PREC&N NETWORK RECONSTRUCTION
For large-scale networks, it is infeasible to compute the scores of all P node pairs and rank them to reconstruct the raw networks. So, we can only approximately estimate the reconstruction precision by sampling. The description in the paper is actually straight forward. First we sample [E] randomly matched node pairs as the noise node pairs, denoted as E Specifically,
we have 10 edges in the given network (i.e. [8| 10), randomly sample 10(N - node pairs as fake (noise) edges Ed (E"1 = 10(N - 1)). Then we calculate the scores of edges in 8 and select the top-|E] pairs the reconstructed edges. It means (containing true edges and fake edges), we hope to select 10 edges from the 10.V edges. So far, the computation of precision Prec@.N becomes obvious. Since the process contains random sampling, we need to fix the random seed to ensure the fairness of experiments. Previous works e.g. (Wang al., 2016) also conduct NR for large-scale networks in this way, which is indeed common approach in the research.
have totally 10 edges
E.2 STATISTICS OF DATASETS
The statistics of datasets are given in Table All of them are public online.
Table Statistics and network used in our experiments.
Dataset
YouTube (resp. Cut)
BlogCatalog
PPI
GR-QC
DBLP
DV [
1,138,499 (resp. 22,579) 2,990.443 (resp. 95,596)
10,312
3,890 76,584
5,242
12,591
333,983
14,496
49.627
Avg. degree
5.25 (resp. 8.46)
64.78
39.37
5.53
7.88
Type of info.
Social
Social
Biological
Academic
Academic
19

---

Under review as a conference paper at ICLR 2023
E.3 DETAILED EXPERIMENTAL SETTINGS
E.3.1 BASELINES
LINE (Tang et al., 2015) models first-order and second-order proximity on the adjacency matrix, trains them separately with edge sampling, and concatenates the representations after normalization on node embedding. The number of samples is set as x 10
node2vec (Grover & Leskovec, 2016) uses biased random walk explore both breadth-first and depth-first structure, and train node embedding and hidden embedding by negative sampling. We set p 1 and q = 1 in the experiments, and window size 10, walk length 80 and number of walks for each node 80.
VERSE*
(Tsitsulin et al., 2018) uses node similarity explicitly by Personalized PageRank (PPR), Adajcency Similarity, and SimRank, and learns node embedding by NCE-x. We use the default version with PPR similarity, damping factor a 0.85. We run 10 epochs for each node.
N (Qiu et al., 2019) obtains node embeddings by sparse matrix factorization on sparsified dense random walk matrix. We set rank as 512, window size as 10, rounds as 1000, which the recommended setting by the official code for BlogCatalog.
ProNE (Zhang et al., 2019) initializes embedding by sparse matrix factorization, and then enhances the embedding via spectral propagation. We run Python version in the repository with the default setting, i.e. the term number of the Chebyshev expansion 10, 0 = 0.5, and μ = 0.2. We use the enhanced embedding as the node embedding result.
LouvainNE' (Bhowmick et al., 2020) first adopts Louvain graph partition al- al-gorithm (Blondel et al., 2008) and then learn node embeddings from the partitions. We use Louvain partition as the graph partition algorithm, and set the damping parameter a=0.01 which is the default value in the reposi- tory.
HHNE (Zhang et al., 2021) adopts hyperbolic embedding for heterogeneous networks. We feed random walk sequences into the hyperbolic embedding core. We set window size as 5, the number of negative samples as 10. The other parameters follow the default setting of the official repository.
E.3.2 NODE2KET AND NODE2KET+
Experimental parameter setting of node2ket in Table (network reconstruction). On GR-QC: do 10M sampling iterations. On BlogCatalog: we do 100M sampling iterations. On DBLP: we do 20M sampling iterations. On PPI: we do 20M sampling iterations.
Experimental parameter setting of node2ket+ in Table 2 (network reconstruction). On GR-QC: we do 10M sampling iterations, Louvain graph partition adopts resolution [800, 1000, 1200, 1400, 1600, 1800,-1, TEBs, which results in the row number [2229, 2495, 2656, 2861, 2978, 3113, 5242, 5242]. On BlogCatalog:
(-1 means parition) for the 8 columns in the
do 100M sampling iterations, Louvain graph partition adopts resolution [800, 1000, 1200, 1400, 1600, 1800, -1] (-1 means no parition) for the 8 columns in the TEBs, which results in the row number [7122, 7606, 7989, 8296, 8559, 8754, 10312, 10312). On DBLP: we do 20M sampling iterations, Louvain graph partition adopts resolution [1000, 1500, 2000, 2500, 3000, -1, 11,1] (-1 means no parition) for the columns in the TEBs, which results in the row number [4874, 5995, 6944, 7775, 8372, 12591, 12591, 12591). PPI: we do 20M sampling iterations, Louvain graph partition adopts resolution [2000, 2200, 2400, 2600, -1, -,,11-1 -1] (-1 means no parition) for the 8 columns in the TEBs, which results the row number [3372, 3429, 3458, 3505, 3890, 3890, 3890, 3890).
hhuts//githbb.com//aggaaauuuuuuu
hnapss//gihlubbcoo/////veeeee
20

---

Under review as a conference paper at ICLR 2023
Experimental parameter setting of node2ket+ in Table 3 (network reconstruction). We do 1500M sampling iterations, Louvain graph partition adopts resolution [1500, 3000] for the 2 columns in the TEBs, which results in the row number (81790, 142163).
Experimental parameter setting of node2ket and in Table 4 (link prediction). On GR-QC: do 100M sampling iterations, further sample from 2-hop neighbors for positive samples. On BlogCatalog: we do 100M sampling iterations. On DBLP: we do 50M sampling iterations, we further sample from 3-hop neighbors for positive samples. On PPI: do 100M sampling iterations, we sample from 3-hop neighbors for positive samples.
Experimental parameter setting of node2ket and in Table and Table 10 (node classification). On PPI. we do sampling iterations. On YouTube, we do sampling iterations. For baselines we set embedding dimension p = 8. For node2ket, set B 1, C 2, and and do 100M sampling iterations.
E.4 FULL RESULTS OF ABLATION STUDY
The results are give in Table 8. When or trainable parameters, so the reported results are the same. From the results we see that trainable wa and the increasing block number B may make negative influence on the model. It is possibly because the increased number of parameters brings difficulties to model training.
wa becomes meaningless whether was are constants
Table 8: Network reconstruction precisions on GR-QC with d 8.
Wib are constants
are trainable params
C
C
4
C
2
C
B =
71.32
87.04
96.20
71.32
87.04
96.20
B 2
75.16
85.62
93.42
69.01
86.14
92.35
B = 4
71.57
79.05
89.43
72.84
83.76
89.39
E.5 VISUALIZATION OF RECONSTRUCTION RESULTS
E.5.1 INTERPRETABLE VISUALIZATION ON LADDER GRAPH
We conduct node embedding via node2ket on circular ladder graph of 20 nodes, which is plotted Fig. a) and the adjacency matrix is visualized in Fig. f). For node2ket, we set = 1, reconstruct the adjacency matrix
C' == 2, and d 4. After obtaining the TUs' embeddings, from Column and Column of the TEB and visualize them in Fig. 8 b) and c). Then, from compute the reconstructed adjacency matrix and visualize it in real-
the final node embeddings, valued/binarized form as shown in Fig. 8 d) and e). From the results, we have the findings: i) by comparing Fig. 8 b), c), and d), we see that column and column 2 preserves structures in an approximately orthogonal manner, which means the extracted information is different among columns of a TEB, and ii) by comparing Fig. e) with the ground truth f), node2ket fully reconstructs the input adjacency matrix. To compare the reconstruction performance of different methods on different data, we further investigate a Hypereube graph, 3D-Grid graph, and the real-world Karate Club graph in Appendix E.5. The results directly show the overwhelming performance of node2ket on the network reconstruction task.
E.5.2 VISUALIZATION ON OTHER GRAPHS
We investigate circular ladder graph, 5-hypereube graph, 3D-grid graph, and the Karate club graph, and we evaluate all the baselines. The results in Fig. 9 show overwhelming reconstruction ability of node2ket, compared with different methods. We also find that node2ket does not perfectly reconstruct the adjacency matrix for some complex networks, e.g. the 3D-Grid graph and the real- world Karate Club graph.
Settings, All baseline methods use 8-dim embedding. For node2ket we set = 1, C = 2, and d 4, whose number of parameters for storing embeddings is the same baselines.
21

---

Under review as a conference paper at ICLR 2023
circular ladder graph
Reconstructed (real-valued)
Reconstructed (binarizee)
Column
Column
Ground
Figure 8: Visualization of the reconstructed adjacency matrix at different levels. A darker color represents higher value. The subfigure a) is the input circular ladder graph. In b) and c), a color block at the i-th row and j-th column visualizes the sigmoid score of TUs on the two columns the TEB, i.e. o( u mathematically. In d), color block at the i-th row and j-th column visualizes the sigmoid score of node embeddings, i.e. a xx) In e), binarize the results given by d). And f) is the visualization of the ground-truth adjacency matrix of the graph in a).
E.6 EXPERIMENTS ON NODE CLASSIFICATION
We conduct experiments on PPI (totally 50 labels) and YouTube (totally 47 labels). After embed- dings are obtained, LIBLINEAR (Fan et al., 2008) is used to train one-vs-rest Logistic Regression classifiers. We range the portion of Otraining data from 1% to 9% for YouTube and 10% to 90% for PPI. We use Macro-F1 as the metric. In line with (Perozzi et al., 2014; Tang et al., 2015; Wang ct al., 2016), for each method we perform 10 times of trials and report the average scores. Results given in Table 9 and 10, which shows that node2ket consistently outperforms baselines under the setting.
Table 9: Node classification results on PPI.
Portion of Training Data
10%
30%
50%
70%
90%
line
8.84
9.29
9.59
10.05
9.66
verse
8.60
10.56
10.98
11.29
10.93
node2vec
6.74
9.56
10.82
11.61
11.41
proNE
7.35
8.40
8.92
9.43
9.22
NetSMF
8.26
10.04
10.98
11.47
11.69
LouvainNE
7.34
8.23
8.62
8.36
8.15
ННNЕ
9.10
10.24
10.88
10.98
10.27
node2ket
10.53
12.23
13.15
13.56
13.01
Table 10: Node classification results on YouTube.
Portion of Training Data
1%
3%
5%
7%
9%
line
22.74
24.97
26.40
26.99
27.44
verse
24.09
26.50
27.40
28.09
28.34
node2vec
11.54
19.44
24.14
26.69
28.37
proNE
21.41
23.09
23.54
23.77
23.82
NetSMF
25.44
27.01
27.47
27.81
27.98
LouvainNE
20.43
21.85
21.97
22.38
22.56
HHNEE
23.42
24.82
25.26
25.90
25.91
node2ket
29.69
30.09
30.13
30.14
30.05
22

---

Under review as a conference paper at ICLR 2023
Circular Gruph
Hlypercube
al Input Graph
0
bo Ground-rre -ruth
20 000 20
00
O) nodee
di LING
e) node22ees
00 WERSE
+
hJ LouvainNE E
Figure 9: Visualization of reconstruction results of different embedding methods..
23


Reviews:
[{"review_id": "yIJ6Jnkdbua", "reviewer": "Reviewer_koXd", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper employs the tensorized embedding proposed in word2ket to the network embedding. It is similar with the second order part in network embedding method LINE, which is motivated from word2vec. Its superiority is verified on the tasks of topology reconstruction and link prediction.", "summary_of_the_review": "My main concern are the limited novelty and contribution and insufficient evaluations show in weakness.", "strength_and_weaknesses": "Strength \n- It is interesting to employ tensorized embedding to network embedding field.\n\nWeakness\n- The novelty is very limited. Most of the parts are similar to word2ket. Thus, the contribution to network embedding field is very limited, since only the objective function is different. \n- There is no contribution on the graph topology exploitation. The topology is only used in the the objective function, which is the same as pervious network embedding ones.\n- The experimental evaluations are not sufficient. The performance on node representation is only verified on topology-related tasks. However, that on node classification task is not given. Furthermore, the performance on topology-based tasks are only compared with the classic methods, instead of the SOTA such as hyperbolic space embedding methods.\n- The writing is redundant. Most content is similar to word2ket.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "i9-BYOvRjRq", "reviewer": "Reviewer_vWD3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studied a novel network embedding method inspired by quantum fields and modeled with tensors and contractions (i.e., outer product). More specially, the embedding vector for each node is represented by a linear combination of rank-one tensors, equivalent to the CP model studied in numerical algebra. In the paper, the authors also discussed the compressive power of the proposed method in a theoretical way. In the experiment part, this paper showed superior performance on network analysis tasks and evaluated the parallelizability and interpretability, which is crucial in practice.", "summary_of_the_review": "This is excellent work at least in the tensor community. The problem focused in this paper would inspire lots for tensor researchers to explore more valuable applications in machine learning. It also gives a bridge to connect machine learning to quantum computing.", "strength_and_weaknesses": "++Strength\n\n1. Very interesting model and the combination with quantum is also very smooth and clearly discussed.\n2. The improvement in the empirical performance is remarkable.\n\n— Weakness\n\n1. The theoretical results are not well explained.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "J9IZ1rvUtA", "reviewer": "Reviewer_s1h6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an unsupervised network (graph) embedding technique. Rather than using unstructured vectors to represent nodes, the embedding framework uses sums of Kronecker products of learnable vectors to represent the nodes. This is inspired by entanglement in quantum physics where similar representations are used to represent quantum states.", "summary_of_the_review": "The method proposed in this paper is an interesting idea, but the experiments are not convincing at all. In particular, it's not clear why network reconstruction matters for down-stream tasks. The paper is also unclear in multiple places; the writing needs to be improved.", "strength_and_weaknesses": "Strengths:\n\nS1. The idea itself is interesting. Using compressed tensor formats in ML has been used for a variety of things like analyzing deep NN expressiveness and compression of NN weight layers. I haven't seen it in the context of node embedding before (although my knowledge of the network embedding literature is limited).\n\nS2. Intuitively, it seems like the proposed technique could lead to a substantial reduction in the number of parameters required for a given level of performance in a down-stream task.\n\nWeaknesses:\n\nW1. The main weakness is the experiments. The network reconstruction experiments are not convincing. It is not clear why the ability to reconstruct the original network is important for any interesting down-stream tasks. For example, simply storing the whole network itself only requires 2*(#edges) numbers, and will give perfect \"network reconstruction\" without any computational cost (so this is a \"trivial method\" that any other proposal ought to beat). By contrast, the proposed methods node2ket and node2ket+ require many more parameters than are required to store the original network, but give much worse reconstruction accuracy. Based on the provided parameters in the paper and appendix, I calculated the following parameter requirements for the datasets in Table 1.\n\nGR-QC:\n- Exact representation: 2*(#edges) = 28,992\n- node2ket: 8 * 5242 * 16 = 670,976 (23x more than exact representation)\n- node2ket+: (2229 + 2495 + 2656 + 2861 + 2978 + 3113 + 5242 + 5242) * 16 = 429,056 (15x more than exact representation)\n\nBC: \n- Exact representation: 667,966\n- node2ket: 8 * 10312 * 16 = 1,319,936 (2x more than exact representation)\n- node2ket+: (7122 + 7606 + 7989 + 8296 + 8559 + 8754 + 10312 + 10312) * 16 = 1,103,200 (2x more than exact representation)\n\nDBLP: \n- Exact representation: 99,254\n- node2ket: 8 * 12591 * 16 = 1,611,648 (16x more than exact representation)\n- node2ket+: (4874 + 5995 + 6944 + 7775 + 8372 + 12591 + 12591 + 12591) * 16 = 1,147,728 (12x more than exact representation)\n\nPPI: \n- Exact representation: 153,168\n- node2ket: 8 * 3890 * 16 = 497,920 (3x more than exact representation)\n- node2ket+: (3372 + 3429 + 3458 + 3505 + 3890 + 3890 + 3890 + 3890) * 16 = 469,184 (3x more than exact representation)\n\nSimilarly, the circular ladder only requires 54 numbers for exact representation, while node2ket uses 64 parameters.\n\nThe only case I saw where there was some compression was in Fig 2 (b) when node2vec uses C=2 and d=4. In this case, node2vec uses 0.12 the number of parameters required to store the original network.\n\nThe Link prediction experiment in Sec 5.3 is poorly explained. How is the prediction done? What do you mean by \"mixture of masked edges and noise edges\"? I couldn't find a clarification in the appendix.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject