Truth-Guided Negative Sampling in Self-supervised Graph Representation Learning

The authors would like to thank the reviewer for the review.

W1, Q1

Thanks for pointing out. We have fixed the typos in (1) and (2) in our revised version.

For (3), function g is neither g^+ or g^-. g^+ and g^- are the empirical loss functions in negative sampling, while g is the function in the theoretical risk term (Eq. 5) that we ideally wish to minimize. Their relationship is shown in the condition 2 of Proposition 2, which basically says that negative sampling can be viewed as an approximation of the theoretical risk term, and one of the two premises for this to happen is that we need to assign g^+=-g, and g^-=z_u g. We will further clarify this in the text.

For (4), Z is simply a constant following the convention of math notations. We have clarified this in our revised version.

W2

The class priors $\pi^+$ and $\pi^-$ are defined in lines 175-176 in our revised version. Their calculation and tuning are explained in lines 325-326 and line 425.

Q2

The relationship and indication are explained in lines 224-226 and lines 234-238 in our revised version. Briefly speaking, this is the core idea of the entire Section 4:

• R1(f) is the risk (loss) term that we empirically minimize when doing negative sampling
• R2(f) is the risk (loss) term that we ultimately wish to minimize if we had infinite computing resource.

Proposition 2 tells us that: if and only if we use its suggested design of the proposal negative distribution (q^-), will we be able to treat R1(f) as an unbiased approximation of R2(f). This result provides a theoretical ground for what should be considered a good proposal distribution.

The authors would like to thank the reviewer for the review.

D1

Thanks. We have fixed this typo in our revised version. We will also thoroughly review their paper to eliminate further typos.

D2

We would love to clarify that whether a dataset is biased or unbiased totally depends on the way we construct train/test splits. The datasets themselves only provide a set of recorded user-item edges. We explained how we conduct the splits differently for the biased and unbiased differently in Section 6.1.

D3

Thanks. We will follow the suggestions to add more experiments in our next version.

The authors would like to thank the reviewer for the review.

W1

the relationship between $p^-$ and $p^+$ has been adopted by DCL [a5], and the same formula (line 1, page 4, in [a5]) is used to address sampling bias.

Our contribution towards addressing is way beyond this simple flipping trick: we have never claimed a contribution in connecting p^- and p^+ via the law of total probability, e.g. line 1, page 4, in [a5]. In fact, this flipping trick is a very well-established, simple result that has been seen in many of our cited works, including (Gerych et al.2022) and (Robinson et al. 2021) which is an improved version of [a5] written by the same authors.

More importantly, the “bias” in [a5] is a totally different concept than the “bias” formulated in our paper (Section 5.1). The former simply refers to the issue that we have not excluded known positive samples when doing negative sampling. The latter refers to a much more challenging issue that we only have biased, partial observations of positive distribution which makes the estimation of negative distributions biased as well.

propensity scores have been widely used to address selection bias in the Recommendation Systems (RS) field [a6].

Our method falls into the general category of Inverse Propensity Scoring (IPS) but has the following contributions and novelty:

• Previous propensity methods are mainly designed for reweighing observed data points in recommendations. However, they have not been combined with negative sampling as a way to derive the optimal negative distribution in an end-to-end manner, which is what this paper is doing.
• We use a very different method to estimate the propensity scores. Existing works such as [a6] estimates propensities via naïve bayes or regression over node attributes. Instead, we estimate propensity scores by novely exploiting its known connections various biases encapsulated by graph structural features, including node degrees and embeddings. This has been explained in the second paragraph of Section 5.3.

We will add more references and discussion related to the propensity score methods.

W2

2a) We explained the interpretations of Eq. (4) in lines 213-222, which show that Eq. (4) has intuitive connections with the famous InfoNCE loss and random graph model. Therefore, it is a well-motivated risk term that we ultimately desire to minimize.

2b) We defined and explained them in lines 162-164: an edge e contains two end nodes u, v, so p^+(e)= p^+(u, v)=P(e|y=1)= P(u, v|y=1), according to the definition of p^+. Because the second expression p^+(u, v) in this chain is essentially a joint distribution in space V \times V, we can define its corresponding conditional distribution p^+(\cdot|u).

W3

Thanks for your suggestions. We will follow them to improve our experimental section in the next version.

The authors would like to thank the reviewer for the review.

W1

Thanks. We have added line numbers and fixed the typos in “respective” and caption positions.

For the results of DNS and title alignment:

• The results of DNS are bolded because statistically they are also considered the best performance i.e. close to our performance within the standard error.
• The titles in the pdf and in the system do align. Could you please let us know what difference you have spot on them in reviewer’s portal?

W2

SENSEI did not conduct experiments on node classification tasks, but instead tested only on link-level tasks, including recommendation. Its experiment section states that “we evaluate the effectiveness of the proposed algorithm (SENSEI) for solving link prediction and node recommendation simultaneously in plain networks.”

In fact, all the baselines we compared with have primary study link-level tasks, especially recommendations (link scoring and ranking).

Q1, W3

Thanks for the suggestion. We will supplement more experiments on this in our next version.

Q2

We explained this in lines 60-67. It is certainly most desirable if our negative samples can represent the entire non-interaction space, i.e. we are able to obtain sufficient amount of unbiased samples from ground-truth negative distribution p^-. However, in practice, because the entire non-interaction space is too large (N^2 where N is the number of nodes), the learning variance is very large too, which leads to underperformance. This is exactly why we need to modify the distribution of the negative samples, e.g. via boosting or hard negative sampling. From this perspective, our Section 4, especially Proposition 2, essentially shows how to modify the negative distribution in a theoretically-sound manner.