Response to Reviewer ANgE
We thank the reviewer for the comments, and apologize for a few unclear writings that make the reviewer misunderstand the idea that we tried to express.
We sincerely hope that the reviewer can re-evaluate our paper and raise the rating after reviewing our answers and revised paper.
We address the questions one by one.
> W1. "How to connect the graph information with the performance metric on the task?" Here are some missed related works [1,2,3,4,5].
Thank you for your supplement on related works.
We have added them to Section 2 (Page 2) in our revised paper.
Noting that our focus has two major differences from [1, 2, 3, 4, 5]:
1. These works focus on node classification, while our work majorly focuses on **link prediction**.
2. These works focus on graphs that are heterophily defined by the node labels, while our work focuses on cases such as heterophily w.r.t. node features ("talkative people have silent friends"), as well as heterophily w.r.t. graph structure (forming bipartite cores). We did not consider node labels in link prediction.
> W2. What is $f$ in C4?
As mentioned in the last sentence in C4 (Section 3.2, Page 3), $f$ is the column-wise L2 normalization.
We replace it with $l$ in our revised paper for increased clarity.
> W3. In theorem 1, "Given a discrete random variable Y , we have..." What is "accuracy(Y)"?
As shown in Equation 1 (Page 4), given a discrete random variable, its accuracy is the probability of its most probable outcome.
This is achieved by majority voting, which is the best we can do without any other information.
It is also described in Appendix A.1 (Page 13).
> W4. "Predicting links by GNNs relies on measuring node similarity, which is incorrect if the neighbors have heterophily embeddings." The embedding will be similar even with heterophily connections if the nodes share similar neighborhood patterns.
The main point is that we use **structure** embeddings (C1, Section 3.2, Page 3).
We have clarified our wording as follows (Page 5, 4 lines from the top):
*“Predicting links by GNNs relies on measuring node similarity, which is incorrect if the neighbors are expected to have dissimilar embeddings; for example, in a bipartite graph, …”* in our revised paper.
We agree with the reviewer that in the (label-)heterophily graphs, the **propagated** embeddings (C4 and C5) of connected nodes will be proximity embeddings, and are very likely to be similar.
However, for a (structure-)heterophily graph (e.g., consisting of bipartite cores), our proposed **structure** embeddings (C1), will not be similar even if they share similar neighborhood patterns.
> W5. "the node embeddings of linear GNNs require no model training“. Do you mean SGC [7] don't require training?
The node embeddings of linear GNNs in Equations 6 and 8 (Page 6 and 7, respectively) require no training, as they do not have any learnable parameters and can be computed with the closed-form formula.
By “linear GNNs”, we mean GNNs that have linear transfer functions (instead of non-linear ones, e.g. ReLU) and do not have learnable weight matrices during message-passing.
In our revised paper, we clarified it with the sentence (Page 5, 2 lines from the top): *“Compared to general GNNs, the node embeddings of linear GNNs are given by closed-form formula.”*
> W6. "It results in low value when node i and node j have heterophily embeddings, even if they are connected by an edge." This is not correct, see [2,3,6].
The statement in the paper is correct, when we use **structure** embeddings (C1, Section 3.2, Page 3) in a (structure-)heterophily graph.
In our revised paper, we clarified it with the sentence (Page 5, Section 4.1): *“However, even if node $i$ and node $j$ are connected by an edge, it may result in low value if they are expected to have dissimilar embeddings (e.g. structure embeddings in a bipartite graph).”*
In more detail, in the cited papers [2, 3, 6], these are node features propagated through graph structure, which are similar to our derived **propagated** embeddings (C4 and C5).
As discussed in W4, the **propagated** embeddings of connected nodes can be similar in a (label-)heterophily graph, while the **structure** embeddings will not be similar in a (structure-)heterophily graph.