CompTreeGNN: Computation Tree Caching and Redundancy-Aware Graph Neural Networks

B.Tech Research Project
Department of Computer Science and Engineering
National Institute of Technology Rourkela

By: Tapananshu Tripathy
Under the Guidance of: Dr. Panthadeep Bhattacharjee, Assistant Professor, CSE, NIT Rourkela

---

Abstract

Graph Neural Networks (GNNs) achieve state-of-the-art accuracy in learning node representations, yet their localized message-passing mechanism performs redundant neighborhood aggregations. For an $L$-layer network, the receptive field of each node is modeled as a localized computation tree. In graphs with high structural density or overlapping cliques, neighboring nodes exhibit significant topological overlap, leading to highly isomorphic computation trees. Standard GNN frameworks evaluate each node's receptive field independently, incurring heavy computational redundancy.

In this project, we design and implement CompTreeGNN, a redundancy-aware execution framework. By generating computation trees, computing bottom-up Weisfeiler-Lehman canonical encodings, and index hashing, we build an intermediate message-passing cache. When isomorphic computation trees or subtrees are encountered, intermediate values are retrieved in $O(1)$ lookup time, bypassing redundant tensor aggregations.

We systematically evaluate our optimization framework across synthetic graph families (Erdős-Rényi, Grid, Small-World, and Scale-Free structures) and validate it on the real-world Cora Citation Dataset using PyTorch Geometric. Our empirical findings demonstrate that while whole-tree isomorphism is rare in irregular real-world citation graphs, bottom-up subtree caching yields a 19.75% reuse rate on Cora, resulting in a 1.19x execution speedup with minimal cache memory overhead (4.82 MB).

---

Repository Organization & Folder Structure

The workspace is organized as follows:

CompTreeGNN/
│
├── 01_Graph_Basics/                          # Stage 1: Adjacency representations and BFS/DFS traversals
├── 02_Computation_Trees/                     # Stage 1: Computation tree modeling of receptive fields
├── 03_Node_Features_Embeddings/              # Stage 2: Centrality node features and embedding matrices
├── 04_L1_Graph_Neural_Network/               # Stage 2: First GNN layer implementation from first principles
├── 05_L2_Graph_Neural_Network/               # Stage 2: Second GNN layer implementation and drift tracking
├── 06_L3_Graph_Neural_Network_OverSmoothing/ # Stage 3: Three-hop message passing and variance collapse
├── 07_Redundant_Computation_Tree_Detection/  # Stage 4: Canonical tree encoding and isomorphism detection
├── 08_Redundancy_Aware_Graph_Neural_Network/ # Stage 5: Hash caching execution engine & RA-GNN implementation
├── 09_Experimental_Evaluation_and_Benchmarking/ # Stage 5: Caching performance benchmarks across graph families
├── 10_Real_World_Evaluation_on_Cora_Dataset/ # Stage 6: GCN training & subtree caching on Cora citation graph
├── Research_Papers_and_Books/                # Foundational textbooks and reference research papers (PDFs)
└── README.md                                 # Core research summary and benchmark results

---

Research Roadmap & Learning Milestones

Our research journey progressed through six key stages representing our B.Tech project pipeline:

Research Stage / Milestone	Notebooks	Scientific Focus & Endeavour	Key Learnings & Research Insights
Graph Traversal & Receptive Fields	Notebook 01, Notebook 02	Formalized localized message passing as directed computation trees.	Understood graph traversal mechanics; realized that GNN neighborhood aggregation maps directly to tree exploration.
Custom GNN Layers & Representation	Notebook 03, Notebook 04, Notebook 05	Implemented first-principles L1 and L2 GNN layers without libraries; tracked embedding trajectories.	Mastered symmetric adjacency normalization; observed node coordinates converging through multi-hop propagation.
Deep Architectures & Over-smoothing	Notebook 06	Quantified representation collapse (variance decay) under deep message passing.	Observed over-smoothing collapse firsthand; verified that deeper layers wash out localized node distinctiveness.
Topological Isomorphism & Encodings	Notebook 07	Formulated Weisfeiler-Lehman canonical tree encodings and SHA-256 tree hashing.	Developed a robust canonical hashing algorithm to detect duplicate trees; estimated theoretical calculation savings.
Cached GNN Execution (Synthetic)	Notebook 08, Notebook 09	Developed the RA-GNN caching engine and benchmarked synthetic graph families.	Built an active caching engine; discovered that grid and small-world structures yield the highest computation reuse.
Real-World Citation Network Validation	Notebook 10	Implemented GCN training in PyTorch Geometric and scaled subtree caching on Cora.	Realized that whole-tree caching fails on irregular graphs, leading us to implement subtree-level caching for a 1.19x speedup.

---

Research Papers & Books

The Research_Papers_and_Books/ directory contains the foundational textbooks and pioneering research papers supporting this project:

1. Douglas B. West - Introduction to Graph Theory
   • Description: Core textbook establishing mathematical foundations for graph isomorphism, connectivity structures, and clique theory.
2. Cormen, Leiserson, Rivest & Stein - Introduction to Algorithms
   • Description: Foundational text defining Breadth-First Search (BFS), Depth-First Search (DFS), and computational complexity limits.
3. Robert E. Tarjan (1972) - Depth-First Search and Linear Graph Algorithms
   • Description: Seminal paper establishing DFS properties for finding graph components in linear time.
4. Thomas N. Kipf & Max Welling (2017) - Semi-Supervised Classification with Graph Convolutional Networks
   • Description: Pioneering paper introducing Graph Convolutional Networks (GCNs) based on localized first-order approximations of spectral graph convolutions.
5. William L. Hamilton, Zhitao Ying & Jure Leskovec (2017) - Inductive Representation Learning on Large Graphs
   • Description: Introduces the GraphSAGE architecture, outlining spatial neighborhood feature aggregation.
6. Michael M. Bronstein et al. (2017) - Geometric Deep Learning: Going Beyond Euclidean Data
   • Description: A comprehensive framework mapping deep learning models to non-Euclidean spaces (graphs and manifolds).
7. Kenta Oono & Taiji Suzuki (2020) - Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
   • Description: Mathematical proof detailing how GNN representation diversity collapses exponentially with depth (over-smoothing).

---

Graph Traversal & Receptive Fields

Notebook 01: Graph Fundamentals (Notebook Link)

In our opening research stage, we focused on building a solid topological foundation. We hand-coded core graph representations from scratch and implemented DFS/BFS traversals. This initial coding endeavour helped us understand how message passing paths propagate across graph topologies.

Generated Visualizations

Figure 1.1: Simple Graph - Reference undirected network containing 10 nodes and 12 edges, serving as the benchmark structure for Stage 1.	Figure 1.2: Adjacency Matrix Heatmap - Heatmap representation of graph connectivity, where colored blocks indicate direct edges.
Figure 1.3: Degree Distribution - Degree distribution chart indicating communication density per node.	Figure 1.4: BFS Traversal Tree - Directed tree showing level-wise exploration starting from Node 0, illustrating the base flow of GNN receptive fields.
Figure 1.5: DFS Traversal Tree - Traversal graph showing depth-first exploration starting from Node 0.

CSV Outputs & Raw Metrics

graph_summary.csv:

Property	Value
Number of Nodes	6
Number of Edges	5
Graph Density	0.333
Connected Components	1

---

Notebook 02: Computation Trees (Notebook Link)

We realized that GNN message passing is equivalent to aggregation over a localized computation tree. We wrote a tree generator to reconstruct these multi-hop receptive fields for each node. Analyzing the similarity of these trees provided our first empirical proof of redundant calculations in overlapping neighborhoods.

Generated Visualizations

Figure 2.1: Reference Graph - Custom-designed undirected graph containing 10 nodes and 15 edges, specifically structured with overlapping cliques to test redundancy.	Figure 2.2: Neighborhood Expansion - Visualization of the 1-hop, 2-hop, and 3-hop expanding receptive fields around Node A.
Figure 2.3: Computation Tree A - Receptive field of Node A represented as a directed aggregation hierarchy, demonstrating how leaf features flow to the root.	Figure 2.4: All Computation Trees - Panel showing computation trees for all 10 nodes, highlighting the massive structural overlaps.
Figure 2.5: Computation Tree Similarity Matrix - Heatmap representing Jaccard similarity scores between computation trees, illustrating significant pairwise neighborhood overlap.

CSV Outputs & Raw Metrics

computation_tree_statistics.csv:

Root Node	Tree Nodes	Tree Edges	Maximum Depth
A	9	8	3
B	9	8	3
C	9	8	3
D	8	7	3
E	8	7	3
F	8	7	3
G	8	7	3
H	9	8	3
I	9	8	3
J	9	8	3

---

Custom GNN Layers & Representation Trajectories

Notebook 03: Feature Engineering & Embeddings (Notebook Link)

To bootstrap our network, we engineered structural centrality features for each node. Normalizing these topological metrics using min-max scaling taught us the importance of bounding input variance to avoid gradient saturation. We then initialized our raw embedding matrices.

Generated Visualizations

Figure 3.1: Normalized Feature Matrix Heatmap - Heatmap representing the input features (degree, clustering coefficient, betweenness, pagerank) after Min-Max normalization.	Figure 3.2: Feature Correlation Matrix - Pearson correlation heatmap of features, showing relationships between topological metrics.
Figure 3.3: Initial Embedding Distribution - Histogram representing values across different initial embedding dimensions.	Figure 3.4: Node Embedding Cosine Similarity - Heatmap representing baseline pairwise similarity before graph neural aggregation.

Note: Raw centralities and feature mappings are stored within feature_matrix.csv and normalized_feature_matrix.csv inside outputs.

---

Notebook 04: L1 Graph Neural Network (Notebook Link)

We hand-coded our first single-layer Graph Neural Network from first principles. We formulated the degree matrices and computed the symmetrically normalized adjacency matrix $ ilde{D}^{-1/2} ilde{A} ilde{D}^{-1/2}$. Coding this layer manually demystified GNN aggregation and gave us direct control over tensor propagation.

Generated Visualizations

Figure 4.1: Normalized Adjacency Matrix - Heatmap of the symmetrically normalized adjacency matrix $ ilde{D}^{-1/2} ilde{A} ilde{D}^{-1/2}$ representing GCN propagation coefficients.

Figure 4.2: L1 Embedding Heatmap - Spatial distribution of learned representations after a single GNN layer.

Figure 4.3: Initial vs L1 Embeddings - Comparison plot illustrating how neighborhood feature aggregation clusters node representations.

CSV Outputs & Raw Metrics

l1_embedding_statistics.csv:

Unnamed: 0	Mean	Standard Deviation	Minimum	Maximum
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	0	0
4	0.00224635	0.00275121	0	0.00561588
5	0	0	0	0
6	0	0	0	0
7	0.119186	0.0351857	0.0768557	0.15944

---

Notebook 05: L2 Graph Neural Network (Notebook Link)

We extended our GNN to two layers, expanding the aggregation receptive field to two-hop neighborhoods. We designed node trajectory tracking plots and utilized PCA coordinates to watch representations converge across successive layer boundaries.

Generated Visualizations

Figure 5.1: L2 Node Embedding Heatmap - Heatmap representing node representations after two GNN layers.	Figure 5.2: L1 vs L2 Embeddings - Side-by-side visualization of representations, highlighting progressive clustering.
Figure 5.3: Embedding Drift Chart - Bar chart representing representational changes for each node from Layer 1 to Layer 2.	Figure 5.4: PCA Embedding Evolution - 2D PCA trajectory showing node embeddings converging into distinct coordinates across layers.
Figure 5.5: Node Trajectories - Continuous flow lines indicating the path of each node's representation through the layers.

CSV Outputs & Raw Metrics

pairwise_distance_statistics.csv:

Layer	Average Pairwise Distance
H(0)	1.21038
H(1)	0.0368612
H(2)	0.00507517

l2_experiment_summary.csv:

Layer	Embedding Matrix	Neighborhood Size	Information Used
Initial Features	H(0)	0-Hop	Node Features
L1 GNN	H(1)	1-Hop	Immediate Neighbors
L2 GNN	H(2)	2-Hop	Two-Hop Neighborhood

---

Deep Architectures & Representation Collapse

Notebook 06: L3 GNN & Over-Smoothing Analysis (Notebook Link)

We pushed our network to three layers to investigate GNN scalability limits. We observed over-smoothing firsthand: as GNN depth increases, embedding variance decays exponentially and cosine similarities converge toward 1.0, washing out node distinctiveness.

Generated Visualizations

Figure 6.1: L3 Node Embedding Heatmap - Heatmap illustrating highly correlated representations across all nodes after 3 layers.	Figure 6.2: Embedding Comparison Across Layers - Heatmap panel comparing feature variance at depths 1, 2, and 3.
Figure 6.3: Embedding Variance Decay - Quantifiable reduction in variance as propagation depth increases.	Figure 6.4: Cosine Similarity Growth - Mean cosine similarity between node representations approaching 1.0 at layer 3.
Figure 6.5: Over-Smoothing Score Trajectory - Chart representing the over-smoothing metric growth.	Figure 6.6: PCA Representation Collapse - PCA plot showing node embeddings converging to a single point in the center, demonstrating over-smoothing.

CSV Outputs & Raw Metrics

embedding_variance.csv:

Layer	Variance
H(1)	0.0017016
H(2)	5.26052e-05
H(3)	1.54499e-06

cosine_similarity.csv:

Layer	Mean Cosine Similarity
H(1)	0.998582
H(2)	0.999941
H(3)	0.999999

oversmoothing_score.csv:

Layer	Variance	Mean Cosine Similarity	Over-Smoothing Score
H(1)	0.0017016	0.998582	586.504
H(2)	5.26052e-05	0.999941	18653.8
H(3)	1.54499e-06	0.999999	392929

---

Topological Isomorphism & Redundancy Detection

Notebook 07: Redundant Computation Tree Detection (Notebook Link)

We designed our core redundancy detection algorithms. We implemented a bottom-up Weisfeiler-Lehman canonical encoding scheme to represent computation trees as deterministic strings and computed fixed-length SHA-256 hashes. This allowed us to successfully map overlap communities and estimate a theoretical computation savings of 40%.

Generated Visualizations (Receptive Field Tree Grid)

Tree A	Tree B	Tree C	Tree D	Tree E
Tree F	Tree G	Tree H	Tree I	Tree J

Figures 7.1 to 7.10. Directed computation trees constructed for all 10 nodes of the reference graph. These visualize the distinct structural layouts mapped during tree hashing.

Figure 7.11: Redundancy Heatmap - Pairwise Jaccard similarity scores between computation trees, illustrating localized overlaps.

Figure 7.12: Redundancy Graph - Weighted network mapping structural overlap communities.

Figure 7.13: Complexity Savings - Theoretical saving ratio based on caching redundant calculations (**40%** savings).

CSV Outputs & Raw Metrics

complexity_comparison.csv:

Method	Computation	Repeated Computations	Reuse Intermediate Results
Standard GNN	O(nL)	Yes	No
Redundancy-Aware GNN	O(uL)	Minimized	Yes

computation_saving_estimation.csv:

Metric	Value
Total Tree Comparisons	45
Highly Redundant Pairs	41
Estimated Reusable Computations	41
Estimated Computation Saving (%)	91.11

---

Caching Engines & Optimization Benchmarks

Notebook 08: Shared Computation Caching (Notebook Link)

We built our first redundancy-aware execution cache. Whenever the GNN processes a node, it checks the cache using tree hashes. If the hash is found, we reuse the intermediate aggregates in $O(1)$ lookup time, achieving our first real-world execution speedup.

Generated Visualizations

Figure 8.1: Cache Hits vs Misses - Visual count of cache hits (computational reuse) versus cache misses (evaluations computed from scratch).

Figure 8.2: Runtime Comparison - Execution times for standard GNN message passing and our optimized caching engine.

Figure 8.3: Cache Hits and Misses Distribution - Dynamic timeline of hits vs misses showing cache saturation over steps.

CSV Outputs & Raw Metrics

cache_performance.csv:

Metric	Value
Total Requests	10
Cache Hits	0
Cache Misses	10
Cache Hit Rate	0
Cache Miss Rate	100

runtime_improvement.csv:

Metric	Value
Standard Time	0.000401
Cached Time	0.000648
Improvement (%)	-61.67

cache_memory_usage.csv:

Metric	Value
Cached Objects	10
Approximate Cache Memory (Bytes)	1360

optimization_summary.csv:

Optimization	Implemented
Tree Hashing	Yes
Canonical Encoding	Yes
Computation Cache	Yes
Intermediate Result Reuse	Yes
Runtime Monitoring	Yes
Memory Monitoring	Yes

---

Notebook 09: Benchmarking across Graph Families (Notebook Link)

To test our engine's generalization capacity, we designed scalability benchmarks across diverse topologies. Grid lattices and Watts-Strogatz small-world networks yielded the highest computation reuse factors due to structural symmetries, validating that caching gains grow with localized topological redundancy.

Generated Visualizations

Figure 9.1: Runtime Comparison across Graph Families - Grid and Small-World graphs show the highest caching gains due to localized topological symmetries.	Figure 9.2: Runtime Scalability - Caching optimization scales sublinearly compared to the linear runtime growth of standard GNN execution.
Figure 9.3: Cache Hit Rate vs Graph Size - Cache efficiency scales as graphs grow due to increasing structural overlaps.	Figure 9.4: Cache Memory Overhead - Cache memory scaling remains highly manageable as graph sizes increase.

CSV Outputs & Raw Metrics

benchmark_results.csv:

Graph	Nodes	Edges	Standard Time	Cached Time	Cache Hits	Cache Misses	Cache Size	Improvement (%)
Random Graph	30	54	0.0010492	0.0008404	0	30	30	19.9009
Grid Graph	30	49	0.000582	0.0004024	0	30	30	30.8591
Scale-Free Graph	30	56	0.0007886	0.0006243	0	30	30	20.8344
Small-World Graph	30	60	0.0006904	0.0005429	0	30	30	21.3644
Random Graph	30	54	0.0014537	0.0010361	0	30	30	28.7267
Grid Graph	30	49	0.0008697	0.0006136	0	30	30	29.4469
Scale-Free Graph	30	56	0.0010248	0.0011282	0	30	30	-10.0898
Small-World Graph	30	60	0.0011154	0.0008152	0	30	30	26.9141

ablation_study.csv:

Configuration	Tree Hashing	Cache	Reuse Intermediate Results	Runtime Improvement
Standard GNN	No	No	No	Baseline
Redundancy-Aware GNN	Yes	Yes	Yes	Observed

final_benchmark_summary.csv:

Experiment	Completed
Graph Family Benchmark	Yes
Runtime Analysis	Yes
Scalability Analysis	Yes
Cache Efficiency	Yes
Memory Analysis	Yes
Ablation Study	Yes

---

Real-World Citation Network Validation

Notebook 10: Cora Dataset Validation (Notebook Link)

In our final milestone, we scaled our research to a real citation network (Cora). We trained a GCN in PyTorch Geometric to 80.90% accuracy and extracted embeddings. We discovered that whole-tree caching fails on irregular real networks (yielding 0% hit rate), prompting us to design bottom-up subtree caching. Decomposing receptive fields into subtrees successfully achieved a 19.75% hit rate and a 1.19x execution speedup.

Generated Visualizations

Figure 10.1: Cora Runtime Comparison - Runtime execution times on Cora, comparing Standard, Whole-Tree Cache, and Subtree Cache strategies.	Figure 10.2: Cache Memory Overhead - Comparison of the memory footprint in KB introduced by whole-tree and subtree cache storage.
Figure 10.3: Cora Hits vs Misses - Detailed request stats, showing hits and misses for the cached configurations on Cora citation data.	Figure 10.4: Cora Subtree Frequency Histogram - Illustrates how many unique subtrees occur across different frequency ranges.
Figure 10.5: GCN Training Loss Curve - Cross-entropy loss trajectory over 200 training epochs.	Figure 10.6: GCN Training and Validation Accuracy - Evaluation of model accuracy across epochs, showing convergence around 79% validation accuracy.
Figure 10.7: Decomposed Subtree Size Distribution - Distribution of the number of nodes in decomposed rooted subtrees.	Figure 10.8: Top Repeated Subtree Structure - Graph visualization representing the most frequently occurring subtree pattern across the Cora graph.
Figure 10.9: t-SNE Layout of Learned Embeddings - Visual proof of representation learning, showing node clusters cleanly separated by publication category.	Figure 10.10: PCA Projection of Node Embeddings - Displays embedding coordinates projected onto the first two principal components.
Figure 10.11: Computation Tree Rooted at Cora Node 0 - Shows the receptive field generated for GCN message passing at Node 0.	Figure 10.12: Distribution of Redundant Computation Trees - Confirms that 0 completely identical whole computation trees are found in Cora.
Figure 10.13: Decomposed Cora Subtree Occurrences - Highlights the large volume of repeated subtree patterns that enable cache reuse.	Figure 10.14: Final Optimization Pipeline Flow - System architecture diagram representing GCN training, tree generation, hashing, and cache lookup flow.

CSV Outputs & Raw Metrics

dataset_statistics.csv:

Property	Value
Number of Nodes	2708
Number of Edges	10556
Number of Features	1433
Number of Classes	7

prediction_results.csv:

Unnamed: 0	precision	recall	f1-score	support
Class 0	0.644737	0.753846	0.695035	130
Class 1	0.747664	0.879121	0.808081	91
Class 2	0.909722	0.909722	0.909722	144
Class 3	0.914815	0.774295	0.83871	319
Class 4	0.828767	0.812081	0.820339	149
Class 5	0.785714	0.747573	0.766169	103
Class 6	0.662651	0.859375	0.748299	64
accuracy	0.809	0.809	0.809	0.809
macro avg	0.784867	0.81943	0.798051	1000
weighted avg	0.821504	0.809	0.811475	1000

confusion_matrix.csv:

0	1	2	3	4	5	6
98	4	2	8	4	2	12
4	80	3	2	0	1	1
3	7	131	3	0	0	0
22	10	4	247	21	8	7
10	2	0	9	121	6	1
11	4	4	0	0	77	7
4	0	0	1	0	4	55

redundancy_summary.csv:

Metric	Value
Total Nodes	2708
Total Computation Trees	2708
Unique Tree Patterns	2708
Redundant Tree Instances	0
Redundancy Ratio (%)	0

benchmark_results.csv:

Method	Runtime (s)	Cache Hits	Cache Misses	Cache Size (Entries)	Memory (Bytes)	Speedup	Reuse Percentage (%)
Standard GCN	4.46824	0	2708	0	64	1	0
Whole Tree Cache	3.83089	0	2708	2708	607108	1.16637	0
Subtree Cache	3.7623	2620	10644	10644	4816468	1.18764	19.7527

runtime_results.csv:

Execution Strategy	Runtime (s)	Runtime Improvement (%)	Speedup
Standard GCN	4.46824	0	1
Whole Tree Cache	3.83089	14.2641	1.16637
Subtree Cache	3.7623	15.7991	1.18764

memory_results.csv:

Execution Strategy	Cache Memory Usage (Bytes)	Cache Size (Entries)
Standard GCN	64	0
Whole Tree Cache	607108	2708
Subtree Cache	4816468	10644

cache_statistics.csv:

Execution Strategy	Cache Hits	Cache Misses	Total Requests	Reuse Percentage (%)
Whole Tree Cache	0	2708	2708	0
Subtree Cache	2620	10644	13264	19.7527

final_summary.csv:

Metric	Value
Standard GCN Runtime (s)	4.46824
Whole Tree Cache Runtime (s)	3.83089
Subtree Cache Runtime (s)	3.7623
Subtree Speedup	1.18764
Subtree Cache Hit Rate (%)	19.7527
Subtree Reuse Percentage (%)	19.7527
Subtree Cache Memory (Bytes)	4.81647e+06

---

Discussion & Conclusions

Our research yields several critical insights into GNN message-passing execution:

1. Receptive Field Isomorphism: Nodes in dense cliques share substantial structural receptive fields. Standard GNN execution models perform redundant tensor aggregations by ignoring this overlap.
2. Limits of Whole-Tree Caching in Irregular Graphs: Hashing complete 2-hop trees yields a 0% hit rate on Cora due to topological irregularities. Complex real-world networks exhibit irregular localized structures, rendering whole-tree caches ineffective.
3. Subtree Decomposition as a Viable Caching Pattern: Decomposing trees bottom-up reveals hidden structural similarities. In the Cora network, decomposing computation trees yielded 99,596 total subtrees, with 3,740 repeated patterns. Utilizing Weisfeiler-Lehman canonical subtree hashing achieved a 19.75% cache reuse rate.
4. Execution Speedups: The subtree caching framework achieved a 1.19x execution speedup on CPU, reducing GNN message-passing evaluation time. The memory overhead for storing the 10,644 cached tensor embeddings was only 4.82 MB, demonstrating high computational savings with minimal memory footprint.

Summary Benchmarking Comparison (Cora)

Execution Method	Runtime (s)	Cache Hits	Cache Misses	Cache Size (Entries)	Memory (Bytes)	Speedup	Reuse %
Standard GCN	4.4682	0	2708	0	64	1.00x	0.00%
Whole Tree Cache	3.8309	0	2708	2708	607,108	1.17x	0.00%
Subtree Cache	3.7623	2620	10644	10644	4,816,468	1.19x	19.75%

---

Installation & Usage

1. Requirements

Ensure you have the following packages installed:

pip install torch torch-geometric networkx numpy pandas matplotlib scikit-learn tqdm

2. Running the Code

To reproduce the findings, run the notebooks in sequential order:

01_Graph_Basics -> 02_Computation_Trees -> ... -> 10_Real_World_Evaluation_on_Cora_Dataset

---

References

1. Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ICLR.
2. Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive Representation Learning on Large Graphs. NeurIPS.
3. Oono, K., & Suzuki, T. (2020). Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. ICLR.
4. Weisfeiler, B., & Leman, A. A. (1968). A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Tekhnicheskaya Informatsiya.

---

By: Tapananshu Tripathy
Under the Guidance of: Dr. Panthadeep Bhattacharjee, Assistant Professor, CSE, NIT Rourkela