SIGMA: Similarity-based Efficient Global Aggregation for Heterophilous
  Graph Neural Networks
Graph neural networks (GNNs) realize great success in graph learning but
suffer from performance loss when meeting heterophily, i.e. neighboring nodes
are dissimilar, due to their local and uniform aggregation. Existing attempts
of heterophilous GNNs incorporate long-range or global aggregations to
distinguish nodes in the graph. However, these aggregations usually require
iteratively maintaining and updating full-graph information, which limits their
efficiency when applying to large-scale graphs. In this paper, we propose
SIGMA, an efficient global heterophilous GNN aggregation integrating the
structural similarity measurement SimRank. Our theoretical analysis illustrates
that SIGMA inherently captures distant global similarity even under
heterophily, that conventional approaches can only achieve after iterative
aggregations. Furthermore, it enjoys efficient one-time computation with a
complexity only linear to the node set size $\mathcal{O}(n)$. Comprehensive
evaluation demonstrates that SIGMA achieves state-of-the-art performance with
superior aggregation and overall efficiency. Notably, it obtains 5$\times$
acceleration on the large-scale heterophily dataset \emph{pokec} with over 30
million edges compared to the best baseline aggregation.
Haoyu Liu, Ningyi Liao, Siqiang Luo
# SIMGA: A Simple and Effective Heterophilous Graph Neural Network with Efficient Global Aggregation

###### Abstract

Graph neural networks (GNNs) realize great success in graph learning but suffer from performance loss when meeting heterophily, i.e. neighboring nodes are dissimilar, due to their local and uniform aggregation. Existing attempts in incorporating global aggregation for heterophilous GNNs usually require iteratively maintaining and updating full-graph information, which entails \(\mathcal{O}(n^{2})\) computation efficiency for a graph with \(n\) nodes, leading to weak scalability to large graphs. In this paper, we propose SIMGA, a GNN structure integrating SimRank structural similarity measurement as global aggregation. The design of SIMGA is simple, yet it leads to promising results in both efficiency and effectiveness. The simplicity of SIMGA makes it the first heterophilous GNN model that can achieve a propagation efficiency near-linear to \(n\). We theoretically demonstrate its effectiveness by treating SimRank as a new interpretation of GNN and prove that the aggregated node representation matrix has expected grouping effect. The performances of SIMGA are evaluated with 11 baselines on 12 benchmark datasets, usually achieving superior accuracy compared with the state-of-the-art models. Efficiency study reveals that SIMGA is up to 5\(\times\) faster than the state-of-the-art method on the largest heterophily dataset _pokec_ with over 30 million edges.

## 1 Introduction

Graph neural networks (GNNs) have recently shown remarkable performance in graph learning tasks [1; 2; 3; 4; 5; 6; 7]. Despite the wide range of model architectures, traditional GNNs [1] operate under the assumption of _homophily_, which assumes that connected nodes belong to the same class or have similar attributes. In line with this assumption, they employ a uniform message-passing framework to aggregate information from a node's local neighbors and update its representations accordingly [8; 9; 10]. However, real-world graphs often exhibit _heterophily_, where linked nodes are more likely to have different labels and dissimilar features [11]. Conventional GNN approaches struggle to achieve optimal performance in heterophily scenarios because their local and uniform aggregations fail to recognize distant, similar nodes and assign distinct weights for the ego node to aggregate features from nodes with the same or different labels. Consequently, the network's expressiveness is limited [12].

To apply GNNs in heterophilous graphs, several recent works incorporate long-range connections and distinguishable aggregation mechanisms. Examples of long-range connections include the amplified multi-hop neighbors [13], and the geometric criteria to discover distant relationships [14]. The main challenge in such design lies in deciding and tuning proper neighborhood sizes for different graphs to realize stable performance. With regard to distinguishable aggregations, Yang et al. [15] and Liu et al. [16] exploited attention mechanism in a whole-graph manner, while Jin et al. [17] and Li et al. [18] respectively considered feature Cosine similarity and global homophily correlation. Nonetheless, the above approaches require iteratively maintaining and updating a large correlation matrix for all node pairs, which entails \(\mathcal{O}(n^{2})\) computation complexity for a graph of \(n\) nodes, leading to weak scalability. In the state-of-the-art method GloGNN++ [18], the complexity of global aggregation
can be improved to \(\mathcal{O}(m)\) with extensive algorithmic and architectural optimizations, where \(m\) is the number of edges. However, \(\mathcal{O}(m)\) can still be significantly larger than \(\mathcal{O}(n)\). In summary, the existing models, while achieving promising effectiveness in general, suffer from efficiency issues due to the adoption of the whole-graph long-range connections.

Addressing the aforementioned challenges calls for a global node-similarity metric with two properties. First, a high degree of similarity should indicate a high likelihood of having the same label, particularly when the nodes also entail similar attributes. Second, the computation of pair-wise similarity can be approximated efficiently. For the first property, Suresh et al. [19] suggested that nodes surrounded with similar graph structures are likely to share the same label. Hence, the property boils down to the computation of similarity between the nodes regarding their surrounding graph structure. This insight motivates us to incorporate SimRank [20] into Graph Neural Networks (GNNs) to facilitate global feature aggregation. SimRank is defined based on an intuition that two nodes are similar if they are connected by similar nodes. Hence, nodes with high SimRank scores indicate that they reside within similar sub-structures of the graph. For instance, in an academic network illustrated in Figure 1(c), two professors from the same university are likely to belong to the same category (i.e., possess the same label) because they are connected to similar neighbors, such as their respective students in the university. Furthermore, this similarity propagates recursively, as the students themselves are similar due to their shared publication topics. To examine the effectiveness of SimRank in capturing the pairwise label information, we further conduct empirical evaluation as shown in Figure 1 (a) and (b). In contrast to traditional neighbor-based local aggregation (Figure 1(a)), SimRank succeeds in discovering distant nodes with the same labels as the center node (Figure 1(b)). In heterophilous graphs, this property is especially useful for recognizing same-label nodes which may be distant. As we will show in Theorem 3.3, we further theoretically derive a novel interpretation between SimRank and GNN that, the SimRank score is exactly the inner product of node embeddings output by a converging GNN, which reveals the ability of SimRank's global aggregation expressiveness. SimRank is also desired for the second property for its high computational efficiency. As we will show in Proposition 3.7, the SimRank matrix can be efficiently computed beforehand in near \(\mathcal{O}(d^{2})\) time for average degree \(d\), where \(d^{2}\) is significantly smaller than \(n\) for all the datasets that are commonly used.

