Library

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

Heterophily, or the tendency of connected nodes in networks to have different class labels or dissimilar features, has been identified as challenging for many Graph Neural Network (GNN) models. While the challenges of applying GNNs for node classification when class labels display strong heterophily are well understood, it is unclear how heterophily affects GNN performance in other important graph learning tasks where class labels are not available. In this work, we focus on the link prediction task and systematically analyze the impact of heterophily in node features on GNN performance. Theoretically, we first introduce formal definitions of homophilic and heterophilic link prediction tasks, and present a theoretical framework that highlights the different optimizations needed for the respective tasks. We then analyze how different link prediction encoders and decoders adapt to varying levels of feature homophily and introduce designs for improved performance. Our empirical analysis on a variety of synthetic and real-world datasets confirms our theoretical insights and highlights the importance of adopting learnable decoders and GNN encoders with ego- and neighbor-embedding separation in message passing for link prediction tasks beyond homophily.

cs.LGAdvanced Graph Neural NetworksComplex Network Analysis TechniquesAdvanced Clustering Algorithms ResearchComputer Science
Source

Paper

References (60)

01NetInfoF Framework: Measuring and Exploiting Network Usable InformationMeng-Chieh Lee, Haiyang Yu, Jian Zhang et al.2024 · International Conference on Learning Representations · 4 citations In Library
02Revisiting Link Prediction: A Data PerspectiveHaitao Mao, Juanhui Li, Harry Shomer et al.2023 · International Conference on Learning Representations · 46 citations In Library
03Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New BenchmarkingJuanhui Li, Harry Shomer, Haitao Mao et al.2023 · Neural Information Processing Systems · 136 citations In Library
04Pitfalls in Link Prediction with Graph Neural Networks: Understanding the Impact of Target-link Inclusion & Better PracticesJing Zhu, Yuhang Zhou, V. Ioannidis et al.2023 · Web Search and Data Mining · 21 citations In Library
05A critical look at the evaluation of GNNs under heterophily: are we really making progress?Oleg Platonov, Denis Kuznedelev, Michael Diskin et al.2023 · International Conference on Learning Representations · 422 citations In Library
06Neural Common Neighbor with Completion for Link PredictionXiyuan Wang, Hao-Ting Yang, Muhan Zhang2023 · International Conference on Learning Representations · 98 citations In Library
07Graph Neural Networks for Link Prediction with Subgraph SketchingB. Chamberlain, S. Shirobokov, Emanuele Rossi et al.2022 · International Conference on Learning Representations · 136 citations In Library
08Flashlight: Scalable Link Prediction with Effective DecodersYiwei Wang, Bryan Hooi, Yozen Liu et al.2022 · LOG IN · 10 citations In Library
09Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and BeyondOleg Platonov, Denis Kuznedelev, Artem Babenko et al.2022 · Neural Information Processing Systems · 82 citations In Library
10Link Prediction on Heterophilic Graphs via Disentangled Representation LearningShijie Zhou, Zhimeng Guo, C. Aggarwal et al.2022 · arXiv.org · 20 citations In Library
11Understanding convolution on graphs via energiesFrancesco Di Giovanni, J. Rowbottom, B. Chamberlain et al.2022 · Trans. Mach. Learn. Res. · 70 citations In Library
12Shopping Queries Dataset: A Large-Scale ESCI Benchmark for Improving Product SearchC. K. Reddy, Lluís Màrquez i Villodre, Francisco B. Valero et al.2022 · arXiv.org · 105 citations In Library

Scroll for more · 38 remaining

Similar papers

Beyond Homophily in Graph Neural Networks: Current Limitations and Effective DesignsJiong Zhu, Yujun Yan, Lingxiao Zhao et al.2020 · arXiv (Cornell University) · 38 citations In Library
Graph Neural Networks for Graphs With Heterophily: A SurveyXin Zheng, Yue Wang, Yixin Liu et al.2026 · IEEE Transactions on Knowledge and Data Engineering In Library
Graph Neural Networks for Graphs With Heterophily: A SurveyXin Zheng, Yi Wang, Yixin Liu et al.2026 · IEEE Transactions on Knowledge and Data Engineering In Library
Graph Neural Networks for Graphs with Heterophily: A SurveyXin Zheng, Yixin Liu, Shirui Pan et al.2022 · IEEE Transactions on Knowledge and Data Engineering · 315 citations In Library
Revisiting the role of heterophily in graph representation learning: An edge classification perspectiveJincheng Huang, Ping Li, Rui Huang et al.2022 · arXiv (Cornell University) · 19 citations In Library
Learn from Heterophily: Heterophilous Information-enhanced Graph Neural NetworkYilun Zheng, Jiahao Xu, Lihui Chen2024 · arXiv (Cornell University) · 4 citations In Library
Revisiting the Role of Heterophily in Graph Representation Learning: An Edge Classification PerspectiveJincheng Huang, Ping Li, Rui Huang et al.2023 · ACM Transactions on Knowledge Discovery from Data In Library
Learn from Heterophily: Heterophilous Information-enhanced Graph Neural NetworkYilun Zheng, Jiahao Xu, Lihui Chen2025 In Library
Revisiting Heterophily For Graph Neural NetworksSitao Luan, Chenqing Hua, Qincheng Lu et al.2022 · arXiv (Cornell University) · 325 citations In Library
Revisiting Homophily Ratio: A Relation-Aware Graph Neural Network for Homophily and HeterophilyWei Huang, Xiangshuo Guan, Desheng Liu2023 · Electronics In Library

