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

Authors: jiong  zhu
gaotang  li
yao-an  yang
jing  zhu
xuehao  cui
danai  koutra
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 06:10:30

Abstract: 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. 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. Based on our definitions, we identify and analyze six real-world benchmarks spanning from homophilic to heterophilic link prediction settings, with graphs containing up to 30M edges. 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.

Main paper: 
 introduction: 
 Graph-structured data are powerful and widely used in the real world, representing relationships beyond those in Euclidean data through links. Link prediction, which aims to predict missing edges in a graph, is an important task with applications spanning from recommendation systems [41] to knowledge graphs [38] , and social networks [8] . Traditional algorithms for link prediction are heuristic-based and impose strong assumptions on the link generation process. To alleviate the reliance on handcrafted features, recent link prediction approaches are transformed by Graph Neural Networks (GNNs), which can effectively learn node representations in an end-to-end fashion. Vanilla GNN for link prediction (GNN4LP) methods keep the original GNN model for encoding node embeddings, followed by a decoder acting on pairwise node embeddings, e.g. dot product [20] . However, these methods are not effective at capturing pairwise structural proximity information [54, 24] , i.e. neighborhood heuristics such as the number of common neighbors. To further enhance model capabilities, the current state-of-the-art GNN4LP approaches augment GNNs by incorporating pairwise structural information [6, 52, 51, 49, 43] .Nevertheless, as the core of today's SOTA approaches, GNNs rely on the message-passing mechanism which works well when the underlying data exhibit homophily, i.e. connected nodes tend to share similar attributes with each other. Such inductive bias has been widely analyzed and has been shown to be an important factor for GNN's superior performance in the task of node classification on homophilic graphs [55, 14, 28, 29] . It has also been widely observed that GNN's performance degrades on heterophilic graphs in node classification tasks, where connected nodes tend to have different labels [1, 58, 60, 34, 17, 27] . In contrast, there are merely works focusing on the problem of heterophily in link prediction tasks: almost all existing definitions of homophily rely on the node class labels [25, 35] , which are often not available for the link prediction tasks. Furthermore, prior works on GNN4LP have largely focused on the effects of pairwise structural information to link prediction performance, while there is no dedicated work focusing on the effects of feature heterophily. In light of this, this work aims to characterize the notion of heterophily in the link prediction problem, understand the effects of heterophily and feature similarity in existing models that leverage node features, and explore designs to improve the use of dissimilar features in GNN link prediction. We detail our contributions as follows:• Definitions of Non-homophilic Link Prediction: We introduce formal definitions of homophilic and non-homophilic link prediction tasks: instead of relying on the magnitude of feature similarity, our definitions are based on the separation of feature similarity scores between edges and non-edges, which is justified by a concise theoretical framework that highlights the different optimizations needed for the respective tasks.• Designs Empowering GNNs for Non-homophilic Link Prediction: We identify designs for GNN encoders and link probability decoders that improve performance for non-homophilic link prediction settings and show that (1) decoders with sufficient complexity are required for capturing non-homophilic feature correlations between connected nodes; (2) ego-and neighbor-embedding separation in GNN message passing improves their adaptability to feature similarity variations.• Benchmarks for Non-homophilic Link Prediction: We introduce six real-world datasets spanning from homophilic to heterophilic settings for link prediction, with edge counts ranging from 88K to over 30M, to benchmark the performance of various GNN models. These datasets come from diverse domains and exhibit different levels of feature similarity, providing a robust foundation for evaluating GNN adaptability to non-homophilic conditions in link prediction tasks.• Empirical Analysis on Impacts of Feature Heterophily: We conduct comprehensive empirical analyses using both synthetic and real-world graphs. Through synthetic graphs with controlled feature similarity levels, we analyze how link prediction methods with different designs adapt to varying levels of heterophily. On real-world graphs, we evaluate both overall performance and local behavior across edges with different node degrees and feature similarities, revealing important insights about model adaptability in practice. 
related work: 
 Graph Neural Networks for Link Prediction. Traditional algorithms for link prediction are primarily heuristic-based, which have strong assumptions on the link generation process. These approaches compute the similarity scores between two nodes based on certain structures or properties [2, 3, 5, 51] . Later, various representation-based algorithms for link prediction were proposed, which aim at learning low-dimensional node embeddings that are used to predict the likelihood of link existence between certain node pairs and usually involve the use of GNNs [21, 15, 42] . Compared with the heuristic-based algorithms, representation-based algorithms do not require strong assumptions and perform learning over the graph structure and node features in a unified way. A representative method is the Variational Graph Autoencoder [20] , which uses GCN as the encoder for learning node representations and inner product as the decoder for pairwise link existence predictions. More recently, the state-of-the-art methods for link prediction are built on top of the representation-based algorithms and augment them with additional pairwise information. For instance, subgraph-based approaches perform link prediction between two nodes by first extracting their enclosing subgraphs and subsequently applying the standard representation-based algorithms on the extracted subgraphs [52, 6, 62] . Concurrently, other works have been proposed to augment GNN learning with common neighbor information [43, 49, 43] . Despite the tremendous success, prior link prediction works mainly assume homophily, where node pairs with similar features or neighbors are more likely to link together. In contrast, this work considers a more general setting where there may be a spectrum of low-to-high homophily in the underlying data, characterizes a notion of heterophily in link prediction and explores how popular approaches perform under this characterization. Related work also examines the influence of data for link prediction from a joint perspective of graph structure and feature proximity [30, 22] . While these works provide valuable insights into the interplay between structural and feature information, our work specifically focuses on characterizing and analyzing the impact of node feature through the lens of heterophily, offering complementary insights into how varying degrees of feature similarity affect link prediction performance.There is a rich literature on graph neural networks addressing heterophily, but most of them tackle the node classification task [1, 58, 60, 34, 17, 27] . Very few works focus on the problem of link prediction under heterophily. Among them, Zhou et al. [56] propose to disentangle the node representations from latent dissimilar factors, and Di Francesco et al. [9] extend the physics-inspired GRAFF [10] , originally designed for handling heterophilic node classification tasks, to heterophilic link prediction tasks. These works use the same class-dependent homophily measure as typically used in node classification, while our work emphasizes the influence of features in link prediction and more systematically benchmarks model performance against different homophily levels. 
