Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness–Generalization Perspective
Authors: Ming Gu
Zhuonan Zheng
Sheng Zhou
Meihan Liu
Jiawei Chen
Qiaoyu Tan
Liangcheng Li
Jiajun Bu
Venue: NeurIPS 2025 poster ()
Keywords: Heterophily
Varying Homophily
Message Passing
Graph Neural Networks
Oversmoothing
Primary area: deep_learning
TL;DR: We identify a smoothness-generalization dilemma in message passing that limits GNN universality across varying homophily and propose the Inceptive Graph Neural Network (IGNN), a universal framework to address the dilemma.

Abstract: Graph Neural Networks (GNNs) have achieved great success but are often considered to be challenged by varying levels of homophily in graphs. Recent empirical studies have surprisingly shown that homophilic GNNs can perform well across datasets of different homophily levels with proper hyperparameter tuning, but the underlying theory and effective architectures remain unclear. To advance GNN universality across varying homophily, we theoretically revisit GNN message passing and uncover a novel \textit{smoothness-generalization dilemma}, where increasing hops inevitably enhances smoothness at the cost of generalization. This dilemma hinders learning in high-order homophilic neighborhoods and all heterophilic ones, where generalization is critical due to complex neighborhood class distributions that are sensitive to shifts induced by noise or sparsity. To address this, we introduce the Inceptive Graph Neural Network (IGNN) built on three simple yet effective design principles, which alleviate the dilemma by enabling distinct hop-wise generalization alongside improved overall generalization with adaptive smoothness. Benchmarking against 30 baselines demonstrates IGNN's superiority and reveals notable universality in certain homophilic GNN variants. Our code and datasets are available at \href{https://github.com/galogm/IGNN}{https://github.com/galogm/IGNN}.

Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generaiiattio Perspective
Ming Gu * + Zhuonan Zheng* Sheng Zhou * Meihan Liu?,
Jiawei Chen Qiaoyu Tan Liangeheng Li* ; Jiajun Bu*
Zhejiang Key Laboratory of Accessible Perception and Intelligent Systems, Zhejiang University College of Computer Science and Technology. Zhejiang University
SSchool of Software Technology, Zhejiang University
tChina University of Mining and Technology 8 Department of Computer Science, New York University Shanghai
Abstract
Graph Neural Networks (GNNs) have achieved great success but are often consid- ered to be challenged by varying levels of homophily in graphs. Recent empirical studies have surprisingly shown that homophilic GNNs can perform well across datasets of different homophily levels with proper hyperparameter tuning. but the underlying theory and effective architectures remain unclear. To advance GNN uni- versality across varying homophily, we theoretically revisit GNN message passing and uncover a novel smoothness generalization smootthess--enevvllzaaaon dilemma, where increasing hops inevitably enhances smoothness at the cost of generalization. This dilemma hinders learning in high-order homophilic neighborhoods and all heterophilic ones, where generalization is critical due complex neighborhood class distributions that are sensitive to shifts induced by noise or sparsity. To address this, we introduce the Inceptive Graph Neural Network (IGNN) built on three simple yet effective design principles, which alleviate the dilemma by enabling distinct hop-wise gen- eralization alongside improved overall generalization with adaptive smoothness. Benchmarking against 30 baselines demonstrates IGNN's superiority and reveals notable universality in certain homophilic GNN variants. Our code and datasets are available at https:/giiibbcoom//gggg/////G
Introduction
Graph Neural Networks (GNNs) 14 have attracted substantial attention, achieving notable success across various domains 8 Broadly, GNNs are classified into homophilic GNNs (homoGNNs) [ and heterophilic GNNs (heteroGNNs) [10]. HomoGNNs operate under the homophily assumption, which posits that adjacent nodes tend share similar labels. In contrast, heteroGNNs are tailored for heterophilic graphs, where connected nodes are more likely to have differing labels.
However, real-world graphs do not exhibit clear dichotomy between homophily and heterophily, but instead present a continuous spectrum. As illustrated in Figure La and varying homophily appears within a single graph across hops and nodes. Therefore. generalize to different levels of homophily, rather than making separate designs for homophily and heterophily as in existing methods. Recent studies [T]] have empirically shown that homoGNNs, after hyperparameter tuning with residual connections and dropout, can outperform advanced methods designed for heterophily. This suggests that homoGNNs possess an inherent potential adapt to
essential to develop GNNs that
Cooresponding Author: liangeheng_li liw:lii.ic......o
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

