On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks

Q3 Expand beyond GNN

Currently, GNN4LP methods are the state-of-the-art methods for the link prediction task; additionally, many heuristics such as common neighbors do not make use of node features. Therefore, we primarily restrict our study to the scope of GNNs. However, the notion of "feature heterophily" can have implications beyond GNNs, such as decoder-only models that only consider pairwise node features. Furthermore, there could be interesting dynamics between feature and structural proximity, which is beyond the scope of this paper and could be an interesting direction for future work. We will mention some of these connections in the paper.

W1 Significance of the work

Thank you for your feedback. We want to point out that going beyond the global characterization of the graphs for the link prediction task, we also provided a zoom-in analysis on the performance on heterophilous edges per method for all the real-world datasets, which also demonstrates the effectiveness of our identified designs in improving GNN performance on the full spectrum of low-to-high feature similarity (c.f. Line 360-365, 370-374, and Figure 4). This is important since in reality every dataset exhibits variance in feature similarity across all the links. That said, we acknowledge that finding real-world, publicly-available graphs that align with the heterophilic link prediction task, as discussed in Section 3, is non-trivial. Currently, we have identified e-comm as a high-quality non-homophilic network for link prediction. In Figure 1 of our general response plots, we have demonstrated that many real-world heterophilous node classification benchmarks, such as Pokec [1] and Amazon Ratings [2], are predominantly homophilous for the link prediction task, with most edges connecting nodes with similar features. Nevertheless, as we mentioned above, these datasets still have heterophilous edges where our theory and findings apply.

We believe that the current limited number of high-quality heterophilous link prediction datasets does not imply that the problem itself is artificial. To bring in a bit more context, the lack of high-quality heterophilous datasets for node classification tasks was also a longstanding challenge before the challenge of heterophily for GNNs became widely recognized in the field. As the problem attracted more interest, various research teams dedicated their efforts to introducing a range of heterophilous datasets, thereby advancing findings and methodologies within the subfield. Additionally, as we mentioned above, heterophilous connections can also arise locally even if the graph is homophilous in general, which motivates our locallized, more nuanced analysis (cf. Figures 4 and 9). Thus, by casting light to the problem of link prediction beyond homophily, we hope that our work will motivate the introduction of a high-quality set of benchmarks with diverse feature similarity, beyond the real data that we presented.

[1] Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. (NeurIPS 2021).

[2] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? (ICLR 2022).

W2 Relation of synthetic graph generation with other random graph generation methods

Our synthetic graph generation process is detailed in Lines 512-520 in Appendix A. Most of the random graph generation methods in existing literature studying heterophilous graphs are for creating synthetic datasets for node classification: [3,4] follow a modified preferential attachment process, where the probability of an edge is determined by both the class compatibility matrix and the node degree, while [5] follows to use contextual stochastic block model (CSBM) for synthetic graph generation. However, all of the aforementioned approaches control the homophily/heterophily levels defined on class labels of the generated synthetic graphs, while for graphs for link prediction usually do not have class labels. NetInfoF [6] recently generates synthetic graphs as link prediction benchmarks by controlling the correlation between node feature and edge existence. However, their generation process only allows node features to be fully correlated, partially correlated, or uncorrelated with edge existence; it lacks the capability to granularly control the feature similarity of the generated graph as in our graph generation process, and it is also not capable of generating graphs where features are negatively correlated among connected nodes. We will include these discussions in our final version.

[3] Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. (ICML 2019).

[4] Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. (NeurIPS 2020).

[5] Adaptive universal generalized pagerank graph neural network. (arXiv 2020).

[6] NetInfoF Framework: Measuring and Exploiting Network Usable Information. (ICLR 2024).

W3 Theorem connections with GNNs

Thank you for the feedback. Existing GNN4LP methods are composed of encoders and decoders, both of which are essential components. Our first two theorems primarily consider the effectiveness of link prediction decoders, which, as our experiment shows, have a significant impact on GNN performance under link prediction tasks. Furthermore, the choice of decoders in link prediction tasks is not as trivial as it might seem: while MLP decoder is more preferred in academic research, DOT product decoder is more widely adopted in industry due to its scalability in tasks such as retrieval. Our theoretical analysis reveals the limitation of DOT product decoder for non-homophilic link prediction tasks and helps identify DistMult as an effective substitute which maintains the scalability of DOT product with closer-to-MLP link prediction accuracy. We will make the connections more clear in our paper.

Q1 Insights for non-attributed graphs

Our study primarily focuses on the impact of feature heterophily. As we define heterophily on node features, our definition and analysis is not applicable to graphs without node features. Given the prevalence of attributed graphs in real-world applications (e.g., textual information is often associated with nodes in industrial and other applications), we believe that the contributions of this work are significant for these commonplace settings.

Q2 Expand the analyses to k-hop neighbors