notation and preliminaries: 
 Let G = (V, E) be an undirected and unweighted homogeneous graph with node set V and edge set E.We denote the 1-hop (immediate) neighborhood centered around v as N (v) (G may have self-loops), and the corresponding neighborhood that does not include the ego (node v) as N (v). We represent the graph by its adjacency matrix A ∈ {0, 1} n×n and its node feature set as X with matrix form X ∈ R n×F , where the vector x v corresponds to the ego-feature of node v, and {x u : u ∈ N (v)} to its neighbor-features. We further represent the degree of a node v by d v , which denotes the number of neighbors in its immediate neighborhood N (v).Graph Neural Networks for Link Prediction. Following [23, 53] , we define the task of link prediction to be estimating the likelihood of reconstructing the actual adjacency matrix. Formally, ŷi,j = Âi,j = p(i, j|G, X),where ŷi,j or Âi,j is the predicted link probability between nodes (i, j) and was traditionally calculated by heuristics-based algorithms. For (i, j) in the training set, we set the ground truth probability y i,j = A i,j . Existing GNN4LP approaches typically use a GNN-based method for encoding node representations (denoted by ENC) and some decoder function (denoted by DEC) between node embedding pairs:ŷi,j = Âi,j = DEC(z i , z j ), whereEQUATIONThe original graph autoencoder approach [20] uses a two-layer GCN [21] as the encoder and a dot product as the decoder. There are many different choices of encoders that do not need to strictly follow the original GNN architecture. For the decoder, while dot product remains a popular simple choice [20, 33] , more expressive alternatives include concatenation followed by an MLP.Graph Feature Similarity. We measure the "graph feature similarity" through averaging the mean-centered feature similarity from connected node pairs. Definition 1 (Node Feature Similarity) For a node pair (u, v) with x u and x v as the node features and a similarity function ϕ : (•, •) → R, we define the node feature similarity as k(u, v) = ϕ(x u , x v ).In this work, we set ϕ(x u , x v ) = xu• xv ∥xu∥∥xv∥ to be the mean-centered cosine similarity of node features, where we denote the mean feature vector of all nodes in the graph as x = 1 |V| v∈V x v , and the mean-centered node feature for node v as xv = x v -x. Empirically, we find that the mean-centering operation is crucial for accurate characterization of the pairwise feature similarity and its impact on link prediction performance. We further define the graph feature similarity as follows. Figure 1 : Categorizing link prediction tasks based on the distribution of feature similarity scores of positive node pairs (i.e., edges -colored in green) and negative node pairs (non-edges -colored in red): two distributions whose density is visualized in the plots are (approximately) separated by the threshold(s) M . Homophilic and heterophilic link prediction differs in whether the positive similarity scores fall into the larger or smaller side of the threshold M , while the magnitude of M indicates the variance of positive similarity. Gated link prediction is a more complex case where the distribution of positive and negative similarity scores cannot be separated by a single threshold.Definition 2 (Graph Feature Similarity) We measure the graph feature similarity K through averaging the feature similarity of all its connected nodes pairs:K = (u,v)∈E k(u,v) |E| .Unlike the homophily measures defined on node class labels which are non-negative [25] , the feature similarity k(u, v) ∈ [-1, 1] can additionally be negative, indicating negative correlations. We refer to the graph as positively correlated if K > 0 and negatively correlated if K < 0.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