Putting the ideas together, we propose **SIMGA1**, a heterophilous GNN model that can effectively capture distant structurally similar nodes for heterophilous learning, while achieving high efficiency by its one-time global aggregation whose complexity is only near-linear to the number of graph nodes \(n\). To the best of our knowledge, we make the first attempt of developing an inherent relationship between SimRank structural similarity and a converging GNN, as well as integrating it into GNN designs to achieve high efficacy. Benefiting from its expressiveness attribute, SIMGA enjoys a simple model architecture and efficient calculation. Its simple feature transformation also brings fast inference and scalability to large graphs. Experiments demonstrate that our method achieves \(5\times\) speed-up over the state-of-the-art GloGNN++ [18] on the _pokec_ dataset, currently the largest heterophily dataset with 30 million edges.

Footnote 1: SIMGA, **SIMRank** based **GNN** Aggregation.

We summarize our main contributions as follows: (1) We demonstrate that SimRank can be seen as a new interpretation of GNN aggregation. Based on the theory, we propose SIMGA, utilizing SimRank as the measure to aggregate global node similarities for heterophilous graphs. (2) We demonstrate

Figure 1: **(a) Neighborhood-based local aggregation and (b) SimRank aggregation on _Texas_ heterophily graph.** Node color represents aggregation score with respect to the center node (\(\blacktriangle\) in orange). Conventional aggregation focuses on nearest nodes regardless of node label, while SimRank succeeds in assigning high values for nodes with same label (\(\blacktriangle\) in blue). **(c) Simrank illustration on a social network.** Two professors inherit high similarity because they share similar neighbors.
SIMGA's effectiveness by proving the grouping effect of generated node embedding matrix and design a simple but scalable network architecture that simultaneously realizes effective representation learning and efficient computation, which incorporates near-linear approximate SimRank calculation and fast computation on million-scale large graphs. (3) We conduct extensive experiments to show the superiority of our model on a range of datasets with diverse domains, scales, and heterophilies. SIMGA achieves top-tier accuracy with \(5-10\times\) faster computation than the best baseline.

## 2 Preliminaries

**[Notations].** We denote an undirected graph \(G=(V,E)\) with node set \(V\) and edge set \(E\). Let \(n=|V|\), \(m=|E|\) and \(d=m/n\), respectively. For each node \(v\), we use \(N(v)\) to denote node \(v\)'s neighborhood, i.e. set of nodes directly link to \(v\). The graph connectivity is represented by the adjacency matrix as \(A\in\mathbb{R}^{n\times n}\), and the diagonal degree matrix is \(D\in\mathbb{R}^{n\times n}\). The input node feature matrix is \(F\in\mathbb{R}^{n\times f}\) and we denote \(Y\in\mathbb{R}^{n\times k}\) the ground truth node label one-hot matrix, where \(f\) is the feature dimension and \(N_{y}\) is the number of labels in classification.

**[Graph Neural Network].** Graph neural network is a type of neural networks designed for processing graph data. We summarize the key operation in GNNs into two steps: Firstly, aggregating local representations: \(\hat{h}_{u}^{(l)}=\textit{AGG}(\{h_{v}^{(l)}:\forall v\in N(u)\})\). Then, combining the aggregated information with ego node to update its embeddings: \(h_{u}^{(l+1)}=\textit{UPD}(h_{u}^{(l)},\hat{h}_{u}^{(l)}),\) where \(h_{u}^{(l)}\) denotes the embeddings of node \(u\) generated by the \(l\)-th layer of network. For a model of \(L\) layers in total, the final output of all nodes form the embedding matrix \(H^{(L)}\), which can be fed to higher-level modules for specific tasks, such as a classifier for node label prediction. _AGG_(\(\cdot\)) and _UPD_(\(\cdot\)) are functions specified by concrete GNN models. For example, GCN [8], representing a series of popular graph convolution networks, uses _sum_ function for neighbor aggregation, and updates the embedding by learnable weights together with _ReLU_ activation.

**[Graph Heterophily and Homophily].** The heterophily and homophily indicate how similar the nodes in the graph are to each other. Typically, in the context of this paper, it is mainly determined by the node labels, i.e., which category a node belongs to. The homophily of a graph can be measured by metrics like node homophily [14] and edge homophily [11]. Here we employ node homophily defined as the average proportion of the neighbors with the same category of each node:

\[\mathcal{H}_{node}=\frac{1}{|V|}\sum\limits_{v\in V}\frac{|\{u\in N(v):y_{u}=y _{v}\}|}{|N(v)|}. \tag{1}\]

\(\mathcal{H}_{node}\) is in range \((0,1)\) and homophilous graphs have higher \(\mathcal{H}_{node}\) values closer to 1. Generally, high homophily is correlated with low heterophily, and vice versa.

**[SimRank]** SimRank holds the intuition that two nodes are similar if they are connected by similar neighbors, described by the following recursive formula [20]:

\[S(u,v)=\begin{cases}1&(u=v)\\ \frac{c}{|N(u)||N(v)|}\sum\limits_{u^{\prime}\in N(u),v^{\prime}\in N(v)}S(u^{ \prime},v^{\prime})&(u\neq v)\end{cases}, \tag{2}\]

where \(c\in(0,1)\) is a decay factor emperically set to 0.6. Generally, a high SimRank score of node pair \(u,v\) corresponds to high structural similarity, which is beneficial for detecting similar nodes.

## 3 Simga

In this section, we first elaborate on our intuition of incorporating SimRank as a novel GNN aggregation by presenting the new interpretation between SimRank and GNN. Then we propose our SIMGA model design and analyze its scalability and complexity.

### Interpreting SimRank in GNN

In graphs with node heterophily, neighboring nodes usually belong to different categories. Their feature distributions also diversify. Such disparity prevents the model to aggregate information from neighbors that is meaningful for predictive tasks such as node classification [11]. Consequently, local uniform GNN aggregation produces suboptimal results for smoothing local dissimilarity, i.e. heterophilous representations of nodes in a few hops, failing to recognize intra-class node pairs distant [21; 22]. On the contrary, it is inferred from Eq. (2) that, SimRank is defined for any given node pairs in the graph and is calculated by recognizing whole-graph structural information. Even for long distances, SimRank succeeds in assigning higher scores to structurally similar node pairs and
extracts relationships globally. We validate the ability of SimRank for aggregating global homophily in Figure 2, where frequencies of the SimRank score of node pairs in six graphs are displayed. It is clearly observed that similarity values for intra-class node pairs are significantly higher than those of inter-class ones, which is useful for the model to recognize information from homophily nodes.

To theoretically analyze the utilization of SimRank as GNN global aggregation, we further explore the association between SimRank and GNN. First we look into the concept of random walk:

**Definition 3.1** (_Pairwise Random Walk_[20]).: The pairwise random walk measures the probability that two random walks starting from node \(u\) and \(v\) simultaneously and meet at the same node \(x\) for the first time. The probability of such random-walk pairs for all tours \(t^{(2l)}\) with length \(2l\) can be formulated by:

\[P_{pair}(u,v|t^{(2l)})=\sum_{t^{(2l)}_{u:v}}P_{pair}(u,v|t^{(2l)}_{u:v})=\sum_ {x\in V}p(x|u,t^{(l)}_{u:x})\cdot p(x|v,t^{(l)}_{v:x}), \tag{3}\]

where \(t^{2l}_{u:v}\) is one possible tour of length \(2l\), \(t^{l}_{v:x}:\{v,...,x\}\) is the sub-tour of length \(l\) compositing the total tour, and \(p(x|v,t^{(l)}_{v:x})\) denotes the probability a random walk starting from node \(v\) and reaching at node \(x\) under the tour \(t^{(l)}_{v:x}\).

Since random walk visits the neighbors of the ego node with equal probability, \(p(x|v,t^{(l)}_{v:x})\) can be trivially calculated as: \(p(x|v,t^{(l)}_{v:x})=\prod_{w_{i}\in t_{v:x}}\frac{1}{|N(w_{i})|},\) where \(w_{i}\) is the \(i\)-th node in tour \(t^{(l)}_{v:x}\). Generally, a higher probability of such walks indicates a higher similarity between the source and end nodes. Pairwise random walk paves a way for node pair aggregation that can be calculated globally, compared to conventional GNN aggregation that is interpreted as random walks with limited hops, which is highly local [10; 23]. In fact, we will later show that random walk probability can be seen as GNN embeddings. In this paper, we especially consider the SGC-like architecture for representative GNN aggregation [24]. For each layer the _AGG_ and _UPD_ operation are accomplished by a 1-hop neighborhood propagation, and the node features are only learned before or after all layers. In other words, each intermediate layer can be written in the matrix form as \(H^{(l+1)}=\mathcal{L}H^{(l)}\), where \(\mathcal{L}=D^{-1}A\) denotes the graph Laplacian matrix. For other typical GNN architectures such as GCN and APPNP, similar expressions also exist [22]. We hereby present the next lemma, linking random walk and such network embeddings:

**Lemma 3.2**.: _(See Appendix B.1 for proof). For any \(l\geq 0\) and node-pair \(u,v\in V\), the probability of length-\(l\) random walk under all tour \(t^{(l)}\) equals to the \(l\)-th layer embedding value \(h^{(l)}_{u}[v]\) of node \(u\):_

\[h^{(l)}_{u}[v]=p(v|u,t^{(l)}_{u:v}).\]

Lemma 3.2 states that an \(l\)-layer GNN is able to simulate \(l\)-length random walks and its embedding contains the information of the each node's reaching possibility. This conclusion is in line with other studies and displays the expressiveness of GNN in graph learning [10; 24; 22]. Based on the connection, we investigate a GNN mapping function \(\mathcal{G}\) stacking multiple SGC layers. We are specifically interested in the case when network converges to infinity layers \(L\rightarrow\infty\), denoted as \(\mathcal{G}^{(\infty)}\). We derive SimRank as the novel interpretation of such GNN model in the following theorem:

**Theorem 3.3**.: _(See Appendix B.2 for proof). On a graph \(G=(V,E)\), the SimRank matrix calculated by Eq. (2) is \(S\). Then, the SimRank value \(S(u,v)\) of node-pair \(u,v\in V\) is equivalent to the layer-wise

Figure 2: **Distribution of SimRank scores over intra-class and inter-class node pairs. X-axis denotes the logged value for each SimRank score corresponding to one node pair and Y-axis reflects the density (frequency). Note that we filter values which are trivial, i.e. near zero.**
summation of inner-product of network \(\mathcal{G}^{(\infty)}\) node representations \(h_{u}^{(l)},h_{v}^{(l)}\), with a decay factor \(c\):_

