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 2024 poster (2024)
Keywords: graph neural networks
heterophily
link prediction
Primary area: graph_neural_networks
TL;DR: We formalize and analyze heterophilic link prediction with GNNs, when connected nodes have dissimilar features. We identify real-world heterophilic benchmarks and show that learnable decoders and separated node embeddings are crucial for such graphs.

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.

On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks
Jiong Zhu
Gaotang Li* University of Illinois Trrbana-Champlr gaotang3@il1 1iinoiis edu
Yao-An Yang University of Michigan ayayangOumich.. edu
University of Michigan j jionzzhu@umic ch. edu
Jing Zhu
Xuehao Cui University of Michigan credus@umi ch. edu
Danai Koutra University Michigan dkoutra@umi ch. edu
University Michigan jingzhun@umico ch. edu
Abstract
Heterophily, the tendency of connected nodes in networks 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 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 synthetic and real- world datasets confirms our theoretical insights and highlights the importance of adopting learnable decoders and GNN encoders with ego- and separation in message passing for link prediction tasks beyond homophily.
Introduction
Graph-structured data are powerful and widely used in the real world, representing relationships beyond those Euclidean data through links. Link prediction, which aims predict missing edges in 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 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 lear node representations in end-to-end fashion. Vanilla GNN for link prediction (GNN4LP) methods keep the original GNN model for encoding node embeddings, followed by 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
"Equal contribution.
tork done prior to the author's affiliation with Amazon.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

capabilities, the current state-of-the-an GNN4LP approaches augment GNNs by incorporating pairwise structural information [6, 52, 51, 49, 43].
Nevertheless, as the core of today's 's SOTA approaches, GNNs rely on the message-passing mechanism which works well when the underlying data exhibit homophily, L.e. connected nodes tend 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-homon 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- 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-embeddingg separation in GNN message passing improves their adaptability to feature similarity variations.
We introduce six real-world datasets spanning from homophilic to heterophilic settings for link prediction, with edge counts ranging from 88K 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 non-homophilic conditions in link prediction tasks.
Benchmarks for Non-homophilic Link Prediction:
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.
2 Related Work
Graph Neural Networks for Link Prediction. Traditional algorithms for link prediction are primar- ily 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 representationn-busel 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 repre- sentations and inner product as the decoder for pairwise link existence predictions. More recently, the state-of saute-ofttee the- methods for link prediction are built on top of the representationn-asse algorithms and augment them with additional pairwise information. For instance, subgraph-baan -haspe approaches perform link prediction between two nodes by first extracting their enclosing subgraphs and subse- quently applying the standard representation-bun Concurrently, other works have been proposed to augment GNN learning with common neighbor
algorithms on the extracted subgraphs [52, 6, 62).
2

---

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 link together. In contrast, this work considers more general setting where there may be spectrum of low-to-high homophily in the underlying data, characterizes a notion heterophily in link prediction and ex- plores 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.
Graph Neural Networks Addressing Heterophily. 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-inspiree 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
GRAFF [10], originally designed for handling
performance against different homophily levels.
Notation and Preliminaries
Let = EV,E) be an undirected and unweighted homogeneous graph with node V and edge set We denote the 1 1-hop (immediate) neighborhood centered around as N(e) (g may have self-loops), and the corresponding neighborhood that does not include the ego (node v)) as N()). We represent the graph by its adjacency matrix A {0, 1 and its node feature set as X' with matrix form X E =R= where the vector x, corresponds to the ego-feature of node v, and {x,, : u E (v)) to its neighbor-features. We further represent the degree of node e by d,, which denotes the number of neighbors its immediate neighborhood N (v))
Graph Neural Networks for Link Prediction. Following [23, 53]. we define the task of link prediction be estimating the likelihood of reconstructing the actual adjacency matrix. Formally,
Dh. A.j- p((, p(g,
(1)
where Di.j or As, is the predicted link probability between nodes (i and was traditionally caleulated by heuristics-based algorithms. For (i,j) in the training set, we set the ground truth probability Vi,j = Aij- 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:
Ú..j = A = DEC(2,, 2j), where 2, = ENC(1, 9,X), 23 EEN(J. G.X).
(2)
The 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 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 (Node Feature Similarity) For a node pair (u, v) with x., and x, as the node features and a similarity function Φ: ((y)) + R. we define the node feature similarity as k(u, v) = ((x,, xx).
In this work, we set o(x xx) Xx to be the mean-centered cosine similarity of node features,
[|x.T]|
where we denote the mean feature vector of all nodes in the graph as x ক Erey Xv, and the mean-centered node feature for node as X, = x, x. Empirically, we find that the mean-centering operation crucial for accurate characterization of the pairwise feature similarity and its impact on link prediction performance. We further define the graph feature similarity follows.
3

---

M
M
My
M2
-1.0
0.5
1.0
(a) Homophilic, larger M (b) Homophilic, lower M (c) Hcterophilic
(d) Gated
Figure 1: Categorizing link prediction tasks based 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) .. 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 single threshold.
Definition (Graph Feature Similarity) We measure the graph feature similarity K through aver- aging the feature similarity of all its connected nodes pairs: K E(u,)ee
k(w.v)
[E]
Unlike the homophily measures defined on node class labels which are non-nega non-negative [25], the feature similarity k(u, v) E [-1, can additionally be negative, indicating negative correlations. We refer to the graph as positively correlated K >> O and negatively correlated K < 0.
Homophilic & Heterophilic Link Prediction
While existing works node classification usually define homophilic heterophilic graphs by whether the majority of connected nodes share the same class labels [25, 35], the class information is 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 separated, as these definitions capture the fundamental differences on how link prediction scores are correlated with feature similarity scores. Within the category of homophilic heterophilic tasks, 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.
4.1 Categorizing Link Prediction Distributions of Feature Similarity
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 of feature similarity scores for positive (edge) node pairs in the graph as Kposs 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 Koos and Kneg are (approximately) separated:
Definition (Homophilic Link Prediction) The task homophilic if M exists such that for most samples Kooz C Koos and Kneg C. Kneg satisfies sup(Knee) M S inf (Kpos)
Prior works have mostly focused 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 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 A exists such that for samples Kops C Kepos and Kneg C Knegg satisfies sup(K) S M < inf((eee))
We give intuitive examples of homophilic and heterophilic link prediction tasks in Fig. 1: the key difference berween homophilic and heterophilic tasks whether Kyos is predominantly distributed above threshold M while Kneg is below M (homophilic), or vice versa (heterophilic), Fig. la vs. Ic. The categorizations homophilichheterpphiii link prediction tasks should not be confused with the magnitude of A4 that indicates the variance of positive similarity scores: while its
shown in

---

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 Kops and Kneg cannot be separated by single threshold M. Most of these cases are too complex to be formalized and studied theoretically, but we formalize one of them (Fig. Id) below and later report empirical results ($ 6).
Definition (Gated Link Prediction) The task gated if it neither homophilic nor heterophilic, but M1, M2 E IR exist such that M2 2 sup(Kpos) 2 inf (Kpos) 2 M
4.2 Differences between Homophilic & Heterophilic Link Prediction
In $4.1, we have situated our discussions of link prediction tasks based on how the positive and negative samples separated in the feature similarity score space. In this section, reveal stylized learning setup the fundamental differences in optimizations for homophilic and heterophilic link prediction tasks.
Theoretical Assumptions. Assume training graph with node E V whose feature vectors are 2-dimensional unit vectors and can be represented as x, (cos 0g sin 0.). We consider DistMult decoder for predicting the link score for candidate node pair u, E V with feature vec- tors Xu. Specifically, the link score is calculated as Va.u = =(x, 6 x2) JTw w + b. where w and b are learnable parameters for the decoder, with training loss function (e)L(() such that ğ 2 0 for all edges (positive samples) and ÿ < 0 otherwise. Fur- thermore, we assume that the Kopo and Kneg are ideally separable by a threshold M E [0, 1] in the feature similar- ity score space such that the homophilic or heterophilic conditions hold for all samples.
Hiterophiiic
Homophiltc
Pav
40/13
-2
C=y C=y-Reell -ReLU--9) + (1-
Figure 2: Link prediction scores Yu'v' for decoders optimized under homophilic (yellow) and heterophilic (blue) setups in Thm. (for M = 0.5).
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 Following the above ussumptions, consider two DistMult decoders that are fully opti- mized for homophilic and heterophilic link prediction problems respectively. Given an arbitrary node pair (u', v') with node features X,' (cos ou' .in sin ) and X (cos Out sin og)) and pairwise feature similarity k(u', "'),, the following holds for the predicted link probability Dwe
For the homophilic problem where sup(Kneg)) < iinf(Kppe)) = - < 1, when bounding Nu.r 1 if k(u,, u) = during training, Dw'v' increases with ke(,, v²) at a linear rate of TI-
For the heterophilic problem where -1 S sup(Kgos)= = M < (ine()n)))) when bounding Du.e if (fk(u,, v) = -1 during training, Yurer decreases with ku(u,, v²) at a linear rate of (1-M)-
We give the proof in App. $B.1 and visualize in Fig. 2 how the predicted link score jw' 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.
5 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
5

---

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.
5.1 Decoder Choice for Heterophilic & Gated Link Prediction
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 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 several OGB datasets [18] and proposed 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 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 purameter exists for single linear decoder that perfectly sepurates 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.
5.2 Improving GNN Representation Power with Heterophily-adjussee Designs
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 neighbor- embeddings 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 neighhor-features together less capable of generalizing under heterophilic settings than graph-agnostic model. We give the proof in Appendix $B.3.
Theorem Consider the same DistMult decoder and loss function L as the assumptions in $4.2. but trained on heterophilic graph where (1) feature vectors for all nodes can be either (cos 01, sin 01) or X2 = (cos 92 sin Oz), and (2) nodes u and are connected if and only xu. # Xg- Assume two DistMult decoders GNN representations Iu instead of node features Xw, where ru is obtained with a linear GNN model [T EieN(u) Xi 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 huve degree d'. Then for any d' > 0 when d = O, or 1 < d' < d when d 2 2, the DistMult decoder optimized on GNN representations Va reduce the separation distance between edges and non con-s for the test nodes compared to the baseline optimized with node features X..
trained, one baseline with node features Xa, and the other with
Fu [x + 1

---

1.
0.8
0.6
3.6
0.6
0.2
0.2
02
0.64
-6.2
0.4
0.64
0.2
Graph Feature Similarity
Graph Feature Simllarity
Graph Feature Similarity
(a) Comparison of decoder choices with SAGE encoder.
(b) Comparison of decoder choices with GCN encoder.
(c) Comparison of different encoder choices with MLP decoder.
Figure 3: Comparing link prediction methods on synthetic graphs with varying levels of feature similarity: (a) and (b) focus on decoders, while (c) focuses on encoders. We include MLP decoder without GNN as a graph agnostic baseline in all plots. Numerical results are reported in Table 2.
Empirical Analysis
We aim 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- 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 our experiments, and then present the results on synthetic and real-world datasets. More details about setups and results are available in App. A.
Link Prediction Methods. As in the previous sections, follow encoder-decoder framework and consider different combinations of both components. For decoders, we consider the options mentioned in $:.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-embeddingg affects link prediction performance: (1) GraphSAGE [15] which separates ego- and neighbor- embeddings 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], state-of-the-art method reported in 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 wrighbor-embedding
during message passing, and (5) NoFeat, structure-only bascline 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]. Resouree Allocation (RA) [57], Adamic-Adar (AA) [2], and Personalized PageRank (PPR) [19].
6.1 Experiments on Synthetic Graphs
We generate synthetic graphs that resemble diffferent types of link prediction tasks (i.c., homophilic, heterophilic, and gated) by varying the feature similarity between connected nodes. These graphs provide controlled environments that allow 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.
focus on the effects of feature similarity on link
Performance Trend Across the Full Similarity Specturm. We visualize the performance trends per method in Fig. and present the numerical results in Table 2. We observe that the performance of all feature-consuming methods is significantly affected by the level feature similarity: most methods reach their best performance at the positive extreme (homophilic tasks) and the second best the
3 Our experiment code is available at https: http:/gggtttttteeeeeeeeee httpi/aaw.cccm/mmmmma//teeeeeaae
7

