{'fraction_non_alphanumeric': 0.03376480308454971, 'fraction_numerical': 0.007821536766730927, 'mean_word_length': 4.856774193548387, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, '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}}
Revisiting Heterophily in Graph Convolution Networks by Learning Representations Across Topological and Feature Spaces

Graph convolution networks (GCNs) have been enormously successful in learning representations over several graph-based machine learning tasks. Specific to learning rich node representations, most of the methods have solely relied on the homophily assumption and have shown limited performance on the heterophilous graphs. While several methods have been developed with new architectures to address heterophily, we argue that by learning graph representations across two spaces i.e., topology and feature space GCNs can address heterophily. In this work, we experimentally demonstrate the performance of the proposed GCN framework over semi-supervised node classification task on both homophilous and heterophilous graph benchmarks by learning and combining representations across the topological and the feature spaces.


INTRODUCTION
Owing to their great capacity in node representation learning, graph convolutional networks (GCNs) have widely been adopted across numerous graph-based machine learning tasks ranging from graph classification [1], link prediction [2], recommendation systems [3], fault diagnosis [4], network embedding [5], and computer vision [6]. However, most of the existing methods are centered around the homophily assumption for semi-supervised node classification (SSNC) task, i.e, a pair of nodes tend to be connected if they are similar or alike. The homophilous assumption is mainly attributed to the recursive neighbourhood aggregation mechanism in GCNs wherein a node's representation is obtained from its neighbours which are likely to have the same label. Several works [7,8] advocate that GNNs are best suited to address homophily and are not suitable for heterophilous graphs and have designed new architectures to explicitly address heterophily in graphs. However, Ma et al. [9] have shown that there exist certain specific types of heterophily over which GCNs in their original form can show strong performance. As per [9], GCNs learn equivalent embeddings for nodes that share same neighbourhood distribution. Further, Wang et al. [10] studied the performance of multi-channel graph convolutional networks in obtaining the information from both topological and features space. In this work, we take a step further and demonstrate that by learning and fusing features from topological and feature spaces, GCNs can address heterophily in a more general sense, i.e., not restricted to any specific kind of neighbourhood distributions.
Homophily and heterophily in graphs. When the connected nodes in a graph have similar labels or properties, the graph is said to have homophily. Homophily is found in several real-world graphs such as friendship networks [11], political networks [12,13], citation networks [14] and others. When the connected nodes have different properties or labels, the graph is said to possess heterophily. The examples of heterophilous graphs include dating networks or molecular networks [7]. We observe that implicitly there is some sort of commonality within a heterophilous connections. Consider a dating network, where potential dates are more likely to be connected if they share common interest or hobbies. Similarly, in molecular or protein networks, different types of amino acids make up a protein based on their bio-chemical compatibility. In both these examples, the common attributes between nodes of different labels shows inherent homophily (commonality) in a heterophilous connection.
GCNs for heterophily. Following these observations, we argue that GCNs can show improved performance over heterophilous graphs if they can be modeled to identify these hidden commonalities within a heterophilous connection. In traditional GCNs, the node representation learning is guided solely by topology graphs. However, both network topology and node features offer holistic understanding for the graph representation learning. We cannot obtain accurate neighborhood information by solely considering the topological view as the node features are often smoothened out when the feature information is propagated over network topological structure. Also, GCNs in their original form fail to adaptively learn correlation information between topological and feature views [10]. In this work, we propose a multi-channel GCN framework that first extracts information individually from the topology and feature graph by using two separate GCN encoders and then uses another encoder to extract information common to both the spaces for the node classification task and apply this to address heterophily. Remember that the role of the common encoder is to fill in the missing information obtained from each of the individual spaces.

RELATED WORK
In this section, we briefly review the development of GCNs over the years and understand how they have been applied to address heterophily. Bruna et al. [15] designed the graph convolution operation in Fourier domain using graph Laplacian and Defferrard et al. [16] employed its Chebyshev expansion to improve the efficiency. Later, Kipf and Welling [17] simplified the convolution operation and proposed feature aggregation from the one-hop neighbors. After this, a plenty of variants like GraphSAGE [18], GAT [19], SGC [20], and GMNN [21]. were introduced. While they have have shown performance improvement over node classification, most of them have suffered due to inherent low-pass filtering of node features due to Laplacian smoothing. For a more detailed review on different vari-ants of GCNs, we refer the readers to [22,23]. Surprisingly, all these methods only use a single topology graph for node aggregation and fail to completely utilize the information from the feature space. A few methods like AM-GCN [10] have shown better performance by extracting embeddings from both topology graph and feature graph. However, these have mostly performed well on homophilous graphs. Several recent works have methods to address heterophily in graphs by re-designing or modifying model architectures such as Geom-GCN [24], H2GCN [7], GPR-GNN [25], and CPGNN [8]. Further, [9] has established that GCN can potentially achieve good performance on some specific types of heterophily in graphs. In this work, our focus is on understanding whether the information learned and fused across topological and feature graphs can be used to address heterophily in general.

Mathematical Preliminaries.
Let us consider an undirected graph G = (V, E) characterized by an adjacency matrix A, a diagonal degree matrix D ( A and D when self-loops are considered), N nodes, and a node feature matrix X ∈ IR N×d containing a d-dimensional feature vector for each node in the graph.
GCN Layer. A single GCN layer takes the form of H (l+1) = σ( PH (l) W (l) ), where H (l) and H (l+1) represent the input and output features of the l th layer, W (l) represents the parameter (weight) matrix that transforms features, and σ represents ReLU activation. Further, Homophily. The edge homophily ratio is defined as the fraction of edges that connect nodes with the same labels [9]. Mathematically, Here, Y is the set of all the node labels yi and 1(·) is an indicator function. 0.5 ≤ H(·) ≤ 1 corresponds to high homophily and 0 ≤ H(·) ≤ 0.5 corresponds to high heterophily.

Proposed Framework
The overall information flow in the proposed framework is shown in Figure 1. The main idea is to propagate the node features through both the topological and the feature space. We start with two 2layer GCN encoders Tenc and Fenc that take G = (H (0) , A) and to obtain the feature maps ZT and ZF corresponding to two views. Please note that G is the regular topological graph and G f is the knearest neighbour feature graph based on node feature matrix X and adjacency matrix A f of the k-NN graph. Further, each GCN layer is designed to have a residual connection to initial features H (0) (or X), as described in Equation 2.
Here, α = 0.8. We deploy a residual connection from the input features H (0) such that the final representation of each node retains at least a fraction of information (α) from the input features. This 3 We use cosine similarity to compute the similarity s ij between two node features x i and x j . s ij = x i .x j |x i ||x j | helps to slow down the rate of convergence of features to a point or smaller subspace -a common cause of oversmoothing in GCNs [26,27].
As discussed in Section 1, we learn the information with common characteristics between these two spaces. We deploy a common GCN encoder Cenc with shared parameter to learn the embeddings ZCT and ZCF which in turn are combined together to get the common embedding ZC using a multi-layer perceptron (MLP). However, unlike methods like AM-GCN [10], we use a weighted combination of the learned features (ZT and ZF ) and the initial features X as input to Cenc. Specifically, ZC in = ζH + (1 − ζ)Z Here, H = fMLP (H 0 ) and Z represents either ZT or ZF and we set ζ = 0.85 This formulation was found to provide performance improvement over just using the learned ZT or ZF .
With ZT , ZF , and ZC at hand, we now wish to find an optimal combination of these features that decides the final predicted labels, as governed by Equation 3.
Here, αT , αF , and αC are the feature-level attention weights for ZT , ZF , and ZC , respectively, such that α = f M LP (Z ) where ∈ {T, F, C}, f M LP is the corresponding MLP, and is the element-wise Hadamard product. Consequently, we obtain the final set of labels Y as shown in Equation 4.

Training Details
We train and evaluate the proposed framework over both homophilous and heterophilous graph datasets as listed in Table 1. Closeness Constraint. We want the two output embeddings ZCT and ZCF arising out of Cenc to be close as possible. Therefore, we apply a closeness constraint enabling to search for commonality. Following [10], we first obtain the similarity of N nodes as, Here, ZCT nor and ZCF nor are the L2-normalized version of ZCT and ZCF , respectively. Using these, we define the closeness constraint using the Frobenious norm, as shown in Equation 6.
Disparity Constraint. An input graph from the same view generates two representations, i.e., G → (ZT , ZCT ) and G f → (ZF , ZCF ). In order to ensure that they capture different information, we introduce a disparity regularization L d (similar to [5]) to enlarge distances between them using the negative cosine similarity, as described in Equation 7.
Classification Loss. Let Y be the one-hot encoded label matrix, Vtrain be the set of training nodes, and Y be the prediction, as defined in Equation 4. We minimize the standard cross-entropy loss to train the network.
The overall optimization objective function is as described in Equation 9. LT = λL cl + βLc + γL d Here, λ, β, and γ are the weights for the classification loss, closeness, and disparity constraints, respectively. 1

EXPERIMENTAL EVALUATION
In this section, we evaluate the proposed approach on homophilous and heterophilous graph datasets (see Table 1) and reason out several design choices. Please note that we have chosen high performing standard GCN variants and AM-GCN [10] for a fair comparison keeping in mind that our aim is to establish the ability of GCNs in addressing heterophily with any major change in its original formulation. All experiments have been performed with 40 labeled nodes per class. We find that this is a reasonable approximation of the real world scenario where we are less likely to provided with lots of labeled nodes.  Table 2 shows the performance of the proposed approach with the most recent and relevant baselines over six different graph datasets in terms of accuracy and the F1-score. We observe that the proposed framework either performs best or the second best among different baselines. It achieves relative improvements of around 3.78% (accuracy) and 4.61% (F1-score) averaged over the heterophilous datasets. Further, the proposed framework is observed to outperform GCN and kNN-GCN on nearly all the datasets. This indicates the effectiveness of extracting useful information from both the spaces rather than only from the topological space (as in GCN) or the feature space (as in kNN-GCN). Moreover, we find that GCN operating solely on a topology graph fails to provide better result than on a feature space graph. This is due to the inherent useful differences in information that each space carries, thus establishing the need of introducing feature space graph in GCN. Overall, the margin of improvement over heterophilous datasets is observed to be higher than that over the homophilous datasets. This establishes our claim that learning representation across topological and feature spaces does help in better addressing the heterophily. Network design choices We discuss the three important design choices in the proposed framework. (a) Initial Residual Connection:

Semi-supervised node classification
We observed an improvement of 2.14% (accuracy) and 3.09% (F1score) on an average by using initial residual connection (Equation 2) in GCNs versus vanilla GCN. (b). Feature-wise attention values: Owing to a better feature selectivity for node classification [27], we observed improved performance by learning feature-wise attention values (weighing each feature of every node) instead of just one attention value per node (as AM-GCN [10]). Finally, (c) Negative cosine similarity as disparity constraint: It speeds up (almost ×4) the training (and offers better performance) when compared to Hilbert-Schmidt Independence Crtierion (HSIC), as used in [10].  Table 2. Node classification results in terms of Accuracy and F1score across different real-world datasets. Best performance is reported in BOLD and second best performance is ("underlined"). Compute K, the number of heterophilous edges to added 5 Sample K nodes such that each node i ∼ U nif orm(V) 6 for i = 1 to K do

Effect of extent of heterophily
In this section, we attempt to understand the effect of variation in the extent of heterophily H over the model performance. We synthetically alter the topological graph G = (X, A) starting from the original heterophily hinit up-to 95% heterophily in all the six graph datasets as per Algorithm 1. Here, N = |V| and Vj is the set of nodes with label yj. Fig. 2. Effect of increasing heterophily on homophilous (first column) and heterophilous (second column) datasets. Figure 2 shows the performance variation with increasing heterophily. Each point on plot in Figure 2 represents the performance of the proposed framework on the generated graph corresponding to the heterophily value in x-axis with the first point denoting the original graph, i.e, K = 0. As depicted in Figure 2, as K increases (thus, the heterophily) the classification performance first decreases and then eventually begins to increase (except on the CORA dataset). This shows that the the proposed GCN framework can perform under higher heterophily as well. The shape of the curve is attributed to the "phase transition" where at the beginning the initial topology is disturbed by added edges making the topological space less informative. However, as we add more edges, the network adapts itself to look for heterophilous properties in the feature space and starts showing better performance. While this is similar to that observed in [9] for specific kind of heterophily, our framework applies to a general case by adapting itself to increasing heterophily. However, the performance on CORA dataset reduces as K increases. This can be attributed to the fact that randomly adding heterophilous edges to a highly homophilous graph can sometimes not be very meaningful and can turn out to be noisy, similar to adding an edge between nodes that are actually never related in real-world.

Analysis of attention values
In this section, we analyze the variation in attention values during the training process. The main idea is to get an understanding of how does the framework decide to choose between the information from topological and feature space under different extent of heterophily. Here, we consider ACM and Citeseer (homophilous) and Flickr and BlogCatalog (heterophilous) datasets for visualization. Since the attention maps (αT ), (αF ), and (αC ) are matrices, we first L2normalize them across rows and then compute the average of these row-wise norms. Figure 3 shows that at the beginning, the attention values (in the L2-norm sense) of topology (αT ), feature (αF ), and common (αC ) embeddings are almost the same. However, as the number of epochs increase, the attention values begin to differ. Specifically, for homophilous datasets (Figure 3, first column), (αT ) increases more than (αF ) and vice-versa for the heterophilous datasets ( Figure 3, second column). Following these observations, we see that for homophilous datasets, the framework focuses more on information from the topological space and that on the feature space over heterophilous datasets. The information from both the spaces augment network learning by adaptively assigning appropriate attention values to information from each space and perform well on both homophilous and heterophilous datasets.

CONCLUSION
We explore the ability of GCN in fusing information from network topological and feature space, and additionally address heterophily in graphs. While there is a method that shows GCNs in their original form addressing certain specific type of heterophily, others have advocated that GCNs are implicitly designed with homophily in mind. Further, they have not been suitable for heterophilous graphs unless their architectures are modified and redesigned specifically to address heterophily. We have shown that the proposed framework is able to handle heterophily across different real-world datasets with varied amount of heterophily not restricted solely to certain specific types. In the near future, we would like to explore whether such a multi-channel framework can be used to predict the missing node features in a graph and extend to dynamic graphs.