mO Shuaicheng[#1]

#  GPatcher: A Simple and Adaptive MLP Model for Alleviating Graph Heterophily

Shuaicheng Zhang*
Department of Computer Science
Virginia Tech
Blacksburg, VA, 24060
<EMAIL_ADDRESS>
&Haohui Wang*
Department of Computer Science
Virginia Tech
Blacksburg, VA, 24060
<EMAIL_ADDRESS>
Si Zhang
Meta
Menlo Park, CA, 94025
<EMAIL_ADDRESS>
&Dawei Zhou
Department of Computer Science
Virginia Tech
Blacksburg, VA, 24060
<EMAIL_ADDRESS>

###### Abstract

While graph heterophily has been extensively studied in recent years, a
fundamental research question largely remains nascent: _How and to what extent
will graph heterophily affect the prediction performance of graph neural
networks (GNNs)_? In this paper, we aim to demystify the impact of graph
heterophily on GNN spectral filters. Our theoretical results show that it is
essential to design adaptive polynomial filters that adapt different degrees
of graph heterophily to guarantee the generalization performance of GNNs.
Inspired by our theoretical findings, we propose a simple yet powerful GNN
named GPatcher by leveraging the MLP-Mixer architectures. Our approach
comprises two main components: (1) an adaptive _patch extractor function_ that
automatically transforms each node’s non-Euclidean graph representations to
Euclidean patch representations given different degrees of heterophily, and
(2) an efficient _patch mixer function_ that learns salient node
representation from both the local context information and the global
positional information. Through extensive experiments, the GPatcher model
demonstrates outstanding performance on node classification compared with
popular homophily GNNs and state-of-the-art heterophily GNNs.

111*Equal Contributions

##  1 Introduction

Graph Neural Networks (GNNs) have emerged as powerful tools for learning
graph-structured data in various domains, such as biology [1], chemisty [2,
3], finance [4], natural language processing [5], and computer vision [6, 7].
From the perspective of graph signal processing, GNNs can be naturally
interpreted as a graph filter $g(\mathbf{\Lambda})$ defined in the spectral
domain. Formally speaking, given a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$ and a set of training node
labels $\mathcal{Y}_{l}$, GNNs are typically designed to learn a spectral
filter $g(\mathbf{\Lambda})$ (also referred as hypothesis function) that
removes noise from input graph and predict the unknown “true signal”
$\mathcal{Y}_{u}$ (i.e., labels of the unlabeled nodes) [8]. It has been
theoretically demonstrated that the majority of GNNs are essentially a low-
pass filter [8], which assumes the node labels $\mathcal{Y}$ exhibit a low-
frequency nature (i.e., nearby nodes tend to share similar attributes with
each other). However, it is often the case that real-world graphs are
heterophily [9, 10], where nodes with similar features or common connections
have disparate classes. Moreover, growing empirical evidence [9, 10, 11]
suggests that graph heterophily largely deteriorates conventional GNNs’
performance, even worse than vanilla Multilayer Perceptron (MLP) [12].

To alleviate the negative impact of graph heterophily on GNNs, existing works
focus on the techniques such as non-local neighbor extension [13, 14] and GNN
refinement [15, 16]. Despite the promising performance, there are limited
theoretical tools to provide a deep understanding of the impact of heterophily
on GNNs. Therefore, in this paper, we begin by posing the research question
Q1: "How and to what extent will graph heterophily affect the prediction
performance of GNNs?". In response, we propose a theoretical model to
demystify the complex relationship between the degree of graph heterophily and
graph filters $g(\mathbf{\Lambda})$. Perhaps more interestingly, our result
implies that the average of frequency responses in $g(\mathbf{\Lambda})$ and
the graph heterophily degree may not follow an intuitive linear correlation,
which deviates from the common assumption that higher-pass graph filters are
preferred for graphs with higher heterophily degrees. As an illustrative
example, in Figure 1, we present the obtained graph filters
$g(\mathbf{\Lambda})$ on various benchmark graphs in a two-dimensional space,
where the horizontal axis corresponds to the heterophily degree of input
graphs while the vertical axis corresponds to the average of frequency
responses in $g(\mathbf{\Lambda})$.

Figure 1: An illustrative example of the average of obtained frequency
responses graph filters $\frac{\sum{g(\lambda_{i})}}{n}$ vs. heterophily
degree $\frac{\sum{H_{i}}}{n}$ on various benchmark graphs.

Moreover, our theoretical results motivate us to ask the second research
question Q2: "Can we leverage adaptive yet simpler GNN models to automatically
characterize the graph heterophily degree and learn salient node
representations?". Recent studies have illuminated the potentials of MLP-Mixer
models in delivering superior performance in computer vision [17] and natural
language processing [18], often comparable to or even exceeding that of the
transformer-based and autoregressive models, yet with a simple structure. This
potential leads us to propose a novel MLP-Mixer-based GNN named GPatcher,
which is designed to learn salient node representations by adapting to the
heterophily degree of input graphs. While patches in the original MLP-Mixer
for images are well-defined, they are not directly applicable to graph data.
This is because traditional adjacency matrices do not readily support the
conversion from non-Euclidean graph data into a format compatible with
Euclidean processing capabilities. To address this issue, we propose a _patch
extractor function_ that transforms non-Euclidean graph data into Euclidean
representations, making them amenable to processing by the GPatcher. Inspired
by our theoretical results, this heterophily-aware patch extractor is also
designed to serve as an _adaptive polynomial filters_ , capturing individual
node importance and incorporating adaptivity based on the degree of
heterophily. In addition, we introduce an efficient _patch mixer function_
that captures both the local context information [19, 20] and the global
positional information [21], which are essential to address graph heterophily
across varying degrees.

The key contributions of this paper are threefold. (1) For the first time, we
provide theoretical analyses, which demystify the relationship between graph
filter $g(\mathbf{\Lambda})$ and the graph heterophily degree $H$. (2)
Inspired by our theoretical results, we introduce the GPatcher, a novel
adaptation of the MLP-Mixer model to graphs, maintaining simplicity while
adaptively capturing the global positional information and label information
based on the degree of heterophily. We further extend it to a more efficient
variation named Fast-GPatcher, which embraces more simplicity. (3) We
substantiate the generalization performance of our GPatcher, through rigorous
theoretical analysis in Theorem 1 and extensive experiments on both synthetic
and real-world networks, emphasizing the potential of simpler yet highly
effective architectures for analyzing graph-structured data.

##  2 Preliminaries

###  2.1 Notations

We use regular letters to denote scalars (e.g., $c$), boldface lowercase
letters to denote vectors (e.g., $\mathbf{r}$), and boldface uppercase letters
to denote matrices (e.g., $\mathbf{X}$). We represent a graph as
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$, where $\mathcal{V}$
represent the set of nodes, $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$
represent the set of edges, and $\mathbf{X}$ represent the node feature
matrix. We define $n$ as the number of nodes, $\mathcal{Y}$ as the set of
labels. $\mathbf{L}$ ($\mathbf{A}$) is the Laplacian (adjacency) matrix, and
$\tilde{\mathbf{L}}$ ($\tilde{\mathbf{A}}$) is the normalized Laplacian
(adjacency) matrix. Table 5 in Appendix A summarizes the main symbols and
notations in this paper.

###  2.2 Graph Spectral Filters

Spectral-based GNNs provide an effective way of spectral analysis on graphs
according to graph signal processing. Specifically, the eigendecomposition of
symmetric normalized Laplacian is
$\tilde{\mathbf{L}}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{T}$, where
$\mathbf{U}\in\mathbb{R}^{n\times n}$ is the graph Fourier basis formed by $n$
eigenvectors, and $\mathbf{\Lambda}$ denotes the diagonal eigenvalue matrix.
Then the graph Fourier transform of the input signal of all nodes
$\textbf{x}\in\mathbb{R}^{n}$ is defined as
$\hat{\textbf{x}}=\mathbf{U}^{T}\textbf{x}$, where $\hat{\textbf{x}}$ is the
Fourier transformed graph signal. The inverse graph Fourier transform is given
as $\textbf{x}=\mathbf{U}\hat{\textbf{x}}$. Hence, the spectral graph
convolution of the signal x is defined as
$\textbf{x}*_{\mathcal{G}}g=\mathbf{U}g(\mathbf{\Lambda})\mathbf{U}^{T}\textbf{x}$,
where $g$ is the graph filter. Vanilla graph convolutional network (GCN) [20]
can be considered as the spectral convolution with a simplified first-order
Chebyshev polynomial to approximate the spectral filter
$g(\mathbf{\Lambda})=(I+\mathbf{\Lambda})^{-1}$, which attenuates the high-
frequency more than the low-frequency thus is a low-pass filter [8, 22].

###  2.3 Graph Heterophily

Many of the existing works on GNN models share a vital assumption of graph
homophily, i.e., locally connected nodes should be similar in terms of their
features and labels [20, 22]. However, recent research shows interest in the
limitations of graph models in dealing with heterophily graphs, where
connections often occur between nodes that are not similar. A commonly used
metric for modeling the heterophily of a graph is node heterophily [10].

######  Definition 1.

The neighbor set of $i$-th node $v_{i}$ is denoted as
$\mathcal{N}(v_{i})=\\{v_{j}:(v_{i},v_{j})\in\mathcal{E}\\}$, $y_{i}$ is the
label of node $v_{i}$, then we define the node heterophily $H_{i}$ as the
proportion of neighbors with a different label of node $v_{i}$:

$H_{i}=\frac{|\\{v_{j}\in\mathcal{N}(v_{i}):y_{j}\neq
y_{i}\\}|}{|\mathcal{N}(v_{i})|}.$ (1)

$H=(H_{0},\ldots,H_{n-1})$ defines vector of all node heterophilies in graph
$\mathcal{G}$.

Based on the above definition of node-level heterophily, the graph-level
heterophily can be derived by averaging across nodes, i.e.,
$\frac{1}{n}\sum_{0\leq i\leq n-1}H_{i}$. Real-world networks, such as those
represented by the Texas, Squirrel, Chameleon, Cornell, Wisconsin, and Actor
datasets [23, 24, 25], often exhibit a high heterophily. The standard approach
of graph convolutional networks, which updates node features by aggregating
neighboring node features, is thus less effective in these cases. Therefore,
it is crucial to gain a mathematical understanding of the research question
(Q1).

##  3 Demystify the Impact of Graph Heterophily on Graph filters

Existing works [13, 15, 26] share a common consensus that high-pass graph
filters are preferable for heterophily graphs, while low-pass filters are
favored for homophily graphs. However, this consensus is weak and not
necessarily accurate. The study of $g(\mathbf{\Lambda})$ focuses on low-pass/
high-pass filters in the spectral domain, while heterophily indicates the
differences among neighbor labels, which, although highly correlated, are not
necessarily equivalent. For example, consider a graph where each node is
assigned a different label, resulting in a highly heterophilic graph. In this
case, a high-pass filter may be appropriate for dealing with the graph
heterophily. However, in the graph coloring problem where each node is
assigned a color such that connected nodes have different colors while
minimizing the total number of colors used, the graph exhibits extreme
heterophily, with all neighbor nodes having different labels (colors).
Nevertheless, since the number of labels (colors) may be limited, only a low-
pass filter may be required to capture the necessary information [27, 28].

A key challenge to building the connection between graph filter and graph
heterophily is that they are originally defined in different domains: graph
filter is given in the spectral domain, while graph heterophily is in the
spatial domain. Therefore, we propose a novel notion of graph heterophily that
is defined in the spectral domain via graph Fourier Transformation.

######  Definition 2.

Denote $\mathbf{U}$ as the eigenvector matrix of normalized adjacency matrix
$\tilde{\mathbf{A}}$, the heterophily in spectral domain $\hat{H}$ is defined
as:

$\hat{H}=H\cdot\mathbf{U}$ (2)

where $\hat{H}=(\hat{H}_{0},\ldots,\hat{H}_{n-1})$ is denoted as the frequency
components of $H$.

Based on Definition 2, we provide the following lemma to show the lower bound
of graph filters concerning graph heterophily. The proof of Lemma 1 is
provided in Appendix B.

######  Lemma 1.

$\tilde{\mathbf{A}}$ is the normalized adjacency matrix, $n$ is the number of
nodes, $\lambda_{i}$ is the $i$-th eigenvalue of $\tilde{\mathbf{A}}$, where
$-1=\lambda_{0}\leq\cdots\leq\lambda_{n-1}\leq 1$, and $\mathbf{\Lambda}$ is a
diagonal matrix of all eigenvalues. $g(\mathbf{\Lambda})$ is the graph filter,
then we have the lower bound of the average of $g(\mathbf{\Lambda})$:

$\sum_{0\leq i\leq
n-1}\frac{g\left(\lambda_{i}\right)}{n}\geq\frac{\sum_{0\leq i\leq
n-1}\log|\hat{H}_{i}|}{n(\log\sum_{0\leq i\leq
n-1}g\left(\lambda_{i}\right)|\hat{H}_{i}|-\log\sum_{0\leq i\leq
n-1}g\left(\lambda_{i}\right))}$ (3)

Remark. Lemma 1 theoretically demonstrates that the average of frequency
responses in $g(\mathbf{\Lambda})$ and the graph heterophily degree might not
follow a linear correlation. The general observation is that heterophily
graphs have a smaller average frequency response, and homophily graphs have a
larger average frequency response. However, as shown in Figure 1, PubMed
dataset has a small heterogeneity degree, but the average of frequency
responses graph filters obtained from our experiments is small unlike other
datasets, illustrating that $\frac{1}{n}\sum_{0\leq i\leq n-1}g(\lambda_{i})$
and $\frac{1}{n}\sum_{0\leq i\leq n-1}\hat{H}_{i}$ may follow a complex
nonlinear relationship.

##  4 Approach

In this section, we first introduce the two main components of our model
GPatcher: patch extractor and patch mixer, discussed in detail in Section 4.1.
These components collaboratively resolve the challenges of graph heterophily
for semi-supervised node classification. Then, we delve into the theoretical
aspects of our approach, elucidating the generalization bound to ensure the
robustness of our model. Furthermore, we propose a fast algorithm in Section
4.2 to improve the efficiency and scalability of our model. This comprehensive
discussion underlines the unique characteristics of our approach,
distinguishing it from classic GNN methodologies and those tailored for graph
heterophily.

###  4.1 GPatcher Framework

Here we present the technical details of the patch extractor, which extracts
patches from $\mathcal{G}$, followed by the patch mixer, which mixes
information within each patch to learn better node representations.

#### Patch Extractor.

The patch extractor acts as the pivotal module of our model, transforming the
graph-structured data into a Euclidean representation. Its primary function is
to identify and extract a relevant set of top-$p$ nodes tailored to a specific
objective. To address the heterophily challenge Q2, we introduce a
heterophily-aware patch extractor that effectively recognizes and adapts to
varying heterophily levels. This extractor constructs a patch for each
individual node, which is a subset of nodes (not necessarily the direct
neighbors) that hold high relevance in the context of graph heterophily. The
extractor selects nodes with the highest relevance scores and incorporates the
top-$p$ scoring nodes into the corresponding node’s patch. Grounded in our
theoretical investigation of graph heterophily and guided by Q2, the patch
extractor’s design capitalizes on the graph’s spectral properties and exhibits
the necessary adaptability to accommodate diverse heterophily degrees.
Consequently, the generated patches capture the core characteristics of the
graph data and its heterophily degree, forming a solid basis for the
subsequent stages of our model.

The heterophily-aware patch extractor utilizes the normalized adjacency matrix
$\tilde{\mathbf{A}}$ instead of the graph Laplacian, as the former provides a
powerful representation of local graph structure and its underlying
relationships. This choice allows the spectral graph filter framework to be
utilized, emphasizing local connectivity and effectively addressing graph
heterophily. The filter operation based on an adaptive polynomial filter is
defined as

$g(\mathbf{\Lambda})=\sum^{K}_{k=1}\sigma(\textbf{w}_{k}\odot\mathbf{\Lambda}^{k}),$
(4)

where $\sigma$ denotes a non-linear activation function, and $\textbf{w}_{k}$
are learnable parameters. To extract the patch for each node, we first compute
a scoring matrix $\textbf{R}\in\mathbb{R}^{n\times n}$ where

$\textbf{R}=\mathbf{U}\left(\sum_{k=1}^{K}\textbf{w}_{k}\odot\mathbf{\Lambda}^{k}\right)\mathbf{U}^{T}.$
(5)

Subsequently, we utilize it as a rank-order metric to extract the top-$p$
nodes, viewed as the patch for each node. For each column $col$ in R, the
indices are organized in descending order according to their corresponding
relevance scores. This operation is mathematically represented as
$\text{sorted}_{col}=\text{argsort}(\textbf{R}{:,col},\text{descending})$.
Following this, the indices of the top $p$ nodes with the highest relevance
scores for each column $col$ are chosen, denoted as
$\text{top-}p_{col}=\text{sorted}_{col}[0:p]$. In this way, the patch
extractor is equivalent to

$\phi(\tilde{\mathbf{A}})=\text{top-}p_{col}\biggl{(}\mathbf{U}\left(\sum_{k=1}^{K}\textbf{w}_{k}\odot\mathbf{\Lambda}^{k}\right)\mathbf{U}^{T}\biggl{)}.$
(6)

Using the selected node indices, we extract input node features of the patch
for each node $v$, denoted by
$\textbf{P}_{v}={\textbf{X}[\text{top-}p(\textbf{R}_{v})]}$. This process
results in patches $\textbf{P}\in\mathbb{R}^{n\times p\times d}$. This patch
representation encapsulates the learning of complex relationships among nodes.
It also allows for an effective approach to handle graph heterophily via the
patch mixer, thereby enhancing the precision of node representation and
improving model performance across various levels of graph heterophily.

#### Alternate Patch Extractor

To underscore the adaptability and versatility of our model, we consider
several alternative patch extractors, including heat filters, bandpass filters
[29], and a method employing shared parameters. The heat filter, emulating a
graph’s diffusion process, works in the spectral domain. Given a normalized
adjacency matrix $\mathbf{\tilde{A}}$ with eigenvalues $\mathbf{\lambda}_{i}$
and eigenvectors $\mathbf{u}_{i}$, the basis of heat filter extractor is
represented as
$g_{(heat)}(\mathbf{\Lambda},t)=\sum^{K}_{k=1}\sigma(e^{-t\mathbf{\Lambda}}$),
with $t$ serving as the filter number in our model. Conversely, the bandpass
filter isolates specific spectral components of a graph signal. For a
normalized adjacency matrix $\tilde{\mathbf{A}}$ with corresponding
eigenvalues and eigenvectors, the basis of the bandpass filter extractor is
defined as
$g_{(bandpass)}(\mathbf{\Lambda},l,h)=\sum^{K}_{k=1}\sigma(\mathcal{R}(\mathbf{\Lambda},l,h,k))$,
where $l$ and $h$ set the lower and upper-frequency boundaries, respectively,
and $\mathcal{R}(\mathbf{\Lambda},l,h,k)$ is a rectangular function. The
concept of shared parameters refers to a design choice where a common set of
filter parameters is employed across all filter numbers. Formally, the basis
of the share parameters extractor is defined as
$g_{(shared)}(\mathbf{\Lambda})=\sum^{K}_{k=1}\sigma(\textbf{w}_{1}\mathbf{\Lambda}^{k})$.
This approach enhances model parsimony and consistency in the patch extraction
process, potentially leading to more powerful representations.

#### Patch Mixer.

The original MLP-Mixer consists of two types of layers: channel-mixing and
patch-mixing layers. In response to Q1, we redefine these concepts for graph-
structured data as follows:

  1. 1.

Feature-Mixing Layer: Given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$
with nodes $\mathcal{V}$ and edges $\mathcal{E}$, and a patch $\mathbf{P}_{v}$
for a node $v\in\mathcal{V}$, this layer applies a multilayer perceptron (MLP)
to the nodes in $\mathbf{P}_{v}$ to mix information within the patch, denoted
as $\mathbf{P}_{v}=\mathrm{MLP}(\mathbf{P}_{v})$.

  2. 2.

Patch-Mixing Layer: This layer mixes information across patches. Given the
output $\mathbf{P}_{v}$ of the patch-mixing layer for each node
$v\in\mathcal{V}$, it applies an MLP across patches independently for each
feature, denoted as $\mathbf{P}=\mathrm{MLP}(\mathbf{P}^{T})^{T}$, where
$\mathbf{P}$ is the collection of all patches $\mathbf{P}_{v}$ for all nodes
$v\in\mathcal{V}$.

In our patch mixer, we incorporate two distinct types of information: local
contextual information [20, 19] and global positional information [21]. The
local contextual information encapsulates the attribute data related to a node
and its immediate topological neighborhood. This localized data is captured
and processed by the Feature-Mixing Layer, which applies a multilayer
perceptron (MLP) to nodes within each patch, effectively mixing the
information within these local patches. On the other hand, the global
positional information, which refers to a node’s broader position and role
within the entire graph, is incorporated by the Patch-Mixing Layer. This layer
employs an MLP across all patches for each feature, allowing for a global
perspective that considers the interconnectedness and relationships between
patches. Thus, our model adeptly integrates both local contextual information
and global positional information via the feature-mixing layers and patch-
mixing layers.

#### Generalization Analysis of GPatcher.

Although we propose patches that adaptively capture the varying degrees of
heterophily, the extent to which our algorithm can guarantee generalization
performance remains unclear because of the limited theoretical tools.
Therefore, in order to shed light on this issue, we propose an upper bound of
the error in terms of graph filters, graph heterogeneity, graph features, and
labels. The proof of Theorem 1 is provided in Appendix B.

######  Theorem 1.

For a binary classification problem on graph $\mathcal{G}_{n}$ with
$\tilde{\mathbf{A}}$, let
$\mathbf{X}=\left(\mathbf{x}_{0},\mathbf{x}_{1}\right)$ be the learnable input
of $g(\tilde{\mathbf{A}})$ in the last layer and
$\mathbf{Y}=\left(\mathbf{y}_{0},\mathbf{y}_{1}\right)$ be the label matrix,
the error bound is:

$\overline{Er}(\mathbf{X},\mathbf{Y})\leq
c_{1}-\frac{\min_{i\in\mathcal{I}_{g,\delta,\eta}}\psi_{\frac{1}{g\left(1-\mathbf{\lambda}_{i}\right)\delta_{i}}}\left(\eta_{i}\right)\cdot\delta_{i}\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}\log|\hat{H}_{i}|}{2n\log\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}g\left(1-\mathbf{\lambda}_{i}\right)|\hat{H}_{i}|-2n\log\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}g\left(1-\mathbf{\lambda}_{i}\right)}$
(7)

