- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper introduces a new interpretable graph additive model that combines mixture of neural bases for feature-wise nonlinear modeling with sparse RRWP aggregation for structural propagation. MoNB routes each feature to a small subset of shared basis experts using feature identity rather than the current input, preserving globally inspectable univariate functions. SRA applies feature specific, nonnegative mixtures of random walk powers without constructing dense node pair tensors. This method is evaluated on various node and graph level tasks
Critical strengths
- The model provides exact feature, source node, and walk length contributions to its logits without requiring an auxiliary explainer.
- Shared neural bases limit per-feature parameter overhead, while exact sparse propagation avoids quadratic node-pair materialization.
Critical weaknesses
- Insufficiently established methodological novelty
a. Restricting RRWP to a linear topology function yields a feature-wise polynomial graph filter evaluated through sparse recursion. The authors should distinguish the novelty of its additive parameterization from this computational reformulation. A comparison against an additive neural-basis model with learned sparse polynomial propagation is needed to substantiate the contribution.
b. The integration is largely modular: MoNB supplies feature responses, while SRA propagates them without explicitly exploiting the individual expert decomposition. Moreover, the MoNB theory sets aside graph propagation, leaving unclear when its specialization advantage translates into better graph predictions. Parameter-matched comparisons against a global NBM with identical sparse aggregation are needed to establish the benefit of this particular pairing beyond the independent advantages of its components.
-
The combination of random-walk propagation and sum pooling introduces an exact expressivity limitation. On undirected regular graphs, the random-walk matrix is doubly stochastic, so . Together with , the graph readout in Appendix G.6 reduces to , eliminating dependence on connectivity for fixed input features. Consequently, the model cannot distinguish regular graphs with identical node-feature multisets, even with nonconstant attributes, and neither additional experts nor propagation depths resolves this limitation. Although this does not invalidate the node-classification model, the authors should characterize this boundary and evaluate its practical significance through topology-sensitive graph-classification tests.
-
The combined equations imply that the model uses same feature response function across all propagation hops. Only the hop weights change as . Consequently, the model cannot learn a linear effect from a node's own feature and a quadratic effect from its neighbours for the same feature. Adding more neural-basis experts does not resolve this limitation, since their outputs are combined before graph propagation. The authors should discuss this restriction and compare against hop-specific response functions or expert-specific propagation.
Questions for authors
Please refer Weaknesses
7 comments
Rebuttal by Authors
W1b. On the modular integration of MoNB and SRA
The modular integration of MoNB and SRA is an intentional design choice to preserve transparent and interpretable feature modeling and structural propagation. Rather than tightly coupling these mechanisms, HARMONIA separates two complementary questions: how each feature contributes to a prediction and how that contribution propagates through the graph. MoNB learns specialized nonlinear feature responses, while SRA models their propagation across source nodes and multiple hops.
Importantly, this modularity does not discard individual expert contributions. Since SRA is linear and MoNB routing depends on feature identity, propagating a mixture of expert responses is mathematically equivalent to propagating each expert response separately and combining them with the same routing weights. Thus, expert-level contributions remain analytically decomposable without requiring separate propagation for every expert.
Regarding theory, we isolate MoNB specialization from graph propagation to characterize its approximation advantages independently of graph topology. Our specialization–routing analysis identifies when specialized basis spaces improve upon a fixed-dimensional global basis space. We acknowledge that better feature approximation does not automatically guarantee better graph predictions, since propagation and supervision may suppress differences between feature representations.
To directly evaluate the benefit of specialization in graph learning, we provide parameter-matched comparisons between MoNB and a global NBM using identical sparse aggregation architectures and training protocols. Test accuracy is reported as mean SD across seeds.
| Setting (seeds) | Parameters MoNB / NBM | MoNB Acc. (%) | Global NBM Acc. (%) |
|---|---|---|---|
| 64-node synthetic (10) | 1,669 / 1,663 | ||
| Cora (5) | 47,641 / 47,642 | ||
| PubMed (5) | 11,878 / 11,876 | ||
| ogbn-arxiv (5) | 10,416 / 10,417 | ||
| IGB-Small (5) | 47,187 / 47,188 |
MoNB achieves higher mean accuracy across all five settings under matched parameter budgets and identical propagation mechanisms. These results provide empirical evidence that feature specialization can benefit downstream graph prediction, consistent with the specialization advantage characterized in Theorem 1.
Rebuttal by Authors
W2. On the expressivity limitation for regular graphs
We agree with the reviewer's mathematical observation. For undirected regular graphs, the random-walk matrix is doubly stochastic. Consequently, under sum pooling, the normalized propagation operator preserves the global sum of each feature response, making the specified graph-level readout independent of connectivity for fixed node-feature multisets.
This is a direct consequence of combining stochastic propagation with linear sum pooling, rather than an overlooked limitation of MoNB. Increasing the number of experts or propagation depths does not resolve this property, as the reviewer correctly notes.
However, it is important to distinguish this graph-level restriction from node-level structural modeling. Although the global sum is preserved, propagation can still redistribute feature information across individual nodes according to graph connectivity. Consequently, node-level predictions remain sensitive to structural relationships.
HARMONIA is not intended to distinguish every pair of non-isomorphic graphs. Rather, it prioritizes fine-grained interpretability and efficient multi-hop structural modeling, particularly for large-scale node-level learning.
We will explicitly characterize this graph-level expressivity boundary. To assess the practical value of propagation under the same sum readout, we compared zero-hop MoNB with MoNB using 8 walk orders on three graph classification benchmarks.
| Dataset | HARMONIA Acc. (%) | Zero-hop MoNB Acc. (%) | Illustrative gain (pp) |
|---|---|---|---|
| Mutagenicity | 74.70 | 70.4 | +4.3 |
| PROTEINS | 70.76 | 68.5 | +2.3 |
| DD | 75.38 | 72.3 | +3.1 |
These results show that multi-hop propagation can improve graph-level prediction while preserving HARMONIA's additive readout.
Rebuttal by Authors
We thank the reviewer for the careful and technically detailed assessment. We would like to clarify that HARMONIA is designed to improve functional flexibility, interpretability, and scalability within a deliberately structured graph additive model, rather than to maximize unrestricted graph expressivity. Several observations raised by the reviewer follow directly from these design choices. We address each concern below.
W1a. On the novelty of SRA and polynomial graph propagation
We acknowledge that restricting RRWP to a linear topology function yields a feature-wise polynomial graph filter, and we do not claim novelty in polynomial filtering or sparse matrix multiplication themselves.
Specifically, the linearity of RRWP allows dense source-to-target aggregation to be reorganized into recursive sparse propagation without approximation or changes to the underlying predictive function. This reduces aggregation complexity from O(Tn2d) to O(T∣E∣d), without materializing dense RRWP operators.
The methodological distinction is therefore the additive parameterization and its integration with specialized feature responses, which enables fine-grained attribution within a scalable graph learning framework, rather than the introduction of a new propagation primitive.
We will clarify this distinction and further discuss its relationship to existing polynomial graph propagation methods in the revised manuscript.