homophilic & heterophilic link prediction: 
 While existing works on node classification usually define homophilic or heterophilic graphs by whether the majority of connected nodes share the same class labels [25, 35] , the class information is not available for link prediction. Instead, we 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, as these definitions capture the fundamental differences on how link prediction scores are correlated with feature similarity scores. Within the category of homophilic or heterophilic tasks, we further show that the variation of the positive feature similarity scores affects the rate of change for the link prediction scores. We present definitions with intuitive examples in §4.1 and theoretical analysis in §4.2.We begin our discussion by considering the distributions of feature similarity scores for a random positive (edge) and negative (non-edge) node pair in the graph: consider the set of feature similarity scores for positive (edge) node pairs in the graph as K pos , and negative (non-edge) node pairs as K neg . We first formalize different categories of link prediction tasks, which are defined by how the distributions of K pos and K neg are (approximately) separated:Definition 3 (Homophilic Link Prediction) The task is homophilic if M ∈ R exists such that for most samples Kpos ⊂ K pos and Kneg ⊂ K neg it satisfies sup( Kneg ) < M ≤ inf( Kpos ).Prior works have mostly focused on the homophilic category for the link prediction problem while overlooking other possibilities. For other cases where the homophilic conditions are not satisfied, we refer to them generally as non-homophilic link prediction problems. In the definition below, we formalize an easy type of non-homophilic link prediction problem:Definition 4 (Heterophilic Link Prediction) The task is heterophilic if M ∈ R exists such that for most samples Kpos ⊂ K pos and Kneg ⊂ K neg it satisfies sup( Kpos ) ≤ M < inf( Kneg ).We give intuitive examples of homophilic and heterophilic link prediction tasks in Fig. 1 : the key difference between homophilic and heterophilic tasks is whether K pos is predominantly distributed above threshold M while K neg is below M (homophilic), or vice versa (heterophilic), as shown in Fig. 1a vs. 1c. The categorizations of homophilic/heterophilic link prediction tasks should not be confused with the magnitude of M that indicates the variance of positive similarity scores: while its magnitude does not determine the type of the link prediction problem, our analysis in the next section does show that it affects the rate of change for the link prediction scores.However, beyond the heterophilic setting defined above, there are other non-homophilic settings with even more complexity, where the distribution of K pos and K neg cannot be separated by a single threshold M . Most of these cases are too complex to be formalized and studied theoretically, but we formalize one of them (Fig. 1d ) below and later report empirical results ( § 6).Definition 5 (Gated Link Prediction) The task is gated if it is neither homophilic nor heterophilic, butM 1 , M 2 ∈ R exist such that M 2 ≥ sup( Kpos ) ≥ inf( Kpos ) ≥ M 1 .In §4.1, we have situated our discussions of link prediction tasks based on how the positive and negative samples are separated in the feature similarity score space. In this section, we reveal on a stylized learning setup the fundamental differences in optimizations for homophilic and heterophilic link prediction tasks.Figure 2 : Link prediction scores ŷu ′ v ′ for decoders optimized under homophilic (yellow) and heterophilic (blue) setups in Thm. 1 (for M = 0.5).Theoretical Assumptions. Assume a training graph with node v ∈ V whose feature vectors are 2-dimensional unit vectors and can be represented asx v = (cos θ v , sin θ v ).We consider a DistMult decoder for predicting the link score for candidate node pair u, v ∈ V with feature vectors x u , x v . Specifically, the link score is calculated as ŷu,v = (x u ⊗ x v ) T w + b, where w and b are learnable parameters for the decoder, with training loss functionL = y • ReLU(-ŷ) + (1 -y) • ReLU(ŷ)such that ŷ ≥ 0 for all edges (positive samples) and ŷ < 0 otherwise. Furthermore, we assume that the K pos and K neg are ideally separable by a threshold M ∈ [0, 1] in the feature similarity score space such that the homophilic or heterophilic conditions hold for all samples.With the above assumptions, we now show that (1) the predicted link score and feature similarity scores are positively correlated for homophilic tasks, while negatively correlated for heterophilic tasks;(2) the change rate for the predicted link probability with respect to the feature similarity is determined by the magnitude of the threshold M that separates the positive and negative samples.Theorem 1 Following the above assumptions, consider two DistMult decoders that are fully optimized for homophilic and heterophilic link prediction problems respectively. Given an arbitrary node pair (u ′ , v ′ ) with node features x u ′ = (cos θ u ′ , sin θ u ′ ) and x v ′ = (cos θ v ′ , sin θ v ′ ) and pairwise feature similarity k(u ′ , v ′ ), the following holds for the predicted link probability ŷu ′ v ′ :• For the homophilic problem where sup(K neg ) < inf(K pos ) = M ≤ 1, when bounding ŷu,v = 1 if k(u, v) = 1 during training, ŷu ′ v ′ increases with k(u ′ , v ′ ) at a linear rate of 1 (1-M ) ;• For the heterophilic problem where-1 ≤ sup(K pos ) = M < inf(K neg ), when bounding ŷu,v = 1 if k(u, v) = -1 during training, ŷu ′ v ′ decreases with k(u ′ , v ′ ) at a linear rate of 1 (1-M ) .We give the proof in App. §B.1 and visualize in Fig. 2 how the predicted link score ŷu ′ v ′ changes under the homophilic and heterophilic settings. Though the above results are derived under simplified assumptions, it clearly highlights the different optimizations needed for homophilic and heterophilic link prediction tasks that have not been studied in prior literature. In §6, we observe that these differences go beyond our theoretical assumptions and affect the performance of all GNN encoders and link prediction decoders on datasets with higher complexity, which warrant our study of effective encoder and decoder choices for non-homophilic link prediction in the next section. 