\[S(u,v)=\sum_{l=1}^{\infty}\ c^{l}\cdot\langle h_{u}^{(l)},h_{v}^{(l)}\rangle, \tag{4}\]

_where \(h_{u}^{(l)}\) is node \(u\) embedding generated by \(l\)-th layer of \(\mathcal{G}^{(\infty)}\), and \(\langle\cdot\,\ \cdot\rangle\) denotes the inner product._

### SIMGA Workflow

The implication of Theorem 3.3 is that, by calculating the SimRank matrix, it naturally retrieves the information that common GNN architectures can only represent after a number of local aggregations. As SimRank assigns high scores to node relations with topological similarities, it can be regarded as a powerful global aggregation for GNN representation, guiding the network to put higher weights on such distant but homophilous node pairs. Hence, our goal is to design effective and efficient model architecture that exploits the desirable capability of SimRank.

Considering SimRank already carries global similarity information implicitly, our model removes the need of iteratively aggregating and updating embeddings by incorporating the similarity matrix such as [17; 18]. Instead, we employ a precomputation process to acquire the SimRank matrix \(S\) and only apply it once as model aggregation. Since the aggregation is as straightforward as a matrix multiplication, we establish the simple but effective transformation scheme to concatenate and learn node attributes and local adjacency. In a nutshell, the architecture of SIMGA is summarised as:

\[Z_{Sim}=\textit{SoftMax}(S\cdot f_{\theta}(F,A)), \tag{5}\]

where \(f_{\theta}\) is a mapping function to transform features \(F\) and adjacency \(A\) into node embeddings. Here \(S\) plays the role of final and global aggregation which gather information for all nodes according to the SimRank scores as weights. To further explain why SIMGA is effective, we mark that SIMGA in the form of Eq. (5) shares a similar idea to the representative message-passing model APPNP [10], whereas the latter follows a local propagation according to the Personalized PageRank matrix \(\Pi\), while ours spotlights \(S\) for global similarity measure in heterophilous settings. As a natural merit, our SIMGA satisfies various advantages of decoupled GNN models like APPNP, ranging from batch computation to scalability on large graphs.

In specific, SIMGA firstly uses two _MLPs_ to embed node feature matrix and adjacency matrix respectively. Then, it linearly combines them with the tunable parameter \(\delta\in[0,1]\), namely the feature factor, after which the concatenation is fed into a main _MLP_ network:

\[H_{F}=\textit{MLP}_{F}(F),\ H_{A}=\textit{MLP}_{A}(A);\qquad H=\textit{MLP} _{H}\big{(}\delta\cdot H_{F}+(1-\delta)\cdot H_{A}\big{)}, \tag{6}\]

where \(H_{F}\in\mathbb{R}^{n\times N_{y}}\) and \(H_{A}\in\mathbb{R}^{n\times N_{y}}\) represents the intermediate embeddings of feature and adjacency, \(H\in\mathbb{R}^{n\times N_{y}}\) is the main node embedding, and \(N_{y}\) is the number of categories. Then to conduct SimRank aggregation, we apply the score matrix \(S\) to the main embedding as \(S\cdot H\). Referencing the common approach in Klicpera et al. [10], we adopt skip connection with tunable parameter \(\alpha\in[0,1]\) to balance global aggregation and raw embeddings:

\[Z=(1-\alpha)\cdot S\cdot H+\alpha\cdot H. \tag{7}\]

We depict the model architecture in Appendix C and next we explain the expressiveness of SIMGA.

### Grouping Effect

If two nodes \(u,v\) share similar attributes and graph structures, their characterizations from other nodes are supposed to be close. This derives the formal definition of grouping effect as follow:

**Definition 3.4**.: [_Grouping Effect [25]_] Given the node set \(V\), two nodes \(u,v\in V\) and \(u\)-th row of \(A^{k}\) and \(F\) as \(a_{u}^{k}\) and \(x_{u}\) respectively, let \(u\mathrel{\hbox to 0.0pt{\hbox{\kern-2.0pt\lower 4.0pt\hbox{$\sim$}}} \raisebox{0.0pt}{$>$}}v\) denote the conditions that (1) \(||f_{u}-f_{v}||_{2}\to 0\) and (2) \(||a_{u}^{k}-a_{v}^{k}||_{2}\to 0\), \(\forall k\in[1,K]\). A matrix \(Z\) is said to have grouping effect if condition below meets:

\[u\to v\Rightarrow\forall p\in V,\ \ |Z(u,p)-Z(v,p)|\to 0. \tag{8}\]

Equipped with approximated matrix \(S\), we demonstrate the effectiveness of SIMGA as follow:

**Theorem 3.5**.: _(See Appendix B.3 for proof). Matrices \(Z\) and \(H\) both have grouping effect when \(K>log_{c}\epsilon\approx 4\), where \(\epsilon\) denotes the absolute error for approximately calculating \(S\)._

The grouping effect of \(Z\) sufficiently demonstrates the effectiveness of SIMGA, that for two nodes regardless of their distance, if they share similar features and graph structures, their aggregated representations will be similar. Besides, for inter-class nodes, due to the low or near zero coefficients assigned by aggregation matrix \(S\), their combined representations will hence be different. In a nutshell, SIMGA is capable of handling heterophily graphs due to the distinguishable aggregation.
### Scalability & Complexity