Peer review

Accept (poster)NeurIPS 2024 · via OpenReview
Reviewer ufZT4/10 · confidence 5/52024-06-25

Summary

This paper studies the impact of feature heterophily, rather than class heterophily, on link prediction tasks with GNN. It introduces the definition of non-homophilic link prediction based on the pairwise feature similarity of connected/non-connected node pairs of the graph. It further shows that the choice of encoders (GCN vs SAGE) and decoders (linear vs MLP) can lead to different link prediction performance on non-homophilic graphs. Various experiments on both synthetic and real graph benchmarks showcase that the feature heterophily can influence the GNNs' performance on link prediction tasks.

Strengths

1. The paper writing is clear and easy to understand. 2. The research problem of feature heterophily on link prediction tasks is novel. 3. The theoretical analysis part is comprehensive and intuitive. 4. The experiment is interesting, especially the comparisons of encoders/decoders on graphs with different levels of feature heterophily. It supports the claim made in the analysis part.

Weaknesses

1. While the research problem of feature heterophily is novel, the significance of the study is limited. The authors propose the concept of Heterophilic Link Prediction tasks. However, it is almost impossible to find such graphs in the real world. The most non-homophilic graph in the experiment is E-Commerce, which also has positive feature similarity. It will make the study more significant if the authors provide more real-world graphs with strong Heterophilic properties. Otherwise, it makes the study less practical and the Heterophilic Link Prediction becomes an *artificial* problem. 2. To consolidate the research problem and show that the synthetic graphs are valid in the real world, there can be some discussions about how the Synthetic Graph Generation is related to the other random graph generation methods. 3. While the research is centered around GNNs, Sec 3 and Sec 4.1 have no clear connection to GNNs. Also, Theorem 1 and 2 have no connection to GNNs. The discussion brings nothing beyond classical ML that a classification problem with complex decision boundaries requires a model with higher expressiveness to fit in.

Questions

1. Beyond the graphs with node features, is there any insight from this study on graphs without node features? Non-attributed graphs are a significant set of benchmarks for link prediction tasks. 2. Beyond the feature heterophily in the direct neighbors, are there any discussions or analyses about the feature heterophily of k-hop neighbors? I suspect in the real-world graphs, k-hop heterophily is much more common, which can further improve the significance of this study. 3. Is it possible to expand the scope of this study to any link prediction method rather than GNNs?

Rating

4

Confidence

5

Soundness

3

Presentation

4

Contribution

2

Limitations

See the weakness.

Authorsrebuttal2024-08-07

**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.

Reviewer ufZT2024-08-11

Thanks for addressing my questions in the rebuttal. However, I still have my main concerns as in the original review: 1. **One real-world dataset is not enough**: I appreciate the author's comments about the high-quality non-homophilic network for link prediction. I agree that finding such datasets was also a challenge when researchers started noticing heterophily issues in node classification tasks. In those studies, there are at least more than one heterophilic real-world datasets being evaluated. It can indicate that such heterophilic issues exist widely in real-world datasets. However, this study only finds one such dataset with heterophilic properties. This greatly undermines the generalization of this study. Researchers will be hardly interested in novel research that is limited to only one real-world dataset. On the other hand, if the paper can present more heterophilic datasets, it can enhance the contribution of this study, and have a huge impact on the research community just like heterophily issues in node classification. In this way, this problem can attract more interest. 2. **Method part is trivial**: If we look into the method part of the paper, the proposed method is trivial. If we look at the heterophilic papers the authors suggested, they presented novel methods even though evaluating heavily on the synthetic datasets. So another way to improve the study is to revise the method part, which can introduce more contribution to the research value. Due to the main concerns above, I keep my original rating.

Authorsrebuttal2024-08-12