where $c_{1}$ is a constant, $\delta$, $\eta$ are the spectra of $\Delta y$
and $\Delta x$, $\mathcal{I}_{\delta}=\\{i|\delta_{i}\neq 0,i=0,\cdots,n-1\\}$
is the indicator set of nonzero elements of $\delta$, and
$\psi(x)=\min\\{\max\\{x,-1\\},1\\}$ is a clamp finction.

###  4.2 Fast-GPatcher

While the heterophily-aware patch function is a powerful method for adaptively
capturing graph heterophily, its computational complexity can be the
bottleneck for large-scale graph datasets due to the computations of eigen
decomposition (i.e., $O(n^{3})$). To address this challenge, we seek to
develop an efficient algorithm that retains the performance of our model
without compromising scalability and applicability. In pursuit of an efficient
patch extraction method, we uncover the relationship between our adaptive
polynomial filters-based method and the non-adaptive variant inspired by a
classic optimization-based ranking algorithm which aims to minimize the
following objective function for each node $v$.

$\mathcal{J}(\mathbf{r}_{v})=c\mathbf{r}_{v}^{T}(\mathbf{I}-\tilde{\mathbf{A}})\mathbf{r}_{v}+(1-c)\|\mathbf{r}_{v}-\mathbf{e}_{v}\|_{2}^{2}$
(8)

