Bypassing Skip-Gram Negative Sampling: Dimension Regularization as a More Efficient Alternative for Graph Embeddings

We appreciate the reviewer’s comments. Here we respond to the overall concerns regarding the practical relevance of our method as well as its novelty:

The main contribution of our work is a conceptual connection between the noise contrastive estimation (NCE) loss and dimension regularization. Our connection is novel because while the SSL community has proposed dimension-based non-contrastive methods, these have been based on the squared-loss and a dimension-regularization approach has not been proposed for NCE.

The main intended use case of our theoretical contribution is scaling graph embeddings to graphs where using GNNs would be prohibitive given the memory constraints. To focus on capturing network structure we evaluate on link prediction and select the largest OGB benchmark datasets available. If the reviewer has larger graphs to suggest we would be happy to evaluate on them.

There are two secondary use cases for our theoretical contribution. First, our regularization is relevant in settings where graph data contain many false negatives e.g. implicit feedback. In these cases it would be better to prioritize the positive examples and not explicitly repel negative pairs, which may be false negatives. Second, another potential downstream application would be utilizing our dimension regularizer in self-supervised learning models that currently use NCE. One could eliminate negative samples in those models and utilize a dimension-centering regularization instead.

In addition, we thank the reviewer for the questions on skip-gram language models and evaluation metrics, which we answer below:

Could the proposed algorithm be used to scale up skip-gram based language models?

The efficiency gain is most relevant for graph skip-gram models because the number of nodes in graphs generally exceeds the vocabulary size of language skip-gram models.

Why in table 2 and 3, the key performance metric is AUROC instead of MRR/Hits@K? Given that link prediction tasks typically rely on ranking metrics, wouldn't MRR/Hits@K be more appropriate?

We include these results in the Appendix (Figures 5 and 6), and for the most part they corroborate the takeaways from the AUC-ROC results so we have omitted them from the main body to conserve space.

We thank the reviewer for their comments. Below we provide clarifications regarding the intended use case / novelty of our method along with proposals for follow up work:

What's the primary draw of the proposed method? If its truly efficiency, then we need to see how an online version of your method performs vs SGNS.

The primary draw of our method is indeed efficiency, especially in cases where the memory requirements of GNNs and negative sampling in general are prohibitive. Our method unlocks the ability to utilize graph learning in settings that were previously unfeasible. A secondary draw would be establishing a conceptual connection between the noise contrastive estimation (NCE) loss and dimension regularization, specifically dimension centering.

There are some questions about novelty

While the SSL community has examined non-contrastive approaches, these have focused on the squared loss which amounts to enforcing orthogonality among dimensions. To the best of our knowledge, there is not a connection between NCE loss and dimension regularization.

While the efficiency of the method is definitely better, its not obvious that it's an "online" loss.

We thank the reviewer for this comment. Regarding the online setting, our augmentation inherits the online ability of SGNS. Given a stream of positive edges, our augmentation performs an attraction update for each pair and then centers the embedding dimensions at intervals of positive edges. In fact this approach is more parallelizable than SGNS for large-scale settings. For instance, in a setting where embeddings are distributed across multiple machines, the elimination of negative samples reduces the need for inter-machine communication assuming the embeddings are assigned to machines via clustering. While positive updates tend to be local, negative updates are not given that negative samples are chosen randomly across the graph.

Finally, we appreciate and thank the reviewer for comments regarding additional baselines and figures similar to Figure 2d. We are running supplemental follow-up analysis evaluating our method on graphs of even larger size (where GNNs would be infeasible) and can compare against other scalability baselines apart from vanilla skip-gram models. Further, similar to Figure 2d, we are examining the performance of our model for highly sparse graphs where the positive signal is difficult to detect. In fact, per the reviewer’s comment, in these settings the class imbalance renders the full gradient suboptimal as the repulsion force dominates the attraction force.

We thank the reviewer for their detailed read of our submission. Below, we provide clarifications regarding the questions asked and the comments on our theoretical analysis.

In addition to the below, we welcome the reviewer to elaborate on the originality concerns, such as past works we may have omitted. To the best of our knowledge, the SSL community has focused on dimension orthogonality, but the connection between NCE objectives and origin centering in our work is novel.

Questions

Question 1

A: We agree that an important observation in our work is that for some real-world graphs applying only positive updates without any repulsion performs well. As the reviewer suggests, in the case of $II^0$, a small number of epochs are used to prevent embedding collapse. The number of epochs is tuned using the validation edge set.

Question 2

A: Yes, the method can be extended to the weighted setting. For instance, one can sample positive edges such that the probability of selecting an edge is proportional to its weight. Repulsion would still be applied via dimension regularization as proposed in our augmentation.

Comments

For instance, in the proof of Proposition 2.2, it is not clear how we obtain the equation given in Line 730 from Equation 27.

We thank the reviewer for this comment and note it is due to a difficulty in the readability of our notation. The constant $C$ in line 730 ($<X_i^t, X_j^t> + C$) is different from the constriction symbol $\mathcal{C}$. We will make this distinction clearer in the Appendix.

In Lines 731-732, the authors state that the constriction is monotonically increasing, since it remains positive. But this argument doesn’t guarantee that we will obtain C ≥ c for any given c.

We thank the reviewer for pointing out this correction. We will update Proposition 2.2 to state “As the Euclidean norm of the initial embeddings and the learning rate approach zero, there exists a time step $t$ such that applying gradient descent on $P_{SG}$ monotonically increases the constriction”. The revised claim still supports the argument that without repulsion the embeddings approach collapse.

However, Equation 11 holds since the denominator term goes to infinity so it does not establish the convergence of the gradients of $N_{SG}$ and $N’_{SG}$.

We note that Proposition 2.3 is not trivial since even though the denominator approaches infinity, it is not obvious the numerator remains small in comparison. The numerator difference $\nabla (N_{SG}' - N_{SG})$ ) corresponds to the repulsion of positive pairs, which one would expect to be large in magnitude. In the proof we show that when the embedding norm is bounded (not infinitely large), the sparsity of the graph ensures that the repulsion between positive pairs is small relative to the repulsion among negative pairs.

The derivation from Equation 37 to Equation 35 is not clearly explained.

In short, the transition from (35) to (36) is the triangle inequality. From (36) to (37), we utilize the following: $K_{ij} \leq \mathcal{C}$; $\| X_i\| \leq \beta_{max}$; the number of negative pairs is $n^2 - m$. We are happy to elaborate as needed.

We thank the reviewer for their notes on notation and will incorporate the recommended changes.