encoder & decoder choices for link prediction beyond homophily: 
 In §4, we gave formal definitions of homophilic and heterophilic link prediction tasks and highlight their differences in model optimizations. As non-homophilic settings are largely overlooked in prior literature, we aim to verify whether existing GNN message passing designs for node features remain effective beyond homophily. We follow the encoder-decoder perspective in [16] and discuss designs for both GNN encoder and link prediction decoder that adapt to non-homophilic settings.For homogeneous graphs that only have one edge type (as opposite to heterogeneous or knowledge graphs), popular decoder choices for deriving link probability from node representations are either a simple dot product (DOT) operation or more complex multi-layer perceptron (MLP). While the MLP decoder has a stronger representation power due to its non-linearity, the inner product decoder is more preferred in large-scale applications due to its fast inference speed: it is well established that maximum inner product search (MIPS) can be approximated with sublinear complexity using packages such as Faiss [12] . A prior work [44] has benchmarked the performance of different link prediction decoders on several OGB datasets [18] and proposed a sublinear approximation of MLP decoder during inference time. However, no study has been conducted on the performance of decoders for non-homophilic link prediction tasks across the negative to positive similarity spectrum.Our takeaways for effective decoder choices for non-homophilic link prediction tasks are as follows:(1) for non-homophilic (e.g., gated) tasks, only non-linear decoders such as MLP are suitable; (2) for heterophilic tasks, a linear decoder with learnable weights (e.g., DistMult [47] ) can be used in lieu of MLP to achieve better scalability while maintaining comparable performance; (3) dot product decoder is only suitable for homophilic link prediction tasks.Theoretically, we formalize our first takeaway with the below theorem, which shows the limitations of using linear decoders (such as DOT and DistMult) in non-homophilic link prediction tasks:Theorem 2 No parameter exists for a single linear decoder that perfectly separates link probability for edges and non-edges for gated link prediction.We give the proof in Appendix §B.2. For linear models, while both DistMult and DOT product decoders share the same time complexity during inference, we observe empirically in §6 that DistMult outperforms DOT decoder by up to 55% on non-homophilic link prediction tasks. Intuitively, the learnable weights in DistMult decoder allow the model to capture the negative correlation between connected node features and improve its effectiveness for heterophilic tasks.We now consider the impact of GNN architectures on non-heterophilic link prediction performance. In particular, we examine whether the effective designs for node classification beyond class homophily can be transferred to link prediction tasks beyond feature homophily. A design that significantly improves classification performance under low class homophily is the separation of ego-and neighborembeddings in GNN message passing, which has consistently shown to improve classification performance across multiple studies [60, 36] . As real-world graphs usually follow a power-law degree distribution and exhibit large variation in node degrees, prior work has used the robustness of GNN models to degree shift as a proxy to measure the generalization ability of GNN models for heterophilic node classification [60] . We follow a similar approach in the theorem below and show that a GNN model that embeds ego-and neighbor-features together is less capable of generalizing under heterophilic settings than a graph-agnostic model. We give the proof in Appendix §B.3.Theorem 3 Consider the same DistMult decoder and loss function L as the assumptions in §4.2, but trained on a heterophilic graph where (1) feature vectors for all nodes can be either 2 .x 1 = (cos θ 1 , sin θ 1 ) or x 2 = (cos θ 2 , sin θ 2 ), 