We appreciate the reviewer for sharing this valuable suggestion. We believe it would be an interesting direction to explore in future work.

2. Thank you for your suggestion. As a pioneering study in this area, our primary objective has been to characterize the problem and identify useful design principles. We believe that our work is significant in setting a new research direction, which is essential for advancing the field. Furthermore, it is also noteworthy that many complex architecture designs proposed for handling heterophily in node classification were later found to be not as effective as following the simple principle of separating ego-and neighbor-embeddings in model architecture (e.g., applying it to GAT and Graph Transformer), as highlighted in [13]. Our study takes a comprehensive approach, laying the groundwork for future research. We acknowledge that there is ample room for exploring more effective methods, and we view this as a key avenue for future research.

[1] TUDataset: A collection of benchmark datasets for learning with graphs

[2] MoleculeNet: A Benchmark for Molecular Machine Learning

[3] Benchmarking Graph Neural Networks

[4] Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks

[5] Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking

[6] Benchmarking Graph Neural Networks

[7] Predicting multicellular function through multi-layer tissue networks

[8] PANE: scalable and effective attributed network embedding

[9] Pitfalls of Graph Neural Network Evaluation

[10] Multi-scale Attributed Node Embedding

[11] An Information Flow Model for Conflict and Fission in Small Groups

[12] User Preference-aware Fake News Detection

[13] A critical look at the evaluation of GNNs under heterophily: Are we really making progress?

Thank you for your additional feedback. We have carefully considered your concerns and would like to address them as follows:

1. Following your suggestion, we have conducted a thorough examination of various real-world benchmarks, including those that are typically used for other graph learning tasks (e.g., graph or node classification). We see the challenge of identifying heterophilic link prediction benchmarks as an opportunity to introduce more diverse, real datasets for this task. Specifically, we have identified a range of biological graph datasets from the TUDataset [1] that exhibit feature heterophily (these datasets are typically used for graph classification). In particular, the following datasets comprise entirely heterophilic graphs (i.e., every single graph has negative homophily ratios):

• aspirin
• benzene
• malonaldehyde
• naphthalene
• salicylic_acid
• toluene
• uracil

These datasets are substantial in size, as detailed below:

In addition, some datasets contain instances that are strongly heterophilious (with homophily ratio -1.0), including bbbp, NCI1, AIDS, and QM9 [2]. Note that such findings are not only limited to biological datasets. For instance, 73% of graphs from PATTERN [3] (Mathematical Modeling) have negative homophily ratios.

Furthermore, we have identified node classification benchmarks from torch-geometric.datasets that display a wide range of feature homophily ratios, many of which are more heterphilious than e-comm, the one we proposed in paper. Notably, some real-world benchmarks exhibit negative homophily ratios. We summarize our findings in the following table.

In addition to the homophily ratios presented above, we provide the feature similarity distributions for edges and random node pairs across several datasets in this anoynomized GitHub repo, following the same convention as Figure 5 in our paper. These plots reveal clear signs of heterophily in the existing benchmark graphs.

Consequently, we believe that our study is grounded in existing benchmarks. We will include these findings in our paper to present a set of diverse link prediction datasets and we will also encourage the introduction of additional heterophilic datasets, thereby broadening the scope of research in this area. Thank you again for leading us to this direction!

We have additionally conducted experiments on one heterophilic dataset we identified (Amazon-Computers, feature homophily ratio=0.07) and present the result in the table below. We find that the conclusions from our main paper still hold (SAGE > GCN, due to the sparation of the ego- and neighbor-embeddings, and the use of DistMult/MLP decoders is better than DOT).

We will include these new results in the final version of the paper.

W1 Exploring the relationship between feature similarity and structural similarity

Thank you for raising this valuable suggestion. Exploring the dynamics between feature and structural similarity would indeed be an interesting direction for future research. In this work, our aim is to provide the first essential characterizations of the impact of feature heterophily on link prediction for GNNs. Future work can explore more fine-grained questions, such as the insightful one you raised.

W2 Benchmark datasets

Thank you for your feedback. First, we would like to emphasize that we have run experiments on a series of synthetic graphs of different heterophily ratios/feature similarity distributions. Second, going beyond the global characterization of the graphs for the link prediction task, we also provided a zoom-in analysis on the performance on heterophilous edges per method for each real-world dataset, which also demonstrates the effectiveness of our identified designs in improving GNN performance on the full spectrum of low-to-high feature similarity (c.f. Line 360-365, 370-374, and Figure 4). This is important since in reality every dataset exhibits variance in feature similarity across all the links. Finally, by casting light on the problem of link prediction beyond homophily, we hope that our work will motivate the introduction of a high-quality set of benchmarks with diverse feature similarity, beyond the real data that we presented. This trend was also observed in the literature after the challenges of heterophily for GNNs were pointed out in the node classification task [1,2]: as the problem attracted more interest, various research teams dedicated their efforts to introducing a range of heterophilous datasets, thereby advancing findings and methodologies within the subfield. In Figure 1 of our general response plots, we have shown that many real-world heterophilous node classification benchmarks, such as pokec [1] and Amazon ratings [2], are homophilous for link prediction, with most edges connecting nodes with similar features. Nevertheless, as we mentioned above, these datasets still have heterophilous edges where our theory and findings apply.