where $\mathbf{r}_{v}$ is the ranking vector w.r.t. node $v$ and
$\mathbf{e}_{v}$ is a node indicator vector. To solve this optimization
problem, the iterative approach can be formulated as

$\textbf{r}_{v}=c\tilde{\mathbf{A}}\textbf{r}_{v}+(1-c)\textbf{e}_{v}$ (9)

and the closed-form solution is
$\textbf{r}_{v}=(1-c)(1-c\tilde{\mathbf{A}})^{-1}\textbf{e}_{v}$.

By the Neumann series expansion, the closed-form solution can be approximated
by

$\textbf{r}_{v}=(1-c)\sum_{k=0}^{K}c^{k}\tilde{\mathbf{A}}^{k}\mathbf{e}_{v}=(1-c)\sum_{k=0}^{K}c^{k}(\mathbf{U}\mathbf{\Lambda}^{k}\mathbf{U}^{T})\textbf{e}_{v}.$
(10)

Obviously, by selecting top-$p$ nodes based on $\mathbf{r}_{v}$, it can be
considered as a special case of Eq. (6) by substituting $(c\mathbf{\Lambda})$
with $\textbf{w}\mathbf{\Lambda}$

$\phi_{\text{fast}}(\tilde{\mathbf{A}})=\text{top-}p_{col}(\mathbf{R})=\text{top-}p_{col}([\mathbf{r}_{1},\cdots,\mathbf{r}_{n}])$
(11)

Compared with heterophily-aware patch extractor’s $O(n^{3})$ complexity, Fast-
GPatcher is more scalable and computation efficient with $O((n+m)t)$ where $m$
is the number of edges and $t$ is the number of iterative steps. Fast-GPatcher
extractor computes proximity scores in an iterative manner. In each iteration,
the algorithm must update the rank value for each node in the graph, which is
a process with a time complexity of $O(n+m)$,

##  5 Experiment

###  5.1 Experiment Setup

#### Datasets.