empirical analysis: 
 We aim to understand through empirical analysis (1) what are the performance trends of link prediction methods under different link prediction tasks in the full spectrum of negative to positive feature similarity, and (2) how different encoder and decoder designs adapt to non-homophilic link prediction tasks, including variations of feature similarity and node degrees within the same graph. We first introduce the link prediction methods that we consider in our experiments, and then present the results on synthetic and real-world datasets. More details about setups and results are available in App. A. 3Link Prediction Methods. As in the previous sections, we follow an encoder-decoder framework and consider different combinations of both components. For decoders, we consider the options mentioned in §5.1: (1) Dot Product (DOT), (2) Multi-Layer Perceptron (MLP), and (3) DistMult [47] .For encoders, we consider two GNN methods to study how separating ego-and neighbor-embeddings affects link prediction performance: (1) GraphSAGE [15] which separates ego-and neighborembeddings during message passing, and (2) Graph Convolutional Network (GCN) [21] , which does not make this separation. We couple these encoders with the decoders above to form six GNN4LP models.Furthermore, to understand how message passing designs affect performance for GNN4LP models that leverage both node features and pairwise structural information, we consider BUDDY [6] , a state-of-the-art method reported in a recent benchmark [23] . BUDDY augments GNN encoders with subgraph sketching to capture structural information. Specifically, we consider three variants: (3) BUDDY-GCN, which uses GCN for feature aggregation, (4) BUDDY-SIGN, which uses SIGN aggregation [38] to separate ego-and neighbor-embeddings during message passing, and (5) NoFeat, a structure-only baseline that excludes node features and relies solely on structural information for link prediction. All BUDDY variants use an MLP decoder as part of their architecture.Finally, we also consider these link prediction heuristics tested in [6] : Common Neigbhors (CN) [32] ,Resource Allocation (RA) [57] , Adamic-Adar (AA) [2] , and Personalized PageRank (PPR) [19] .We generate synthetic graphs that resemble different types of link prediction tasks (i.e., homophilic, heterophilic, and gated) by varying the feature similarity between connected nodes. These graphs provide controlled environments that allow us to focus on the effects of feature similarity on link prediction performance without mingling them with other data factors such as structural proximity.We give the details of the synthetic graph generation process and the experiment setup in App. §A.Performance Trend Across the Full Similarity Specturm. We visualize the performance trends per method in Fig. 3 and present the numerical results in Table 2 . We observe that the performance of all feature-consuming methods is significantly affected by the level of feature similarity: most methods reach their best performance at the positive extreme (homophilic tasks) and the second best at the negative extreme (heterophilic tasks); between the two extremes (gated tasks), the performance of all methods drops significantly as the feature similarity score approaches 0, which creates a U-shaped performance trend across the feature similarity spectrum. It is worth noting that graph-agnostic MLP decoder without GNN (NoGNN) also exhibits the U-shaped performance trend, which suggests the challenges of leveraging node features effectively in these settings for non-GNN methods as well.Intuitively, as the similarity scores for a random pair of nodes follow a normal distribution centered around 0, the performance drop when average feature similarity scores approach 0 can be contributed to the reduced distinguishability between the similarity scores of edges and non-edges in the graph.For feature agnostic heuristics such as Common Neighbors and Personalized PageRank, they show mostly unproductive performance except at the positive extreme. This suggests that graphs formed by positive feature correlations are also likely to show strong structural proximity, which is beneficial for the heuristic-based methods for the homophilic link prediction task.Decoder Choices: MLP and DistMult over DOT. We further validate our main points in §5 regarding how different decoder choices adapt to non-homophilic link prediction settings. In Fig. 3a-b , we compare the performance of different decoders with fixed SAGE and GCN encoders, respectively. With both SAGE and GCN encoders, we observe that DOT decoder performs the worst among all choices across all feature similarity levels: it is outperformed by MLP decoder with a margin of 50% in the negative extreme and 10% in the positive extreme under SAGE encoder. DistMult decoder performs significantly better than the DOT decoder, especially in the region of negative feature similarity: at the negative extreme, DistMult decoder outperforms DOT decoder by 55% and even outperforms MLP decoder by 5.6%. Empirically, we observe that the optimization process of DistMult is more stable than MLP when using a SAGE encoder in the negative similarity region, allowing it to reach optimal performance without suffering from instabilities at the negative extreme. However, the performance of DistMult coupled with SAGE decoder is significantly lower than MLP with up to 37% gap between the negative and positive extremes, where the link prediction tasks are gated instead of being homophilic or heterophilic. This validates our theoretical analysis in §5.1 that the linear decoders like DOT and DistMult are not suitable for the settings where non-linear separation between similarity scores of edges and non-edges are required. With GCN encoder, the performance of DistMult decoder is mostly on par with MLP decoder across the spectrum, which shows that the performance bottleneck is on the encoder side rather than the decoder side. Overall, MLP decoder is the most robust choice across different feature similarity levels and link prediction tasks, yielding the best performance in all but one cases when coupled with SAGE encoder, with DistMult being a more scalable alternative for homophilic and heterophilic link prediction tasks.Encoder Choices: Importance of Ego-and Neighbor-Embedding Separation. In Fig. 3c , we compare the performance of different encoder choices with fixed MLP decoder, which is the bestperforming decoder option for nearly all cases. In addition to GCN and SAGE encoders that rely only on node features, we also include variants of BUDDY [6] that leverage structural proximity and (optionally) node features. Comparing between SAGE and GCN encoders, we observe that SAGE consistently outperforms GCN across all feature similarity levels by up to 44%. For BUDDY variants with SIGN and GCN feature encoders, we also observe consistently better performance with SIGN encoder across all feature similarity levels with up to 9.0% gain. Both comparisons suggest the importance of adopting ego-and neighbor-embedding separation in GNN encoder design for link prediction: as discussed in §5.2, this design allows GNN encoders to learn representations that are more robust to variations of node degrees and feature similarity levels in the graph instead of overfitting to specific degrees or similarity scores, which we also observe in the real-world datasets.Importance of Node Features vs. Structural Proximity. Here we compare two approaches in Fig. 3c : (1) SAGE+MLP, which combines node features with implicit graph structural information captured through GNN message passing, and (2) BUDDY-SIGN, which additionally incorporates explicit structural proximity (e.g., number of shared neighbors) through subgraph sketching. We find that BUDDY-SIGN's performance is consistently lower than SAGE+MLP across all feature similarity levels, with the gap reaching up to 26% between the negative and positive extremes. This suggests that when graph connections are predominantly driven by feature similarity (as in our synthetic graphs), the additional structural information from subgraph sketching may not provide added benefit beyond the structural information already captured by GNN message passing. While real-world graphs are typically influenced by both feature similarity and structural proximity, these results emphasize the importance of carefully balancing these two information sources in link prediction models, particularly for non-homophilic settings where structural proximity alone may be less informative. Next we compare performance of different link prediction methods on real-world graphs of varying sizes and feature similarities. Unlike our synthetic graphs where the feature similarity of connected nodes is controlled, real-world graphs tend to have a significantly larger variation in feature similarity across edges. Our analysis aims to not only compare the overall performance of the methods, but also to understand their local performance discrepancies across feature similarity variations within a graph, which is typically overlooked in the literature.Experiment Setups. Based on our definitions ( §4.1), we employ 6 real-world datasets spanning from homophilic to non-homophilic link prediction tasks: ogbl-collab [18] , ogbl-citation2 [18] , e-comm [61] , facebook [39] , PPI [63] , and amazon-computers [40] . The details and experiment setup are in App. §A. We report dataset statistics in Table 1 and show feature similarity distributions of edges vs. random node pairs in Fig. 6 (App. A): while ogbl-collab and ogbl-citation2 are approximately homophilic, e-comm, facebook, PPI and amazon-computers are non-homophilic. We have also identified additional real-world datasets exhibiting feature heterophily in App. §C.Motivated by prior findings about the interplay of node degree and heterophily [46, 59, 26] , we analyze how different encoder and decoder choices perform across edges with varying graph properties. Specifically, we group edges into buckets based on two key properties: (1) the degrees of their connected nodes and (2) their feature similarity scores. For each bucket, we compute the average link prediction performance of different methods, with detailed methodology in App. §A. To understand how encoders and decoders adapt to these property variations, we fix one component (encoder or decoder) while varying the other, and visualize the resulting performance differences across buckets.The main results are shown in Fig. 5 , with additional analyses in Fig. 7 8 9 10 .Significance of Decoder Choices. We first compare the performance of different decoder choices while fixing the encoder. As we observed on the synthetic datasets, for both GCN and SAGE encoders, MLP has the highest overall performance, followed by DistMult and DOT. In terms of the robustness to local variations of node degrees and feature similarity scores, we observe in Fig. 5c that despite MLP only outperforms DOT by 2.3% on the full test split, it outperforms DOT on the majority of the feature similarity range by up to 7.4% as DOT overfits to the lowest feature similarity bucket; we also observe similar overfitting of DistMult to the highest feature similarity bucket in Fig. 5a , despite it being significantly more robust than DOT. Overall, MLP is the most robust choice for link prediction tasks on real-world graphs with varying feature similarity levels.Significance of Encoder Choices. We finally compare different encoder choices while fixing the decoder. Matching our observations on synthetic datasets, we find that SAGE encoder outperforms the GCN encoder by significant margin under most datasets and decoder choices. On e-comm dataset, the performance of GCN on the full test split is on-par with SAGE under MLP decoder, but we observe in Fig. 5d that GCN largely overfits to the edges in the high feature similarity and low degree bucket, with SAGE outperforming GCN by up to 3.5% in the remaining buckets. The similar overfitting is also observed on SIGN vs. GCN with BUDDY and MLP decoder on ogbl-citation2 (Fig. 5b ). These observations show that the separation of ego-and neighbor-embeddings in the SAGE and SIGN encoders help GNNs to better adapt to local variations in feature similarity and node degrees in the real-world graphs.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: The paper specifies training and test details in §6 and Appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion: 
 We characterized non-homophilic link prediction through the distributions of feature similarities between linked and unlinked nodes, and proposed a theoretical framework highlighting the optimizations needed for different tasks. Our analysis revealed how link prediction encoders and decoders adapt to varying feature homophily levels, identifying key designs-learnable decoders (e.g., MLP or DistMult) with GNN encoders that separate ego-and neighbor-embeddings-for improved link prediction performance beyond homophily. Experiments on synthetic and real-world datasets demonstrated the effectiveness of these designs across the feature similarity spectrum.In summary, our work advances the understanding of heterophilic link prediction, and lays the groundwork for future research. First, we believe that there is a need for introducing more featureheterophilic benchmark datasets for link prediction. Expanding the diversity of available datasets would enhance the generality and practical significance of studies in this area, allowing for more robust validation of methodologies and mitigating potential biases from the scarcity of strongly heterophilic benchmarks. Second, additional in-depth theoretical frameworks could provide a more comprehensive understanding of the complexities inherent in real-world networks. This includes exploring the interplay between feature similarity and structural similarity and how these relationships influence the performance of different link prediction methods.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: Error bars for experiments have been included, and the variability captured have been stated in App. §A.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: This paper discusses foundational research in GNN and is not tied to particular applications that could result in potential negative societal impacts. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: This paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Computing Resources. For most experiments, we use a workstation with a 12-core AMD Ryzen 9 3900X CPU, 64GB RAM, and an NVIDIA Quadro P6000 GPU with 24 GB GPU Memory. BUDDY experiments on ogbl-citation2 require higher CPU RAM, in which case we use a server with 128GB RAM and an NVIDIA A100 GPU with 48 GB GPU Memory.Synthetic Graph Generation. The synthetic graphs are generated by random sampling 10,000 nodes with their features in ogbl-collab [18] and connect 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. We list the average feature similarity score of each synthetic graph in Table 3 : the negative extreme is the most negatively correlated graph featuring edges with feature similarity scores ranging in [-1, -0.33], which resembles the heterophilic link prediction task; the positive extreme is the most positively correlated graph with edges similarity scores in [0.44, 1.00], resembling the homophilic link prediction task. Other synthetic graphs correspond to the gated link prediction task with feature similarity scores ranging from the negative to positive spectrum.Comparing with synthetic graph generation methods in existing literature studying heterophilous graphs, most of these methods focus on node classification tasks. For example, [1] and [60] propose modified preferential attachment processes where edge probabilities are determined by both class compatibility matrices and node degrees, while [7] employs a contextual stochastic block model (CSBM). However, these approaches control homophily/heterophily levels based on node class labels, which are typically unavailable in link prediction settings. More recently, [22] proposed NetInfoF for generating link prediction benchmarks by controlling correlations between node features and edge existence. However, their approach only supports three discrete correlation levels (fully, partially, or uncorrelated) and cannot generate graphs with negatively correlated features among connected nodes. In contrast, our generation process allows for fine-grained control over feature similarity distributions and can produce graphs spanning the full spectrum from negative to positive feature correlations.Experiment Setups of the Synthetic Graphs. For each generated synthetic graph, we randomly split the edges into training, validation, and test sets with a ratio of 8:1:1. We repeat each experiment 3 times with different random seeds and report the average performance with standard deviation in Table 2 . We use 2 convolutional layers for SAGE and GCN, and 256 hidden dimensions for all neural network models.Additional Experiment Setups of the Real-world Datasets. We consider three real-world datasets:(1) ogbl-collab [18] , a collaboration network between researchers, with nodes representing authors, edges representing co-authorship, and node features as the average word embeddings of the author's papers;(2) ogbl-citation2 [18] , a citation network where nodes represent papers and edges represent citations, with the average word embeddings of the paper's title and abstract as node features; (3) e-comm [61] , a sparse graph extracted from [37] representing exact matches of queries and related products in Amazon Search, with BERT-embeddings of queries and product information as node features. For ogbl-collab and ogbl-citation2, we follow the recommended metrics (Hit@50 and MRR, respectively) and train-validation-test splits provided by OGB [18] . For e-comm, we use the splits shared by [61] , adopt the SpotTarget approach [61] as graph mini-batch sampler for training and use MRR as the evaluation metric. We report each method's average performance on the full test split across 3 runs with different random seeds, and present the results in Table 1 .Creation of Node Degree and Feature Similarity Buckets on Real-world Datsets. To create these buckets, we first calculate each edge's feature similarity score and the minimum degree of its two connected nodes. We then create on each graph three buckets per property based on the distribution of feature similarity scores and node degrees, with each bucket covering one-third quantile, except for node degrees of e-comm, where only two buckets are created due to its sparsity. Homophilic Link Prediction Problem. For homophilic link prediction problem, we have 1 ≥ inf(K pos ) = M > sup(K neg ). As M = inf(K pos ), a pair of nodes u, v ∈ V must exist in the training graph with feature vectors x u = (cos θ u , sin θ u ) andx v = (cos θ v , sin θ v ) such that k(u, v) = cos(θ u -θ v ) = M .Now let us consider a fully optimized DistMult decoder for the problem. We parameterize the DistMult decoder with w = (w 1 , w 2 ) and b; in this case, the predicted link probabilityŷuv = (x u ⊗ x v ) T w + b = w 1 cos θ u cos θ v + w 2 sin θ u sin θ v + b As M = inf(K pos ), any pairs of nodes (u ′ , v ′ ) that has feature similarity k(u ′ , v ′ ) slightly smaller than M should have ŷu ′ v ′ ≤ 0.Therefore, we must have ŷuv = 0. Furthermore, since we are boundingŷu ′ v ′ = 1 if k(u ′ , v ′ ) = 1during training, we must have ŷuu = 1 and ŷvv = 1. Using ŷuv = 0, ŷuu = 1 and ŷvv = 1, we can obtain the solutions for w 1 , w 2 and b as follows:w 1 = 1 1 -cos(θ u -θ v ) , w 2 = 1 1 -cos(θ u -θ v ) , b = 1 cos(θ u -θ v ) -1 + 1As w 1 = w 2 = 1 1-M , we have the similarity score for arbitrary node pair (u ′ , v ′ ) asŷu ′ v ′ = 1 1 -M cos(θ u ′ -θ v ′ ) + 1 M -1 + 1 = 1 1 -M k(u ′ , v ′ ) + 1 M -1 + 1We can verify that the above link prediction model is fully optimized with loss function L = 0 as it always yield ŷuv ≥ 0 for k(u ′ , v ′ ) ≥ M and ŷuv < 0 for k(u ′ , v ′ ) < M . Therefore, we show that ŷu ′ v ′ increases with k(u ′ , v ′ ) at a linear rate of 1 (1-M ) for homophilic link prediction problem.Heterophilic Link Prediction Problem. For heterophilic link prediction problem, we have -1 ≤ sup(K pos ) = M < inf(K neg ). As M = sup(K pos ), a pair of nodes u, v ∈ V must exist in the training graph with feature vectors x u = (cos θ u , sin θ u ) andx v = (cos θ v , sin θ v ) such that k(u, v) = cos(θ u -θ v ) = M .Similar to the homophilic case, as M = sup(K pos ), any pairs of nodes (u ′ , v ′ ) that has feature similarity k(u ′ , v ′ ) slightly larger than M should have ŷu ′ v ′ ≤ 0. Therefore, we must have ŷuv = 0. Furthermore, since we are bounding ŷu ′ v ′ = 1 if k(u ′ , v ′ ) = -1w 1 = - 1 1 + cos(θ u -θ v ) , w 2 = - 1 1 + cos(θ u -θ v ) , b = 1 - 1 1 + cos(θ u -θ v ) As w 1 = w 2 = -11+M , we have the similarity score for arbitrary node pair (u ′ , v ′ ) asŷu ′ v ′ = - 1 1 + M cos(θ u ′ -θ v ′ ) + 1 - 1 1 + M = - 1 1 + M k(u ′ , v ′ ) + 1 - 1 1 + MWe can similarly verify that the above link prediction model is fully optimized with loss function L = 0 as it always yield ŷuv ≥ 0 for k(u ′ , v ′ ) ≤ M and ŷuv < 0 for k(u ′ , v ′ ) > M . Therefore, we show that ŷu ′ v ′ decreases with k(u ′ , v ′ ) at a linear rate of 1 (1-M ) for heterophilic link prediction problem. ■Proof 2 The decision boundary for gated link prediction is non-linear since it involves multiple disjoint intervals for each class (edge and non-edge). A linear model can only create a single threshold x 0 to separate the classes: one region for x ≤ x 0 and the other for x > x 0 . Therefore, there always exists misclassified points regardless of the choice of x 0 . ■Proof 3 We begin by considering the decoder trained with the linear GNN representation r u that does not separate ego-and neighbor-embeddings in its message passing. Following our assumptions, the aggregated representation r 1 for training nodes with feature x 1 is r 1 = 1 d+1 x 1 + d d+1 x 2 , and r 2 can be obtained similarly.Similar to Proof 1, we parameterize the DistMult decoder with w = (w 1 , w 2 ) and b. Suppose node u has feature vector x 1 and node v has feature vector x 2 . As the training graph is heterophilic and (u, v) is connected on the graph, we should have ŷuv > 0 in this case. Without the loss of generality, we set ŷuv = 1. Furthermore, as self-loops (u, u) and (v, v) are not connected in the graph, we should also have ŷuu = α < 0 and ŷvv = α < 0. Using ŷuv = 1, ŷuu = α < 0 and ŷvv = α < 0, we can obtain the solutions for w 1 , w 2 and b as follows:w 1 = w 2 = - (α -1)(d + 1) 2 (d -1) 2 (cos(θ 1 -θ 2 ) -1) b = 2 sin(θ 1 + θ 2 ) -d 2 + (α + d(αd -2)) cos(θ 1 -θ 2 ) + 2αd -1 (d -1) 2 (-2 sin(θ 1 + θ 2 ) + sin(2θ 1 ) + sin(2θ 2 ))Now we apply the optimized DistMult decoder on the test nodes with degree d ′ . For the test node u ′ with feature vector x 1 , the aggregated representationr ′ 1 is r ′ 1 = 1 d ′ +1 x 1 + d ′ d ′ +1 x 2 .Similarly, r ′ 2 can be obtained.Assume the test nodes u ′ has feature vector x 1 and node v ′ has feature vector x 2 . Based on assumptions, (u ′ , v ′ ) should be connected in the heterophilic graph. Plugging in the optimized DistMult parameters, the predicted link probability ŷu ′ v ′ for positive (edge) node pairs can be written asEQUATIONOn the other hand, for nodes with the same feature vectors (e.g., self-loops), they should not be connected in the graph. The predicted link probability ŷu ′ u ′ for self-loops can be written asEQUATIONThus, the separation distance between edges and non-edges for the test nodes on DistMult decoder optimized with GNN representations can be represented as∆ GNN = |ŷ u ′ v ′ -ŷu ′ u ′ |.Now let us consider the baseline DistMult decoder optimized with node features x u . It is straight forward to see that if the decoder is optimized such that ŷuv = 1, ŷuu = α < 0 and ŷvv = α < 0, we will continue to have ŷu ′ v ′ = 1 and ŷu ′ u ′ = α for the test nodes, as the decoder is graph-agnostic. Thus, the separation distance between edges and non-edges for the test nodes on the baseline DistMult decoder can be represented as ∆ baseline = 1 -α.The GNN-based DistMult decoder reduces the separation distance between edges and non-edges for the test nodes compared to the baseline DistMult decoder when ∆ GNN < ∆ baseline . Solving this inequality for integers d and d ′ under the constraints of d ≥ 0, d ′ ≥ 0, α < 0, we obtain the solutions asd ′ > 0 if d = 0, or 1 ≤ d ′ < d if d ≥ 2. ■In addition to the dataset we employ in experiments, we identified a diverse range of heterophilious datasets from other graph learning tasks (e.g. graph or node classification). Specifically, we have identified a range of biological graph datasets from the TUDataset [31] 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• tolueneThese 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 [45] . Note that such findings are not only limited to biological datasets. For instance, 73% of graphs from PATTERN [13] (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 Table 4 .In addition to the homophily ratios presented above, we provide the feature similarity distributions for edges and random node pairs across several datasets in Figure 11 , following the same convention as Figure 5 in our paper. These plots reveal clear signs of heterophily in the existing benchmark graphs. [39] 0.12 AQSOL [13] / Yelp 0.12 PPI [63] 0.11 Facebook [48] 0.11 Amazon-Photo [40] 0.10 Amazon-Computers [40] 0.07 Twitch-DE [39] 0.07 Twitch-FR [39] 0.06 BlogCatalog [48] 0.06 CiteSeer [48] 0.05 TWeibo [48] 0.01 Karateclub [50] -0.03 UPFD [11] -0.10 BBBP instances [45] -1.00 NC11 instances [31] -1.00 AIDS instances [31] -1.00 QM9 instances [45] -1.00 Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.| N (u)|+1 x u + 1 | N (u)|+1l∈ N (u) x l that considers self-loops in its message passing process. We further assume a degree shift between training and test sets, where all training nodes have degree d while the test nodes have degree d ′ . Then for any d ′ > 0 when d = 0, or 1 ≤ d ′ < d when d ≥2,the DistMult decoder optimized on GNN representations r u reduce the separation distance between edges and non-edges for the test nodes compared to the baseline optimized with node features x u .Our experiment code is available at https://github.com/GemsLab/HeteLinkPred. 


Decision: This paper presents a pioneering approach that explicitly characterizes feature heterophily in link prediction using Graph Neural Networks (GNNs). It highlights the fundamental differences in optimization strategies for homophilic and heterophilic link prediction tasks and provides insights into effective decoder selection for non-homophilic scenarios. However, reviewers have raised concerns about the motivation, novelty, experimental design, and theoretical contributions of the work. Although these concerns have not been fully addressed by the authors, two reviewers have strongly recommended accepting the paper. Therefore, acceptation is suggested.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * 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: 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.
limitations: limitations: * Add more heterophilic real-world datasets to demonstrate the generality of conclusions.
paper_summary: paper_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.
strength_weakness: strength_weakness: The theoretical analysis is a bit over-simplified.
questions: 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?
limitations: limitations: the authors adequately addressed the limitations
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: Yes, the author has a clear understanding and explanation of the limitations of the proposed method.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: As pointed out in Questions 3, the theoretical results for more general cases need to be addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: See the weakness.

Comments: title: Additional Rebuttal: Results on additional heterophilic dataset
Response to Reviewer ufZT (3): results on additional heterophilic dataset
Response to Reviewer ufZT (2)
Response to Reviewer ufZT (1)
Reminder to Check Authors' Reply
comment: 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.
Thanks for the reply and I will keep my rating.
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.
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.
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:

| 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!
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.
Thank the authors for the response to my concerns.
Dear Reviewers,

Would you mind checking the authors' responses?

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