Graph layouts and graph contrastive learning via neighbour embeddings

The experimental performance is good. This method is easy to implement and experimentally efficient.

We thank the Reviewer for their positive evaluation!

Indeed, our graph t-SNE beats SOTA results by a large margin, and our graph CNE beats SOTA on MLP-based graph contrastive learning. Also, we believe that the connection between graph layouts and graph contrastive learning is a novel and important insight of our paper.

This work uses MLP to transform node features and gives reasons for not using GCN. If possible, I think it would be helpful to include experiments that use GCN to transform node features.

We did not use GCNs because all existing GCL papers use GCNs, so we thought it is sufficient to refer to them. For example, Local-GCL is the most similar method to ours but uses GCN. Conveniently, Local-GCL authors also report the results using MLP architecture (quoted in our Table 2), and our Graph CNE outperforms them on all datasets.

As we explain in our Discussion, we think that for node-level graph learning, GCNs are not very appropriate, as they cannot process one node at a time. GCNs can be very suitable for graph-level contrastive learning, but this is conceptually a very different task requiring different datasets (not one graph at a time, but a collection of graphs, such as e.g. molecular stuctures).

We have now found another existing paper that reports MLP-based results (Guo et al., NeurIPS 2023, run experiments on GRACE with MLP: https://arxiv.org/abs/2311.02687), and added it to Table 2. Strikingly, Graph CNE outperforms both reported MLP-based GCL results on all datasets.

This work seems to apply only at the node level but not at the graph level. [...] Is the proposed method applicable at the graph level?

Not really. Of course one can average the node-level representation across all nodes and thus obtain a graph-level representation. But we do not think that our method is a reasonable approach for that. To be honest, we do not consider this is a limitation: graph-level contrastive learning is a very different task requiring different datasets (not one graph at a time, but a collection of graphs, such as e.g. molecular structures) and different methods.

In this work we focused on node-level learning, both in 2D (graph layouts) and in high-D (graph contrastive learning).

If there any further concerns, we will be happy to clarify!

The authors claim that "graph CNE performed comparably to the state-of-the-art graph contrastive learning algorithms." However, in Table 2, Local-GCL looks better. Please provide more evidence (for example, t-test) to support this sentence.

Indeed, in Table 2 some GCL methods outperform our Graph CNE, but only by a small margin, and on one of the datasets (PUB), Graph CNE is actually the best. This is what we mean by "comparably": not that it performs the best, but it performs close to the best.

Crucially, as we explain in the paper, the more relevant comparison is to the GCL methods when they also use MLP architecture. We have now found another existing paper that reports MLP-based results (Guo et al., NeurIPS 2023, run experiments on GRACE with MLP: https://arxiv.org/abs/2311.02687), and added it to Table 2. Strikingly, Graph CNE outperforms both reported MLP-based GCL results on all datasets.

Why not try GNN architecture if the authors want to compare the proposed graph CNE with other GCL methods?

This is a good question. We did not use GCNs because all existing GCL papers use GCNs, so we thought it is sufficient to refer to them. Local-GCL is the most similar method to ours but uses GCN. Conveniently, Local-GCL authors also report the results using MLP architecture (quoted in our Table 2), and our Graph CNE outperforms them on all datasets.

As we explain in our Discussion, we think that for node-level graph learning, GCNs are not very appropriate, as they cannot process one node at a time. For graph-level learning, GCNs can be very appropriate, but that is another story.

Why is Figure 1 shown on Page 1 but cited on Page 7?

We added a reference to Figure 1 on Page 2, and also in some other places throughout the text. Thank you.

How are the hyperparameters decided?

For graph t-SNE, we used all default hyperparameters of openTSNE.

For graph CNE, we mostly used default hyperparameters of CNE, but increased the number of epochs and the number of negative samples to ensure convergence and improve the InfoNCE approximation (as per Damrich et al. 2023). We also adapted the batch size to ensure convergence, based on our pilot experiments.

We added some clarifications to the text.

".. where running CNE for more epochs and/or with higher m could likely yield better results." Is the m explained somewhere in this paper?

Yes, the $m$ value is explained in Section 3.2 (see Equation 4), but we now removed this sentence because we now believe that $m=100$ that we used was sufficiently high.

If there any further concerns, we will be happy to clarify!

The results on graph layouts look promising. The proposed graph CNE does not rely on the entire graph as input.

We thank the Reviewer for this assessment!

Just to clarify what we think our main contributions are:

• We are the first to point out and explore conceptual connection between graph layouts and node-level graph contrastive learning, tying together two distinct fields.
• We suggest 2D graph contrastive learning (graph CNE with $d=2$) as a novel graph learning task as a "missing link" between graph layouts and standard graph contrastive learning.
• Our graph t-SNE beats SOTA on graph layouts by a large margin (!).
• Our graph CNE beats SOTA on MLP-based graph contrastive learning.

The Reviewer scored the "novelty" aspect as 1, but we believe the our work contains a whole lot of novel results: both conceptual insights and SOTA achievements!

In Section 4, the authors say "we split all nodes into a training (2/3 of all nodes) and a test set (1/3 of all nodes)." Is this setting applied to all datasets? How to choose nodes for training? Why not use K-fold splits?

Yes, we used the same 2:1 splitting on all datasets. The set of training nodes was selected randomly. We could indeed use K-fold cross-validation, but used a fixed train/test split for simplicity and because it is standard in the field. The graphs that we used are large enough (number of nodes $n>2000$) so that the sampling error here is small anyway.

We do not see this as a limitation, but if the reviewer disagrees, we are happy to provide some K-fold classification results for comparison.

In Section 6, Paragraph 2, the authors say "we used the cosine distance and the Gaussian similarity kernel for d=128." Does it make sense to evaluate the models by NN recall/accuracy, which is based on Euclidean distance?

This is an excellent question! Indeed, for $d=128$ embedding we also tried using cosine-metric kNN graph for measuring recall/accuracy, but found that it did not noticeably affect the results. So for simplicity we only reported Euclidean kNN evaluation. We have now inserted a clarification about it into the text.

In Section 6, Paragraph 3, the authors say "The number of epochs was set to 100." I think the number of epochs should be decided by the convergence of a model. The authors also say "running CNE for more epochs and/or with higher could likely yield better results" and "be due to insufficient optimization length and/or m value" in the following paragraphs. Does this mean the models are not well-trained?

Thank you for bringing this up. Since the original submissions, we have done additional experiments, and by now believe that 100 epochs is sufficient for convergence on all our datasets. We removed all statements that you quoted here.

In Section 3.2, the authors use CNE to denote the framework of [1], and the proposed contrastive learning model is named graph CNE. However, the CNE in Figure 4 and Table 2 seems to denote the proposed method, which is confusing.

Thank you! We changed Figure 4 and Table 2 to always say "graph CNE".

In Table 2, are the baseline methods using the same experiment settings (for example, train/val/test split) as the proposed method?

We took the values reported in Table 2 from the literature (as indicated in the caption). The train/test splits there could be different. However, given that the graphs are large and that the train sets are selected at random, that should not play a major role. In fact, the variability due to network re-training (which is what is shown in Table 2 as $\pm$ intervals) is likely larger than the variability due to the test set selection. We have now clarified where exactly the quoted values are coming from.

The exploration of the connection between graph layouts and graph contrastive learning is a relatively under-explored yet important topic given the abundance of graph data nowadays and the need to visualize and process graph data.

We thank the reviewer for this assessment!

Indeed, we also believe that this connection is conceptually very important, and our paper is the first to point it out and explore. Along the way, we beat SOTA on graph layouts, beat SOTA on MLP-based graph contrastive learning, and suggest 2D graph contrastive learning (graph CNE with $d=2$) as a novel graph learning task and a "missing link" between graph layouts and standard graph contrastive learning.

Paper writing can be made better. For example, for Equation 3, there is no description of the meaning of y. The definitions of parametric and non-parametric embeddings should be clearly described earlier in the paper.

Thank you for these suggestions! We added the definition of $\mathbf y_i$ vectors into Section 3.1 and added a definition of parameteric/non-parametric embeddings into Section 3.2. We also carefully went over the entire paper and inserted clarifications and cross-references. Please do let us know if you find any other specific places that should be clarified!

As the authors mention, it is suspected that "in GCL algorithms employing GCNs, it is the GCN that does the heavy lifting, and not the specifics of the GCL algorithm." However, there is no experimental setup where the authors verify this hypothesis, which is a pity.

Indeed, we do not provide experimental evidence for this, but in fact, another paper (not ours) has just been accepted to NeurIPS and published online: Guo et al. 2023 Architecture matters: Uncovering implicit mechanisms in graph contrastive learning (https://arxiv.org/abs/2311.02687). This paper explicitly studies the effect that GCN architecture has in GCL and indeed shows that it does the heavy lifting in pulling connected nodes together. We have therefore reformulated this paragraph and cited this paper.

Does graph t-SNE use the graph node features?

No it does not. The Reviewer's understanding is correct.

If this is the case, I am still unsure if kNN classification accuracy is the right metric, since the metric quantifies local class separation, yet the class label for each node is unobserved by the layout methods. If this is the case, please justify the adoption of such a metric for comparing different graph layout algorithms. The concern is, what if for a real-world dataset, the class labels of nodes are less related or unrelated to the structure/topology of the graph? Then wouldn't all the layout methods show low accuracy? Fundamentally, the question is about the justification of using this metric to evaluate layout algorithms.

This is an excellent question. Indeed, the standard approach in the graph layout literature is to use kNN preservation metrics, such as the kNN recall that we use in Figure 3a. We also consider it our main metric for graph layouts (and note that our graph t-SNE outperformed all other methods on all considered datasets, according to this metric).

We additionally showed kNN accuracy in Figure 3b because it is similar to the metric always used in node-level graph contrastive learning (linear classification accuracy). Given that one of the aims of the paper is to establish the conceptual connection between graph layouts and graph contrastive learning, we think it is useful to show this metric here. But again, we agree with the Reviewer that the kNN recall metric is more important here.

We have clarified this in the text.

If there any further concerns, we will be happy to clarify!

Dear reviewer pX5U, thanks again for your feedback. We hope our edits have resolved your concerns! If there are any remaining concerns, we would still have 2 hours to respond.