Examining the respective stages of SIMGA, operations with dominant computation include the calculation on SimRank matrix \(S\) and the final aggregation of \(S\cdot H\). Without optimization, calculating matrix \(S\in\mathcal{R}^{n\times n}\) based on Eq. (2) in a recursive way requires \(\mathcal{O}(Tn^{2}d^{2})\) time and \(\mathcal{O}(n^{2})\) space, where \(T\) is the number of iterations and \(d\) is the average degree of each node. In addition, the aggregation \(S\cdot H\) also needs a computation time of \(\mathcal{O}(N_{y}n^{2})\). This is inapplicable to graphs with large amount of nodes. Luckily, SimRank can be calculated really efficiently [26].

```
Input: Graph \(G\), decay factor \(c\), error threshold \(\epsilon\) Output: Approximate SimRank matrix \(\hat{S}\)
1\(S\gets 0\), \(R\gets I\)
2while\(\max_{(u,v)}R(u,v)>(1-c)\epsilon\)do
3\(\hat{S}(v,v)\leftarrow\hat{S}(v,v)+R(u,v)\)
4for\(\textbf{d}^{\prime}\in N(u),v^{\prime}\in N(v)\)do
5\(R(u^{\prime},v^{\prime})\gets R(u^{\prime},v^{\prime})+c\cdot\frac{R(u,v)} {N(u^{\prime}):|N(v^{\prime})|}\)
6\(\overline{R}(u,v)\gets 0\)
7return matrix \(\hat{S}\)
```

**Algorithm 1** Localpush [27]

To solve above limitations, we first use the Localpush [27], one state-of-the-art all-pair SimRank computation algorithm with accuracy guarantee to speed up the calculation process. Its pseudo code is shown in Algorithm 1 and has the following approximation guarantee:

**Lemma 3.6** ([27]).: _Algorithm 1 returns an approximate SimRank matrix \(\hat{S}\) in \(\mathcal{O}(\frac{d^{2}}{c(1-c)^{2}\epsilon})\) time and holds that \(\|\hat{S}-S\|_{max}<\epsilon\)._

The accuracy of the approximate SimRank matrix is bounded by the parameter \(\epsilon\) which is usually a constant representing absolute error threshold. Thus, the computation time of \(S\), which is \(\mathcal{O}(\frac{d^{2}}{c(1-c)^{2}\epsilon})\), becomes practical. Further, to reduce memory overhead of the SimRank matrix, we sparsify the matrix by utilizing top-\(k\) pruning to select the \(k\)-largest scores for each node as utilized in [28]. This helps to reduce the space cost from at most \(\mathcal{O}(n^{2})\) to \(\mathcal{O}(kn)\), where \(k\) is the number of values selected in top-\(k\) pruning. By utilizing the pruned matrix, the aggregation by multiplying \(S\) is also reduced to \(\mathcal{O}(N_{y}kn)\). The other parts of SIMGA are all based on matrix multiplication. In Eq. (6), the computation complexities for \(H_{F}\), \(H_{A}\) and \(H\) are \(\mathcal{O}(N_{y}fn)\), \(\mathcal{O}(dfn)\) and \(\mathcal{O}(N_{y}^{2}n)\), respectively. Combining them together, we derive the time complexity of SIMGA as follows:

**Proposition 3.7**.: _The total time complexity of SIMGA is \(\mathcal{O}(\frac{d^{2}}{c(1-c)^{2}\epsilon}+c_{1}n)\), where \(c_{1}=kN_{y}+N_{y}f+df+N_{y}^{2}\ll n\)._

Based on Proposition 3.7, we conclude that SIMGA with such optimization achieves a near-linear time complexity to node numbers \(n\), where \(\mathcal{O}(\frac{d^{2}}{c(1-c)^{2}\epsilon})\) is insignificant when \(d\ll\sqrt{n}\) and \(\epsilon\sim 10^{-1}\). In Table 1, we compare the complexity of our SIMGA with heterophily GNNs regarding the cost of linking global connections in one hidden layer.

## 4 Related Work

GNNs achieve great advances and they usually root in graph manipulations and develop a variety of explicit designs surrounding aggregation and update schemes for effectively retrieving graph information [29; 30; 22]. GCN [8] mimics the operation in convolutional neural networks by summoning information from neighboring nodes in graphs and achieves larger receptive fields by stacking multiple layers. GCNII [31] chooses to stack network layers for a deeper model and further aggregation. GAT [9] exploits the attention mechanism for a more precise aggregation, while Mixhop [13] assigns weights to multi-hop neighbors. GraphSAGE [2] enhances the aggregation by sampling neighborhood and reduces computational overhead. APPNP [10] and SGC [24] decouple the network update by a separated local aggregation calculation and a simple feature transformation. Following works [32; 33; 34; 35] extend the design on scalability and generality.

Latest works notice the issue of graph heterophily and the limited capability of conventional GNNs. Zheng et al. [12] pointed out such limitation is due to that local neighbors are unable to capture informative nodes at a large distance. In addition, a uniform aggregation schema ignores the implicit difference of edges. Approaches addressing this heterophilous graph learning task can be mainly divided into two aspects. Some studies propose diverse modifications to widen the concept of local aggregation. H\({}_{2}\)GCN [11] and WRGAT [19] establish new connections between graph nodes,

\begin{table}
\begin{tabular}{|c|c|} \hline
**Methods** & **Time Complexity** \\ \hline \hline Gcom-GCN[14] & \(\mathcal{O}(|R|inmf)\) \\ GPNN[15] & \(\mathcal{O}(nmf)\) \\ U-GCN[17] & \(\mathcal{O}(n^{2}f)\) \\ WR-GAT[19] & \(\mathcal{O}(|R|n^{2}f)\) \\ GloGNN++[18] & \(\mathcal{O}(mf)\) \\ SIMGA & \(\mathcal{O}(\textbf{knf})\) \\ \hline \end{tabular}
\end{table}
Table 1: **Time complexity comparison with one hidden layer as an example.**
while GGCN [36] and GPR-GNN [37] alternate the aggregation function to allow negative influence from neighboring nodes. Another series of models choose to rethink locality and introduce global information, including global attention [15; 16] and similarity measurement Jin et al. [17]. Especially, LINRX [38] and GloGNN++ [18] both employ feature-topology decoupling and simple MLP layers for embedding updates. We highlight the uniqueness of SIMGA to all the above works for its global aggregation incorporating the well-defined topological similarity.