varying homophily, but the underlying theory and effective architectures remain unclear. A question arises: What enables universality across varying homophity in GNNs, or even in homoGNNs?
To gain a deeper understanding, we theo- retically revisit the classic GNN message- passing process and identify novel
Edge Homophily
dilemma, as depicted in Figure Ic Here, smoothness refers to the alignment of node represen- tations within neighborhoods, while gen- eralization denotes the ability handle distribution shifts across neighborhoods. As the number of hops increases, smooth- ness inevitably rises, while generalization correspondingly declines due the in- trinsic trade-off between the two. This dilemma negligible in low-order ho- mophilic neighborhoods, where strong homophily naturally aligns with smooth- rendering generalization less criti- cal. However, it becomes detrimental in higher-order homophilic neighborhoods and all heterophilic ones. We show that strong generalization is crucial in these cases to address complex neighborhood class distributions, which are highly sensi- tive to shifts induced by noise or sparsity. Yet, it remains constrained by the increasing smoothness imposed by the dilemma. This insight suggests that resolving the muoothnes--eeerrrliittio dilemma can benefit both homophilic and heterophilic settings without requiring separate designs (Figure Idj.
seooothness-generaliin
8,
Re
Node Homophit
sepird
5
Hops
Hops
arth Dhmmr ande
(a)
(h)
Capabllity
Hanaphdy
Capabiity
Hommpliyy
Anr
15pps
Hogs
(c) Dilemma
(d) Adaptive
Figure I: Varying homophily across (a) hops or (b) nodes. Conceptual illustration of the theoretical insight: (c) Sooothness-Generalzzzaiioo dilemma identified in GNNs; (d) Expected adaptive capabilities for varying homophily.
thereby unlocking the full potential of classic GNNs and paving the way toward achieving universality.
"More is in vain when less will serve, for Nature is pleased with simplicity" [2], echoing Sir Isaac Newton, we seek to make minimal changes classic GNNs to reveal the dilemma fundamental impediment to universality. We introduce Inceptive Graph Neural Network (IGNN), where the term inceptive [33 signifies concurrent learning of multiple receptive fields. IGNN is built upon three minimal design principles: separative neighborhood transformation (SN), inceptive neighborhood aggregation (IN), and neighborhood relationship learning (NR). Theoretically and empirically, we demonstrate that these changes alleviate the dilemma from two perspectives: First, inceptive neighborhood relationship learning, IN &NR, enable GNNs to approximate arbitrary graph filters for adaptive smoothness capabilities. Second, incorporating SN allows distinct hop-wise generalization and improved overall generalization. Our main contributions are:
Theoretical Insights. We advance the theoretical understanding of GNN universality across varying levels homophily by uncovering the smoothness oetirnneesggeeeeelzzaaiooonno dilemma, providing a foundation for theoretically grounded universal designs.
Universal Framework. We introduce IGNN, a universal message-passing framework based on three minimal yet effective design principles. IGNN mitigates the dilemma without relying on specialized modules tailored for either homophilic or heterophilic graphs.
Benchmark and Empirical Findings. We establish comprehensive benchmark consisting of 30 representative baselines to assess the effectiveness of our design principles. Our results demonstrate that not only can classic GCNs enhanced with these principles achieve state-of-the-art (SOTA) performance, but also that certain existing homoGNNs inherently possess universal capabilities.
2 Related Works
Homophilic Graph Neural Networks. GNNs have demonstrated remarkable abilities in managing graph-structured data, particularly under the assumption of homophily. Traditional GNNs can be broadly categorized into two categories. Spectral GNNs, such as the GCN 22. leverage various graph filters to derive node representations. In contrast, spatial GNNs aggregate information from

---

neighboring nodes and combine it with the ego node to update representations, employing methods such as attention mechanisms [ and sampling strategies [9. Unified frameworks [14 [5] have been proposed to integrate and elucidate these diverse pessage-passing approaches. Several multi-hop techniques were proposed to address the limitations of long-range dependencies, such as residual connections [16] and jumping knowledge [17]. However, these homophilic methods are often considered less effective when dealing with heterophilic settings, while a recent empirical study shows its potential to universality 117y but lacks theoretical understanding.
Heterophilic Graph Neural Networks. Addressing the challenges posed by heterophily, several innovative approaches have been proposed: (1) Neighborhood extension: Techniques such as high-
order neighborhood concatenation [10 18] neighborhood discovery [19], neighborhood refinement
[20]. and global information capture
(2) Neighborhood discrimination: Methods including [2 ego-neighbor separation [0), and hetero-/homo- -pilly neighbor-
ordered neighborhood encoding
hood separation [23] (3) Fine-grained information utilization: Strategies such as multi-filter signal
usage 24 25 intermediate layer combination [0,, and refined gating or attention mechanisms
[26]. These methods generally retain the practice of message passing [27 that aggregates multi-hop neighborhood information. However, these methods often treat homophily and heterophily separately, leading paradox: effectively separating them would require prior knowledge of node labels, while it is precisely the labels that need to be learned. A holistic understanding is needed to guide the development of architecture that adapts to both settings without different treatments.
Oversmoothing, Heterophily and Generalization. Early studies 28 30 investigate oversmoothing or generalization without considering varying homophily, while later works reveal that oversmooth- ing and heterophily are often intertwined leaving generalization unexamined. Bodnar al. [31 attribute both oversmoothing and heterophily to the underlying graph geometry using sheaf- based formulation. Park et al. [32] counter the two by reversing the diffusion process, yet their approach remains architecturally motivated without theoretical insight into generalization. Meanwhile, sev- models [22]
eral heterophily-oriee oversmoothing-foot focused designs [6 34 also perform well under heterophily. In contrast, Ma et al. 335 explore the link between heterophily and generalization while omitting oversmoothing. In sum- mary, existing studies have examined all pairwise combinations among oversmoothing, heterophily, and generalization, yet no unified framework has bridged all three. We fill this gap through a unified theoretical lens, demonstrating that the issues of oversmoothing, poor generalization, and heterophily all stem from a shared underlying trade-off between smoothness and generalization, thereby offering principled foundation for unified understanding and guides the design of more universal GNNs.
23
33
have been shown to alleviate oversmoothing, while
3 Notations and Preliminaries
Given an undirected graph G(V, X, A, with the node set V = (vi..... ] and feature matrix X [xo...., XN] E R ND the edge set & is represented by the adjacency matrix A E NNN Aij if (ti, Uz) E, otherwise Aij O. The degree matrix D diag(d), dN) E N d, = ΣS Aiy. The re-normalization A is A = D (A - IN D +, where Iy is the identity ma- trix. The symmetrically normalized graph Laplacian matrix f. IN- A. Edge and node homophily computed as: he (1/(El) Eoseypes 1(c, cj), hn 1/N EM,D Eiorn Il(c. cj)/d4.
3.1 Smoothness of GNNs
Oono and Suzuki 29 describe the smoothness characteristic of GNNs with information loss from X on asymptotic behaviors of GNNs from a dynamical systems perspective. They demonstrate that when it extends with more layers, the GNN representation (i.c., H a (A see Section 4
exponentially approaches information-less states, which is a subspace M in Definition 3.1
Definition 3.1 (subspace). Let M == {EB E MxD] be an M-dimensional subspace in NXD, where E e N is orthogonal, i.c. E E = IM, and M < N.
Following their notations, we denote the maximum singular value of w(O) by and set = supieN, st. Denote the distance that induced as the Frobenius norm from X to M by dx((X) == infyem || Y|IF= = D. The following Corollary 3.2 shows the information loss as layer I goes.

---

Corollary 3.2 (Oono and Suzuki (29).. Let λ S... be the eigenvalues of A, sorted in ascending order. Suppose the multiplicity of the largest eigenvalue AN M ( N). L.e, NN-M M <
AN-M+1 = AN and the second largest eigenvalue defined as == max N-M |aal < [AN
n=1
Let E to be the eigenspace associated with AN -M+1 AN. Then have X < AN 1, and
dm ( S spdds (H
(1)
where M E BE BRRD). If SLÀ < 1, the 1-th layer output exponentially approaches M.
Greater smoothness with larger information loss is indicated by a smaller distance d' (H (rom the representations to the subspace M [29]. This is because the subspace denotes the convergence state minimal information retained from the original node features X, with the only information
of the connected components and node degrees of A. This means that for any Y E M, two nodes ti f/j V are in the same connected component and their degrees identical, then the corresponding column vectors of Y are identical, i.c., they cannot be distinguished.
3.2 Generalization of GNNs
GNN generalization can be governed by the Lipschitz constant as discussed in existing works 33 37]: Definition 3.3 (Lipschitz constant). A function R + R is called Lipschitz continuous if there exists constant L such that Vı, y E I"" [lf f I L||. yll2, where the smallest L for which the previous inequality is true is called the Lipschitz constant of f and denoted L.
Better generalization is exhibited by GNNs with a smaller Lipschitz constant 38 This paper does not discuss generalization graph domain adaption [39), but discusses generalization regarding inherent structural disparity [40] and data distribution shifts from training to test sets (38].
Theoretical Analysis of Classic GNNs
Generally, GNNs capture multi-hop information by stacking message-passing (MP) layers
h (0) = X.s m
(k)
((h (k-1) (())( h*) COM (k. m (1)))
where h is the hidden representation and m
(k) is the message for node v in the k-th layer. AGG(-) and COM(-) denote the aggregation and combination function, while N(w) is the set of neighbors adjacent to node v. Denoting (*) [bg
D E RNF the widely used GCN implementation can be written as H = o (H
(k) h,,hh (k)
where (-)) is the activation function.
4.1 Smoottness-Genneraliattooo Dilemma
The following Theorem 4.1 reveals dilemma in classic GCNs of & layers. See proof in Appendix A. Theorem 4.1. Given graph 9(X, A), let the representation obtained via rounds of GCN message passing symmetrically normalized A be denoted H a ((HH(--))())) and the Lipschitz constant of this k-layer graph neural network be denoted as Lc. Given the distance from X to the subspace M as (X) = DD then the distance from H!A to M satisfies:
dm(HH S LG\'D
where L. IT W and X < 1 is the second largest eigenvalue of A. (k))
Corollary 4.2. VLG.e > 0, 3k [(log // log X1, such that (H where [.] is the ceil of the input.
Remark. As D is constant with respect to X, we observe that the distance is upper- houereb by three factors: the second largest eigenvalue of A, the Lipschitz constant LG corresponding to the norm of the product of all W and the layer depth k. Several conclusions can be drawn.

---

First, there exists amoothness--eeeealizaatie dilemma. Since lime-+oo A = 0, La has to rise when l increases prevent d (M G from convergent to O. This is evidenced by the upper bound of the Lipschitz constant continuing to increase as training progresses [37]. However, a large LG implies reduced generalization, leading to a significant performance gap between training and test accuracy [8]. Consequently, either oversmoothing or poor generalization will occur at large k.
Second, from Corollary 4.2 we see that for any given La there exists a le such that the distance from the representations to the subspace is smaller than any arbitrarily small Thus, extremely small distance with indistinguishable representations becomes inevitable for sufficiently large k, as LG computing from weight matrices can not be infinitely large due to the finite computational precision.
In summary, although oversmoothing has been associated with generalization before 229,, this dilemma reveals a more intricate balance in an either-or situation. When the classic GCN attempts to counter oversmoothing and recover discriminative representations from the over-smoothed A X by increasing the spectral norm of W(), the resulting larger Lipschitz constant inevitably worsens generalization. Conversely, constraining the norm of W to maintain a low Lipschitz constant and preserve generalization prevents the model from effectively reversing the over-smoothed A X yielding indistinguishable node embeddings. This interplay constitutes the core of the smooth- ness-generalization dilemma: efforts improve one aspect inherently compromise the other.
4.2
How this Dilemma Hinders Performance across Varying Homophily
Next, we bridge the pogoohness-generalizaatee dilmma with varying homophily to elucidate the intrinsic relationship among oversmoothing, generalization, and heterophily. In essence, graph learning requires adaptive capabilities in both smoothness and generalization for neighborhoods of varying homophily. Table Sooleessmmaane summarizes these dilemma impacts.
In homophilic settings, the dilemma pri- marily affects high-order neighborhoods, whereas low-order ones are less impacted. This can be intuitively understood as smoothness and generalization aligning in low-order homophilic neighborhoods, which always favors pulling together the representations of same-label nodes within these hops. However, smoothness begins to conflict with generalization in high orders of low or varying homophily, as bringing closer nodes of different labels in these neigh- borhoods is detrimental. This discrepancy generalization is clearly exemplified in PMLP 42
Table 1: Dilemma Impacts. S. and G. are short for smoothness and generalization, while +, - and ~ denote strong, poor and adaptive capability. O means inconse- quential (when S. aligns with the homophily bias).
Homoopily
Oversmovrhing
Low Orders
Hlgh Orders
Heterphily
Mised
G.
G.
Classic MP
Cupabality
Learning
Homo
high
Inn/harying
Requirements
Hetero
low/vayyng
lowiaarinng
In heterophilic settings, the dilemma ex- hibits negative effects across both low- and high-order neighborhoods. First, the complex neighborhood class distribu- tion (NCD) (35) in heterophilic neighbor- hoods makes easy for noise or even sparsity to result in mismatched or in- complete NCDs for nodes of the same label, which requires strong generaliza- tion ability to mitigate. A toy example demonstrates that heterophilic in Figure 2
Shop
sparsifled
class
class
(4) Homophily
(by Heterophily
#0
Sparsity
Sparsity
#1
#2
Figure 2: Toy Example of the Sparsity Influence. Three nodes the same positions are sparsified from the (a) homo- and (b) hetero-philic neighborhoods of the same structure. Statistics of the neighborhood information and NCD shift variances s² are presented as:
neighborhoods suffer from larger NCD) shifts caused by the same sparsity, ev- idenced by larger distribution variances 2 heeter both in hop I and 2 compared to those Siomo of homophilic neighbor- hoods. Second, there greater struc- tural inconsistency between the training
Neighees SCD
Naglors
CCD
Nailoar C. NCD Seighves
C. NCD
dls
11
11
1.
11F 11
D.
131 m1
B.
DII
Iop 150
(1,000
20
5.5
Iop 2
18001041
RA030
bop
#F
and test sets in heterophilic graphs compared to homophilic ones 40 as heterophilic graphs exhibit
mixture of homophilic and heterophilic patterns, which also requires good generalization.
5

---

In summary, the core insight is that challenges are posed by the smoothness generalization dilemmaa in both homophily and heterophily, resulting in the absence of universality across varying homophily.
smoothmes--ennralizaaee
Making Classic GNNs Strong Baselines: Inceptive Message Passing
An intuitive approach to addressing the dilemma is to (1) decouple smoothness and generalization from a rigid trade-off, endowing them with the capacity to adapt independently to varying homophily; and (2) preserve the embeddings of low/nedium orders, acknowledging that oversmoothing is inevitable at sufficiently large hops. To this end, we propose unified message-passile termed Inceptive Graph Neural Networks (IGNN), which is designed to realize this adaptivity with minimal cost. Instead of introducing additional complex modules, IGNN can easily empower even the classic GNNs by addressing the dilemma through three simple yet effective design principles.
architecture
5.1 Inceptive GNN Framework (IGNN)
Separative Neighborhood Transformation (SN) avoids sharing or coupling transformation layers across neighborhoods: h = f(x) (x.) x. W(A), where f(() (-) is the transformation for the k-th neighborhood. The absence of SN implies all k-hop neighborhood transformations either share the same parameters W or are cascade-coupled in a multiplicative manner, such as II; W (see Appendix D.I.. This design aims to capture the unique characteristics of each neighborhood, enabling personalized generalization capability with distinct Lipschitz constants for each neighborhood.
Inceptive Neighborhood Aggregation (IN) simultancously embeds different receptive fields:
(k) = AGG (R) ( ((h!.) ( u E N(*h))) where (GG (-) represents the neighborhood aggrega-
me
tion function of the k-th hop. The simplest approach involves partitioning the k-th order rooted tree of
neighborhoods into distinct neighborhoods A/! (A*) with AA = [v) The inceptive na- ture of the architecture preserves the embedding of low orders and prevents high-order neighborhood representations from being computed based on low-order ones, which avoids cascading the learning of different hops and propagating errors if one becomes corrupted. Morcover, it prevents the product- type amplification of the Lipschitz constant (Theorem 4.1 and 5.3). which would otherwise limit the generalization ability. Notably, some dynamic message-passingg methods [18 43 unconstrained by the fixed neighborhood structure A can be viewed as advanced variants of inceptive architectures with skip connections [17 44 However, as goal is to enhance classical GNNs with minimal overhead rather than adopt complex dynamic aggregations, we do not employ them in IGNN
Neighborhood Relationship Learning (NR) adds neighborhood- wise relationship learning module to learn the correlations among neighborhoods: h, REL (mm (4) 0 < k K)). where REL(-)
is the relationship learning function of multiple neighborhoods. The relationships among various neighborhoods represent a new characteristic in IGNN, extending the combination field from a single neighborhood of ego and neighboring nodes in COM(-) to multiple neighborhoods of various hops in (- Based on the learning mechanism of relationships, IGNN can be divided into three variants.
A brief overview of the variants is pre- sented in Table 2 with a comparison in Appendix D.I The classic GCN AGG(-) is consistently used, and lay- ers formed by these three principles can be further stacked. Other AGG(-) can be applied, but as long as they can achieve GCN, the introduced advan- tages of IGNN always hold. Table and 10 illustrates how existing works falls into IGNN variants.
Table 2: Three IGNN variants with GCN AGG().
SN b
IIGNN
Coupled or shared Wie).
Ea(As,ni
( w be
IINN
h: ob
I-NN
x, W
EojAe, ("))
h [ (.)
Residual I-IGNN variants leverage the residual connection [45) as: (a( = ( (K) ()()) + +h (t-1)
whose matrix format is H (8) = o (k) + ( 1), It is easy to observe that the expansion of (b) covers all Á < i < & (see Appendix A.2), which is an inceptive variant with IN &NR designs. Besides, some methods [46] [6] adopt an initial residual connection, constructing connections to the initial representation (0) (see Appendix D.2). Luo al. [T] empirically demonstrated that this variant equipped with dropout and batch normalization establishes strong bascline, but the theoretical

---

rationale remains unclear. Our work extends this understanding by explaining its effectiveness under varying homophily through the lens of the amoothness-generalizze
dilemma. We first prove its adaptive smoothness capability in Theorem 5.1 and further expose its inherent generalization limitations via quantitative analysis in Section 5.2.3 thereby elucidating the necessity of dropout and
batch normalization, which can improve generalization and prevent feature collapse [47].
Attentive a-IGNN variants leverage the attention mechanism to realize node-wise personalized neighborhood relationship learning, defined as: h = Oe m (k)
+ (1 Ctv "h where
(R)
(*) (m. (8) he D) and (-) is the mechanism function. Several methods, such as
Oh
g
DAGNN 48). GPRGNN [3], ACMGCN [24], and OrderedGNN [22]. employ different attention
mechanisms yet unintentionally share the same IN &NR design.
Concatenative c-IGNN variants concatenate multi- neigh-eeigh with a learnable transformation:
h, - (11 (m )))). where || means concatenation. A c-IGNN with GCN AGG(.) is HIG.A = (All5
w E RDx and W E R*FxFF,, Although simple, its power is strong, as can achieve various relationships, such as general layer-wise neighborhood mix- ing, personalized and generalized PageRank as in Proposition 5.2 Notably, when SN is incorporated in c-IGNN, the REL(-) becomes optional, as the SN and NR transformations can be merged.
5.2 Theoretical and Empirical Analysis of Dilemma Alleviation
5.2.1 IN &NR: Adaptive Smoothness Capabilities
Theorem 5.1. Inceptive neighborhood relationship learning (IN &NR) can approximate arbitrary graph filters for adaptive smoothness capabilities extending beyond simple low- or high-pass ones, expressing the K order polynimial graph filter (Ei=n O,L') with arbitrary coefficients 0,, including c-IGNN (SN, IN and NR), as well as r-IGNN and a- (IN &NR).
Proposition 5.2. IGNN-s can achieve (1) SIGN, (2) APPNP with personalized PageRank, (3) MixHop with general layerwise neighborhood mixing, and (4) GPRGNN with generalized PageRank.
Remark. Wu et al. 49 found that the vanilla GCN essentially simulates K-order polynomial filter [50] with predetermined coefficients, limited to a low-pass filter. However, many works has highlighted the significance of high-frequenc signals for heterophily [14 The inceptive neighborhood relationship learning module (IN +NR) benefits IGNN with the expressive power beyond simple low-pass or high-pass filters as in Theorem 5.1 achieving the K-order polynomial graph filter with arbitrary coefficients, which has been proven able to approximate any graph filter (52) Consequently, many existing methods are just simplified cases of IGNN as Proposition 5.2.
5.2.2 SN: Improved Hop-wise and Overall Generalization
Theorem 5.3. Let the representation of c-IGNN incorporating the SN principle be denoted as HIG, (A and the Lipschitz constant of it be denoted as LIG. Given Wo
dx D and W
then the distance from HIG,K k to M satisfies:
Wx
d (MH &
Σ xwWWW
D.
where X < 1 is the second largest eigenvalue of A, and i. = -I WoW.22
Remark. Theorem 5.3 demonstrates the mitigation of the dilemma from two perspectives. From the local perspective, each i-th hop has a distinct Lipschitz constant with isolated transformations (W()),) allowing for a separate handle of its own generalization expectations. High-order homophilic neighborhoods with extremely small X' demand large Lipschitz constants to mitigate massive information loss from oversmoothing, while low-order heterophilic ones can enjoy small Lipschitz constants to guarantee good generalization. From the global perspective, the entire network's 's Lipschitz constant is effectively shrunk from cascade multiplication to summation, avoiding the extreme decline in overall generalization ability. The overall Lipschitz constant is summation of individual multiplication of each layer transformation (LIG - w well2) in c-IGNN,
7

---

squirrl
10
10
20
Vasilla GCN
10'
Vanilli P4GNN
H4GNN
16
10a
20
60
LayersHope
Lagess Bops
Figure 3: Quantitative Analysis on the Cora (Homophily) and Squirrel (Heterophily) Datasets.
whose increase in magnitude will be much smaller than that of cascade multiplication LG I w in the traditional framework, which will grow exponentially as the layer increases since each high-order neighborhoods suffering from oversmoothing all demand large W(1),
5.2.3 Quantitative Analysis on Smoothhnss-GGenerlliiiiie Delimma
We conducted a quantitative study of the dilemma using three GNNs on the Cora and Squirel dataset: (I) vanilla GCN. (2) r-IGNN (IN and NR), and (3) c-IGNN (IN, NR, and SN). The trends of presented in Figure
d H ()) and Lipschitz constant f., computed following Cong al. 53
First, as l increases in vanilla GCN, (H) initially decreases (indicating increased smoothness) before rising again due to strong supervision from the classifier. In contrast, f. follows inverse pattern. This behavior aligns with the penattnness-geeraliiatttin alleviates oversmoothing, as evidenced by the increased d (M(())) exhibits steadily increasing i., suggesting degraded generalization. Finally, c-IGNN, which integrates all three principles, demonstrates stable and moderate trends in both d (H)) and L, indicating its ability to preserve generalization while avoiding excessive smoothness. See Appendix for more details.
dilemma. Second, ,hile r-IGNN
6 Experiments
Research questions are: RQI: How does IGNN perform compared to SOTA methods? RQ2: What the contributions of the three principles? RQ3:
How is the dilemma resolved across various hops?
6.1 Datasets, Baselines and Settings
Following recent works [54], we select 13 representative datasets of various sizes, excluding those too small or class-imbalancee 277: (i) Heterophily: Roman-empire, BlogCatalog, Flickr, Actor, Squirrel-fittered, Chameleon-filteree Amazon-ratings, Pokec; (ii) Homophily: PubMed, Photo, wikics, ogbn-arxiv, produtts. The statistics are in Table and
Datasets:
Baselines: We selected 30 representative baselines, as shown in Table II These models are categorized into four types: graph-agnostic models, homophilic GNNs, heterophilic GNNs, and graph transformers. GNNs are further divided into Non-inceptive and Inceptive ones.
Settings: We randomly construct 10 splits with proportions of 48%/32%%/20% for training/valida- tion/testing, which is guided by our theoretical emphasis on generalization. Prior work 44) has shown that different splitting strategies can lead to substantial variations in structural distributions, thereby influencing generalization behavior. To mitigate this, we adopt unified split scheme [19 22). reducing variance across datasets that may arise from the heterogeneous splitting policies used in earlier studies. For the large-size datasets (ogbn-arxiv arxiv, Pokec, and ogbn- productss.. we use the public splits. The network is optimized using the Adam [55], with hyperparameter settings provided in Appendix E..2 Our code with best hyperparamter settings and search scripts are available at http:://githubb.. https///gthub..cogggggggg/////// com/galogm/IGNNN Additional results and code for public splits are also provided in the repository. We report the mean and standard deviation of classification accuracy across splits, with complexity, paramter count and runtime analysis and comparison documented in Appendix

---

Table 3: Overall Performance of Node Classification. The best results in bold. and the second-best
results are underlined. A.R is the average of all ranks across datasets. OOM means out of memory.
Daluset
Actor
Blog
Flickr
Romun-E
SquireeFt
Chame-T
Amazoo R
Pubmed
Photo
Wikiss
0/2008
0,2072
0,2357
1,7014
07272
078333
4FAges
#Nudes
38,544
7,600
171,742
5,186
239.288
7,575
22,662
32,927
2.224
8.854
890
24,092
97,050
19.777
44,388
238
7,650
431
11,70/
A.R.
8,789
12,047
300
2,089
2,325
390
500
1500
Noa.
GUN
77.
36
26.7
GAT
30
85 25.3
57.87-2m
62. 200s
36.22
40.05 40.89
$7.64
94.72
76. 76.92
28.0
Homospille
GraphSAGE
34.52.9
95. 65.75665
91 91.744
66 3943 16
34:83-224
41.24 14.244444
46.71-m
88.71
14.52
80.
23.2
APPIPT
DX 133534
71 36
41 2253225
21:3
JKNet-GUN
30.4941-11
84 44.25
71.72-144
69.61 14042
40.1
63.33.812
45.15
83.30
23.0
InceptiCN
48.09
46.674
90:42
43.3
Inwp-
MisHlop
46.05
89.78
79. 40
41
44.61.316
94.91104
83.15
15.8
FAGUN
15.98
35.98::33
95.6750
92. 02.74-mm
75.65
40.53-10
42. 04
85.00-.11
10.5
GAT
34.96
94 05
00.33 10..20m1.0 11
R0 00.9811 00
34.07 25
19
85. 17
19.1
DAGNN
35.04a1.
96. 15
1877
35.62-114
40 40.9512211
35.07-477
14.2
GUNI
35.094..0
38 28:4
13:2.
47.05
90.00+
35.15-444
13.7
13
11.33-04
01.35
25.5
Non.
GBRGNN
GGCN
25.7241
90.37 16.
00M
36.04.34
O0M
19.19
45.324057
85-15-10
23.1
Hiteephill
GleGNN
15 15
92.5 aa
88 1
70875534
15. 19
40 40.28
49.0
88.
92.1 15
84 20
23.6
HOGGUN
16.05a w
95 7
90
40
D0M
15.10-115
58 18.4
00M
00M
48 90
83.
83.57
25.5
GPRGKN
35 W5. m
01 s
72 10as
K3 16
17.5
ACMGON
35.08411
68 -
43.05.11 37.60-1138
13
19.1
Inee
OrderdGNN
91.13
36227:159
42.1 133304
51.5
90.01
.0:00mmm
72662
42
18.004112
34.07-44
16.4
37
15
UniFilter
36.11 1a
96 43
91 19
74 90
42
42.40-214
46 46.072474
15
85.4
9.6
Node2
36.10.
23.7
DIF Former
16.13 13 1
96 5
00 90
70 3eaes
41.12-10
41 99
49.35
00
95.67
84 84.27-17
13.6
SGFormer
37.36 27.36 1
96 06.8
01
42:22
44 44
60
20.75 80.75
95344
84 72
84
GOAT
35. 35.90
39,43-13
36.27 1101
48.10..4
51.47
29.85
18.3
85 .6.
14.3
Pulynormer
37.274::5
78664
01-98-474
40113-23
43,00+109
-3.35-1
89.98-43
Ourss
tnopp
-IGNN
17.541
95:24am
00
40.05:330
05.73
85.75-mm
C-GNN
38.51
97.241434
93.27
945574635
90,41
95.914039
6.2 Performance Analysis (RQ1)
From Table 3 and it is evident that IGNN incorporating all three principles consistently outperforms baselines.
Table 4: Performance on Large Datasets.
A subset of homoGNNs. which happen to be inceptive vari- ants, outperform many recent heteroGNNs, highlighting the strength of inceptive architectures in addressing the
Datnset
oghn-arsiv
pokec
oghn-prrcduets
0.66
0.44
0.8)
ehoder
169.345
1632 303
2,400,02
4Edges
1.166,213
30.622,561
123,718,200
dilemma hindering universality. Specifically, the average ranks of inceptive homoGNNs exceed those of all non- inceptive heteroGNNs, and in many cases, surpass those
#Frons
128
100
MIP
55.501611
GCN
71.54as25
74. 74.05
75.45
GAT
71.74aass
72.77=21x
79, 25
SGC
20.74acas
73.77
74.78
of inceptive heteroGNNs. These homoGNNs have been largely overlooked previously, as their designs are not tailored for heterophily. Only DAGNN and GCNII have specific features to mitigate oversmoothing. Surprisingly, the mere incorporation of inceptive designs is sufficient to achieve superior performance. This strongly suggests that the key factor limiting universality is the dilemma.
20.28
77.98:014
GPRGNN
71.40
62662-15
78.25
Node Fomerrrmer
67.72ac53
70.12..04
71.25
DIFFormer
69.85-1234
72.89
14.16
SGFormer
72.624011
73.24 94
76. 76.2419055
82.7
IGNN IIGNN
72.00133:
82.09-035
73.26:1331
32.09-011
82.04:0as
Inceptive heteroGNNs demonstrate better performance compared to non-inceptive heteroGNNs, while graph transformers also show relatively strong performance. First, inceptive heteroGNNN are mostly attentive variants employing different attention mechanisms. Interestingly, these models exhibit significant differences in performance, indicating that the design of the attention mechanism plays a critical role. Second, graph transformers excel likely because they move beyond the traditional message passing process, which utilizes the global attention mechanisms. Notably, Polynormer shows a great advantage on roman-empiin which is not observed in other datasets. Upon examination, we found it was long-chain graph derived from words, aligning with the inherent strengths of transformert transformers in natural language processing. Nevertheless, we observe an interesting insight for language graphs: for the same receptive field size k, they achieve better performance when stacking k IGNN layers than when using a single IGNN layer with RN across is hops. As we focus on general graphs and the A.R. of IGNN-s show consistent advantages, we leave such graphs to future studies.
IGNN outperforms all baselines with or without inceptive architectures, while inceptive GNNs also vary in performance, suggesting that the effectiveness is significantly influenced by whether all principles are integrated and how they are implemented. In particular, concatenative variants (e.g.. e- C-IGNN SIGN, and IncepGCN) generally outperform residual and attentive ones, with the ordered

---

Table 5: Ablation of Three Principles. A.R. denotes the average of all ranks across datasets.
SN
IN
NR
Vartian
Actor
Blog
Flickr
Roman-I:
Squirreee
Chame-f
Amazon R
Puhmed
Phato
wikles
A.R.
GCA
30.22111 124
65100-155
26.25.35
37:00
43:401355
1::0c.00
41:10035
75.20
JKNEEGUN
30.49
71.72-147
40.11.29
43.31
87.41.00
$8.39
SIGN
30. 30.36.00
26.06.00 Jnes
9131 Lo3s
$1.55.0d1
42,13 13.13
64 64.061344
52.47 025
90 29
45.53.00
35. 15.591177
3.0
KIGNN
28.49.029
02.32-0 m08
90.35 045
34.07:200
45031130
1210-11
95.3-884
85.20104)
25
gating mechanism of OrderedGNN standing out evidence that order information is crucial for capturing neighborhood relationships. However, two concatenative variants show low performance due to unique designs: original JKNet does not include ego features without propagation, and MixHop requires stacking layers, reintroducing transforamtion decoupling. Furthermore, most inceptive GNNs fail to incorporate all three principles, thereby not fully resolving the dilemma and degrading their performance on universality. See detailed comparison of inceptive GNNs in Appendix D.1
6.3 Ablation Studies of SN, IN and NR (RQ2)
Table 5 presents the ablation of the three prin- ciples. It is important to note that SN cannot be applied without IN, so the ablations do not include any combinations of SN without IN. Sev-
photo
Accuracy (%)
eral key conclusions can be drawn: First, the
best performance is achieved when all princi-
ples are applied, as c-IGNN obtains the high-
est average rank (Rank 1) (line 6 vs. others).
GOON
GAT
Second, JKNet-GCN shows a significant per- formance gap depending on IN (line 3 vs. line 5), where the difference lies in whether each hop aggregated independently with the ego feature transformation included. This indicates that incorporating IN and the ego representation into the final representation enhances generaliza- tion. Third, SN and NR demonstrate excellent synergy, yielding significantly improved results when used together. Although IN is incorpo- rated in lines 6-6, adding either SN or NR alone (lines 4, 5) does not lead to the best improvement compared to incorporating both, as seen in c-IGNN (line 6).
squirre]
Accuracy (%)
10
Layens/Hlps
Figure 4: Performance of Different Hops
6.4 Performance of Different Neighborhood Hops (RQ3)
Figure illustrates various method performance across different hops. In the homophilic context (photo). many inceptive methods effectively mitigating the oversmoothing issue, such as GCNII, GPRGNN, IGNN and OrderedGNN. Conversely, in the heterophilic scenario (squirrel), most of them consistently struggle with high-order neighborhoods, as evidenced by a trend of initial improvement followed by a decline in performance. In contrast, c-IGNN exhibits notable increase in perfor- mance that stabilizes thereafter, highlighting the effectiveness of incorporating all three principles in improving hop-wise and overall generalization well alliviating the dilemma.
7 Conclusion
This paper advances GNN universality across varying homophily by identifying the smoothness- generalization dilemma. which impairs learning in high-order homophilic neighborhoods and all heterophilic ones. We propose the Inceptive Graph Neural Network (IGNN), a unified message- passing framework built on three key design principles: separative neighborhood transformation. inceptive neighborhood aggregation, and neighborhood relationship learning. These principles alleviate the dilemma by enabling distinct hop-wise generalization, improving overall generalization, and approximating arbitrary graph filters for adaptive smoothness. Extensive benchmarking against 30 baselines demonstrates IGNN superiority and reveals notable universality certain homophilic GNN variants. For limitation discussion, please refer to Appendix F
10

---

Acknowledgments and Disclosure of Funding
This work is supported by the National Natural Science Foundation of China (Grant No. 62476245), Zhejiang Provincial Natural Science Foundation of China (Grant No. LTGG23F030005)
References
[1] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61 2008.
[2] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1rXiv:1609.02900 2016.
[3] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. stat, 1050(20)10-48888 2017.
[4] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. International conference on machine learning, pages 1263-1272. PMLR, 2017.
[5] GuanJun Liu, Jing Tang, Yue Tian, and Jiacun Wang. Graph neural network for credit card fraud detection. In 2021 International Conference Syber-Physicall Social Intelligence (ICCSI), pages 1-6. IEEE, 2021.
[6] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pages 417-426, 2019.
[7] Zeyu Fang, Ming Gu, Sheng Zhou, Jiawei Chen, Qiaoyu Tan, Haishuai Wang, and Jiajun Bu. Towards unified framework of clustering- based anomaly detection. arXiv preprint arXiv:2406.0044 00452, 2024.
[8] Siyi Lin, Chongming Gao, Jiawei Chen, Sheng Zhou, Binbin Hu, Yan Feng, Chun Chen, and Can Wang. How do recommendation models amplify popularity bias? an analysis from the spectral perspective. In Proceedings of the Eighteenth ACM International Conference on Web Search and Data Mining, pages 659-668, 2025.
[9] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[10] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
[11] Yuankai Luo, Lei Shi, and Xiao-Ming Wu, Classic gnns are strong baselines: Reassessing gnns for node classification. arXiv preprint arXiv:2406.0888 089933 2024.
[12] Isaac Newton and NW Chittenden. Newton's 's Principia: the mathematical principles of natural philosophy. Geo. P. Putnam, 1850.
[13] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1-9, 2015.
[14] Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks graph signal denoising. In Proceedings the 30th ACM International Conference on Information & Knowledge Management, pages 1202-1211, 2021.
[15] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pages 1215-1226, 2021.
11

---

[16] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1725-1735. PMLR, 2020.
[17] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference muchine learning, pages 5453-5462. PMLR, 2018.
[18] Junshu Sun, Chenxue Yang. Xiangyang Ji, Qingming Huang, and Shuhui Wang. Towards dynamic message passing on graphs. arXiv preprint arXiv:2410.23660 2024.
[19] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.052877 2020.
[20] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), pages 1287-1292. IEEE, 2022.
[21] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning, pages 13242-13256. PMLR, 2022.
[22] Yunchong Song, Chenghu Zhou, Xinbing Wang, and Zhouhan Lin. Ordered GNN: Ordering message passing to deal with heterophily and over-smoothing. In The Eleventh International Conference on Learning Representations, 2023. URLttttss: //tperrveee/eeeeeeee. wwwpeeewwwwwwweeeeeeeeeeeeeeeeee formm?
Id=uKPmPEHSnTT
[23] Erlin Pan and Zhao Kang. Beyond homophily: Reconstructing structure for graph-agnostic clustering. In International Conference on Machine Learning, pages (6868-26877) PMLR, 2023.
[24] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35: 13:2-11133 2022.
[25] Keke Huang, Yu Guang Wang. Ming Li, et al. How universal polynomial bases enhance spectral graph neural networks: Heterophily, over-smoothing, and over-squashing. arXiv preprint urXiv:2405.12474 2024.
[26] Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Gbk-gnn: Gated bi-kerlel graph neural networks for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, pages 1550-1558, 2022.
[27] Zhuonan Zheng, Yuanchen Bei, Sheng Zhou, Yao Ma, Ming Gu, Hongjia Xu, Chengyu Lai, Jiawei Chen, and Jiajun Bu. Revisiting the message passing in heterophilous graph neural networks. arXiv preprint arXiv:2405..7766, 2024.
[28] Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems, 35:2268 22081,22111122 2022.
[29] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint
10947, 2019.
[30] Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention-based graph neural networks. Advances in Neural Information Processing Systems, 14:35084-35106, 2023.
[31] Cristian Bodnar, Francesco Di Giovanni, Benjamin Chamberlain. Pictro Lio, and Michael Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns. Advances in Neural Information Processing Systems, 25:18527-18544 2022.
[32] MoonJeong Park, Jaeseung Heo, and Dongwoo Kim. Mitigating oversmoothing through reverse process of gnns for heterophilic graphs. In Proceedings of the 4/ International Conference on Machine Learning, pages 39667-39681, 2024.
12

---

[33] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
[34] 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.
[35] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In 10th International Conference Learning Representations, ICLR 2022, 2022.
[36] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
[37] Grigory Khromov and Sidak Pal Singh. Some fundamental aspects about lipschitz continuity of neural networks. In The Twelfth International Conference on Learning Representations, 2024.
[38] Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In International Conference on Machine Learning, pages 33719- PMLR, 2023.
[39] Meihan Liu, Zeyu Fang, Zhen Zhang, Ming Gu, Sheng Zhou, Xin Wang, and Jiajun Bu. Rethinking propagation for unsupervised graph domain adaptation. In Proceedings of the AAAI Conference Artificial Intelligence, pages 13963-13971, 2024.
[40] Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. Demystifying structural disparity in graph neural networks: Can one size fit all? Advances in neural information processing systems, 36, 2024.
[41] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 00826, 2018
[42] Chenxiao Yang. Qitian Wu, Jiahua Wang, and Junchi Yan. Graph neural networks are inherently good generalizers: Insights by bridging gnns and mips. arXiv preprint arXiv:22/2.09034, 2022.
[43] Ben Finkelshtein, Xingyue Huang, Michael Bronstein, and ismail iIkan Ceylan. Cooperative graph neural networks. In Proceedings of the 41st International Conference on Machine Learning, pages 13633-13659, 2024.
[44] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. European conference on computer vision, pages 630-645. Springer, 2016.
[45] Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016
[46] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.0599) 2018.
[47] Yuankai Luo, Xiao-Ming Wu, and Hao Zhu. Beyond random masking: When dropout meets graph convolutional networks. In The Thirteenth International Conference on Learning Repre- sentations, 2025.
[48] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 338-348, 2020.
[49] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference machine learning. pages 6861-6871. PMLR, 2019.
[50] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
13

---

[51] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low- owwfrequeney information in graph convolutional networks. Proceedings of the AAAI conference on artificial intelligence. pages 3950-3957, 2021.
[52] David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine. 30(3):83-98, 2013.
[53] Weilin Cong. Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936 9949, 2021.
[54] Sitao Luan, Chenqing Hua, Qincheng Lu, Liheng Ma, Lirong Wu, Xinyu Wang, Minkai Xu, Xiao-Wen Chang, Doina Precup, Rex Ying, al. The heterophilic graph learning hand- book: Benchmarks, models, theoretical analysis, applications and challenges. arXiv preprint arXiv:2407.09618, 2024.
[55] P Kingma Diederik and Jimmy Ba Adam. A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[56] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International conference on machine learning, pages 23341-23362 PMLR, 2022.
[57] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint 1XXv:2004.11199. 2020.
[58] Simona Juvina, Ana-Antonia Neacşu, Jean-Christophe Pesquet, Burileanu Corneliu, Jérôme Rony, and Ismail Ben Ayed. Training graph neural networks subject to tight lipschitz constraint. Transactions on Machine Learning Research Journal, 2024.
[59] Moshe Eliasof, Lars Ruthotto, and Eran Treister. Improving graph neural networks with learnable propagation operators. In International Conference on Machine Learning, pages 9224 9245. PMLR, 2023.
[60] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint /907. 2019.
[61] Tao Wang, Di Jin, Rui Wang, Dongxiao He, and Yuxiao Huang. Powerful graph convolutional networks with adaptive propagation mechanism for homophily and heterophily. In Proceedings of the AAAI conference artificial intelligence, pages 4210-4218, 2022.
[62] Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[63] Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. Dif- former: Scalable (graph) transformers induced by energy constrained diffusion. In International Conference on Learning Representations (ICLR), 2023.
[64] Qitian WU, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Sgformer: Simplifying and empowering transformers for large-graph representations. In Advances in Neural Information Processing Systems (NeurIPS). 2023.
[65] Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C Bayan Bruss, and Tom Goldstein. Goat: A global transformer on large-scale graphs. In International Conference Machine Learning, pages 17375-17390. PMLR, 2023.
[66] Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-expresin graph transformer in linear time. In The Twelfth International Conference on Learning Representations, 2024.
14

---

NeurIPS Paper Checklist
Claims
Do the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes].
Justification: The abstract and introduction include the claims made in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Please refer to Appendix
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification,
asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech- sarch-to-texx system might not be used reliably to provide closed captions for online lectures because fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Please refer to Section Section 5.2 and Appendices A. to A.4
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
15

---

All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely. any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer to Appendix H.2 Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Please refer to Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc/publll
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for open-source benchmark).
16

---

The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines
Muiides/ooeeuube swisssoiioccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please refer to Section O and Appendix E.2 Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Please refer to Section Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eтrоrs not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). If eтror bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification: Please refer to Section 6 and Appendix Guidelines:
H2
17

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make it into the paper).
Code of ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:://etrrippee http:///ccccccc//...c..c.u..aaa.
Answer: [Yes]
Justification:
No deviations.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is foundational research and not tied to particular applications. Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
We use publicly available datasets of no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
18

---

Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Please refer to Section
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL..
The name of the license (e.g., CC-BY 4.0) should included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpppppppppaeee thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information creators.
available online, the authors are encouraged reach out the asset's
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provided URL. in Section 6
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should included in the main paper.
19

---

According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, non- standard component of the core methods this research? Note that if the L.MM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, or non-standard components. Please refer to our L.LM policy should or should not be described.
for what
20

---

Table of Contents
Proofs of Theoretical Results
A.1
Proofs of Theorems 4. and Corollary 4.2
Proof of Theorem 5.T
Proofs of Proposition 5.2
Proof Theorem
5.3
Model Analysis
B.1
Complexity Analysis
B
Parameter Count Analysis
3%
Runtime Efficiency Comparision
Additional Quantitative Analysis
32
Additional Theoretical Analysis
33
D.1
Exisiting GNNs with Partial Inceptive Architectures
D.2
Analysis of the Initial Residual Variant
E
Ex Exprimennal Settings and Additional Results
33
E.
Varying Homophily across Hops and Nodes Hyperparameters and Search Spaces
F
Limiation Discussion
36
A Proofs of Theoretical Results
A.1 Proofs of Theorems 4.1 and Corollary 4.2
Restatement of Theorem 4.1 Given graph G(X, A), let the representation obtained via k rounds
of GCN message passing symmetrically normalized A be denoted H o (A and the Lipschitz constant of this k-layer graph neural network be denoted as LG. Given the distance from to the subspace M as (X) = -D, then the distance from H(() to M satisfies:
d - LGA"D,
(5)
where LG II
2. and X < 1 the second largest eigenvalue of A.
proof of Theorem 4.1 To prove Theorem 4.1 need to borrow the following notations and Lemmas
from Oono and Suzuki 29 For N, FE À NNN is symmetric matrix and (
D for k E N.. For M < N, let U be -ddimensional subspace of RN, We assume U
and Á satisfy the following properties that generalize the situation where U is the eigenspace
associated with the smallest eigenvalue of the graph Laplacian L In À (that is, zero). We endow R N with the ordinal inner product and denote the orthogonal complement of U by U =
{u E T (u, v) = 0, Vv E U}. We can regard À a linear mapping À
U
U-.
U
Choose the orthonormal basis (em)m= of U consisting of the eigenvalue of Ä V-
Let
Am be the eigenvalue of À which 6m associated (m M + 1...., N). Note that since the is X, we have |mml for all M + .,,
operator norm of À
N. Since (em) (em) forms
U4
the orthonormal basis of N we can uniquely write X E N as X Dmm cm Wm for some Wm. DRD with @ denoting the Kronecker product. Then, we have
dx
Σ m= M+1
|wm
(6)
21

---

where || ll2 is the 2-norm. On the other hand, we have
Axw( = emm)) @ (W(() wm)
m=1
(Aem) 2 (W(k)* wm)+ +
Σ (Aem) @ (W(K) Wm)
(7)
m=1
m= M+1
M
N
Amm) 2 (W((k) Wm)
Σ
Cm @ (Am W(k) wm).
+
M=M+1
Since U is invariant under A (29]. for any m E [M], we can write Aem as a linear combination of (n E [M]). Therefore, we have
Lu (Axw())=
Σ
|mm w((h wm 1
(8)
m=M+1
Lemma A.1 (Oono and Suzuki
29
For any X E ERNxD have dM(o(X)) dx(X).
Based on Lemma A. by simplifying the GCNs by removing the nonlinear activation functions in
the intermediate layers [56
49
57
and retaining only the final activation function, we have
L
L2m (A(AA(-!!)
<dGu
(AH
(k W(N))
di
(A² (k-2 2) W()-
= LMm
A A'xW@ W(())
Σ
A (wrD)... .....a
Wm
Lemma A.2 (Juvina al. (88). For any k-layer GCN with I-Lipschitz activation functions (e.g. ReLU, Leaky ReLU, SoftPlus, Tanh or Sigmoid), defined as H(k) (AH the Lipschitz constant becomes
Le
w
(10)
We recall the the Lipsehitz constant L. of GCN as Lemma A.2 and substitute Equation into Equation Q.. we have:
10
N
H
(wr()
w())
Wm
m:
M=
Σ
X [mm 11
w
M+1
(11)
N
Wm 1
M+=+11
12 2k
|mml
-3 (X)().
22

---

Restatement of Corollary 4.2 vL..e 0,3k
[(log L log X1, such that d (HH)) )
where [.] is the ceil of the impur.
proof of Corollary 2
order to have dm dM(H
(1)) S L < since LG >= D >= 0 and
A
1, we have
dm(H s < 1
<E
LOD
klogg X < log
L
(12)
log LoD
k >
log A
Therefore, there exists k* = of the input.
log T log A
such that d.
d (H < LG <6, where [-]
is the ceil
A.2 Proof of Theorem 5.1
In this subsection, we present the proofs for the concatenative (c-IGNN), residual (r-IGNN), and attentive (a-IGNN) variants, demonstrating their expression capability of the K-order polynomial graph filter with arbitrary coefficients.
Inceptive neighborhood relationship learning (IN &NR) can ap- proximate arbitrary graph filters for adaptive smoothness capabilities extending beyond simple low- high-pass ones, expressing the K order polynimial graph filter (E 0,L²) with arbitrary coefficients 0,, including c-IGNN (SN, IN and NR), as well as r-IGNN and a-IGNN (IN &NR).
Restatement of Theorem 5.1
Proof of the Concatenative Variant c-IGNN. A polynomial graph filter 50 defined on Å is given by:
K Σ
K 0g - 2)* x.
= H
0gL
L
X
=
Σ k=0
(13)
A=
Expanding NIN ) using the binomial theorem and rearranging the summation order yields:
K
A (+)
H
O2
x
Σ
02(-1) 1)a
A X.
(14)
O==0
Mcanwhile, the matrix formulation of c-IGNN can be expressed as:
K ((
Σ (A [(A'xW()))
K
H H
(15)
km
Wo
where W- =
W
By simplifying the above expression, omitting the non-linee con-iinear layers, and setting
Wk
(()) = I, W.
0,( ( ((-1)(()))) II we obtain:
Dink
K I
H Σ (A Σ 0.(
ΣΣ 0.( 0-1+)) A
(16)
Swapping the notation of and k, we get H polynomial graph filter form in Equation 13). Since coefficients (E 0:( 0((-1)+(1)) can be arbitrary
K
Σ
O& ())- A'X, which matches the
to learn by each Wg. the concatenative variant (c-IGNN) capable of expressing the K-order polynomial graph filter with arbitrary coefficients.
23

---

Proof of the Residual Variant r-IGNN. We begin by verifying, using mathematical induction, that
the residual variant H(k) w((h)
H satisfies the general formula:
H 0
Σ
II W
(17)
m=U
JC(.2...AAj.JJ
where & 2 0, and Ecc(12.....)) [J|=m
Jle W6) Jf
(I) Base Case (k 0). When ht == 0, the recursive formula reduces to H H)) The general
formula for k is: H()) E A
A (H))
Esco1.....o Ile W H ( I H (0))
Thus, the base case holds.
(2) Inductive Hypothesis. Assume that the general formula holds for k 2 0, i.e.
R-1
(k-1))
Σ
A
Σ
IwO). W(k)
(18)
m==
JC.
[J =m
(3) Inductive Step. Using the recurrence relation: hypothesis for H (k-)):
H AH
H
H-1),,
substitute the
(
Ä
Σ
A
" H
Σ
II w
W(K)
A m H (0)
Σ
II W
JE(1. k- JEJ [][=m
JS(1,2.... k- jEJ |
(19)
For the first term, let m' = m + 1. The corresponding range of m' is S m < k as
S m v 1 When m = O, we have
0. E.gg,....)) IlEEs W I. Thus
D| the corresponding range of m' can be safely expanded as 0 S m' S k. and we obtain Em'=o A m (0)) E5c(1.... Ilies w((kk) After renaming back, the first term is: J|=m
Σ A
Σ II (()).
(20)
Here, C
- ( with | m 1, and adding (*) corresponds to all subsets where
[J] with i added. Since the second part is exactly the case where J C 21, k), |J] and l & J. Combining the two terms, we have:
HK) Σ A H
Σ (
(21)
JC(12....R)
1
Thus, the formula holds for k, completing the induction and verification.
We now prove the general formula can express the K order polynomial graph filter with arbitrary coefficients. Let (i) (-1), for < Sjsk k. Substituting this into the general formula gives:
Σ
II
166-
Σ
Il
(-1)a
JC... jEJ [J]=m
JC k) jEJ
(22)
(-1)mm
Σ
JC(1.2....))) jEJ |
24

---

By substituting Equation (22 into Equation 21
and setting W I0., H
XW
=
we have:
H
A
(-1)
E
II
7
m=U
(1.2..... j
m
E
II
7
A m
H
(C jEj 1
(23)
k
1) mm
Σ
II
7
A m
XW
m==
JC..2....kkk AJEJ |
k
(-1) m
70
Σ
II
73
Am m
X.
m==
(C [
JEJ
Comparing this with the polynomial graph filter:
K
K
A: A' )
Hp
0&
1-11)
x
p
1
Y=0
1'' (m))
Σ
Og (-((-1) 1m
A
x
(24)
Σ
(-1) m
Og
m
X,
in order to prove the residual variant representation (k) can express the K order polynomial graph filter representation Hp with arbitrary coefficients, we only need to show the following equation system:
70
Σ
II
1h
Σ Or V=
(m)
(25)
[
has a solution or good approximation for m 0, o,...kk.
Case 0: Since 0. EEC(1 Ile W =I E,c(12.....))
Ise 75 1. We
[/|=m
11|=0
have To Σ Og. ......
Case m = 1,..., k: We can approximate it by
70
II
Σ #m
0r
(26)
m
e' d' d'=k-ma ml+1
and solve by
D$ k Op (1))
76 m+1
(27)
Σx =m
9r (m-
for =,....kk k. The above solution may fail when Σ Ep=m-1 Oy (n11) 0. Similar to the analysis
of the boundary conditions in Chen et al. [16], this case is rare the K-order filter ignores all features from the m-hop neighbors, and we can set 7 sufficiently large so that Equation (27) still good approximation.
25

---

Since coefficients can be arbitrary to learn by each W we now proved that residual variant r-IGNN can express the K-th order polynomial filter with arbitrary coefficients. For the proof of the initial residual variant being able to express the K-th order polynomial filter, please refer to the proof of Theorem 2 in Chen et al. [16].
Proof of the Attentive Variant a-IGNN. For simplicity, we set all feature transformation matrices, except those used in attention mechanisms, to the identity matrix I. Then the implementation of an
a-IGNN with the GCN AGG(-) (i.e., m (N) Σ o (A h
U)) () is defined as:
(k) = 0
(k)
Σ A A h (k-1) + (1 - a 0 n
(28)
1
where (k) = g(k) (E, A ha (R) = (AH((-1))
(k-1) he
(( We define:
w (k), H RRN W(k E 1R2X1
(29)
where || is the concatenation operator, and [:l represents the v-th row. Several activation functions can be used to limit the range of attention values. Here we leave out the activation for simplicity.
Next we demonstrate that for any given ogg,k 2 1, there exists a transformation W(k) such that
H ())( = holds for all v. That is, (k-1) (k-) H W()
ag1.
We rewrite (A)
W W2
where (R) w(() E Rx1, Substituting, we obtain:
ÁH
H
0g
(30)
Rearrange the equation: ÁH (6-
ag 1
H ( w Let w(() arbitrary, and
w(k) (AH( (agl H ((k ( where (.)1 denotes the pseudoinverse. For any og.
there exists (4)) of the following form that ensures a = a2 for all o:
(A) - H 1
(1))=
(31)
((() (R)
Under these conditions, the a-IGNN variant be expressed as: (k-1) (k-1) + (1 or. ((--1)
(k) kk)
ag A A
II
o;AA + (1 - ax) ())
1=1
(32)
Σ
II
II a:) Am (()
CC(122....)) mEC
iEc
where Eos(12. Hee Hlg ass) = 1 for 0.
Compared to the polynomial graph filter H, (mmo (Ee=m Or (-) À
X. since ag
arbitrary, by setting a' = -aa (0) (0 (0) X((ol),, we arrive at:
H ( =
Σ 1-1
Σ
II
a
II içc
at)
m Xaol
m=
(C NEC
(33)
Σ (-1)m
Σ
II
a II (1 at)
Am X.
Cg
m==
CC11.2.... =m IEC
igC
26

---

To satisfy the equality, we only need to show the following equation system: & Σ P=mm
00
Σ
II II (1++))=
8:r
(34)
m
(1. A,ICC iEC
sCC
has solution good approximation for m .., Case 0: When m 0, given Ecg Iliec
llie ai Lige az) -I have
0g -v== Op.
Case m 1,...,k. k We can approximate it by
&
of k-m
t''
00
II
(1+ of)
Σ p'
0g
(35)
m
m+1
and solve by
d 0,
if 1, .,..., m1,
m 2 (e((
(36)
o
if k- m
k.
Similar the previous proof, the above solution may fail when E 0r (x-+)= = and this case is rare as the K-order filter ignores all features from the m-hop neighbors. We can set af sufficiently large so that Equation (36) is still a good approximation.
for I,...,k.
A.3 Proofs of Proposition 5.2
Here, we take c-IGNN as variant example to demonstrate the proofs of Proposition 5.2 The proof's of other variants can be achieved in similar way.
Restatement of Proposition 5.2, IGNN-s can achieve (1) SIGN, (2) APPNP with personalized PageRank, (3) MixHop with general layerwise neighborhood mixing, and (4) GPRGNN with general- ized PageRank.
Proof 1: SIGN simplified case of c-IGNN. The architecture of SIGN can be trivially obtained by omitting the NR function and replacing it with a non-learaale concatenation as
H I1 (Atx(())) k=
HSIGN.
(37)
Proof 2: APPNP as simplified case of c-IGNN. The architecture of APPNP 46 lows:
defined as fol-
H APENE fo(X) XW 0,
H (k)
APINE (1 a) AH (k-1)
oH (0)
(38)
APPNP
APPNP
where E (0, 1] represents the teleport (or restart) probability. Consequently, (R) expressed in terms H APPNP as:
APeNP can be
k-1
H APPNP (1 (
Σ
a(1 Q''A (
(39)
APPNP
APENP
According to Equation 15 by omitting all non-linearity and setting (+)) We, W = (1 (1-o) and W = a(1 a)* for ko E [0, K - 1], we obtain a simplified case of IGNN as:
K-1
H A K (
A'XWoal1-aj1
K-1
(40)
= (1 - 0)) ( X +
af1 - -
k=0
(K)
APPPP
27

---

Proof 3: MixHop simplified case of c-IGNN. Here, illustrate that c-IGNN achieve the general layer-wise neighborhood mixing MixHop Abu-El-Haija et 6 by specializing the
weight matrix as W
R
Wx
K H
( ( ( k=
k o (A (A
(41)
where w RDEE Wa E FxF in:
Setting F" D. W = I and Wx axIp results
h
Σ a (x((()))axrrr)
E k=0
(42)
K
ago (A
which represents general layer-wise neighborhood mixing relationship demonstrated by Definition 2 of Abu-El-Haija et al. [34] to exceed the representational capacity of vanilla GCNs within the traditional suessage-passing framework. We achieve this advantage through simple neighborhood concatenation and non-linear feature transformation, climinating the need to stack multiple layers of message passing done in Abu-El-Haija et al. [34), thus calling it Hop-wise Neighborhood Relation rather than layer-wise.
Proof 4: GPRGNN simplified case of c-IGNN. Based on Equation 41 p. by sharing the param- eters of all (kk) as (kk Wa. setting W, 7 and leaving out all the non-linear layers of REL(-), we have:
K
K
K
H
A h x
W. = > XWo
Σ km
7h A
XWo),
(43)
k=
which is the exact architecture of GPRGNN B3
Proof 5: mean/sum pooling as a simplified case of c-IGNN. Based on Equation 44 by setting
W マ I, we obtain H [Σk (A (A)))))))).. which corresponds mean pooling,
o (A*xW()))) which corresponds to Alternatively, by setting W have (
sum pooling.
A.4 Proof of Theorem 5.3
Restatement of Theorem 5.3
Let the representation of c-IGNN incorporating the SN principle be
denoted as HIG. = o()) X ) and the Lipschitz constant of be denoted as Lic-
W.
Given (X) = D and w
then the distance from HIG.& to M satisfies: w.
(HIGH) &
Σ
Ewwww, D.
(44)
==
where À < 1 is the second largest eigenvalue of A and Lig Et w.W.k.
28

---

Proof of Theorem 5.3 We first derive the inequality:
(HIG.) = dr (o (1li=00 A (AXW()))))
dM
Σ oA LA
Eo(A'xwoo)w.)
(45)
Wo w
< d
Σ
A''wWWW.))
Given U invariant under A, U is also invariant under A'. Similar to the derivation of Equation (8). we have
dM ( (Hi & di
km0
N
k
(w)) Wm
TWW
m/ M
+
Σ
X x(WWOO
Wm
M=M+1
i=
1mml2
Σ A XWWOW W;
(46)
m=M+1
k
N Σ
W
1m
m== M+1
XwOWw W.
(X)
w
D
Recall the Theorem 3.1 in Juvina al. [58
as following Theorem A.3 Similar Equation (45
can obtain HIG.E = (E o ( IGNN, we have
W.). w.) Since Ax = for A', applying Theorem A.3 to
L - + Σ wow.l. 1=
(47)
Theorem A.3 (Juvina et al. 588 Consider generic graph convolutional neural network like
(k) ( + (k w wi(h) with M symmetric (corresponding to an undirected graph) with non-negative elements. Let AK be its maximum eigenvalue. Assume that, for every
i [k....,k). matrices w(i) and w( have non-negative elements, w 2 0 and w 2 0. Let
() v(4) = =l((w + +w(+)) (Wo" + (
(48)
Then, a Lipschitz constant of the network is given by -= (Ak)..
(49)
L
B Model Analysis
The computational complexity and parameter count of vanilla GCN, r-GGN,, a-IGNN, c-IGNN and Fast c-IGNN are presented in Table Several key observations are:
29

---

Table 6: Comparison Computational Complexity and Parameter Count
Model
Per-layer Complexity
Total Training Complexity
Parameter Count
Vanilla GCN
OINDF EIF NE
ONNDF + K(S)F + N
O,DE + KF*)
I-GNNN
OINDF +
OINDE KIEF NF
O,DF KFF)
a-IGNN O(NDE E +NF
OINDE + KF NF))
O K-2FF
c-GNNN
O(NDF E| N
O(NDF4 K[EEPP NP9))
0,DP KF
Preprocessing: OIKIE D).
Fast c-INNN
Training: NDKF KNPP))
OLK(NDF NNF))
O(K(P+ 19)
1. r-IGNN:
The residual connection does not significantly change the complexity compared to GCN. If the representation of the previous hop also has transformation in the residual connection, then will require more parameters.
2. a-IGNN: The model adaptively determines Ot eter count. Its per-layer complexity lower than others, but still scales with the number of edges and nodes.
(k) for each node, which slightly reduces the param-
c-IGNN: The explicit multi-hop aggregation increases computational cost compared to GCN. The complexity grows with K, making it more expensive as the number of hops increases. However, it better captures long-range dependencies and enjoys hop-wise distinct generalization and overall generalization, which holds significance in GNN universality across varying homophily.
By decoupling aggregation into preprocessing, shifts the expensive aggregation operations outside training, making training complexity independent of the aggregation. This makes scalable for large graphs. Among these models, Fast c-IGNN achieves the best scalability by precomputing multi-hop information. In contrast, a-IGNN and r-IGNN require more computational resources due to their recursive neighborhood aggregation.
Fast c-IGNN (see Appendix :.I):
B.1 Complexity Analysis
Complexity of Baseline Vanilla GCN
H o (H())))
(50)
Complexity per layer: (1) Pre linear transformation: O(NDF) (2) Aggregation: ((EE) (assum- ing sparse adjacency matrix with |E] edges); (3) Transformation: O(NF²); (4) Total training complexity: O(NDF + [
NF*).
Therefore, the total complexity (K layers) of the vanilla GCN is: O(NDF K(E)F+
Complexity r-IGNN
H (k) = or (AH w())) + (k-1))
(51)
Complexity per layer: (1) Pre linear transformation: O(NDF) (2) Aggregation: O(EEF) : (3) Transformation: O(NF²); (4) Total training complexity: O(NDF + | N
Therefore, the total complexity (K layers) of r-IGNN is the as the vanilla GCN: O(NDF K[[EFF + F2)..
Complexity of a-NINN
h(4) (k)
(k) a
Σ
A Ar.ub(k-1
(k-1) + (((())
(52)
a (AH 1)
H ( ()( (a).
(53)
Complexity per layer: (1) Pre linear transformation: O(NDF) (2) Aggregation: O({E (k), O(NF); (3) Total training complexity: ONNDF +FF+NNF).
(3)
Computation of o%
Therefore, the total complexity (K layers) of a-IGNN lower since does not use full weight matrix but instead relies gating mechanism: O(NDF + K(EEF NF)).
30

---

Complexity of original c-IGNN
k H = oA A X
(54)
K=
Complexity: (1) Pre linear transformation: O(NDF) (2) Multi-hop propagation: O(K F); Feature transformation: O(KNF2); (4) Summation and final transformation: O(KNF); (5) Total training complexity: O(NDF ((8) + ))
Complexity of the Fast c-IGNN
To enhance IGNN's efficiency, employ preprocessing technique to decouple expensive ag- gregation operations from training. By examining the matrix formulation of IGNN: HIG. ((l) (A' AXX@O))W) we observe that the aggregations A for different hop neighborhoods are independent and can be computed in parallel. To optimize this, we preprocess these aggrega- tions m, = A'X X and store them prior to training. This approach reduces both the time spent on aggregations and the memory overhead during training.
The overall time complexity can thus divided into two components:
1. Preprocessing: This involves recursively computing Å for hops, with a complexity of D) for sparse cases;
2. Training: During training, the complexity of the operation o )()))) W, m e RNxD, w E RDxF, W RKF is O(KNDF + KNNF)
The only aggregation operation occurs during preprocessing, ensuring that training efficiency decoupled from the edges. This design makes IGNN scalable and efficiency.
B.2 Parameter Count Analysis
Parameter Counts are presented as:
r-IGNN: Since each layer has weight matrix (kk RFFF, the total number of parameters for K layers are (DF + K F²2)
a-IGNN: Each layer has a weight matrix ( 22 Thus, the total parameters for layers are O(DF + K 2F))
c-IGNN: As each layer has (ik) FxF and W FxF, the total parameters are O(DF-
KF²).
Fast c-IGNN: The total parameters are O(KDF+KP>
B.3
Runtime Efficiency Evaluation
We empirically evaluated the training efficiency of the 10 top models listed in Table 3 using a consistent hidden dimensionality of 512 across all methods ensure fair comparison. To provide comprehensive analysis, we measured the average training time (in seconds) over 100 epochs under representative settings:
Squirrel (heterophilic, 2223 nodes, full-batch): hop sizes of 2, 8, 16, and 32. OGB-Arxiv (homophilic, 169,343 nodes, full-batch): hop sizes of 2 and 10.
The average training runtimes under each setting are reported. The three most efficient models per benchmark are emphasized in bold.
These results demonstrate that our IGNN variants particularly fast c-IGNN consistently achieve competitive or superior training efficiency across both heterophilic and homophilic graph settings. The runtime advantages are especially pronounced under large-hop configurations, owing to fast c-IGNN's use of precomputation and caching strategies for efficient neighborhood aggregation. This design enables fast c-IGNN to scale effectively without compromising expressiveness or generalization capability. Note that all results reported for c- c-IGNN in Table correspond to the fast c-IGNN variant.
31

---

Table 7: Training time (in seconds) on Squirrel dataset across different hop sizes.
Model / Hop
2
8
16
32
Avg. Rank
IncepGCN
1.6=0.11
10.2+:0.4
1..
130.9+5.3
8.75
SIGN
1.0+0.1
1.6+0.3
2.7+0.1
4.7:10.3
1.00
DAGNN
1.6=0.3
2.4
3.2:#0.1
5.4+0.33
2.62
GCNII
1.8=0.2
3.910.1
6.420.1
10.3+0.2
5.88
OrderedGNN
2.0.1..2
4.6.1..3
7.640..9
15.8
8.25
DIFFormer
4.5
10.5
18.40.66
36.7+42.77
9.75
SGFormer
4.3++..1
10.9+0.1
21.5+4.8
50.2++6.0
10.25
a-IGNN
1.720.1
4.210.1
7.5=0.1
12.6=0.2
6.75
r-IGNN
1.610.11
3.310.1
6.020.2
11.2:10.5
4.75
c-IGNN
1.910.1
3.40.11
5.610.11
10.3
5.38
fast c-IGNN
1.40011
2.420.1
3.5+0.4
6.9+0.11
2.62
Table 8: Training time (in seconds) on OGB-Arxiv dataset. OOM indicates out-of- -emmoryor errors.
Model/HHop
2
10
Avg. Rank
IncepGCN
00M
OOM
SIGN
6.3+0.0
19.0#0.1
2.0
DAGNN
4.0=0.00
5.9::0.0
1.0
GCNII
33.1#1.11
141.9#0.4
7.5
OrderedGNN
29.5+0000
0OM
7.0
DIFFormer
50.7++0.3
OOM
9.0
SGFormer
66.2+0.1
OOM
10.0
a-IGNN
20.2
80.4E0.1
5.5
rINNN
21.6111.3
78.
5.5
c-IGNN
16.0+11.0
42.740.1
4.0
fast c-IGNN
15.1
38.5+0.4
3.0
C Additional Quatitative Analysis
We conducted additional quantitative experiments to evaluate the aeooothness-generaliiinee dilemma by measuring the smoothness du (H( and the empirical Lipschitz constant i. following the implementation in Cong et al. (53) across different models: vanilla GCN, c-IGNN (integrating all three proposed principles), and r-IGNN (adopting only the IN and RN principles), shown in Figures 6
The results provide strong empirical support for our theoretical claims regarding the dilemma.
Key Observations:
Vanilla GCN and the Dilemma. While d. (H() initially increases (indicating reduced smooth- ness) for & < 10 (Figure this trend does not persist for larger hops. Specifically, for & 2 32 (Figure 6). d (H (H) greatly decreases (reflecting increased smoothness), followed by a subse- quent rise likely due to the transition from approximation classifier supervision. Meanwhile, i exhibits an inverse trend, in alignment with our theoretical predictions of the smoothness- generalization dilemma.
r-IGNN. Although r-IGNN alleviates oversmoothing by yielding higher (H())) it also shows a continuous increase in f., suggesting that generalization capability deteriorates as hop count increases.
c-IGNN. By incorporating all three design principles, c-IGNN sustains stable and moderate trends in both f. and d (H())), thereby ensuring robust generalization while avoiding excessive smoothing.
32

---

squirrel
Lipchitz Constant
Lipchitz Constant
10
10
10
10
10
10
3000
GCN
3000
Vanilla GCN
c-IGNN
e-IGNN
1TREE (N))
TTEE (N))
r-IGNN
r-IGNN
2000
2000
1000
1000
6
10
2
4
10
Layers/Hops k
Layers/Hops k
(a) Cora 10ps=10
(b) Squirrel hops=10 10
Figure 5: Additional Quantitative Experiments (1).
Table 9: Comparison of Inceptive GNNs in incorporating three principles.
Molhaak
APEND INNE-E
SION
MIXTEO
maree
desnr comnees XCMOEN mameaac NOW MaNN GlON
88
IN
NR
merged nnoo SN
D Additional Theoretical Analysis
D.1
Exisiting GNNs with Partial Inceptive Architectures
Table 9 shows the comparison of inceptive GNN variants in incorporating three principles, while Table 10 demonstrates the detailed SN,IN, and NR architectures of each variant. Except for c-IGNN, the other methods lack at least one principle. The best performance of c-IGNN shows that the combination of all three principles can best climinate the dilemma.
D.2 Analysis of the Initial Residual IGNN Variant
The initial residual connection in Chen et al. [6 can be formulated as: (K) -(H(t H where O (XW(()) Leaving out all non-linearity for simplicity, we can derive the expression for H in terms X as:
h
H h))
Σ A (W
w j=++1
II
(55)
1=0
This formulation is also inceptive variant of IN design. It avoids an excessive increase in the parameter (+k) for low-order neighborhoods when is small, in original residual connection, thereby preventing the smoothing effect caused by multiplications of W((). This distinction may provide insight into why initial residual connections offer greater relief to over-smoothing, low-
order neighborhood representation remains the performance of its lower-order GNN counterparts.
E Experimental Settings and Additional Empirical Results
E.1 Varying Homophily across Hops and Nodes
Figure 7 demonstrates the varying edge and node homophily inherent within single graph.
33

---

Lipchitz Constant
Lipchitz Constant
10
10
10
10
10
20
30
20
40
60
GCN
10"
Vanilla GCN
10
e-IGNN
e-IGNN
D M(11(())
M((T(()))
r-IGNN
10"
r-IGNN
10
10"
10"
10
20
30
0
20
40
60
Layers/Hops k
Layers/Hops k
(a) Cora hops=32 squirrel
(b) Cora hops=64 squirrel
Lipchitz Constant
Lipchitz Constant
10
10
10"
10
10
20
30
20
40
60
Vanilla GCN
10a
Vanilla GCN
10
c-IGNN
c-IGNN
M((I(())
M(II(())
r-IGNN
10
r-IGNN
10
10"
10
10
10a
10
20
30
0
20
40
60
Layers/Hops k
Layers/Hops k
(c) Squirel hops=32
(d) Squirrel hops=64
Figure 6: Additional Quantitative Experiments (2).
Varying Homophily across Hops We compute the edge homophily each i-th hop based on A with self-loops removed (Figure 7a) added (Figure7bb The edge homophily levels across hops all show diverse trends, including upward, downward, and oscillating, although the trends appear to be more stable after adding the self-loop.
Varying Homophily across Nodes We compute the node homophily of N nodes in each i-th hop based on A' with self-loops removed. From Figure to 7c two conclusions can be safely drawn that the node homophily levels (1) show continuous variation from to among all nodes, and (2) display an overall declining trend with fluctuations when the hop order increases.
E.2 Best Hyperparameters and Search Spaces
We present the optimal hyperparameter settings for all IGNN-s in our public code repository: https://github.com/grt www.///llom//GG//..
E.2.1 Search Spaces of Baseline models
The code for all 30 basclines in Table I1 is
34

---

Table 10: Comparison of inceptive GNNs variants. The following notations are used only to illustrate the relevant forms and do not necessarily conform to the actual expressions. Y denotes learnable coefficients, and K is the network depth. s(.) refers to the softmax function, while g(.) represents the ordered gating attention function. W. is the weight matrix for the attention, and W W W // W mix denote weight matrices of hull-loow/highh-pss////
signals, respectively. IN &NR (weight of k-th hop)
Model
Subtype
SN (W of &-th hop)
a(1 a)",
APPNP
Residual
W
(1 a) a (0.1)
JKN
Concatenative
II
w
IncepGCCN
Concatenative
w
Concatenative
W
MixHop
Concatenative
W
DAGNN
Attentive
W
o (A A.W,WW..
Residual
I
W
implicit T6 explicit Th
GPRGNN
Attentive
(I W
((1))) (k)
T/L/1 wilk
I/T
ACMGCN
Attentive
11 11i w
W
OrderedGNN
Attentive Residual
We
g(me h (1)
r-IGNN
Eec(L....))) A) MF
Ih. WO
implicit 7
a-IGNN
Attentive Concatenative
W
explicit 74
c-IGNN
W
implicit 7
cora
cura
Edge Homophily
0.8
0.8
0.7
photo
0.7
photo
pubmed
Homophil
0.6
puhmed
0.5
wikies
0.5
wikies
0.4
wisconsin
0.4
wisconsin
0.3
squiret
squirrel
0.1
flickr
0.2
flickr
2
4
S
8
reman empire
blogcatalog
0.1
2
$
6
blogeatalog
reman emplre
Hops
Hops
amazon-ratings
amaoon- ratings
(a) Remove self-loops
(b) Add self-loops
Pubmed (homao nodes
Hops
Chameleun (hetero) modes
200
Hops
Roman- Cannan-Emphe Emprn---errrreeee (heteru) modes
5000 10090
Hops
10000
400
15000
20000
s00
15000
20000
(c)
Figure 7: Varying homophily across hops and nodes.
a baseline has its own folder, a search.py script is included for hyperparameter tuning with optuma. See the README.md in the folder for details.
If baseline does not have its own folder, it can be run with provided script baselines,py which can conveniently derive the corresponding search.py script.
All search
spaces
used in the experiments are
documented in
http://iiiconadaaee//oooooooooos prid.p
35

---

Table 11: Baselines. Incep. and Non. are inceptive not.
Type
Subtype
Model
Graph-agnostic
MLP
Homo.
Non.
GCN SGC
[3] Gra
GNNs
APPNP 46 SIGN [57], JKt [7]] MixHop
34
Incep.
FAGCN ST GAT [59] IncepGCN 80
DAGNN 488.
H2GUN 10, GBKGNN [2]] GGCN 20
Hetero.
GloGNNN 21 HOGGCN [6]]
GNNs
GPRGNN [33]. ACMGCN [24]. OrderedGNN
Incep.
N [[8] CoGNN [43] UniFilter 25
NodeFormer (62]. DiFFomer [63. SOFormer [6]]
Graph Transformer
GOAT Polynormer
Limitation Discussion
This work contributes to advancing the universality of Graph Neural Networks (GNNs) under varying levels of homophily by identifying the smoothness--eneralizzeeee generalization dilemma, which poses fundamental challenges to learning both higher-order homophilic and heterophilic settings. While our findings provide unified theoretical and empirical foundation for this dilemma, we acknowledge the following limitations: (1) Use of existing architectural components. Our proposed framework is constructed by revisiting and systematically organizing existing design principles rather than introducing entirely new architectural modules. This choice intentional: by building on widely adopted components, our framework offers practical and interpretable foundation for diagnosing and addressing smoothness- generalization related failures in GNNs. Nonetheless, the absence of newly designed modules may be as limitation from pure architectural perspective. (2) Scope of theoretical analysis. Our theoretical formulation is grounded in the classical GCN setting to ensure analytical clarity and generality. While this enables clean and interpretable derivations, it does not explicitly cover more complex GNN architectures such as adaptive message- message-passing models. However, we believe the identified dilemma and derived principles are broadly applicable, and extending the theoretical analysis to more expressive GNNs represents a promising direction for future work.
36


Reviews:
[{"review_id": "MWig45vR53", "reviewer": "Reviewer_7CTQ", "summary": "This paper studies the problem of how to design GNNs that can generalize across graphs with varying levels of homophily and heterophily. The authors propose IGNNs, a modular framework composed of separative neighborhood transformations, inceptive aggregation, and neighborhood relationship learning, which together enable the model to adaptively handle multi-hop structural variations and alleviate the smoothness-generalization dilemma.", "questions": "See W1-W4.", "limitations": "Yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strong Points\n\nS1. The theoretical analysis appears to be sound.\n\nS2. Designing efficient GNNs that can generalize across graphs with varying homophily levels is an important and timely problem.\n\nWeak Points\n\nW1. The overall model is relatively complex and has high inference costs, while the lightweight variant r-IGNN offers lower computational overhead but exhibits significantly weaker performance. However, the paper does not include efficiency comparisons, which limits a comprehensive assessment of the method’s practical applicability.\n\nW2. For a more consistent and fair evaluation, I would suggest the authors adopt dataset splits and evaluation metrics aligned with prior work. For example, the roman-empire and cham-f datasets are typically evaluated using the fixed splits provided by their original sources.\n\nW3. The paper omits several important related works, such as [1, 2, 3]. Notably, [2] and [3] should be included as baseline methods for a more complete comparison.\n\nW4. The authors devote considerable attention to theoretical analyses, including the smoothness-generalization dilemma and variations in homophily across hops. However, the connection between these theoretical insights and the model design is not sufficiently clear, making the overall motivation well-established but not fully reflected in the architectural choices.\n\nMinor\n\nIt is recommended that the authors explicity inelude the intermediate variables $ h_v^{(k)}$ and $ m_v^{k}$ directly in the formulas presented in the second and third columns of Table 2, as is done in the fourth column. This would improve clarity and consistency in presentation.\n\n[1] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? ICLR 2023.\n\n[2] Chenhui Deng, Zichao Yue, Zhiru Zhang. Polynormer: Polynomial-expressive graph transformer in linear time. ICLR 2024.\n\n[3] Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C. Bayan Bruss, Tom Goldstein. GOAT: A global transformer on large-scale graphs. ICML 2023.", "was_revised": true, "final_justification": "Thank you to the authors for their detailed rebuttal. Most of my concerns have been addressed. Specifically:\n\n- The authors provided a comprehensive comparison of the runtime performance, which clarified my concerns regarding efficiency.\n\n- They included new experiments on public splits and introduced additional baselines, which substantially strengthen the empirical support for their method.\n\nGiven these additions and clarifications, I find the response satisfactory and have updated my score accordingly.", "rebuttal": "> W1:  ...the paper does not include **efficiency comparisons**...\n\nWe thank the reviewer for pointing out efficiency comparisons. We apologize for not making this aspect more prominent in the main manuscript due to space constraints, as **we have provided detailed analyses of model complexity, parameter counts, and runtime comparision in Appendix B**, and summarize the key findings of **efficiency comparisons** here for convenience.\n\nAn empirical analysis of training runtimes across the top models in overall performance is conducted. We measured the average training time over 100 epochs under two settings:\n- Squirrel (heterophilic, full-batch): hops (2, 8, 16, 32)\n- OGB-arxiv (homophilic, full-batch): hops (2, 10).\n\nSquirrel (seconds):\n|Model/Hop|2|8|16|32|avg_rank|\n|-|-|-|-|-|-|\n|IncepGCN|1.6±0.1|10.2±0.4|34.7±1.5|130.9±5.3|8.75|\n|SIGN|1.0±0.1|1.6±0.3|2.7±0.1|4.7±0.3|**1.00**|\n|DAGNN|1.6±0.3|2.4±0.2|3.2±0.1|5.4±0.3|**2.62**|\n|GCNII|1.8±0.2|3.9±0.1|6.4±0.1|10.3±0.2|5.88|\n|OrderedGNN|2.±0.2|4.6±0.3|7.6±0.9|15.8±1.3|8.25|\n|DIFFormer|4.5±0.2|10.5±0.5|18.4±0.6|36.7±2.7|9.75|\n|SGFormer|4.3±0.1|10.9±0.1|21.5±4.8|50.2±6.0|10.25|\n|a-IGNN|1.7±0.1|4.2±0.1|7.5±0.1|12.6±0.2|6.75|\n|r-IGNN|1.6±0.1|3.3±0.1|6.0±0.2|11.2±0.5|**4.75**|\n|c-IGNN|1.9±0.1|3.4±0.1|5.6±0.1|10.3±0.2|**5.38**|\n|fast c-IGNN|1.4±0.1|2.4±0.1|3.5±0.4|6.9±0.1|**2.62**|\n\nOGB-arxiv (seconds):\n|Model|2|10|avg_rank|\n|-|-|-|-|\n|IncepGCN|OOM|OOM|-|\n|SIGN|6.3±0.0|19.0±0.1|**2.0**|\n|DAGNN|4.0±0.0|5.9±0.0|**1.0**|\n|GCNII|33.1±1.1|141.9±0.4|7.5|\n|OrderedGNN|29.5±0.0|OOM|7.0|\n|DIFFormer|50.7±0.3|OOM|9.0|\n|SGFormer|66.2±0.1|OOM|10.0|\n|a-IGNN|20.2±1.7|80.4±0.1|**5.5**|\n|r-IGNN|21.6±1.3|78.3±0.3|**5.5**|\n|c-IGNN|16.0±1.0|42.7±0.1|**4.0**|\n|fastc-IGNN|15.1±0.7|38.5±0.4|**3.0**|\n\nThe top 5 most efficient models are highlighted in bold. These results demonstrate that our IGNN variants, especially (fast) c-IGNN with a preprocessing and caching technique to decouple expensive aggregation operations from training (line 740-753), **consistently achieve competitive or superior training efficiency**.\n\nWe hope these additional analyses sufficiently address the reviewer’s concern.\n\n> W2: suggest...adopt dataset splits aligned with prior work...roman-empire and cham-f...\n\nWe thank the reviewer for this valuable suggestion.\n\n(1) **Justification for Split Strategy**: Our choice was guided by our theoretical emphasis on **generalization**, an aspect highly sensitive to dataset splits. Prior work [4] has demonstrated that **different split strategies can exhibit substantial variation in structural distributions**, which in turn can significantly affect generalization behavior. To mitigate these confounding effects, we adopted a unified 10× random split scheme with a 48%/32%/20% train/validation/test ratio [5,6,7,8]. This **reduces variance across datasets stemming from heterogeneous splitting policies in earlier work**.\n\n(2) **Evaluation on Standard Splits**: In response, we have also re-evaluated the top 5 baselines with the same parameters on the public splits of roman-empire and cham-f as follows. The results confirm that the observed performance **remains consistent with those from our splits. The similarity in partition ratios contributes to the consistency.**\n\n- cham-f\n|splits|<ours, 48%/32%/20%>|<public [1], 46%/32%/22%>|our rank|public rank|\n|-|-|-|-|-|\n|SGFormer|44.44±3.01|43.30±3.92|4|3|\n|UniFilter|46.07±4.74|43.76±4.00|2|2|\n|OrderedGNN|42.13±3.04|42.57±3.82|7|6|\n|SIGN|44.66±3.46|43.02±2.98|3|4|\n|IncepGCN|43.31±2.18|42.98±2.75|5|5|\n|r-IGNN|42.47±3.06|41.64±2.62|6|7|\n|a-IGNN|40.45±3.80|41.49±3.78|8|8|\n|c-IGNN|47.13±5.18|46.50±3.77|1|1|\n\n- roman-empire\n|splits|<ours, 48%/32%/20%>|<public [1], 50%/25%/25%>|our rank|public rank|\n|-|-|-|-|-|\n|SGFormer|75.71±0.44|75.74±0.55|7|7|\n|UniFilter|74.90±0.91|75.10±0.69|8|8|\n|OrderedGNN|82.65±0.91|83.39±0.33|2|2|\n|SIGN|81.56±0.57|79.46±0.68|3|5|\n|IncepGCN|80.97±0.49|80.73±0.42|4|3|\n|r-IGNN|80.67±0.47|80.34±0.40|5|4|\n|a-IGNN|78.01±3.12|79.02±3.00|6|6|\n|c-IGNN|86.07±0.60|86.54±0.54|1|1|\n\nIn the revised version, we will report results under both split protocols. \n\n> W3: ...omits several related works. Notably, [2] and [3] should be included...\n\nWe thank the reviewer for highlighting these important works. We report their performance in comparison with the top 10 baselines as follows. **Their inclusion does not alter the overall conclusions of our study.**\n\nNotably, Polynormer shows a great advantage in roman-empire which was not seen in other datasets. We checked it and found **it was a long-chain graph converted from words**. This aligns with the strengths of transformers in natural language processing. As **we focus on general graphs and IGNNs' avg_rank still show consistent advantages, we leave the language graphs to future studies.**\n\n|**model**|**actor**|**blogcatalog**|**flickr**|**roman-empire**|**squirrel**|**chameleon**|**amazon-ratings**|**pubmed**|**photo**|**wikics**|**A.R.**|\n|-|-|-|-|-|-|-|-|-|-|-|-|\n|IncepGCN|35.69±0.75|96.67±0.48|90.42±0.71|80.97±0.49|38.27±1.36|43.31±2.18|52.72±0.80|89.32±0.47|95.66±0.40|85.22±0.48|9.0|\n|SIGN|36.76±1.00|96.06±0.68|91.81±0.58|81.56±0.57|42.13±1.99|44.66±3.46|52.47±0.95|*90.29±0.50*|95.53±0.43|85.59±0.79|5.8|\n|MixHop|36.82±0.98|96.05±0.48|89.78±0.63|79.39±0.40|41.35±1.04|44.61±3.16|47.91±0.53|89.40±0.37|94.91±0.45|83.15±0.96|10.8|\n|DAGNN|35.04±1.03|96.73±0.61|*92.18±0.73*|73.94±0.45|35.62±1.48|40.96±2.91|50.44±0.52|89.76±0.55|95.70±0.40|85.07±0.73|9.8|\n|GCNII|35.69±1.08|96.25±0.61|91.36±0.68|80.55±0.82|38.43±2.10|42.13±2.04|47.65±0.48|90.00±0.46|95.54±0.34|85.15±0.56|9.8|\n|OrderedGNN|36.95±0.85|96.39±0.69|91.13±0.59|82.65±0.91|36.27±1.95|42.13±3.04|51.58±0.99|90.01±0.40|*95.87±0.24*|*85.60±0.77*|6.6|\n|N2|37.41±0.60|94.72±0.57|91.08±0.79|75.32±0.41|39.35±2.39|38.60±1.12|48.08±0.76|89.16±0.24|**95.92±0.27**|84.07±0.39|10.9|\n|UniFilter|36.11±1.04|96.534±0.47|91.89±0.75|74.90±0.91|*42.40±2.58*|*46.07±4.74*|49.36±0.98|90.15±0.39|94.91±0.62|85.43±0.67|7.5|\n|DIFFormer|36.13±1.19|96.50±0.71|90.86±0.58|79.36±0.54|41.12±1.09|41.69±2.96|49.33±0.97|88.90±0.47|95.67±0.29|84.27±0.75|10.5|\n|SGFormer|37.36±1.11|*96.98±0.59*|91.62±0.55|75.71±0.44|42.22±2.45|44.44±3.01|51.60±0.62|89.75±0.44|95.84±0.41|84.72±0.72|6.4|\n|GOAT|35.90±1.31|95.20±0.54|89.43±1.28|79.41±0.81|36.27±2.13|44.10±4.06|51.47±0.96|89.85±0.57|95.48±0.33|85.56±0.72|9.9|\n|Polynormer|37.27±1.52|96.73±0.45|91.98±0.74|**92.46±0.43**|40.13±2.28|43.60±3.29|**53.35±1.06**|89.98±0.44|95.75±0.22|84.76±0.82|*5.2*|\n|r-IGNN|37.43±1.16|96.95±0.38|91.82±0.91|80.67±0.47|38.76±2.18|42.47±3.06|49.47±1.25|89.79±0.56|95.67±0.45|85.51±0.56|6.7|\n|a-IGNN|*37.58±0.88*|96.87±0.44|91.09±0.88|78.01±3.12|40.90±2.78|40.45±3.80|49.73±0.82|89.97±0.52|95.42±0.30|84.18±0.74|9.0|\n|c-IGNN|**38.71±1.00**|**97.13±0.21**|**93.23±0.61**|*86.07±0.60*|**43.89±1.79**|**47.13±5.18**|*53.01±0.77*|**90.30±0.41**|95.79±0.43|**86.09±0.48**|**1.5**|\n\nWe will revise the manuscript to include proper citations and discussions.\n\n> W4: the connection between these theoretical insights and the model design is not sufficiently clear...\n\nWe thank the reviewer for the opportunity to clarify the connection between our theoretical analyses and the architectural design.\n\n(1) **Theoretical Objectives**: Our theoretical investigation highlights the smoothness-generalization dilemma under varying homophily across hops, demanding\n(a) resolve the trade-off,\n(b) adaptive smoothness that aligns with varying homophily,\n(c) strong generalization across diverse structural conditions.\n\n(2) **Architectural Realization**: Our IGNN introduces three key principles\n   1. **IN: Decoupling dilemmas across hops (Lines 284–288).** While fully decoupling smoothness and generalization within message-passing is intractable due to their coupled factors (A,k,W), we address this by **decoupling the dilemmas across hops**. The Inceptive Aggregation (IN) **enables each hop to regulate its own smoothness-generalization trade-off independently**, without interference from other hops. This partial decoupling ensures hop-specific adaptation.\n   2. **RN: Enabling adaptive smoothness (Section 5.2.1).** To ensure that each hop can flexibly address its own homophily, we introduce three RN modules. We theoretically show that these RN modules, when built atop IN, **endow each hop with adaptive smoothness (Theorem 5.1), a key requirement for varying homophily.**\n   3. **SN: Enhancing generalization (Section 5.2.2).** Recognizing that different hops encounter distinct generalization challenges due to structural disparities (line 188-207), we further introduce SN. By isolating the transformation matrices across hops, SN enables **independent generalization capacities per hop (distinct Lipschitz constant)**. Our theoretical results demonstrate that SN leads to **a shrunk overall Lipschitz constant (Theorem 5.3)**, implying better generalization for the entire model.\n\nThis design is thus a direct and principled instantiation of our theoretical insights, ensuring that the dilemma is mitigated in a hop-aware and structure-sensitive manner.\n\n\n> Minor: It is recommended that the authors explicity inelude the intermediate variables in Table 2...\n\nThank you for your suggestion. We will carefully revise it to ensure better clarity.\n\n**Thank you again for your constructive comments.  Please let us know if you have any further questions. We’d be happy to clarify.**\n\n---\n[4] Haitao Mao, et al. Demystifying structural disparity in graph neural networks: Can one size fit all? NeurIPS 2024\n\n[5] Pei, Hongbin, et al. GEOM-GCN: GEOMETRIC GRAPH CONVOLUTIONAL NETWORKS. ICLR 2020.\n\n[6] Yan, Yujun, et al. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. ICDM 2022.\n\n[7] Song, Yunchong, et al. \"Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing.\" ICLR 23.\n\n[8] Zhu, Jiong, et al. Beyond homophily in graph neural networks: Current limitations and effective designs.  NeurIPS 2020."}, {"review_id": "GOP5WGy8lY", "reviewer": "Reviewer_3eBz", "summary": "This paper studies the problem of applying GNNs on both homophily and heterophily dataset. The authors propose a novel smoothness-generalization dilemma to uncover the theory behind the problem. Furthermore, the authors alleviate the dilemma and propose a new GNNs named Inceptive Graph Neural Network based on three design principles. The paper is overall well written and the theoretical part is well organized. The experimental results show the effectiveness of the proposed method, demonstrating the value of the dilemma.", "questions": "1.Concerning the hope-wise analysis, the two evaluated datasets are heterophily datasets, are there any homophily datasets or larger scale heterophily datasets? I expect the authors make detailed discussion on the neighbor hop, which is critical for IGNN.\n\n2.In the ablation study Table 5, why is GCN+SN not evaluated? And why GCN+SN+NR not evaluated?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n1.The phenomenon of GNNs success in both homophily and heterophily is quite interesting and the authors provide a theoretical dilemma to explain this. This can be valuable to the community, especially for the graph foundation models that aim to apply GNNs on various types of graphs.\n\n2.The dilemma is theoretically supported and the authors provide a detailed proof, I think the dilemma explains why GNNs can perform well on both homophily and heterophily.\n\n3.The inceptive GNN framework is simple but effective, the results show the effectiveness of the proposed IGNN. This show that the dilemma is both theoretical and practical useful.\n\n**Weaknesses**\n\n1.Concerning the proposed IGNN method, the combination of SN, IN and NR may make the IGNN complex. As a result, the complexity of IGNN should be carefully evaluated and discussed. \n\n2.The combination may require careful tuning of hyperparameters，the authors should provide comprehensive tuning results. The table 11 only provide hyperparameter configureation rather than detailed tuning results.", "was_revised": true, "final_justification": "I have read all the reviews and the responses. All of my concerns have been well addressed. I think this is a solid and interesting work. I support the acceptance of this work.", "rebuttal": "> W1:  **the complexity** of IGNN should be carefully evaluated and discussed.\n\nWe appreciate the reviewer’s suggestion for the complexity. Due to space constraints in the main paper, **we provided model complexity, parameter count, and runtime analysis in Appendix B**. Below, we summarize the key findings for convenience. For details, please refer to **Appendix B.1**.\n\n- r-IGNN: The residual connection does not significantly change the complexity compared to GCN.  If the representation of the previous hop also has a transformation in the residual connection  (which we do not apply in our implementations), then it will require more parameters.\n- a-IGNN: The model adaptively determines α_v^(k) for each node, which slightly reduces the parameter count (O(K · 2F)). Its per-layer complexity is lower than others, but still scales with the number of edges and nodes.\n- c-IGNN: **The explicit multi-hop aggregation increases computational cost compared to GCN**. The complexity grows with K, making it more expensive as the number of hops increases. However, it enjoys hop-wise distinct generalization and overall generalization, which holds significance in GNN universality across varying homophily.\n- Fast c-IGNN (see Appendix B.1): By decoupling aggregation into preprocessing, it shifts the expensive aggregation operations outside training. This makes it scalable for large graphs. Among these models, **Fast c-IGNN achieves the best scalability by precomputing multi-hop aggregation. In contrast, a-IGNN and r-IGNN require more computational resources due to their recursive neighborhood aggregation.**\n\nWe hope these analyses sufficiently address the reviewer’s concern.\n\n> W2: authors should provide comprehensive tuning results.\n\nWe thank the reviewer for highlighting the importance of  hyperparameter tuning.\n\n(1) While Table 11 in Appendix E.2.2 provides the final configurations, we fully agree that reporting the tuning process is also important. To support reproducibility, **we have already released the detailed search space definitions in our anonymous repository as presented in Appendix E.2.2 (line 840)**. Based on this, researchers can readily reproduce the tuning process using standard hyperparameter optimization frameworks such as Optuna [1], in combination with our publicly available codebase.\n\n(2) In response to the reviewer’s suggestion, we will additionally include ready-to-run Optuna tuning scripts in the revised version of the code repository. \nDue to the NeurIPS 2025 anonymity policy, we are currently unable to update the anonymous repository during the rebuttal period. We apologize for this temporary limitation, but we will ensure these scripts are included in the revised version.\n\n> Q1: Concerning the hope-wise analysis,  the two evaluated datasets are heterophily datasets, are there any homophily datasets or larger scale heterophily datasets?\n\nWe thank the reviewer for the thoughtful question.\n\n(1) We would like to clarify that the datasets used in the hop-wise analysis **already cover both homophilic and heterophilic regimes (line 386-392)**. Specifically:\n\n- The Photo dataset has a high homophily ratio of 0.8272, representing a typical homophilic graph.\n\n- The Squirrel dataset has a low homophily ratio of 0.2072, representing a heterophilic graph.\n\nThis combination allows us to evaluate the behavior of different IGNN variants across contrasting structural regimes. As shown in Figure 4, **our variants consistently show a first increase then steady performance trend across a wide range of hops (from 0 to 64), demonstrating strong adaptability in both settings**.\n\n(2) In response to the reviewer's suggestion regarding larger-scale heterophilic datasets, we have additionally showcased a hop-wise analysis on Pokec, a real-world social network dataset with heterophily (homophily ratio ≈ 0.44). \n||3|8|16|\n|-|-|-|-|\n|r-IGNN|75.49±4.56|82.44±0.51|82.01±0.53|\n|a-IGNN|74.49±4.56|82.02±0.45|81.98±0.35|\n|c-IGNN|72.49±0.56|80.72±0.06|81.37±0.15|\n\nThe results exhibit a notable increase in performance that stabilizes thereafter, highlighting the effectiveness in improving hop-wise and overall generalization.\n\n> Q2:  why is GCN+SN not evaluated? And why GCN+SN+RN not evaluated\n\nWe appreciate the reviewer’s thoughtful questions.\n\nWe did not include GCN+SN or GCN+SN+RN in our ablation studies because the **SN module is designed to operate in conjunction with the IN structure**. Specifically, without the IN architecture, the transformation layers are shared or decoupled across all hops, and thus SN cannot effectively disentangle the transformations of different neighborhood orders. As a result, without IN, applying SN in isolation or in combination with RN would not preserve its intended design or functionality.\n\nHowever, to assess the contribution of SN in a meaningful context, **we evaluated its addition to the IN and IN+RN settings**, as shown in Table 5. In both cases, we observe consistent performance gains, validating SN’s utility in adapting to varying homophily and improving generalization.\n\nIn short, **SN is not a standalone module but rather one that is structurally dependent on the IN design**. We will clarify this architectural dependency and our evaluation choices more explicitly in the revised version.\n\n**We appreciate your time and are open to any follow-up questions.**\n\n---\nReferences:\n\n[1] Akiba, Takuya, et al. \"Optuna: A next-generation hyperparameter optimization framework.\" Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. 2019."}, {"review_id": "D21KMmMp8U", "reviewer": "Reviewer_mzgb", "summary": "This paper argues that separately designed GNN architectures for homophilic and heterophilic graphs are not the way forward, but rather different levels of homophily at different orders of neighborhoods in a graph should also be catered to. To suppor this, they present three design principles, against which they assess several existing architectures, and based on a combination of these techniques, claim propose a more universal architecture. In doing so, the paper also sheds lights on what makes these popular existing GNN architectures successful in dealing with oversmoothing and achieving desirable generalization performance.", "questions": "1. What is the source of Fig 1 (c) and (d) and what does the zig-zag-like pattern in them signify?\n2. By 'smoothness', do the authors refer to the smoothing induced by the transformation step or the aggregation step in GNNs? \n3. Line 164 \"Consequently, either oversmoothing or poor generalization will occur at large $k$\".  I believe the whole point was a smoothness-generalization trade-off, i.e. oversmoothing would lead to poor generalization, so how is this an either-or situation?\n4. Could dirichlet energy, a common smoothness measure, also be used to showcase the trade-off between smoothness and generalization empirically and how it varies for IGNN?\n5. Do the architectures like GAT-sep[4] and GATE-sep that also combine the ego node features with the neighborhood based on concatenation also  incorporate all three principles?\n\n[4] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? (ICLR 2023).\n\n[5] GATE: How to Keep Out Intrusive Neighbors (ICML 2024)", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: \n\n1. The core idea of catering to different levels of homophily and heterophily even within the same graph and moving away from the assumption that it is known if/how an input is homophilic or heterophilic is directed towards understanding and designing more universal GNN design.\n2. The paper consolidates well-known existing GNN architectures under a unifying framework with a set of design principles against which GNNs can be analyzed and that can guide the design of even newer or more efficient architectures. \n\nWeaknesses:\n\n1. I understand that the authors have already used several baselines to compare their approach against, but there are some recent approaches that aim to cater to both homophily and heterophily but are missing from the discussion/evaluation, such as sign-based propagation methods such a FAGCN [1] and $\\omega$GAT [2] and more adaptive message passing methods capable of varying receptive fields at the node level such as CO-GNNs[3]. \n2. The paper is a little difficult to read and follow. For example, the abbreviated terms need to be tracked and mapped to different concepts throughout, some statements and figures are confusing (See Questions 1 and 3). \n\nminor: line 78: classic GCNs enhanced -> classic GCNs be enhanced\n\n[1] Beyond Low-frequency Information in Graph Convolutional Networks (AAAI 2021)\n\n[2] Improving Graph Neural Networks with Learnable Propagation Operators (ICML 2023)\n\n[3] Co-operative GNNs (ICML 2024)", "was_revised": true, "final_justification": "Given the extended evaluation provided during the rebuttal and adequate resposne to my questions, I have increased my final score to 5.", "rebuttal": "> W1: some recent approaches that aim to cater to both homophily and heterophily but are missing...FAGCN [1] and \\omega GAT [2]**...**CO-GNNs[3]...\n\nThank you for the valuable suggestion. We have now included the results of FAGCN [1], ω-GAT [2], and Co-GNN [3] as follows, which compares the top-10 methods in table 3 (Overal performance in the manuscript) including Polynormer and GOAT as suggested by other reviewers.\n\n\n|**model**|**actor**|**blogcatalog**|**flickr**|**roman-empire**|**squirrel**|**chameleon**|**amazon-ratings**|**pubmed**|**photo**|**wikics**|**A.R.**|\n|-|-|-|-|-|-|-|-|-|-|-|-|\n|**IncepGCN**|35.69±0.75|96.67±0.48|90.42±0.71|80.97±0.49|38.27±1.36|43.31±2.18|52.72±0.80|89.32±0.47|95.66±0.40|85.22±0.48|10.1|\n|**SIGN**|36.76±1.00|96.06±0.68|91.81±0.58|81.56±0.57|42.13±1.99|44.66±3.46|52.47±0.95|*90.29±0.50*|95.53±0.43|85.59±0.79|6.5|\n|**MixHop**|36.82±0.98|96.05±0.48|89.78±0.63|79.39±0.40|41.35±1.04|44.61±3.16|47.91±0.53|89.40±0.37|94.91±0.45|83.15±0.96|12.8|\n|**DAGNN**|35.04±1.03|96.73±0.61|92.18±0.73|73.94±0.45|35.62±1.48|40.96±2.91|50.44±0.52|89.76±0.55|95.70±0.40|85.07±0.73|11.2|\n|**GCNII**|35.69±1.08|96.25±0.61|91.36±0.68|80.55±0.82|38.43±2.10|42.13±2.04|47.65±0.48|90.00±0.46|95.54±0.34|85.15±0.56|11.3|\n|**OrderedGNN**|36.95±0.85|96.39±0.69|91.13±0.59|82.65±0.91|36.27±1.95|42.13±3.04|51.58±0.99|90.01±0.40|*95.87±0.24*|85.60±0.77|7.7|\n|**N2**|37.41±0.60|94.72±0.57|91.08±0.79|75.32±0.41|39.35±2.39|38.60±1.12|48.08±0.76|89.16±0.24|**95.92±0.27**|84.07±0.39|13.0|\n|**UniFilter**|36.11±1.04|96.534±0.47|91.89±0.75|74.90±0.91|*42.40±2.58*|*46.07±4.74*|49.36±0.98|90.15±0.39|94.91±0.62|85.43±0.67|8.8|\n|**DIFFormer**|36.13±1.19|96.50±0.71|90.86±0.58|79.36±0.54|41.12±1.09|41.69±2.96|49.33±0.97|88.90±0.47|95.67±0.29|84.27±0.75|11.9|\n|**SGFormer**|37.36±1.11|*96.98±0.59*|91.62±0.55|75.71±0.44|42.22±2.45|44.44±3.01|51.60±0.62|89.75±0.44|95.84±0.41|84.72±0.72|7.3|\n|**GOAT**|35.90±1.31|95.20±0.54|89.43±1.28|79.41±0.81|36.27±2.13|44.10±4.06|51.47±0.96|89.85±0.57|95.48±0.33|85.56±0.72|11.3|\n|**Polynormer**|37.27±1.52|96.73±0.45|91.98±0.74|**90.48±0.50**|40.13±2.28|43.60±3.29|**53.35±1.06**|89.98±0.44|95.75±0.22|84.76±0.82|*5.9*|\n|**FAGCN**|35.98±1.34|96.67±0.35|*92.74±0.79*|75.65±1.01|40.83±3.08|42.70±3.33|50.14±0.76|90.24±0.51|95.31±0.45|85.02±0.51|9.3|\n|**CoGNN**|37.52±1.66|96.41±0.56|89.91±0.93|*87.57±0.46*|37.89±2.23|40.45±2.48|52.89±0.81|89.49±0.53|95.15±0.55|*85.70±0.71*|9.7|\n|**wGAT**|34.66±0.97|94.95±0.61|90.20±1.13|80.98±1.00|34.07±2.16|41.07±4.23|48.81±0.92|89.58±0.50|95.19±0.47|85.17±0.83|14.0|\n|**r-IGNN**|37.43±1.16|96.95±0.38|91.82±0.91|80.67±0.47|38.76±2.18|42.47±3.06|49.47±1.25|89.79±0.56|95.67±0.45|85.51±0.56|7.7|\n|**a-IGNN**|*37.58±0.88*|96.87±0.44|91.09±0.88|78.01±3.12|40.90±2.78|40.45±3.80|49.73±0.82|89.97±0.52|95.42±0.30|84.18±0.74|10.1|\n|**c-IGNN**|**38.71±1.00**|**97.13±0.21**|**93.23±0.61**|86.07±0.60|**43.89±1.79**|**47.13±5.18**|*53.01±0.77*|**90.30±0.41**|95.79±0.43|**86.09±0.48**|**1.6**|\n\nThese methods achieve mid-range average ranks overall. We believe they are still worth discussing due to the following reasons:\n\n(1) **FAGCN and ωGAT are both variants of the a-IGNN family**, which achieves adaptive filtering capabilities. As shown in our experimental section, **a-IGNN variants (e.g., GPRGNN, OrderedGNN, DAGNN, ACMGCN, etc.) exhibit significantly diverse performance**, which we attribute to their customized attention-based designs. **This highlights the sensitivity of their results to hand-crafted attention mechanisms**.\n\n(2) Co-GNN, on the other hand, is a node-level dynamically adaptive message-passing method.**It demonstrates unique advantages in neighbor selection and long-range tasks**. For instance, in the roman-empire dataset, a long-chain language-token graph generated from word sequences and syntactic dependencies, Co-GNN outperforms many baselines due to its fine-grained adaptivity, while the graph transformer Polynormer shows great advantages probably due to the success of the transformer architecture in language tasks.\n\nWe will incorporate the results and cite these methods in the revised version accordingly.\n\n\n> W2: ..some statements and figures are confusing (See Questions 1 and 3)...\n\nWe thank the reviewer for the helpful suggestions on improving the clarity of specific statements and visual elements. Below, we provide point-by-point responses and will revise the corresponding text and figures to improve clarity in the final version.\n\n> Q1: What is the source of Fig 1 (c) and (d) and what does the zig-zag-like pattern in them signify?\n\nWe appreciate the reviewer’s attention to Fig. 1 (c) and (d). These plots are designed to **offer visual intuition for the core insight of our work**.\n\nFig. 1(c) **illustrates the emergence of a dilemma** between smoothness and generalization in classic GCN message passing across varying levels of homophily of difference hops. \n\nFig. 1(d)  **illustrates the alleviation of this dilemma** through decoupled adaptive smoothness and generalization, demonstrating how an ideal architecture would balance smoothness and generalization dynamically.\n\nThese figures are conceptual illustrations intended to reflect our theoretical findings. We will revise the captions to make these intentions clearer.\n\n> Q2: By 'smoothness', do the authors refer to the smoothing induced by the transformation step or the aggregation step\n\nThis is an excellent question. In our theoretical analysis, we consider smoothness as influenced by **both the aggregation step and the transformation step**.\n\nIn particular, the smoothness indicator d_M(H^(l)), as discussed in **Corollary 3.2 and Theorem 4.1**, is bounded by: the second largest eigenvalue of the adjacency matrix (capturing **the aggregartion effect**), and the maximum singular value or Lipschitz constant of the transformation matrix W^(l) (capturing **the effect of the transformations**).\n\nTherefore, our analysis integrates both sources of smoothness. We will revise the explanation to more clearly reflect this dual contribution.\n\n> Q3: \"Consequently, either oversmoothing or poor generalization will occur at large k\". I believe the whole point was a smoothness-generalization trade-off, i.e. oversmoothing would lead to poor generalization, so how is this an either-or situation?\n\nWe appreciate the reviewer’s thoughtful question and the opportunity to clarify this point.\n\nWhile it is true that oversmoothing typically leads to poor generalization, our theoretical framework reveals a more nuanced dilemma:\n- If the model attempts to counteract oversmoothing (i.e., to recover discriminative representations from the over-smoothed A^kX) by **increasing the spectral norm of W^(i)**, this leads to a larger Lipschitz constant, which in turn worsens the generalization.\n- Conversely, if **the model limits the norm of W^(i) to maintain a low Lipschitz constant** and preserve generalization ability, **it cannot effectively reverse the over-smoothed A^kX**, resulting in poor discriminability of node embeddings.\n\nIn this sense, the phrase emphasizes that **attempting to fix one inevitably worsens the other**. This constitutes the core of the smoothness–generalization trade-off we identify: **mitigating oversmoothing through amplification degrades generalization, while preserving generalization risks severe embedding collapse**.\n\nWe will revise the phrasing in the final version to make this interplay clearer and avoid the false implication of mutual exclusivity.\n\n> Q4: Could dirichlet energy be used to showcase the trade-off between smoothness and generalization empirically and how it varies for IGNN?\n\nThank you for this insightful suggestion. Indeed, as shown in Lemma 1 of [1], the Dirichlet energy at the k-th layer of a GCN can be upper and lower bounded by the eigenvalues of the (augmented) normalized Laplacian and the singular values of the transformation matrices. **This implies a theoretical connection between Dirichlet energy and the smoothness-generalization we found in our framework**.\n\nWhile we focus on a different smoothness measure in this work, the Dirichlet energy may indeed serve as **an alternative empirical indicator of the dilemma** and may help further validate and extend our findings. We consider this a promising direction for future research and will mention this possibility in our discussion section.\n\n> Q5: Do the architectures like GAT-sep and GATE-sep ... also incorporate all three principles?\n\nWe thank the reviewer for this important question.\n\nNo, architectures such as **GAT-sep and GATE-sep do not satisfy all three of our proposed design principles**. Specifically, while they implement ego-neighbor separation by isolating the ego features H^(0) from aggregated multi-hop features H^(K), **they do not realize inceptive message passing across intermediate neighborhood hops H^(1)~H^(k)**. This limits their ability to achieve the fine-grained neighborhood-wise generalization that our design principle emphasizes.\n\nIt is worth noting that ego-neighbor separation has indeed become a common technique in heterophilic GNNs, first formalized in H2GCN, and subsequently adopted by many follow-up works such as GPR-GNN, ACM-GCN, and even some recent graph transformer implementations. However, our experiments demonstrates that ego-neighbor separation alone is not sufficient to achieve optimal performance. Several models that incorporate this technique still underperform compared to those that fully embrace more principles of inceptive message passing.\n\nIn summary, while ego-neighbor separation is benefit for heterophilic settings, GAT-sep and GATE-sep  do not fulfill the full set of principles proposed in our framework.\n\n**We thank the reviewer for the constructive comments. We’re happy to address any remaining concerns.**\n\nReferences:\n\n[1] Zhou, Kaixiong, et al. \"Dirichlet energy constrained learning for deep graph neural networks.\" Advances in neural information processing systems 34 (2021): 21834-21846."}, {"review_id": "aUsXlY91hy", "reviewer": "Reviewer_SKcX", "summary": "The paper highlights the problem of oversmoothing in graph neural networks (GNNs) and studies it’s connection to generalization under the “smoothness-generalization dilemma”. The paper provides a theoretical analysis of over-smoothing connecting it to generalization through a novel bound on the distance from the representations to the subspace M. The paper also introduces IGNN as well as three variants (r-IGNN, a-IGNN and c-IGNN) to alleviate the problem of oversmoothing in graphs with different levels of homophily. This novel method is evaluated across several datasets and compared to several existing methods.", "questions": "What is the difference between the “smoothness-generalization dilemma” and the known problem of oversmoothing? Oversmoothing always implies a drop in performance, why is the tie to OOD generalization particularly interesting? What parts of this dilema are novel and what parts have been previoulsy studied? Making these things clearer would improve the paper.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n-\tThe paper tackles the known and important problem of over-smoothing and provides novel theoretical insights.\n-\tThe paper introduces the inceptive graph neural network (IGNN), a well motivated method with convincing results across different datasets.\n-\tThe paper is clear, well written, thorough in its evaluation and seems theoretically sound. \n\n**Weaknesses:**\n\n-\tThe paper does not sufficiently engage with the extensive over-smoothing literature. The connection to over-smoothing is first mentioned in line 165. While it does seem like this paper adds something new to the theoretical connection between generalization and oversmoothing, the following line does not convey the amount of existing work connecting oversmoothing to generalization, risk or decreases in test accuracy (Keriven 2022, Wu et al. 2023, Oono & Suzuki 2020 to name a few). “Note that several works [25] have analysed the oversmoothing in GNNs. However, they fail to connect it with generalization.”. Similarly saying the paper “uncovers a novel smoothness-generalization dilemma” in the abstract and the introduction would suggest that the field was not aware that oversmoothing hurts generalization. I understand that this work is more focused on OOD generalization and it's connection to oversmoothing, but it should be clearer that previous works have studied how oversmoothing hurts performance in GNNs and why the distinction of focusing on OOD generalization is important. Framing the contributions of this paper in the context of the oversmoothing literature, clearly highlighting novel and existing work would improve the paper.  \n-\tSimilarly, clearly stating that several existing architectures satisfy one or 2 of the design principles but c-IGNN is the first one to satisfy all 3 would make the paper’s contributions clearer. While this is clearly conveyed in the Appendix (Table 9), I believe it should be made clear in Section 5 and perhaps in the introduction. Mentioning some existing methods that follow each design principle could also help convey the intuition to readers familiar with previous methods. \n\n\nKeriven, N. (2022). Not too little, not too much: A theoretical analysis of graph (over)smoothing. Advances in Neural Information Processing Systems, 35 (NeurIPS 2022). https://doi.org/10.48550/arXiv.2205.12156\n\nWu, X., Ajorlou, A., Wu, Z., & Jadbabaie, A. (2023). Demystifying Oversmoothing in Attention-Based Graph Neural Networks. Advances in Neural Information Processing Systems, 36 (NeurIPS 2023). https://doi.org/10.48550/arXiv.2305.16102\n\nOono, K., & Suzuki, T. (2020). Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. International Conference on Learning Representations (ICLR 2020). https://doi.org/10.48550/arXiv.1905.10947", "was_revised": true, "final_justification": "The authors have addressed my main concerns regarding a clearer discussion and delimitation from the oversmoothing literature, as well as a clearer acknowledgement of other methods that satisfy some of their design principles. \n\nGiven these changes I am happy to increase my rating from a 4 to a 5 and recommend acceptance.", "rebuttal": "> Q1: What is the difference between the “smoothness-generalization dilemma” and the known problem of oversmoothing?\n\nWe appreciate the reviewer’s thoughtful question and the opportunity to clarify this point.\n\nThe classical over-smoothing problem refers to a phenomenon **predominantly studied in homophilic graphs**, where repeated message passing over **high-order neighborhoods** leads to node representations becoming overly similar or even indistinguishable. This convergence diminishes discriminative power and degrades performance, particularly in **deeper GNNs**.\n\nIn contrast, the smoothness-generalization dilemma proposed in our work is a **broader and more general phenomenon**. It encapsulates a fundamental trade-off between enforcing smoothness and maintaining strong generalization across diverse graph structures, including **both homophilic and heterophilic graphs, and across both low-order and high-order neighborhoods**.\n\nSpecifically, we show that in heterophilic graphs, even low-order neighborhoods can exhibit complex neighborhood class distributions. In such cases,  **smoothing acorss low-order hops, even at shallow layers, can distort informative signals, harming generalization**. Furthermore, under distributional shifts induced by noise or sparsity, such poor generalization hurts performance, **regardless of whether over-smoothing occurs**.\n\nIn summary, **over-smoothing can be regarded as a special case of the broader smoothness-generalization dilemma across varying homophily and neighborhood orders**.\n\n> Q2: Oversmoothing always implies a drop in performance, why is the tie to OOD generalization particularly interesting?\n\nWe thank the reviewer for raising this important question.\n\nWhile it is well established that over-smoothing leads to performance degradation, our work reveals a deeper underlying mechanism, namely, the tension between smoothness and generalization, which governs this behavior and extends beyond classical interpretations.\n\n(1) **A unified perspective on varying homophily and oversmoothing**.\nTraditionally, over-smoothing and homophily variation have been treated as separate challenges in GNN design: the former associated with high-order aggregation in homophilic graphs, and the latter with poor representation in heterophilic graphs. Our formulation **unifies both phenomena** under the broader lens of the **smoothness-generalization dilemma**, which captures the fundamental trade-off between enforcing smoothness and achieving robust generalization under neighborhood class distribution shifts.\n\nThis perspective explains why:\n\n- In high-order neighborhoods, smoothness impairs generalization due to over-smoothing.\n- In low-order, heterophilic settings, smoothness also harms generalization, even though classical over-smoothing does not occur.\n\nBy identifying a shared root cause (e.g., the conflict between smoothness and generalization of task-relevant signals under structural variability), our framework offers theoretical insights that span different homophily regimes and neighborhood orders, providing practical guidance for architecture design.\n\n(2) We further emphasize that the negative impact of over-smoothing is not solely due to the convergence of node representations  (e.g., via A^kX). Instead, the core issue lies in **the inability to balance discriminative expressiveness with generalization**.\n\nIn theory, one might attempt to recover expressiveness after smoothing (e.g., through large transformation weights W^(i)). However, our analysis shows that while such compensation may improve **training performance**, it often **worsens generalization**, particularly in graphs of varying homophily, where minor structural perturbations can cause significant shifts in local distributions [1].\n\nThis explains a widely observed empirical phenomenon: GNNs can perform well on the training set despite over-smoothing, yet exhibit sharp performance drops on the test set.  Our formulation provides a theoretical explanation for this gap, demonstrating that **generalization failure—not representational collapse alone—is the crux of the issue**. This makes the connection to OOD generalization both novel and essential for understanding the practical limitations of current GNNs.\n\n> Q3: What parts of this dilema are novel and what parts have been previoulsy studied? \n\nWe appreciate the reviewer’s question and the opportunity to clarify the novel contributions of the dilemma.\n\nWhile the issue of **oversmoothing in high-order neighborhoods**, particularly in homophilic graphs, has been previously investigated, our work extends beyond this established line of inquiry by identifying a **general smoothness–generalization trade-off** that emerges not only in high-order settings but also **across both low- and high-order neighborhoods, and under varying degrees of homophily and structural disparity**.\n\nNotably, we show that performance degradation can occur even **in the absence of classical oversmoothing**, uncovering new failure modes of GNNs that are not explained by existing theories. **This observation is particularly important for graphs of varying homophily**, where conventional wisdom about neighborhood similarity does not hold, yet degradation still arises through a different mechanism tied to the message passing itself.\n\n**Our contribution lies in reframing and extending oversmoothing and varying homophily within a broader and more general theoretical framework**, allowing us to explain performance degradation at different neighborhoods and varying homophily under a single analytical lens. This unification enables **a consistent understanding of GNN behavior across different regimes of homophily, depth, and structural variation.**\n\nWe believe this reframing offers important insights for both theoretical understanding and practical GNN design.\n\n---\n> W1: ...does not convey the amount of existing work connecting oversmoothing to generalization, risk or decreases in test accuracy (Keriven 2022, Wu et al. 2023, Oono & Suzuki 2020 to name a few)...it should be clearer that previous works have studied how oversmoothing hurts performance in GNNs and why the distinction of focusing on OOD generalization is important...\n\nWe sincerely thank the reviewer for this insightful comment.\n\nWe fully agree that our current draft could better contextualize our contribution within the existing body of work connecting oversmoothing to generalization performance, and we will revise the manuscript accordingly to explicitly cite and discuss the relevant studies, including Oono & Suzuki (2020), Keriven (2022), and Wu et al. (2023).\n\nOur work builds upon and extends this line of research in the following key ways:\n- **Theoretical Advancement**: We adopt the analytical framework of Oono & Suzuki (2020), as discussed in our preliminaries, and derive a tighter upper bound that explicitly links smoothness to generalization performance, offering a clearer and more refined understanding of the trade-off involved.\n- **Extension to Varying Homophily**: While prior works focus on oversmoothing primarily in homophilic and high-order settings, we demonstrate that performance degradation also arises under varying degrees of homophily, including **low-order neighborhoods**, which cannot be captured by classical oversmoothing analyses alone. This significantly broadens the scope of prior studies.\n- **Architectural Contribution**: **Unlike all the three works, which focus on theoretical analysis without architectural innovation, we propose a unified IGNN framework that is empirically validated**. Our design incorporates three variants tailored to mitigate the smoothness–generalization trade-off under diverse homophily regimes.\n- **Broader Perspective**: Keriven (2022) and Wu et al. (2023) focus on oversmoothing without considering structural disparity or varying homophily. Wu et al. (2023), in particular, restricts its analysis to attention-based GNNs and task-specific test risk without offering architectural strategies. In contrast, our IGNN framework provides a generalizable design principle that addresses smoothness and generalization across different architectures and homophily conditions, thereby offering a unified perspective for future GNN development.\n\nWe will ensure that these distinctions are made clearer in the revised manuscript.\n\n---\n> W2:  While this is clearly conveyed in the Appendix (Table 9), I believe it should be made clear in Section 5 and perhaps in the introduction. Mentioning some existing methods that follow each design principle could also help convey the intuition to readers familiar with previous methods.\n\nWe appreciate the reviewer’s helpful suggestion regarding the clarity.\n\nWhile Table 9 in the Appendix provides a comparison that illustrates how existing architectures satisfy one or two of the proposed design principles, **we agree that this distinction should be more prominently and explicitly presented in the revised main paper**. We will revise Section 5 to clearly highlight that c-IGNN is the first architecture to simultaneously satisfy all three principles, in contrast to prior methods that typically meet only a subset.\n\nWe appreciate the reviewer’s thoughtful feedback, which will help improve the clarity of our presentation.\n\n**We thank the reviewer for the insightful comments. Please let us know if you have any further questions. We’d be happy to clarify.**\n\nReferences:\n\n[1] Haitao Mao, Zhikai Chen, et. al. Demystifying structural disparity in graph neural networks: Can one size fit all? Advances in neural information processing systems, 36, 2024"}]

Author rebuttal:

Meta-review: This paper designs more universal GNN architecture that can generalize across graphs with varying levels of homophily and heterophily. It also introduces new theoretical insights for varying homophily and oversmoothness. The problem tackled in this work is important and the proposed approaches and principles are novel and interesting. All reviewers are happy with the paper quality after the rebuttal. 

Several reviewers have noted that the paper lacks a comprehensive literature review or misses important baselines. I recommend that the authors expand the related work section, particularly by including discussions on topics such as over-smoothing and heterophilous GNNs, in the final version.
Decision: Accept (poster)