[1] Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. (NeurIPS 2021).

[2] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? (ICLR 2022).

Q1 Clarification on \hat{y}

Thank you for carefully reading our paper! For our theoretical analysis in Sections 3 & 4, the "predicted link probability" $\hat{y}_{u,v}$ is derived based on the equation in Line 144 ("Theoretical Assumptions" paragraph) in Section 3.2.

We note that we should have used "predicted link score" instead of "predicted link probability" for the discussions in Section 3, as the "link probability" term would imply that our prediction $\hat{y}_{u,v}$ is bounded within $[0,1]$ which is not the case in our analysis. We will revise the usage of "predicted link probability" term and make changes to ensure the notations are consistent and clear in our final version.

Q2 Identical scores for positive pairs

Thank you for the question. Figure 1 gives some example distributions of positive node pairs (i.e., edges – colored in green) and negative node pairs (non-edges – colored in red) for homophilic and heterophilic link prediction tasks to contextualize the introduction of these concepts. In these examples, the feature similarity scores of positive node pairs are simplified to follow a uniform distribution, hence we show the horizontal green lines in the Probability Density Function (PDF) plots of the similarity score distribution. Of course in real-world datasets the similarity score distributions for both positive and negative node pairs can be more complex: in Figure 5 in the Appendix we show the actual feature similarity score distributions for real-world datasets used in our experiments.

Q3 Generality of theoretical results on learning rate

The goal of this theorem is to show that the predicted link probability is related to the magnitude of the threshold M that separates the positive and negative samples, which highlights the different optimizations needed for homophilic and heterophilic link prediction tasks that have not been studied in prior literature. While generalizing the theorem to higher dimensions is non-trivial, our experiments in Section 6 have strengthened this implication to datasets of significantly higher complexity.

Q4 Details about the real-world data

The above table shows the details of the split of edges for train, validation, and test on real-world datasets. Note that in standard GNN4LP research, there are usually far more training edges than validation and test edges combined (see Table 2 in [14] in paper references). We follow the standard approach of data splitting. It would be an interesting future direction to consider the impact of data splitting on model performance.

Q5 Reasons for dividing the buckets

Thank you for the question. We use the minimum degree of connected nodes to divide the buckets in Fig. 4 since it has been shown in previous works that the presence of low-degree nodes (see [44] in paper references) can increase the complexity of heterophily for node classification tasks and negatively impact GNN performance. By using the minimum degree instead of maximum or average degree, we can group edges that are connecting at least one node with low degree and examine how different approaches perform on these edges. We will also explain our choice in the paper.

W1, Q1 Clarifications (1) implementation of feature extraction (2) generation of synthetic graphs

Thank you for your questions.

• For W1(1) implementation of feature extraction, we interpret the "feature extraction" part in your comment as how we obtain the node features for our synthetic and real-world datasets---please correct us if our interpretation is not right. For real-world graphs, we use the original node features provided in the datasets that are created by previous works: ogbl-collab and ogbl-citation2 from Open-Graph Benchmark [1], and e-comm from [2]. We give a brief overview of how the node features are created in Lines 532-539 in Appendix A. Our synthetic datasets are created by rewiring the edges among 10,000 sampled nodes from the real-world dataset ogbl-collab; we keep the features attached to each node during the sampling process, which become the node features for our synthetic graphs instead of generating new node features ourselves.
• For W1(2) and Q1 generation of synthetic graphs, we describe our synthetic graph generation process in Lines 512-520 in Appendix A (as we mentioned in Line 280 in Section 6.1): the synthetic graphs are generated by randomly sampling 10,000 nodes with their features in ogbl-collab and connecting 2% of all possible node pairs whose feature similarity falls within specified ranges; all graphs share the same set of nodes and features and only differ in their edges. More specifically, we calculate the pairwise feature similarity between all node pairs and create 50-quantiles of feature similarity scores. We select the 3 smallest quantiles, the 3 largest quantiles, and 4 quantiles in equal intervals in between, resulting in 10 quantiles. We then create 10 synthetic graphs by connecting node pairs whose feature similarity scores fall within the same quantile. Thus, by gradually increasing the range of similarity for connected nodes, we create graphs which resemble different types of link prediction tasks and average feature similarity.

[1] Open Graph Benchmark: Datasets for Machine Learning on Graphs. (NeurIPS 2020)

