{'fraction_non_alphanumeric': 0.039028526105625905, 'fraction_numerical': 0.019527938079479255, 'mean_word_length': 4.722065727699531, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Break the Wall Between Homophily and Heterophily for Graph Representation Learning

Homophily and heterophily are intrinsic properties of graphs that describe whether two linked nodes share similar properties. Although many Graph Neural Network (GNN) models have been proposed, it remains unclear how to design a model so that it can generalize well to the whole spectrum of homophily. This work addresses the challenge by identifying three graph features, including the ego node feature, the aggregated node feature, and the graph structure feature, that are essential for graph representation learning. It further proposes a new GNN model called OGNN (Omnipotent Graph Neural Network) that extracts all three graph features and adaptively fuses them to achieve generalizability across the whole spectrum of homophily. Extensive experiments on both synthetic and real datasets demonstrate the superiority (average rank 1.56) of our OGNN compared with state-of-the-art methods.


INTRODUCTION
Graph neural networks (GNNs) have been proven to be a powerful approach to learning graph representations for node classification tasks (Kipf & Welling, 2016). Researchers have proposed different GNN model designs based on the underlying assumption of either graph homophily or heterophily. On the one hand, many works (Kipf & Welling, 2016;Hamilton et al., 2017;Veličković et al., 2017;Gao et al., 2018;Klicpera et al., 2018;Xu et al., 2018b;Wu et al., 2019) assume strong graph homophily, which means linked nodes in the graph tend to share similar properties or labels. These GNNs adopt a message passing paradigm that recursively propagates and aggregates node features through the edges in the graph to produce smoothed node representations (Gilmer et al., 2017;Battaglia et al., 2018). We refer to these GNNs as homophily-based GNNs.
On the other hand, some recent works empirically demonstrate the poor performance of homophilybased GNNs on heterophilic graphs, which have the opposite property to homophily. Examples of these graphs include online transaction networks where fraudsters are more likely to connect with customers than their colleagues, and protein networks where different amino acid types tend to be connected. GNNs designed for heterophilic graphs leverage various strategies to generalize better on these graphs, such as embedding and mixing graph topology with node features (Lim et al., 2021a), ego-neighbor embedding separation, and higher-order neighborhood representation combination (Zhu et al., 2020), degree correction and signed messages (Yan et al., 2021), and generalized PageRank weights (Chien et al., 2020). They perform much better on graphs with a strong heterophily property but achieve only comparable, if not worse, accuracy on homophilic graphs than homophily-based GNNs. We refer to these GNNs as heterophily-based GNNs.
Neither homophily-based GNNs nor heterophily-based GNNs are ideal, since they invisibly establish a wall between homophily and heterophily for graph representation learning -a GNN can work well on either heterophilic graphs or homophilic graphs, but not both. Real-world graph data, however, could have various levels of homophily. It is a hassle to first classify a graph as homophilic or heterophilic before a suitable GNN model can be identified. What's worse, some graphs cannot be easily classified as homophilic or heterophilic. For example, twitch-gamer (Rozemberczki & Sarkar, 2021) is a social network graph in which the users follow each other by their game interests, while the nodes (i.e., users) are labeled by gender. Since the following relationships (i.e., the connections) are not dominated by gender (i.e., the label), the homophily of twitch-gamer is 0.55, which falls in the ambiguous intermediate region on the homophily spectrum. One needs to try both homophily-based GNNs and heterophily-based GNNs to identify the suitable models, significantly increasing data analytic costs.
To address the problems, this paper proposes a model called omnipotent GNN (OGNN) that can generalize well to the whole spectrum of homophily. The design of OGNN is motivated by the observation that each node in a graph can be modeled by different types of features, including the feature of itself, the feature of its neighbors, and its connections with the other nodes. These features are of different importance in determining a node's property depending on the graph's homophily. The basic idea of OGNN is to effectively transform and adaptively fuse these features to derive each node's representation in the graph. Our main contributions are summarized as follows: • We identify three aspects of the graph features that are essential for graph representation learning: ego node feature, aggregated node feature, and graph structure feature. We analyze the importance of these graph features and propose a general form for extracting them. Our detailed ablation study demonstrates that these features have different importance for the graphs with different homophily. • We propose the OGNN model that generalizes to graphs over the homophily spectrum.
OGNN could effectively learn graph representation by integrating the three graph features with adaptive feature fusion under a bi-level optimization framework. • We conduct extensive experiments to compare OGNN with state-of-the-art GNNs using synthetic and real graph benchmarks that cover the full homophily spectrum. OGNN outperforms 8 baseline models and achieves an average rank of 1.56 on 9 real datasets. Specifically, OGNN achieves higher node classification accuracy, 4.55% higher than GCN (Kipf & Welling, 2016), 4.39% higher than MIXHOP (Abu-El-Haija et al., 2019), and 3.27% higher than H2GCN (Zhu et al., 2020), on average over the real datasets.

NOTATIONS AND PRELIMINARIES
Notations. Let G = (V, E) denotes a graph with N nodes and M edges, where V and E are the set of nodes and edges respectively, |V| = N and |E| = M . We use A ∈ {0, 1} N ×N as the The raw feature vectors of all nodes in the graph form a feature matrix X ∈ R N ×D . The nodes are categorized into C classes. The label of a node v i of class k is represented by a one-hot vector y i of size C, whose k-th dimension is 1 while the other dimensions are 0. All the label vectors form the label matrix Y ∈ {0, 1} N ×C . This paper focuses on the node classification task (Kipf & Welling, 2016). The goal of the node classification task is, given a train set V train ∈ V with label set Y train , learn a mapping F : V → Y, which maximizes the possibility P (arg max F(v) = arg max y v ) for any vertex v ∈ V \ V train .
Homophily and Heterophily. Graph homophily H measures the overall similarity between the nodes connected by an edge in terms of the labels. There are multiple ways for computing graph homophily (Pei et al., 2020;Zhu et al., 2020;Lim et al., 2021b;Apollonio et al., 2022). In this paper, we adopt the most widely-used edge homophily (Zhu et al., 2020): Definition 1. Given a graph G = (V, E) with labels Y, the edge homophily is defined as , which represents the fraction of the edges that connect two nodes with the same class label.
The edge homophily ranges from 0 to 1. Graphs with edge homophily close to 1 are called homophilic graphs, while the ones with edge homophily close to 0 are called heterophilic graphs.
Graph Neural Networks. Most GNNs follow the message passing framework. In the message passing framework, the hidden state of a node v ∈ V depends on the features of its neighbors and its ego feature. A typical message passing layer is where h l represents the hidden feature of a node at layer l, Ψ and Φ are transformation functions, which could be any differentiable functions like linear transformations or multi-layer perceptron (MLP). Γ is a permutation invariant function such as sum, mean, and max, while N (v) is the node set of v's neighborhoods. The message passing layer transforms the features from the neighborhoods with Φ as the messages and then aggregates them with Γ. After that, Ψ updates the node feature with the ego feature and the aggregated message. By stacking multiple message passing layers in the model, GNNs could iteratively propagate information to the target node from multi-hop neighborhoods.

GRAPH REPRESENTATION LEARNING OVER DIFFERENT HOMOPHILY
Although many different GNNs have been proposed, most of them are designed under the assumption of either strong homophily or heterophily, making them incapable of generalizing well to a whole spectrum of homophily. To illustrate our statement, we conduct experiments to validate the classification accuracy of several GNN models on a synthetic benchmark syn-cora (Zhu et al., 2020). syn-cora provides homophily levels varying from 0.0 to 1.0 with 0.1 as the interval. The nodes and their raw features of syn-cora are from the Cora dataset (Sen et al., 2008;Yang et al., 2016), while the edges are randomly generated according to different homophily settings. Details about syn-cora are in Section 5.1. Figure 1 shows the result of different GNNs and our proposed OGNN on syn-cora with varying homophily levels. Overall, most existing GNNs cannot generalize well over the spectrum of homophily. Specifically, GCN (Kipf & Welling, 2016), and DAGNN  achieve high accuracy on graphs with high homophily, but their performance drops severely as the homophily decreases. When the homophily is lower than 0.5, their performance is even worse than Multi-Layer Perceptron (MLP) which relies solely on the node features without any structural information. Meanwhile, LINKX (Lim et al., 2021a) outperforms MLP, DAGNN, and GCN on graphs with low homophily, but its performance on the graphs with strong homophily, i.e., 0.7 ∼ 1.0 is the worst besides MLP.
Both H2GCN (Zhu et al., 2020) and GPR-GNN (Chien et al., 2020) are designed to adapt to both homophilic and heterophilic graphs. However, GPR-GNN cannot compete with MLP on low edge homophily because their model design still follows the message passing paradigm. Although H2GCN is the winning solution from existing GNNs on the syn-cora dataset, it is outperformed by our proposed approach OGNN. Moreover, H2GCN shows worse performance on real-world heterophilic graphs compared to heterophily-based GNNs, e.g., LINKX (see Section 5.2). We suspect that the reason is that H2GCN does not leverage graph structure features as in LINKX and our approach OGNN. In Section 5.2, we empirically show that graph structure is an important feature for learning on real-world heterophilic graphs.
To summarize, existing GNNs hardly show consistently good performance on graphs with various homophily settings. Therefore, in this paper, we aim at designing a new GNN that can generalize well across graphs with different homophily.

OGNN: A GNN FOR GRAPHS WITH DIFFERENT HOMOPHILY
In this section, we first analyze three types of features from a graph: the ego-node feature, the aggregated neighborhood feature, and the graph structure feature, which cover multi-faceted information for graph representation learning. Then we present our model OGNN which effectively extracts the three types of features and adaptively fuses them with a bi-level optimization training scheme.

GRAPH INFORMATION ANALYSIS
Ego-Node Feature. The ego-node feature refers to a node's embedding resulting from transforming the node's raw feature without considering its neighborhoods. Formally, the ego-node feature h ego of a node v with its raw feature x v is: where f ego (·) can be any transformation functions such as linear transformation or MLPs.
The ego-node feature is the basic and essential information for node classification tasks. This intuition is based on two observations. First, as shown in Figure 1, applying MLP on only raw node features of heterophilic graphs can significantly outperform many homophily-based GNNs (Kipf & Welling, 2016;Veličković et al., 2017; that rely on both the raw node features and the aggregated neighborhood features. This empirical observation implies that the ego-node feature alone plays an important role in GNN's generalizability. Second, a recent study (Zhu et al., 2020) proves that, under some conditions, a GCN layer that separately embeds ego-node features and neighbor-node features is more capable of generalizing to heterophilic graphs than co-embedding them. It is because, in heterophilic settings, the class labels and the raw features of a node and its neighborhoods may be different. The ego-node feature could be a more robust signal for the node's label than the mixture of features from the node itself and its neighborhood.
We empirically validate this intuition in Section 5.2 and demonstrate that (1) GNNs with ego-node features can achieve 0.25% ∼ 4.30% higher accuracy than those without ego-node features across graphs with different levels of homophily.
(2) The importance of ego-node features increases as the homophily of a graph becomes lower. For example, on syn-cora graph with 0.8 homophily, the importance of ego-node features is 0.197 out of 1, while with 0.2 homophily, the importance increases to 0.656.
Aggregated Neighborhood Feature. The aggregated neighborhood feature complements ego-node features by capturing the information from the neighborhood to the target node. Formally, the aggregated neighborhood feature h agg of a node v with raw feature where N k (v) represents the set of k-hop neighbors and f agg (·) is a function that transforms and aggregates the features from the neighborhood as well as the target node's own feature.
There are many approaches to materialize the function f agg (·). One approach is to simply stack multiple message passing layers as in many homophily-based GNNs such as GCN and GAT. Each message passing layer first transforms the features and then aggregates them to pass to the next layer, as in Eq. 1. However, this approach allows only a limited size of neighborhoods to be considered since the performance of these GNNs degrades severely when more than three layers are stacked (Li et al., 2018;Zhang et al., 2022). An alternative approach is a decoupled transformation and aggregation strategy where raw features are transformed first and then go through multiple aggregation layers without being transformed again. Recent works (Klicpera et al., 2018; demonstrate that the alternative approach could achieve much better generalization performance on homophilic graphs as it can effectively capture the information from a large neighborhood region. We will also adopt this strategy in OGNN. Our empirical study shows that (1) GNNs with aggregated neighborhood features can achieve 0.13% ∼ 13.96% higher accuracy than those without aggregated features across graphs with different homophily, and (2) the importance of the aggregated neighborhood features increases as the homophily of a graph becomes higher. For example, on syn-cora graph with 0.2 homophily, the importance of aggregated features is 0.284 out of 1, while with 0.8 homophily, the importance increases to 0.772.
Graph Structure Feature. Although the aggregated neighborhood feature involves the local connections around the target node, it loses a fair amount of the graph structural information because of the permutation invariant aggregation process. Therefore, it is necessary to take the graph structure information as an independent information source for graph representation learning. Formally, the graph structure feature is: where A k is the k-th power of the adjacency matrix A, A k [v, :] is the v-th row of A k , and f strc (·) could be any transformation functions.
Graph structure feature has been shown to be very effective in node classification tasks on heterophilic graphs. Both LINK and LINKX (Zheleva & Getoor, 2009;Lim et al., 2021a) leverage the simplest form of graph structure feature, the adjacency matrix, to learn node embedding and show better performance than many GNNs on heterophilic graphs (Abu-El-Haija et al., 2019; Chien et al., 2020;Zhu et al., 2020). However, these works consider only k = 1, i.e., the adjacency matrix with only 1-hop neighbors. In this work, We propose to use the combination of different powers of the adjacency matrix as a more general form of graph structure feature. The intuition behind it is that k = 1 captures local structure information while k > 1 captures regional/global structure information.
Our empirical study shows that (1) on all the 9 real-world graphs we experiment with, the best performance is achieved when k is larger than one, and (2) graph structure features can improve classification accuracy by 0.78% ∼ 20.49% across the graphs with different homophily.
To sum up, the three types of features summarize distinct graph information: the ego-node feature and the aggregated neighborhood feature model the information from a node's feature and its neighborhoods respectively; the graph structure feature models both the local and global structure information regardless of the node features.

OGNN MODEL DESIGN
OGNN effectively extracts all three types of graph features and adaptively fuses them together to achieve good generalizability across the whole spectrum of homophily. We now explain its three main components, feature extractors, adaptive feature fusion, and bi-level optimization in details.
Feature Extractors. The Ego-Node Feature Extractor is a simple linear transformation of the raw node feature matrix X ∈ R N ×D : H ego = XW ego , where W ego ∈ R D×d is the transformation matrix and H ego ∈ R N ×d is the extracted ego-node features. We use linear transformation instead of MLP because linear transformation consistently achieves the best accuracy in our empirical evaluation.
The Aggregated Neighborhood Feature Extractor adopts the state-of-the-art design in the message passing framework, where feature transformation and propagation are decoupled (Zeng et al., 2021). It propagates the ego-node features H ego and combines the features of different propagation steps to enlarge the receptive field: is the normalized adjacency matrix, and D is the diagonalized node degrees. s 1 is the maximum propagation step.
The Graph Structure Feature Extractor computes the combination of different powers of the adjacency matrix after a linear transformation: H strc = s2 j=1 A j W strc , where W strc ∈ R N ×d is the transformation matrix, and s 2 is the maximum power of the adjacency matrix. The use of a simple linear transformation is for its efficiency, as we do not observe performance gains from an MLP.
Adaptive Feature Fusion. The three types of features play different roles in modeling graph information and thus their importance in different homophily settings varies. The adaptive weighted feature fusion module assigns a trainable scalar importance score for each feature so that it can automatically learn the features' importance from the input graph: where H is the fused feature and σ is a non-linear activation function ReLU. P = {p i |i = 1, 2, 3} are trainable parameters, and {π i |i = 1, 2, 3} are the weights for each feature.
After obtaining the fused feature H, we predict the labels for each node with a linear classifier, Y pred = Softmax(HW pred ), where Y pred ∈ R N ×C is the predictions and W pred ∈ R d×C is the predictor's parameters.
Bi-level Optimization. To train our model parameters and feature fusion weights jointly, we borrow the idea of bi-level optimization (Liu et al., 2018;Dong & Yang, 2019). Suppose the model parameters is W and the parameters for feature fusion is P. The loss function of the node classification tasks is: where G is the graph, X and Y are raw node features and ground-truth labels respectively, and y i ∈ Y pred is the prediction of our model for node i. Then the objective of our bi-level optimization is: min In short, we optimize the model parameters W on the train set, while optimizing the feature fusion parameters P on the validation set alternatively.

EXPERIMENTS
We conduct experiments on both synthetic datasets and real datasets with various homophily to examine the efficacy of our model in terms of test accuracy.

EXPERIMENTAL SETTINGS
Synthetic Dataset. We generate synthetic graphs syn-cora with the approach in H2GCN (Zhu et al., 2020). The syn-cora dataset provides 11 graphs with homophily ranging from 0.0 to 1.0 with 0.1 as the interval. The raw node features and labels for each graph are sampled from the cora dataset (Sen et al., 2008). The edges of the graph are generated gradually according to the given homophily. We evaluate the average test accuracy over five trials for all the methods on these graphs with the same train/validation/test data splits (25%, 25%, 50%, for each class).
Real Dataset. We also evaluate our method and existing GNNs on 9 real-world datasets, whose homophily ranges from 0.222 ∼ 0.931. Table 4 in Appendix Section A summarizes the datasets detailed statistics. Cora (Sen et al., 2008), CiteSeer (Sen et al., 2008), PubMed (Sen et al., 2008), and Coauthor CS & Physics (Shchur et al., 2018) are widely-used homophilic graphs, while penn94 (Traud et al., 2012), arXiv-year (Hu et al., 2020), genius (Lim & Benson, 2021), and twitch-gamer (Rozemberczki & Sarkar, 2021) are graphs with low to medium homophily (Lim et al., 2021b;a). The data splits of these datasets are explained in Appendix Section A. We report the average and the standard deviation of the test accuracy in the following experiments.  (Chien et al., 2020)). Our experiments also include MLP because it is a strong baseline for heterophilic graphs. We did grid-based hyper-parameter search for all baselines and our approach (Details in Appendix Section C).
Hardware Specifications. We run experiments on both synthetic and real world benchmarks with a 12-core CPU, 8 GB Memory, and an NVIDIA GeForce GTX 1080 Ti GPU with 11 GB GPU Memory for all the methods except for H2GCN, because it suffers from the out-of-memory (OOM) problem. For H2GCN, we use a workstation with a 12-core CPU, 32 GB Memory, and an NVIDIA Quadro RTX 8000 GPU with 48 GB GPU Memory.

QUANTITATIVE RESULTS
Results on Synthetic Dataset. Table 1 reports the average test accuracy over five random splits on the graphs in the syn-cora dataset. Overall, OGNN outperforms the existing methods on most homophily settings, with seven settings at top-1 and four at top-2. Especially, in the ambiguous homophily region (about 0.4 ∼ 0.6), OGNN achieves state-of-the-art results by pushing the best accuracy up to 2.76%. A full version with standard deviation can be found in Appendix Section D.
The results echo our analysis in Section 3. The performance of homophily-based GNNs such as GCN, GAT and DAGNN are outstanding at high homophily settings. However, they fail to perform well on the heterophilic graphs and are much worse than the baseline MLP, which is graph-agnostic. LINKX is a simple but strong baseline on non-homophilic graphs, but it performs poorly on high homophily settings (≥ 0.7), merely better than MLP. For H2GCN, MIXHOP, and GPR-GNN, which are designed to generalize well on both homophilic and heterophilic graphs, they show variant performance in our experiments. MIXHOP and GPR-GNN cannot achieve as good accuracy as they claimed on low homophily settings, reflecting their unsatisfying generalization performance. H2GCN shows the most competitive performance among existing GNNs, especially on very low homophily settings (0.0 and 0.1). However, OGNN outperforms it on a larger range of homophily (0.2 ∼ 0.8), which are also more common cases in real-world datasets. Results on Real Dataset. Table 2 reports the results on the 9 real datasets. Overall, OGNN achieves seven top-1 and one top-2 over 9 datasets, with an average rank of 1.56. Compared with homophily-based GNNs including GCN, GAT, and DAGNN, our method outperforms the best of them (i.e., DAGNN) on the homophilic graphs and is far better than any of them on the heterophilic graphs. OGNN is also competitive compared to the heterophily-based GNNs, including LINKX, H2GCN, MIXHOP, and GPR-GNN. On penn94 and arXiv-year, we improve the accuracy by 0.72 ∼ 4.31% and 0.5 ∼ 11.61% respectively. On genius and twitch-gamer, we have small gaps (0.86% and 0.13%) compared with the best method LINKX.  Ablation Study. We present ablation study to show the effectiveness of our design choices: the three graph features, adaptive feature fusion, and bi-level optimization. Table 3 reports the accuracy results from five variants of our model by removing one design element at a time.
Graph features. The 2nd to the 4th row demonstrate the contribution of the three graph features on the model's accuracy. Overall, models without one of the features suffer from 2.49% ∼ 5.81% accuracy drop on all the datasets on average, indicating the importance of these features on graph representation learning regardless of their homophily. Specifically, models without the aggregated neighborhood feature have a larger accuracy drop on homophilic graphs (i.e., Cora, CiteSeer, PubMed, Coauthor CS & Physics). It echoes the high performance of message passing-based neural networks (e.g., GCN and DAGNN) on homophilic graphs. On the contrary, models without the graph structure feature suffer more severely on heterophilic graphs (i.e., penn94, arXiv-year, genius, and twitch-gamer). It echoes the high performance of GNNs that rely heavily on graph structures (e.g., LINKX) on heterophilic graphs.
Adaptive feature fusion. Models without adaptive feature fusion treat the three graph features equally and sum them up without re-weighting to produce the final node feature. It suffers from an accuracy drop of 2.22% on average, indicating the importance of adaptive feature fusion. Another widely-used approach for feature fusion is to concatenate the features. Although concatenation could learn separated parameters for different features, the features could not be balanced well by these parameters, leading to similar unsatisfying results as summing up the features (see Table 9 in Appendix Section D.2).
Bi-level optimization. Without bi-level optimization, the feature fusion weights are jointly optimized with the model parameters on the training dataset. Its accuracy drops by 2.65% on average. This phenomenon is consistent with the observation in the NAS domain (Liu et al., 2018): training model parameters and feature fusion weights jointly on the same training set would cause over-fitting and thus poor generalization performance.
Feature Fusion Analysis. We measure the importance of the three graph features by computing the proportion for each of them after feature fusion. Formally, the importance of the features is computed by I s = πi Hs π1 Hego +π2 Hagg +π3 Hstrc , where s ∈ {ego, agg, strc} and · computes the averaged absolute value of a specific feature.
Figures 2a show the results on syn-cora. We could observe three dominant trends. (1) The importance of the ego-node features increases from close to around 0.05 to 0.8 as the homophily of a graph becomes lower. This indicates that the ego-node feature is a more reliable signal than other features for graphs with low homophily. (2) The importance of the aggregated neighborhood feature increases from 0.2 to 0.8 as the homophily increases, echoing the intuition that a node has similar properties to its neighbors on homophilic graphs. (3) All the features have a non-trivial importance score for graphs with homophily within 0.2 and 0.8 (which is common for real graphs). This indicates the importance of all the features in learning node embeddings, echoing insights from ablation study. One thing worth mentioning is, since the graph links in syn-cora are generated randomly, which means that the graph structure features cannot capture meaningful information from the adjacency matrix as we expected, it's hard to figure out the trend of this feature from Figure 2a. Figure 2b shows the results on real graphs. Since real graphs have different intrinsic graph properties, including the raw node features and the graph links, we cannot compare the changes in feature importance across graphs like what we did for syn-cora. Instead, we focus on comparing the importance of different features given specific graphs. Our observations are summarized as follows.
(2) For graphs with low to medium homophily (i.e., arXiv-year, penn94, and twitch-gamer), the graph structure features take the biggest proportion compared to the other two features, indicating the strong impact of this feature. It is consistent with our ablation study where removing the graph structure features causes the most severe accuracy drops. (3) The graph genius almost totally relies on ego-node features. We suspect that the reason is that its node features are sufficient to serve the node classification task. As shown in Table 2, applying MLP on the raw node feature already forms a strong baseline for this graph.

RELATED WORKS
Graph neural networks (GNNs) have achieved remarkable success on node classification tasks (Gao et al., 2018;Klicpera et al., 2018;Xu et al., 2018b;Wu et al., 2019). Many GNNs (Niepert et al., 2016;Hamilton et al., 2017;Monti et al., 2017;Veličković et al., 2017;Gao et al., 2018;Xu et al., 2018a;Wang et al., 2019) fall into the message passing framework (Gilmer et al., 2017;Battaglia et al., 2018), which iteratively transforms and propagate the messages from the spatial neighborhoods through the graph topology to update the embedding of a target node. To name a few, GCN (Kipf & Welling, 2016) designs a layer-wise propagation rule based on a first-order approximation of spectral convolutions on graphs. GraphSAGE (Hamilton et al., 2017) extends GCN by introducing a recursive node-wise sampling scheme to improve the scalability. Graph attention networks (GAT) (Veličković et al., 2017) enhances GCN with the attention mechanism (Vaswani et al., 2017). Later works (Gao et al., 2018;Xu et al., 2018a;Wang et al., 2019;Li et al., 2021;Zeng et al., 2021) try to design more expressive GCN variants by overcoming the over-smoothing problem of GCNs (Oono & Suzuki, 2019;Zhang et al., 2022). DeepGCN (Li et al., 2019) utilizes residual connections, dense connections, and dilated convolutions to build deeper GCNs for point cloud semantic segmentation. APPNP (Klicpera et al., 2018) leverages personalized PageRank to improve the propagation scheme. DAGNN  proposes to decouple the transformation and the propagation operation to increase receptive fields. However, most of the above-mentioned GNNs fail to achieve good performance on heterophilic graphs (Pei et al., 2020;Lim et al., 2021a) because they assume strong homophily in graphs.
Recent works start to pay attention to heterophilic graphs. MixHop (Abu-El-Haija et al., 2019) proposes a graph convolutional layer that utilizes multiple powers of the adjacency matrix to learn general mixed neighborhood information. H2GCN (Zhu et al., 2020) identifies three key designs, egoand neighbor-embedding separation, higher-order neighbors, and the combination of intermediate representations to boost the representation learning for heterophilic graphs. Generalized PageRank (GPR) GNN (Chien et al., 2020) adaptively controls the contribution of different propagation steps. LINKX (Lim et al., 2021a) separately embeds the adjacency matrix and the node features and then combines them with MLPs. GGCN (Yan et al., 2021) leverages two strategies, including degree correction for adjusting degree coefficients and signed messages for optionally negating the messages, to overcome the over-smoothing problem. Although many of these methods achieve better performance on heterophilic graphs, they achieve comparable, if not worse, accuracy on homophilic graphs than traditional message passing-based GNNs. In this paper, our goal is to design a GNN that can generalize well to the whole spectrum of homophily.

CONCLUSION
In this paper, we propose a graph neural network OGNN, which integrates three classes of graph features including the ego node feature, the aggregated neighborhood feature, and the graph structure feature. OGNN automatically handles graphs with different homophily via adaptive feature fusion and bi-level optimization. Extensive experiments show that OGNN achieves state-of-the-art accuracy performance compared with strong baselines on both synthetic datasets and real datasets covering the full graph homophily spectrum. Additional ablation studies further illustrate the necessity of the three aspects of the graph features and the proposed adaptive features fusion mechanism.

A REAL-WORLD DATASETS DETAILS
In our experiments, we use the following real-world datasets to evaluate our method and existing GNNs. The homophily of these datasets ranges from 0.222 ∼ 0.931. Table 4 summarizes the detailed dataset statistics.
Cora (Sen et al., 2008), CiteSeer (Sen et al., 2008), PubMed (Sen et al., 2008), and Coauthor CS & Physics (Shchur et al., 2018) have high edge homophily and are usually considered as homophilic graphs. For these graphs, we follow the data split in GCN (Kipf & Welling, 2016) and DAGNN . For Cora, CiteSeer, and PubMed, we randomly sample 20 nodes from each class as the train set, and sample 500 nodes from the rest as the validation set and 1000 nodes as the test set. For Coauthor CS & Physics, we randomly sample 20 nodes per class as the train set, 30 nodes per class as the validation set, and the rest nodes as the test set.
For all the datasets, we generate 5 random data splits for computing the average and standard deviation of the models' performance. The implementation of OGNN basically follows the model we described in Section 4.2, in which we omit some details for simplicity. The complete implementation details of OGNN are listed in Table 5. Before extracting the ego-node feature, the raw input node features are fed into a Dropout layer. In the aggregated neighborhood feature extraction, we reuse the intermediate results of different hops of neighbors to simplify the computation. For example, when computingÂ i Hego, we use the dot product ofÂ · (Â i−1 Hego) instead of computing the power ofÂ. Moreover, becauseÂ i−1 Hego has the same shape of Hego, computingÂ · (Â i−1 Hego) is always a sparse-dense matrix multiplication, which is more efficient than computing the power ofÂ. Similarly, we use the same strategy to compute Hstrc. Because we use the original adjacency matrix instead of a normalized one in structure feature extraction (for accuracy performance purposes), the magnitude of A j will grow exponentially with j increasing, which may cause the value out of range problem. Therefore, we utilize Batch Normalization layers to scale down the feature matrix after each adjacency matrix multiplication. In the feature fusion module, we dropout the fused features before activating it with ReLU.

B.2 TRAINING DETAILS
To implement our bi-level optimization training scheme, we utilize two optimizers to train the model parameters W and the feature fusion parameters P respectively. The model parameters W are trained with an Adam optimizer (Kingma & Ba, 2014) O1 on the training dataset. The learning rate and weight decay rate of O1 is decided by the hyper-parameter settings, which is described in Section C. On the other hand, the feature fusion parameters P are trained with another Adam optimizer O2 on the validation dataset with a fixed learning rate 0.01. We train P for 10 epochs after training W for every 20 epochs. When training P, we'll set the Dropout

C HYPER-PARAMETER SETTINGS
In our experiments, we use the hidden channels (d), the propagation steps for aggregated neighborhood feature extraction (s1), the power of the adjacency matrix for graph structure feature extraction (s2), the learning rate η, the weight decay λ, and the feature normalization (ν) as the hyper-parameters. For all the datasets, we perform grid search over the following hyper-parameter options: We also list the best hyper-parameter settings for all the real-world datasets in Table 6

D.1 DETAILED SYNTHEIC DATASET RESULTS
We list the detailed results of the experiments on the synthetic datasets in Table 7 and 8, which includes standard deviation of the accuracy performance compared to Table 1. Overall, OGNN outperforms the existing methods on most homophily settings with seven settings at top-1 and four at top-2, and pushes the best accuracy boundary for up to 2.76%. Table 9 shows the experimental results of using concatenation as feature fusion approach instead of summing up the features.