## 5 Experiments

We comprehensively evaluate the performance of SIMGA, including classification accuracy as well as precomputation and training efficiency. We also provide a specific study on embedding homophily for aggregating similar nodes globally. More details can be found in Appendix.

### Experiment Setup

**Baselines** We compare SIMGA with 11 baselines, including: (1) general graph learning models: MLP, GCN [8], GAT [9], Mixhop [13], and GCNII [31]; (2) graph convolution-based heterophilous models: GGCN [36], H\({}_{2}\)GCN [11], GPR-GNN [37] and WRGAT [19]; (3) decoupling heterophilous models: LINRX [38] and GloGNN++ [18].

**Parameter Settings** We calculate exact SimRank score for small datasets, while adopting approximation in Section 3.4 with \(\epsilon=0.1\) and \(k=1024\), which is sufficient to derive excellent aggregation coefficients (see Section 5.4). The decay factor \(c=0.6\) and \(\alpha=0.5\) on all the datasets. The layer number of _MLP\({}_{H}\)_ is set to 1 and 2 for small and large datasets. We use the same dataset train/validation/test splits as in Pei et al. [14] and Liu et al. [16]. We conduct 5 and 10 repetitive experiments on the small and large datasets, respectively. Exploration on parameters including feature factor \(\delta\), learning rate \(r\), dropout \(p\) and weight decay are elaborated in Appendix E and H.

### Performance Comparison

We measure our SIMGA's performance against 11 baselines on 12 benchmark datasets of both small and large scales as Table 2, where we also rank and order the models based on respective accuracy. We stress the effectiveness of SIMGA by concluding the following observations:

\(\bullet\) Common graph learning models generally perform worse. Among MLP, GAT, and GCN, GCN achieves the highest ranking 7.25 over all datasets. The reason may be that they fail to distinguish the homophily and heterophily nodes due to the uniform aggregation design. It is surprising that MLP only utilizing node features learns well on some datasets such as _Texas_, which indicates that node features are important in heterophilous graphs' learning. Meanwhile, Mixhop and GCNII generally hold better performance than the plain models. On _pokec_, the accuracy for Mixhop and GCNII are 81.07 and 78.94, outperforming the former three models significantly. They benefit from strategies considering more nodes in homophily and combine node representations to boost the performance, showing the importance of modifying the neighborhood aggregation process.

\(\bullet\) With respect to heterophilous models, those graph convolution-based approaches enjoy proper performance on small graphs by incorporating structural information, but their scalability is a