[2] Pitfalls in Link Prediction with Graph Neural Networks: Understanding the Impact of Target-link Inclusion & Better Practices. (WSDM 2024)

W2 Structure of paper; position of the related work section

Thank you for your suggestion. We will revise the paper structure and specifically move the related work section to an earlier location (e.g., Section 2) in the final version.

Q2 How is the predicted link probability derived

Thank you for your question. For our theoretical analysis in Sections 3 & 4, the "predicted link probability" $\hat{y}_{u,v}$ is derived based on the equation in Line 144 ("Theoretical Assumptions" paragraph) in Section 3.2.

We note that we should have used "predicted link score" instead of "predicted link probability" for the discussions in Section 3, as the "link probability" term implies that our prediction $\hat{y}_{u,v}$ is bounded within $[0,1]$ which is not the case in our analysis. However, our analysis can still be given a probabilistic perspective as we can derive the predicted link probability by taking sigmoid $\mathrm{sigmoid}(\hat{y})$ on the predicted link score. We will revise the usage of "predicted link probability" term in our final version.

W1 Theoretical Analysis

Thank you for your feedback. First, our theorems are derived under reasonable simplifications, which are typical in the heterophily literature (e.g., [1-2]). Second, our empirical analysis extends well beyond these theoretical assumptions, demonstrating that our theory holds more broadly. Finally, we emphasize that our theoretical analysis aims to provide concise characterizations as an initial step in formalizing this problem. We believe that extending beyond our current theoretical framework will be a valuable direction for future research.

[1] Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. (NeurIPS 2020).

[2] Revisiting Heterophily For Graph Neural Networks. (NeurIPS 2022).

Q1 Notation of mean feature vector: use $\bar{\mathbf{x}}$ instead of $\bar{\mathbf{X}}$

Thank you for reading our paper carefully! We will make this modification in our final version.

Q2 Other Heterophily-specific techniques, e.g. high-pass filter

Thank you for your suggestion. We agree that considering different heterophily-specific techniques is important and will be an interesting direction for future work. The main contribution of this paper is to propose and characterize feature heterophily, marking a pioneering effort in this area.

W1&2 Intuitive conclusions & novelty

We thank the reviewer for the feedback. We note that this is the first work that explicitly characterizes feature heterophily in link prediction with GNNs. Our work pioneers in formalizing the problem, providing concise characterizations, and examining effective designs. Our paper highlights the necessity of careful selection of link prediction designs, including the significant limitation of DOT product decoders, which are widely adopted in the industry, for non-homophilic link prediction tasks, and identifies DistMult as a scalable alternative for settings which offers high scalability. We believe all these are significant and meaningful contributions to the field and open up interesting future avenues for research.

W3 Heterophilic real-world datasets

Thank you for your questions. First, we would like to emphasize that we have run experiments on a series of synthetic graphs of different heterophily ratios/feature similarity distributions. Second, going beyond the global characterization of the graphs for the link prediction task, we also provided a zoom-in analysis on the performance on heterophilous edges per method for each real-world dataset, which also demonstrates the effectiveness of our identified designs in improving GNN performance on the full spectrum of low-to-high feature similarity (c.f. Line 360-365, 370-374, and Figure 4). This is important since in reality every dataset exhibits variance in feature similarity across all the links. Finally, by casting light on the problem of link prediction beyond homophily, we hope that our work will motivate the introduction of a high-quality set of benchmarks with diverse feature similarity, beyond the real data that we presented. This trend was also observed in the literature after the challenges of heterophily for GNNs were pointed out in the node classification task [1,2]: as the problem attracted more interest, various research teams dedicated their efforts to introducing a range of heterophilous datasets, thereby advancing findings and methodologies within the subfield. In Figure 1 of our general response plots, we have shown that many real-world heterophilous node classification benchmarks, such as pokec [1] and Amazon ratings [2], are homophilous for link prediction, with most edges connecting nodes with similar features. Nevertheless, as we mentioned above, these datasets still have heterophilous edges where our theory and findings apply.

[1] Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. (NeurIPS 2021).

[2] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? (ICLR 2022).

Q: potential suggestions

Thank you for your valuable suggestions. Following your recommendation, we have added one more heterophilic GNN as the encoder for experiments (highlighted in Table 1 general response pdf) and our conclusions about the GNN decoder and encoder still hold.

Following your and reviewer ufZT, YTzD's insightful suggestions, we have identified a range of real-world datasets that exhibit strong feature heterophily (please refer to our lateset response to reviewer ufZT). In addition, We have additionally conducted experiments on one heterophilic dataset we identified (Amazon-Computers) and present the result in the table below. We find that the conclusions from our main paper still hold (SAGE > GCN, due to the sparation of the ego- and neighbor-embeddings, and the use of DistMult/MLP decoders is better than DOT).

We will include these new results in the final version of the paper.