---

negative extreme (heterophilic tasks); between the two extremes (gated tasks), the performance of all methods drops significantly as the feature similarity score upproaches 0, which creates U-shaped performance trend across the feature similarity spectrum. It is worth noting that graph-agnostic MIP 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 O, 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 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-hased methods for the homophilic link prediction task.
Decoder Choices: MLP and MistMult over DOT. We further validate our main points in $5 regarding how different decoder choices adapt to homophiiii 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 margin of 50% in the negative extreme and 10% in the positive extreme under SAGE encoder. DistMullt 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 MI.P 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- non-edges are required. With GCN encoder, the performance of DistMult decoder 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.
Importance of Ego- and Neighbor-Embe Embedding Separation. In Fig. 3c, we compare the performance of different encoder choices with fixed MLP decoder, which is the best- performing 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 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.
Encoder Choices:
the importance of adopting ego- and
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 (c.g., number of shared neighbors) through subgraph sketching. We find that BUDDY-SIGN
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- non-homophilii settings where structural proximity alone may be less informative.
8

---

Table Results on real-world graphs. "*" denotes results quoted from [6].
Dataset
ogbl-collab
ogbl-citat2
e-comm
facebook
PPI
amzn-comp
#Nodes
235,868
2,927.963
346,439
4,039
56,944
13,752
#Edges
2.358.104
30,387,995
682,340
88,234
1,612,348
491,722
Feat. Sim
0.70
0.40 MRR
0.18
0.11
0.11
0.07
Metrics
Hits 50
MRR
MRR
MRR
MRR
HEURISTICS
56.44
51.47*
19.96
53.83
62.77
55.05
AA
64.35*
51.89*
19.96
54,90
64.66
57.94
RA
64.00*
51.98*
19.96
55.50
64.26
58.03
DOT DECODER
GCN SAGE
10.64
10.38+1.52
33.83+1.34 52.30+5.11
39.95+b.14
13.35+0.43
24.67=0.60
19.71
71.39+0.28
49.59
18.94
42.25=0.54
DISTMULT DECODER
GCN SAGE
25.62#0..2
62.31
53.09+2.37
15.63
14.31
31.59=1.04
13.50
82.2610.02
15.15
50.64:0.19
22.2610.35
58.42
MLP DECODER
NoGNN
6.07
27.64+0.22
24.65+0..21
16.57
1.96
21.15
GCN
30.17.42.90
73.57+0.35
54.82+3.42
49 40.29
17.67
52.90
SAGE
48.6420.39
83.6720007
54.6020.09
50.1220.05
35.30
58.3820.07
BUDDY WITH MLP DECODER
NoFeat
66.0622.22 22
83.36:20114
6.6810.00
42. 12.0627.87
66.4220.03
53.5320.02
GCN SIGN
26.21
87.0540.04
13.131199
52.9910.13
65.1220.49
60.99
66.6440.64
87.5310.12
10.95
51.8110.13
53.22:0.21
60.05=0.12
6.2 Experiments on Real-world Graphs
Next compare performance of different link prediction methods real-world graphs of varying sizes and feature similaritics. Unlike our synthetic graphs where the feature similarity of connected nodes is controlled, real-world graphs tend have 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 graph, which is typically overlooked 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 [6] facebook [39], PPI [63], and amazon-computer [40]. The details and experiment setup are in App. SA. We report dataset statistics in Table and show feature similarity distributions of edges random node pairs in Fig. 6 (App. A): while ogbl-collab and ogbl-citation2 are approximately homophilic, e-comm, facebook, PPI and umazon-computen are non homphoopp We have also identified additional
datasets exhibiting feature heterophily in App. SC.
Motivated by prior findings about the interplay node degree and heterophily [46, 29, 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. SAA. To understand how encoders and decoders adapt to these property variations, 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-10.
fix component (encoder or
Significance 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 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% DOT overfits to the lowest feature similarity bucket; also

---

(a)-(b) ogbl-citat2
(c)-(d) e-comm
(e)-(f) facebook
(g)-(h) PPI
tax1 (.23 (822.550 (25...
0.16
0.75
7.43
3.53
6.51
1.26
2.21
8.00 -1.97
Feature Similertty
23
Feature Similarity
Festure Simitrity
Feature Simtlrity
2.19
5.38
-1.08
(6.70 a
-1.84
29.23
Degrees
(A450))
Node Degrees
Node Degroes
UAMI 186.0)
[B.a] (2L 19.30)
Degrees
(a) MTTMLP M
(c) SITMLP mIIDOT
(e)
BITDOT
MTTMLP mrTDOT
with SAGE encoder.
with SAGE encoder.
with SAGE encoder.
with SAGE encoder.
1o (0-01,0200 (030330) (33243 (33331 (1.1.
1 (4000 (6.0)..11 29- 16.000
(603 68N 15.0 3 160)
0.06
1.22
1.43
7:24
8.31
5.72
25.89
15.56
Feature Smillrity
Feature Simiarity
255
039
3.47
10.14
28.15
17.06
Feature
.0.72
0.09
-0.41
3.12
0.66
-5.87
11.27
27.37
14.70
[04]
15.341
Degress
13-551 58
12.31
Node Degrees
0358)
Node Degrees
(M22]
Node
122/5)
(b) METSIGN MEEGEN with BUDDY & MI.P
(d) MITSAGE MTIGCN with MLP decoder.
(f) MErSAGE MITGON
(h) METSAGE with MLP decoder.
with MLP decoder.
Figure 5: Pairwise comparison of encoder or decoder choices on test edges grouped by node degrees (X-axis) and feature similarity (y-axis): Green denotes MRR increases and purple denotes decreases. More plots in Fig. 7-10.
observe similar overfitting of DistMult to the highest feature similarity bucket in Fig. 5a, despite it being significantly more robust than DOT. Overall, MIP is the most robust choice for link prediction tasks 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 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 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 neighhor-embeddingg 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.
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 op- timizations needed for different tasks. Our analysis revealed how link prediction encoders and decoders adapt to varying feature homophily levels, identifying key designs lesannl-learnable decoders (e.g., MLP or DistMult) with GNN encoders that separate ego- and weighbor-embeddding-- improved link prediction performance beyond homophily. Experiments 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 need for introducing more feature- heterophilic 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.
10

---

Acknowledgments and Disclosure of Funding
We thank Yuhang Zhou for sharing the experiment code for SpotTarget [61], which served as the foundation for our experiment implementation. We also thank the reviewers for their constructive feedback. This material is based upon work supported by the National Science Foundation under IIS 2212143 and CAREER Grant No. IIS 1845491. We gratefully acknowledge the support of NVIDIA Corporation with the donation of the Quadro P6000 GPÜ used for this research. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or other funding parties.
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyun- yan, Greg Ver Steeg, and Aram Galstyan. 2019. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. international conference on machine learning. PMLR, 21-29.
[2] Lada Adamic and Eytan Adar. 2003. Friends and neighbors the web. Social networks 25, 3 (2003), 211-230.
[3] Albert-Lááse László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. science 286, 5439 (1999), 509-512.
[4] Aleksandar Bojchevski and Stephan Günnemann. 2017. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv preprint 17Xiv:1707.038// (2017).
[5] Sergey Brin and Lawrence Page. 1998. The anatomy of large-scale hypertextual web search engine. Computer networks and ISDN systems 30, 1-7 (1998), 107-117.
[6] Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Yannick Hammerla, Michael M Bronstein, and Max Hansmire. 2022. Graph neural networks for link prediction with subgraph sketching. In The eleventh international conference on learning representations.
[7] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2021. Adaptive Universal Generalized PageRank Graph Neural Network. In International Conference Learning Representations. httpps://openrevien /tt/fformmiidnn]17feee
[8] Nur Nasuha Daud, Siti Hafizah Ab Hamid, Muntadher Saadoon, Firdaus Sahran, and Nor Badrul Anuar. 2020. Applications of link prediction in social networks: A review, Journal of Network and Computer Applications 166 (2020), 102716.
[9] Andrea Giuseppe Di Francesco, Francesco Caso, Maria Sofia Bucarelli, and Fabrizio Silvestri. 2024. Link Prediction under Heterophily: Physics-Inspired Graph Neural Network Approach. arXiv preprint arXiv:2402. 14802 (2024).
[10] Francesco Di Giovanni, James Rowbottom, Benjamin P Chamberlain, Thomas Markovich, and Michael M Bronstein. 2022. Understanding convolution on graphs via energies. arXiv preprint arXiv:2206.100 10991 (2022).
[11] Yingtong Dou, Kai Shu, Congying Xia, Philip S Yu, and Lichao Sun. 2021. User preference-awar aware fake news detection. In Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval. 2051 1051-2055.
[12] Mathijs Douze, Alexandr Guzhva, Chengqi Deng. Jeff Johnson, Gergely Szilvasy, BemreeEmmauuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The Faiss library. (2024).
[13] Vijay Prakash Dwivedi, Chaitanya Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2023. Benchmarking graph neural networks. Journal of Machine Learning Research 24, 43 (2023), 1-48.
[14] Jonathan Halcrow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi. 2020. Grale: Designing networks for graph learning. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2523-2533 25322.
[15] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs In Advances in neural information processing systems (NeurIPS). 1024-1034,
11

---

[16] William L Hamilton, Rex Ying, and Jure Leskovec. 2017. Representation learning on graphs: Methods and applications, arXiv preprint ccXiv:179.005884 (2017).
[17] Mingguo He. Zhewei Wei, Hongteng Xu, et al. 2021. Bernnet:
Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems 34 (2021), 14239- 4229-11451..
[18] Weihua Hu, Matthias Fey, Marinka Zitikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee, 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv preprint arXiv:2005.0063 (2020).
[19] Glen Jeh and Jennifer Widom. 2003, Scaling personalized web search. In Proceedings of the 12th international conference World Wide Web. ACM, 271-279.
[20] Thomas N Kipf and Max Welling. 2016. Variational graph auto-encoders. arXiv preprint arXiv: (2016).
[21] Thomas N. Kipf and Max Welling. 2017. Networks. In International Conference on Learning Representations (ICLR).
Semi-Supervised Classification with Graph Convolutional
[22] Meng-Chich Lee, Haiyang Yu, Jian Zhang, Vassilis N. Ioannidis, Xiang song, Soji Adeshina, Da Zheng, and Christos Faloutsos. 2024. NetInfoF Framework: Measuring and Exploiting Network Usable Information. In The Twelfth International Conference on Learning Representations. https://openrevai wwwpopeeeviieeee net/ forum?id Boruuidd-KYeNNll.jV
[23] Juanhui Li, Harry Shomer, Haitao Mao, Shenglai Zeng, Yao Ma, Neil Shah, Jiliang Tang, and Dawei Yin. 2023. Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. arXiv [cs.LG] (June 2023).
[24] Shuming Liang, Yu Ding, Zhidong Li, Bin Liang, Yang Wang, Fang Chen, et al. 2022. Can GNNs Learn Heuristic Information for Link Prediction? (2022).
[25] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. 2021. Large Scale Learning on Non-Hompphilou Graphs: New Benchmarks and Strong Simple Methods. In NeurlPS.
[26] Donald Loveland, Jiong Zhu, Mark Heimann, Benjamin Fish, Michael T. Schaub, and Danai Koutra. 2023. On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks. In Learning Graphs Conference (P (Proceedings of Machine Learning Research), Vol. 231. PMLR, 6.
[27] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. 2022. Revisiting heterophily for graph neural networks. Advances in neural information processing systems 35 (2022).
[28] Sitao Luan, Chenqing Hua, Minkai Xu, Qineheng Lu, Jiaqi Zhu, Xiao- Chang, Jie Fu, Jure Leskovec, and Doina Precup. 2023. When Do Graph Neural Networks Help with Node Classification? Investigating Thirty-seventh Conference on Neural Information the Homophily Principle on Node Distinguishability, http:/forummdddddmy33333 id=kJmYu33222 Processing Systems. https: // /pwp//vpeeeeeeeeeeee/ee/e hwtp:/iwweeeeeeeeeeeeeeeeeee ner/forum?
[29] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. 2022. Is Homophily a Necessity for Graph Neural Networks?, International Conference on Learning Representations. httpe://openreviee..e forum?idrucASPPDeer
[30] Haitao Mao, Juanhui Li. Harry Shomer. Bingheng Li, Wengi Fan, Yao Ma. Tong Zhao, Neil Shah and Jiliang Tang. 2023. Revisiting link prediction: A data perspective. arXiv preprint arXiv:2310.00993 (2023).
[31] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neu- mann. 2020. Tudataset: A collection of henchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663 (2020).
[32] Mark EJ Newman, 2001. Clustering and preferential attachment in growing networks. Physical Review E 64, 2 (2001), 025102.
[33] Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chenggi Zhang, 2018 Adversarially regularized graph autoencoder for graph embedding. In International Joint Conference on Artificial Intelligence. 2609-2615.
[34] Hongbin Pei, Bingzhe Wei, Kevin Chen Chuan Chang, Yu Lei, and Bo Yang. 2020. Geom-gen; Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287 (2020).
12

---

[35] Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova, 2024. Characterizing graph datasets for node classification: Homophily--eeleopphi dichotomy and beyond. Advances in Neural Information Procexsing Systems 36 (2024).
[36] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. 2022. critical look at the evaluation GNNs under heterophily: Are we really making progress?. In The Eleventh International Conference on Learning Representations.
[37] Chandan K Reddy, Lluís Mårquez, Fran Valero, Nikhil Rao, Hugo Zaragoza, Sambaran Bandyopadhyay, Amab Biswas, Anlu Xing, and Karthik Subbian. 2022. Shopping queries dataset: A large-scale ESCI benchmark for improving product search. arXiv preprint arXiv:2206.06558 (2022).
[38] Andrea Rossi, Denilson Barbosa, Donatella Firmani, Antonio Matinata, and Paolo Merialdo. 2021. Knowl- edge graph embedding for link prediction: A comparative analysis. ACM Transactions on Knowledge Discovery from Data (TKDD) 15, 2 (2021), 1-49.
[39] Benedek Rozemherczki, Carl Allen, and Rik Sarkar, 2021. Multi-scale attributed node embedding. Journal of Complex Networks 9, 2 (2021), cnab014. cnab0444
[40] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of Graph Neural Network Evaluation. Relational Representation Learning Workshop, NewrlPS 2018 (2018).
[41] Mohammadsadegh Vahidi Farashah, Akbar Etebarian, Reza Azmi, and Reza Ebrahimzadeh Dastjerdi. 2021. hybrid recommender system based-on link prediction for movie baskets analysis. Journal Big Data 8 (2021), 1-24.
[42] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. International Conference on Learning Representations (ICLR) (2018). https: sttps://oppnrevi.e.
[43] Xiyuan Wang, Haotong Yang. and Muhan Zhang. 2023. Neural common neighbor with completion for link prediction. arXiv preprint arXiv:2302. (2023).
[44] Yiwei Wang, Bryan Hooi, Yozen Liu, Tong Zhao, Zhichun Guo, and Neil Shah. 2022. Flashlight: Scalable link prediction with effective decoders. In Learning on Graphs Conference. PMLR, 14-1.
[45] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleh Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. 201 8. MoleculeNet: a benchmark for molecular machine learning. Chemical science 9, 2 (2018), 513-530.
[46] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. 2022. Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks. In JEEE International Conference on Data Mining. IEFE, 1287-1292.
[47] Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2014. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv:1412.6575 (2014).
[48] Renchi Yang, Jieming Shi, Xiankui Xiao, Yin Yang, Sourav S Bhowmick, and Juncheng Liu. 2023. PANE: scalable and effective attributed network embedding. The VLDB Journal 32, 6 (2023). 1237-1262.
[49] Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang. and Hyunwao J Kim. 2022. Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for link prediction. arXiv [cs.LG] (June 2022).
[50] Wayne W Zachary. 1977. An information flow model for conflict and fission in small groups Journal of anthropological research 33, 4 (1977), 452-473.
[51] Muhan Zhang. 2022. Graph neural networks: link prediction. Graph Neural Networks: Foundations, Frontiers, and Applications (2022), 195-223.
[52] Muhan Zhang and Yixin Chen. 2018, Link prediction based on graph neural networks. Advances in neural information processing systems 31 (2018).
[53] Muhan Zhang, Pan Li. Yinglong Xia, Kai Wang, and Long Jin. 2020. Revisiting graph neural networks for link prediction. (2020).
[54] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. 2021. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems 34 (2021). 9061-9073.
13

---

[55] Xin Zheng, Yi Wang. Yixin Liu, Ming Li, Miao Zhang, Di Jin, Philip S Yu, and Shirui Pan. 2022. Graph neural networks for graphs with heterophily: survey. arXiv preprini crXiv:2202.07062 (2022).
[56] Shijie Zhou, Zhimeng Guo, Charu Aggarwal, Xiang Zhang, and Suhang Wang. 2022. Link prediction on heterophilic graphs via disentangled representation learning. arXiv preprint arXiv:2208. 01820 (2022).
[57] Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. 2009, Predicting missing links via local information. The European Physical Journal B 71, 4 (2009), 623-630.
[58] Jiong 7hu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. 2020. Graph Neural Networks with Heterophily. arXiv preprini 2tt:::200091336660 (2020).
[59] Jiong Zhu, Yujun Yan, Mark Heimann, Lingxiao Zhao, Leman Akoglu, and Danai Koutra. 2023. Het- erophily and Graph Neural Networks: Past, Present and Future. IEEE Data Eng. Bull. 46, (2023), 34.
[60] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances neural information processing systems 33 (2020), 7793-7804.
[61] Jing Zhu, Yuhang Zhou, Vassilis loannidis, Shengyi Qian, Wei Xiang Song, and Danai Koutra. 2024. Pitfalls in Link Prediction with Graph Neural Networks: Understanding the Impact of Target-link Inclusion & Better Practices. In Proceedings of the 17th ACM International Conference Web Search and Data Mining. 994-1002.
[62] Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. 2021. Neural bellman- ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems (2021), 79476-29490. 29490.
[63] Marinka Zitnik and Jure Leskovee. 2017. networks. Bioinformatics 33, 14 (2017), Predicting multicellular function through multi-layer tissuc
14

---

A Additional Details on Experiments
Computing Resources. For most experiments, we use workstation with a 12-core AMD Ryzen 3900X CPU, 64GB RAM, and an NVIDIA Quadro P6000 GPU with 24 GB GPU Memory. BUDDY experiments on ogbl-citt giil-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 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 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 the most negatively correlated graph featuring edges with feature similarity scores ranging in [-1, -0.33).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. 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, [i] 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/heterophh 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- mee-griined control over feature similarity distributions and can produce graphs spanning the full spectrum from negative to positive feature correlations.
levels based on node class labels,
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: (I) ogbi-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], 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 BERRT-embediings of queries and product information as node features. For ogbl-collab and ogtl-citation,, 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.
15

---

2.00
1.75
Deredy
1,00
0.3
0/1
6m
Featore Smiarty
(a) ogbl-collab
(b) ogbl-citation2
(c) e-comm
2.00
1.20
1,00
0.00
Jobo
Lie
6.0
-5.5
Festum Seilaity
Fearre Siilartyy
(d) facebook
(e) PPI
(I) amzn-comp
Figure 6: Comparison of feature similarity distributions for edges and random node pairs on real- world datasets used in our experiments. For similarity scores of random node pairs, we randomly sample 1000 nodes and compute the pairwise cosine similarity between these node features. Similarity score distributions for random node pairs are good approximations of the distributions for non-edge node pairs due to the sparsity of the graphs.
E-0.94, 20.30.0.72 72) 10.72.0.90 90)
20000
[-0.110.22] 32.0-33 [0-1. 1000
10200
[-004,00 30) [0. 30, 0.72) (0.72 08]
20000
10000
20245
2500
26000
Feature Similarity
16000
Feature Sim 2r
9000
Featur Similarity
16000
14000
34000
19626
3119
10164
9225
19626
3119
32000
10000
64000
8000
42000
8000
18573
4172
9992
10168
8706
18573
4172
4000
4000
8800
11,13
(14,568)
[1,1]
(1,18)
Node Degrees
Degrees
Node Degrees
(a) Number of test edges each (b) Number of test edges in each bucket ogbl-citation2.
(c) Number of test edges in each bucket on e-comm.
bucket on ogbl-collab.
(0.00,0.110) 0.181 (0.18.11 1.00)
F-0.85 -0,55 (-0.05,0.19) 5.119 (0.19,1.000 1.00]
2086
1842
1954
21.00
21514
17392
16648
21000
5406
5100
5884
Feature Similarity
Feature Similarity
20.00
0003) [0.03,0.13
20000
sim bin
1854
1868
2160
3900
18468
18906
19646
5026
5336
6028
5200
5000
[-0.57,0.00 00)
3800
-10000
4800
19384
17664
19244
6004
4404
4600
3700
-7000
(0.31]
(23,45)
(45,566)
11.028.00 128.6544005444000 088.54.0154..1555.g degree bin
Node Degrees
Node Degrees
(d) Number of test edges in each bucket PPI.
(e) Number of test edges in each
(f) Number of test edges in each bucket amazon-comen comzunecomputer.
bucket facebook.
Figure 7: Number of edges in each bucket on different datasets.
16

---

Table 2: Results on synthetic graphs. We report MRR averaged over 3 runs.
Graph Index Feat, Sim
3
0.38820.04
-0.31
-0.2820.01
0..14...00
-0.0420.00
0.69
0.65
0.66
1.58
2.44
RA
0.69
0.65
0.66
1.64
2.58
AA 0.69
0.65
0.66
1.63
2.57
PPR
10.91
3.30
2.46
3.17
3.68
GCN+DOT
15.8840.37
8.16-0.11
5.96=+.07
3.55
3.79=0.00
SAGE+DOT
25.53+0.00
9.35=0.02
6.32++..02
3.80
3.51
GCN+DistMult
46.1940.98
17.20
12.57:10.05
4.86
3.58
SAGE+DistMult
80.97
23.85
14.66.10.03
6.05
6.57
NoGNN+MIPP
57.8440.37
23.83=0.00
18.30+0.09
9.05=0.02
7.89
GCN+MLPP
45.6920.47
17.4320.08
12.62:40.08
5.03
3.9820.0
SAGE+MLP
+5.39+
43.37 +2235
33.6441.01
19.85+t0.as
23.8443.15
BUDDY-NoFeat
27.51+0.05
10.12+0.95
6.72+0.88
2.377
2.15+1.111
BUDDY-GON
69.47:0.65
24.2620.5e 56
17.6010.48
6.4620.10
4.9920.00 0.07
BUDDY-SIGN
75.2712.35
26.6520.96 96
20.81
2.
7.57
Graph Index
5
6
8
Feat Sim
0.07
0.24=0.01
0.34
0.40
0.54 000
2.81
6.26
11.97
18.62
70.49
RA
2.96
6.48
12.61
20.24
77.16
AA
2.96
6.50
12.37
19.21
71.91
PPR
3,86
7.44
13.21
19.62
62.06
GCN+DOT
4.1640.04
8,11=0.02
14.27+0.05
20.23
61.37=0.22
SAGE+DOT
2.29+0.10
6.95-0.08
14.7940.02
23.95+0.02
79.90=0.18
GCN+DistMult
4.0840.01
=.97
13.99
19.85
62.92:1.62
SAGE+DistMult
6.71
7.33=0.08
16.05+0.02
27.52+0.05
88.97-0.35
NoGNN+MLP
8.86+0.13
14.78=0.21
23.5940.32
31.88+0.55
70.55+0.88
GCN+MLP
4.19
8.12=0.05
44.03.40.02
20.07
62.24440.39
SAGE+MLP
30.35++0.12
0.
49. 1.442
64.38 8..88
89. 49.774
BUDDY-NoFeat
2.3020.08
5.10=0.97
10.5442.05
18.1320.04
67 67.96:20.01
BUDDY-GCN
3.3920.05
10.11
19.34
29.44
84.44=1.22
BUDDY-SIGN
8.45+0.u8
16.17#0.44
27.49++2.35
38.39++4.77
87.59+1.40
(0.33,333)) 10.30 13.54..55 24
(9.33,0.33 (2) 00.30 00.38 21.4..55 24
(453n 90 13.M 36.6 2140 (M)
3.13
3.84
3.20
8.04
20.53
2.75
75.83
06.34
11:13
0.29
1.49
1.70
[0.35, Similarity
Fecturre Siillarit
Feature Sinilarity
Feature Siillanty.
7.05
8.00
10:23
5.37
10.08
2.13
41.10
20.48
3.88
3.01
4.40
25
28
4.30
1.44
10.59
[1.]] (tit)
(15315)
(5.88 2831bl
iissi n8512l Degrees
[1.]
Degrees
Degrees
Degrees
(a) hitMIP hit with SAGE encoder.
(b) hitMLP hitpisM
hitsAGE hitgeN
hitsIGN hitGON with BUDDY MLP.
with GCN encoder.
with MLP decoder.
Figure 8: Performance comparison ogbl-collab among different node degree and edge similarity scores buckets.
17

---

[Q.41 (3.33) (9326.20 (931 (931...0 1.00
(04,000) (6.224.33) (021) 1.00
[a. 933 16.324:33 (051 100
255
8.68
13
Smilanns
Feature Smilarity
Feature Siillarit
Feultuee Simileiity
00.6
1.22
1.43
1.21
1.39
1.49
12.89
-12
14.79
0.25
2.53
2.79
2.30
26.32
14.00
12.87
11.20
7.83
3.77
Noda Degrees
Node Degrees
Noda Degreas
Node Dagress
(a) MITMLP MITDieM
MFEDisM mIEDOT
(c) METSAGE mFTGCN
(d) METSIGN MIIGCN
with SAGE encoder.
with SAGE encoder.
with MLP decoder.
with BUDDY & MLP
Figure 9: Performance comparison on ogbl-citation2 among different node degree and edge similarity
scores buckets.
Similarity [ost (0:3),5) (0.355.722 (5.72400)
10,4,030 1.....0.22 1h.72 1h.72..33
co 0201 (5-3;-0771 16-72800
7.43
00000 10:30 6.22 (6:533.00
Feature Similarity
Feature Simi Laritartty
Feature Similantty
-1.36
14.02
1.59
2.19
-5.23
10.33 51
-1.84
-1.62
-3 3.92
3.69
3.12
0.66
-13.26
3.26
11.31
0.10)
12.88)
Node Degrees
Node Degrees
Node Degrees
Node Degrees
a MYYMPP mITDOT
BITMPP mrrDiaM
(c) METSAGE mrEGCN
(d) METSIGN MITGON
with SAGE encoder.
with GCN encoder.
with MLP decoder.
with BUDDY & MLP.
Figure 10: Performance comparison on e-comm among different node degree and edge similarity scores buckets.
B Proofs of Theorems
B.1 Proof of Theorem 1
Proof We prove separately for homophilic and heterophilic link prediction problems.
Homophilic Link Prediction Problem. For homophilic link prediction problem, we have 2 inf M sup(Kneg)) As M inf(Kooos), pair of nodes u. E must exist in the training graph with feature vectors X., = (cos 0,, sin 8.) and X = (cos 0p, sin sin such that k(,,v) cos(f,, 0.) = M.
Now let us consider a fully optimized DistMult decoder for the problem. We parameterize the DistMult decoder with w = (wi, W2) and b; in this case, the predicted link probability
Buo = (Xo xx) T + W1 cos O2 cos 0,, + w2 sin O2 sin 0, +
As M (n any pairs of nodes (u',v') v') that has feature similarity k(u', v²) slightly smaller than M should have Yutr" S O. Therefore, we must have Due = Furthermore, since we are bounding Ve''d 1 k(u', "okuu,,0 v²) 1 during training, must have Dou = 1 and Dov = 1. Using Yus Duu and Dov we can obtain the solutions for W1. W2 and as follows:
1
W1
1 - cos (0, 0.) U2 1 - cos(0, 0,) b
0,)² cos(O, - 00,) +
As W1 = W2 = I- we have the similarity score for arbitrary node pair (u', vl) as
1
1
Dul 1 M cos(O Owr) M
+ T k(u
M-1
We can verify that the above link prediction model is fully optimized with loss function L = 0 as it always yield Dao for k(u', x²) 2 M and She 0 for k(u',u') < M. Therefore, we show that oe increases with k( v.) at linear rate of (T-M for homophilic link prediction problem.
18

---

Heterophilic Link Prediction Problem. For heterophilic link prediction problem, we have -1 S pos(K M inf((Kneg)- As M pos(K) a pair of nodes u,v E V must exist in sin sin 0n) and = (cos D. sin 02) such that
the training graph with feature vectors = (cos On, k(,,v) cos -0.) M.
Similar to the homophilic case, as M = sup(Kpoo), any pairs of nodes (u', that has feature similarity k(u', ,'') slightly larger than M should have Du'v' < 0. Therefore, we must have Huo , v') ==)== = during training, for nodes u and
Furthermore, since we are bounding Davv = 1 k(w', u* where Xux Xu and Xux -xy, we must have Yuux
and dovs = Using tu
Yaun = 1 and Hove = 1, we can obtain the solutions for W1, W2 and b as follows:
1
11 1 cos(Ou B.)
U22
1 + cos - 0.) b
1 cos(Ou 0.)
As W1
W2 M we have the similarity score for arbitrary node pair (1/, v²) as
1
1
1 + M cos(Owu 0w + 1+M 1+ M
M(d, v/) + 1 M
We can similarly verify that the above link prediction model is fully optimized with loss function C 0 as it always yield Duv 0 for k(u', r²) S M and Duv < for k(u', , o') >> M. Therefore, show that Du'r decreases with k(u', "aul,,') at a linear rate of (1- for heterophilic link prediction problem.
B.2 Proof of Theorem 2
Proof 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 single threshold Ny to separate the classes: one region for S Bo and the other for > Tu. Therefore, there always exists misclassified points regardless of the choice of zq-
B.3 Proof of Theorem 3
We begin by considering the decoder trained with the linear GNN representation v, that does not separate ego- and neighbor-embeddie in its message passing. Following our assumptions, the aggregated representation 1 for training nodes with feature x is r1 J X1 + - X2, and Y22 can be obtained similarty.
Proof 3
Similar to Proof 1, we parameterize the DistMult decoder with w = (W1, W2) and b. Suppose node u has feature vector X1 and node v has feature vector X2- As the training graph is heterophilic and (u, v) is connected on the graph, we should have Duo > 0 in this case. Without the loss of generality, set Juv 1. Furthermore, as self-loops (u, u) and (u, v) are connected in the graph,
should also have Jun. < 0 and Dvo = a < O. Using Dwe = 1, Dan < O and Dos = a < 0,
we can obtain the solutions for W1, w2 and as follows:
(a 1) + 1)2
w1 = W2 =
(d (0oss - O2) -
2 sin (0) + 02) (- (a + d(ad 2)) cos(O) 01 022 + 2nd - 1) + 02) + sin((0,) + sin(202))
b
Now we apply the optimized DistMult decoder on the test nodes with degree d'. For the test node w' with feature vector X1, the aggregated representation r4 is - + d' T- X2. Similarly, r'y can be obtained.
Assume the test nodes us has feature vector X1 and node o' has feature vector X2. Based on assumptions, (') should be connected in the heterophilic graph. Plugging in the optimized DistMult parameters, the predicted link probability Du'v' for positive (edge) node pairs can be written as
2xx (d - d') (dd' - 1) - Add' + (d')² + d² (d')² + +1)+1
(d - 1)2 (d' 112
19

---

On the other hand, for nodes with the same feature vectors (e.g. self-loops), they should not be connected the graph. The predicted link probability Du'n for self-loops can be written as
Du' a (-4dd' + (d') + de ( (d') + + + +2 - d') (dd'
(d - 1)3 (d' 1)²
Thus, the separation distance between edges and non-edges for the test nodes DistMult decoder optimized with GNN representations can be represented as
ANNN = 13''''" - Du'al
Now let us consider the baseline DistMult decoder optimized with node features Xu. is straight forward to see that if the decoder is optimized such that Buo = 1, Dun o < and Yoo = a < O, we will continue have Du'v' and Du'n' for the test nodes, the decoder is graph-agnostic. Thus, the separation distance between edges and non non-edges for the test nodes on the baseline DistMult a.
decoder can be represented as Absseline
The GNN-based DistMult decoder reduces the separation distance between edges and non-edges for the test nodes compared the baseline DistMult decoder when AGNN Absseline Solving this inequality for integers d and d' under the constraints of d Z 0, 2 0, a < O, we obtain the solutions as d' 0 d 0, d' < <didd
C Additional Real- Datasets Exhibiting Feature Heterophily
In addition the dataset we employ in experiments, identified a diverse range of heterophilious datasets from other graph learning tasks (e.g. graph or node classification). Specifically, we have identified 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_acie aeid
toluene
uracil
These datasets substantial in size, detailed below:
Table Number of entirely heterophilic Graphs in Different Datasets (from TUDataset)
Dataset
Number of Graphs
aspirin
111,763 527,984
benzene
malonaldehyde
893,238
naphthalene
226,256
salicylic_ade 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 [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.
20

---

Furthermore, we have identified node classification benchmarks from torch wrrch-geometric.oo datasets that display a wide range 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.
.tttsesss
In addition to the homophily ratios presented above, we provide the feature similarity distributions for edges and random node pairs across several datasets Figure 11, following the same convention as Figure 5 in our paper. These plots reveal clear signs of heterophily in the existing benchmark graphs.
Table 4: Homophily Ratios for Different Datasets
Dataset
Homophily Ratios
Ogbl-ppa
0.74
Ogbl-collab
0.70
Ogbl-citat2
0.40
WikiCS
0.35
PubMed [4]
0.22
e-comm
0.18
DBLP [4]
0.13
Cora [4] / Pagepao [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
21

---

-1.00 -011 -6.9 -625
63)
030 6-5
105
-1.0 -0.5 -009
-635
689
ads
350 87 1.0
-57
+6.0
+0.5
625
635
1.0
(a) AIDS Instance
(b) BBBP Instance
(c) Beneze Instance
1.70
3.50
+800
-025
C.5
8.0
+2s d.0 1/0
1.0 .an
Eis Stmlerty
250
Festare
Smilatt
(d) Computers Instance
(e) NCI Instance
PPI Instance
mnde
36-
221
36
Nattre Semilanty
(g) QM9 Instance
(h) Salicylic Acid Instance
(i) Toluene Instance
Figure 11: Heterophilic Sample Feature Distributions
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract introduces the paper's contributions on analyzing impact of heterophily in node features GNN performance. A detailed description of the paper's contributions can be found at the end of introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed limitations of our work and future directions the conclusion
($7).
Guidelines:
The answer NA means that the paper has 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 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
23

---

Answer: [Yes]
Justification: We provided the full set of assumptions in the paper with clear notations. We justify our theorems through complete and correct proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Information needed to reproduce experimental results have been in- cluded in $6, Appendix and the our GitHub repository HeteLinkPred.
com/GemsLate
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code to reproduce experimental results is provided at htttt:::/ggiieei com /t/GGesaaabeeettiiikreldd
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //niss. wwtpcccpppccaaecccccccccccccttlt htt////ddss//ee/ (oodeSummissionPoo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
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 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, as supplemental material.
7. Experiment Statistical Significance
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. SA.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
25

---

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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provided sufficient information on the computer resources for all our experiments in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /tttps:/nneurpp... httppli//tticssuiiee.ee
Answer: [Yes]
Justification: Research conducted in this paper conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
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.
26

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All assets used in this paper have been properly credited to the best of the authors' knowledge.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
27

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. Crowdsoureing 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 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 the supplemental material is fine, but if the main contribu- tion 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.
15. 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
28

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
29


Reviews:
[{"review_id": "3D2mu0qE4q", "reviewer": "Reviewer_JA9K", "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.", "questions": "Some potential suggestions:\n* Add some heterophilic GNNs as the encoders for supplement.\n* Design new decoder specifically for heterophilic link prediction tasks.\n* Analyze the reasons for the appearance of heterophilic links.", "limitations": "* Add more heterophilic real-world datasets to demonstrate the generality of conclusions.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "* This paper provides a basics including definitions and preliminary conclusion for future non-homophilic link prediction works.\n* 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.\n* The novelty is insufficient. The theoretical contributions are limited while the solutions are combinations of off-the-shelf modules.\n* Only one heterophilic real-world dataset is not enough, which may introduce bias and affect the generality of conclusions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1&2 Intuitive conclusions & novelty**\n\nWe thank the reviewer for the feedback. We note that this is the first work that explicitly characterizes feature heterophily in link prediction with GNNs. Our work pioneers in formalizing the problem, providing concise characterizations, and examining effective designs. Our paper highlights the necessity of careful selection of link prediction designs, including the significant limitation of DOT product decoders, which are widely adopted in the industry, for non-homophilic link prediction tasks, and identifies DistMult as a scalable alternative for settings which offers high scalability. We believe all these are significant and meaningful contributions to the field and open up interesting future avenues for research.\n\n**W3 Heterophilic real-world datasets**\n\nThank you for your questions. First, we would like to emphasize that we have run experiments on a series of synthetic graphs of different heterophily ratios/feature similarity distributions. Second, going beyond the global characterization of the graphs for the link prediction task, we also provided a zoom-in analysis on the performance on heterophilous edges per method for each real-world dataset, which also demonstrates the effectiveness of our identified designs in improving GNN performance on the full spectrum of low-to-high feature similarity (c.f. Line 360-365, 370-374, and Figure 4). This is important since in reality every dataset exhibits variance in feature similarity across all the links. Finally, by casting light on the problem of link prediction beyond homophily, we hope that our work will motivate the introduction of a high-quality set of benchmarks with diverse feature similarity, beyond the real data that we presented. This trend was also observed in the literature after the challenges of heterophily for GNNs were pointed out in the node classification task [1,2]: as the problem attracted more interest, various research teams dedicated their efforts to introducing a range of heterophilous datasets, thereby advancing findings and methodologies within the subfield. In Figure 1 of our general response plots, we have shown that many real-world heterophilous node classification benchmarks, such as pokec [1] and Amazon ratings [2], are homophilous for link prediction, with most edges connecting nodes with similar features. Nevertheless, as we mentioned above, these datasets still have heterophilous edges where our theory and findings apply.\n\n[1] Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. (NeurIPS 2021).\n\n[2] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? (ICLR 2022).\n\n**Q: potential suggestions**\n\nThank you for your valuable suggestions. Following your recommendation, we have added one more heterophilic GNN as the encoder for experiments (highlighted in Table 1 general response pdf) and our conclusions about the GNN decoder and encoder still hold.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2IGaDkAlWW", "reviewer": "Reviewer_kFpa", "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.", "questions": "1. It's better to denote the mean feature vector of all nodes as $\\hat{x}$ instead of $\\hat{X}$\n\n2. Have you tried other heterophily-specific techniques, e.g. high-pass filter or negative message passing?", "limitations": "the authors adequately addressed the limitations", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "originality: good\nquality: good\nclarity: good \nsignificance: good", "weaknesses": "The theoretical analysis is a bit over-simplified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1 Theoretical Analysis**\n\nThank you for your feedback. First, our theorems are derived under reasonable simplifications, which are typical in the heterophily literature (e.g., [1-2]). Second, our empirical analysis extends well beyond these theoretical assumptions, demonstrating that our theory holds more broadly. Finally, we emphasize that our theoretical analysis aims to provide concise characterizations as an initial step in formalizing this problem. We believe that extending beyond our current theoretical framework will be a valuable direction for future research.\n\n[1] Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. (NeurIPS 2020).\n\n[2] Revisiting Heterophily For Graph Neural Networks. (NeurIPS 2022).\n\n\n**Q1 Notation of mean feature vector: use $\\bar{\\mathbf{x}}$ instead of $\\bar{\\mathbf{X}}$**\n\nThank you for reading our paper carefully! We will make this modification in our final version. \n\n**Q2 Other Heterophily-specific techniques, e.g. high-pass filter**\n\nThank you for your suggestion. We agree that considering different heterophily-specific techniques is important and will be an interesting direction for future work. The main contribution of this paper is to propose and characterize feature heterophily, marking a pioneering effort in this area.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g4DHdDiOzc", "reviewer": "Reviewer_dskj", "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.", "questions": "1. How to generate synthetic graphs that resemble different types of link prediction tasks by varying the feature similarity between connected nodes?\n2. 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": "Yes, the author has a clear understanding and explanation of the limitations of the proposed method.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "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? \n2、In addition, the hierarchical structure of the paper is not very reasonable, such as the chapter positions of the relevant work in Section 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1, Q1 Clarifications (1) implementation of feature extraction (2) generation of synthetic graphs**\n\nThank you for your questions. \n- For **W1(1)** implementation of feature extraction, we interpret the \"feature extraction\" part in your comment as how we obtain the node features for our synthetic and real-world datasets---please correct us if our interpretation is not right. For real-world graphs, we use the original node features provided in the datasets that are created by previous works: ogbl-collab and ogbl-citation2 from Open-Graph Benchmark [1], and e-comm from [2]. We give a brief overview of how the node features are created in Lines 532-539 in Appendix A. Our synthetic datasets are created by rewiring the edges among 10,000 sampled nodes from the real-world dataset `ogbl-collab`; we keep the features attached to each node during the sampling process, which become the node features for our synthetic graphs instead of generating new node features ourselves.\n- For **W1(2) and Q1** generation of synthetic graphs, we describe our synthetic graph generation process in Lines 512-520 in Appendix A (as we mentioned in Line 280 in Section 6.1): the synthetic graphs are generated by randomly sampling 10,000 nodes with their features in ogbl-collab and connecting 2% of all possible node pairs whose feature similarity falls within specified ranges; all graphs share the same set of nodes and features and only differ in their edges. More specifically, we calculate the pairwise feature similarity between all node pairs and create 50-quantiles of feature similarity scores. We select the 3 smallest quantiles, the 3 largest quantiles, and 4 quantiles in equal intervals in between, resulting in 10 quantiles. We then create 10 synthetic graphs by connecting node pairs whose feature similarity scores fall within the same quantile. Thus, by gradually increasing the range of similarity for connected nodes, we create graphs which resemble different types of link prediction tasks and average feature similarity.\n\n[1] Open Graph Benchmark: Datasets for Machine Learning on Graphs. (NeurIPS 2020)\n\n[2] Pitfalls in Link Prediction with Graph Neural Networks: Understanding the Impact of Target-link Inclusion & Better Practices. (WSDM 2024)\n\n**W2 Structure of paper; position of the related work section**\n\nThank you for your suggestion. We will revise the paper structure and specifically move the related work section to an earlier location (e.g., Section 2) in the final version.\n\n\n**Q2 How is the predicted link probability derived**\n\nThank you for your question. For our theoretical analysis in Sections 3 & 4, the \"predicted link probability\" $\\hat{y}_{u,v}$ is derived based on the equation in Line 144 (\"Theoretical Assumptions\" paragraph) in Section 3.2. \n\nWe note that we should have used \"predicted link score\" instead of \"predicted link probability\" for the discussions in Section 3, as the \"link probability\" term implies that our prediction $\\hat{y}_{u,v}$ is bounded within $[0,1]$ which is not the case in our analysis. However, our analysis can still be given a probabilistic perspective as we can derive the predicted link probability by taking sigmoid $\\mathrm{sigmoid}(\\hat{y})$ on the predicted link score. We will revise the usage of \"predicted link probability\" term in our final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3mG23TAzxi", "reviewer": "Reviewer_YTzD", "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.", "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.\n\n2. The green line in Fig.1 denotes the score distribution of positive node pairs, why all the scores for positive pairs are identical? \n\n3. 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.\n\n4. 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?\n5. 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": "As pointed out in Questions 3, the theoretical results for more general cases need to be addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n2. The paper is well-written and easy to follow.\n3. 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.\n2. More benchmark datasets can be considered to cover a diversity of feature similarity distribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1 Exploring the relationship between feature similarity and structural similarity**\n\nThank you for raising this valuable suggestion. Exploring the dynamics between feature and structural similarity would indeed be an interesting direction for future research. In this work, our aim is to provide the first essential characterizations of the impact of feature heterophily on link prediction for GNNs. Future work can explore more fine-grained questions, such as the insightful one you raised.\n\n**W2 Benchmark datasets**\n\nThank you for your feedback. First, we would like to emphasize that we have run experiments on a series of synthetic graphs of different heterophily ratios/feature similarity distributions. Second, going beyond the global characterization of the graphs for the link prediction task, we also provided a zoom-in analysis on the performance on heterophilous edges per method for each real-world dataset, which also demonstrates the effectiveness of our identified designs in improving GNN performance on the full spectrum of low-to-high feature similarity (c.f. Line 360-365, 370-374, and Figure 4). This is important since in reality every dataset exhibits variance in feature similarity across all the links. Finally, by casting light on the problem of link prediction beyond homophily, we hope that our work will motivate the introduction of a high-quality set of benchmarks with diverse feature similarity, beyond the real data that we presented. This trend was also observed in the literature after the challenges of heterophily for GNNs were pointed out in the node classification task [1,2]: as the problem attracted more interest, various research teams dedicated their efforts to introducing a range of heterophilous datasets, thereby advancing findings and methodologies within the subfield. In Figure 1 of our general response plots, we have shown that many real-world heterophilous *node classification* benchmarks, such as pokec [1] and Amazon ratings [2], are homophilous for link prediction, with most edges connecting nodes with similar features. Nevertheless, as we mentioned above, these datasets still have heterophilous edges where our theory and findings apply.  \n\n[1] Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. (NeurIPS 2021).\n\n[2] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? (ICLR 2022).\n\n**Q1 Clarification on \\hat{y}**\n\nThank you for carefully reading our paper! For our theoretical analysis in Sections 3 & 4, the \"predicted link probability\" $\\hat{y}_{u,v}$ is derived based on the equation in Line 144 (\"Theoretical Assumptions\" paragraph) in Section 3.2. \n\nWe note that we should have used \"predicted link score\" instead of \"predicted link probability\" for the discussions in Section 3, as the \"link probability\" term would imply that our prediction $\\hat{y}_{u,v}$ is bounded within $[0,1]$ which is not the case in our analysis. We will revise the usage of \"predicted link probability\" term and make changes to ensure the notations are consistent and clear in our final version. \n\n**Q2 Identical scores for positive pairs**\n\nThank you for the question. Figure 1 gives some *example distributions* of positive node pairs (i.e., edges – colored in green) and negative node pairs (non-edges – colored in red) for homophilic and heterophilic link prediction tasks to contextualize the introduction of these concepts. In these examples, the feature similarity scores of positive node pairs are simplified to follow a uniform distribution, hence we show the horizontal green lines in the Probability Density Function (PDF) plots of the similarity score distribution. Of course in real-world datasets the similarity score distributions for both positive and negative node pairs can be more complex: in Figure 5 in the Appendix we show the *actual* feature similarity score distributions for real-world datasets used in our experiments.\n\n**Q3 Generality of theoretical results on learning rate**\n\nThe goal of this theorem is to show that the predicted link probability is related to the magnitude of the threshold M that separates the positive and negative samples, which highlights the different optimizations needed for homophilic and heterophilic link prediction tasks that have not been studied in prior literature. While generalizing the theorem to higher dimensions is non-trivial, our experiments in Section 6 have strengthened this implication to datasets of significantly higher complexity.\n\n**Q4 Details about the real-world data**\n\n| Dataset          | Training Edges | Validation Edges | Test Edges |\n|------------------|----------------|------------------|------------|\n| ogbl-citation2   | 30,387,995     | 86,956           | 86,956     |\n| ogbl-collab      | 1,179,052      | 60,084           | 46,329     |\n| e-comm           | 238,818        | 34,117           | 68,235     |\n\nThe above table shows the details of the split of edges for train, validation, and test on real-world datasets. Note that in standard GNN4LP research, there are usually far more training edges than validation and test edges combined (see Table 2 in [14] in paper references). We follow the standard approach of data splitting. It would be an interesting future direction to consider the impact of data splitting on model performance. \n\n**Q5 Reasons for dividing the buckets**\n\nThank you for the question. We use the minimum degree of connected nodes to divide the buckets in Fig. 4 since it has been shown in previous works that the presence of low-degree nodes (see [44] in paper references) can increase the complexity of heterophily for node classification tasks and negatively impact GNN performance. By using the minimum degree instead of maximum or average degree, we can group edges that are connecting at least one node with low degree and examine how different approaches perform on these edges. We will also explain our choice in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jbSj73maOI", "reviewer": "Reviewer_ufZT", "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.", "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.\n\n2. 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.\n\n3. Is it possible to expand the scope of this study to any link prediction method rather than GNNs?", "limitations": "See the weakness.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The paper writing is clear and easy to understand.\n\n2. The research problem of feature heterophily on link prediction tasks is novel.\n\n3. The theoretical analysis part is comprehensive and intuitive.\n\n4. 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.\n\n2. 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1 Significance of the work**\n\nThank you for your feedback. We want to point out that going beyond the global characterization of the graphs for the link prediction task, we also provided a zoom-in analysis on the performance on heterophilous edges per method for all the real-world datasets, which also demonstrates the effectiveness of our identified designs in improving GNN performance on the full spectrum of low-to-high feature similarity (c.f. Line 360-365, 370-374, and Figure 4). This is important since in reality every dataset exhibits variance in feature similarity across all the links. That said, we acknowledge that finding real-world, *publicly-available* graphs that align with the heterophilic link prediction task, as discussed in Section 3, is non-trivial. Currently, we have identified e-comm as a high-quality non-homophilic network for link prediction. In Figure 1 of our general response plots, we have demonstrated that many real-world heterophilous node classification benchmarks, such as Pokec [1] and Amazon Ratings [2], are predominantly homophilous for the link prediction task, with most edges connecting nodes with similar features. Nevertheless, as we mentioned above, these datasets still have heterophilous edges where our theory and findings apply.\n\nWe believe that the current limited number of high-quality heterophilous link prediction datasets does not imply that the problem itself is artificial. To bring in a bit more context, the lack of high-quality heterophilous datasets for *node classification* tasks was also a longstanding challenge before the challenge of heterophily for GNNs became widely recognized in the field. As the problem attracted more interest, various research teams dedicated their efforts to introducing a range of heterophilous datasets, thereby advancing findings and methodologies within the subfield. Additionally, as we mentioned above, heterophilous connections can also arise *locally* even if the graph is homophilous in general, which motivates our locallized, more nuanced analysis (cf. Figures 4 and 9).  Thus, by casting light to the problem of link prediction beyond homophily, we hope that our work will motivate the introduction of a high-quality set of benchmarks with diverse feature similarity, beyond the real data that we presented. \n\n[1] Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. (NeurIPS 2021).\n\n[2] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? (ICLR 2022).\n\n**W2 Relation of synthetic graph generation with other random graph generation methods**\n\nOur synthetic graph generation process is detailed in Lines 512-520 in Appendix A. Most of the random graph generation methods in existing literature studying heterophilous graphs are for creating synthetic datasets for node classification: [3,4] follow a modified preferential attachment process, where the probability of an edge is determined by both the class compatibility matrix and the node degree, while [5] follows to use contextual stochastic block model (CSBM) for synthetic graph generation. However, all of the aforementioned approaches control the homophily/heterophily levels defined on class labels of the generated synthetic graphs, while for graphs for link prediction usually do not have class labels. NetInfoF [6] recently generates synthetic graphs as link prediction benchmarks by controlling the correlation between node feature and edge existence. However, their generation process only allows node features to be fully correlated, partially correlated, or uncorrelated with edge existence; it lacks the capability to granularly control the feature similarity of the generated graph as in our graph generation process, and it is also not capable of generating graphs where features are *negatively* correlated among connected nodes. We will include these discussions in our final version. \n\n[3] Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. (ICML 2019).\n\n[4] Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. (NeurIPS 2020).\n\n[5] Adaptive universal generalized pagerank graph neural network. (arXiv 2020).\n\n[6] NetInfoF Framework: Measuring and Exploiting Network Usable Information. (ICLR 2024).\n\n**W3 Theorem connections with GNNs**\n\nThank you for the feedback. Existing GNN4LP methods are composed of encoders and decoders, both of which are essential components. Our first two theorems primarily consider the effectiveness of link prediction decoders, which, as our experiment shows, have a significant impact on GNN performance under link prediction tasks. Furthermore, the choice of decoders in link prediction tasks is not as trivial as it might seem: while MLP decoder is more preferred in academic research, DOT product decoder is more widely adopted in industry due to its scalability in tasks such as retrieval. Our theoretical analysis reveals the limitation of DOT product decoder for non-homophilic link prediction tasks and helps identify DistMult as an effective substitute which maintains the scalability of DOT product with closer-to-MLP link prediction accuracy. We will make the connections more clear in our paper.\n\n**Q1 Insights for non-attributed graphs**\n\nOur study primarily focuses on the impact of feature heterophily. As we define heterophily on node features, our definition and analysis is not applicable to graphs without node features. Given the prevalence of attributed graphs in real-world applications (e.g., textual information is often associated with nodes in industrial and other applications), we believe that the contributions of this work are significant for these commonplace settings.\n\n**Q2 Expand the analyses to k-hop neighbors**\n\nWe appreciate the reviewer for sharing this valuable suggestion. We believe it would be an interesting direction to explore in future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to express our gratitude to the reviewers for their thoughtful and constructive feedback. We are pleased that all reviewers find the paper clear, most reviewers recognize the novelty of studying the impact of feature heterophily on link prediction with GNNs, and some reviewers (e.g., YTzD, ufZT) point out that they value our theoretical analysis and find that our empirical analyses are comprehensive and validate our theoretical findings. 

We answer each reviewer’s questions in separate rebuttals. In this general response, we provide supplementary figures, to which we refer in the individual reviewer questions, as needed.

Meta-review: 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.
Decision: Accept (poster)