We evaluate our model, GraphPatcher, using several standard graph datasets
originated from [30]: Cora, Citeseer, PubMed, Texas, Squirrel, Chameleon,
Cornell, Wisconsin, and Actor. These datasets are diverse in terms of their
sizes and degrees of heterophily. They cover a range of domains including
citation networks (Cora, Citeseer, PubMed[31, 32]), web page networks (Texas,
Cornell, Wisconsin[25]), animal interaction networks (Squirrel,
Chameleon[23]), and Actor is an actor co-occurrence network[24]. Homophily
datasets are Cora, Citeseer, and PubMed, while Texas, Squirrel, Chameleon,
Cornell, Wisconsin, and Actor are heterophily datasets. The statistics of
these datasets are summarized in Appendix D.

#### Comparison Methods.

We compare our model with several baseline methods, including GPRGNN [33],
ChebNet [34], APPNP [35], GCN-JKNet [36], GCN [20], GAT [37], GraphSage [38],
FAGCN [26], H2GCN [13], and MLP. GPRGNN aims to improve the performance of
GNNs by incorporating graph pooling and refinement. ChebNet utilizes Chebyshev
polynomial filters to perform graph convolutions. APPNP introduces
personalized PageRank to iteratively propagate information in the graph.
GCNJKNet combines graph convolutional networks (GCN) and Jumping Knowledge
Networks (JKNet) to capture multi-scale information. GCN is a classic graph
convolutional network that operates on a fixed neighborhood. GAT employs
attention mechanisms to selectively aggregate information from neighboring
nodes. GraphSage performs inductive learning by sampling and aggregating
features from a node’s local neighborhood. FAGCN incorporates both low and
high-frequency signals. H2GCN focuses on analyzing heterophilic graphs by
considering higher-order neighborhoods. MLP is an attribute-only-based multi-
layer perceptron. We compare our proposed model against these baselines to
evaluate its performance and effectiveness in handling graph heterophily.

| Homophily Dataset | Heterophily Dataset
---|---|---
Model | Cora | CiteSeer | PubMed | Texas | Squirrel | Chameleon | Cornell | Wisconsin | Actor
$\frac{\sum{H_{i}}}{n}$ | 0.19 | 0.26 | 0.2 | 0.89 | 0.78 | 0.77 | 0.89 | 0.84 | 0.76
MLP | 49.7 $\pm$ 1.5 | 48.8 $\pm$ 4.6 | 69.8 $\pm$ 1.1 | 74.4 $\pm$ 5.6 | 33.6 $\pm$ 1.4 | 45.8 $\pm$ 2.0 | 69.9 $\pm$ 2.9 | 80.4 $\pm$ 3.7 | 35.0 $\pm$ 0.7
GPRGNN | 76.1 $\pm$ 0.9 | 63.9 $\pm$ 1.2 | 75.6 $\pm$ 0.7 | 64.2 $\pm$ 5.3 | 30.4 $\pm$ 2.0 | 36.3 $\pm$ 2.1 | 59.1 $\pm$ 4.4 | 72.8 $\pm$ 4.5 | 30.9 $\pm$ 0.7
ChebNet | 73.7 $\pm$ 0.7 | 59.7 $\pm$ 1.1 | 75.1 $\pm$ 0.8 | 74.4 $\pm$ 5.8 | 33.4 $\pm$ 1.0 | 47.5 $\pm$ 1.5 | 69.7 $\pm$ 2.8 | 77.9 $\pm$ 3.0 | 34.8 $\pm$ 1.0
APPNP | 76.5 $\pm$ 1.6 | 64.2 $\pm$ 1.3 | 75.8 $\pm$ 1.7 | 56.3 $\pm$ 3.9 | 27.8 $\pm$ 0.7 | 38.8 $\pm$ 1.5 | 42.9 $\pm$ 3.7 | 52.3 $\pm$ 4.9 | 28.4 $\pm$ 0.6
GCNJKNet | 76.9 $\pm$ 1.7 | 63.4 $\pm$ 1.4 | 74.1 $\pm$ 0.9 | 57.8 $\pm$ 2.0 | 26.3 $\pm$ 0.6 | 37.5 $\pm$ 1.9 | 40.9 $\pm$ 4.6 | 49.6 $\pm$ 4.8 | 27.9 $\pm$ 0.8
GCN | 76.1 $\pm$ 2.3 | 63.9 $\pm$ 2.4 | 75.8 $\pm$ 0.9 | 58.7 $\pm$ 2.8 | 27.1 $\pm$ 0.5 | 39.9 $\pm$ 2.0 | 40.3 $\pm$ 3.3 | 49.4 $\pm$ 3.0 | 28.4 $\pm$ 0.7
GAT | 75.6 $\pm$ 2.3 | 63.4 $\pm$ 1.0 | 75.2 $\pm$ 1.0 | 58.3 $\pm$ 4.8 | 28.7 $\pm$ 0.9 | 42.8 $\pm$ 1.5 | 46.3 $\pm$ 4.3 | 51.1 $\pm$ 6.2 | 28.9 $\pm$ 0.5
GraphSage | 73.9 $\pm$ 0.5 | 63.7 $\pm$ 1.6 | 75.5 $\pm$ 1.1 | 74.3 $\pm$ 3.7 | 36.2 $\pm$ 0.8 | 47.4 $\pm$ 1.8 | 69.1 $\pm$ 3.5 | 76.9 $\pm$ 4.5 | 34.6 $\pm$ 0.7
FAGCN | 73.2 $\pm$ 0.7 | 61.2 $\pm$ 0.7 | 74.9 $\pm$ 1.1 | 65.4 $\pm$ 2.8 | 33.9 $\pm$ 0.8 | 43.2 $\pm$ 0.9 | 55.4 $\pm$ 5.1 | 65.7 $\pm$ 4.3 | 34.4 $\pm$ 0.5
H2GCN | 76.5 $\pm$ 2.3 | 60.5 $\pm$ 0.9 | 75.5 $\pm$ 1.9 | 81.1 $\pm$ 5.2 | 32.2 $\pm$ 1.2 | 54.0 $\pm$ 1.1 | 68.5 $\pm$ 2.9 | 78.0 $\pm$ 3.1 | 34.9 $\pm$ 0.4
BM-GCN | 75.6 $\pm$ 2.3 | 63.0 $\pm$ 1.0 | 75.2 $\pm$ 1.0 | 75.4 $\pm$ 4.8 | 34.2 $\pm$ 0.9 | 53.6 $\pm$ 1.5 | 62.3 $\pm$ 4.3 | 75.4 $\pm$ 5.2 | 34.7 $\pm$ 0.5
Fast-GPatcher | 76.3 $\pm$ 0.6 | 62.5 $\pm$ 1.8 | 75.3 $\pm$ 0.9 | 81.3 $\pm$ 2.2 | 36.7 $\pm$ 1.1 | 55.4 $\pm$ 1.1 | 69.9 $\pm$ 2.3 | 80.5 $\pm$ 2.4 | 36.7 $\pm$ 0.9
GPatcher |  77.3 $\pm$ 0.6 |  64.5 $\pm$ 1.8 |  76.3 $\pm$ 0.9 |  85.0 $\pm$ 3.5 |  37.8 $\pm$ 1.6 |  57.3 $\pm$ 1.2 |  71.5 $\pm$ 3.4 |  83.2 $\pm$ 3.4 |  37.8 $\pm$ 0.7

Table 1: Results for different models on the homophily and heterophily
datasets.

#### Implementation Details.

We employ the Adam optimizer with a learning rate of 0.005 and a weight decay
of 5e-4 for training the model. The default training setting for all models is
performed using torch-geometric default masks(train, validation, and test) and
trained for a maximum of 500 epochs, a hidden dimension of 64, a dropout rate
of 0.5, and a number of layers of 2. Early stopping is applied with a patience
of 50 epochs, which monitors the validation loss and terminates the training
if there is no improvement observed within the specified patience. This helps
prevent overfitting and ensures the model generalizes well to unseen data. To
assess the performance of the models, we use the standard accuracy metric,
which is commonly adopted in node classification tasks.

Model | Cora | Chameleon
---|---|---
GCN |  74.1 $\pm$ 1.0 |  56.0 $\pm$ 2.0
FAGCN |  74.8 $\pm$ 0.4 |  48.3 $\pm$ 2.2
GPatcher |  77.3 $\pm$ 0.6 |  57.3 $\pm$ 1.2
Table 2: Ablation study results comparing GCN, FAGCN on Cora and Chameleon
datasets with induced graphs from heterophile-aware patch function.

###  5.2 Quantitive Analysis

In this section, we present a comprehensive quantitative analysis comparing
the performance of our proposed method with various state-of-the-art graph
neural network models. Our proposed method consistently outperforms the other
models across both homophily and heterophily datasets. In particular, the
performance gains are more prominent in the challenging heterophily datasets,
where the underlying graph structure exhibits more complex relationships
between nodes. The results demonstrate the effectiveness of our approach in
capturing and leveraging the diverse connectivity patterns present in these
datasets. We also examine different variations of our proposed method,
including the fast GPatcher and standard GPatcher model. The performances of
these variations are relatively similar, indicating the robustness and
versatility of our method in handling different graph structures. In summary,
the quantitative analysis demonstrates the superiority of our approach
compared to the existing models, especially in the context of heterophily
datasets.