\begin{table}
\begin{tabular}{l|c c c c c c c c c c c c} \hline \hline  & \multicolumn{4}{c}{**Small Scale Datasets**} & \multicolumn{4}{c}{**Large Scale Datasets**} \\ \cline{2-13}  & **Texas** & **Cleester** & **Cleester** & **Cleester** & **Cleester** & **Combation** & **Pubanned** & **Squirrel** & **graphics** & **arXiv-year** & **Panual** & **twide-guares** & **snap-patations** & **polace** \\ \hline
**Categories** & 5 & 6 & 7 & 5 & 3 & 5 & 2 & 5 & 2 & 2 & 5 & 2 \\
**Nodes** & 183 & 3.327 & 2.308 & 2.277 & 19.171 & 5.201 & 42.961 & 109.343 & 41.554 & 168.114 & 2.9232 & 1.6328 & **Rank** \\
**Edges** & 295 & 4.65 & 5.278 & 31.421 & 44.327 & 198.403 & 998.979 & 1.1663 & 1.3823 & 1.8229 & 6.7937 & 1.3957 & 7.886 & 0.8225 & 5.064 \\
**Patterns** & 1,030 & 7.303 & 1.433 & 2.235 & 50 & 2.009 & 12 & 128 & 5 & 7 & 20 & 65 & \\
**Methods** & 0.11 & 0.74 & 0.61 & 0.23 & 0.40 & 0.22 & 0.61 & 0.22 & 0.47 & 0.54 & 0.07 & 0.44 & 0.44 \\ \hline MLP & 80.81 \(\pm\) 4.75 & 74.02 \(\pm\) 1.90 & 75.69 \(\pm\) 2.00 & 46.23 \(\pm\) 2.90 & 87.16 \(\pm\) 0.37 & 27.71 \(\pm\) 1.66 & 86.68 \(\pm\) 0.09 & 36.70 \(\pm\) 0.21 & 73.61 \(\pm\) 0.40 & 60.32 \(\pm\) 0.07 & 31.34 \(\pm\) 0.05 & 62.37 \(\pm\) 0.05 & 9.75 \\ GAT & 52.16 \(\pm\) 4.68 & 75.65 \(\pm\) 1.21 & 37.30 \(\pm\) 1.10 & 60.26 \(\pm\) 2.06 & 86.33 \(\pm\) 0.48 & 40.72 \(\pm\) 1.58 & 55.80 \(\pm\) 0.37 & 60.65 \(\pm\) 0.51 & 85.38 \(\pm\) 0.55 & 98.99 \(\pm\) 4.12 & 45.57 \(\pm\) 0.04 & 17.77 \(\pm\) 6.18 & 8.58 \\ WRGAT & 80.62 \(\pm\) 5.50 & 78.81 \(\pm\) 8.50 & 83.20 \(\pm\) 2.25 & 65.47 \(\pm\) 8.82 & 88.32 \(\pm\) 0.48 & 88.73 \(\pm\) 0.48 & 0.00 & 0.00 \(\pm\) 3.72 & 6.03 \(\pm\) 0.03 & 0.00 & 0.00 & 8.33 \\ HOG & 80.48 \(\pm\) 9.78 & 70.81 \(\pm\) 1.11 & 85.70 \(\pm\) 1.21 & 60.11 \(\pm\) 0.87 & 80.38 \(\pm\) 1.64 & 80.03 \(\pm\) 1.64 & 0.00 \(\pm\) 0.01 & 31.31 \(\pm\) 0.00 & 0.00 & 0.00 & 0.00 & 8.04 \\
**GCN** & 78.38 \(\pm\) 4.36 & 77.13 \(\pm\) 1.81 & 73.58 \(\pm\) 1.18 & 58.48 \(\pm\) 1.51 & 73.54 \(\pm\) 0.38 & 31.68 \(\pm\) 1.24 & 90.05 \(\pm\) 0.31 & 45.07 \(\pm\) 0.21 & 83.18 \(\pm\) 0.16 & 61.89 \(\pm\) 0.29 & 40.19 \(\pm\) 0.03 & 78.83 \(\pm\) 0.05 & 7.62 \\
**GCN** & **81.86 \(\pm\) 4.55 & 77.14 \(\pm\) 1.45 & 75.95 \(\pm\) 1.05 & 74.14 \(\pm\) 1.86 & 89.15 \(\pm\) 0.37 & 57.17 \(\pm\) 1.75 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 7.58 \\ GCN & 55.14 \(\pm\) 5.36 & 76.50 \(\pm\) 1.36 & 86.90 \(\pm\) 1.27 & 64.22 \(\pm\) 2.38 & 84.42 \(\pm\) 0.50 & 53.43 \(\pm\) 2.01 & 74.27 \(\pm\) 0.47 & 40.67 \(\pm\) 0.26 & 82.38 \(\pm\) 0.38 & 45.65 \(\pm\) 0.04 & 74.56 \(\pm\) 0.17 & 7.25 \(\pm\) 0.04 & 6.27 \(\pm\) 0.05 & 6.55 \(\pm\) 0.04 & 7.54 \(\pm\) 0.17 & 7.25 \\
**Multiple** & 77.84 \(\pm\) 3.73 & 73.65 \(\pm\) 1.33 & 87.61 \(\pm\) 0.85 & 93.60 \(\pm\) 2.53 & 83.31 \(\pm\) 0.61 & 83.40 \(\pm\) 1.29 & 83.05 \(\pm\) 0.16 & 83.05 \(\pm\) 0.15 & 81.51 \(\pm\) 0.17 & 87.47 \(\pm\) 0.71 & 65.48 \(\pm\) 0.27 & 51.26 \(\pm\) 0.09 & 83.74 \(\pm\) 0.10 & 6.41 \\
**GCN** & 77.53 \(\pm\) 3.73 & 73.18 \(\pm\) 1.21 & 82.21 \(\pm\) 2.15 & 83.60 \(\pm\) 1.30 & **83.48 \(\pm\) 0.34** & 84.39 \(\pm\) 0.40 & 87.19 \(\pm\) 0.20 & 42.12
bottleneck. Specifically, GGCN, H\({}_{2}\)GCN, and WRGAT cannot be employed in most large datasets due to their high memory requirement for simultaneously processing features and conducting propagation, which hinders their application. GPR-GNN, on the contrary, shows no superiority in effectiveness. On the other hand, decoupling heterophilous models LINKX and GloGNN++ achieve the most competitive accuracy over most datasets where LINKX separately embeds node features and graph topology and GloGNN++ further performs node neighborhood aggregation from the whole set of nodes in the graph, bringing them performance improvement. Notably, the advantage of LINKX is not consistent and is usually better on large graphs than on smaller ones.

\({}^{\bullet}\) Our method SIMGA achieves outstanding performance with the highest average accuracy on 9 out of 12 datasets and the top ranking 1.25, significantly better than the runner-up GloGNN++. We state that the superior and stable performance over various heterophilous graphs is brought by the capability of global aggregation that exploits structural information and evaluates node similarity. The simple decoupled feature transformation network architecture also effectively retrieves node features and generates embeddings. Specifically, on datasets like _snap-patents_, SIMGA outperforms the runner-up methods by nearly 1%., a significant improvement indicating that our method aggregates excellent neighborhood information to distinguish the homophily and heterophily. Besides, we consider SIMGA being slightly worse than the best method in three datasets due to the shallow feature transformation layers, which may have insufficient capacity for a large amount of input information and can be improved by introducing more specific designs. We leave this for future.

### Efficiency Study

To evaluate the efficiency aspect of SIMGA, we investigate its learning time and convergence on 6 large-scale datasets as shown in Table 3 and Figure 3, respectively.

**Learning Time** We compare the learning time of SIMGA with LINKX and GloGNN++ as they are all decoupling heterophilous methods and achieve first-tier performance. Learning time is the sum of pre-computation time and training time, since SIMGA needs to calculate the aggregation matrix before conducting network training. We use the same training set on each dataset and run 5-repeated experiments for 500 epochs. The average learning time is reported in Table 3.

It can be seen that SIMGA costs the least learning time over all the 12 datasets, especially on the large ones, thanks to its scalable pre-computation and top-\(k\) global aggregation mechanism. The result aligns with our complexity analysis in Section 3.4. Besides, the one-time similarity measurement calculation in SIMGA also benefits its speed compared with the GloGNN++'s to be-updated measurement. On datasets such as _Penn94_ and _pokce_, it outperforms GloGNN++ by around \(10\times\) faster, which is a significant speed-up. Although LINKX is relatively fast due to its simple yet effective architecture, it is still slower than SIMGA, i.e. 5 times slower on the largest dataset _pokce_.

