Interpretable and Parameter Efficient Graph Neural Additive Models with Random Fourier Features
Authors: Thummaluru Siddartha Reddy
Vempalli Naga Sai Saketh
Mahesh Chandran
Venue: NeurIPS 2025 poster ()
Keywords: Interpretability
Graph Neural networks
Finite Impulse Response Filters
Random Fourier Features
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: Parameter efficient interpretable neural additive model for graph data

Abstract: Graph Neural Networks (GNNs) excel at jointly modeling node features and topology, yet their black-box nature limits their adoption in real-world applications where interpretability is desired. Inspired by the success of interpretable Neural Additive Models (NAM) for tabular data, Graph Neural Additive Network (GNAN) extends the additive modeling approach to graph data to overcome limitations of GNNs. While being interpretable, GNAN representation learning overlooks the importance of local aggregation and more importantly suffers from parameter complexity. To mitigate the above challenges, we introduce Graph Neural Additive Model with Random Fourier Features (G-NAMRFF), a lightweight, self‐interpretable graph additive architecture. G-NAMRFF represents each node embedding as the sum of feature‐wise contributions where contributions are modeled via a Gaussian process (GP) with a graph- and feature-aware kernel. Specifically, we construct a kernel using Radial Basis Function (RBF) with graph structure induced by Laplacian and learnable Finite Impulse Response (FIR) filter. We approximate the kernel using Random Fourier Features (RFFs) which transforms the GP prior to a  Bayesian formulation, which are subsequently learnt using a single layer neural network with size equal to number of  RFF features. G-NAMRFF is light weight with $168\times$ fewer parameters compared to GNAN. Despite its compact size,  G-NAMRFF matches or outperforms state-of-the-art GNNs and GNAN on node and graph classification tasks, delivering real-time interpretability without sacrificing accuracy.