Response to Reviewer ufZT (1)

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: | Dataset (from TUDataset) | Number of Graphs | |--------------------------|------------------| | aspirin | 111,763 | | benzene | 527,984 | | malonaldehyde | 893,238 | | naphthalene | 226,256 | | salicylic_acid | 220,232 | | toluene | 342,791 | | uracil | 133,770 | 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. | Dataset | Homophily Ratios | | ----------------------------------------- | ---------------- | | Ogbl-ppa | 0.74 | | Ogbl-collab (in the paper) | 0.70 | | Ogbl-citat2 (in the paper) | 0.40 | | WikiCS [4] | 0.35 | | PubMed [5] | 0.22 | | e-comm (in the paper) | 0.18 | | DBLP [5] | 0.13 | | Cora [5] / FacebookPagepage [10] | 0.12 | | AQSOL [6] / Yelp | 0.12 | | PPI [7] | 0.11 | | Facebook [8] | 0.11 | | Amazon-Photo [9] | 0.10 | | Amazon-Computers [9] | 0.07 | | Twitch-DE [10] | 0.07 | | Twitch-FR [10] | 0.06 | | BlogCatalog [8] | 0.06 | | CiteSeer [8] | 0.05 | | TWeibo [8] | 0.01 | | Karateclub [11] | -0.03 | | UPFD [12] | -0.10 | | BBBP instances [2] | -1.00 | | NCI1 instances [1] | -1.00 | | AIDS instances [1] | -1.00 | | QM9 instances [2] | -1.00 | 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](https://anonymous.4open.science/r/FeatureHeteroPlots-D591), 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!

Authorsrebuttal2024-08-12

Response to Reviewer ufZT (2)

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?

Authorsrebuttal2024-08-13

Response to Reviewer ufZT (3): results on additional heterophilic dataset

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). | Encoder | Decoder | MRR | std | | ------- | -------- | ----- | ---- | | GCN | DOT | 24.67 | 0.61 | | GCN | DistMult | 31.59 | 1.04 | | GCN | MLP | 52.90 | 0.86 | | SAGE | DOT | 42.26 | 0.54 | | SAGE | DistMult | 58.42 | 0.12 | | SAGE | MLP | 58.38 | 0.07 | | (NoGNN) | MLP | 21.15 | 0.23 | We will include these new results in the final version of the paper.

Reviewer YTzD7/10 · confidence 4/52024-07-10

Summary

This paper proposes to connect the feature similarity/dissimilarity to the linking possibilities between node pairs. It theoretically demonstrates the necessity of considering the overall feature heterophily of a graph for better link prediction by using a two-dimensional model. On the other hand, the numerical experiments are conducted to show the impact of feature heterophily on link prediction and the influences of encoder and decoder in final performance.

Strengths

1. The isssue of feature heterophily is valuable to be addressed, which can contribute to the understanding the formation of links among nodes. This work provides a concise theoretical analysis regarding it. 2. The paper is well-written and easy to follow. 3. The numerical experiments have been done to validate the theoretical results. The results are comprehensive and seems convincing to me.

Weaknesses

1. Since GNN encode node contents and local structures, it is worthwhile to see the relationship between feature similarity and structural similarity, i.e. whether these two properties are consistent, and its role in affecting the performances of heuristic methods and feature learning methods, e.g., the performance comparison on ogbl-collab for two types of link prediction approaches in Table 1. 2. More benchmark datasets can be considered to cover a diversity of feature similarity distribution.

Questions

1. In eq.(1), \hat{y} is the predicted link probability, so \hat{y}>=0. But in Sec.3.2 in theorem assumption, \hat{y} can be negative. I'm confused. 2. The green line in Fig.1 denotes the score distribution of positive node pairs, why all the scores for positive pairs are identical? 3. Theorem 1 is derived based on the assumption that nodes are 2-dimensionl. For high dimensional features, the learning rate is still linearly with 1/(1-M)? The generality of theoretical results is required to discuss. 4. What is the split for training/validation/test on real-world datasets? How does the size of training data affect the performance of heuristic methods and learning based methods, respectively? 5. I cannot understand why the buckets are divided according to the minimum degree of connected nodes (in x-axis dimension). Why not consider the degree differences or some functions of degrees of two nodes? At least on the surface, nodes with similar degrees have big chance to be linked in assortative graphs, and vice versa in dissassortiative graphs.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

As pointed out in Questions 3, the theoretical results for more general cases need to be addressed.

Reviewer dskj7/10 · confidence 3/52024-07-13

Summary

The paper analyze the impact of heterophily in node features on link prediction tasks, and the authors present a theoretical framework that highlights the different optimizations needed for the homophilic and heterophilic link prediction tasks.

Strengths

The paper analyze the impact of heterophily in node features on GNN performance, the authors argue that the homophilic and heterophilic link prediction tasks should be defined based on how the distributions of feature similarity scores between connected and unconnected nodes are separated, which is innovative. The paper reveals the fundamental differences in optimizations for homophilic and heterophilic link prediction tasks, as well as insights into effective decoder selection for non-homomorphic link prediction tasks.