**Convergence** We then study the convergence time as another indicator of model efficiency in graph learning. We compare SIMGA against models with leading efficacy in Table 2 in Figure 3. Among the methods, MixHop and GCNII are GNNs containing multi-hop neighbors as the ego node's neighborhood for aggregation or combine nodes with their degree information, while LINKX and GloGNN++ are decoupling heterophily methods without explicit graph convolution operation. Both SIMGA and GloGNN++ select nodes from the whole set of nodes in the graph, while SIMGA only considers nodes with significant scores and filters irrelevant ones through the top-\(k\) pruning.

Figure 3 shows that SIMGA shares favorable convergence states among all graphs, i.e. achieves high accuracy in a short training time. Generally, SIMGA and LINKX are the two fastest models among all competitors. GloGNN++ can converge to the first-tier results, but its speed is usually slower than SIMGA. For example, on the largest dataset _pokce_ with over 1.6 million nodes, SIMGA is approximately 5\(\times\) faster than GloGNN++. For _Penn94_, the speed difference even reaches 10\(\times\). Other methods such as MIXHOP is exceeded by a larger extent. These results validate that SIMGA is both highly effective and efficient, and can be capably applied to large heterophilous graphs.

\begin{table}
\begin{tabular}{c|c c c c c c c c c c c} \hline \hline  & **Texas** & **Citeseer** & **Cora** & **Chameleon** & **Pubmed** & **Squirrel** & **genius** & **arXiv-year** & **Penn94** & **twitch-game** & **snap-patents** & **pokce** \\ \hline LINKX & 8.6 & 19.0 & 12.4 & 12.9 & 20.1 & 19.9 & 292.3 & 51.2 & 112.1 & 302.7 & 701.8 & 2472.9 \\ GloGNN++ & 7.41 & 12.7 & 11.4 & 10.8 & 13.7 & 13.7 & 358.7 & 134.1 & 183.5 & 783.0 & 732.9 & 1564.7 \\
**SIMGA** & **4.3** & **10.2** & **6.6** & **7.5** & **12.1** & **12.7** & **153.6** & **36.5** & **17.2** & **236.5** & **408.2** & **388.5** \\ \hline _precomp_ & 0.0 & 0.1 & 0.2 & 0.1 & 1.6 & 0.3 & 8.6 & 9.3 & 3.9 & 14.0 & 15.9 & 11.4 \\ _training_ & 4.3 & 10.1 & 6.4 & 7.4 & 10.5 & 12.4 & 145.0 & 27.1 & 13.3 & 222.5 & 392.3 & 377.1 \\ \hline \hline \end{tabular}
\end{table}
Table 3: **The average learning time (s) of decoupling heterophily methods on 12 datasets. We separately show the _precomputation_ and _training_ time of SIMGA. The fastest is marked in bold.**
### Ablation Study

**Parameter \(\mathbf{\delta}\)** and \(\mathbf{S}\). In the initial embedding formation of SIMGA, the node attribute matrix and adjacency matrix are transformed into vectors using two MLPs. These vectors are then combined using the parameter \(\delta\) in Eq.(6). To investigate the importance of these two sources of information, we consider two variants: SIMGA-NA and SIMGA-NF. SIMGA-NA removes the adjacency matrix (\(\delta=0\)), while SIMGA-NF removes the node attributes (\(\delta=1\)). After obtaining the initial embeddings \(H\), SIMGA aggregates each node's features using \(S\) in Eq.(7) to capture distant intra-class nodes. We denote the variant that excludes the aggregation matrix \(S\) as SIMGA-NS. The results on large-scale datasets, as shown in Figure 4(a), indicate that removing either matrix leads to a performance drop. This demonstrates the effectiveness of the aggregation process \(S\) and highlights the benefits of incorporating both node attributes and the adjacency matrix in forming initial node embeddings.

**Parameter \(\mathbf{\delta}\)** and \(\mathbf{\varsigma}\). Choosing larger values for \(k\) and smaller values for \(\epsilon\) in the calculation of \(S\) introduces increased computational complexity (Proposition 3.7). In our empirical evaluation (Figure 4(b)), we observed that setting \(\epsilon=0.1\) provides satisfactory classification scores for the largest dataset, _pokec_. More stringent accuracy requirements by setting \(\epsilon=0.01\) only yield minimal performance improvements while significantly inflating pre-computation time by approximately 100 times. Similarly, we found that larger values of \(k\) lead to better results. Notably, setting \(k=1024\) already achieves excellent performance, and the amount of information filtered in \(S\) becomes negligible (refer to Appendix E for a more detailed discussion).

## 6 Conclusion

In this paper, we propose SIMGA, a simple and effective heterophilous graph neural network with near-linear time efficiency. We first derive a new interpretation of SimRank as global GNN aggregation, highlighting its capability of discovering structural similarity among nodes which are distant and have same label in the whole graph. Based on this connection, we employ a decoupling GNN architecture and utilize SimRank as aggregation without iterative calculation, where efficient approximation calculation can be applied and realize a time complexity near-linear to \(n\).

Figure 4: **Parameter effect of \(\delta\), \(S\), \(k\) and \(\epsilon\). \(\delta\) denotes the balancing factor in Eq.(6), \(k\) denotes number of selected nodes, \(S\) the aggregation matrix and \(\epsilon\) the absolute error tolerance for \(S\).**

Figure 3: **Convergence efficiency of SIMGA and selected baselines. X-time (s) and Y-accuracy.**