Interpretable and Parameter Efficient Graph Neural Additive Models with Random Fourier Features
Thummaluru Siddartha Reddy, Vempalli Naga Sai Saketh, Mahesh Chandran (Thummaluru Siddarthareddy, nagasaisaketh, vempalli, Mahesh. Chandran @ @ujitsu.com
Fujitsu Research of India, Bangalore.
Abstract
Graph Neural Networks (GNNs) excel at jointly modeling node features and topol- ogy, yet their black-box nature limits their adoption in real-world applications where interpretability is desired. Inspired by the success of interpretable Neural Additive Models (NAM) for tabular data, Graph Neural Additive Network (GNAN) extends the additive modeling approach graph data overcome limitations of GNNs. While being interpretable, GNAN representation learning overlooks the importance of local aggregation and more importantly suffers from parameter complexity. To mitigate the above challenges, we introduce Graph Neural Additive Model with Random Fourier Features (G- NAMRFF), a lightweight, celf-interpretable graph additive architecture. G-NAMRFF represents each node embedding as the sum of feature-wist contributions where contributions are modeled via Gaussian process (GP) with graph- and -waae kernel. Specifically, we construct a kernel using Radial Basis Function (RBF) with graph structure induced by Lapla- cian and learnable Finite Impulse Response (FIR) filter. We approximate the kernel using Random Fourier Features (RFFs) which transforms the GP prior to a Bayesian formulation, which are subsequently learnt using single layer neural network with size equal to number of RFF features. G- G-NAMRFF is light weight with 168x fewer parameters compared to GNAN. Despite its compact size, G-NAMRFF matches or outperforms state-oftthe-- GNNs and GNAN on node and graph classification tasks, delivering real-time interpretability without sacrificing accuracy
Introduction
Graph Neural Networks (GNNs) powerful and topology-aware deep representation learning
architectures that leverage the structure of graphs as an inductive bias [12 20 33). While GNNs
have demonstrated impressive performance various downstream machine learning tasks such as
node and graph classification, they remain largely as a black-box models 5
3 As result, the
learned representations often lack interpretability which limits their adoption in regulated domains like healthcare, finance, and defense 315). Interpretability in machine learning focuses on designing models whose representations directly reveal how each feature contributes the output (28). This stands in contrast to post hoc explainable models which seeks to generate explanations for the model inference after the model has been trained
3 [3
Additive models are the cornerstone for interpretable representation learning for tabular data. Notable examples of such models includes Neural Additive Model (NAM) [2], Neural Basis Model (NBM) 24 and Gaussian Process Additive Model (CPAM) [41. The key innovation of this additive model lies in its ability handle each feature independently by learning a separate univariate function for every feature and then summing these contributions to obtain the final prediction. Although all these models share common trait i.e., additive structure, they differ in how each feature's
Code reproduce the results available at abtp:://gghbbbooooooiiiooeeoeeee
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

univariate function is represented and learned. For example, NAM approximates each feature's s effect with a dedicated deep neural network (DNN), yielding high flexibility but also posing significant computational overhead. In contrast, NBM and GPAM represent each feature using fixed dictionary of basis functions (e.g., splines, Fourier bases, or Gaussian process kernels) and learn only the linear combination of weights, thereby retaining interpretability while dramatically reducing training time.
Building on the success of additive models for tabular data, efforts have been made to extend to graph data. GNAN is the first graph neural additive model that incorporates graph structure as an inductive bias into a neural additive models [5], thus making it self- interrettrreet glass-box model by design, in contrast to the conventional and well-studied post- hoc models designed to explain black-box GNNs outputs [31 37 22 17.. GNAN disentangles feature effects and graph topology by learning separate univariate functions, one per each feature and one for neighborhood weighting via DNNs, respectively. The neighborhood weighting done through distance measure that spans the entire graph. However, this design has two key drawbacks. Firstly, modeling each feature and neighbourhood with separate neural networks with multiple layers leads to a large trainable parameters with a sigmificant training time. Secondly, for graph with N nodes and E-edges,
Number of learnable parameters
10'
10
10a
10
G-NAMRFF
GNAN
1000
2000 3000
4000 5000
Feature dimension (D)
Figure 1: Parameter complexity.
GNAN aggregation over all nodes requires O(N + F)) distance computations per node, leading to quadratic scaling of the neighbourhood weighting function with graph size. Additionally, distant, non-neighbouring nodes influence the embeddings through the weighting function in a non-trivial way, introducing opacity to the interpretation unlike localized aggregation.
In this work, we introduce the Graph-aware Neural Additive Model with Random Fourier Features (G-NAMRFF), a lightweight and inherently interpretable glass-box model designed for representation learning with graphs. Similar to NAM, G-NAMRFF represents each node prediction as the sum of individual feature contributions; however, it replaces deep neural networks with Gaussian Pro- cess (GP) prior characterized by a kernel explicitly designed to be both graph- and feature-aware. Specifically, we propose a similar attributes to yield similar outputs. In particular, the proposed kernel can be expressed as a Radial Basis Function (RBF) where inputs are projected features that capture one-hop neighbourhood in the graphs. Based on Bochner's theorem, we approximate the kernel effectively using RFFs, transforming the GP priors into a linear Bayesian formulation. To effectively capture multi-hop graph information, we embed the node features using Finite Impulse Response (FIR) filters with trainable coefficients. These coefficients, trained jointly with univariate functions help uncover critical graph structural information by highlighting which hops significantly influence the node predictions. With the equivalent Bayesian linear model established, we learn the model parameters using a single-layer network whose complexity depends solely on the number of RFFs, thereby ensuring G-NAMRFF's computational efficiency and lightweight nature. Figure 1 illustrates the parameter complexity comparison between our proposed model and existing method, clearly demonstrating the reduced parameter requirements of our approach. More importantly, by feeding RFFs with structure- features computed via learnable filter coefficients, our model seamlessly integrates graph topology and feature mapping into single module unlike GNAN.
prommotingg kernel that encourages neighboring nodes with
We summarize the main contributions of this paper as follows:
We propose G-NAMRFF, light-weight, interpretable graph neural additive model with RFFs and minimal parameter overhead. G-NAMRFF a unified approach that seamlessly inte- grates topology and feature learning in one framework providing feature level interpretability through univariate functions and clear hop-level interpretability through the learned FIR coefficients.
We provide theoretical guarantees that establish the robustness and permutation equivariance properties of G-NAMRFF.
The proposed G-NAMRFF is parameter-efficient with 168x fewer parameters compared to GNAN and consistently outperforms it on both node- and graph-classification tasks, and also

---

matches or outperforms state-of of- aff-the-rtt black- box GNNs, demonstrating its suitability for sensitive and performance critical applications.
Notation:
Throughout this paper, we represent matrices and vectors as X (boldface capital letters) and x (boldface lowercase letters), respectively. The (i,j)-th element of matrix is indexed by za.j- Identity matrix of dimension M denoted by las-
Preliminaries
In this section, we set up the mathematical background required for the development of the proposed model.
2.1 Graph Neural Additive Network
Consider graph 9 with N nodes, with the feature vector associated with each node being x E RRD: the feature matrix X E Nx The GNAN models each feature independently using DNN and weights it with learnable function that captures underlying graph topology. Formally, the embedding of k-th component of node is given by,
N
(dist. 1 disl( (T+ fu fe(I),)), 21,h Σ
Here f(-), p(-) are the learnable non-linear functions. dist(i, j) captures the distance between the nodes and (t,ist;(,,)) j) is the number of nodes at dist((i, from node i. From (T) it is clear that embedding of the i-th node requires computing the distance of the i-th node all the nodes of G. which makes ① ineffective to handle large graphs.
2.2 Gaussian Process
A Gaussian Process (CP) [26 is probabilistic framework that defines a distribution over functions, where any finite set of function values follows multivariate Gaussian distribution. is completely specified by a mean function, m(x) and covariance kernel Kx(x,)) x'), where and x' are data points on IgD We denote the GP prior as f(xx) GP (m(x), Kx(x, x")), where Kø x') =
[xx=x'11²) with 6 being the bandwidth.
exp
202
2.3 Kernel Approximation with Random Fourier Features
Random Fourier Features (RFFs) based kernel approximation is a popular technique for addressing the scalability of kernel-based methods such Gaussian Processes (25]. The key idea behind RFFs is to approximate a shift-invariant kernel by expressing it as an inner product of low-dimensional feature mappings and is built Bochner's theorem:
Theorem 2.1 (Bochner's Theorem and RFF Approximation (25 ). Let Kg E R N denote a
bounded, shift-imvariant and positive definite kernel (i.e., Kg Fourier transform of non negative measure). Kg when properly scaled can be approximated using RFF as
M
{V cost (2 + Dm))
5x(xxx))= T (x));
xx(x)
(2)
M
m=1
where 4. a feature map termed as random Fourier features with M being the number of RFF features, ~ (N ID) and bm E Unif(O, 2Tr) are drawn from normal and uniform distributions.
This approximation enables a scalable reformulation of the GP prior into linear Bayesian model. Specifically, prior be modeled f(x) 5 (x)w, where E Mx1 I
3 Graph-aware Neural Additive Model with Random Fourier Features
In this section, we present G-NAMRFF, a lightweight, self-interpreeabble graph neural additive model that integrates graph topology through GP priors and RFF.
3

---

Let G = (V.E) be weighted and undirected graph with N nodes and the associated graph Laplacian as LG E N We assume that each node V is associated with D dimensional feature
E Dx1 and represent the feature matrix as X E NR
Given X and Lg. G-NAMRFF models each feature contribution fi: IR. I through Gaussian process whose covariance kernel enforces smoothness with respect to both the feature values and the underlying graph topology. particular, G-NAMRFF obtains the contribution of each feature to node prediction as
D/ (a(L))
J GP(0, Kg(Fea)
where (g...)) a graph covariance kernel. The embedding of node i.e., In what follows, we first define the graph covariance kernels that enforce smoothness assumption, which are shift invariant and can be approximated using RFFs. Then, leveraging this approximation we propose the light-weigh model.
, Z,
RD is obtained
by stacking ( f2(22,2), ..... fD) (
3.1 Gaussian Process Priors with Graph-aware Kernel
To encode the prior knowledge that adjacent nodes with similar feature values should output similar function values i.e., function should vary smoothly across the nodes, we impose the prior with the graph aware covariance kernel as
(g( = exp (=or, 2z,k x2
20
where θ > 0 is the hyperparameter that controls the width of the function and as.j > O corresponds to i-clemeent of weight matrix A with weights assigned based the distancc/similarity between the nodes. Observe that if the nodes are close in the graph and features are similar the kernel outputs high covariance, whereas for distant nodes with features being dissimilar Kg yields low covariance. Thus, the proposed kernel Kg is both feature and graph-aware. Imposing such a prior enforces f& (Tx,K) to vary smoothly across the connected nodes. Note that for fixed az.j. kernel defined in (4) is shift
invariant with respect nodes j locally, i.e., Kg(0, y) Gg(r -).. with Gg(t) exp( 2er
Shift invariance of the kernel (Stationarity is required for the approximation kernels by Bochner's Theorem (see Theorem 2.1 which in turn aids in formulating the hight-weigh model.
Observe
that Eq.
can
be equivalently expressed as Kg(DIR, F.,k)
exp -ZL (",a)
Let us call projected features as Hi,6 Vaigdi, and
20
J.A
j.. By rewriting, we obtain kernel function with graph-aware inputs
Kg(Ea,,, exp (
(= ( -
(5)
20
In other words, the Kg is modified RBF with inputs filtered features based on one-hop neighbour- hood since the projected variables use weighted graph adjacency.
Remarks:
Although the proposed kernel function Kg is shift invariant and graph-aware, it is apparent that it only captures the information from one hop and may fail to capture the information from larger depths (see the importance in section 6)
More importantly, to study the interpretability, it is also important analyze for a fixed node which neighbors are influencing the predictions.
To address the aforementioned challenges, we reformulate the kernel to incorporate information from deeper neighborhoods. Specifically, we make the kernel inputs topology-aware by replacing the original features with graph-filtered representations. This yields an RBF kernel whose inputs are graph-aware feature embeddings. Notably, this formulation preserves both stationarity globally and positive definiteness, ensuring that the resulting covariance function remains valid under the Gaussian process framework and RFF approximation.

---

Bigs Bay
WIAI
Rbbt Order
Vp.
R41
Figure 2: Architecture of G-NAMRFF.
3.1.1 Topology-Aware Random Fourier Features with Learnable FIR Filters
We aggregate multi-hop information through learnable FIR filters, represented as polynomial func- tions of the graph shift operator-either the adjacency matrix or the graph Laplacian. Specifically, employing the graph Laplacian as the shift operator, the filter is implemented as:
H
on g.
h=0
is the normalized graph Laplacian and is the filter order which hyperparameter that controls how multi-hop information is aggregated. In our framework, we set the filter parameters learnable. We emphasize that instead of fixing the filter parameters, making them learnable enhances the interpretability (see Section 6). In particular, one inspect the filter coefficients and infer information such as the hops that are contributing to the node embedding. Using (q.(6), the filtered response given by X HX E NR with X is now the smoothened graph features encoding much richer neighborhood beyond one-hop. Note that modifying the kernel input by the filtered response transforms Kg to be structure aware RBF that is shift invariant and also non negative. Following Bochners theorem, can be expressed as Kg (24, xz & (ā ( Pa (T),)). where ži.k corresponds to (i. k)-th element of X.
where Lg I-
A- IID-
Leveraging the kernel upproximation technique (Bochner's 's theorem), the GP prior defined in can be cquivalently expressed in linear Bayesian formulation as
(x = T (ii,k)kk:
Wk ~ NO, IM)
where (0.,(),)) -
= (V
2 cos (2 Bi.k + bmn) bm)) as
with a.()) a feature map, which we refer to
m=1 as graph-aware Random Fourier Features (G-RFFs), Om ~ N 1) and bm E (O, 2T) are drawn from normal and uniform distributions. To summarize, G-NAMRFF, learns contribution of features to node-i prediction as
D 1I = Σ (
Wy ~ N,
(8)
RFF Linear Layer
Note that under modified prior, each fa. is a linear transformation whose weights can be obtained by single-layer neural network with exactly M learnable parameters per feature. Also, embedding the structural information into features and representing the univariate function using graph-aware RFFs results light- model with number of trainable parameters dependent on number of RFFs and filter order (more discussion in section 4). We conclude this section with some important observations: (a) for = 1 and og = 0, the present approach resembles the first approach where features are transformed based one-hop neighbourhood.
(b) The filter order and number of RFF features required are less compared to hidden units for all the graph datasets (more details in Appendix C.3).
3.2
Implementation Details
In Fig. we present end end architecture G-NAMRFF for obtaining the prediction i-th node summation of univariate function outputs. Considering X e F. NDD pass each feature
5

---

Algorithm Algorithm for G-NAMRFF
1: Inputs: Feature matrix X RNXD, normalized Laplacian Lg, RFF dimension M, bandwidth
O filter order R.
2: Trainable parameters:
li weight vectors {wx E B 3km= 3: Output: Node predictions }yi)i=1
4: Filtering: Compute filtered features X = =hh an L'z X.
5: RFF computation: Sample frequencies {ar,m Jmm1 No., 1) and phases (br.m)
Uniform(0, 2x) for each k. RFF map: $n(x) V M
[coos( (R + bx.1)s... "aob-..., MO
bg.
6: for each node i 1,..,, do
7: for each feature k = 1, 1,...: ..... D do
8: Obtain feature embedding: (x( $ = (āa,k) WA-
9: Prediction: yr < Eh-r fx(1,,))
10: return [
column through the graph filter parameterized by shared filter coefficients. The magnitude of the filter coefficients reflects the importance of the neighbourhood. In other words, they explain which hop information plays key role in the prediction. We also emphasize that sharing filter parameters reduces the complexity without compromising the accuracy (more details in Section 6). In the following step, for the target node i, we extract D-features and feed them RFF layer where undergoes the cosine transformation with the sampling parameters (am, bm } m== shared across the features. The output the RFF layer the M-dimension RFF vector (P.) each feature. Each of these undergoes linear transformation using single layer NN with size as number of RFF features.
M
The final predictions are obtained depending on the downstream tasks:
For node classification: For node classification task, the predictions obtained following { are passed through activation function (for ex sigmoid or softmax).
For graph classification: We obtain the representation for the complete graph by sum pooling as >E Zg Si-t z, Then the prediction follows by passing representation through activation function. Handling multi-class datasets: If the dataset contains C-classes, we project the weights of a single layer RFF the number of classes thereby enabling class-wise interpretability (more details in Section 6
We present detailed step by step process in Algorithm
Theoretical Characterization and Learnable Parameters Computation
In this section, we discuss some important properties of G-NAMRFF i.e., permutation equivariance and robustness to the perturbations, and then discuss parameter complexity.
= Theorem 4.1 (Permutation Equivariance). Let P = (P e {0, 10,1NNx P = IN} be the set of all N x N permutation matrices. Then under the permutation of the graph Laplacian Lg and mode-featur matrix X by any P P, the outputs from G-NAMRFF also modifies as Yperm Py, where y E RN is the predictions across all the nodes.
The proof for Theorem 4.1 relegated to Appendix A Observe that Theorem 4.1 guarantees any simultaneous permutation of node indices in the Laplacian and feature matrix results in the same permutation of the learned embeddings. This symmetry is essential for ensuring that the model's predictions depend only on the graph's structure, not on arbitrary ordering of its nodes.
Theorem 4.2 (Robusiness to perturbation of graph Laplacian). Let Lg LL + ALg be the Laplacian of the perturbed graph, with |ALall2 S e, and assume that the RFF map (.).) is -Rpp-Lipschitz continuous. Then each node prediction satisfies 17, Wel C. [X]|2 where
It are constants.
C' = CCFFF (max; [wwll2), 1|/0011 (R2-
-
R-1 R+1
The proof Theorem 4.2 is relegated to Appendix A emphasizes the error i.e, difference between the predictions from G NAMREF is bounded linearly with the norm of the error term ALg. Hence, the

---

node predictions are robust to small changes in the graph structure. The proof follows by leveraging the perturbation bounds on FIR filters and then invoking the Lipschitz continuity of RFF features.
4.1 Parameter Complexity
Recall, CNAN employs deep network f& for each of D features plus an additional DNN for p to encode
the graph structure. If each of these D is an L layer feed forward neural network with H,, hidden units, the total number of parameters to be learnt are (D + 1) x (H) x (L- (L+ x H.. + 1).
For G-NAMRFF, the only learnable parameters are filter coefficients and weights of dimension M. Therefore, total number of learnable parameters are D x M + R 1, where R the filter order. For numerical comparison, considering the values given in GNAN [5] with H 64, L 5 and D 100, for the proposed method with M = 100 and R 5, the number of parameters are approximately 168x fewer. This reduction in model size, translates to arguably smaller run times of G-NAMRFF (see discussion on run times in Appendix
Related Works
The existing works that closely related follows:
be broadly classified into categories as
Black-box GNN Architectures: Graph representation learning with GNNs has become ubiquitous across a wide range of applications. Broadly speaking, existing black-box GNNs can be categorized into two types: (a): Message-passing models, which iteratively aggregate and update node features architectures, which perform graph filtering in the Fourier domain to capture global structure [40] 6 20 42 [4]. Additionally,
via learned message functions [2 11] (b): opectral-convoltioon
to better weigh the influence of individual neighbors while aggregating messages, attention based extensions such Graph Attention Networks (GAT)
32 and more recently, graph transformer variants [39 33 have been proposed. 33 39 32]. Finally, several works employ Gaussian processes graphs to capture predictive uncertainty directly 7 [0]. 7 [0]. Despite these advances, all these approaches model a black-box function, and their learned embeddings must be supplemented by separate interpretability techniques.
Interpretable Additive Models: Additive modeling is the workhorse principle of interpretable architectures for tabular data since the inception of Generalized Additive Models (GAMs) [4] to recent methods such as GPAM [41] 2 24 [8. However, these methods were developed primarily for tabular inputs, and naive application of them to graph-structured data fails exploit the relational inductive biases inherent in the graph topology. To address this gap, (5] extends generalized additive modeling graphs by learning node-wise contributions aggregated across neighborhoods. As discussed earlier, this approach suffers with high parameter complexity and employs aggregation schemes that do not fully capture the influence of local graph structure.
Post-hoc GNN Explainers: Explainable models for graph data are mostly post-hoc methods that interpret pretrained GNNs by identifying critical substructures or features after model training. For instance, models like GNN -xpl-xplaieer [37]. PG-PP EG-Explainer [22] uncover the important subgraphs and corresponding node features for explaining the feature predictions, whereas Graph-LIME [17] extends LIME [27] to GNN architectures to quantify each feature contribution to a node-level decision. Recently, GRAPHTRAIL(4] enhances GNN interpretability by translating learned representations into concise, human- readable Boolean formulas. A comprehensive study of post-hoc explainable models detailed in 38).
6 Numerical Experiments and Discussion on Interpretability
In this section, we evaluate G- G-NAMRFF performance and demonstrate its ability to learn interpretable representations node and graph classification tasks.
6.1
Interpretability Node Classification Task
To begin with, we analyze the univariate functions learnt on PubMed (2 dataset with node- classification task. PubMed is multiclass citation-networt dataset where nodes are research articles
7

---

categorized into three diabetes classes: Type 1, Type 2 and gestational [5] To reveal how individual features influence the model's predictions, we plot each learned function against its corresponding raw input values. In particular, as G-NAMRFF produces three outputs per feature (one score for each At any given feature value,
class), we plot three separate curves for each feature as shown Fig. 3 the curve with the highest output indicates the class that the feature most strongly supports.
In Fig a), we show the influence of feature "children" on model output. It can be observed that model learnt a stronger contribution toward Type diabetes, indicating that the presence of this term in an article increases the likelihood of it being classified under this category. This observation aligns with clinical understanding, as Type diabetes is autoimmune in nature with children being susceptible 30), leading increased mention of pediatric-related terms in relevant literature. Similarly, Fig. cc). we show the influence of BMI (Body Mass Index), where it is clear that model associates predominantly with Type 2 diabetes. This clearly aligns with the clinical findings that elevated BMI is a major risk factor for Type 2 diabetes []. In Fig. (b), we show the influence of "sex (gender)," , where model shows relatively lower contributions to both Type and Type diabetes, which is consistent with the fact that sex plays mere role for diagnosis of Type I and Type 2 diabetes. However, in the case of gestational diabetes, which by definition is diagnosed during pregnancy, the model attributes higher importance.
Although these explanations merely match model prediction and interpretation with ground truth, for more challenging and high-stakes scenarios, subject matter expert would better assess the correctness of such plots. Doing so, we can truly utilize the transparency of the model increase the belief in such predictions and also use the feedback to improve the model further.
1.25
Gartational EROMPE
bro: EuRdd
1.2
60
3.0
0.75
0.50
sestatonaa diarro 1ye rdibeos
-02
0.
Goidiana ckdetza
bec 1 (kapii
04
Spa dadasee
Spe da3aM
3.04
0.30
-00
-0.25
-0.0
-1.
60
02
0.4
0.8
(a)
[b]
(c)
(d)
Figure 3: PubMed dataset: Univariate function outputs on different features.
6.2 Empirical Results on Node Classification Task
Having demonstrated G-NAMRFF's ability to learn interpretable representations, we empirically evaluate its performance medium-scale and large scale datasets namely Cora, Citeseer, PubMed [36), [23) ogbn-arxiv and egbn-produue accuracy along with the standard deviation over five independent runs with different random seeds. Hyperparameter details (e.g., number of RFFs (M), scale (e), filter order (R), and optimizer settings) provided in the Appendix C.I
[16]. In Table [ we report mean classification
Across all six datasets, G-NAMRFF matches or exceeds the performance of state-of-the-art black-box GNNs, confirming that interpretability need not come at the cost of accuracy. We also observe that in- corporating information from multiple hops (G-NAMRFF) outperforms the one-hop variant (G-NAMRFF (R = 1)), highlighting the value of deeper neighborhood aggregation. Finally, among interpretable models, G NAMRFF outperforms the state-of state-of-the-ar -he-arr models in addition to scaling effectively. In par- ticular, on ggbn-products, both NAM and GÑAN encounter out-of-memory errors, whereas G-NAMRFF trains successfully. A comprehensive study on hyperparameters is presented in the Appendix C.3
6.3 Interpretability Graph Classification Task
In this section, we discuss the interpretability on the graph classification task with the widely studied Mutagenicity dataset [1 99. The dataset includes 4,337 molecules represented as graphs and each graph is associated with binary labels. In contrast to node classification, here we present both global level and local level interpretations. Recall that we obtain the graph-level embeddings by sum pooling node embeddings. To begin with, we discuss the feature level importance.
8

---

Table 1: Performance comparison on node classification task.
Model
Cora
Citescer
Pubmed
Cornell
ogbn-urxiv
ogbn-products
GCN 20
81.23 + 1.1
71.20 + 1.7
78.50
+ 1.3
65.90 = 0.3
71.74 = 0.3
75.64 + 0.3
GAT [2]
80.32 + 2.3
70.26
+ 2.3
77.12
1 2.4
72.50
+ 0.7
71.95 0.6
79.45 4 0.5
GraphSAGE 12
79.94 + 3.4
65.12
1.9
78.25
+ 1.2
75.90
+ +.0
71.49
0.2
75.63 + 0.3 0.3
Graph Transformer 39
80.70 +: 0.5
76.00
+: 0.9
78.80
+ 1.4
70.50
1.7
70.13
= 0.5
0.5
NAM 12]
51.35 1: 2.3
55.40
1.9
58.16
2.
59.15
2.6
56.12 1 3.4
OOM
GPAM [4
59.96 +: 3.2
60.30
3.9
62.30
3.7
3.7
60.12
62.35 4.2
60.13 +.9
GNAN S
77.89 +: 5.1
65.23
75.13
2.4
71.76
69.56
= 0.9
OOM
G-NAMRFF (R 1)
75.32 + 1.8
67.12
75.12
+ 3.8
64.12 2.9
66.94 1.6
55.73 1.8
G-NAMRFF
79.84 1: 1.7
69.45 1: 2.5
77.30 1 1.4
73.54 1 4.9
70.02 = 3.9
72.13 0.4
34
(c) Figure 4: (a). Feature level explanation on Mutagenicity dataset. (b). Local structure level explanation on Mutagenicity dataset. (c). Learnt FIR filter coefficients.
(a)
(b)
Focusing mutagenic class, we obtain the feature level scores globally by taking the sum of each atom's contribution across the graphs. In Fig. 4 [). we present per-atom importance for the mutagenic class. Notably, Nitrogen, Oxygen, and Lithium atoms exhibit the highest positive contributions towards predicting mutagenicity. This interpretability not only helps us understand why the model makes given prediction, but also directs domain experts to inspect and, if necessary. adjust the features or model. For example, if the model misclassifies a molecule, one can review the atom importance scores assess which atomic features drove the error and representation learning can be modified accordingly.
Although feature-level importance gives insight into individual atom contributions, understanding which substructures are responsible for mutagenicity is crucial for molecular datasets. Using our model, we obtain local explanations by aggregating the feature-level attributions along the neighbor- hood to highlight the subgraph responsible for prediction.
In Fig. 4b). we visualize these extracted substructures for two representative molecules classified as mutagenic. In the first molecule, the nitro (NO2) and amino (N H2) groups emerge as the dominant substructures each exhibiting strong positive attribution toward the mutagenic label. In the second, the aromatic carbon ring itself drives the mutagenicity score. These findings align closely with prior toxicology studies [9 37 which identify N H22, 2O,, and polyaromatic rings as key mutagenic motifs. Importantly, our model reveals that hydrogen and oxygen atoms directly bonded to nitrogen also carry significant contribution towards mutagenic class, whereas isolated hydrogens carbon rings do not play that significant role. This observation supports the global atom-importance ranking in Fig. a)), where nitrogen outranks hydrogen. The study presented again emphasizes the G-NAMRFF ability in llobel-level and local-level attributions. Recall that each FIR filter coefficient oi quantifies how much the model weights information from its h-hop neighborhood. To demonstrate this on the Mutagenicity dataset, in Fig. [fc. we plot the filter coefficients for fixed filter order. It can be observed that there is clear decay in magnitude as h increases, confirming that model naturally prioritizes close neighbors and progressively down-weights more distant nodes. As explained earlier, these learned coefficients thus offer direct, interpretable insight into the receptive field of each atom.
6.4 Empirical Evaluation Graph Classification Task
In this section, we report G-NAMRFF performance on several standard graph-classification benchmarks: Proteins, NCII, Mutagenicity, MUTAG, and PTC [16]. We compare the proposed model against both blx GNNs and interpretable models. In Table 2 we present the mean graph classifica-

---

Table Performance comparison on graph classification task.
Model
Proteins
Mutag
Mutagenicity
NCT1
PTC
GCN 20
7..97+4.66
68.07+6.3
75.69+0.9
6..35+1.3
56.98
GAT
32
69.92+4.00
67.20++3.4
69.40+1.2
66.12++2.1
55.60+11.1
GraphSAGE
12
67.35+223
64.12+2.4
69.25+3.9
65.56+3399
57.12+44.9
Graph Transformer
39
69.7613.2
66.30:15.3
73.1010.9
68.24113.4
55.90
NAM 2
62.45+4.2
63.12:t9.1
67.35+2.5
57.15+1.2
54.97=7..5
GPAM
65.68+4.1
64.30
65.46+2.2
53.80
52.65+8.1
GNAN
5
59.64
67.35+1.99
66.64114.7
50.87
55.07+5.2
G-NAMRFF (R=1)
67.83+14.4
7..20
68.98
63.65++2.8
55.65
G-NAMRFF
69.94
79.81+5.3
71.70++2.0
66.10+1177
61.91+3.4
tion accuracies from 10-fold cross-validation, each repeated over three random seeds. The results highlights the strength of proposed model in obtaining the interpretable graph embeddings without compromising the accuracy. Detailed hyperparameter settings and ablation studies provided in Appendix and C.3
7 Limitations and Future Directions
While G-NAMRFF models the prediction output as a sum of independent feature-wise contributions, this formulation overlooks potential correlations among features. straightforward extension that explicitly models both individual and pairwise feature interactions would substantially increase the parameter count, compromising the model efficiency. Hence designing a parameter- formulation that can capture feature dependencies and higher-order correlations without sacrificing interpretability remains an important direction future research. Further, recall that the smoothness prior imposed on the function limits its effectiveness on heterophilic graphs, where connected nodes often have dissimilar labels. Therefore, extending the current approach to better handle heterophilic data presents interesting and promising direction for future research.
Conclusions
In this work, we introduced G-NAMRFF, a self-interpretable. lightweight additive model for graphs. We proposed unified interpretable architecture that integrates both graph topology and node features into univariate functions via Random Fourier Features. Further, we provided theoretical guarantees showing that G- G-NAMRFF is robust to graph perturbations and permutational equivariant. Our analysis on parameter complexity revealed that G-NAMRFF requires 168x fewer parameters than GNAN. Finally, through experiments on node and graph classification benchmarks, we demonstrated that although being weight and interpretable, G-NAMRFF does not compromise predictive performance.
References
[1] Ali Abbasi, Dorota Juszczyk, Cornelia HM van Jaarsveld, and Martin C Gulliford. Body mass index and incident type and type diabetes in children and young adults: a retrospective cohort study. Journal of the Endocrine Society, 1(5):524-537, 2017.
[2] Rishabh Agarwal, Levi Melnick, Nicholas Frosst, Xuezhou Zhang, Ben Lengerich, Rich Caruana, and Geoffrey E Hinton. Neural additive models: Interpretable machine learning with neural nets. Advances in neural information processing systems, 34:4699-4711, 2021.
[3] Kenza Amara, Rex Ying, Zitao Zhang. Zhihao Han, Yinan Shan, Ulrik Brandes, Sebastian Schemm, and Ce Zhang. Graphframex: Towards systematic evaluation of explainability methods for graph neural networks. arXiv preprint ar arXiv:2206.09677 2022.
[4] Burouj Armgaan, Manthan Dalmia, Sourav Medya, and Sayan Ranu. Graphtrail: Translating gnn predictions into iuman-interpretablee logical rules. Advances Neural Information Processing Systems, 37:123443-1234 2024.
10

---

[5] Maya Rechler-Speicher, Amir Globerson, and Ran effective graph neural additive network. Advances Neural Information Processing Systems, 37:90552-90578, 2024.
The intelligible and
[6] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEF transactions on pattern analysis and machine intelligence, 44(7):3496-3577, 2021.
[7] Viacheslav Borovitskiy, Iskander Azangulov, Alexander Terenin, Peter Mostowsky, Marc Deisenroth, and Nicolas Durrande. Matérn gaussian processes on graphs. In International Conference Artificial Intelligence and Statistics,, pages 2593-2601. PMLR, 2021.
[8] Chun-Hao Chang, Rich Caruana, and Anna Goldenberg. Node-gam: Neural generalized additive model for interpretable deep learning. arXiv preprint arXiv:2106.016// 2021.
[9] Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activin relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-33 1991.
[10] Jinyuan Fang. Qiang Zhang, Zaiqiao Meng, and Shangsong Liang. Structure-awars random fourier kernel for graphs. Advances in Neural Information Processing Systems, 34: 17681111177 2021.
[11] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11 /1.0000..1199.. 2020.
[12] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[13] Vikas Hassija, Vinay Chamola, Atmesh Mahapatra, Abhinandan Singal, Divyansh Goel, Kaizhu Huang, Simone Scardapane, Indro Spinelli, Mufti Mahmud, and Amir Hussain. Interpreting black-box models: a review on explainable artificial intelligence. Cognitive Computation, 16 (1):45-74, 2024.
[14] Trevor Hastie and Robert Tibshirani. Generalized additive models. Statistical science, 1(3): 297-310, 1986.
[15] Trevor Hastie. Generalized additive models. Statistical models in S, pages 249-307, 2017.
[16] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances neural information processing systems, 33:22118-22133 2020.
[17] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 35(7):6968-66) 6971,,66622222 2022.
[18] Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry. 48(1):312-33) 2005.
[19] Henry Kenlay, Dorina Thanou, and Xiaowen Dong. On the stability of polynomial spectral graph filters. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5350-5354. IEFF, 2020.
[20] Thomas N Kipf and Max Welling. Supe-supe classification with graph convolutional networks. arXiv preprint arXiv: 1609000000 2016.
[21] Anna-Maria Lampousi, Sofia Carlsson, and Josefin E Löfvenborg. Dietary factors and risk of islet autoimmunity and type diabetes: systematic review and meta-analysis. EBBiMediiiine
72, 2021.
11

---

[22] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 19960-19963,,, 2020.
[23] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287 2020.
[24] Filip Radenovic, Abhimanyu Dubey, and Dhruv Mahajan. Neural basis models for interpretabil- ity. Advances in Neural Information Processing Systems, 35:8414-844 2022.
[25] Ali Rahimi and Benjamin Recht. Random features for scage kernel machines. In Advances Neural Information Processing Systems, volume 20, 2007.
[26] Carl Edward Rasmussen and Christopher KI Williams. Gaussian processes for machine learning. MIT press, 2006.
[27] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. " why should trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135-1144, 2016.
[28] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 155):206-215, 2019.
[29] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. magazine, 29(3):93 93, 2008.
[30] AG Unnikrishnan, Eesh Bhatia, Vijayalakshmi Bhatia, Sanjay Kumar Bhadada, Rakesh Kumar Sahay, Arun Kannan, V Kumaravel, Dipti Sarma, Bantwal Ganapathy, Nihal Thomas, al. Type diabetes versus type 2 diabetes with onset in persons younger than 20 years of age: results from an indian multicenter study. Annals of the New York Academy of Sciences, 1150(1): 239-244, 2008.
[31] Daniel Vale, Ali EI-Sharif, and Muhammed Ali. Explainable artificial intelligence (xai) post-hoc explainability methods: Risks and limitations in non-diserimination law. Al and Ethics, 2(4): 2022.
[32] Petar Velickovi'c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Represen- tations, 2018
[33] Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces. arXiv preprint arXiv:2402.00789, 2024.
[34] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International conference machine learning, pages 23341-23366 PMLR, 2022.
[35] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:
2018
[36] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMIR, 2016.
[37] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
[38] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: taxonomic survey. IEEE transactions on pattern analysis and machine intelligence, 45(5): 5782-5799, 2022.
[39] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
12

---

[40] Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: comprehensive review. Computational Social Nenworks, 6(1):1-23, 2019.
[41] Wei Zhang, Brian Barr, and John Paisley. Gaussian process neural additive models. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 16865-16872, 2024.
[42] Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International conference on learning representations, 2021.
13

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] is generally preferable to "[No]" it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA]" is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
The abstract and introduction clearly state two key contributions: (1) lightweight model with far fewer parameters than the state of the art interpretable GNN model, and (2) unified self-interpretable structure via graph-aware Random Fourier Features and learnable FIR filters. These two contributions are strongly supported by the emphasis on parameter-complexity analysis.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
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 not attained by the paper.
2. Limitations
14

---

Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper acknowledges that the proposed model obtains predictions by assum- ing Peature-wist independence, thereby overlooking potential correlations among features. This design choice is intentional, as the primary objective is to develop lightweight and interpretable model without compromising predictive performance. Extending the current framework to efficiently capture feature correlations while maintaining interpretability is identified important direction for future work.
Guidelines:
The answer NA means that the paper has no 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should 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 low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss
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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. 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: The outline of proofs and assumptions are discussed in the main paper whereas, complete proof for the Theorems are provided the Appendix.
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.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
15

---

Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The detailed hyperparameter analysis and step by step process followed to generate the results are detailed in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to 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 a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be 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 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 or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We have included the repository link in the abstract.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
cablic/guides httpa///giides/oeeeubiiiise
for more details.
While we encourage the release of code and data, we 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 (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips http:///www....eeeeeee////////sp
for more details.
16

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have followed the standard splits available from the open benchmark graph datasets and wherever they available we have given detailed explanation in the Appendix. Detailed hyperparameter analysis is given in the Appendix.
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 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, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Mean accuracies along with standard deviations reported. We clearly mentioned the factors of variablity.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence 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 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 a library function, bootstrap, etc.)
The assumptions made should be given (e.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 I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is 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 range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
17

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: All the details regarding the compute workers and runtime plots are mentioned in the Appendix.
Guidelines:
The answer NA means that the paper does 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 estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Experimentation is mostly performed on open benchmark datasets which are widely acceptable.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or 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: There is direct societal impact of the work.
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 why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 particular applications, let alone deployments. However, if there is 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 a 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
18

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks. mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper doesnot have such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual- 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or 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?
Question:
Answer: [Yes]
Justification: Properly acknowledged the assets used.
Guidelines:
The answer NA means that the paper does not 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 URL.
The name of the license (e.g., CC-BY 4.0) should be 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.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper doesnot release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
19

---

Researchers should communicate the details of the dataset/code/mmodel as part of their submissions 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 used.
At submission time, remember 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 to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The current work doesnot involve any research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or 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: Current work doesnot involve any research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs are only used for formatting the tables.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : /ttaar:///./..../ Cct.oooeeeeeeccss/22255. for what should or should not be described.
20

---

Appendix
We organize the content in the Appendix as follows: In section present proofs that supports permutation equivariance and robustness properties of G-NAMREF. In section B we include an additional discussion interpretability with node and graph classification tasks. In section C present an ablation studies with respect to the hyperparameters.
A Proofs for the Theoretical Characterization of G-NAMRFF
In this section, we present the proofs for the permutation equivariance and robustness properties of G-NAMRFF.
Theorem. 4.1. (Permutation Equivariance) Let (P 10,1) P In} be the set of all N x N permutation matrices. Then under the permutation of the graph Laplacian Lg and node-feature matrix X by any P E P. the output from G-NAMRFF also modifies as yperm Py, where y E R& the predictions across all the nodes.
Proof. Let P be the permutation matrix acting on the graph G. Under this permutation, the graph Laplacian and feature matrix transforms pem PLg and Xpem PX. Let call the prediction of the node under the permutation as yi.perm. whereas yperm is obtained by stacking
yi.pem-
Under the permutations, filter output modifies as
R Σ h=0
X
pem
Σ
aa
L
pern
perm
P
h=0
R
ag
P
PX.
where 9 (a). follows from the property of permutation matrix i.e., PTP = I. Observe that from
(b) under the permutation, filtered outputs also gets permuted. Leveraging this, we now evaluate the prediction of G- NAMRFF under permutation
Y perm
y1 pemn ... WN.ppem)
Φ T a (0 (01.).pem): ...; (5 N. k.pmm))
Wk.
(10)
(a)
P
④ T (1.)):.......
4 (āNx)) Wk.
k=1
Py.
where (1)) follows from (b) where it can be observed that for fixed feature k i.e., Xk.pemm N Pžt, therefore mappings gets reordered with Ve permm E N P Also it can be observed that R perm = cquivariance of Mt..
E NR = Pzg from the permutational
Theorem. 4.2. (Robustness to perturbation of graph Laplacian) Let La = Lg + ALg be the Laplacian of the perturbed graph, with ||Lgll2 S c, and assume that the RFF map Pa(.) Eurr-Lipschits continuous. Then each node prediction satisfies (T. Yel & C |X||
where
R
C = CRFF (max: [[well)), K ||10 (R²
R-1 1+1
are constants.
21

---

Proof. Before proceeding to the proof, we state the following Lemma that bounds the error between the FIR filters built with Lg and Lg. With slight abuse of notation from here on we represent normalized Laplacian with Lg instead of Lg.
Lemma A.1. 1799 Consider polynomial filter H(LG) =En=o an Ln and perturbed Laplacian as Lg = Lg + ALg with Aلووي S e tthen
R
H[G) ) H( - 71lalli -1) 1)
R-1
(11)
where ||]] [oo........ anl E R R
Lemma A. shows that the error between the outputs of two filters fed with true and perturbed Laplacian is bounded and scales linearly with the error norm. We leverage the above Lemma to bound the difference between the prediction obtained from G-NAMRFF under perturbations.
Assume that the prediction node under the graph perturbation as Úμ- To begin with we evaluate the difference between the filter outputs. Considering the filter outputs with and without perturbation of graph X and Xper We have
X = ( per H(L
(12)
Then the difference between the filtered outputs are bounded as
XX per
||2
|[H(Lg) X H(LL)XX)
[H((L)) - [12
(13)
11
||||| (R² -) ( X 2+
where (a) follows from a norm inequality and (b) follows from (TT). From (3) is clear
that the difference of filter outputs is bounded linearly with the energy in the error term. Leveraging this now evaluate the difference in the prediction output. We index the i, & element of X with R.p. Then,
D Σ
D
Σ S T
00
Vil =
$ a
)
1m1
km
Φ (Zr,
- Φ (Z 1
k=1
CRFF
-
(14)
R
(lrmmax([Iwall 4 (F -1)
Rt-1 R++
< <|
K
CKcD|X
where (a) follows from Lipschitz continuity of 4a. (b),)). follows from (b). Whereas, (4)(c) follows by considering the C CR [//l 2 From (I4),c), is clear that difference in the node predictions scales linearly with the norm of the error term ALg.
B Additional Discussion on Interpretability
B.1 Interpretability on Node Classification Task
In this section, we present additional examples of the learned univariate functions on the PubMed datasct for the node classification task. Specifically, in Fig, 5 we illustrate the univariate function
22

---

outputs for the features i e. keywords as insulin, fat, liver, and diet. Recall that at any given feature value, the curve with the highest output indicates the class that the feature most strongly supports.
In Fig. Sa we examine the influence of the presence of diet keyword in the document on the model's predictions. It can be observed that the model associates higher output with type 2 diabetes, suggesting that diet is a strong predictor for this class. This observation aligns well with existing medical literature, which indicates that type diabetes heavily influenced by dietary factors, whereas type diabetes, being an autoimmune condition is less affected by diet 22. Consistent with this, the model assigns less importance to type diabetes for this feature. Fig. 5b we plot the influence of far keyword in the document where it is clear that it contributes less significantly to the prediction of type diabetes, further supporting the model's 's ability to capture medically relevant patterns. Similarly, in Fig. |C and Fig. [dd we plot the impact of these features on model prediction where it is clear that presence of this word aligns prediction towards type 2 and gestational diabetes. Although for illustration purposes we have presented few examples one can follow a similar procedure to obtain the contribution of different features on different datasets.
0.4
0.8
0.2
0.6
Function output
Function output
0.0
Gestational diabetes
0.4
Gestational diabetes
Type diabetes
Type 1 diabetes
-0.2
Type diabetes
Type 2 diabetes
0.2
-0.4
0.0
-0.6
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.8
1.0
'diet'
'fat'
(a)
(b)
0.75
1.75
0.50
1.50
0.25
1.25
Function output
Function output
1.00
0.00
Gestational diabetes
Gestational diabetes
-0.25
Type diabetes
0.75
Type 1 diabetes
Type di diabetes
Type 2 diabetes
-0.50
0.25
-0.75
0.00
-1.00
-0.25
-1.25
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50 'liver'
0.75
1.00
'insulin'
(c)
(d)
Figure 5: PubMed dataset: Univariate function outputs on features.
B.2 Interpretability on Graph Classification Task
In this section, we include more discussion on interpretability on the mutagenicity dataset. Here the main target is to give local level (structural) explanations and also compare them with the GNN Explaaine [37] which is post-hoc explainer.
23

---

With the focus mutagenic class, we give structure level explanations for the model prediction. In Figs. 6a and 6e we present three example molecules that are predicted mutagenic and highlight predicted substructures responsible for the mutagenic prediction. is clear that the NH2, NO₂ and aromatic rings act key contributors mutagenic class. These explanations align with the existing studies which advocate the presence of these substructures highly influences the mutagenicity [9]. For fair comparison we present the substructures revealed from GNN MoN-Explainer in Fig. 6bb 6d and 6f It can be observed that compared to -alnnexplainer, our proposed model identifies Nilg, NO₂ and aromatic rings more precisely.
(b)
(d)
(c)
(f)
Figure 6: Mutagenicity dataset: Local level explanations.

---

C Hyperparameter Details and Ablation Studies
In this section, we first present the hyperparameter details used our node and graph classification tasks. Then we analyze how each of these hyperparameters affects G-NAMRFF performance across datasets.
C.1 Hyperparameter Details
We have conducted all the experiments using an NVIDIA A30 GPU. In particular, we set the tuning
range as follows: Number of RFFs (M) (20, 40, 50, 100, 200), filter order (R) [1. 7]. kernel width
(9)- [1.0, 4.0J, learning rate (Lr) [le 4, 2e 1] and weight decay (Wd)- [le 5, 1e 2]. The
hyperparameter configurations that yielded the best validation performance are detailed Table 3 For node classification tasks, we follow the standard dataset splits as specified in [16 20 23 case graph classification tasks, where no standard splits are available, we employ 10-fold cross-validation. All models trained for 1000 epochs using the AdamW optimizer with randomly initialized parameters. The specific learning rates and weight decay values used across different experiments are also reported in Table For node classification, accuracy computed over five independent random seeds. For graph classification, we report the mean classification accuracy across 10 folds, with each fold averaged over three random seeds.
In
report the mean classification
GNAN
G-NAMRFF
10a
Run Time (s)
10-1
Cora
Citeseer
Mutagenicity
Proteins
Figure 7: Run time comparison.
C.2 Run time analysis
In this section, we compare the runtime performance of G-NAMRFF, against GNAN, which is the only existing glass-box GNN architecture, In Fig. present the per-epoch runtime comparison on both node and graph classification tasks. Notably, it can be observed that even when GNAN is configured
Number of RFFs (M)
Filter Order
Kernel width (9)
Learning rate
Weight Decay (Wd)
Dataset
(R)
(Lr)
Cora
100)
7
2,2
1.8e-1
2.4e-4
Citeseer
100
5
2.5
5.1c-1
3.1c-4
Pubmed
100
3.8
2.7e-2
4c-4
Cornell
100
6
2.9
7.3e-2
3.7e-4
ogbn-arxiv
100
3.4
5.2e-2
1.3e-4
ogbn-products
40
5
2.3
2.9c-2
5c-4
Proteins
50
1.9
3.2e-3
5e-3
Mutag
200
7
1.2
3,7e-2
Se-3
Mutagenicity
200
6
1.4
1.le-2
Se-4
NCII
50
3.7
1.6e-2
5e-4
PTC
50
5
1.7
2.9e-3
2.5e-5
Table 3: Hyperparameter details.
25

---

0.71
0.76
0.70
Arcuraty
0.74
0.69
0.72
0.68
0.70
Filter Order
Filter Order
(b) Pubmed Figure 8: Classification accuracy against filter order.
(a) Mutagenicity
with a relatively small hidden dimension of 32, it still requires 10 to 100 times more runtime per epoch compared to G- G-NAMRFF.
Furthermore, is worth emphasizing that on small-scale datasets such as Citeseer and Pubmed, increasing the hidden dimension to 64 can already result in out-of-memory (OOM) errors when training GNAN, large-scale datasets like ogbn-products, training GNAN becomes entirely infeasible due to excessive memory requirements.
C.3 Ablation studies
In this section, we analyze the impact of hyperparameters on the model performance. Recall the key typerparameters in G- NAMRFF includes the filter order (R) and number of RFF (M).
Filter Order: In Fig. g we illustrate the effect of the filter order on classification accuracy for two tasks: node classification
the Pubmed dataset and graph classification on the Mutagenicity dataset. Recall that filter of order It aggregates information from ft-hop neighborhoods in the graph. It can be observed that as the filter order increases, the model is able incorporate information from larger receptive fields, leading to an initial improvement in classification accuracy. However, beyond certain point, further increasing the filter order causes the accuracy to saturate or decline, likely due to oversmoothing. Notably, we observe that using higher-order filters (R >>> 1) significantly improves performance compared to = highlighting the benefit of aggregating information from larger graph neighborhoods.
To further highlight the relative importance different node neighborhoods, we present the magni- tudes of the learned filter coefficients for fixed filter order in Fig. 9 using the Mutagenicity and Cornell datasets. It can be observed that the model assigns higher weights closer neighborhoods, emphasizing the greater importance of immediate node interactions in the classification task.
2.5
2.0
Megnitude
Magnitude
0.5
453
0.0
a1
02
d3
C4
05
Filter confficients
(a) Mutag
(b) Cornell
Figure 9: Filter coefficients magnitude against filter order.
26

---

Random Fourier Features:
We analyze the effect of the number of RFFs classification accuracy. Figures. T0a 10b and 10c show the performance variation on the Comell, PubMed, and NCI1 datasets, respectively. As the number of random Fourier features (M) increases, the classification accuracy initially improves due to better kernel approximation. However, beyond a certain point, performance drops as the model may begin overfit with larger M. Across all datasets, we observe that good performance can be achieved with relatively small values of M, which translates to lower number of learnable parameters. Recall that the total number of parameters in G-NAMRFF is M R As observed M being small the model remains lightweight while being effective.
0.75
0.060
0.70
0.770
0.655
0.05
0.050
0.700
0.55
0.645
0.50
0.45
0.750
0.745
0.030
0.625
100
150
200
50
300
150
200
50
100
150
200
Number IUTss
Number
Number RTTS
(a) Cornell
(b) Pubmed
NCII
Figure 10: Classification accuracy vs number of RFFs.
27


Reviews:
[{"review_id": "q4SgcMUFFa", "reviewer": "Reviewer_wbe8", "summary": "This paper studies a graph neural additive model that leverages random Fourier features to yield a relatively less complex and self-interpretable graph additive architecture, referred to as G-NAMRFF.", "questions": "See strengths and weaknesses section.", "limitations": "The authors claim that their work has no limitations. I disagree with this assessment (see weaknesses section above).", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. G-NAMRFF offers interpretability, which makes it suitable for real applications that require transparent decisions. \n2. G-NAMRFF requires a substantially less complex computing architecture relative to existing approaches. \n3. G-NAMRFF is shown to be robust to small perturbations in the graph structure, lending stability to its decisions. \n4. G-NAMRFF achieves competitive performance in node and graph classification tasks. \n\n**Weaknesses**\n1. The effectiveness of the model seems to depend on careful fine-tuning of a large set of hyperparameters.\n2. The interpretability aspect is limited to static data.\n3. The effectiveness of G-NAMRFF beyond graph or node classification tasks is not clear.", "was_revised": true, "final_justification": "Among the concerns raised in my review, the authors provided sufficient response only to the concern about the number of hyperparameters. While authors are confident about the generalizability of their approach to broader settings involving dynamic graphs, they could not provide any convincing evidence/arguments about resolving these aspects in their rebuttal. Additionally, the authors claim their approach to be task-agnostic. However, the concept of a 'task-agnostic' approach is not rigorously defined or explored in this paper or their rebuttal. With these concerns, my recommendation is to reject this paper in its current form.", "rebuttal": "We thank the reviewer for the detailed review and also for the positive feedback on the strengths of the proposed model.  We address specific questions in detail below:\n- # The effectiveness of the model seems to depend on careful fine-tuning of a large set of hyperparameters. \nThe proposed G-NAMRFF model includes a limited and interpretable set of hyperparameters: the filter order ($R$), number of random Fourier features ($M$) and kernel bandwidth ($\\theta$).   Among these $R$  controls the receptive field depth and is typically constrained to small values (e.g., 1–5), as higher values lead to oversmoothing, a well-established limitation in graph representation learning,  $M$ and $\\theta$ are kernel approximation parameters which are common in any Random Fourier Feature (RFF) or Gaussian Process-based methods and are not specific to our model.\n \nWe further highlight that compared to GNAN, our model has significantly less hyperparameters.  GNAN requires separate deep neural networks for each feature and for neighborhood weighting, each with tunable number of layers, hidden units, and additional regularization mechanisms (e.g., dropout), increasing tuning complexity.\n\nWe also emphasize that the performance of G-NAMRFF is relatively robust across different settings of hyperparameters as demonstrated in the supplementary material.  This clarifies that G-NAMRFF is both parameter-efficient and more manageable in terms of tuning compared to prior interpretable baselines.\n\n- # The interpretability aspect is limited to static data\nG-NAMRFF, as correctly pointed out, is a self-interpretable and lightweight model developed primarily for static graphs. Our study explicitly focuses on static graph settings, as detailed in the paper, given the early stage of research in interpretable graph models—where, to the best of our knowledge, only one prior self-interpretable method (GNAN) has been proposed. The goal of this work is to develop a first-of-its-kind interpretable and parameter-efficient architecture that performs on par with black-box GNNs, while offering real-time interpretability.\n\nThat said, the modular design of G-NAMRFF readily allows for extensions to streaming or temporal graph data. In particular, the model’s core strength lies in its use of graph-aware FIR filters, which are functions of the graph Laplacian.  In the dynamic setting—commonly modeled via Discrete-Time Dynamic Graphs (DTDGs)—both the graph Laplacian $\\mathbf{L}$ and node features evolve with time. Existing works [1, 2] in graph signal processing (GSP) has extensively studied time-varying graph filters which can be directly used to generate time-varying filtered features. These filtered signals can then be passed through the same RFF-based univariate modeling framework, preserving interpretability while capturing temporal dynamics.  While our current implementation is for static graphs, the architectural components are well-positioned for principled extension to dynamic graphs which we consider an exciting direction for future work.  We will add this in a future direction section while submitting the final  draft. \n\n [1] Isufi, Elvin, et al. \"Filtering random graph processes over random time-varying graphs.\" IEEE Transactions on Signal Processing 65.16 (2017): 4406-4421.\n\n[2] Bohannon, Addison W., Brian M. Sadler, and Radu V. Balan. \"A filtering framework for time-varying graph signals.\" Vertex-Frequency Analysis of Graph Signals. Cham: Springer International Publishing, 2018. 341-376. \n\n- # The effectiveness of G-NAMRFF beyond graph or node classification tasks is not clear.\n\nWe thank the reviewer for the comment.  Following prior works in interpretable and explainable graph learning we focused on node and graph classification tasks to enable a fair and direct comparison. However, the core strength of G-NAMRFF lies in its design: graph signal filtering followed by additive modeling via RFFs. This structure is task-agnostic and readily extends to other downstream tasks, such as link prediction and graph regression. \nTo validate this, we conducted additional experiments with downstream task as  link prediction. Given a node pair (say $u,v$), we compute their embeddings using G-NAMRFF and predict the likelihood of an edge via a dot product decoder followed by a sigmoid activation.  Importantly, since node embeddings are formed through additive combinations of filtered, RFF-transformed features, the model retains feature-level interpretability in the link prediction setting. Specifically, we can decompose the link score into contributions from individual features and hop depths for each node, allowing us to quantify which features most strongly influence the prediction. We quantitatively  present the results on benchmark datasets with AUC as a metric.  From the results we emphasize that the G-NAMRFF is task agnostic and offers interpretability  without compromising the accuracy. \n\n| Models         | Cora             | Citeseer        | Pubmed          |\n|----------------|------------------|-----------------|-----------------|\n| GCN            | 92.03 ± 0.27     | 94.78 ± 0.35    | 98.69 ± 0.06    |\n| GAT            | 93.08 ± 0.32     | 96.25 ± 0.20    | 98.20 ± 0.07    |\n| GraphSAGE           | 92.35 ± 0.15     | 93.12 ± 0.30    | 98.87 ± 0.04    |\n| GPAM           | 83.46 ± 0.37     | 88.65 ± 1.50    | 78.38 ± 0.08    |\n| GNAN           | 84.95 ± 0.55     | 81.12 ± 0.90    | 88.77 ± 0.40    |\n| G-NAMRFF(ours) | 93.83 ± 0.35     | 93.96 ± 1.20    | 97.25 ± 0.21    |\n\n\n- #  Comment on limitations \nWe thank the reviewer for the suggestion.  Following your suggestion,  we will include a section in the revised draft mentioning limitations and future directions as follows: \n\n\\section{Limitations and Future Directions}\n\nG-NAMRFF, as discussed, is primarily developed under the assumption of a static graph structure and static node features. While this is consistent with most existing interpretable graph learning frameworks, it limits applicability to dynamic real-world data from social or communication networks, where both the graph topology and node attributes evolve over time.\n\nExtending G-NAMRFF to dynamic graphs is a promising direction for future work. In particular, both continuous-time dynamic graphs (CTDGs) and discrete-time dynamic graphs (DTDGs) are widely used to model temporal graph data. The modular nature of G-NAMRFF—particularly its use of FIR graph filters and additive modeling—suggests that it can be adapted to these settings by incorporating time-varying graph filters and temporally evolving RFF features. Developing such lightweight, interpretable models for dynamic graphs remains an exciting and important research challenge."}, {"review_id": "FuIJ1NmHqU", "reviewer": "Reviewer_i8kU", "summary": "This paper introduces the Graph Neural Additive Model with Random Fourier Features (G-NAMRFF), a novel, lightweight, and self-interpretable model for graph-structured data. The interpretability is achieved by additive modelling, i.e., the output of a node is a sum of each individual channels of transformed features without channel mixing. A core design to avoid the quadratic complexity of global feature aggregation, is to leverage random Fourier features to approximate a graph kernel that captures node-pairwise interaction.", "questions": "Please see **Weaknesses**.", "limitations": "The authors did not discuss any potential limitations. Please see **Weeknesses** for possible improvements.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- The paper tackles the critical problem of computational complexity and parameter efficiency in interpretable GNNs.\n- A theoretical quantification of robustness is provided, which is crucial for model generalization.\n- Extensive experiments demonstrate interpretability with descent predictive performance.\n- The paper is well-written and easy to follow\n\n\n**Weaknesses**\n- There could be concerns about model capacity, since the overall model is pretty much linear. The expressivity problem could be worse since there is no feature mixing for interpretability.  \n- In the main experiments, it is not clear how the number of parameters of the proposed method is compared to other baselines. This is of particular interest as being lightweight is one of the main motivations.\n- Minor: equation (1), I believe it should be $f_{k}(x_{j,k})$.", "was_revised": true, "final_justification": "My concern regarding parameter comparison has been addressed by the authors’ rebuttal. While expressive power could be a limitation, I view it more as an avenue for future work, particularly in studying the trade-offs between interpretability, robustness, and expressivity in this framework. \n\nRegarding Reviewer wbe8's comment on the limitation to static graphs, I do not consider this to be a major limitation of the current contribution.\n\nRegarding Reviwer 9JUV's comment on Theorem 2.1, I feel like it is a standard statement in random features. \n\nTaking all these aspects into account, I maintain my recommendation for acceptance.", "rebuttal": "We thank the reviewer for the very positive feedback on the strengths of the work and the presentation of the paper. We address the specific questions in detail below. \n- #  Comment on expressivity\nWe thank the reviewer for the insightful comment. As pointed out correctly,  G-NAMRFF models the output as a sum of univariate functions, each acting on a single feature independently. This design avoids feature mixing basically for two reasons: (1) To reduce the parameter complexity and design a very light-weight model (2)  To position the model in line with recent interpretable models such as NAMs and GNAN. We acknowledge that this imposes a limitation on expressivity, as it does not explicitly capture inter-feature correlations.  Despite this constraint, G-NAMRFF being light-weight matches or outperforms several black-box GNNs across benchmarks, demonstrating that the core design is effective for many practical tasks. \n\nTo further enhance expressivity while preserving interpretability, we highlight that G-NAMRFF can be readily extended using ideas from NODE-GAM [1] and GAMI-Net [2], which incorporate structured pairwise interactions. Specifically, G-NAMRFF can model both independent  and pairwise feature effects as:\n\n$ y_{i}  = \\sum_{k=1}^{D} f_{k}(x_{i,k})  + \\sum_{k=1}^{D}  \\sum_{k'>k}^{D} f_{k,k'}(x_{i,k},x_{i,k'})$, where $f_{k,k'}$ is modeled as a Gaussian Process with a 2D input. These functions can be efficiently approximated using 2D random Fourier features (RFFs) as \n\n$f_{k,k'}(x_{i,k},x_{i,k'}) = \\mathbf{\\Phi}_ {a}^{T}([\\tilde{x}_{i,k},\\tilde{x} _{i,k'}])\\mathbf{w} _{k,k'}.$ \n\nThe overall prediction of node $i$ then becomes\n\n$y_{i}  = \\sum_{k=1}^{D} \\mathbf{\\Phi}_ {a}^{T}(\\tilde{x}_{i,k}) \\mathbf{w} _{k}  + \\sum _{k=1}^{D}  \\sum _{k'>k}^{D} \\mathbf{\\Phi} _{a}^{T}([\\tilde{x}  _{i,k},\\tilde{x}   _{i,k'}])\\mathbf{w}  _{k,k'}$\n\nAs discussed earlier, this further increases the complexity due to increase in the number of learnable parameters . \n\nIn the final draft, we plan to add this as a remark. \n\n[1] Chang, Chun-Hao, Rich Caruana, and Anna Goldenberg. \"NODE-GAM: Neural Generalized Additive Model for Interpretable Deep Learning.\" International Conference on Learning Representations 2022.\n\n[2] Yang, Zebin, Aijun Zhang, and Agus Sudjianto. \"GAMI-Net: An explainable neural network based on generalized additive models with structured interactions.\" Pattern Recognition 120 (2021): 108192.\n\n- # Comparison of number of parameters with other baselines\nWe thank the reviewer for the comment. Although in the main paper we compared the parameter efficiency against GNAN, here we present the comparison against the other black box and glass box models. In particular,  we present the ratio of number of parameters of black/glass  box models to G-NAMRFF.   Considering $H_u$ as  size of the hidden layer, $D$ as input feature dimension, $M$ as number of RFFs, $R$ as  filter order, $L$ as number of GCN layers or MLP layers and $K$ as number of heads in GAT,  we present the parameter efficiency in the below table where it is clear that proposed model is parameter efficient.  \n\n| Model    | Parameter ratio   | Learnable parameter equation                               |\n|----------|------------------------------------------------------------|------------------------------------------------------------|\n| GNAM-RFF | 1.0                                                       | $D \\times M + R+1$                                         |\n| GCN      | 5.12                                                      | $( H_u \\times D + H) +(L - 1)(H_u^2 + H_u) + (H_u + 1)$                                                         |\n| GAT      | 10.24                                                     | $K(H_u \\times D+3H_u) + (L-1)K(H_u^2 + 3H_u) + K \\times H_u + 1$                                                      |\n| NAM      | 150                                                       | $ (D)\\times( H_u^{2}\\times (L-1) + (L+2)\\times H_u + 1)$   |\n| GNAN     | 168                                                       | $ (D+1)\\times( H_u^{2}\\times (L-1) + (L+2)\\times H_u + 1)$ |\n\n\n- # Comment on equation 1\n\nWe thank the reviewer for pointing out the typo. We will correct this while submitting the final draft. \n\n- # Comment on limitations \n\nWe thank the reviewer for the suggestion. Following your suggestion, we will include a section in the revised draft mentioning limitations and future directions as follows:\n\n\\section{Limitations and Future Directions}\nG-NAMRFF, as discussed, is primarily developed under the assumption of a static graph structure and static node features. While this is consistent with most existing interpretable graph learning frameworks, it limits applicability to dynamic real-world data from social or communication networks, where both the graph topology and node attributes evolve over time.\n\nExtending G-NAMRFF to dynamic graphs is a promising direction for future work. In particular, both continuous-time dynamic graphs (CTDGs) and discrete-time dynamic graphs (DTDGs) offer formal models for temporal graph data. The modular nature of G-NAMRFF—particularly its use of FIR graph filters and additive modeling—suggests that it can be adapted to these settings by incorporating time-varying graph filters and temporally evolving RFF features. Developing such lightweight, interpretable models for dynamic graphs remains an exciting and important research challenge."}, {"review_id": "Wk6rUW6NEG", "reviewer": "Reviewer_zafR", "summary": "This paper introduces G-NAMRFF, a lightweight, interpretable model for graph learning. It improves upon GNAN (the only existing glass-box GNN architecture) by using Random Fourier Features (RFFs) to approximate Gaussian process kernels, reducing parameter complexity while maintaining interpretability. G-NAMRFF represents node embeddings as feature-wise contributions, with a graph-aware kernel based on Radial Basis Function (RBF) and Laplacian. It outperforms SOTA black-box GNNs and GNAN on node and graph classification tasks, providing real-time interpretability without sacrificing accuracy.", "questions": "1. Please analyze the time complexity of the method proposed in this paper, specifically the time complexity of Algorithm 1. How does it compare to that of GCN?\n2. In line 61, the authors mention that GNAN requires O(N+E) distance computations per node. Why is this considered 'quadratic scaling'?", "limitations": "No. Please see the Weaknesses and Questions Section.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. The proposed G-NAMRFF is a novel method that effectively reduces the parameters of existing graph neural additive networks while maintaining strong interpretability and performance.\n\n2. Extending the Random Fourier Features-based kernel approximation to the Graph Neural Additive Model is an intriguing approach and offers valuable potential for future research.\n\n3. This paper provides sufficient theoretical and empirical analysis, particularly through real-world node and graph classification experiments, runtime analysis, and ablation studies, all of which demonstrate the effectiveness of the proposed methods.\n\n4. The paper is well-written, with a clear logical structure that makes it easy to read.\n\n### Weaknesses\nAlthough I believe this paper presents a novel contribution, it still has some issues.\n1. The paper contains several minor errors; I have provided a few examples and kindly ask the authors to review them:  \n    a) The description of Figure 1 does not specify what the x-axis represents.  \n    b) Theorem 2.1 lacks the necessary references.  \n    c) Some figures and tables are missing punctuation after the captions, such as Figures 1 and 2, and Table 2.  \n    d) The notation is inconsistent, for example, the Laplacian matrix in Theorem 4.2 is not written in boldface capital letters.  \n2. The paper focuses solely on parameter complexity and does not address time complexity.\n3. No code is provided for reproducibility.", "was_revised": true, "final_justification": "After reviewing the author’s rebuttal and the feedback from other reviewers, I have decided to support this paper and believe it deserves acceptance. \n\nThe use of Random Fourier Features to improve the complexity of Graph Neural Additive Networks and enhance interpretability is both novel and technically elegant, with strong theoretical foundations and empirical validation. The intuitive illustrations in Figures 3 and 4, in particular, are interesting. \n\nRegarding reviewer wbe8's question, I believe it is somewhat outside the scope of this paper. Dynamic graphs should be addressed in future research, and the authors have already incorporated link prediction, demonstrating the effectiveness of the proposed method across three fundamental graph learning tasks: node classification, graph classification, and link prediction. \n\nRegarding Theorem 2.1 in the Preliminaries section, the authors' writing is unclear, and references are non-standard. While this issue should be addressed in a revision, it does not constitute grounds for rejection.", "rebuttal": "We thank the reviewer for the positive feedback on the model strengths and the presentation of the paper.  We address the specific questions in detail below.\n- # Comment on typos \nWe thank the reviewer for the thorough reading of the manuscript and pointing out the typos.  We will include all the suggestions in the revised manuscript. More specifically, we will add the details such as label for X-axis,  references for the Theorem 2 and carefully check for the other typos as well.  \n- # Comment on time complexity\nThe complexity of G-NAMRFF is dominated by two key steps as outlined in Algorithm 1 in supplementary material, namely (1) Filtering (2) RFF approximation.  For a graph with $N$ nodes and $D$ dimensional features, we have Laplacian as $\\mathbf{L} \\in \\mathbb{R}^{N \\times N}$, graph data as $\\mathbf{X} \\in \\mathbb{R}^{N \\times D}$. Then the graph filtering operation costs  $\\mathcal{O}(N^{2}D)$. Whereas the RFF approximation costs  $\\mathcal{O}(NMD)$.  Hence the total time complexity for dense graph i.e., worst case complexity of the proposed algorithm is $\\mathcal{O}(N^{2}D + NMD)$. Exploiting the sparsity in the Laplacian, let say if $\\mathbf{L}$ has atmost $d$ (aka degree) non-zero entries the graph filtering operation costs $\\mathcal{O}(dND)$. Total time complexity is  $\\mathcal{O}(dND+NMD)$. \n\nFor dense graphs,  the time complexity of GCN with  $K$ layers is $\\mathcal{O}(KN^2F + K N F^2)$. Exploiting the sparsity the time complexity for GCN is given by $\\mathcal{O}(KEF+ KNF^2)$, where  $E$ is the total number of edges in the graph. So the time complexity is comparable to the black-box model.\n\n- # The authors mention that GNAN requires O(N+E) distance computations per node. Why is this considered 'quadratic scaling'?\n As explained in the introduction, GNAN requires computing the distance of a node $i$ to all $N$ nodes in the graph, leading to a per-node complexity of $\\mathcal{O}(N + E)$. Aggregating over all $N$ nodes results in an overall complexity of $\\mathcal{O}(N(N + E))$. In the case of a complete graph, where $E = \\mathcal{O}(N^2)$, the total complexity becomes $\\mathcal{O}(N^3)$, making GNAN computationally expensive. This quadratic (or cubic) scaling limits its scalability even if sparsity can be exploited in more realistic sparse graphs. \n\nWe will make the code public including all the suggestions in the final draft."}, {"review_id": "GjjXS6M8F8", "reviewer": "Reviewer_9JUV", "summary": "This paper proposes a new model for graph data named Graph-aware neural additive model with random features (G-NAMRFF). It assumes that the outputs are additive functions. The component-functions are drawn from a Gaussian prior (GP) with covariance generated from a graph-reweighed square exponential kernel. Two theoretical results are derived in Section 4. The method is compared to standard procedures in Section 6 for node and graph classification datasets.", "questions": "- Could you make this deep, by staking G-NAMRFF layers on top of each other?\n- I did not understand Theorem 2.1 (for instance what do you mean with approximated?) and the statement could be wrongly formulated. Could you provide a reference or a proof? \n- Can you address the issue of the expressivity?", "limitations": "I did not find anything in the text discussing the potential limitations of this work.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- I did enjoy reading the article. Everything is well-explained and clean. \n- The approach seem to be motivated by proposing small models. It is highlighted that the approach requires 168  times less parameters than GNAN without destroying the performance. \n\n\nWeaknesses:  \n- My overall impression is that everything is quite straightforward: The method is just regression with a specific GP, Theorem 4.1 seems (at least intuitively) to be clear. While there is nothing wrong with the paper, I did miss some deeper insights. \n- The expressivity of an additive model is very limited and in learning tasks often just inappropriate, e.g. if the inputs are highly correlated. The authors should have invested much more in motivating how the inclusion of the covariance could overcome that such that one can learn large function classes with G-NAMRFF. Without some more theoretical insights on that, I find the approach hard to believe.", "was_revised": true, "final_justification": "The answers of the authors mainly confirmed my initial assessment. While this is a timely topic, I do not find the article sufficiently innovative and also think that it is sometimes a bit sloppy. An example is the discussion about Theorem 2.1. To my opinion, the way this theorem is stated is impossible to process by a reader.", "rebuttal": "We thank the reviewer for the positive feedback and also happy to hear that you enjoyed reading the article.  We address the specific questions in detail below:\n\n- #  The method is just regression with a specific GP, Theorem 4.1 seems (at least intuitively) to be clear. While there is nothing wrong with the paper, I did miss some deeper insights. \n\nWe thank the reviewer for this comment. To emphasize the strengths of our approach and contrast it with traditional GP regression on graphs, we briefly review prior graph‑GP methods. Most of these methods place a full prior\n\n$\nf \\sim \\mathcal{GP}\\bigl(0,K\\bigr),\\quad \\text{where} \\quad K\\in\\mathbb{R}^{N\\times N},\n$\n\nwhere $K$ may be a graph aware Matérn kernel \\[1] or a wavelet‐inspired kernel \\[2] to name a few. Inference is done by obtaining the posterior distribution and it involves inverting $K + I$ matrix, incurring $\\mathcal{O}(N^3)$ time and $\\mathcal{O}(N^2)$ memory. While they can quantify uncertainty—unlike GCN or GAT, which yield only point estimates. GP based models still exhibit some key limitations: 1. Lack of feature‑wise interpretability, since every prediction mixes all features and nodes through the dense inverse; 2. Scalability due to matrix inversion operation; 3. Cannot be linearized, because the most of these graph aware kernels do not satisfy the conditions stated by Bochners theorem. Importantly, these black box approaches to be interpretable/explainable requires a post-hoc explainers that adds complexity and lacks transparency.  In contrast, our current framework is self interpretable by design.\n\nOur framework is inspired by additive models and achieves feature‑level interpretability. We treat each feature independently (also check below for discussion on the correlated features), place a GP prior on its  graph‑filtered values, and choose a kernel that satisfies Bochner’s conditions for shift invariance. More specifically, our kernel is RBF that operates on the filtered feature vector $\\tilde x_i$, it remains shift‑invariant —unlike conventional graph kernels. This design admits a RFF linearization, yielding a lightweight, linear‑in‑parameters model with $\\mathcal{O}(NMD)$ forward‑pass complexity instead of costly matrix inversion.  \n\nImportantly this is the first work that introduces learnable FIR filters into the GP framework where each coefficient $\\alpha_h$ directly quantifies the contribution of the $h$-hop neighborhood, providing  structural interpretability alongside feature‑wise insights. To the best of our knowledge, this is the first work to provide a theoretical justification for embeddings that are not only permutation equivariant but also stable under graph perturbations, owing to the use of finite impulse response (FIR) filters.\n\nFinally, Theorem 4.1 states permutation equivariance property that captures the graph symmetry.  We emphasize that   this property is non-trivial due to non-linearity involved (contrary to any GP based regression algorithms).  The novelty again lies in integration of FIR filters and RFF based approximations, which induces the structure dependencies while maintaining the permutation equivariance.\n\nIn summary, G‑NAMRFF transforms a black‑box, cubic‑cost GP regression into a glass‑box, linear‑cost, interpretable model, going well beyond standard GP approaches.\n\n[1] Borovitskiy et al., “Matérn Gaussian processes on graphs,” AISTATS ’21.\n\n[2] Fang et al., “Wavelet kernels for graph Gaussian processes,” ICML ’21.\n\n- # Comment on expressivity \n\nWe thank the reviewer for the insightful comment. As pointed out correctly,  G-NAMRFF models the output as a sum of univariate functions, each acting on a single feature independently. This design avoids feature mixing basically for two reasons: (1) To reduce the parameter complexity and design a very light-weight model (2)  To position the model in line with recent interpretable models such as NAMs and GNAN. We acknowledge that this imposes a limitation on expressivity, as it does not explicitly capture inter-feature correlations.  Despite this constraint, G-NAMRFF being light-weight matches or outperforms several black-box GNNs across benchmarks, demonstrating that the core design is effective for many practical tasks. \n\nTo further enhance expressivity while preserving interpretability, we highlight that G-NAMRFF can be readily extended using ideas from NODE-GAM [1] and GAMI-Net [2], which incorporate structured pairwise interactions. Specifically, G-NAMRFF can model both independent  and pairwise feature effects as:\n\n$ y_{i}  = \\sum_{k=1}^{D} f_{k}(x_{i,k})  + \\sum_{k=1}^{D}  \\sum_{k'>k}^{D} f_{k,k'}(x_{i,k},x_{i,k'})$  \nwhere $f_{k,k'}$ is modeled as GP is modeled as a Gaussian Process with a 2D input. These functions can be efficiently approximated using 2D random Fourier features (RFFs) as \n\n$f_{k,k'}(x_{i,k},x_{i,k'}) = \\mathbf{\\Phi}_ {a}^{T}([\\tilde{x}_{i,k},\\tilde{x} _{i,k'}])\\mathbf{w} _{k,k'}.$ \n\nThe overall prediction of node $i$ then becomes\n\n$y_{i}  = \\sum_{k=1}^{D} \\mathbf{\\Phi}_ {a}^{T}(\\tilde{x}_{i,k}) \\mathbf{w} _{k}  + \\sum _{k=1}^{D}  \\sum _{k'>k}^{D} \\mathbf{\\Phi} _{a}^{T}([\\tilde{x}  _{i,k},\\tilde{x}   _{i,k'}])\\mathbf{w}  _{k,k'}$\n\nAs discussed earlier, this further increases the complexity due to increase in the number of learnable parameters.\nWe again emphasize that the main motivation involved in design of G-NAMRFF is the low-complexity without compromising the performance compared to the black-box models.  \n\nIn the final draft, we will add a remark stating how G-NAMRFF can be extended to handle correlated features.\n \n[1] Chang, Chun-Hao, Rich Caruana, and Anna Goldenberg. \"NODE-GAM: Neural Generalized Additive Model for Interpretable Deep Learning.\" International Conference on Learning Representations 2022.\n\n[2] Yang, Zebin, Aijun Zhang, and Agus Sudjianto. \"GAMI-Net: An explainable neural network based on generalized additive models with structured interactions.\" Pattern Recognition 120 (2021): 108192.\n\n- #  Could you make this deep, by staking G-NAMRFF layers on top of each other?\n\nYes — in principle, G-NAMRFF layers can be stacked to increase model capacity. However, doing so introduces significant interpretability overhead. Each additional layer brings its own set of FIR filter coefficients $\\{\\alpha_h^{(\\ell)}\\}$ and RFF weight vectors $\\{w_k^{(\\ell)}\\}$, making it harder to attribute predictions to specific input features or graph structure components.\n\nUnlike message-passing GNNs such as GCNs, which expand their receptive field across layers via\n\n$\nX^{(\\ell+1)} = \\sigma\\bigl(AX^{(\\ell)}W^{(\\ell)}\\bigr),\n$\n\nour model uses explicit FIR graph filtering, which already aggregates $R$-hop neighborhood information in a single layer.\n Therefore, deeper stacking is not necessary purely for increasing receptive field — a single G-NAMRFF layer with properly tuned filter order $R$ and RFF dimension $M$ is often sufficient.\n\nEmpirically, we evaluate stacking multiple G-NAMRFF layers on node classification task on Cora dataset and observe only marginal gains or even performance degradation. We attribute this to two competing effects: (1) oversmoothing, where repeated graph filtering causes node features to become indistinguishable, and (2) overfitting from stacking multiple layers of high-dimensional RFF projections.\n\nIn summary, while stacking G-NAMRFF is technically feasible and may increase function class capacity, it compromises interpretability and offers limited performance benefits. Our results suggest that a carefully designed single-layer G-NAMRFF already achieves competitive performance with far greater transparency.\n\n\n| RFF(M) | Filter Order (R) | Layers | Accuracy (%) |\n|-----|--------------|--------|--------------|\n| 100 | 3            | 2      | 78.40 ± 0.25 |\n| 200 | 3            | 2      | 80.12 ± 0.36 |\n| 100 | 5            | 2      | 75.50 ± 0.11 |\n| 200 | 5            | 2      | 75.92 ± 1.98 |\n| 100 | 3            | 3      | 76.56 ± 0.23 |\n| 200 | 3            | 3      | 75.77 ± 0.45 |\n| 100 | 5            | 3      | 72.35 ± 1.26 |\n| 200 | 5            | 3      | 71.19 ± 2.49 |\n\n- # I did not understand Theorem 2.1 (for instance what do you mean with approximated?) and the statement could be wrongly formulated. Could you provide a reference or a proof? \n\nWe thank the reviewer for the comment.  The statement of Theorem 2.1 is a standard result: By Bochner’s theorem, a shift‑invariant kernel can be expressed as $K(x,x') = \\mathbb{E}_{a,b}(\\mathbf{\\Phi} _{a}^{T} (x) \\mathbf{\\Phi}  _{a}(x))$. The finite dimensional inner product is therefore an unbiased Monte carlo estimate of true kernel approximating it to the sampling error. Complete proof along with the convergence and the concentration bounds can be found in Theorem 1 in [1].\n\nWe will add this reference in the revised manuscript. \n\n[1] Rahimi, Ali, and Benjamin Recht. \"Random features for large-scale kernel machines.\" Advances in neural information processing systems 20 (2007).\n\n- #  Comment on limitations \nWe thank the reviewer for the suggestion.  Following your suggestion,  we will include a section in the revised draft mentioning limitations and future directions as follows: \n\n\\section{Limitations and Future Directions}\n\nG-NAMRFF, as discussed, is primarily developed under the assumption of a static graph structure and static node features. While this is consistent with most existing interpretable graph learning frameworks, it limits applicability to dynamic real-world data from social or communication networks, where both the graph topology and node attributes evolve over time.\n\nExtending G-NAMRFF to dynamic graphs is a promising direction for future work. In particular, both continuous-time dynamic graphs (CTDGs) and discrete-time dynamic graphs (DTDGs) are widely used to model temporal graph data. Developing such lightweight, interpretable models for dynamic graphs remains an exciting and important research challenge."}]

Author rebuttal:

Meta-review: The paper proposes Graph Neural Additive Model with Random Fourier Features (G-NAMRFF),  an extension of Graph NAM, that is claimed to be interpretable, computational efficient and lightweight, seamlessly integrating graph topology and feature mapping into a single module. Interpretability is inherited by GNAM, while a better integration of graph structure and node features (wrt GNAM), is obtained via the adoption of a kernel, that implements a Gaussian Process prior, capturing integrated information for one-hop neighbourhood in the graph,  The kernel is approximated via Random Fourier Features, and multi-hop graph information is obtained by  embedding the node features using Finite Impulse Response filters with trainable coefficients. The adoption of univariate functions supports interpretability. The experimental assessment of the proposed approach provided evidence of the ability of G-NAMRFF to learn light-weight and interpretable models able to reach comparable performances wrt to comparable approaches.

The main strengths of the paper can be summarised as follows:
- addresses an important problem involving computational complexity and parameter efficiency in interpretable GNNs;
- the paper claims, i.e. compact interpretable models with very good predictive performances, seems to be supported by an extensive experimental assessment;
- theoretical results on permutation equivariance, as well as robustness to perturbation of graph Laplacian are provided;
- overall (with the exception of Theorem 2.1) the paper is well-written and easy to follow.

The paper also has some weaknesses, the main ones of which are listed below:
- it is not clear how expressive is the family of functions that can be implemented by the proposed approach. This could limit the scope of applicability.
- the contribution could be considered incremental, given that it consists of the application of existing techniques.

After discussion with SAC, it was decided that the positive contributions outweigh the weaknesses, which can be addressed in future work.
Decision: Accept (poster)