#### Ablation Study: Induced Graph.

We conduct an ablation study comparing the performance using several other
popular graph neural network models on induced graphs obtained from our patch
function. The baseline models include GCN, H2GCN, and the evaluation datasets
used include Cora and Chameleon.

We summarize the results of the ablation study in Table 2, which includes the
performance metrics of each model on the dataset. The results in Table 2
demonstrate that our method achieves better performance compared to the other
models, highlighting the effectiveness of our heterophily-aware patch function
and the adaptive polynomial filters. Additionally, the comparison between
H2GCN and FAGCN reveals the importance of incorporating adaptive polynomial
filters in addressing graph heterophily.

Figure 2: Scalability analysis. Model | Cora | Chameleon
---|---|---
Bandpass Filter |  71.3 $\pm$ 0.8 |  52.1 $\pm$ 1.5
Heat Filter |  70.4 $\pm$ 1.69 |  47.7 $\pm$ 1.73
Shared parameters |  73.0 $\pm$ 1.3 |  52.2 $\pm$ 1.1
Heterophily-aware |  77.3 $\pm$ 0.6 |  57.3 $\pm$ 1.2
Table 3: Performance comparison of alternative patch functions on Cora and
Chameleon datasets.

#### Ablation Study: Alternative Patch Functions.

We assess the impact of alternative parameters in our method by comparing the
performance of our model using different patch functions and settings.

The results in Table 3 indicate that the choice of patch function and
parameter settings plays a significant role in the performance of our model.
Using a shared parameter setting yields better results across the datasets,
suggesting that it effectively captures the underlying graph structure and
accurately represents the relationships among nodes in the graph. Moreover,
the comparison between bandpass and heat filters reveals the importance of
selecting an appropriate filter function for the given task and dataset.

Figure 3: Parameter sensitivity analysis results for Cora(left) and
Texas(right) datasets, respectively.

#### Ablation Study: Patch Order Importance.

We investigate the importance of patch order in our method at table 4. We
compare the performance of our model with different patch orders by random
shuffling, where the patch order refers to the number of neighbor nodes
considered in the patch extraction process. Our findings reveal that shuffling
the patch order leads to significant degrading performance, indicating that
considering patch node order plays a vital role in capturing the complex graph
structures and addressing heterophily.

#### Scalability Analysis on patch mixer.

We analyze the runtime of the algorithm as the number of nodes and patch size
varies to assess the scalability of our proposed approach in Figure 2. We
perform experiments on synthetic datasets with varying numbers of nodes from
{10, 100, 1,000, 10,000, 100,000}. We also consider different patch sizes,
specifically {8, 16, 32, 64}. The runtime results are reshaped into a matrix
for visualization purposes. Figure 2 shows the runtime in seconds on a
logarithmic scale for the different patch sizes as a function of the number of
nodes. As expected, the runtime increases with the number of nodes and patch
size. Nevertheless, our method demonstrates reasonable scalability as the
growth in runtime is sub-linear, indicating that our approach can handle
large-scale graph datasets effectively. The results also highlight the
importance of selecting an appropriate patch size to balance the trade-off
between computational efficiency and performance.

Dataset | Random Order | Ranked Order
---|---|---
Cora | $71.4\pm 1.1$ | $\textbf{77.3}\pm 0.6$
Citeseer | $60.7\pm 1.4$ | $\textbf{64.5}\pm 1.8$
Squirrel | $35.4\pm 1.2$ | $\textbf{37.8}\pm 1.6$
Chameleon | $51.0\pm 1.2$ | $\textbf{57.3}\pm 1.1$
Table 4: Importance of patch order.

#### Parameter Sensitivity Analysis.

We conduct a parameter sensitivity analysis to investigate the impact of patch
size and the number of filters in Figure 3. The analysis was performed on two
datasets, namely the Cora and Texas datasets. We varied the patch size from
{8, 16, 32, 64} and the number of filters from {10, 50, 100, 200}. We measure
the accuracy of the model for each combination of parameters. Figure 3 shows
the results of the parameter sensitivity analysis. The plots reveal that for
both datasets, increasing the patch size and the number of filters generally
leads to higher accuracy, although the improvements tend to plateau beyond
certain values. This indicates that our model can effectively handle different
patch sizes and filter configurations while highlighting the importance of
selecting appropriate parameters to achieve optimal performance.

##  6 Related Work

#### Graph Neural Networks.

Traditional Graph Neural Networks have achieved remarkable results in learning
representations from graph-structured data, particularly under the assumption
of homophily, where connected nodes are more likely to share the same label.
These models, including Graph Convolutional Networks [20], Graph Attention
Networks (GATs) [37], and GraphSAGE [38], rely heavily on localized filters or
attention mechanisms for information aggregation. More recently, transformer-
based models [39] and MLP-Mixer-inspired architecture [40, 41] have emerged,
extending the capability of GNNs to capture global positional information.
Nevertheless, these models are still inherently tied to the concept of
homophily and often struggle when faced with heterophilic scenarios.

#### Learning on Heterophily Graphs.

The challenge of heterophily, where connected nodes are less likely to share
the same label, necessitated the development of specialized GNNs. These
heterophily GNNs, such as H2GCN [13], FAGCN [42], and BM-GCN [16], employ a
variety of strategies, from using both low-pass and high-pass filters to
feature augmentation and block-matching techniques. While they exhibit
improved performance on heterophilic graphs, they often involve intricate
design choices and lack robustness to different heterophily levels. In
contrast, our proposed GPatcher model strikes a balance between the simplicity
of MLP-Mixer architecture and the versatility of adaptive polynomial filters,
efficiently utilizing both low-pass and high-pass information. More
importantly, it provides a theoretical link between adaptive polynomial
filters and heterophily degree, thereby offering a more generalized and
adaptive solution for graph heterophily.

##  7 Conclusion

In conclusion, our study conducts a thorough theoretical analysis of the
impact of graph heterophily on GNN spectral filters and highlights the
necessity of designing adaptive polynomial filters to ensure generalization
performance across varying degrees of heterophily. The proposed GPatcher
model, inspired by the MLP-Mixer architecture, effectively addresses graph
heterophily and consistently outperforms traditional GNNs and state-of-the-art
heterophily GNNs in node classification tasks. This work underscores the
significance of developing adaptive and robust GNN model architectures to
tackle graph heterophily, paving the way for future research in graph
representation learning.