Weaknesses

1、Some details in the paper are not very clear, such as How is feature extraction implemented? How to generate synthetic graphs that resemble different types of link prediction tasks by varying the feature similarity between connected nodes? 2、In addition, the hierarchical structure of the paper is not very reasonable, such as the chapter positions of the relevant work in Section 5.

Questions

1. How to generate synthetic graphs that resemble different types of link prediction tasks by varying the feature similarity between connected nodes? 2. the variation of the positive feature similarity scores affects the rate of change for the link prediction scores, the authors present definitions with intuitive examples in §3.1 and theoretical analysis in §3.2. but how the predicted link probability is derived?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

4

Limitations

Yes, the author has a clear understanding and explanation of the limitations of the proposed method.

Reviewer kFpa6/10 · confidence 4/52024-07-15

Summary

The paper examines how heterophily in node features affects the performance of Graph Neural Networks (GNNs) in link prediction tasks, which typically do not utilize node class labels. It introduces formal definitions of homophilic and non-homophilic link predictions, proposes GNN designs optimized for feature heterophily, and demonstrates through synthetic and real-world data that appropriate decoders and the separation of ego- and neighbor-embeddings can significantly enhance performance in non-homophilic settings.

Strengths

originality: good quality: good clarity: good significance: good

Weaknesses

The theoretical analysis is a bit over-simplified.

Questions

1. It's better to denote the mean feature vector of all nodes as $\hat{x}$ instead of $\hat{X}$ 2. Have you tried other heterophily-specific techniques, e.g. high-pass filter or negative message passing?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

the authors adequately addressed the limitations

Reviewer JA9K4/10 · confidence 4/52024-07-16

Summary

This paper analyzes the impact of node features in the link prediction task. Based on the feature similarity, it first categorizes and defines link prediction into homophilic, heterophilic and gated ones then shows the differences among them. Further, it explores the encoder and decoder choices along with the ego-neighbor separation for non-homophilic link prediction by theoretical and empirical analysis.

Strengths

* This paper provides a basics including definitions and preliminary conclusion for future non-homophilic link prediction works. * The overall writing is logical and easy to read.

Weaknesses

* The core conclusions are not exciting enough. For example, the different optimizations needed for homophilic and heterophilic link prediction tasks and the importance of adapting ego-neighbor separation for link prediction are actually intuitive. * The novelty is insufficient. The theoretical contributions are limited while the solutions are combinations of off-the-shelf modules. * Only one heterophilic real-world dataset is not enough, which may introduce bias and affect the generality of conclusions.

Questions

Some potential suggestions: * Add some heterophilic GNNs as the encoders for supplement. * Design new decoder specifically for heterophilic link prediction tasks. * Analyze the reasons for the appearance of heterophilic links.

Rating

4

Confidence

4

Soundness

2

Presentation

4

Contribution

2

Limitations

* Add more heterophilic real-world datasets to demonstrate the generality of conclusions.

Authorsrebuttal2024-08-13

Additional Rebuttal: Results on additional heterophilic dataset

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](https://openreview.net/forum?id=3LZHatxUa9&noteId=2UskaksmAp)). 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). | Encoder | Decoder | MRR | std | | ------- | -------- | ----- | ---- | | GCN | DOT | 24.67 | 0.61 | | GCN | DistMult | 31.59 | 1.04 | | GCN | MLP | 52.90 | 0.86 | | SAGE | DOT | 42.26 | 0.54 | | SAGE | DistMult | 58.42 | 0.12 | | SAGE | MLP | 58.38 | 0.07 | | (NoGNN) | MLP | 21.15 | 0.23 | We will include these new results in the final version of the paper.

Area Chair f8zT2024-08-11

Reminder to Check Authors' Reply

Dear Reviewers, Would you mind checking the authors' responses? AC

Reviewer YTzD2024-08-11

Thank the authors for the response to my concerns.

Reviewer kFpa2024-08-13

Thanks for the reply and I will keep my rating.

Reviewer JA9K2024-08-13

I appreciate the responses from authors. However, there are still some concerns remaining: * I agree broadly with the author's description of the paper's contributions, but they just don't seem exciting to me. An innovative and feasible solution based on these new formalizations and characteristics is the key for people to be convinced and follow this work. * Synthetic datasets struggle to simulate all the factors that affect performance in real-world datasets (e.g., degree distribution, noise, etc.), which is beyond feature similarity. Therefore, insufficient results on real-world datasets may cast doubt on the validity of the theory and findings in real-world application scenarios. Given the above concerns, I will keep my original rating.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC