Learning from Historical Activations in Graph Neural Networks
Authors: Yaniv Galron
Hadar Sinai
Haggai Maron
Moshe Eliasof
Venue: ICLR 2026 Poster (2026)
Keywords: Deep Learning; Graph Neural Networks; Graph Pooling
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a novel mechanism for learning from intermediate activations of GNNs called HistoGraph. We discuss its properties and demonstrate its effectiveness by evaluating it on a variety of graph benchmarks.

Abstract: Graph Neural Networks (GNNs) have demonstrated remarkable success in various domains such as social networks, molecular chemistry, and more. A crucial component of GNNs is the pooling procedure, in which the node features calculated by the model are combined to form an informative final descriptor to be used for the downstream task. However, previous graph pooling schemes rely on the last GNN layer features as an input to the pooling or classifier layers, potentially under-utilizing important activations of previous layers produced during the forward pass of the model, which we regard as historical graph activations. This gap is particularly pronounced in cases where a node’s representation can shift significantly over the course of many graph neural layers, and worsened by graph-specific challenges such as over-smoothing in deep architectures. To bridge this gap, we introduce HistoGraph, a novel two‑stage attention‑based final aggregation layer that first applies a unified layer-wise attention over intermediate activations, followed by node-wise attention. By modeling the evolution of node representations across layers, our HistoGraph leverages both the activation history of nodes and the graph structure to refine features used for final prediction. Empirical results on multiple graph classification benchmarks demonstrate that HistoGraph offers strong performance that consistently improves traditional techniques, with particularly strong robustness in deep GNNs. Our code is at https://github.com/YanivDorGalron/HISTOGRAPH

LEARNING FROM HISTORICAL ACTIVATIONS IN GRAPH NEURAL NETWORKS
Yaniv Galron
Hadar Sinai
Technion - Israel Institute of Technology yaniv. v. ronl campus techniors on il
Technion Israel Institute of Technology hada radarsite
@campus i
techni ac i
Haggai Maron
Moshe Eliasof
Technion - Israel Institute of Technology
Ben-Gurion University of the Negev University of Cambridge
NVIDIA
hargaimaroonttehnion..cc
eliaso triasoffbqu.... ac.il
ABSTRACT
Graph Neural Networks (GNNs) have demonstrated remarkable success in vari- ous domains such as social networks, molecular chemistry, and more. A crucial component of GNNs is the pooling procedure, in which the node features calcu- lated by the model are combined to form an informative final descriptor to be used for the downstream task. However, previous graph pooling schemes rely on the last GNN layer features as an input to the pooling or classifier layers, po- tentially under-utilizing important activations of previous layers produced during the forward pass of the model, which we regard as historical graph activations. This gap particularly pronounced in cases where node's s representation can shift significantly over the course of many graph neural layers, and worsened by graph-specific challenges such as over-smoothing bridge this gap, we introduce HISTOGRAPHI novel two-stage attention-based final aggregation layer that first applics a unified layer-wise attention over interme- diate activations, followed by node-wiss attention. By modeling the evolution of node representations across layers, our HISTOGRAPH leverages both the activation history of nodes and the graph structure to refine features used for final prediction. Empirical results on multiple graph classification benchmarks demonstrate that HISTOGRAPII offers strong performance that consistently improves traditional techniques, with particularly strong robustness in deep GNNs. Our code is at http::///aa.taaacooo//////////t/
deep architectures. To
INTRODUCTION
Graph Neural Networks (GNNs) have achieved strong results on graph-structured tasks, including
molecular property prediction and recommendation (Ma et al., 2019 Gilmer et al.] 2017 Hamilton
al.
2017). Recent advances span expressive layers (Maron et al.) 2019 Morris
2023
Frasca
ct al.
2022
Zhang et al. [2023a b, Puny et al. (023)), positional and structural encodings (Dwivedi
al.
2023 Rampášek et al. 2022 Eliasof al. 2023a Belkin & Niyogi 2003
Maskey al.
2022
Lim et al. Huang et al. 2024). and pooling Ying et al. 2018 Lee et al. 2019 Bianchi
al.
2020;
al. 2020 Vinyals al. 2015 Zhang al. 2018 Gao 2019
Ranjan et
2020
Yuan & 2020) However, pooling layers still underuse intermediate activations produced
during message passing, limiting their ability capture long-range dependencies and hierarchical
patterns (Alon & Yahav 2020
Li et al. 2019 Xu al. 2019).
In GNNs, layers capture multiple scales: early layers model local neighborhoods and motifs, while deeper layers encode global patterns (communities, long-range dependencies, topological roles) (Xu et al. 2019), mirroring CNNs where shallow layers detect edges/textures and deeper layers capture object semantics (Zeiler & Fergus 2014). Greater depth can overwrite early information (Li et al.) 2018 Eliasof et | 2022) and cause over-smoothing, making node representations indistinguish-
able (Cai & Wang 2020 Nt & Maehara 2019 Rusch et al. 2023). We address this by leveraging

---

(1) Stacking Graph Activatione
MPNN
MPNN
L
(2) Compute Layerwise Attention
QJK: Ej1PKK K,
Q = W W
amarage
Add Layer
(3) Compute Nodewise Attention
amerage
D
E NxD
M H)) Z R.D
Figure 1: Overview of HISTOGRAPH. (1) Given input node features X, and adjacency A, a backbone GNN produces historical graph activations X .., X (2) The Layer-wise attention module uses the final-layer embedding as a query to attend over all historical states while averaging across nodes, yielding per-node aggregated embeddings H. (3) Node-wise self-attention module refines H by modeling interactions across nodes, producing Z, then averaged if graph embeddings G is wanted.
historical graph activations, the representations from all layers, integrate multi-scan scale features at readout (Xu et al. 2018).
Several works have explored the importance of deeper representations, residual connections, and expressive aggregation mechanisms to overcome such limitations (Xu et al.) 2018 Li et al.) 102T
Bresson & Laurent 2017). Close to our approach are specialized methods like state space (Ceni
al.] (025) and autoregressive moving average (Eliasof al. 2025) models graphs, that consider a sequence node features obtained by initialization techniques. Yet, these efforts often focus on improving stability during training, without explicitly modeling the internal trajectory of node features across layers. That is, we argue that a GNN's ' computation path and the sequence of node features through layers be valuable signal. By reflecting this trajectory, models can better understand which transformations were beneficial and refine their final predictions accordingly.
In this work, propose HISTOGRAPI, self-reflective architectural paradigm that enables GNNs to reason about their historical graph activations. HISTOGRAPI introduces a two-stage self-attention mechanism that disentangles and models critical axes of GNN behavior: the evolution of node embeddings through layers, and their spatial interactions across the graph. The layer-wise module treats each node's 's layer representations as a sequence and learns to attend to the most informative representation, while the node-wise module aggregates global context to form richer, context-aware outputs. HISTOGRAM design enables learning representations without modifying the underlying GNN architecture, leveraging the rich information encoded in intermediate representations to enhance many graph related predictions (graph classification, node classification and link prediction).
We apply HISTOGRAPII in two complementary modes: (1) end-to-end joint training with the backbone, and (2) post-processing as lightweight head on a frozen pretrained GNN. The end-to-end variant enriches intermediate representations, while the post-processing variant trains only the head, yielding substantial gains with minimal overhead. HISTOGRAPH consistently outperforms strong GNN and pooling baselines TU and OGB benchmarks (Morris et al. 2020
Hu et al. 2020).
2

---

demonstrating that computational history is powerful, general inductive bias. Figure overviews HISTOGRAPH.
Main contributions. (1) We introduce self-reflective architectural paradigm for GNNs that leverages the full trajectory of node embeddings across layers; (2) We propose HISTOGRAPH, a two-stage self-attention mechanism that disentangles the layer-wise node embeddings evolution and spatial aggregation of node features; (3) We empirically validate HISTOGRAPH on graph-level classification, node classification and link prediction tasks, demonstrating consistent improvements over state-of- the-art baselines; and, (4) We show that HISTOGR APII can be employed as a post-processing tool to further enhance performance of models trained with standard graph pooling layers.
2 RELATED WORKS
Graph Neural Networks. GNNs propa- gate and aggregate messages along edges produce node embeddings that cap- ture local structure and features (Scarselli
Table I: Comparison of pooling methods based on inter- mediate representation usage, structural considerations, and layer-node modeling.
al. 2008 Gilmer al., 2017). GNN architectures are typically divided into two families: spectral GNNs, defining convolutions with the graph Laplacian (e.g., ChebNet (Defferrard et al.) 2016), GCN (Kipf & Welling, (2166), and spa- tial GNNs, aggregating neighborhoods di-
Int. Repr.
Layer-Node Model.
Method
Struct.
JKNet (Xu ct al.
2018
Yes
No
No
Se12Set Vinyals el al.
2015
No
Yes
No
SAGPool Lee et al. DifiPool
2019)
No
Yes
No
Ying cl
2018
No
Yes
No
SSRead [Lee et al.
2021
No
Yes
No
rectly (e.g.. GraphSAGE (Hamilton et al.
DKEPool (Chen ei al.
2023
No
Yes
No
2017). GAT (Veličković et al.) 2017)).
SOPool (Wagg & J1, 2023
No
Yes
No
Greater GNN depth expands receptive fields but introduces over-smoothing (Cai
GMT (Back ct al.
202T
No
Yes
No
Mcan/Max/Sum Pool
No
No
No
& WWnn 2020 Nt & Maehara 2019
HISTOGRAPH (Ours)
Yes
Yes
Yes
Rusch et al. 2023 Li al. 2018)) and over-
squashing (Alon & Yahav 2020). Mitigations include residual and skip connections (Chen al.
2020: Xu et al.) (0188), graph rewiring (Topping et al. [02T). and global context via positional
encodings or attention (Graphormer (Ying et 20.11.. GraphGPS (Rampášek et al.) (0222). Several models preserve multi-hop information for robustness and expressivity. HISTOGRAPH maintains node-embedding histories across propagation and fuses them at readout. Unlike per-layer mixing, this yields consolidated multi-scale summary, mitigating intermediate feature degradation and retaining local and long-range information.
Pooling in Graph Learning. Graph-level tasks (e.g.. molecular property prediction, graph classifi- cation) require a fixed-size summary of node embeddings. Early GNNs used cormmutationiivaaree
readouts such as sum, mean, and max (Gilmer et al. 2017: Zaheer et al., 2017), in GIN (Xu ct al. 2019). Richer structure motivated learned pooling: SortPool sorts embeddings and selects top-k (Zhang et al.) 2018);; DiffPool learns soft clusters for hierarchical coarsening (Ying et al. 2018); SAGPool scores nodes and retains a subset (Lee et al.] 2019). Set2Set uses L.STM attention for iterative readout (Vinyals et al. 2015). while GMT uses multi-head attention for pairwise interac- tions (Back et al. 2021). SOPool adds covariance-style statistics (Wang & Ji (023). Concurrently, Wang et al. (2024) propose leveraging global interactive patterns for cross-graph interpretabilityy which targets a complementary goal to our per- per-graph readout. A recent survey (Liu et al. 2022) reviews flat and hierarchical techniques on TU and OGB benchmarks. Hierarchical approaches (e.g., Graph U-Net (Gao & Ji (019)) capture multi-scale structure but add complexity and risk information loss. In contrast, HISTOGR APH directly pools historical activations: layer-wise attention fuses multi-depth features, node-wise attention models spatial dependencies, and normalization stabilizes contributions. This preserves information across propagation depths without clustering or node dropping. Table summarizes design choices and shows HISTOGRAPH is the only method combining intermediate representations with structural information.
Residual Connections. Residuals are pivotal for deep GNNs and multi-scale features. Jumping Knowledge flexibly combines layers (Xu et al. 2019). APPNP uses personalized PageRank to preserve long-range signals (Gasteiger et al. 2018), and GCNII adds initial residuals and identity
3

---

mappings for stability (Chen al. 2020). In pooling, Graph U-Net links encoder-decodee via skips (Gao & Ji 2019), and DiffPPoo's cluster assignments act as soft residuals preserving early-layer information Ying al. 2018). Other methods show that learnable residual connections mitigate oversmoothing (Fliasof et al. 2023b), and allow a dynamical system perspective on graphs (Eliasof HISTOGRAPE departs by introducing historical pooling: readout, accumulates node histories across layers, creating a global shortcut at aggregation that revisits and integrates multi-hop features into the final representation unlike prior models that apply residuals only within node updates or via hierarchical coarsening.
et al. 2024). Differently,
LEARNING FROM HISTORICAL GRAPH ACTIVATIONS
We introduce HISTOGRAPH, learnable pooling operator that improves graph representation learning across downstream tasks by integrating layer evolution and spatial interactions in end-to-end differentiable framework. Unlike pooling that operates on the last GNN layer, HISTOGRAPII treats hidden representations as a sequence of historical activations. It computes node embeddings by querying each node's 's history with its final-layer representation, then applies spatial self aiff-attention to produce fixed-size graph representation. Details appear in Appendix B and Algorithm Figure overviews HISTOGRAPH, and Table compares to other methods.
Notations. Let F ND denote the raw input node features, where N the number of nodes in the batch and Dio is the input feature dimensionality. The initial representation is given by ( Emb,((), where Emb,a is linear layer projecting input features to the GNN hidden dimension. For each subsequent layer = 1...., L 1, the representations are computed recursively as x (1) = GNN (X (x(),)), where GNN( denotes the (-th GNN layer.
We denote by X
(X) x ..... X(!-11) NXXXD the historical graph activations, i.e.. the stacked node embeddings across all L layers. Each node thus has L historical embeddings corresponding to different depths of message passing. When GNN layers produce activations with varying dimensionalities Do, D DL-1, we apply per-layer linear projections W RR.r
Rd to map each layer's 's output to common hidden dimension D before stacking into X.
Input Projection and Per-Layer Positional Encoding, We project the historical activations to common hidden dimension D using linear transformation:
X
Emb (X) E R NxLxD
To encode layer ordering, we add fixed sinusoidal positional encodings as in Vaswani et al. (2017)
Pl.2 sin (11
1 (100002/D)
P122+11
cos (1000024/7)
for 0 < L,0 D/2, resulting in P RLXD The positional encoding is broadcast across the node dimension and added element-wise to obtain layer-aware features: X,,; X', Pt, for each node e and layer I, yielding X BNNLLD
Layer-wise Attention and Node-wise Attention. We view each node through its sequence of historical activations and attention learn which activations most relevant. We use only the last-layer embedding as the query to attend over all historical states:
Q = Xx-,WW E NXIXD
X E NXLXD V-XERNXIXD.
We apply scaled dot-product attention and average across nodes, obtaining a layer weighting scheme:
QK
Average
E L
VD
Rather than softmax, which enforces non-negative weights and suppresses negative differences, we apply normalization that permits signed contributions ai Σ1- This allows the model to
4

---

express additive subtractive relationships between layers, akin to approximations in dynamical systems. The cross-layer pooled node embeddings are computed as:
H
X
X ERNXD.
(5)
-ー- 1=0 1== cV
1=0
Graph-level Representation. We first aggregate each node's history weighted by relevance to the final state, with a residual recency bias from the final-layer query, into H. To obtain a graph-level representation, we apply multi-head self-attention across nodes exactly once at the readout stage-not not at every GNN depth-omitting spatial positional encodings to preserve permutation invariance:
= (H, H, H) E RNDD
(6)
optionally followed by residual connections and I LayerNorm. Averaging over nodes yields G Average(Z) RD, which then feeds the final prediction head (typically an MLP). Crucially, because node-wise self-attention is applied only once at the final readout-rather than at every message- passing layer- it does not contribute to werrssoothing during the GNN forward pass and incurs only single D) cost. Early message- passgggggggngggggg layers capture local interactions, whereas deeper layers encode global ones (Gasteiger et al. 2019; Chien al., (020). By attending across layers and nodes, HISTOGR APH fuses local and global cues, retaining multi-scale structure and validating our motivation.
Computational Complexity. Layer-wise attention costs OLLD) per node; spatial attention over N nodes costs O(N Thus the per-graph complexity
O + N2 O(N(L N
attention costs ( which is prohibitive. Our two-stage scheme first across layers (O(LD) per node), then across nodes DD) this. Since L < in practice, the dominant cost is O(N² matching single graph-transformer layer. A standard graph transformer that stacks L, such layers incurs O D) (Yun al. 2019); HISTOGRAPH reduces the depth coefficient from L to 1, because layer-wiss wise attention operates per node in OLL)) and the O(N2 spatial attention is applied only once readout. This decomposition keeps historical activations tractable despite the quadratic node term. Empirically, HISTOGRAPH adds only a slight runtime over standard GNN forward pass (Figure while delivering significant gains across multiple benchmarks, as seen in Tables 2 and
with memory ( + N2) from attention maps. naïve joint
Frozen Backbone Efficiency. With a pretrained, frozen paassage-passing backbone, we train only the HISTOGRAPH head. We cache the N x L x D activations per graph in one forward pass and skip gradients through the backbone, removing O(L(ED + ND²)) work (where is the number of edges). The backward pass applies only to the head, O(N(L + N)D), substantially reducing memory and training time. This is especially useful in low-resource or few-shot regimes, and when fine-tuning large datasets where repeated backpropagation through T. GNN layers is prohibitive.
Scalability Considerations. The current design is best suited for small-to-medium--sied graphs; we discuss scaling strategies for larger graphs in Appendix G
4 PROPERTIES OF HISTOGRAPH
In this section, we discuss the properties of our HISTOGRAPH, which motivate its architectural design choices. While the general idea of attention over a sequence of representations is not unique to HISTOGRAPH, the specific combination with GNN historical activations yields properties that do not arise standard attention-ben based pooling. In particular, these properties show how (i) lase attention mitigates over-smoothing and acts as dynamic trajectory filter, (rather than softmax) enables the architecture to approximate low/high pass filters over the layer trajectory, and (iii) node-wise attention readout is beneficial in our HISTOGRAPH.
(ii) the signed normalization
HISTOGRAPH RAPH can mitigate Over-smoothing. One key property of HISTOGRAPH is its ability to mitigate the over-smoothing problem in simple way. As node embeddings tend to become
5

---

FT
Norm of Difference
End-to-End
End to End
0.016
Atterton
0.015
0.034
14
21
42
Layer
Figure 2: Visualizations on the IMDB-B dataset with 64-layer HISTOGRAPH. (left) Attention patterns layers under different training regimes. (right) Emhedding evolution throughout training, measured by the normed difference between final and intermediate representations.
indistinguishable after a certain depth los, i... (xf 1, l2 2 los. HISTOGRAPH aggregates representations across layers using weighted combination:
X ((x) = for all node pairs u, and layers
hu
atxu (1)
with Ma=1
early layers let the final embedding h. retain discrim- inative early representations, countering over-smoothing so node embeddings remain distinguishable (hh, he # 0). This mechanism underlies HISTOGRAPH'S robustness deep GNNs, corroborated by the depth ablation in Table 17
Attention weights or that place nonzero
Fig. 2 (which shows substantial early-layer attention and nonzero differences between historical activations), and the feature distance diagnostics in Table T2 (which confirms that HISTOGRAPH increases embedding diversity across all layers compared to a standard GCN), We formalize HISTOGRAPII'S mitigation of over-smoothing Proposition [ the proof appears in Appendix B
Proposition 1 (Mitigating Over-smoothing with HISTOGRAPH). Les x E TR. denote the embed- ding of node v at layer I of a GNN. Suppose the GNN exhibits over-smoothing, i.e., there exists layer Lo sufficiently large such that for all layers (1, l2 > Lo and all nodes u, v,
||x
x x((2) 0.
(9)
Let HISTOGRAPH compute the final node embedding as
L-1
hy
axx!
(10)
I=0
where on are learned attention weights. Then, for distinct nodes u and v, there exists at least one layer 1' < Lo with ou + such that
hh hell > 0.
(11)
That is, HISTOGRAPH retains information from early layers and mitigates over-smoothing.
Interpretability of Learned Attention Weights. Figure shows that HISTOGRAPH learns non- trivial layer weightings: substantial weight is placed on early over-smoothingg layers and the final layer, forming task-adapted profile that balances local and global information. A detailed analysis appears in Appendix [
HISTOGRAPH's Layer-wise Attention an Adaptive Trajectory Filter. We interpret HISTO-
GRAPII'S layer-wise attention
Adaptive Trajectory Filter, which dynamically aggregates
node's embeddings across layers based on learned weights. Let (x() JE= c RD denote node's embeddings at each layer. We define aggregated embedding as:
4-1
L-1
h Σ
O with Ea=
(12)
1=0

---

(a) Input
(b) Target
(c) GCN
(d) HISTOGRAPH
Figure 3: Graph and signal transformations: (a) input node features; (b) prediction target, the node-
feature gradient; (c) GCN output trained to approximate (b) from (a): (d) HISTOGRAPH output. The gap between GCN and HISTOGRAPII underscores the importance of adaptive trajectory filtering. Node colors: red, blue, and green denote values 0,
where og are learnable attention weights. general, any weighted combination over a sequence can be viewed filter. However, two design choices make HISTOGRAPH's filtering distinct from standard attention mechanisms. First, the signed normalization (division by sum rather than softmax) permits negative weights, enabling the model to express subtractive relationships between eovers-nnaloguus to a finite impulse response (FIR) filter with signed coefficients. This allows the aggregation to implement: (i) low-pass filter when dy I (uniform average); (ii) a high-pass filter when on = 6,, ō (first difference); and (iii) a general FIR filter when are learned. Standard softmax-based attention, by contrast, is restricted non-negative convex combinations and cannot realize subtractive (high-pass) filtering. Second, HISTOGRAPH applies this filtering specifically to the GNN's computational trajectory- sequence of representations that progressively encode larger neighborhoods rrathr than to an arbitrary set of features. This means the filter directly controls the balance between local shallow-layer) and global (deep-layer) information at readout, property that is specific to the GNN setting.
Figure illlsstaate case where GCN fails at high-pass filtering, whereas HISTOGRAPH succeeds. The barbell graph-a symmetric clique joined by single edge-createe a sharp gradient discontinuity, highlighting how the adaptive filtering of HIstoGRAPE preserves such signals, unlike standard GCNs. Appendix DaaddiiDDuun further analyzes the usefulness of node-wise attention in HISTOGRAPH.
EXPERIMENTS
In this section, conduct an extensive set of experiments demonstrate the effectiveness of HISTOGRAPH as a graph pooling function. Our experiments seek to address the following questions:
(Q1) Does HISTOGRAPH consistently improve GNN performance over existing pooling functions across diverse domains?
(Q2) Can HISTOGRAPH be applied as a post-processing step to enhance the performance of pretrained GNNs?
(Q3) What is the impact of each component of HISTOGRAPH performance?
Baselines. We compare HISTOGRAPH against diverse baselines spanning graph representation and
pooling. dlessage-passigg GNNs: GCN and GIN with mean or sum aggregation (Kipf & Welling
2016 Xu et al. 2019). Set-level pooling: Set2Set (Vinyals et al.
2015). Node-dropping pooling:
SortPool Zhang et al., 2018), SAGPool (Lee et al. 2019), TopKPoo Pool [Gao & Ji 2019). ASAP (Ran-
jan et al. 2020). Clustering- based pooling: DiffPool Ying et al. 2018). MinCutPool (Bianchi
et 2000), HaarPool (Wang et al. 2020), StructPool (Yuan & Jil 2000). EdgePool (Diehl 2019
merges nodes along high-scoring edges. Attention based global pooling: GMT (Baek et al.
2021)
Additional models: SOPool (Wang & 20.3). HAP (Liu et al.] (202)) PAS (Wei et al. 202
GMN (Ahmadi 2020), DKEPool (Chen et al./ (023). JKNet (Xu et al. 2018). On TUdatasets, we also include five kernel baselines: GK (Shervashidze et al. 2009). RW (Vishwanathan al. 2010).
WL subtree (Shervashidze et al.) (011). DGK (Yanardag & Vishwanathan 2015), and AWE (vvnoo
& Burnaey 2018). An overview of baseline characteristics versus HISTOGRAPH appears in Table
Benchmarks. We use the OGB benchmark (Hu et al. 2020) and the widely used TUDatasets (Morris
al. 2020); dataset statistics appear in Tables and in Appendix A For OGB, follow Back et al.
7

---

Table Comparison of graph-clasiffiation accuracy (%) 1 on TU datasets with HISTOGRAPH and existing benchmark methods. All methods use a 5-layer GIN backbone. Only top-three methods (plus JKNet) are shown and marked First, Second, Third. Additional results and methods appear in Table 9
in Appendix F
Method / Dataset
IMDB-B
IMDB-M
MUTAG
PTC
PROTEINS
RDT-B
NC11
SOPool Wang & Ji
2023
78.
54.6+3.6
45.3
75.0
80.1
91.7-2.7
84.5.1.3
GMT
Back et at. 2021)
79.5+2.5
55.042.8
95.843.2
74.5
80.3
93.9
84.1-2.1
HAP
I.u ct at.
202T
79.1
55.3+2.6
95.212.8
75.243.6
79.944.
92.2
81.3-1.8
PAS
[Ci ct al.
2021
77.34:4.1
53.743.1
94.3
71.4
78.5
93.7
82.8-2.2
HaarPool Wang ct al.
2020
79.3.33.4
53.843.0
90.0
73.145.0
80.4+1.88
93.6+1.1
78.6
GMN (Ahmadi 20220)
76,644.5
54.2+2.7
95.7
76.3
79.5
93.5
82.4_1.9
DKEPool (Chen ei al.
2023
80.942.3
56.312.0
97.3+3.6
79.614.00
81.243.8
95.0+1.0
85.4
JKNet [Xu et al.
2018)
78.5
54.542.0
93.043.5
72.5+2.0
78.0
91.522.0
82.0_1.5
HISTOGRAPH (Ours)
87.2+1.7
61.9
97.9
79.144.8
97.840.4
93.4
85.9
Table 3: Comparison of graph classification ROC-AUC (%) on different datasets between HIs- TOGRAPH and existing baselines on OGB datasets. All methods use a 3-layer GCN backbone for fair comparison. Only the top three methods are included and marked by First, Second, and Third. Additional methods are presented in Table 10 in Appendix
symbolizes non- -ca-nacrabble methods.
Method / Dataset
MOLHIV
MOLBBBP
MOLTOX21
TOXCAST
GCN
Kipf& Welling
2016
76. 16.188.u 18
65.67 1..86
75.04-10.80
60.53
GIN
(uu al.
2019)
15.84
66.78.1.77
73.27
60.83
MinCutPool (Bianchi et al.
2020
75.37=2.00
65.97+1.18
75. +0.60
62.48+1.33
GMT (Back et al. 2021
77.56
68.31
77.30+0.59
65.44
HAP
(Luu al.
2021
71.31
66.01+1.43
PAS
Wei et al.
2021
2..
66.97:11.21
DKEPool (Chen ct al.
2023
78.65
69.73
HISTOGRAPH (Ours)
77.81
72.02:1146
77.49 66.35
(202 Chen et al. (202)) with 3 GCN layers; for TUDatasets, we adopt Wang & Jil (023): Chen et al. 2023) Gao & Ji (2019); : Gao al. (202T) typically using GIN layers. For deeper variants, we keep the backbone and vary the number of layers. Hyperparameters are in Appendix C.T Additionally. we benchmark HISTOGRAPP APH on several node-classification datasets spanning heterophilic and homophilic graphs (Table [T] and across varying GNN depths (Table 4.. Further results appear Appendix F feature-distance across layers for GCN and GCN with HISTOGRAPH (Table 12).
comparison the GraphGPS baseline (Table 14), and link prediction (Table 13).
5.1 END-TO-END ACTIVATION AGGREGATION WITH HISTOGRAPH
We evaluate end-to-end activation aggregation with HISTOGRAPH on graph-level benchmarks and node classification. We first report results on TUDatasets (Table 2) followed by OGB molecular property prediction (T) and finally depth-scaled node classification (Table
TUDatasets. On seven datasets (Morris al., 2020) (IMDB-B, IMDB- MM, MUTAG, PTC, PROTEINS,
RDT-B, NCT1), HISTOGR APH attains state-of-thh-arr performance on 5 of 7: IMDB-B 87.2%, IMDB-M 61.9%, MUTAG 97.9%, PROTEINS 97.8%, NC11 85.9%. marginally behind on PTC at 79.1 % versus 79.6% for DKEPool. Relative to the second-best method, gains substantial PROTEINS (+16.6%), IMDB-B (+6.3%), and IMDB-M (+5.6%). Although DKEPool slightly leads on PTC and RDT-B, the overall trend favors HISTOGRAPH across diverse graph classification benchmarks.
The large gain on PROTEINS (+16.6%) is driven by all three HISTOGRAPH components: the ablation in Table 6 shows that removing any of signed normalization, layer-wise, or node-wise attention substantially degrades performance, and Table 16 confirms that uniform averaging and randomized attention fall far short. We provide detailed discussion in Appendix
8

---

Table 4: Node classification accuracy (%) on benchmark datasets with varying GNN depth.
Dataset
Method
16
32
64
Cora
GCN
81.1
80.4
69.5
64.9
60.3
28.7
GCN + HISTOGRAPH
81.3
82.9
80.7
83.1
80.6
77.5
Citeseer
GCN
70.8
67.6
30.2
18.3
25.0
20.0
GCN + HISTOGRAPH
70.9
69.5
69.9
69.3
67.2
63.4
Pubmed
GCN
79.0
76.5
61.2
40.9
22.4
35.3
GCN + HISTOGRAPH
78.9
78.2
78.6
80.4
80.0
79.3
OGB molecular property prediction. On four OGB datasets (Hu at 2020) (MOLHIV, MOLTOX21, TOXCAST, MOLBBBP). HISTOGRAPH achieves the top ROC-AUC on 3 of 4: MOLBBBP 72.02%, MOLTOX21 1 77.49%, TOXCAST 66.35%. Margins over the second-best are +2.29% on MOLBBBP versus DKEPool, +0.91 % on TOXCAST versus GMT, and 40.19% on MOLTOX21 versus GMT. On MOLHIV, DKEPool leads with 78.65%, while HISTOGRAPH is competitive 77.81 %, ranking the top three, indicating strong generalization across molecular property prediction.
Node classification. Table shows that HISTOGRAPII mitigates over- smoothing: standard GCN accuracy degrades with depth, whereas HISTO- GRAPH maintains stable, competitive performance up to 64 layers. This improves feature propagation while preserving discriminative power, par- ticularly on heterophilic graphs. Additional node-classification results for heterophilic and homophilic datasets appear in Table 11 in Appendix
Table 5: Graph classifica- tion accuracy (%) 1 sum- mary. More results are reported in Table I7
Method
MeanPool
54.7
5.2 POST-PROCESSING OF TRAINED GNNS WITH HISTOGRAPH
FT
67.3
IMDB-M
Full FT
62.7
We evaluate HISTOGRAPH as a lightweight post-processing strategy on four TU graph-clasiffiatioon datasets: IMDB-B, IMDB-M, PROTHINS, and PTC. For each dataset, we train GINs with 5, 16, 32, and 64 layers using standard architectures and mean pooling. After convergence, save per-fold checkpoints and apply HISTOGRAPH in three modes: (i) auxiliary head on frozen backbone (HISTOGRAPH(TT), (ii) full joint fine-tuning (HisToGRaPH(Fu)) FT)), and (iii) end-to-end training from scratch for comparison. Complete depth-wise results appear in Table 17
MeanPool
76.0
FT
IMDB-B
Full FT 94.0
McanPool
75.9
FT
97.3
PROTEINS
Full FT
97.3
in Appendix
McanPool
77.1
FT
85.7
Table summarizes the grash-clasiificttion accuracy (%) across GIN depths for each dataset and method. HISTOGRAPII used as a frozen auxiliary head (FT) consistently improves performance vs. MeanPool, often matching surpassing full fine-tur fine-tuning (Full FT) and end-to-end training. For example, on IMDB-M, FT raises accuracy from 54.7% (McanPool) to 67.3%; on IMDB- B, both FT and Full FT reach 94.0%, far above the baseline (76.0%) and end-to-end (87.2%) On PROTEINS, all HISTOGRAPH variants achieve near-optimal performance, demonstrating effectiveness across datasets of varying size and characteristics. On PTC, Full FT attains the best score (97.1%), showing joint fine-tuning can further enhance results. Overall, HISTOGRAPH offers a flexible, effective post-processing strategy that consistently boosts GNN performance.
PTC
Full FT
97.1
End-to-tind
Runtime Analysis. We measure average training and inference time per epoch for GCN backbones with 3 and 32 layers on MOLHIV and TOXCAST, comparing MeanPool, End-to-End, and FT. As shown in Fig. End-to-End is costlier than McanPool during training (c.g.. 60.34s vs. 41.27s for 32 layers on MOLHIV) yet remains scalable. FT, which fine-tunes only the head on a pretrained MeanPool model, cuts overhead: training time is slightly higher for 3 layers but significantly lower for 32 layers on both datasets. At inference time, HISTOGRAM GRAI adds negligible overhead over MeanPool since no backward pass is required and the forward cost of the HISTOGRAPIC head (O(NLD= 22 D)) is small relative to the GNN backbone on the molecular-sen scale graphs evaluated (see Table 18 in Appendix for detailed inference times). While achieving results comparable End-to-Ent (Table I7), FT offers an efficient way to boost existing models. Finally, HISTOGRAPH is significantly faster than GMT (Baek et al. 2021) in almost all cases, with larger speedups for deeper networks.

---

282.825
43.34s
GMT
GMT
End-to-End
End-to-End
FT
Time (seconds)
10a
MeanPool
Time (seconds)
MeanPool
60.34s
10.65s
10
41.27s
7.245
5.02s
15.11s
2.94s
2.10s
1:91s
9.20s
1.52s
7.59s
32
Number Layers
Number of Layers
(a) MOLHIV
(b) TOXCAST
Figure 4: Average training time per epoch (in log scale) for GCN backbones with 3 and 32 layers, evaluated on the MOLHIV and TOXCAST datasets, Each configuration is compared across four post- processing methods: (ack et al. 202T), MeanPool, HISTOGRAPH, and HISTOGRAPI-FT.
5.3 ABLATION STUDY
Setup. We assess component contributions the TUDatasets PROTEINS dataset by removing or modi- fying parts and measuring classification accuracy (Ta- 6l. We test three variants: (i) removing division- by-sum normalization, (ii) disabling layer-wise tention that models inter-layer dependencies, and (iii) disabling node-wise attention that captures cross- node dependencies.
Table 6: Ablation on the PROTEINS dataset. Each row shows the performance of HISTO- GRAPH variant with a component removed.
Variant
Acc. (%)
Std.
DKEPool
81.20
3.80
w/o Division by Sum
74.45
6.28
w/o Layer-wise Attention
78.61
4.82
Results and discussion. GRAPH attains 97.80% accuracy with 0.40 standard deviation. Every ablation reduces accuracy; remov- ing division-by-sum normalization performs worst at 74.45% + 6.28, indicating each component is necessary. Removing layer-wise normalization allows attention weights to grow unbounded, destabilizing training and overshadowing early discriminative layers. Our signed normalization balances layer contributions and enables additive and subtractive filtering (Section F preserving discriminative information and stability. Against alternative aggregation strategies (mean aggregation and randomized attention). HISTOGRAPP consistently outperforms them by a significant margin (Table T6. Appendix F Overall, normalization, layer-wise attention, and node-wise attention critical for capturing complex dependencies and realizing the full performance of HISTOGRAPH.
PROTEINS, HISTO-
w/o Node-wise Attention
80.78
7.71
HISTOGRAPH (Ours)
97.80
0.40
6 CONCLUSION
We introduced HISTOGRAPH, two-stage cicnntion-based pooling layer that learns from historical activations to produce stronger graph-level representations. The design is simple and principled: layer- wise attention captures the evolution of each node's trajectory across depths, node-wise self oeff-attention models spatial interactions readout, and signed layer-wise normalization balances contributions across layers preserve discriminative signals and stabilize training. This combination mitigates over-smoothing and supports deeper GNNs while keeping computation memory overhead modest. Across TU and OGB graph-level benchmarks. node-clan ciadecllassficationn settings, and link prediction (OGBL-COLLAB), HISTOGRAPH consistently improves over strong pooling baselines and matches surpasses leading methods multiple datasets. Moreover, used lightweight post-processing head on frozen backbones, HISTOGRAR GRAH delivers additional gains without retraining the encoder. The current design is best suited for moall-to-medium---ine graphs; extending HISTOGRAPH to very large graphs via sparse attention or hierarchical coarsening is a promising direction for future work. Taken together, the results establish intermediate activations valuable signal for readout and position HISTOGRAPH practical, general drop-in in pooling layer for modern GNNs.
10

---

Acknowledgements HM is supported by the Israel Science Foundation through personal grant (ISF 264/23) and an equipment grant (ISF 532/23), and by the Career Advancement Chairs in Artificial Intelligence Schhiitt Futures. ME acknowledges support from the Isracli Ministry of Innovation, Science & Technology.
Reproducibility Statement To ensure reproducibility, we provide all code, model architectures, training scripts, and hyperparameter settings in public repository (available upon acceptance). Dataset preprocessing. splits, and downsampling are detailed in Appendix [A] Hyperparameter configurations, including batch sizes, learning rates, hidden dimensions, and model depths, are documented in Appendix [. Experiments were conducted using PyTorch and Py PyTorch Geometric on NVIDIA L40, A100, and GeForce RTX 4090 GPUs, with Weights and Biases for logging and model selection. All random seeds and training protocols are specified to facilitate replication.
Ethics Statement Our work involves minimal ethical concerns. We use publicly available datasets (TU, OGB) that are widely adopted in graph learning research, adhering their licensing terms. No private sensitive data is introduced. Our method is primarily methodological, but we encourage responsible use to avoid potential misuse in applications that could impact privacy or enable harm. We acknowledge the environmental impact of large-scale training and note that HISTOGRAPHI's computational efficiency may reduce energy costs compared to retraining full models.
Usage Large Language Models This Work Large language models were used solely for minor text editing suggestions to improve clarity and grammar. All research concepts, code development, experimental design, and original writing were performed by the authors.
REFERENCES
Amir Hosein Khas Ahmadi. Memory-based graph networks. University of Toronto (Canada), 2020.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05200 2020.
Álvaro Arroyo, Alessio Gravina, Benjamin Gutteridge, Federico Barbero, Claudio Gallicchio, Xiaowen Dong, Michael Bronstein, and Pierre Vandergheynst. On vanishing gradients, over- smoothing, and over-squashin in gnns: Bridging recurrent and graph learning. arXiv preprint SEKV:22502.08811 2025.
Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. In International Conference on Learning Representations, 2021. URL
https: optp://///eeeeeiiew net forum wow.mmidd--Hcgaaaaaaii
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput., 1373-1333) June 2003.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International conference machine learning, pp. 874 883. PMLR, 2020.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL httph:ttp///// hwtp:::://wwww.. wandb com/ Software available from wandb.com.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets.
arXiv preprint
arXiv:1711.07553. 2017.
Chen Cai and Yusu Wang. A note over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
Andrea Ceni. Alessio Gravina, Claudio Gallicchio, Davide Bacciu, Garola-Bibiane Schonlieb, and Moshe Eliasof. Message-passing state-space models: Improving graph learning with modern sequence modeling. arXiv preprini arXiv:2505. 18728, 2025.

---

Kaixuan Chen, Jie Song, Shunyu Liu, Na Yu, Zunlei Feng, Gengshi Han, and Mingli Song. Dis- tribution knowledge embedding for graph pooling. IEEE Transactions on Knowledge and Data Engineering. (5(8):7888-7908 2023. doi: 10.109/TKDDE222.3206066
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference machine learning, pp. 1725-17255 1735. PMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.09988, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filterin.. Advances in neural information processing systems, 29, 2016.
Frederik Diehl. Edge contraction pooling for graph neural networks. arXiv preprint arXiv: 10990, 2019.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
Moshe Eliasof, Eldad Haber, and Eran Treister. pathgen: Learning general graph spatial operators from paths. In International conference on machine learning, pp. 5878-5891. PMLR, 2022.
Moshe Eliasof, Fabrizio Frasca, Beatrice Bevilacqua, Eran Treister, Gal Chechik, and Haggai Maron. Graph positional encoding via random feature propagation. In International Conference on Machine Learning, pp. 9202-9223, PMLR, 2023a.
Moshe Eliasof, Lars Ruthotto, and Eran Treister. Improving graph neural networks with learnable propagation operators. International Conference on Machine Learning, pp. 9224-9245 PMLR, 2023b.
Moshe Eliasof, Eldad Haber, Eran Treister, and Carola-Bibiane Schönlieb. On the temporal domain of differential equation inspired graph neural networks. In International Conference on Artificial Intelligence and Statistics, pp. 1792-1800 PMLR, 2024.
Moshe Eliasof, Alessio Gravina, Andrea Ceni, Claudio Gallicchio, Davide Bacciu, and Carola- Bibiane Schönlieb. Graph adaptive autoregressive moving average models. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu (eds.). Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 15232 - PMLR, 13-19 Jul 2025. URL pattps://pae pettps://prrceeciing mlr...smm....................mm. wrw.srpesssss.... stttess/v2677 wtttess/v257/eeeasst22222
html
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and ex- tending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems, 35:31376-3 31390, 2022.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning, pp. 2083-2092. PMLR, 2019.
Hongyang Gao, Yi Liu, and Shuiwang Ji. Topology-aware graph pooling networks. IEEE Transactions Pattern Analysis and Machine Intelligence, 43(12):4512-45 4518, 2021.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv: 1810.0999 2018.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems, 32, 2019.
12

---

Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, PP- 1263-1272. PMLR, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
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 in neural information processing systems, 33:22 18 11-12133, 2020.
Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanic Jegelka, and Pan Li. On the stability of expressive positional encodings for graphs, In The Twelfth International Conference on Learning Representations, 2024, URL BRLnttps:/// http::/:///peewwwe....... new.eeewwweeeeeeeeeeeeeeeeeeeeee nerm/orrmm
1d=xAqcJ9XoTf
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International conference machine learning, pp. 2186-2195 PMLR, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1609.06000.00000 (099000997 2016.
Dongha Lee, Su Kim, Seonghyeon Lee, Chanyoung Park, and Hwanjo Yu. Learnable structural semantic readout for graph classification. In 202/ IEEE International Conference Data Mining (ICDM). pp. 1180-1 185. IEFE, 2021.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings of the 36th International Conference on Machine Learning, 09-15 Jun 2019.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9267-9276, 9276, 2019.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference on machine learning, pp. 6437-6449. PMLR, 2021.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-sun sumissuperiieed learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In The Eleventh International Conference on Learning Representations, 2023. URL https
//openreviews www.wwiwww.... net http:/forummiddde /tgpr//eoo....o.ooooooomooo/oooo UHqMorzil
Chuang Liu, Yibing Zhan, Chang Li, Bo Du, Jia Wu, Wenbin Hu, Tongliang Liu, and Dacheng Tao. Graph pooling for graph neural networks: Progress, challenges, and opportunities. arXiv preprint (rXiv:2204.0732// 2022.
Ning Liu, Songlei Jian, Dongsheng Li, Yiming Zhang, Zhiquan Lai, and Hongzuo Xu. Hierarchical adaptive pooling by capturing high-order dependency for graph representation learning. IEEE Transactions Knowledge and Data Engineering, 35(4):3952 32639992295999299 2021.
Yao Ma, Suhang Wang, Charu C. Aggarwal, and Jiliang Tang. Graph convolutional networks with cigenpooling. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 19, pp. 723-731, New York, NY, USA, 2019, ACM. ISBN 978- 1-4503-6201-6. doi: 10. 10.1 10.1145/32925003333088 03925500.333999
URL http::////ooooo acm. wtt.://.......ooo.........1
Haggai Maron, Heli Ben-Hamu. Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
13

---

Sohir Maskey, Ali Parviz, Maximilian Thiessen, Hannes Stärk, Ylli Sadikaj, and Haggai Maron. Generalized laplacian positional encoding for graph representation learning. In NewrIPS 2022 Workshop on Symmetry and Geometry in Neural Representations, 2022. URL | //openreview. net/
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663, 2020.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey. and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. Journal of Machine Learning Research, 24(333):1 2023.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprini arXiv: met:::9005995500 2019.
A Paszke. Pytorch: An imperative style, segh-performance deep learning library. arXiv preprint arXiv:1912.01703. 2019.
Omri Puny, Derek Lim, Bobak Kiani, Haggai Maron, and Yaron Lipman. Equivariant polynomials for graph neural networks. In International Conference Machine Leurning, pp. 28191-28222. PMLR, 2023.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems, 35, 2022.
Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 5470-5477, 2020.
Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprint 2.XX::2303.10993 2023.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61 100 2008.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pp. 488-495. PMLR, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lhmann graph kemnlls. Journal of Machine Learning Research, 12(9), 2011.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111. 14522, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. arXiv preprint arXiv:1511.0639 2015.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. The Journal of Machine Learning Research, 11:1201-1242, 2010.
Yu Guang Wang, Ming Li, Zheng Ma, Guido Montufar, Xiaosheng Zhuang, and Yanan Fan. Haar graph pooling. In International conference machine learning, pp. 9952-9962. PMLR, 2020.
14

---

Yuelin Wang, Muxi Zhang, et al. Graph neural networks with learnable and optimal polynomial bases. arXiv preprint arXiv:2-02.122440 2024.
Zhengyang Wang and Shuiwang Ji. Second-order pooling for graph neural networks. IEEE Transac- fions on Pattern Analysis and Machine Intelligence, 4566))6870-6880, June 2023. ISSN 1939-3539. doi: 10. wwtp:ppmii2200.2990000
URL http: / 1109/ / AMI. 2020
2999032
Lanning Wei, Huan Zhao, Quanming Yao, and Zhiqiang He. Pooling architecture search for graph classification. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2091-2100, 2021.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453-5462. PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https: 7/openreview net.
Pinar Yanardag and SVN Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888, 2021.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling. Advances neural information processing systems, 31, 2018.
Hao Yuan and Shuiwang Ji. Structpool: Structured graph pooling via conditional random fields. In Proceedings of the 8th international conference on learning representations, 2020.
Seongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo Kim. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poezos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslic, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang. Li Yang. and Amr Ahmed. Big bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems, volume 33, pp. 17283-17297, 2020.
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In Computer Vision-ECCV 2014 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part / 13, pp. 118-833. Springer, 2014.
Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler- tests. In International Conference on Machine Learning, pp. 41019-41077. PMLR, 2023a.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. arXiv preprini arXiv:2301.0m 1.00005 2023b.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings the AAAI conference on artificial intelligence, volume 32, 2018
15

---

A DATASET STATISTICS
Tables and summarize the statistics of the datasets used in our experiments. Table 7 covers molecular property prediction datasets from the Open Graph Benchmark (OGB). including MOLHIV, MOLBBBP, MOLTOX21, and TOXCAST, reporting the number of graphs, number of prediction classes, and average number of nodes per graph. Table 8 presents the statistics of graph classification datasets from the TU benchmark suite, including social network datasets (IMDB-B, IMDB-M) and bioinformatics datasets (MUTAG, PTC, PROTEINS, RDT-B, NCIl). These datasets vary widely in graph sizes and label space, providing comprehensive evaluation setting across small, medium, and large graphs with diverse class distributions.
Table 7: Dataset statistics: number of graphs, number of classes, and average number of nodes.
Dataset
MOLHIV
MOLBBBP
MOLTOX21
TOXCAST
Graphs
41,127
2,039
7,831
8,576
Classes
2
2
12
617
Nodes (avg.)
25.51
24.06
18.57
18.78
Table 8: Statistics of TU benchmark datasets.
IMDR-B
IMDB-M
MUTAG
PTC
PROTEINS
RDT-B
NCI
Graphs
1000
1500
188
344
1113
2000
4110
Dataset
# Classes
2
3
2
2
2
(odes(max)
136
89
28
109
620
3783
111
Nodes(avg.)
19.8
13.0
18.0
25.6
429.6
29.2
B IMPLEMENTATION DETAILS OF HISTOGRAPH
Algorithm outlines the forward pass of HISTOGRAPH. The input X E NRNxLLDD consists of node embeddings across GNN layers, for N nodes per graph (referred to as historical graph activations). We first project the input to common hidden dimension D using shared linear transformation. Sinusoidal positional encodings are added to encode the layer index. The final-layer embeddings serve as the query in attention mechanism, while all intermediate layers act key and value inputs. Attention scores are computed, averaged across nodes, and normalized over layers to yield a weighted aggregation of layer-wise features. A multi-head self-attention (MHSA) block is then applied over the aggregated node representations to capture spatial dependencies. Finally, a global average pooling operation over the node dimension produces the final graph-level representation Y IR
To stabilize training, we combined the output of HISTOGRAPII with a simple mean pooling baseline using learnable weighting factor a [0, 1]. Specifically, the final graph representation was computed as a convex combination of the output of our method and the mean of the final-layer node embeddings: Yinal
Y HiSTOGRAPH + (1 a) Y mean- We experimented both with fixed and learnable values of and found that incorporating the mean-pooling signal helps guide the optimization in early training stages.
C EXPERIMENTAL DETAILS
We implemented method using PyTorch (Paszee 2019) (offered under BSD-3 Clause license) and the Py ToTch Geometric library (Fey & Lenssen 2019) (offered under MIT license). All experiments NVIDIA L40, NVIDIA A100 and GeForce RTX 4090 GPUs. For logging, hyperpa- rameter tuning, and model selection, we used the Weights and Biases (W&B) framework (Biewald 2020).
In the subsection below, we provide details on the hyperparameter configurations used across our experiments.
16

---

Algorithm 1 HISTOGRAPII Forward Pass
Input: X RNxxxx
Output: Graph-level representation Y e RDD
X' <- Embrisi
D Linear projection to dimensions
X t PP
b Add sinusoidal positional encoding Query: last-layer embedding
Q <- WOX
K < W X, V
Key and Value: all layers
C QK
D. Dot-product attention logits
VB
< Average(c)
Average across nodes b Normalize over time
0 + Ey
H Et- a,X;
Layer-wise aggregation
Z - MHSA(H, H)
P Node-wise self-attention
return Y Average(Z) (Z)
b Average across nodes
C.I. HYPERPARAMETERS
The hyperparameters in our method include the batch size B, hidden dimension D, learning rate 1, and weight decay 7.. We also tune architectural and attention attention-specific components such as the number of attention heads H, of fully connected layers, inclusion of zero attention token, use of layer normalization, and skip connections. Attention dropout rates are controlled via the multi- head attention dropout Puba and attention mask dropout Pmask- We further include the use of learning rate schedule as a hyperparameter. Additionally, we consider different formulations for the attention coefficient parameterization Otype: including learnable, fixed, and gradient-constraines variants. Hyperparameters were selected via a combination of grid search and Bayesian optimization, using validation performance as the selection criterion. For baseline models, we consider the search space of their relevant hyperparameters.
D ADDITIONAL PROPERTIES OF HISTOGRAPH
Contribution of Node-wise Attention for Graph-Level Prediction. Let H = lh....., hN] E N be the cross-layer-poolle f F.RNX RND + R that is permutation invariant but non-uniform (e.g., depends on inter-node interactions). Then, standard mean pooling cannot approximate ʃ uulees it includes additional inter-node operations like node-wise attention.
node embeddings. Suppose the downstream task requires function
As a concrete example where the node-wise attention beneficial in our HISTOGRAPH, let us consider graph G (V, E) composed of two subgraphs connected by narrow bridge. Let G, = (Vz, Et) large graph G(n,p) p) with n >> 1, and let GR = (VR, ER) be a singleton graph containing single node un- The resulting structure is illustrated in Figure 5
Suppose the graph-level classification task depends solely on the features of the singleton node UR (c.g., label is determined by property encoded in UR). In this setting. naive mean pooling aggregates all node embeddings uniformly. As n increases, the contribution of Un to the pooled representation becomes increasingly marginal, leading its signal being dominated by the embeddings from the much larger subgraph Gz. This becomes especially problematic when there is distribution shift at test time, e.g., Gr, becomes larger or denser, which further suppresses the contribution of UR.
In contrast, a node-wise attention mechanism can learn to attend selectively to UR. regardless of the size of Gr., making it robust distributional changes. This demonstrates the contribution of node-wise attention in capturing non-unine unifunffomm importance of nodes in our HISTOGRAPH.
E PROOFS
E. HISTOGRAPH MITIGATES OVERSMOOTHING
Proof.
17

---

GL
GL
GR
GR
Figure 5: Barbell graph illustrating distribution shift: a singleton node (right) is connected to larger subgraph (left) whose size increases test time (blue) compared training (green), Node-wise attention helps preserve the importance of the singleton node despite the dominance of the larger subgraph.
Consider two nodes and v. Under the definition of HISTOGRAPII'S final embedding:
L-1 as
x x(!)
ha
(13)
We split the sum into layers before and after Lo:
Lo
1-1
hu ho = Σ
a4
x
x(!1
+
as x(() - x
(14)
1=0
(= Lo +1
By over-smoothing (Eq. 9 for all 1 > Lo:
|x x("1| O,
(15)
and hence the second sum is negligible. Therefore,
ha ho
on (x!)) -x(0)
(16)
Because initial node representations differ (a standard assumption for distinct nodes), there exists at least one layer < Lo for which
|x - ! + O.
(17)
Given that HISTOGRAPH employs learned dynamic attention, suppose ay + 0. Consequently:
hh
Oy (x(() -0(0x)
xx())
Σ ai (x(1) x(!)
(18)
0.
(19)
This directly contradicts the assumption that node embeddings become indistinguishable in the pooled representation. Thus, HISTOGRAPH mitigates over-smoothing by explicitly retaining discriminative early-layer representations.
F ADDITIONAL EXPERIMENTS
Table and Table 10 show the results of different methods two different settings of multiple graph pooling methods. Table II reports node classification accuracy on both heterophilic and homophilic datasets. We observe that method (HISTOGRAPH+ GCN) consistently outperforms standard GCN and Net across all datasets. The improvements are particularly pronounced on heterophilic graphs such Actor, Squirrel, and Chameleon, where method achieves gains of up to 12.3% over
18

---

Table 9: Comparison of graph classification accuracy (%) t on different datasets with HISTO-
GRAPH and existing benchmark graph classification methods on TU datasets. All methods use 5-layer GIN backbone for fair comparison. Top three results are marked First, Second, and Third.
Method / Dataset
IMDB-M
MUTAG
PTC
PROTHINS
RDT-B
NCTI
KERNEL
GK
Shervashidze al.
2009)
65.9_1.0
43.9
81.4
57.3
21.7
77.3
62.3
RW
Vishwanathan et a
2010)
79.2
57.9
74.2
WL
Shervashidze et al.
2011)
73.8_3.9
50.9
82.
60.0=0.5
74.7=0.5
82.2
DGK
Yanardag & Vishwanathan
2015
67.0_0.6
44.620.5
60.1
75.7
78.020.4
80.3
AWE
Ivanov Burnaev
2018)
74.5
51.5
87.9
87.942.5
GNN
ASAP Ranjan et
2020
77.6-2.1
24.5
91.6+3.3
72.4
93.1 4..
75.1
SOP Wang & J1 2023
78.5_2.8
54.623.6
95.324.4
75.0=4.3
80.1
91.7+2.7
84.5
GMT (Back ct al 2021
79.5
55.0
95.813.2
74.5
80.3
93.9
84.1
HAP
Liu et al.
2021
79.1-2.8
55.342.6
95.2128
75.2
79.9
92.212.5
81.3
PAS
Wei al.
2021
77.3-4.1
53.7=3.1
94.345.6
21.4
78.5
93.7+1.8
82.8+2.2
HaarPool Wang et al.
2020
79.3_3.4
53.8+3.0
90.0+3.6
73.1
80.4
93.6+1.1
78.640.5
DiftPool Ying et al.
2018)
73.9_3.6
50.7
94.8+4.8
68.345.9
76.2
91.842.1
76.641.3
GMN (Ahmadi |202 22020
76.6=4.5
54.2+2.7
95.714.0
76.344.3
29.5
93.5.0.7
82.4119
DKEP (Chen al.
2023
80.9
56.342.0
97.343.6
79.644.0
81.2+a.8
95.0+1.0
85.4
JKNet (Xu et al.
2018
54.5
93.043.5
72.5.2.0
78.0
91.542.0
82.0+1.5
HISTOGRAPH (Ours)
87.2+1.7
61.945.5
97.943.5
79.1
97.820.4
93.4
85.941.8
Table 10: Comparison of graph classification ROC-AUC (%) on different datasets between HISTO- GRAPH and existing baselines on OGB datasets. All methods use a 3-layer GCN backbone for fair comparison. The metric used ROC-AUC. The top three methods are marked by First, Second, and Third.
symholizes non-learnalee methods.
Method / Dataset
MOLHIV
MOLBBBP
MOLTOX21
TOXCAST
GCN+ Kipf& Welling
2016
76. 76.1881.226
65.67+1.86
60.63 75.04
GIN
Xu et al. 2019)
75.84
66.78+1.77
73.27
60.8320.40
HaarPool Wang
2020
74.69
66. 66.11
ASAP (Ranjan et al. 2020)
72.86
63.50
72.24
58.0941..0
TopKPaol (Gao & J1
2019
72.27
15.194
69.39 12.02
58.42.10.91
SortPool (Zhang ct al 2018
71.82+1.63
65.98
69.54
58.6941.71
JKNet (Xu al. 2018
74.99 1..60
65.62
65.98
SAGPool (Lee el al. 2019)
74.56
65.1641.03
71.10+1.06
19.88
Se12Set VVinyals el al. 2015
2..70
66.79+1.05
74.10+1.18
59.70.1.04
SAGPool(HI [Lee el al.
2019
1..4
63.94
69.81
58.91
EdgePool Diehhl 2019)
72.66+1.70
67.18+1.97
73.77+0.68
60.70+0.92
MinCutPooT BBanchh et al.
2020
75.37
65.97+1..1
75.11
62.48
StructPool (Yuan Ji 2020)
75.85
67.01+2..65
75.43
17.
SOPool (Wang & J1 2023
1..18
65.82.11.68
GMT (Back et al. 202T)
77.5611.25
68.31
77.30
65.44
HAP (L.u et al. 202T
75.71
66.01
PAS Wei
202T
77.68
66.97+1.21
DifiPool Ying
2018)
75.64
68,25440.96
74.88
62. 22.28
GMN (Ahmadi 2020)
21.25
67. 67.06+11.05
DKEPool Chen et al.
2023
78.65
69.73
HiSTOGRAPH (Ours)
77.81
72.02++1.46
77.49
66.35
GCN. On homophilic datasets like Cora, Citeseer, and Pubmed, we also observe consistent, albeit smaller, improvements.
To evaluate the ability of HISTOGRAPH to mitigate oversmoothing, we measure the feature distance across layers for standard GCN, both with and without HPSTOGRAPH. The results, presented in
19

---

Table 11: Node classification accuracy (mean + std) on heterophilic and homophilic datasets.
Dataset
GCN
JKNet
HISTOGRAPH+ GCN (Ours)
Actor
27.3 + 1.1
35.1 1,4
36.2 + 1.1
Squirrel
53.4 + 2.0
45.0 1.7
65.7 + 1.4
Chameleon
64.8 + 2.2
63.8
69.8 + 1.8
Cora
81.1 0.8
81.0 1.0
83.1 + 0.4
Citeseer
70.8 - 0.7
69.8 0.8
70.9 + 0.5
Pubmed
79.0 + 0.6
78.1 0.5
80.4 + 0.4
Table 12: Feature distance metrics across layers, showing the ability of HistoGraPi APH to mitigate oversmoothing. Compared to standard GCN, HISTOGRAPH yields more diverse node embeddings.
Layer
8
64
Final (pre-classifier)
GCN
2.634
2.385
1.703
1.703
GCN + HISTOGRAPII 3,710
3,403
2.888
5.000
Table 12 show that incorporating HISTOGRAAPH consistently leads to higher feature distances across all layers, with the most pronounced improvement observed in the pre-classifier layer expected due to the oversmoothing.
The results Tables 13 15
further demonstrate versatility and effectiveness of HISTO- GRAPH across different tasks and architectures. On the OGBL-COLLAB link prediction benchmark (Table 13 incorporating HISTOGRAPH as a readout function leads to consistent improvements over a standard GCN baseline. Similarly, in molecular property prediction tasks with GraphGPS backbones (Table 14.. HISTOGRAPE achieves substantial performance gains across multiple datasets, highlight- ing its ability to preserve and leverage historical information across layers. Finally, the ablation the number of historical layers (Table [5) shows that incorporating deeper historical context enhances predictive performance, with the best results obtained when more layers are retained. These findings underscore the robustness of HISTOGRAPI as a drop-in replacement for readout functions across diverse settings. Finally, we present an additional ablation in Table which examines the effect of different aggregation strategies across all layers mean aggregation, randomized attention, and HISTOGRAPH. Across datasets, HISTOGRAPH consistently achieves superior performance.
F.1 SCALABLE POST-PROCESSING WITH HISTOGRAPH
Table 17 indicates that all HISTOGRAPH variants consistently outperform the MeanPool baseline for every depth and dataset. In particular, FT, often matches or even exceeds the accuracy of full end-to-end tuning despite having far fewer trainable parameters. For example, at 5 layers it boosts IMDB-M from 54.0 to 67.3 %, IMDB-B accuracy from 76.0 % to 94.0 %, PROTEINS from 75.0 to 97.3 %, and PTC from 77.1 % to 85.7 %. As model depth grows, FT remains highly competitive: at 16 layers it achieves 64.7%.
We would like to note that while HISTOGRAPH mitigates over-smoothing by dynamically leveraging early-layer discriminative features, at extreme depths (e.g.. 64 layers) we face known optimiza- tion challenges in GNNs (Li et al. 2019 Chen al.) 2020 Arroyo et al. 2025). Nonetheless, HISTOGRAPH consistently outperforms baseline pooling methods, as shown in our experiments Cora, Citeseer, and Pubmed in Table demonstrating robustness model depth.
These findings demonstrate that caching intermediate representations and training a small auxiliary head enables scalable, modular adaptation of GNNs, obtaining strong performance across depths and domains without incurring the computational costs of full model training.
G SCALABILITY CONSIDERATIONS
The current design of HISTOGRAPH is best suited for small-to- small-to-medium-se medium--izee graphs, where the O(N2 D) node-wise attention and O(NT.D) activation storage remain tractable. Our benchmarks
20

---

Table 13: Link prediction results on the OGBL-COLLAB dataset. HISTOGRAPH is applied as drop-in replacement for the readout function with a GCN backbone, demonstrating consistent improvements over the baseline.
Model
Hits@50 (Test) t
@0 (Validation) t
Baseline (GCN)
0.4475 + 0.0107
0.5263 + 0.0115
GCN HISTOGRAPH
0.4533 + 0.0096
0.5314 + 0.0103
Table 14: Performance comparison of GraphGPS baselines with and without HISTOGRAPH multiple datasets. Integrating HISTOGRAPH consistently improves performance by preserving layer- wise historical context and enabling adaptive readout.
Method
PROTEINS
tox21
ToxCast
GPS + MeanPool
79.8 - 2.1
75.7 1 0.4
62.5 + 1.09
GPS + HISTOGRAPH
98.9 = 1.2
77.8 + 2.2
66.9 + 0.69
span molecular graphs (avg. ~0 nodes OGB), social network graphs (avg. ~200-2-000--0 430 nodes TUDatasets), citation networks (Cora, Citeseer, Pubmed), and the large-scale OGBL-COLLAB link prediction benchmark. For graphs with significantly more nodes, the quadratic node-wise attention and activation caching become bottlenecks. Several strategies can extend HISTOGRA APH to larger scales: (i) neighbor sampling (Hamilton al.) 2017) restrict the node set per mini-batch, (ii) sparse attention mechanisms (Zaheer et al. (0200) that replace the dense N x N attention with O(NvN) or O(N log N) approximations, and (iii) hierarchical coarsening to reduce N before applying node-wise attention. We leave the integration of these techniques with HISTOGRAPH to future work.
H INTERPRETABILITY OF LEARNED ATTENTION WEIGHTS
Figure (left) reveals several interpretable patterns in the learned layer-wise attention weights. Across training regimes, the model allocates substantial weight to early layers (particularly layers 0-5), where node embeddings are most discriminative prior to over-smoothing, and to the final layer, which carries the most refined global context. The attention profile is neither uniform nor trivially concentrated a single layer; instead, it forms a task-adapted weighting that balances local and global information. The embedding evolution plot (right) corroborates this: the normed difference between final-layer and intermediate representations grows with depth, confirming that early layers carry distinct information worth attending to. These visualizations demonstrate that HISTOGRAPH learns meaningful, non-trivial layer weightings that are consistent with the multi-scale information structure of deep GNNs.
I DISCUSSION OF PROTEINS PERFORMANCE
The large gain on PROTEINS (+16.6% over the next-best baseline) merits detailed discussion. The ablation study in Table Disolatess the contribution of each HISTOGRAPH component: removing signed normalization drops accuracy to 74.45%. removing layer-wise attention to 78.61 78.61% and removing node-wise attention to 80.78% confirming that all three components are necessary. Table 16 further shows that uniform averaging (70.08%) and randomized attention (80.05%) fall far short, indicating the gain is driven by learned, signed layer weighting rather than any implementation artifact. We attribute the particularly strong performance on PROTEINS to the fact that protein graphs exhibit rich multi-scale structural information across GNN depths, which HISTOGRAPH trajectory aware readout is well- eositiontd to exploit. Protein classification benefits from combining local motifs (secondary structure elements captured by early GNN layers) with global fold topology (captured by deeper layers), and HISTOGRAPH'S layer-wise attention naturally learns weight both scales.
21

---

Table 15: Performance HISTOGRAPH with different numbers of historical layers on PTC.
#Historical Layers
PTC (%)
5
79.1 + 4.8
3
75.6 + 3.7
73.8 + 4.3
Table 16: Comparison between different aggregation options of all layers: mean over all layers, randomized attention, and HISTOGRAPII performance across datasets.
Dataset
Mean over all layers
Randomized attention
HISTOGRAPH
INDB-MULTI
54.73 + 2.3
54.73 + 4.3
61.9 + 5,5
IMDB-BINARY
75.5 + 2.2
76.6 + 1.4
87.2 + 1.7
PROTBINS
70.08 5,8
80.05 + 3.2
97.8 + 0.4
PTC
73.24 + 3.2
73.56 + 2.56
79.1 + 4.8
J INFERENCE TIME ANALYSIS
Table 18 reports average inference time (in milliseconds) for GCN backbones with 3 and 32 layers MOLHIV and TOXCAST. Since inference involves no gradient computation, the FT and End-to-Enu modes yield identical runtimes. At 32 layers MOLHIV, HISTOGRAPH is ~4.88x faster than GMT (3.174 ms vs. 15.158 ms) while adding only modest overhead over MeanPool (3.174ml ms vs. 2.130 ms). Similar trends hold TOXCAST, where HISTOGRAPII is ~3.7x faster than GMT at 32 layers. The overhead relative to MeanPool reflects the cost of the HISTOGRAPH head (O(N + D)), which remains small for the molecular-scale graphs evaluated here.
22

---

Table 17: Graph classification accuracy (%) across varying model depths, comparing methods over multiple datasets and approaches. The top three methods for each setting are marked by First, Second, and Third.
Datasel
Method
Number of Layers
5
16
32
64
McanPool
54.0
54.7
52.0
52.0
FT
67.3
64.7
57.3
66.0
IMDB-M
58.0
62.7
58.0
57.3
End-to-Eind
61.9
58.7
58.7
54.7
McanPool
76.0
76.0
76.0
71.0
FT
94.0
84.0
81.0
78.0
IMDB-B
Fall
81.0
81.0
81.0
End-to-Enn
87.2
79.0
79.0
72.0
McanPool
75.0
75.0
75.0
75.9
FT
97.3
77.7
75.9
77.8
PROTEINS
Fall FT
97.3
84.8
80.4
97.3
End-to-End
97.8
78.6
84.8
94.6
MeanPool
77.1
68.6
71.4
68.5
FT
85.7
80.0
71.5
71.4
PTC
Fall FT
85.7
97.1
82.9
80.0
End-to-End
79.1
88.6
85.7
80.0
Table 18: Average inference time (ms) per epoch for GCN backbones with and 32 layers on MOLHIV and TOXCAST.
Dataset
Layers
GMT
HISTOGRAPH (E2E) FT)
McanPool
1.945
0.848
0.387
MOLHIV
32
15.158
3.174
2.130
0.535
0.764 2.859
0.392
TOXCAST
32
10.678
1.773
23


Reviews:
[{"review_id": "OWmxRBYXIa", "reviewer": "Reviewer_Pj7q", "summary": "This paper proposes HISTOGRAPH, a two-stage attention-based pooling framework for Graph Neural Networks (GNNs) that leverages intermediate activations (“historical graph activations”) from all layers rather than only the final layer. The approach first applies layer-wise attention to capture the evolution of node embeddings across depths, followed by node-wise attention to model spatial dependencies. The method can be integrated end-to-end with a backbone GNN or applied as a lightweight post-processing head on frozen models. Experimental results on TU and OGB benchmarks, as well as node classification tasks, demonstrate improved performance and robustness to over-smoothing in deep architectures.", "questions": "see above", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Novel perspective: The paper introduces a clear and well-motivated idea of learning from the historical trajectory of node activations, addressing the common limitation of relying solely on the last GNN layer.\n\n2. Comprehensive experiments: Evaluations across multiple datasets (TU, OGB, node classification, and link prediction) with both GIN and GCN backbones show consistent improvements.\n\n3. Well-written and well-positioned: The paper situates HISTOGRAPH clearly within prior works on pooling, residual connections, and over-smoothing mitigation", "weaknesses": "1. Limited interpretability of learned attention weights: While attention is used layer-wise and node-wise, the paper could benefit from deeper analysis of what the model learns—e.g., visualization of layer weights across datasets.\n2. The attention mechanism itself is widely adopted and not novel. However, the paper should further clarify why the proposed method achieves such notable performance gains. A deeper analytical discussion and illustrative case studies would substantially strengthen the contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Et7MbBIckO", "reviewer": "Reviewer_iaN5", "summary": "The paper introduces an architectural modification for graph neural networks (GNNs) consisting in (1) an intra-node attention mechanism that aggregates the representations for each node at different layers (i.e., different message passing iterations), and (2) a global inter-node self attention layer (aggregating information across all nodes). \nThe motivation from this architecture comes from the fact that current methods ignore the history of graph activations across layers, even though this may include some useful information.\nThe experimental evaluation compares the proposed method on standard node and graph classification benchmarks, both when training from scratch and when applying the method to a pre-trained model, and compares against a vast number of competitors. The proposed method shows high performance and an ablation studies explores different attention modifications.", "questions": "- The computational complexity analysis is a bit confusing. First it is mentioned that the proposed method improves over a naive \"joint node-layer attention\" which has complexity O(LN^2D) by instead having a method which is O(NLD + N^2D) but then it is (correctly) mentioned that the complexity is dominated by N^2D, which means that there is no advantage. So it seems that the paragraph from line 216 to 220 does not really have much sense. Could you please clarify the point of this paragraph?\n- The same happens in the \"Frozen Backbone Efficiency\" paragraph: as the complexity is dominated by N^2D there is no advantage (I do not doubt that in practice it can have a difference in runtime, but in terms of computational complexity there is no difference). Could you clarify what is the advantage that is mentioned in the paper?\n- What are the hyperparameters for the baselines and how where they selected? These details should be included in the paper\n- It is mentioned that the method can overcome oversmoothing, but global self-attention actually goes against this. Could you elaborate on why global self-attention would not lead to oversmoothing?\n- On PROTEINS the proposed method reaches 97% (almost perfect), while all other methods stop at 80%. This difference is quite striking and should be analyzed. Could the authors comment on this? \n- The runtime analysis shows training time, but I think inference is actually much more important as training only happens once. Could you include some number for inference times? Some plots showing how runtime and memory scale as a function of N and L would be great.\n\nMinor comments:\n- There are some imprecisions in the text, specially in the math formalism:\n\t- lines 166 and 170 define X in different ways\n\t- in line 183 for computing X^tilde the sizes do not match (I understand there is an implicit broadcasting, but it should be formalized better)\n\t- in Section 4 the notation for node vectors is not introduced\n- It would be interesting to see an analysis of the attention maps to understand which layers are receiving the most attention", "limitations": "", "rating": 2, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- It is clear that the authors have spent a lot of effort in the experimental section as they compare against a large number of baselines and consider a large number of datasets.\n- The proposed method can be easily included into existing architectures (at the cost of some training for the new parameters).", "weaknesses": "- Global self-attention is quadratic in the number of nodes, which makes the method impractical for large graphs.\n- Caching in memory the activations at all layers for all nodes can become prohibitively expensive. Together with the above, this makes the proposed method very impractical for large graphs.\n- Section 4 is not very convincing as the arguments are too general. Regarding oversmoothing, Proposition 1 is obvious, and in practice different nodes might perform better with different alphas (which however is not allowed). Furthermore applying global self-attention is actually promoting smoothing. Regarding the trajectory filter, the argument can be made for any attention mechanism, and also it is hard argue whether models actually learn to use this information this way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JvxRNcD45q", "reviewer": "Reviewer_z6Gq", "summary": "This paper proposes a novel and effective GNN architecture, HISTOGRAPH, which mitigates the over-smoothing problem by explicitly modeling and leveraging historical node representations.", "questions": "See the weaknesses above.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The motivation is clear; the authors propose leveraging historical representations to mitigate over-smoothing, which is reasonable and well-justified.\n2. The experiments are comprehensive, thoroughly validating the effectiveness of their method across various tasks.", "weaknesses": "1. Lacks comparison with some more recent baselines [1].\n2. No experimental comparisons were conducted on larger graphs, such as those in the OGB [2] suite. How does the time efficiency compare to the baseline when the graph size increases?\n3. How are the historical representations specifically utilized? What are the theoretical advantages of the gating mechanism?\n4. Lacks a theoretical analysis of the method's effectiveness.\n\n[1] Wang Y, Liu S, Zheng T, et al. Unveiling global interactive patterns across graphs: Towards interpretable graph neural networks[C]//Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024: 3277-3288.\n\n[2] Hu W, Fey M, Zitnik M, et al. Open graph benchmark: Datasets for machine learning on graphs[J]. Advances in neural information processing systems, 2020, 33: 22118-22133.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gedlR5dpDI", "reviewer": "Reviewer_rAFQ", "summary": "HISTOGRAPH is a graph pooling method that leverages historical activations from all GNN layers rather than just the final layer. The method uses a two-stage attention mechanism: (1) layer-wise attention that aggregates node representations across all layers using the final layer as a query, and (2) node-wise self-attention that models spatial interactions between nodes. This approach aims to mitigate over-smoothing in deep GNNs and capture multi-scale graph features.", "questions": "* The method assumes all GNN layers produce embeddings of the same dimension Din. How would you handle architectures where layer dimensions vary, which is common in some GNN designs?\n* Beyond the over-smoothing mitigation proof, can you provide any theoretical guarantees about the expressiveness of HISTOGRAPH compared to standard pooling methods?\n* How critical are the sinusoidal positional encodings for layer positions? Have you tried other encoding schemes or learning the positional embeddings?\n* How sensitive is the method to hyperparameters, particularly the hidden dimension D and the number of attention heads?\n* Have you tested HISTOGRAPH on industrial-scale graphs (millions of nodes)? What are the practical limitations you've encountered?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The method can be used both for end-to-end training and as a post-processing step on frozen pretrained GNNs, making it practical for different scenarios.\n* Extensive experiments across graph classification, node classification, and link prediction tasks demonstrate the method's generalizability.\n* Strong improvement in benchmark results for the proteins dataset (15%).", "weaknesses": "* While the overall idea is novel, the individual components (layer-wise attention, node-wise attention) are standard techniques. The main contribution is their combination for this specific purpose.\n* Storing all intermediate activations (N×L×D) could be memory-intensive for very large graphs or deep networks.\n* Tested datasets are not of large nature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)