## References

  * [1] Kexin Huang, Cao Xiao, Lucas M Glass, Marinka Zitnik, and Jimeng Sun.  Skipgnn: predicting molecular interactions with skip-graph networks.  Scientific reports, 10(1):1–16, 2020.
  * [2] Tianyi Zhao, Yang Hu, Linda R Valsdottir, Tianyi Zang, and Jiajie Peng.  Identifying drug–target interactions based on graph convolutional network and deep neural network.  Briefings in bioinformatics, 22(2):2141–2150, 2021.
  * [3] Dejun Jiang, Zhenxing Wu, Chang-Yu Hsieh, Guangyong Chen, Ben Liao, Zhe Wang, Chao Shen, Dongsheng Cao, Jian Wu, and Tingjun Hou.  Could graph neural networks learn better molecular representation for drug discovery? a comparison study of descriptor-based and graph-based models.  Journal of cheminformatics, 13(1):1–23, 2021.
  * [4] Daixin Wang, Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang, Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang, and Yuan Qi.  A semi-supervised graph attentive network for financial fraud detection.  In 2019 IEEE International Conference on Data Mining (ICDM), pages 598–607. IEEE, 2019.
  * [5] Lingfei Wu, Yu Chen, Kai Shen, Xiaojie Guo, Hanning Gao, Shucheng Li, Jian Pei, and Bo Long.  Graph neural networks for natural language processing: A survey.  Foundations and Trends in Machine Learning, 16(2):119–328, 2023\.
  * [6] Long Zhao, Xi Peng, Yu Tian, Mubbasir Kapadia, and Dimitris N Metaxas.  Semantic graph convolutional networks for 3d human pose regression.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 3425–3435, 2019.
  * [7] Zhao-Min Chen, Xiu-Shen Wei, Peng Wang, and Yanwen Guo.  Multi-label image recognition with graph convolutional networks.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 5177–5186, 2019.
  * [8] Hoang NT and Takanori Maehara.  Revisiting graph neural networks: All we have is low-pass filters.  ArXiv, abs/1905.09550, 2019.
  * [9] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra.  Graph neural networks with heterophily.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11168–11176, 2021.
  * [10] Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S. Yu.  Graph neural networks for graphs with heterophily: A survey, 2022.
  * [11] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup.  Revisiting heterophily for graph neural networks.  In NeurIPS, 2022.
  * [12] Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah.  Graph-less neural networks: Teaching old MLPs new tricks via distillation.  In International Conference on Learning Representations, 2022.
  * [13] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra.  Beyond homophily in graph neural networks: Current limitations and effective designs.  Advances in Neural Information Processing Systems, 33, 2020.
  * [14] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan.  Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing.  In international conference on machine learning, pages 21–29. PMLR, 2019.
  * [15] Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent Lee, and Shirui Pan.  Beyond smoothing: Unsupervised graph representation learning with edge heterophily discriminating.  In AAAI, 2023.
  * [16] Dongxiao He, Chundong Liang, Huixin Liu, Mingxiang Wen, Pengfei Jiao, and Zhiyong Feng.  Block modeling-guided graph convolutional neural networks.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4022–4029, 2022.
  * [17] Yang Liu, Yao Zhang, Yixin Wang, Feng Hou, Jin Yuan, Jiang Tian, Yang Zhang, Zhongchao Shi, Jianping Fan, and Zhiqiang He.  A survey of visual transformers.  IEEE Transactions on Neural Networks and Learning Systems, 2023\.
  * [18] Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu.  A survey of transformers.  AI Open, 2022.
  * [19] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.  LINE: large-scale information network embedding.  In Aldo Gangemi, Stefano Leonardi, and Alessandro Panconesi, editors, Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015, pages 1067–1077. ACM, 2015.
  * [20] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In International Conference on Learning Representations (ICLR), 2017\.
  * [21] Jiaxuan You, Rex Ying, and Jure Leskovec.  Position-aware graph neural networks.  In International conference on machine learning, pages 7134–7143. PMLR, 2019.
  * [22] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying graph convolutional networks.  In International conference on machine learning, pages 6861–6871. PMLR, 2019.
  * [23] Benedek Rozemberczki, Carl Allen, and Rik Sarkar.  Multi-scale attributed node embedding.  Journal of Complex Networks, 9(2):cnab014, 2021.
  * [24] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang.  Social influence analysis in large-scale networks.  In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’09, page 807–816, New York, NY, USA, 2009. Association for Computing Machinery.
  * [25] Alberto P García-Plaza, Víctor Fresno, Raquel Martínez Unanue, and Arkaitz Zubiaga.  Using fuzzy logic to leverage html markup for web page representation.  IEEE Transactions on Fuzzy Systems, 25(4):919–933, 2016.
  * [26] Shouheng Li, Dongwoo Kim, and Qing Wang.  Beyond low-pass filters: Adaptive feature propagation on graphs.  In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13–17, 2021, Proceedings, Part II 21, pages 450–465. Springer, 2021.
  * [27] Wei Li, Ruxuan Li, Yuzhe Ma, Siu On Chan, David Pan, and Bei Yu.  Rethinking graph neural networks for the graph coloring problem.  arXiv preprint arXiv:2208.06975, 2022.
  * [28] Xiangyu Wang, Xueming Yan, and Yaochu Jin.  A graph neural network with negative message passing for graph coloring.  arXiv preprint arXiv:2301.11164, 2023.
  * [29] Hoda Bahonar, Abdolreza Mirzaei, Saeed Sadri, and Richard C Wilson.  Graph embedding using frequency filtering.  IEEE transactions on pattern analysis and machine intelligence, 43(2):473–484, 2019.
  * [30] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur.  Protein interface prediction using graph convolutional networks.  Advances in neural information processing systems, 30, 2017.
  * [31] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  AI magazine, 29(3):93–93, 2008.
  * [32] Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu.  Query-driven active surveying for collective classification.  In 10th international workshop on mining and learning with graphs, volume 8, page 1, 2012.
  * [33] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic.  Adaptive universal generalized pagerank graph neural network.  In International Conference on Learning Representations, 2021.
  * [34] Shanshan Tang, Bo Li, and Haijun Yu.  Chebnet: Efficient and stable constructions of deep neural networks with rectified power units using chebyshev approximations.  arXiv preprint arXiv:1911.05467, 2019.
  * [35] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
  * [36] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka.  Representation learning on graphs with jumping knowledge networks.  In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 5449–5458. PMLR, 2018\.
  * [37] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph Attention Networks.  International Conference on Learning Representations, 2018.
  * [38] William L. Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In NIPS, 2017.
  * [39] Xin Lin, Changxing Ding, Yibing Zhan, Zijian Li, and Dacheng Tao.  Hl-net: Heterophily learning network for scene graph generation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 19476–19485, June 2022.
  * [40] Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi.  Do we really need complicated model architectures for temporal networks?  arXiv preprint arXiv:2302.11636, 2023.
  * [41] Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson.  A generalization of vit/mlp-mixer to graphs, 2022.
  * [42] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen.  Beyond low-frequency information in graph convolutional networks.  In AAAI. AAAI Press, 2021.

##  Appendix A Symbols and notations

Table 5: Symbols and notations. Symbol | Description
---|---
$\mathcal{G}$ | Graph
$\mathcal{V}$ | Set of vertices (nodes) of the graph $\mathcal{G}$
$\mathcal{E}$ | Set of edges of the graph $\mathcal{G}$
$\mathbf{X}$ | Node feature matrix of $\mathcal{G}$.
$\mathcal{Y}$ | Set of labels of $\mathcal{G}$.
$n$ | Number of nodes in the graph $\mathcal{G}$
$\mathbf{L},\mathbf{A}$ | Laplacian matrix and adjacency matrix of $\mathcal{G}$
$\tilde{\mathbf{L}},\tilde{\mathbf{A}}$ | Normalized laplacian matrix and adjacency matrix of $\mathcal{G}$
$\mathcal{N}(v)$ | Set of neighbors of node $v$
$g(\mathbf{\Lambda})$ | A spectral graph filter of eigenvalue $\mathbf{\Lambda}$

##  Appendix B Proofs of the Theorems

See 1

###### Proof.

According to the weighted AM-GM inequality, we have

$\displaystyle\frac{g(\lambda_{0})}{\sum_{0\leq i\leq
n-1}g(\lambda_{i})}|\hat{H}_{0}|+\cdots+\frac{g(\lambda_{n-1})}{\sum_{0\leq
i\leq n-1}g(\lambda_{i})}|\hat{H}_{n-1}|$ (12) $\displaystyle\geq$
$\displaystyle|\hat{H}_{0}|^{\frac{g(\lambda_{0})}{\sum_{0\leq i\leq
n-1}g(\lambda_{i})}}\cdot\cdots\cdot|\hat{H}_{n-1}|^{\frac{g(\lambda_{n-1})}{\sum_{0\leq
i\leq n-1}g(\lambda_{i})}}$

As we have $g(\lambda_{i})\in[0,2]$ for all $i$, then

$\displaystyle\frac{\sum_{0\leq i\leq
n-1}g(\lambda_{i})|\hat{H}_{i}|}{\sum_{0\leq i\leq
n-1}g(\lambda_{i})}\geq|\hat{H}_{0}|^{\frac{1}{\sum_{0\leq i\leq
n-1}g(\lambda_{i})}}\cdot\cdots\cdot|\hat{H}_{n-1}|^{\frac{1}{\sum_{0\leq
i\leq n-1}g(\lambda_{i})}}$ (13) $\displaystyle=$ $\displaystyle\prod_{0\leq
i\leq n-1}|\hat{H}_{i}|^{\frac{1}{\sum_{0\leq k\leq n-1}g(\lambda_{k})}}$

Since both sides of the inequality are greater than 0, we take the logarithm

$\log\left(\frac{\sum_{0\leq i\leq
n-1}g(\lambda_{i})|\hat{H}_{i}|}{\sum_{0\leq i\leq
n-1}g(\lambda_{i})}\right)\geq\frac{1}{\sum_{0\leq k\leq
n-1}g(\lambda_{k})}\sum_{0\leq i\leq n-1}\log|\hat{H}_{i}|$ (14)

Hence completes the proof. ∎

See 1

###### Proof.

Let $\psi$ be the clamp function defined as

