Reconciling Competing Sampling Strategies of Network Embedding
Authors: Yuchen Yan
Baoyu Jing
Lihui Liu
Ruijie Wang
Jinning Li
Tarek Abdelzaher
Hanghang Tong
Venue: NeurIPS 2023 poster (2023)
Keywords: Network embedding

Abstract: Network embedding plays a significant role in a variety of applications. To capture the topology of the network, most of the existing network embedding algorithms follow a sampling training procedure, which maximizes the similarity (e.g., embedding vectors' dot product) between positively sampled node pairs and minimizes the similarity between negatively sampled node pairs in the embedding space. Typically, close node pairs function as positive samples while distant node pairs are usually considered as negative samples. However, under different or even competing sampling strategies, some methods champion sampling distant node pairs as positive samples to encapsulate longer distance information in link prediction, whereas others advocate adding close nodes into the negative sample set to boost the performance of node recommendation. In this paper, we seek to understand the intrinsic relationships between these competing strategies. To this end, we identify two properties (discrimination and monotonicity) that given any node pair proximity distribution, node embeddings should embrace.
Moreover, we quantify the empirical error of the trained similarity score w.r.t. the sampling strategy, which leads to an important finding that the discrimination property and the monotonicity property for all node pairs can not be satisfied simultaneously in real-world applications. Guided by such analysis, a simple yet novel model (SENSEI) is proposed, which seamlessly fulfills the discrimination property and the partial monotonicity within the top-$K$ ranking list. Extensive experiments show that SENSEI outperforms the state-of-the-arts in plain network embedding.

Reconciling Competing Sampling Strategies of Network Embedding
Yuchen Yan, Baoyu Jing, Lihui Liu, Ruijie Wang, Jinning Li, Tarek Abdelzaher, Hanghang Tong University of Illinois at Urbana Champaign, IL. USA {yucheny5, baoyuj2, lihuil2, ruijiew2, jimning4, zaher, htong)@illinois.c edu
Abstract
Network embedding plays a significant role in a variety of applications. To capture the topology of the network, most of the existing network embedding algorithms follow a sampling training procedure, which maximizes the similarity (e.g., embed- ding vectors' dot product) between positively sampled node pairs and minimizes the similarity between negatively sampled node pairs in the embedding space. Typically, close node pairs function as positive samples while distant node pairs are usually considered as negative samples. However. under different or even competing sampling strategies, some methods champion sampling distant node pairs as positive samples to encapsulate longer distance information in link pre- diction, whereas others advocate adding close nodes into the negative sample set to boost the performance of node recommendation. In this paper, we seek to understand the intrinsic relationships between these competing strategies. To this end, we identify two properties (discrimination and monotonicity) that given any node pair proximity distribution, node embeddings should embrace. Moreover, quantify the empirical error of the trained similarity score w.r.t. the sampling strategy. which leads to an important finding that the discrimination property and the monotonicity property for all node pairs not be satisfied simultaneously in real-world applications. Guided by such analysis, a simple yet novel model (SENSEI) is proposed, which seamlessly fulfills the discrimination property and the partial monotonicity within the top-K K ranking list. Extensive experiments show that SENSEI outperforms the state-of-the-arts in plain network embedding.
Introduction
In the era of big data, network embedding
maps nodes in the network to low- dimensional vectors in the embedding space, which plays an important role in many tasks such as
36 14
21 42
node recommendation [54] 61 38
8
20
19
2] networked time series imputation [8
48 9]
knowledge graph completion 49
46
45
28
and network alignment (52 53
60
62
16
To distill the topology information of the network, most existing network embedding methods follow sampling training procedure. Given any central node to be considered, existing network embedding methods build positively sampled node pair set and a negatively sampled node pair set. Then, they optimize the embeddings of nodes by maximizing/minimizing the similarity between positively/negatively sampled node pairs in the embedding space. Explicitly or implicitly, these methods are based on an assumption that nodes close to the central node should be included in the positively sampled node pair set, whereas distant nodes are likely to considered as negative samples. For example, DeepWall Walk (36) and metapath2vee 77] explicitly construct random walk containing positively sampled nodes and select negative nodes according to the degree distribution of the network. The message-passing mechanism in GraphSAGE 05] and graph auto-encoder (GAE) 22 is built on graph Laplacian regularization [2] 57], which makes connected node pairs to be
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

similar. In this case, the close/distant nodes become implicit positive/negative samples for the central node, which can be regarded as a general form of such sampling training procedure.
Numerous network embedding algorithms have been proposed, which focus on improving either the positive sampling strategy or the negative sampling strategy based on various intuitions. Con- sequentially, disparate or even competing sampling strategies emerge in various methods. To name a few, rather than solely favor nodes within two hops as positive samples in LINE [41], node2vec allows a longer random walk length. For graph convolution network (GCN) [21] APPNP
14
23 utilizes personalized pagerank [33] to sample more distant nodes w.r.t the central node for
feature aggregation. The aforementioned two algorithms accommodate farther nodes in the positively sampled node pair set. Meanwhile, SPNE [22] KBGAN 4 and RecNS [56] encourage choosing
closer nodes as difficult negative samples to promote the performance of node recommendation.
Thus, some fundamental questions arise: what is the theoretic root cause behind such antithetical sampling strategies? what are possible and what are impossible for sampling of network embedding? how can we develop a practical embedding algorithm that simultaneousty embraces these competing strategies?
In this paper, we hammer at bringing the intrinsic relationships behind these competing sampling strategies in light. Concretely, we start from two fundamental tasks of graph learning: the link prediction task and the node recommendation task. To tackle the above two tasks synchronously, we identify two desirable properties, including the discrimination property and the monotonicity property, that network embedding vectors should satisfy given a node pair proximity distribution. The discrimination property means that the node pair with high proximity should be distinguished from the node pair owning low proximity in the embedding space (link prediction). For the monotonicity property, the ranking list of nodes recommended to the query node needs to be consistent with the proximity list in the descending order. Theoretically, we analyze the general form of network embedding algorithms' loss functions. We show that the negative sampling distribution should be negatively correlated with the node pair proximity distribution. Furthermore, we show that in the ideal case where the algorithm can sample an infinite number] of positive nodes for the central node, both the discrimination property and the monotonicity property can be fulfilled (i.e., possibility result). However, due to the limited sample size of the real-world data, there exists an inevitable error between the ideal optimal similarity scores and the empirical optimal similarity scores in the embedding space. Regardless of the specific sampling strategy, the discrimination property and the monotonicity property for all node pairs in the network can not be fulfilled the same time (i.e., impossibility result).
Fortunately, in real-world applications, ranking all nodes in the network for the query node is often unnecessary. In many cases, only the top-K recommendation list and its internal order matters, which suggests that we can first achieve the discrimination property to detect candidate nodes to be recommended. After that, we can attain the monotonicity property within the top K ranking list (partial monotonicity). Guided by this intuition and the theoretical results, we propose a simple yet novel model (SENSHI). In detail, SENSEI adopts a commonly used proximity measurement (personalized pagerank 33) and decomposes the embedding process into two steps. The first step is to satisfy the discrimination property. In addition to sampling nodes with large proximity as positive samples, SENSEI also includes nodes with intermediate proximity in the positively sampled node pair set, which reduces the empirical error of the similarity scores for these nodes. Then, in the second step, SENSEI pays attention to the monotonicity property within the positively sampled node pairs from the first step. Nodes are ranked w.r.t. their proximities and importantly, some positively sampled nodes are turned into negative samples, which resembles the strategy of selecting difficult negative samples in some existing methods [4] (,5 In this way, SENSEI creatively integrates these two competing sampling strategies in one integral framework. The experiments demonstrate that SenSEi greatly outperforms various baselines.
To summarize, our contributions are three folds:
Theoretical Analysis. We reveal the underlying relationships between the competing sampling strategies of existing network embedding methods. Specially, we prove that any
IInttead of having an infinite number of nodes in the network, we could sample positive pairs infinite times approximate the true distributions.
2

---

sampling strategy bears an inevitable error gap between the empirical and ideal optimal embedding similarity scores.
Simple yet Novel Model. Based on the theoretical results, we propose two-step model SENSEI which creatively integrates competing sampling strategies in one network embedding framework. It satisfies the discrimination property in the first step and obtains the partial monotonicity property within the positively sampled node pair set in the second step.
Experimental Results. Extensive experiments show that SENSEI outperforms the state-of- the-arts in plain network embedding.
Problem setting. We primarily focus plain network embedding, in which given the adjacency matrix of a plain network A, we aim to output the embedding matrix F.
Analysis
In this section, we uncover the intrinsic relationships of existing competing sampling strategies. First, we describe the sampling-basee network embedding process mathematically. Then, we propose two desired properties for the learned embeddings: the discrimination property and the monotonicity property, which correspond to two common learning tasks: link prediction and node recommendation. Theoretically, we analyze the general form of network embedding algorithmss' loss functions. We show that the negative sampling distribution should be negatively correlated with the given node pair proximity distribution. Guided by this critical insight, we give both possibility and impossibility results for network embedding. First (possibility result), we show that, in the ideal case where an infinite number of positive samples can be obtained, both the discrimination property and the monotonicity property can be satisfied with the optimal solution of the loss function. Second (impossibility result), for the empirical loss function with a limited number of positive samples, prove that there always exists an error gap between the empirical optimal solution and the ideal optimal solution. Regardless of the specific sampling strategy, the discrimination property and the monotonicity property can not be simultaneously satisfied for all node pairs in the network in the empirical situation.
Current sampling-batt based network embedding algorithms can be divided into two phases. The first phase is to construct node pair proximity distribution p(u) v), which serves the positive sampling distribution in the training process. For example, personalized pagerank [33] in APPNP [23] is an explicit node pair proximity distribution, while random walk in DeepWalk (6) and node2vec 14] implicitly constructs such node pair proximity distribution. The second phase is to design a negative sampling distribution Pu (u/e) ())e and to utilize the network embedding loss function train the embedding model. Similar to previous works [55] (56,, we start from analyzing the second phase of the sampling-based network embedding process as follows:
Definition 1. Sampling-based Network Embedding Process in the Second Phase. Given a node proximity distribution p, where p(ulu) refers the proximity of node w.r.t the central node e and En. p(ulv) = 1, the algorithm designs a negative sampling distribution Pw. and adopts a loss function J to obtain similarity scores s(u, v) E [0, 1] of all node pairs (u, v), which are calculated by the node embedding matrix F.
The similarity score s(u, v) defined here is general, which can be implemented with various similarity measurements (e.g.. the sigmoid function a (F(u,)) F(v.)) or the cosine function cos(F F(,,:), F(u,: ))) in various algorithms.
Then, to solve both link prediction and node recommendation tasks, we propose that the general simi- larity score s(u, v)) calculated by node embeddings should possess properties: the discrimination property and the monotonicity property, which are defined as the following: Definition 2. Discrimination and Monotonicity.
Discrimination Property: Given the central node v, node pair (u, v) with large p(ulu) should be clearly distinguished with node pair (w, v) with small p(wlv) in the embedding space, i.e.,
lim s(u.0)
( + when p(u(p) O.
p(a)e)
Monotonicity Property: Given the central node v and two arbitrary nodes u, w in the network, if p(ulu) > p( then s(u, v) > s(w, v).
3

---

5(U2 v)
s(w, = 0.01
s(U v) 0.50
s (uz, v) = 0.8
Case 1
s(u, v) = 0.51
Case 2 s(w, v) 0.49
s(uz.)) v)
s(u,
s(Uz,) v)
First category of methods
s( v)
s(ug, v)
S 0
s(Ug. v)
s(Ug,
s v) 5 s(19, s(UGr v)
s(u,
s
Second category of methods
s suss v)
s(17, v) s(us,
s(ug, v)
s(u,, v) s(120. v) s(ty v) s(u,
Discrimination and monotonicity properties. We star nodes denote nodes with large p(u(v), round nodes to denote nodes with intermediate p(u/v) and rectangle nodes to denote nodes with small p(u/v). We assume that p(ui/e) p(u2(u)
Figure 1:
p(unolu).
The discrimination property bears subtle difference from the monotonicity property. Let look at an illustrative example in the first line in Figure For the central node U, we assume that p(u, (u) 0.45, p(u2/e) 0.4 and p(w(e) 0.001. Case 1: If s(u,, v) = 0.7, s(u2, v) 0.8 and s(w, v) = 0.01, the final node embeddings satisfy the discrimination property (s(wa) 0.0143 and ((an.))
a(w,)) 0.0125, both approaching zero) but do not satisfy the monotonicity property (p(u) [u) > p(ug ()) but s(1, u) < s(w,, v)). Case 2: If s(u,, u) 0.51, s(u2, 7) 0.50 and s(w, v) 0.49, the final node embeddings fulfill the monotonicity property (s(u1, 6) > 8(u2, v) > s(w, v)) but do not satisfy the discrimination property ( (slui,e) 1.04 and s(wa.0) 1.02). From the above example, =(w,²)
we can see that the discrimination property focuses on making node pairs with large proximity closer and pushing away node pairs with small proximity in the embedding space, which is desirable for tasks like binary classification for link prediction (i.e., predicting the existence of a link between two nodes). On the other hand, the monotonicity property pays more attention to the rank of the similarity scores of node pairs, which critical for tasks like ranking for node recommendation.
2.1 Possibility Results in the Ideal Case
We conduct theoretic analysis about the loss function of network embedding. Previous works 24 37|55) have demonstrated that most existing network embedding algorithms can be regarded as implicit matrix factorization and there exists general form of loss function for the given central node If the sigmoid function is adopted as the similarity function. The loss function is:
J = - Eu-p(()))) log o (F(u;) F(u,:) kkE: (w/v) log(1 o (F.,,))) F(e,:)) (F(,,)))F((.:)
(L)
where (-) is the sigmoid function, F(u,)) :). Fl..:) and F F(w,:) are the embeddings of u, and respectively, and & the number negative samples for each positive sample. If the sigmoid function is replaced by other similarity measurements, can obtain more general form of this loss function:
J - log(s(u, v)) kE (w)))) log(1 s(w, u))
where s(.,,) -) is general form of similarity measurement.
In the ideal case where infinite number of positive samples from p(ulv) are available, have the following theorem about the optimal solution of s:
Theorem Optimal Solution of s. The optimal solution of the similarity function s satisfies that for each node pair (u, v).
p(u/v)
s(u, v) p(u/v) + (ulv)
(3)