$\psi(x)\triangleq\min\\{\max\\{x,-1\\},1\\}=\left\\{\begin{array}[]{ll}1&x>1\\\
x&-1<x<1\\\ -1&x<-1\end{array}\right.,$ (15) $\displaystyle d(x,\psi(x))$
$\displaystyle\triangleq\left(\frac{1}{1+e^{x}}-y\right)^{2}-\left(\frac{1}{1+e^{\psi(x)}}-y\right)^{2}$
(16)
$\displaystyle\in\left\\{\begin{array}[]{ll}{[-(\frac{1}{1+e})^{2},0]}&x>1,y=0\\\
{[0,(\frac{1}{1+c})^{2}]}&x>1,y=1\\\ {[0,(\frac{1}{1+e})^{2}]}&x<-1,y=0\\\
{[-(\frac{1}{1+e})^{2},0]}&x<-1,y=1\end{array}\right.\leq\frac{1}{(1+e)^{2}},$

and for $x\in[-1,1]$, the first-order Taylor expansion of $\frac{1}{1+e^{x}}$
is $\frac{1}{2}-\frac{1}{4}x$. Denote $R(x)$ as the remainder term, that is,
$R(x)=\frac{1}{1+e^{x}}-\frac{1}{2}+\frac{1}{4}x$. since

$\left(\frac{1}{\left(1+e^{x}\right)^{2}}\right)^{\prime\prime\prime}=-\frac{e^{x}\left(-4e^{x}+e^{2x}+1\right)}{\left(1+e^{x}\right)^{4}}\leq\left.\left(\frac{1}{\left(1+e^{x}\right)^{2}}\right)^{\prime\prime\prime}\right|_{x=0}=\frac{1}{8},$
(17)

we have

$|R(x)|\leq\max\left|\left(\frac{1}{\left(1+e^{x}\right)^{2}}\right)^{\prime\prime\prime}\right|\frac{|x|^{3}}{3!}=\frac{|x|^{3}}{48}$
(18)

Therefore,

$\displaystyle\left(\frac{1}{1+e^{x}}-y\right)^{2}=\left(\frac{1}{1+e^{\psi(x)}}-y\right)^{2}+d(x,\psi(x))$
(19) $\displaystyle=$
$\displaystyle\left(\frac{1}{2}-\frac{1}{4}\psi(x)-y+R(\psi(x))\right)^{2}+\frac{1}{(1+e)^{2}}$
$\displaystyle=$
$\displaystyle\left(\frac{1}{2}-\frac{1}{4}\psi(x)-y\right)^{2}+\left(R(\psi(x))\right)^{2}+2R(\psi(x))\left(\frac{1}{2}-\frac{1}{4}\psi(x)-y\right)+\frac{1}{(1+e)^{2}}$
$\displaystyle=$
$\displaystyle\left(\frac{1}{2}-\frac{1}{4}\psi(x)-y\right)^{2}+\left(\frac{|\psi(x)|^{3}}{48}\right)^{2}+\frac{|\psi(x)|^{3}}{24}\left|\frac{1}{2}-\frac{1}{4}\psi(x)-y\right|+\frac{1}{(1+e)^{2}}$
$\displaystyle\leq$
$\displaystyle\left(\frac{1}{2}-y\right)^{2}-\frac{(1-2y)\psi(x)}{4}+\frac{\psi(x)^{2}}{16}+\frac{|\psi(x)|^{6}}{2304}+\frac{|\psi(x)|^{3}}{24}\left(\frac{1}{4}|\psi(x)|+\frac{1}{2}\right)+\frac{1}{(1+e)^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{1}{4}-\frac{(1-2y)\psi(x)}{4}+\frac{\psi(x)^{2}}{16}+\frac{|\psi(x)|^{3}}{48}+\frac{\psi(x)^{4}}{96}+\frac{|\psi(x)|^{6}}{2304}+\frac{1}{(1+e)^{2}}$

According to the above conclusion,

$\displaystyle
Er\left(\mathbf{x}_{0},\mathbf{y}_{0}\right)=\sum_{l}\left(\frac{1}{1+e^{g(I-\tilde{\mathbf{A}})\left(\mathbf{x}_{1l}-\mathbf{x}_{0l}\right)}}-\mathbf{y}_{0l}\right)^{2}$
(20) $\displaystyle\leq$
$\displaystyle\frac{n}{4}-\frac{1}{4}\left(\mathbf{y}_{1}-\mathbf{y}_{0}\right)^{\top}\psi(\mathbf{z})+\frac{\|\psi(\mathbf{z})\|_{2}^{2}}{16}+\frac{\|\psi(\mathbf{z})\|_{3}^{3}}{48}+\frac{\|\psi(\mathbf{z})\|_{4}^{4}}{96}+\frac{\|\psi(\mathbf{z})\|_{6}^{6}}{2304}+\frac{n}{(1+e)^{2}}$

$\mathbf{z}=g(I-\tilde{\mathbf{A}})(\mathbf{x}_{1}-\mathbf{x}_{0})_{l}$ ,
noting that
$C\leq\|\psi(\mathbf{z})\|_{6}^{6}\leq\|\psi(\mathbf{z})\|_{4}^{4}\leq\|\psi(\mathbf{z})\|_{3}^{3}\leq\|\psi(\mathbf{z})\|_{2}^{2}\leq
n$, then we have

$\displaystyle
Er\left(\mathbf{x}_{0},\mathbf{y}_{0}\right)\leq\frac{n}{4}-\frac{1}{4}\left(\mathbf{y}_{1}-\mathbf{y}_{0}\right)^{\top}\psi(\mathbf{z})+\frac{217}{2304}\|\psi(\mathbf{z})\|_{2}^{2}+\frac{n}{(1+e)^{2}}$
(21) $\displaystyle=$ $\displaystyle
c_{1}n-\frac{1}{4}\sum_{l}\psi\left((\mathbf{y}_{1l}-\mathbf{y}_{0l})(g(I-\tilde{\mathbf{A}})(\mathbf{x}_{1}-\mathbf{x}_{0})_{l})\right)$

where $c_{1}$ is a constant. For any $\eta$, we construct
$\tilde{\eta}_{i}=\psi_{\frac{1}{g\left(1-\lambda_{i}\right)\delta_{i}}}\left(\eta_{i}\right)$
such that
$\left|\tilde{\eta}_{i}g\left(1-\lambda_{i}\right)\delta_{i}\right|\leq 1$ and
$\sum_{i\in\mathcal{I}_{g,\delta,\eta}}\psi\left(\eta_{i}g\left(1-\lambda_{i}\right)\delta_{i}\right)=\sum_{i\in\mathcal{I}_{g,\delta,\delta,\tilde{\eta}}}\tilde{\eta}_{i}g\left(1-\lambda_{i}\right)\delta_{i}$.
We define
$m_{g}\triangleq\min_{i\in\mathcal{I}_{g,\delta,\eta}}\tilde{\eta}_{i}\delta_{i}$.
From the proof of Lemma 1, for any $g(\cdot)$ and $\delta$, we have

$\displaystyle\sum_{i=0}^{n-1}\psi\left(\eta_{i}g\left(1-\lambda_{i}\right)\delta_{i}\right)=\sum_{i\in\mathcal{I}_{g,\delta,\eta}}\psi\left(\eta_{i}g\left(1-\lambda_{i}\right)\delta_{i}\right)=\sum_{i\in\mathcal{I}_{g,\delta,\tilde{\eta}}}\tilde{\eta}_{i}g\left(1-\lambda_{i}\right)\delta_{i}$
(22) $\displaystyle\geq$ $\displaystyle
m_{g}\sum_{i\in\mathcal{I}_{g,\delta,\tilde{\eta}}}g\left(1-\lambda_{i}\right)=m_{g}\left(\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}g\left(1-\lambda_{i}\right)+\sum_{i\in\mathcal{I}_{g}}g\left(1-\lambda_{i}\right)-\sum_{i=0}^{n-1}g\left(1-\lambda_{i}\right)\right)$
$\displaystyle=$ $\displaystyle
m_{g}\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}g\left(1-\lambda_{i}\right)\geq
m_{g}\frac{\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}\log|\hat{H}_{i}|}{\log\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}g\left(1-\lambda_{i}\right)|\hat{H}_{i}|-\log\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}g\left(1-\lambda_{i}\right)}$

According to Eq. 21 and Eq. 22, we have

$\displaystyle\overline{Er}(\mathbf{X},\mathbf{Y})=\frac{1}{n}\|\sigma(g(I-\tilde{\mathbf{A}})\mathbf{X})-\mathbf{Y}\|_{F}^{2}=\frac{2}{n}Er\left(\mathbf{x}_{0},\mathbf{y}_{0}\right)$
(23) $\displaystyle\leq$ $\displaystyle
c_{1}-\frac{\min_{i\in\mathcal{I}_{g,\delta,\eta}}\psi_{\frac{1}{g\left(1-\lambda_{i}\right)\delta_{i}}}\left(\eta_{i}\right)\cdot\delta_{i}\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}\log|\hat{H}_{i}|}{2n\log\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}g\left(1-\lambda_{i}\right)|\hat{H}_{i}|-2n\log\sum_{i\in\mathcal{I}_{\delta,\tilde{\eta}}}g\left(1-\lambda_{i}\right)}$

∎

##  Appendix C Algorithm

Algorithm 1 GPatcher Framework

1:source graph $\mathcal{G}(\mathcal{V},\mathcal{E},\mathbf{X})$; adjacency
matrix $\mathbf{A}$; patch size $p$; layer number $m$

2:$\mathcal{Y}$

3:$\triangleright$ Preprocessing:

4:$\tilde{\mathbf{A}}\leftarrow\text{Normalization}(\mathbf{A})$