---

Proof.
J p(=(((p)))) log s(u, v) kB k (wrlv) log(1 s(w,e)
(4)
Since s(u, v) is the parameter to be optimized, we can calculate V Vo(u,o) as following:
V Va(u,e) -p(ul() s(u,v) (ul( s(u, r)
(5)
p(ale) Let the derivative to be 0, we can obtain s(u, v) = plal))+ppp(up)) which the optimal solution for J.
With the optimal solution of s(u, v/), we give the following proposition about the design of pa: Proposition 1. The Design of Negative Sampling. In the sampling- saallngg--sadd network embedding process. the negative sampling distribution Pn should be negatively correlated with the given node pair proximity distribution p to fulfill the monotonicity property.
Proof. Here we prove the above proposition in the ideal case by contradiction: In the ideal case, assume that the best embeddings and corresponding similarity scores to satisfy the discrimina- tion property and the monotonicity property obtained with Pn. and pv, is not negatively cor- related with p. It is equivalent to the situation that for one central node v, there must exist two nodes u, with p(ulv) > p(w[e) and Pn (ulv) Pn (wwl)). From Theorem ! we know p(ule)
that s(u, = (pp and s(w, v) kpa Now, we interchange pn (ulv) with Pa (w]lv) and we can get new similarity scores s'(u, v) and s'ww, e) for (u, v) and (w, v). p(w/v) s(u, v). In addition, s'(w, v) +kp,
p(w]u)
(uu, v) p(..
p(ulu)
p(ule)
s(w, v). So, we get two new similarity scores that can satisfy the monotonicity property better, which is contradictory with the assumption that we have already achieved the best embeddings and corresponding similarity scores.
p(w[o)
Intuitively, this proposition makes sense because if one node is more likely to be sampled as a positive sample for the central node, it is less likely that this node also acts negative sample.
From Theorem I we can see that if Pn. negatively correlated with p, when p(ule) is large and Pn (ulv) is small, s(u, v) + 1; and when p(u v)) is small and p.. (u/c) is large, s(u, v) 0, which satisfies the discrimination property. For nodes in the network with p(ui (()lw)== >> p(uglu) > ....> p(u,,u), if we set pv, (ullv) < Pu (u2lv) < < Pre (u,/))) the monotonicity property can be fulfilled with s(u1, v) > s(U2, v) > ... s(Un, v).
2.2 Impossibility Results in the Empirical Case
However, in real-world applications, we can not sample an infinite number of nodes from p(u v). Empirically, existing algorithms fixed number T' of positive samples for the central node and the general loss function in Eq. ( turns into:
T
KT
Je T
Σ 1=1
())
T Σ log(1 - s(w;, 2))
1
(6)
where u; is positive sample from p(ule) and wi is a negative sample from (w]v). We use = [s(u], v), sw2, .., [U,, w)] to denote the final similarity scores to be optimized w.r.t the central node v. For the general loss function in the ideal case, the optimal solution of S is S*, where p(u/vv)
S p( (w]lo)> ........> p(u, (op,,, Io. For the loss function Je in the empirical case with positive samples from p, we represent the optimal solution as S.. For the mean squared error between S* and Se, we have the following theorem:
p(u,lo)
Theorem 2. Mean Squared Error. For the mean squared error between the empirical optimal solution S. and the ideal solution S*, we have
B[II(S.-S")all
(7)
T(2+ (pp( + p(u
p(ulu)
kpp,
(ulu)
p(aee) kp= []
where E. is the expectation and (S. - S) m = se (u, v) (u, v) is the error between the optimal similarity scores obtained in the empirical and ideal cases respectively.
5

---

The proof for Theorem 2 is attached in Appendix A.] If the sigmoid function is adopted as the similarity function, the expectation of the similarity error in Theorem degenerates to its special case:
(llFF((,))) FF(,,) - F (",
1 Fc T p(ulo)
+ kpn(ulu)
x)
(8)
where F. (u, ;) and F (u.3 :) are the optimal embedding vectors of node u in Je and J. Eq. ( was first discovered in MCNS 55 Based on Eq. (8) MCNS advocates that, in order to bound the dot product error for nodes with large p(u(e), Pa should be positively correlated with p. Unfortunately, this not always the best choice due to the following reason. In MCNS, the authors set Pr (u w) X p(ulu)),
where 0- < a < 1. With this negative sampling distribution, the right part of Eq. 8 changes into p(ulu)"")-
T (oocp) (1 + e -1 }. where is constant. If p(ulo) is large, this term can indeed be bounded. However, for distant nodes with small p(ule) (i.e., p( ([(v)) - 0), its positively correlated negative sampling probability Pu(uu)) is also very small and (a(uu) O, which leads to an extremely large error considering that the term p(ulo) + kpp(uluj + 00, which may fail to fulfill the discrimination property.
Discussion. Let us analyze the implications of Theorem 2 If (u(lu))) is negatively correlated
with p(ule), it means that kpp (x/r)
p(ujo] + 0o for nodes with the smallest p(ulu)s. Let us consider the case that p(u/o) is large and (pp(ul)) + O. 1
p(u(v) - O for nodes with the largest p(ulu)s and (p=(wlo)
p(ujo)
B]][(S, - 5*x >ull) < T( (eape )2 (p(ulo) + kpa(wlp) - -1 1) < ( (&pa (eadll )(( ((pule)) + kp.. (pp,((l))) )²
1
1
can be rewritten as ((( p(ule) p(ulv) + (p.(al)) p(ule) p( ). Since p(ule) is among the largest proximity scores, piuluj is approximately bounded by a finite number 1 where is the number of )² p(ulo) -> 0. Therefore, for nodes with large p(u) p(u|e), the empirical embedding similarity score se(u, v) R s (u.v). With similar analysis on nodes with small p(ulp). we reach the same conclusion that se se(u, v) R (u,v), v). Based on the above analysis, we can see that the empirical optimal solution can achieve the discrimination property with a negatively correlated pn: for node pairs with large/small p(u (())))) their similarity scores approach the ideal optimal solution. However, there might exist some nodes with p(uje) = hp,((uu)) (ulv). which are referred to as nodes with intermediate p( u v). For these nodes, the error in Theorem 2 is
nodes in the network. As result, p(ule) p(ulo) - 0 and ( ((pm(a)))
(pl())))
p(ulp)
(pp((ule) + pfule) )² acchevess its minimum larger than nodes with small/large p(u(v) v) because (2 + p(ulv)
when p(u/v) = (ulu). This can also be explained intuitively as follows. Nodes with large p(u(v) and large pa, (u) (small p(u(e)) are always sampled as positive samples and negative samples, while nodes with intermediate p(u v) and pr. (ulv) might be ignored and are less likely to be sampled as positive samples or negative samples. As such, the embedding similarity scores for these nodes bear more uncertainty and large error between the empirical optimal solution and the ideal optimal solution (Theorem
With these findings, we now unveil the underlying reason for the competing sampling strategies in existing methods. The first category of methods (e.g., (36 14 23) champion sampling nodes with longer distance from the given central node as positive samples. The essence of this positive sampling strategy is to include more nodes with intermediate p( p(u(e) ())v)) in the positively sampled node pair set. In this way, these methods realize the goal minimize the error in Theorem 2 for these nodes with intermediate p(u)r). However, this design has cost. When choosing more nodes with intermediate p(ule) as positive samples, it implicitly decreases the p(ulv) for nodes with large p(ulp) (since Σ. p(u(v) = 1). As shown on the second line in Figure [ it hurts the monotonicity between these nodes (round nodes) and nodes with large p(u u) (star nodes). On the contrary, for the second category of methods (e.g., 4 56 (55), ), they prefer to select nodes with intermediate pl (u)))) as difficult negative samples in the recommendation task, they successfully fulfill the monotonicity property between nodes with large p(uje) (star nodes) and nodes with intermediate p(u (u)))) (round nodes).
Unfortunately, as our discussion about Eq. (8) has demonstrated, this pasitively correlated negative sampling distribution could make the empirical enror of the embedding similarity scores of nodes with small p(ulv) quite large. It does harm the discrimination property, which is shown on the last line in Figure (c.g.. g. s(ug, v)).

---

To conclude, due to the limited number T of positive samples, the empirical loss tends to sample nodes with large p(ule) or Pa (ule) and there always exist some nodes that can not be sampled as positive/negative samples and thus are ignored. Therefore, the discrimination property and the monotonicity property for all node pairs in the network can not be satisfied simultaneously in the empirical situation.
Model
In many real-world applications, given the query node, we primarily care about the top- K recom- mendation list. This suggests that we only need to satisfy the discrimination property and the partial monotonicity property within nodes that are likely to appear in the top- K recommendation list. Guided by this and the theoretical results in Section 2 we propose simple yet novel model named SENSEI.
Key Idea. The key idea of SENSEI is to seamlessly integrate two competing sampling strategies into one model together. Concretely, means that we can decompose the proposed SENSEI into two steps. The first step is to satisfy the discrimination property and the second step is to achieve the monotonicity property within nodes that are likely appear in the top- recommendation list. As shown in Figure 2 in the first step, SENSEI samples nodes with intermediate p(ulu), which is the strategy by the first category of methods mentioned in Section 2 SENSEI constructs a combined positive sample set, including nodes with large p(u[v) and nodes with intermediate p(ule). During the training process, SENSEI treats these nodes equivalently as positive samples and maximizes their similarity scores with the given central node. At the same time, it minimizes the similarity scores for nodes with small p(ule) (large Pr, (u(v)) to fulfill the discrimination property. In the second step, SENSEI focuses on the difficult negative samples, which is the strategy by the second category of methods in Section 2 SENSEI pays attention to the monotonicity property within the combined positive sample set in the first step. In detail, the previously sampled positive nodes have two roles: they act as the positive samples compared to nodes with smaller p( ((ule) in the first step and meanwhile function the difficult negative samples compared to nodes with larger p(ule) b) in the second step.
Details. For p(u/c), we run personalized pagerank (33]. which is used throughout SENSEL. In addition, embeddings to have unit L2 norm and adopt the dot product (F(u,:) (o, F(e,)) as the similarity function s(,, v).
s(UG,
s(t
s(Ht.. V)
s(u..o)
S(Mau e))
s(14..
=(Hg.
s(ugg u) Step 1
s(ug, v)
s(Mr v)
normalize node
s(H
s(UL)))
a(M
s(M
s(Ma.e)
s(1b m))
5(17,0) s(1 v)
Step 2
Step 1: Fulfill the Discrimination Prop- erty. In this step. to satisfy the dis- crimination property, we construct com- bined positive sample set P(v) for e in A, which includes nodes with large and intermediate p(ulu). Specifically, we rank the proximity p(ulv) for all nodes in A to obtain a descending list [p(u)lo) p(uzlv) ... p(u, lv)]. Then, we set a threshold r. Nodes with p(u/o) > r form the combined positive sample set
s(ú,,))
s(us, v)
s(H;.
s(tho.
s(Mg.
s(ug. v)
s(Gy,,
s(U,,, v)
s(MG. v)
Figure 2: The training process of SENSEL Similar to Figure T we still utilize star nodes to denote nodes with large p( (() round nodes denote nodes with interme- diate p( o/upp and rectangle nodes to denote nodes with small p(u(p). In Step 1, SENSEI includes round nodes (nodes with intermediate p(ulv)) as positive samples. In Step 2, the round nodes used as hard negative samples for the star nodes.
.(u,,
P(v) for the central node v and the re- maining nodes added into the set (v)), where negative samples will be randomly selected. So, the loss for node is:
m=
(v)
Σ (kF(u,)) F(U::) (EP(v)
- Σ F F(wms:) F(u.))) m=1
(9)
PP()
where i: the negative sample number for each positive sample, u the positively sampled node for and Wm E (N))) is the negatively sampled node. By adding the loss for all es in A. we obtain the
7

---

overall loss in Step as:
Jp = Σ ((0)
(10)
DEA
Step 2: Fulfill the Partial Monotonicity Property. In this step, we focus on the partial monotonicity property within the combined positive sample set in Step 1. For any two nodes uy and Vym in the positive sample set P()), if p(u)(p) (D) > p(um(v), we want to retain the monotonicity between them with F(ur,:) :) F(u,:) :) > F F(um;:) :) F(V,:). . Node un changes from a positive sample for in Step 1 to negative sample for compared with uy, which is consistent with the idea of sampling difficult negative samples. The margin-based ranking loss is:
L(v) Σ -p (max F( F(u;:) F(u,;) (F(e, + 7,0
(11)
the indicator function and yy is positive margin. When p(ull)) ) > p(um/v). 1 ppppp.) In) 1, otherwise, [p(m/e))xp(mm.l)) O. Similar to Eq. (10) in
where wi, um E P(v), 1 p(aale)>p(um
Step 1, we have the loss Lp in Step 2 as:
Lp Σ L(v). DEA
(12)
In fact, Step 2 can be regarded fine-tuning process fulfill the partial monotonicity property. Therefore, this step usually has a small learning rate and a small positive margin 7y. The pseudocode of this algorithm can be found in Appendix A.2
Complexity Analysis. We give a complexity analysis of SENSEI here. For SENSEI, the time com- plexity can be analyzed as the following: (1) Calculating personalized pagerank has the complexity Oiterr ||&|)), where ||E|] the number of edges in the graph and itermax is the maximum itera- tions or hops for personalized pagerank; (2) the time complexity for sorting the proximity distribution p(ulu) and sampling positive/negative nodes for node is O(n log(n)); (3) Calculating (() takes ((IP()))II d). where [|P())]] is the positive sample set, l is the number of negative samples and is the dimension of node embedding. Obtaining Jp takes (n)) time; (4) Computing L(v) in Eq.
(IT) takes ((I[(())]] [[2] d) and calculating Tnp costs O(n). Most of these computations can be further
parallelized.
4 Experiment
In this section, we evaluate the effectiveness of the proposed algorithm (SENSEI) for solving link prediction and node recommendation simultaneously in plain networks.
4.1 Experimental Setup
Datasets. We use 4 public real-world datasets to evaluate the proposed SENSEI model: C.cle [1] Cora 39
Citeseer (39] NS (3I].
Baselines. We compare the proposed SENSEI with the following 5 plain network embedding methods:
node2vec [1. VGAE 222] GAT 4 ARGVA 35 and RBGE [17]
Metrics. For link prediction and node recommendation in plain networks, we randomly split edges in every dataset into 70/10/20% for training, validation, and test 2 The same amount of additionally sampled non-existent edges are taken as negative edges for training, validation and test the link prediction task.
Settings. For the link prediction task in plain networks, we use Area Under the ROC and Precision- Recall Curves (i.e., AUC-ROC and AUC-PR) as the metrics to evaluate the performance of different methods. For the node recommendation task in plain networks, we take Hit@ K as the metrie. Only when the model ranks the correct node as top-K in the recommendation list, it is counted as a hit for this query node in the test set. Therefore, the average hit number for query nodes Hit@ K. We set K 10 for SENSEI.
"The node recommendation task in plain networks is to recommend potential nodes that are most likely to have edges connected the query node.

---

Additional Contents. In Appendix, we provide more contents related to experiments, including (1)
dataset statisties (Appendix A.33): (2) implementation details (Appendix |A.3;; (3) the companson with additional GCN-based methods: GraphSAGE 15
Cluster-gen S APPNP 13
GPRGNN 6
and H2GCN
63
(Appendix A.4).
4.2
Effectiveness of SENSEI
Table 1: The AUC-ROC (tstdd) and AUC-PR (+std) of link prediction in plain networks (%)
Models
AUC-ROC
AUC-PK
AUC--OU
Choseer
AUCCPR
ATC--DX
AUC-PR
ACC-ROC
AFC.PK
mode2ve 1+
18
82.7520.60
69.6-00.97
77.3610.88 89
86.4K10.76
91.3610.75
79.36.1.1
74.27=:1.33
VGAB
78.28:40.53
72.58=0.74
78.001:0.44 40
86.45.0.955
89.99:1.558
77.284-.399
73.50:22.38
GAT [4
76.4:40.77
78.90=11.03
71.79=1.40
76.04+1.118
85 85.8940.84
88.47
74.1644.33
71.21=1.69
ARGVA
75 99999.977
78.11=1.14
71. 71.96-1.70
74, 74.7441:0330 59
88. 18,55+1.12
90.324
77.04:1:71
71.29=2.42
RRGE
[7]
79.334+0.56
80.11
73.89=1.11
77.48+1 1.30
43.96-4.211
28.7742.77
7465444.54
32.07=3.70
SENSEI
01.2730.65
83.59 1 11
76.28 0.90
0.
91.42 1.25
93.10:0.77
77.3330.81
77,28
The results of link prediction on all 4 plain networks are presented in Table [
Our proposed SENSEI
generally outperforms all baselines on all 4 datasets. In particular, SENSEI achieves about 2% improvement in AUC-PR compared to the best competitor (e.g.. VGAE on Citeseer and node2vec on C.ele). For the node recommendation task, as shown in Table node2vee obtains the best @it@@ 10 on Cora and NS among all baselines, which indicates that including more positive samples (7) by setting larger walk length (80) can indeed reduce the error in Theorem 2 Notice that the proposed SENSEI still outperforms node2vec on all 4 datasets, which demonstrates the ability of SENSEI to fulfill the partial monotonicity property.
Table 2: Hit@ 10 (+sld) of node recommendation in plain networks (%).
Models
Cora
Cheseer
NS
Cole
node2veel [4
19.78:00.84
18,50-E1.38 .30
59.8822.68
9.43 41
VGAE
1.62
8.93.10.91
37,26 2.336
9.34.11.32
GAT [3
5.77=0.64
5.99:2.22
53.96:25.39
9.71
ARGVA 35
1.65
4.71.10.56
36.78
9.71
RAGE
1x
1.21
18.99
58.48:1..18
9.48:14.86
(ENSEl(Wo Step 2)
1.88241.18
18.1741..11
61.01
11.07:2.
SENSEI
20.51=1.118
19.03+1.500
61.31=3.46
11.52:+2.13
4.3 Ablation Study and Sensitivity Study
In this subsection, we conduct the ablation study to validate the importance of Step of SENSEI. As illustrated in Table 2 for the node recommendation task (Hit@) 10), Step 2 consistently improves the performance of SENSEL. The results verify that Step 2 is indeed beneficial by fine-tuning node embeddings to satisfy the partial monotonicity property. In addition, we carry out sensitivity study on different K's for @it@ K, which is presented in Figure We observe that when increases from 1 to 30, @it@ K gradually increases and @it@ 30 is much higher than Hit@ 1, which is expected.
5 Related works
Network Embeddings. Network embedding maps nodes in the network low dimensional vec- tors. It can be traced back to matrix low rank approximation [26] and spectral clustering [40]. DeepWalk (36] and node2vec [14] rely on random walk encode the topological information of homogeneous networks. For multi-layered networks or heterogeneous networks, metapath2vec
7 and Hin2vec [10] design metapaths to capture the connectivity between different layers or different types of nodes. Since graph convolutional network (GCN) [2I] emerges, many GCN- based network embedding methods have been proposed. For example, variational graph auto- encoder (VGAE) (22) adopts the same message-passing mechanism as GCN to embed the homo- geneous network. More recently, GCN has been integrated with random walk based heterogeneous network embedding methods, which leads to heterogeneous graph convolutional networks like MAGNN [ and HAN [50]. MANE [25] successfully employs network embedding on multi- layered networks and DMGC (2 accomplishes both network embedding and clustering by utilizing cross-layer links as regularization. In addition, many embedding algorithms for knowledge graph have been proposed such as translational distance model 3 and semantic matching model (32).

---

Sampling in Network Embedding, Sampling is an important technique, which appears recommenda- tion [4 and text embedding [30 to speed up the training process. For network embedding algorithms,
100
Cora
NS
80
Citsseer
C.ele
both the positive sampling strategy and the negative sampling strategy have been applied and improved. For matrix factorization [26], spectral clustering [40] and LINE 4T, direct or two-hop neighboring nodes act positive samples and negative nodes are sam- pled uniformly or according to the degree distribution. In Deep Walk [36], node2vee [4 and metapath2vec
Httr (%)
60
40
20
7 the positive sampling strategy is modified based truncated random walk starting from the central node. The positive and negative sampling are im- plemented implicitly with mnssagg--psssingg mech- anism in GCN-based methods, where nodes to be aggregated can be viewed as positive samples and the remaining nodes are implicit negative samples. For the GCN related works, efforts are mainly made improve the positive sampling strategy. For example, APPNP [3] manipulates positive samples with personalized pagerank [33] to catch long distance information and PGNN [58] randomly fixes an anchor node set for aggregation in each training epoch. Recently, more attention has been paid to improve the negative sampling strategy. Many works suggest to sample closer nodes as difficult negative samples. For instance, MCNS (SS] proposes that the negative sampling distribution should be positively correlated with the positive sampling distribution. KBGAN [4] samples most similar entities to replace the groundtruth positive entity in knowledge graph embedding and RecNS (56) tends to sample negative nodes from the intermediate distance region.
5
10
15
20
25
30
Figure Hit K for SENSEI.
6 Conclusion and Limitations
In this paper, we study the sampling strategies of network embedding. To uncover the underlying relationships of existing competing sampling strategies, conduct theoretical analysis the sampling-basee based network embedding process. In the analysis, we identify two desirable properties for the similarity scores of node embedding, including the discrinination property and the monotonicity property. Furthermore, we prove that there always exists an error gap between the empirical and ideal optimal embedding similarity scores. Guided by such analysis, we propose a simple yet novel model (SENseI), which creatively integrates the two competing sampling strategies to fulfill the the discrimination property and the partial monotonicity property. The effectiveness of SENSEI is verified by extensive experiments.
This paper studies sampling strategies of network embedding, which has no negative ethical impacts on society. The limitations of our paper lie in that the theoretical analysis is conducted on proximity scores and the proposed SENSEI model is designed for plain attribbbb) networks rather than attributed networks. The key to generalize the proposed properties/SENSEI model to attributed networks is a new definition of the node pair similarity, which we leave for future exploration.
Acknowledgement
This work is supported by NSF (1947135, 2134079, 2316233, 1939725, and 2324770), DARPA (HR001121C01655) NIFA (2000-6002-337799) DHS (17STQAC00001-007-00) ARO (W911NF21 10088). The content of the information in this document does not necessarily re- flect the position or the policy of the Government, and no official endorsement should be inferred. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.
References
[1] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Fe-net: Exploitation-exploraaii neural networks in contextual bandits. arXiv preprint arXiv:2110.03117, 2021.
10

---

[2] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Neural exploitation and exploration of contextual bandits. arXiv preprint arXiv:2305.03784, 2023.
[3] Antoine Bordes, Nicolas Usumier, Alberto Garcia-Dural Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi culli-relational data. Advances in neural information processing systems, 26, 2013.
[4] Liwei Cai and William Yang Wang. Kbgan: Adversarial learning for knowledge graph embed- dings. arXiv preprint arXiv: 1711:1111.000 1.0071, 2017.
[5] We Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 257-266, 2019.
[6] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
[7] Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In KDD '7, pages 135- ACM, 2017.
[8] Boxin Du, Si Zhang, Yuchen Yan, and Hanghang Tong. New frontiers of multi-network mining: Recent developments and future trend. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 4038 4039, 2021.
[9] Dongqi Fu, Liri Fang, Ross Maciejewski, Vetle I Torvik, and Jingrui He. Meta-learned metrics over multi-evolution temporal graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 367-377, 2022.
[10] Tao-yang Fu, Wang-Chien Lee, and Zhen Lei. Hin2vec: Explore meta-paths in heterogeneous in- formation networks for representation learning. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 1797-1806, 2017.
[1I] Xinyu Fu, Jiani Zhang. Ziqiao Meng, and Irwin King. Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding. Proceedings of The Web Conference 2020, pages 2331-2341, 2020.
[12] Hongchang Gao and Heng Huang. Self-paced network embedding. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1406-1415 1415, 2018.
[13] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank, arXiv preprint arXiv:1810.0555 2018.
[14] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 355-864, 2016.
[15] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[16] Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference on Machine Learning, pages 8230-8248. PMLR, 2022.
[17] Zexi Huang, Arlei Silva, and Ambuj Singh. A broader picture of aandom-walk based graph embedding. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 685-695, 2021.
[18] Baoyu Jing, Hanghang Tong, and Yada Zhu. Network of tensor time series. In Proceedings of the Web Conference 2021, pages 2425-2437, 2021.
[19] Baoyu Jing, Yuchen Yan, Kaize Ding, Chanyoung Park, Yada Zhu, Huan Liu, and Hang- hang Tong. Sterling: Synergistic representation learning on bipartite graphs. arXiv preprint arX1v:2302.05428, 2023.
[20] Baoyu Jing, Yuchen Yan, Yada Zhu, and Hanghang Tong, Coin: Co-cluster infomax for bipartite graphs. arXiv preprint S.X1:22066000000 2022.
[21] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint urXiv:1609.0220 2016.

---

[22] Thomas N Kipf and Max Welling. arXiv:1611.07308, 2016.
Variational graph auto-encoders.
arXiv preprint
[23] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemamn. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:/810.05997 2018.
[24] Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances in neural information processing systems, 27, 2014.
[25] Jundong Li, Chen Chen, Hanghang Tong, and Huan Liu. Multi-layered network embedding. In Proceedings of the 2018 SIAM International Conference Data Mining, pages 684-692. SIAM, 2018.
[26] Chih-Jen Lin. Projected gradient methods for nonnegative matrix factorization. Neural compu- lation, 19(10)22756-2779 2007.
[27] Hongyi Ling, Zhimeng Jiang, Meng Liu, Shuiwang Ji, and Na Zou. Graph mixup with soft alignments. arXiv preprint arXiv:2306.0677
2023.
[28] Lihui Liu, Boxin Du, Jiejun Xu, Yinglong Xia, and Hanghang Tong. Joint knowledge graph completion and question answering. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 1098-1108, 2022.
[29] Dongsheng Luo, Jingchao Ni, Suhang Wang, Yuchen Bian, Xiong Yu, and Xiang Zhang Deep multi-graph clustering via attentive cross-graph association. In Proceedings of the 13th international conference on web search and data mining, pages 393-401, 2020.
[30] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed repre- sentations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
[31] Mark EJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74(3):036104, 2006.
[32] Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multi-relational data. In leml, 2011.
[33] Lawrence Page, Sergey Brin, Rajeev Motwani, and Temry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
[34] Rong Pan, Yunhong Zhou, Bin Cao. Nathan N Liu, Rajan Lukose, Martin Scholz, and Qiang Yang. One-class collaborative filtering. In 2008 Eighth IEEE International Conference on Data Mining, pages 502-511. IEEE, 2008
[35] Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chenggi Zhang. Adversarially regularized graph autoencoder for graph embedding. arXiv preprint WiXiv:180..044000 2018.
[36] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[37] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pages 45594677,5 201 8.
[38] Shane Roach, Connie Ni, Alexei Kopylov, Tsai- Srai-Ching Lu, Jicjun Xu, Si Zhang, Boxin Du Dawei Zhou, Jun Wu, Lihui I. Liu, et al. Canon: Complex analytics of network of networks for modeling adversarial activities. In 2020 IEEF International Conference on Big Data (Big Data), pages 1643. IEEE, 2020.
[39] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. magazine, 29(3):93 93, 2008
[40] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-908 2000.
[41] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. In Proceedings of the 24th international conference on world wide web, pages 1067-1077, 2015.
[42] Yuxin Tang, Zhimin Ding, Dimitrije Jankov, Binhang Yuan, Daniel Bourgeois, and Chris Jermaine. Auto-differentiation of relational computations for very large scale machine learning. arXiv preprint ar0iv:2366. 3008000800.0.0000000008888880 2023.
12

---

[43] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10900 2017.
[44] Dingsu Wang. Yuchen Yan, Ruizhong Qiu, Yada Zhu, Kaiyu Guan, Andrew Margenot, and Hanghang Tong. Networked time series imputation via position-aware graph enhanced vari- ational autoencoders. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2256-2268, 2023.
[45] Ruijie Wang. Baoyu Li, Yichen Lu, Dachun Sun, Jinning Li, Yuchen Yan, Shengzhong Liu, Hanghang Tong, and Tarek F Abdelzaher. Noisy positive-unlaheled learning with self-training for speculative knowledge graph reasoning. arXiv preprint arXiv:2306.07335 2023.
[46] Ruijie Wang, Zheng Li, Dachun Sun, Shengzhong Liu, Jinning Li, Bing Yin, and Tarek Abdelzaher. Learning sample and aggregate: Few-shot reasoning over temporal knowledge graphs. Advances in Neural Information Processing Systems, 155166633-68766 2022.
[47] Ruijie Wang. Zheng Li, Jingfeng Yang, Tianyu Cao, Chao Zhang, Bing Yin, and Tarek Ab- delzaher. Mutually-pacee paced knowledge distillation for cross-lingus temporal knowledge graph reasoning. In Proceedings of the ACM Web Conference 2023, pages 2621-2633 2023.
[48] Ruijie Wang. Zheng Li, Danqing Zhang, Qingyu Yin, Tong Zhao, Bing Yin, and Tarek Abdelza- her. Rete: Retrieval-enhanced temporal event forecasting on unified query product evolutionary graph. arXiv preprint arXiv:2202.0611 2022.
[49] Ruijie Wang, Yuchen Yan, Jialu Wang, Yuting Jia, Ye Zhang, Weinan Zhang, and Xinbing Wang. Acekg: A large-scale knowledge graph for academic data mining. In Proceedings of the 27th ACM international conference on information and knowledge management, pages 1487-1490, 2018.
[50] Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Het- erogeneous graph attention network. In The World Wide Web Conference, pages 2022-2033 2019.
[51] Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world" networks. nature, 393(6684):444-442 1998.
[52] Yuchen Yan, Lihui Liu, Yikun Ban, Baoyu Jing, and Hanghang Tong. Dynamic knowledge graph alignment. In Proceedings of the AAAI conference on artificial intelligence volume 35, pages 4564 4572, 2021.
[53] Yuchen Yan. Si Zhang, and Hanghang Tong. Bright: A bridging algorithm for network alignment. In Proceedings of the Web Conference 2021, pages 3907-3917, 2021.
[54] Yuchen Yan, Qinghai Zhou, Jinning Li, Tarek Abdelzaher, and Hanghang Tong. Dissecting cross-layer dependency inference on multi-layered inter-dependent networks. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 2341-2351, 2022.
[55] Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, and Jie Tang. Understanding negative sampling in graph representation learning. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1666-1676 2020.
[56] Zhen Yang, Ming Ding, Xu Zou, Jie Tang, Bin Xu, Chang Zhou, and Hongxia Yang. Region or global a principle for negative sampling in braph-based recommendation. IEEE Transactions on Knowledge and Data Engineering. pages 2022.
[57] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[58] Jiaxuan You, Rex Ying, and Jure Leskovec. Position- aware graph neural networks. In Interna- lional Conference on Machine Learning, pages 7134-7143. PMLR, 2019.
[59] Zhichen Zeng, Boxin Du, Si Zhang, Yinglong Xia, Zhining Liu, and Hanghang Tong. Hierarchi- cal multi mallinaarriinal optimal transport for network alignment. arXiv preprint arXiv:2110.04470, 2023.
[60] Zhichen Zeng, Si Zhang, Yinglong Xia, and Hanghang Tong. Parrot: Position-aware regularized optimal transport for network alignment. In Proceedings of the ACM Web Conference 2023, pages 372-382, 2023.
13

---

[61] Qinghai Zhou, Liangyue Li, Nan Cao, Lei Ying, and Hanghang Tong. Admiring: Adversarial multi-network. mining. 2019 IEEE International Conference on Data Mining (ICDM), pages 1522-1527. IEEE, 2019.
[62] Qinghai Zhou, Liangyue Li, Xintao Wu, Nan Cao, Lei Ying, and Hanghang Tong. Attent: Active attributed network alignment. In Proceedings the Web Conference 2021, pages 3896-3906, 2021.
[63] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs, Advances in Neural Information Processing Systems, 13:7793-78044 2020.
14

---

A
Appendix
The appendix is structured as follows:
Subsection
A.1
gives the proof of Theorem 2
Subsection
A.2
gives the detailed algorithm of SENSEI;
Subsection
A.3
introduces the statistics of datasets and the implementation details of SENSEI;
Subsection A.4
compares the performance of SENSEI with 5 additional GCN baselines (Cluster-gen, GraphSAGE, APPNP, GPRGNN and H2GCN) Cora and Citeseer.
A.1 Proofs
Theorem 2. Mean Squared Error of S between the Ideal Loss and the Empirical Loss. For the mean squared error between 5* and Se, we have
(S
1
1
(13)
T(2+
(pl(ulv) p(ule) p(u
p(u(o)
kpm(ulv)
where E. is the expectation and S*
pl
p(u.
kp (w1lo)
p(an kP
Proof. In this proof, since S = [s(u1, v), s(u2, u).... sun, v)] is the parameter to be optimized, write the empirical loss Je function of S JS(... We prove this theorem with the help of Taylor expansion of (S.) around S*. Because S. is the solution to minimize Je. sSJ)((e) So, it can be expressed as:
(..( V)Je((*) + V - S*) O(IIS. 1²)
(14)
Thus, up to terms of order O(1SS, - 5*113), we obtain
S. - S* = (V
(15)
Then, we discuss the term - (S)) and the term VsJa(S*) respectivlly.
For the term -VV) -1, let ((,)) be the one-hot vector, where only the u--th entry is 1.
kT log(1
J.(S) + Σ log(s(u.,,)) b))
s(w;, v))
T
VsJ.(S) 1
Σ
1
s s(u,, v)
e(u))
T
s (wi, v) (uxg)
1=1
i=1
(16)
T
RT
V.J.(S) 1
T
1
Σ
8 w)2
((u))((u)
+
T
(s(ws, 1.) 1)2 O e(m
1=1
i=1
T
kT
V.J.(S) -
Σ
s(ui, w)2
(( [(.))
T
Σ
(s(we, 1) (vor) ((w)))
1=1
Since 8" (w; (kp. and 8² s"(w,,,, v) plw; kp..kll
p(u.lo)
p(w.lw)
1 (p(w.lv) + (us (o))²
-V =
+
(
p(uc/u)²
(17)
(p(wylu (u) + (wp.p/wwwl))) ((m;)e(m)) (kp... x²
15

---

Therefore,
Σ p(us/o) (p(u)le) + (u.((u))))) ((u))
lim V3Je(S") 7-+00
p(u:ln²²
Σ (wsl())))) (p(m))u) + kpm (u)
(kp.(wulv))
((w,)
(18)
(p(u)l)) + (p, (p,(u,))ppplll
((u))))))
where the last line is because that we combine same terms when u, = Wi.
Then, we consider the second term Ve*)(S"). We analyze the expectation and variance of ssJe(S*) to get the final [S| (-)=
For the expectation, as VsJ)(S) as follows:
RT ( v) ((r,)
VsJe(S)) T
slU;, ((u,)
(19)
the expectation is:
S[VsJ((S')] = Σ p(us (o) p(usle) + (u: e(u.)
p(ul/e) (8)
(w:(w:))) p(w/lu) un) kpp v))
(20)
kp (wa (b)
((rr)
0
For the variance VsJe(S*), since E.VsJ((S*) =0
= =
Bumpfu w)
s- 0)2 T
T2
KT
Branoen (m/n)) (1 8* u))a je(
T2
Σ T(T 1) p(uclu)p(uslo)
1
+
(w), 8* (u5, v) (m:))))))
(21)
2T
Σ wp.wy
T (20,1))
8* su v) 1 (wy, v) e k(wy)
2T
Σ
T p(u,lo)p..tu (*),, 5* (wv, v) e(w,) ((u))
KK pm (u 8* swi, v) (wij ((n
T2
16

---

Because 8" (ui,
pluc (1)
()
p(a
8 (wi, v)
plu. kpp (u.
plu ()) kpp
p(w, 10)
and s* (w), v) p(wglo)thp, Eq.
plm;lo)
becomes:
(p(ulv) + (ule))
Cov(Vsse(S") T (pn(u(o)p(ul)) (a))(a))
Σ M4.3y
7 (p(usl))
1
kpm (un
Σ (p(u:lu) (pll(( Ap, (uy)
Σ (p(uglo) u) (or, (
(22)
E (1
KT (p(wslo) kp. 1)) (pol
(p(ale) + (ulo)) ((w))(
T Σ
1
(1 + k
(o(udv)) kp. http://wwwuuuuullaooooooo////un-
Based on Eq.
15
Eq.
Eq. and - Cov(Se (T, u). have
Ell (S. s*)n1}]=
1 kp (ule)pp)p(l
(p(ulv) + kpn
T (p(u + kpm (ulo))3
kpn (ul)))(((())
(23)
(1 (p(ulv) + (pp(()))))
kp (ulv)p(uu)) (p(u/v) + (ulo))
which can be simplified
BlI((S, - >='="1
1 (kpp (u ())()())
kpp (ule) + p(ule) 1t
T (p(ulv) + kp (ulv))
kpn (u (2/2))(((11))
(24)
1
7(2 +
AP [uim] p(u.m)
p(ale (mpj) ) p(ulu) kpp((ll)
A.2
The Algorithm of SENSEI
In this section, we give the detailed algorithm of SENSEI in Algorithm
A.3 Dataset Statisties and Implementation Details.
In this section, we introduce the statstics of datasets and the implementation details SENSEI. The statistics of datasets present in Table
Table 3: Dataset Statistics.
Dataset
Layers
Nodes
Edges
C.ele
297
2,148
Cora
2,708
5,429
Citescer
3,327
4,732
NS
1,589
2,742
Implementation Details. For all the methods, we run times to calculate the standard deviation and for all basclines, use their default parameters. For SENSEI 4 datascts: (C.cle, Cora, Citeseer,
17

---

Algorithm The algorithm of SENSEI
Input: (1) the input plain network A; (2) training epochs in Step (Bi) and in Step 2 (E2), hyper-paramelers lc and ry
Output: Node embeddings F.
Initialize F:
for cach in A do
Run PPR to construct P()) and (v) with the threshold
end for
# Step Fulfill Discrimination Property
e = 0:
while < E1 do
for each in A do
Randomly sample negative nodes from (V)): Compute (()) using Eq. 9
end for
Add all J(v)s to obtain Jp in Eq. 10
Back-propagate the loss and update F; 1;
end while
# Step 2: Fulfiil Partial Monotonicity Property 0;
while E2 do
for each v do Compute L(u) using Eq. 11
end for
Add all L(v)s to obtain Lp Eq. Back- paok-propagate loss and update F; e e++1
end while return F.
NS). we set the threshold 7 {0.008, 0.01, 0.005, 0.05). the number of epochs in Step as (40, 100, 20, 20). the number of epochs in Step 2 as (40, 100, 50, 20), the learning rate in Step 1 as (0.02, 0.1. 0.1, 0.2), the learning rate in Step (0.01, 0.01, 0.005, 0.1), the positive margin y (0.05, 0.0001, 0.0001, 0.1) } and the negative sample number & as 40 on all 4 datasets. All experiments are Tesla-V100 GPU.
A.4 Additional Baselines of Plain Network Embedding
have added another GNNs as additional baselines: GraphSAGE [5), Cluster-gen 5 APPNP 13 GPRGNN (6 and H2GCN (63]. the results are demonstrated in Table We can see that for both link prediction and node recommendation, SENSEI generally beats these GNN methods.
Table The AUC-ROC and AUC-PR link prediction and Hit@ 10 of node recommendation on Cora and Citeseer(5).
Models
Cora AUC-PR
Citeseer AUC-PR
AUC-ROC
Hiter ID
AUC-ROC
Hirer 10
GrahhAGGE
Cluster-gen
65.93
72.39
4.65
67.33
70.45
5.42
APPNP 13
68.77
72.39
11.72
66.45
71.57
11.96
GPRGNN 6
64.44
70.15
13.31
62.93
68.69
10.64
H2GCN 68
61.90
18.89
1.96
60.95
61.94
3.53
Thee simplified code of SENSEI is http:://gtthb..cm/yycceeerr////
18


Reviews:
[{"review_id": "Ilz8TcG20w", "reviewer": "Reviewer_fuvb", "summary": "Graph embedding methods typically involve negative sampling, where a set of nodes are sampled as positive samples (usually nodes of close proximity, such as edges) and a set of nodes are sampled as negative samples. While early work tended to randomly sample negatives from non-edges, more recent work has adopted different approaches for negative sampling. The authors identify two main classes of methods for negative sampling in the literature. Their main contribution is identifying two properties that they claim any good set of node embeddings should satisfy: discrimination and monotonicity. They then demonstrate that these two properties cannot be simultaneously satisfied with a finite number of samples. They propose the SENSEI method that satisfies discrimination and a *partial* monotonicity property and demonstrate strong empirical performance.\n\n*After rebuttal:* The authors have clarified my concerns, and I continue to support the paper. I also did not see anything from the other reviews that would negatively affect my opinion.", "questions": "1. The analysis in Section 2 is quite general with respect to the similarity function $s(u,v)$. Sigmoid and cosine functions are mentioned as examples. What requirements must the similarity function satisfy in order for your analysis to be valid? Would, for example, a Euclidean distance-based similarity such as $\\sigma(||\\mathbf{F}(u,:) - \\mathbf{F}(v,:)||_2)$ meet the requirements?\n\n2. It seems that the two properties of discrimination and monotonicity are very much tied to the two tasks that you assume are important: link prediction and node recommendation. However, if one is only interested in link prediction, is there a reason they should care about monotonicity rather than just discrimination?", "limitations": "Limitations are discussed, but not in much detail and only in the supplement. Such a discussion should be moved to the main paper, with a longer discussion in the supplement if necessary.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Provides an explanation unifying different negative sampling strategies for graph embeddings based on different desirable properties. This is a novel way of thinking about the graph embedding problem.\n- Interesting theoretical results with practical applicability: a possibility theorem to satisfy the two desirable properties in with infinite samples along with an *impossibility* theorem to satisfy the two desirable properties in practice with finite samples.\n- New SENSEI algorithm that satisfies a weaker version of the two desirable properties and shows strong empirical performance.", "weaknesses": "- Generality of results is questionable. The proposed properties of discrimination and monotonicity are very much tied to two assumed tasks: link prediction and node recommendation. If one is only interested in one of these tasks (or perhaps a different task altogether), then the trade off between these two properties may not apply.\n- Discussion of limitations should be moved to the main paper.\n\n\nTypos and minor issues:\n- Figure 1 appears very early on in the paper, before the detailed discussion on the first and second category of methods on page 6. I did not understand it until reading page 6. I suggest the authors place a shorter summary of the first and second categories in the figure caption or earlier in the paper around the first time Figure 1 is used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: The analysis in Section 2 is quite general with respect to the similarity function $s(u,v)$. Sigmoid and cosine functions are mentioned as examples. What requirements must the similarity function satisfy in order for your analysis to be valid? Would, for example, a Euclidean distance-based similarity such as $\\sigma(||\\mathbf{F}(u,:)-\\mathbf{F}(v,:)||_{2})$ meet the requirements?**\n    \n**Response**: (1) Generally, the requirements for the similarity function are $s(u,v)$ is symmetric and $s(u,v)\\in(0,1)$. Here we do not take the corner case that $s(u,v)=0$ or $s(u,v)=1$ because it will leads to $\\log 0$ in the loss function. However, the theoretical conclusions still apply to $s(u,v)=0$ or $s(u,v)=1$ in implementation. (2) if $\\sigma$ in $\\sigma(||\\mathbf{F}(u,:)-\\mathbf{F}(v,:)||\\_{2})$ is the sigmoid function, it still meets the requirement. In addition, we can adopt $e^{-||\\mathbf{F}(u,:)-\\mathbf{F}(v,:)||_{2}}\\in(0, 1]$ as the similarity function, which is also Euclidean based and meets the requirement. \n\n**Q2: It seems that the two properties of discrimination and monotonicity are very much tied to the two tasks that you assume are important: link prediction and node recommendation. However, if one is only interested in link prediction, is there a reason they should care about monotonicity rather than just discrimination?**\n\n**Response**: First, the monotonicity property is closely related with the ranking of target similarity scores. If one is only interested in link prediction, this means that nodes are classified into two groups: (1) nodes with a link to the center node and (2) nodes without a link to the center node. In each group the target similarity scores of each node to the center node are regarded to be equal (1 or 0 respectively) since ''one is only interested in link prediction'' rather than node recommendation. In this case, the monotonicity does not need to be considered. Second, we would like to point out that the essence of link prediction task is a binary classification task and the essence of node recommendation task is a ranking task. Thus, our theoretical results can be transferred to proximity/similarity based binary classification task and ranking task in other domains (e.g., recommender system/NLP). Usually, both the discrimination property and the monotonicity property are important in real-world applications. For example, in an e-commerce system, predicting the candidate set of products that customers may have interests in is a binary classification task (discrimination property) and the rank of items within the candidate set also matters (monotonicity property). Our theoretical analysis is still useful in such real-world applications. \n\n**Other points in weaknesses/limitations/comments**:\n\n**P1 in Weakness 1: Generality of results is questionable. The proposed properties of discrimination and monotonicity are very much tied to two assumed tasks: link prediction and node recommendation. If one is only interested in one of these tasks (or perhaps a different task altogether), then the trade off between these two properties may not apply.**\n\n**Response**: As mentioned in our response to **Q2**, the essence of link prediction task is a binary classification task and the essence of node recommendation task is a ranking task. Thus, our theoretical findings can be transferred to proximity/similarity based binary classification task and ranking task in other domains (e.g., recommender system/NLP) rather than the graph embedding domain. Thus, we believe that these two properties are relevant to a broad range of similar tasks in other domains. \n\n**P2 in Weakness 2: Discussion of limitations should be moved to the main paper.**\n\n**Response**: Thanks for the suggestion. We will move the discussion of limitations to the main paper in the revised version of our paper.\n\n**P3 in Weakness 3: Figure 1 appears very early on in the paper, before the detailed discussion on the first and second category of methods on page 6. I did not understand it until reading page 6. I suggest the authors place a shorter summary of the first and second categories in the figure caption or earlier in the paper around the first time Figure 1 is used.**\n\n**Response**: Thanks for the suggestion. We will add the following text into the caption of Figure 1: ''For the first category of methods, they hurt the monotonicity between the star nodes and the round nodes. For the second category of methods, they keep the *monotonicity* between the star nodes and the round nodes but one rectangle node with small $p(u|v)$ has intermediate $s(u_8,v)$, which hurts the discrimination property.'' In addition, we will adjust the position of Figure 1 in the revised version to make it easier for readers to follow and understand the contents of our paper."}, {"review_id": "35m6nhwMjQ", "reviewer": "Reviewer_1EU9", "summary": "This work targets on network embedding under different strategies. The authors first theoretically demonstrate the dilemma in existing network embedding algorithms, especially the sampling-based framework, that the sampling-based embedding performance can have an error gap due to the competing sampling strategies.  Then, they propose two properties, i.e., discrimination and monotonicity, that should be obeyed, and eventually, under this perspective, they propose a novel network embedding approach called SENSEI to perform the (plain) network embedding. The SENSEI includes two steps, where the first step samples nodes with intermediate distribution following the first category of sampling strategies to satisfy the discrimination property, while the second step follows the second category of sampling strategies to partially satisfy the monotonicity property. Experiments on several datasets show the effectiveness of the proposed approach.", "questions": "+ Why is this approach called `SENSEI’?\n+ According to intuition, the SENSEI-P (w/o Step 2) will perform better than SENSEI-P on the link prediction task. Is it right?\n", "limitations": "Yes. The authors claim that the attribute could have helped promote the approach.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ This work has a clear motivation to devise a new reconciling strategy to satisfy the discrimination and monotonicity properties. \n+ The theoretical analysis is sound and details the significance of the two steps. Corresponding discussions clearly tell the advantages of the proposed embedding approach.\n+ The performance of SENSEI is not incremental in both link prediction and node recommendation tasks. Though the work mainly performs on plain networks, the authors still give the results on multi-layer networks.\n+ The proposed approach seems not to be difficult to reproduce.\n", "weaknesses": "- This work can only be effective on sampling-based embedding algorithms, though I think it is valuable for this field.\n- According to the results of Table 2, the promotion of step 2 is incremental. However, will step 2 harm the performance of the link prediction task? (See my second question in `Questions’) If so, the necessity of reconciling the competing sampling strategies is not very strong.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: Why is this approach called 'SENSEI’?**\n\n**Response**: Thanks for asking us the question about the name of our model. Here we adopt 'SENSEI' for its similarity to the word 'sense'. The word 'sense' has two levels of meanings: (1) the first level meaning is 'notice'. Our work notices the competing sampling strategies in existing methods; (2) the second level meaning is 'understand/unveil'. Our work understands and unveils the underlying reason behind such competing designs of sampling strategies with the help of sound theoretical analysis. \n\n**Q2: According to intuition, the SENSEI-P (w/o Step 2) will perform better than SENSEI-P on the link prediction task. Is it right?**\n\n**Response**: We are afraid  this is a factual misunderstanding. Step 2 will not hurt SENSEI-P's performance on link prediction. STEP 2 focuses on the partial monotonicity property within the positively sampled node set from STEP 1 to improve the performance in node recommendation task. In implementation, STEP 2 just fine-tunes the rank of node pairs with large similarity scores under a *smaller* learning rate. We use the toy example from Figure 1 in our paper to illustrate the optimization process: Assume that (1) $p(u\\_{1}|v)=0.45$, $p(u\\_{2}|v)=0.4$ and $p(w|v)=0.001$; (2) $u\\_1$ and $u\\_2$ have link connected with $v$, and $w$ does not have link connected to $v$. After Step 1, the similarity scores are likely be optimized to $s(u\\_1,v)=0.7$, $s(u\\_2,v)=0.8$ and $s(w,v)=0.01$. In Step 2, $s(u\\_1,v)$ is fine-tuned to be 0.76, $s(u\\_2,v)$ is fine-tuned to be 0.73 and $s(u\\_1,v) > s(u\\_2, v)$, and $s(w, v)$ is still 0.01. After Step 2, only the ranks of $u\\_1$ and $u\\_2$ are affected and the decision threshold (e.g.,$s(\\cdot,\\cdot) = 0.5$) for link prediction is not affected.\n\n**Other points in weaknesses/limitations/comments**:\n\n **P1: This work can only be effective on sampling-based embedding algorithms, though I think it is valuable for this field.**\n    \n**Response**: First, as we mentioned in the introduction section and the related works section: \"many existing network embedding methods follow a sampling training procedure.\" Please refer to these two sections for more details. Second, we would like to make the following clarification on the generality of our work. The essence of link prediction task is a binary classification task and the essence of node recommendation task is a ranking task. Thus, our theoretical findings can be transferred to proximity/similarity based binary classification task and ranking task in other domains (e.g., recommender system/NLP) rather than the graph embedding domain. Thus, we believe that our work can be generalized to a broad range of similar tasks in other domains. "}, {"review_id": "xyUEdKV65G", "reviewer": "Reviewer_FQQK", "summary": "The paper first introduces two desirable properties for network embedding. The discrimination property expresses how well the model is able to distinguish node pairs that are similar from those which are dissimilar. The monotonicity property expresses how the similarity scores obtained from the embedding follow the same order as the probability of a pair in the original dataset. The authors first define these two properties, argue why they are important for network embedding methods, and illustrate them with an example.\nThen, they consider a general framework for network embedding algorithm.\n\nThey present a standard expression of the likelihood of such models, discuss the elaboration of positive and negative samples sets, and derive elementary results of such models regarding the monotonicity and discrimination properties. They show both can be satisfied in an ideal case where infinite data is available (possibility results), and how both cannot be simultaneously satisfied for finite dataset (impossibility results). Doing so, they derive an optimal expression for the similarity between pairs of nodes, and how the positive sampling distribution should (negatively) correlate with the negative sampling distribution in order to satisfy monotonicity. Finally, they analyse the expected gap between empirical optimal solutions (finite dataset) and theoretical optimal solutions (infinite dataset).\n\nThey discuss the implication of these demonstrations. In particular, they detail some caveats of state-of-the-art sampling strategies in light of their findings.\n\nFinally, they design a simple embedding procedure (SENSEI) that focuses on satisfying the discrimination and monotonicity properties to some extent. They show on 4 real-world datsets how their approach outperforms existing methods both in terms of link prediction (related to the discrimination property) and node recommendation (related to the monotonicity property).\n\nThey conclude the paper with a short overview of existing works on network embedding.", "questions": "- l.232-233 - observing the deviation of p(u|v) entries could help choosing an optimal number for k?\n\n- l.141 - Definition of discrimination property : because s \\in [0;1] and p \\in [0;1], the definition seems to boil down to s(w|v)->0 when p(w|v)->0. Also, the definition only considers extreme cases where two nodes are so dissimilar the ratios of p and s diverge; what about intermediate cases, such as the ones given in the paragraph under the definitions? What does \"clearly distinguished in the embedding space\" mean?\n\n- l.144-166 - While I understand this is an illustrative example, I believe there should be at least a small discussion the chosen values of s(.,.). For instance, why would s(u1,v)<s(u2,v) given p(u1|v)>p(u2|v)? Does it happen often? Same for the very close values of s in case 2.\n\n- Eq.7 - Why does k appear along with positive samples, when it is absent from Eq.4?\n\nAdditional comments:\n\nl.107 - the link between discrimination/monotonicity and link pred/node rec should be stated higher in the text\n\nFig.1 - Maybe a matter of taste, but text should not wrap figures. The signification of the two-way gray arrows should be explicited in the legend. Besides, I am not sure that the figure helps the understanding of lines 144-166.\n\nEq.1 - I think the transition between Eq.1 and Eq.2 would be clearer if sigma(-F(w,:)^T F(v,:)) would be directly written as 1-sigma(F(w,:)^T F(v,:)). Also, there should be a reference to Def.1, because some s(.,.) could take values that are not in [0,1]. Dissimilar vector can yield a negative cosine similarity, for instance.\n\nAppendix A.2, Th.1 - Because there is no space constraint, it would be clearer to explicit the definition of the expectation E before differentiating.\n\nAppendix A.2, Th.2, l.600 - Typo \"is is\".\n\nl.206 - Specify the theorem holds for a 1st order Taylor expansion.\n\nl.211-220 - Nice discussion.\n\nl.241-256 - Fig.1 should be placed and explained here. Plotting fictive values of p(u|v) on top of the s(.,.) lines (instead of symbols) would ease the understanding.\n\nTables - Results with overlapping std should be emphasized in a similar way (bold or underline)", "limitations": "In the words of the authors, with which I agree: \n\"The limitations of our paper lie in that the theoretical analysis is conducted on proximity scores and the proposed SENSEI model is designed for plain (non-attributed) networks rather than attributed networks. The key to generalize the proposed properties/SENSEI model to attributed networks is a new definition of the “proximity” (i.e., node pair similarity). Currently, the proximity refers to the topological aspect of the node pair similarity.\"\nThese limitations lay the ground for broader future theoretical works on the topic.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem discussed is general; many previous works could be studied in the light of these findings\n- Writing is clear and sections are well organized.\n- Experiments are well carried out, with ablation tests, numerous baselines and four real-world datasets.\n- The discussion of previous works limits in the light of some findings (Thm.2) is interesting and insightful.\n", "weaknesses": "- Illustrations could be improved. The first line of Fig.1 is not very helpful, gray bars are not explicitly defined, and the symbolic representation of p(u|v) is unclear. I believe simpler visualisations are doable. Also, figures should take the entire width of the page, in my opinion, instead of floating in the middle of the text.\n- There are several mentions of \"large\" and \"small\" values of p and s. While it helps get a sense of what is discussed, I believe these should be better defined, as they are key words in the demonstrations. In line 233, the authors introduce the \"intermediate\" values with a rigorous definition; I believe discussing this above in the text might help to reach an explicit definition of \"large\" and \"small\".\n- All demonstrations are in the appendix. I understand that available space is an issue for large mathematical formulas, but proofs for Th.1 and Prop.1, that are key in the text, are short enough to be included in the main text. In their absence, the main paper cannot be considered as self-sufficient. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thanks: First, we want to thank you again for your *very detailed comments and many valuable suggestions*, which are very helpful for us to further improve the readability and quality of our paper in the revised version.**\n\n**Response to Q1**: \n\nThis is a good observation that the deviation of $p(u|v)$ and $k$ will together determine whether the node $u$ belongs to the group of nodes with largest/smallest/intermediate $p(u|v)$s and whether the similarity function $s(u,v)$ can be well learned. However, we are afraid that we can not say that \"the deviation of $p(u|v)$ entries could help choosing an *optimal* number for $k$\". This is because the number for $k$ is usually manually chosen for the *whole* graph and our analysis is based on one specific center node $v$. A good $k$ for one specific center node $v$ may not be a good $k$ for another center node $v^{\\prime}$ in this graph. Thus, we can not claim that `\"the deviation of $p(u|v)$ entries could help choosing an *optimal* number for $k$''. We think that $k$ should be tuned as a hyper-parameter for different datasets. \n\n**Response to Q2**: \n\nFirst, it is true that the definition will force $s(w|v)$ to approach 0 when $p(w|v)\\rightarrow0$. \n\nSecond, for these intermediate cases and the definition of discrimination property, we had considered adopting a threshold based definition: with two given proximity thresholds $0<p\\_{1}<p\\_{2}<1$ and two similarity score thresholds $0<s\\_{1} < s\\_{2}< 1$, if $p(u|v) < p\\_{1}$, it is regarded as \"small\" and $s(u, v)$ should be smaller than $s\\_{1}$. If $p\\_{1} \\le p(u|v) \\le p\\_{2}$, it is regarded as \"intermediate\" and the range for $s(u, v)$ should fall into $[s\\_{1}, s\\_{2}]$. If $p(u|v)>p\\_{2}$, it is regarded as \"large\" and $s(u, v)$ should be larger than $s\\_{2}$. However, we eventually decided to use the current definition presented in the paper for the following reasons: \n\n(1) the threshold is a *hard boundary* to discriminate between large/intermediate/small but  the range of $p(u|v)$ is continuous. For example, if the threshold $p\\_{2}=0.3$, it is unreasonable to say that $p(u\\_{1}|v)=0.300001$ is large while $p(u\\_{2}|v)=0.299999$ is intermediate. \n\n(2) the thresholds should be decided case by case for different center node $v$s in the graph. It is likely that one threshold value may be a good choice as $p\\_{1}$ for center node $v$, but for another center node $v^{\\prime}$, the threshold is more suitable to function as $p\\_{2}$. \n\n(3) the *limitation* style definition in l.141 is consistent with our following discussion and analysis, which will make it easier for the readers to understand the key ideas/findings of our paper. \n\nThird, for \"clearly distinguished in the embedding space\", this means that for the link prediction task, we want the embedding similarity scores of node pairs with/without links to be much larger (e.g., $s(u,v)> 0.7$)/smaller (e.g., $s(u,v)< 0.3$) than the classification/decision boundary (e.g., $0.5$). \n\nThank you again for raising the discussion about the definition of the discrimination property, we will add the above discussion into the main contents in the revised version of our paper.\n\n**Response to Q3**: \n\nThanks for the suggestion. \n\nFor the first question, it often happens when we adopt the empirical objective function in Eq.4. If $p(u\\_{1}|v)>p(u\\_{2}|v)$ but the values are close, due to the limited number of positive samples $T$, it is possible that $u\\_{2}$ is sampled more times (e.g., once or twice) than $u\\_{1}$ in the sampling process, which will cause $s(u\\_{1},v)<s(u\\_{2},v)$. \n\nFor the second question related to the very close values of s in case 2, this can appear in hard negative sampling strategies. Some nodes with large/intermediate $p(u|v)$s will be sampled as difficult negative samples due to the hard negative sampling strategies. This will make these nodes have small similarity scores w.r.t. the center node, which can not be distinguished with nodes with small $p(u|v)$s. We will add the above discussion into the revised paper.\n\n**Response to Q4**: \n\nThis is an implementation trick: it is equivalent to repeatedly sampling one specific node multiple times. In this way, we can make the best of the positive samples to make the training process converge more quickly.\n\n **Response to Weakness 1**: \n\nThanks for the great suggestion. We will separate the first line (case 1 and case 2) with the second and third line of Figure 1. We will also follow the reviewer's suggestion to add some fictive values of $p(u|v)$ on top of the s(.,.) lines \" in Figure 1.  **Please see the attached figure file uploaded in the general rebuttal.**\n\n**Response to Weakness 2**:  \n\nPlease refer to our response to **Q2** about the discussion of the definitions. In addition, we will incorporate some notations and discussions similar to line 233 (e.g. $p(u|v) >> kp\\_{n}(u|v)$ and $p(u|v) << kp\\_{n}(u|v)$) in the revised version of our paper.\n\n**Response to Weakness 3**: \n\nWe will move proofs for Th.1 and Prop.1 to the main text in the revised version of our paper.\n\n**Response to Additional Comments**: \n\nThank you again for your very detailed and valuable comments on these typos/minor points. We will follow the reviewer's suggestion to fix the typos/minor points and polish the paper in the revised version accordingly. \n"}]

Author rebuttal:
We sincerely thank all reviewers for their valuable time and insightful feedbacks which are very helpful for further improving the quality of our paper. We are grateful that the reviewers appreciate the novelty of the idea (`fuvb`), the importance of our work for "unifying existing different sampling strategies for graph embedding" (`fuvb`) and the potential of our paper for "broader future theoretical works on this topic" (`FQQK`). We are also encouraged that (1) our theoretical analysis is regarded as interesting (`fuvb`), insightful (`FQQK`) and sound (`1EU9`); (2) our experiments are well-carried out (`FQQK`) and the empirical performance is strong (`fuvb`, `1EU9`).  We have provided our point-to-point response to the questions of each reviewer below and we sincerely invite the reviewers for further discussion.  

In addition, we split the first line with the second and third line in Figure 1 and we have followed the suggestion of Reviewer `FQQK` to modify Figure 1, which is presented in the attached pdf file.

Meta-review: All reviewers agree that this paper is a good contribution. I recommend this paper to be accepted as a poster.
Decision: Accept (poster)