5:$\Lambda,\mathbf{U}\leftarrow\text{EigenDecomposition}(\tilde{\textbf{A}})$

6:$\triangleright$ Patch Extractor $\phi$:

7:$\mathbf{R}\leftarrow\mathbf{U}g(\Lambda)\mathbf{U}^{T}$ $\triangleright$
Compute patch extractor score matrix

8:$\mathbf{P}\leftarrow\mathbf{X}[\text{top-}p_{col}(\mathbf{R},p)]$
$\triangleright$ Extract top-$p$ nodes columnwise from patch extractor score
matrix

9:$\mathbf{P}^{0}\leftarrow\mathbf{P}$$\triangleright$
$\mathbf{P}\in\mathbb{R}^{n\times p\times d}$

10:$\triangleright$ Patch Mixer:

11:for $i\leftarrow 1$ to $m$ do

12:
$\mathbf{P}^{i}\leftarrow\sigma(\text{MLP}(\text{LayerNorm}(\mathbf{P}^{i-1}),\boldsymbol{\theta}^{i}_{\text{feature}}))$
$\triangleright$ Mixing along feature dimension

13:
$\mathbf{P}^{i}\leftarrow\sigma(\text{MLP}(\text{LayerNorm}(\mathbf{P}^{i}),\boldsymbol{\theta}^{i}_{\text{patch}}))$
$\triangleright$ Mixing along patch dimension

14:$\mathcal{Y}\leftarrow\text{MLP}(\text{Aggregate}(\mathbf{P}^{m}),\theta_{\text{predict}})$$\triangleright$
Aggregate along patch dimension and predict node label

15:return $\mathcal{Y}$

In the standard GPatcher framework, we generate patches
$\mathbf{P}=\\{\mathbf{P}_{v}:v\in\mathcal{V}\\}$ for all nodes using patch
extractor $\phi$, mix $\mathbf{P}$ using multiple layers of patch mixer
operations to obtain $\mathbf{P}^{m}$ and predict node labels $\mathcal{Y}$
using aggregated $\mathbf{P}^{m}$. We first preprocess the data by normalizing
A and then extracting $\mathbf{\Lambda}$ and U from $\tilde{\textbf{A}}$. We
then apply the patch extractor $\phi$ and selecting on $\mathbf{X}$ to our
graph, yielding patches of size $[n\times p\times d]$, where $n$ is the number
of nodes, $p$ is the patch size, and $d$ is the dimension of the input node
features. Each patch, represented by a $[p\times d]$ matrix, encapsulates the
extracted features from a node and its top $p$ neighboring nodes. The
resulting patches are subsequently processed by a feature-mixing layer, which
utilizes a Multilayer Perceptron (MLP) followed by Layer Normalization and an
arbitrary activation function to operate on the $d$-dimension. This results in
a tensor of size $[n\times p\times d]$. To further mix information across all
nodes in the patch, a patch-mixing layer is applied on the $p$-dimension using
another MLP. This mixing process passes $\mathbf{P}$ through $m$ layers to
construct $\mathbf{P}^{m}$. Finally, we aggregate along the patch dimension
$p$ of $\mathbf{P}^{m}$ using an arbitrary aggregation function which gives us
the final representation of size $[n\times d]$. By further applying MLP to
this final representation, we classify the label of each node which is the
size of $[n\times|\mathcal{Y}|]$.

Algorithm 2 Fast-GPatcher Framework

1:source graph $\mathcal{G}(\mathcal{V},\mathcal{E},\mathbf{X})$; adjacency
matrix $\mathbf{A}$; patch size $p$; layer number $m$; dangling scalar $c$

2:$\mathcal{Y}$

3:$\triangleright$ Preprocessing:

4:$\tilde{\mathbf{A}}\leftarrow\text{Normalization}(\mathbf{A})$

5:$\triangleright$ Patch Extractor $\phi_{\text{fast}}$:

6:for $v$ in $|\mathcal{V}|$ do

7: $\mathbf{r}_{v}\leftarrow\text{Minimize}~{}\mathcal{J}(\mathbf{r}_{v})$
given $\mathbf{A},c$ $\triangleright$ Eq 8

8:$\text{Compute}~{}\mathbf{R}~{}\text{by stacking}~{}\textbf{r}_{v}$

9:$\mathbf{P}\leftarrow\mathbf{X}[\text{top-}p_{col}(\mathbf{R},p)]$
$\triangleright$ Extract top-$p$ nodes column-wise from patch extractor score
matrix

10:$\mathbf{P}^{0}\leftarrow\mathbf{P}$$\triangleright$
$\mathbf{P}\in\mathbb{R}^{n\times p\times d}$

11:$\triangleright$ Patch Mixer:

12:for $i\leftarrow 1$ to $m$ do

13:
$\mathbf{P}^{i}\leftarrow\sigma(\text{MLP}(\text{LayerNorm}(\mathbf{P}^{i-1}),\boldsymbol{\theta}^{i}_{\text{feature}}))$
$\triangleright$ Mixing along feature dimension

14:
$\mathbf{P}^{i}\leftarrow\sigma(\text{MLP}(\text{LayerNorm}(\mathbf{P}^{i}),\boldsymbol{\theta}^{i}_{\text{patch}}))$
$\triangleright$ Mixing along patch dimension

15:$\mathcal{Y}\leftarrow\text{MLP}(\text{Aggregate}(\mathbf{P}^{m}),\theta_{\text{predict}})$$\triangleright$
Aggregate along patch dimension and predict node label

16:return $\mathcal{Y}$

In the Fast-GPatcher framework, we generate patches
$\mathbf{P}=\\{\mathbf{P}_{v}:v\in\mathcal{V}\\}$ for all nodes using patch
extractor $\phi_{\text{fast}}$, mix $\mathbf{P}$ using multiple layers of
patch mixer operations to obtain $\mathbf{P}^{m}$, and predict node labels
$\mathcal{Y}$ using aggregated $\mathbf{P}^{m}$. The patch extraction process
involves minimizing an objective function, as described in Eq 8, to obtain the
patch extractor scores $\mathbf{r}_{v}$ for each node $v$. These scores are
then stacked to form the patch extractor score matrix $\mathbf{R}$. The
dangling scalar $c$ controls the balance between local and global information
integration during the patch extractor score computation. When $c$ is lower,
the focus of the patch extractor score matrix $\mathbf{R}$ is more localized,
prioritizing local structural information. On the other hand, when $c$ is
higher, the patch extractor score matrix $\mathbf{R}$ emphasizes global
structural information and captures more long-range dependencies in the graph.
The choice of $c$ allows for a trade-off between local and global information
integration, enabling the framework to adapt to different graph
characteristics and learning objectives. The rest of the framework remains the
same as the standard GPatcher framework.

##  Appendix D Statistics of Datasets

Dataset | $\mathcal{|V|}$ | $\mathcal{|E|}$ | $|\mathcal{Y}|$ | $|\mathbf{X}|$ | $\frac{\sum{H_{i}}}{n}$
---|---|---|---|---|---
Homophily | Cora | 2708 | 5278 | 7 | 1433 | 0.19
Citeseer | 3327 | 4676 | 6 | 3703 | 0.26
Pubmed | 19717 | 44327 | 3 | 500 | 0.2
Heterophily | Texas | 183 | 295 | 5 | 1703 | 0.89
Squirrel | 5201 | 198493 | 5 | 2089 | 0.78
Chameleon | 2277 | 31421 | 5 | 2325 | 0.77
Cornell | 183 | 295 | 5 | 1703 | 0.89
Wisconsin | 251 | 499 | 5 | 1703 | 0.84
Actor | 7600 | 33544 | 5 | 931 | 0.76
Table 6: Dataset Statistics of homophily and heterophily graph datasets. The
table is divided into two sections. The top section represents homophily graph
datasets, where the graphs exhibit similar attributes and connectivity
patterns within nodes of the same class. The bottom section represents
heterophily graph datasets, where the graphs exhibit diverse attributes and
connectivity patterns across different classes of nodes. The columns show the
number of nodes ($\mathcal{|V|}$), the number of edges ($\mathcal{|E|}$), the
number of unique classes ($|\mathcal{Y}|$), the feature dimension
($|\mathbf{X}|$), and the average heterophily score ($\frac{\sum{H_{i}}}{n}$)
indicating the level of heterophily within each dataset.

##  Appendix E Details of Parameter Settings and Tuning

We perform a grid search to find the optimal hyperparameters for our model,
including the learning rate, patch size, and filter number. The search space
is defined as follows: the learning rate
$\in\\{0.01,0.008,0.005,0.003,0.001\\}$, the patch size
$\in\\{8,16,32,64,96\\}$, and the filter number $\in\\{10,50,100,150,200\\}$.
For Fast-GPatcher, we set $c$ as 0.5 to equally weigh local and global
structural information. The optimal hyperparameters are determined based on
the performance of the validation set.