Introduction¶

Many machine learning systems perform matrix operations. For straightforward calculations, most simple deep learning frameworks, such as Needle, do not account for differences in characteristics between dense and sparse matrices. However, real data often does not look like this. Right now, like user-item interactions, social networks, citation graphs, and many other types of information are usually extremely sparse. Treating sparse matrices as dense wastes both memory and computation, and limits the size of models we can experiment with.

This project extends the Needle framework by adding basic but functional support for sparse matrices, including storage formats, operator definitions, and autograd integration. With these tools in place, we then design a simple graph-based recommendation model and apply it to the MovieLens 100K dataset. The goal is not to beat production systems, but to show that Needle can support sparse workloads and run a non-trivial model end-to-end.

Overview¶

In this projects we already worked on these:

  1. Sparse Array Backend: We implemented a sparse backend for Needle includes:
  • COO and BSR storage formats
  • A new SparseTensor class compatible with Needle's autograd
  • A sparse dense matrix multiplication operator (SparseDenseMatMul)
  1. MovieLens Data Pipeline: Do these with MovieLens 100K ratings dataset:
  • Loading rating records between user and item
  • Constructing a bipartite graph between user and item
  • Building a sparse adjacency matrix in COO/BSR format
  • Preparing user/item index mappings and training labels
  1. GNN Modules: We implements a graph convolution with A simple GCN architecture (SimpleGCNRec) designed for bipartite graphs
  2. Benchmark Tools: We developed the performance comparison (dense vs sparse) under memory usage and SpMM performance

This is the architexture of the codes of our project:

10714_course_project/
├── src/
│   ├── python/needle/
│   │   ├── autograd.py                      [MODIFIED: +SparseTensor, +SparseTensorOp]
│   │   ├── ndarray_backend_sparse.py        [NEW: SparseArray, format conversion]
│   │   ├── ops/
│   │   │   └── ops_sparse.py                [NEW: SparseDenseMatMul, etc.]
│   │   ├── nn/
│   │   │   ├── gnn.py                       [NEW: GraphConv, SimpleGCNRec]
│   │   │   └── nn_basic.py
│   │   └── data/
│   │       ├── movielens.py                 [NEW: read_ml100k_ratings()]
│   │       └── datasets/
│   │           └── mnist_dataset.py
│   ├── apps/
│   │   ├── gnn_movielens.py                 [NEW: Training script]
│   │   └── benchmark_movielens_gnn.py       [NEW: Benchmark script]
│   ├── tests/
│   │   ├── test_ops_sparse.py               [NEW: Operator tests]
│   │   ├── test_gnn_sparse.py               [NEW: GNN tests]
│   │   └── test_matmul_sparse_dense.py      [NEW: Numerical validation]
│   └── data/
│       └── ml-100k/                         [Expected MovieLens 100K files]
│           ├── u.data                       (ratings tab-separated)
│           └── u.item, u.user, etc.
└── README.md

Set up the environment¶

In [ ]:
from google.colab import drive
drive.mount('/content/drive')
Drive already mounted at /content/drive; to attempt to forcibly remount, call drive.mount("/content/drive", force_remount=True).
In [ ]:
url = 'https://drive.google.com/uc?id=1pw5va-C-Rgdk5m-HobRBkhse_wzdQ1n5'
!pip install gdown
import gdown
gdown.download(url, output="10714_course_project-main.zip", quiet=False)
Requirement already satisfied: gdown in /usr/local/lib/python3.12/dist-packages (5.2.0)
Requirement already satisfied: beautifulsoup4 in /usr/local/lib/python3.12/dist-packages (from gdown) (4.13.5)
Requirement already satisfied: filelock in /usr/local/lib/python3.12/dist-packages (from gdown) (3.20.0)
Requirement already satisfied: requests[socks] in /usr/local/lib/python3.12/dist-packages (from gdown) (2.32.4)
Requirement already satisfied: tqdm in /usr/local/lib/python3.12/dist-packages (from gdown) (4.67.1)
Requirement already satisfied: soupsieve>1.2 in /usr/local/lib/python3.12/dist-packages (from beautifulsoup4->gdown) (2.8)
Requirement already satisfied: typing-extensions>=4.0.0 in /usr/local/lib/python3.12/dist-packages (from beautifulsoup4->gdown) (4.15.0)
Requirement already satisfied: charset_normalizer<4,>=2 in /usr/local/lib/python3.12/dist-packages (from requests[socks]->gdown) (3.4.4)
Requirement already satisfied: idna<4,>=2.5 in /usr/local/lib/python3.12/dist-packages (from requests[socks]->gdown) (3.11)
Requirement already satisfied: urllib3<3,>=1.21.1 in /usr/local/lib/python3.12/dist-packages (from requests[socks]->gdown) (2.5.0)
Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.12/dist-packages (from requests[socks]->gdown) (2025.11.12)
Requirement already satisfied: PySocks!=1.5.7,>=1.5.6 in /usr/local/lib/python3.12/dist-packages (from requests[socks]->gdown) (1.7.1)
Downloading...
From: https://drive.google.com/uc?id=1pw5va-C-Rgdk5m-HobRBkhse_wzdQ1n5
To: /content/10714_course_project-main.zip
100%|██████████| 16.8M/16.8M [00:00<00:00, 80.3MB/s]
Out[ ]:
'10714_course_project-main.zip'
In [ ]:
!unzip /content/10714_course_project-main.zip
Archive:  /content/10714_course_project-main.zip
b11bcc2a69289a01866e9cc04541e6a1468c25f7
replace 10714_course_project-main/.gitignore? [y]es, [n]o, [A]ll, [N]one, [r]ename: A
  inflating: 10714_course_project-main/.gitignore  
  inflating: 10714_course_project-main/README.md  
  inflating: 10714_course_project-main/perf/bench_sparse_memory.py  
  inflating: 10714_course_project-main/perf/bench_sparse_runtime.py  
  inflating: 10714_course_project-main/pics/memory_sparse_plot.png  
  inflating: 10714_course_project-main/pics/runtime_sparse_plot.png  
  inflating: 10714_course_project-main/src/apps/benchmark_movielens_gnn.py  
  inflating: 10714_course_project-main/src/apps/gnn_movielens.py  
  inflating: 10714_course_project-main/src/apps/mlp_resnet.py  
  inflating: 10714_course_project-main/src/data/ml-100k/README  
  inflating: 10714_course_project-main/src/data/ml-100k/allbut.pl  
  inflating: 10714_course_project-main/src/data/ml-100k/mku.sh  
  inflating: 10714_course_project-main/src/data/ml-100k/u.data  
  inflating: 10714_course_project-main/src/data/ml-100k/u.genre  
  inflating: 10714_course_project-main/src/data/ml-100k/u.info  
  inflating: 10714_course_project-main/src/data/ml-100k/u.item  
  inflating: 10714_course_project-main/src/data/ml-100k/u.occupation  
  inflating: 10714_course_project-main/src/data/ml-100k/u.user  
  inflating: 10714_course_project-main/src/data/ml-100k/u1.base  
  inflating: 10714_course_project-main/src/data/ml-100k/u1.test  
  inflating: 10714_course_project-main/src/data/ml-100k/u2.base  
  inflating: 10714_course_project-main/src/data/ml-100k/u2.test  
  inflating: 10714_course_project-main/src/data/ml-100k/u3.base  
  inflating: 10714_course_project-main/src/data/ml-100k/u3.test  
  inflating: 10714_course_project-main/src/data/ml-100k/u4.base  
  inflating: 10714_course_project-main/src/data/ml-100k/u4.test  
  inflating: 10714_course_project-main/src/data/ml-100k/u5.base  
  inflating: 10714_course_project-main/src/data/ml-100k/u5.test  
  inflating: 10714_course_project-main/src/data/ml-100k/ua.base  
  inflating: 10714_course_project-main/src/data/ml-100k/ua.test  
  inflating: 10714_course_project-main/src/data/ml-100k/ub.base  
  inflating: 10714_course_project-main/src/data/ml-100k/ub.test  
 extracting: 10714_course_project-main/src/data/t10k-images-idx3-ubyte.gz  
 extracting: 10714_course_project-main/src/data/t10k-labels-idx1-ubyte.gz  
 extracting: 10714_course_project-main/src/data/train-images-idx3-ubyte.gz  
 extracting: 10714_course_project-main/src/data/train-labels-idx1-ubyte.gz  
  inflating: 10714_course_project-main/src/python/needle/__init__.py  
  inflating: 10714_course_project-main/src/python/needle/autograd.py  
  inflating: 10714_course_project-main/src/python/needle/backend_numpy.py  
  inflating: 10714_course_project-main/src/python/needle/backend_sparse.py  
  inflating: 10714_course_project-main/src/python/needle/data/__init__.py  
  inflating: 10714_course_project-main/src/python/needle/data/data_basic.py  
  inflating: 10714_course_project-main/src/python/needle/data/data_transforms.py  
  inflating: 10714_course_project-main/src/python/needle/data/datasets/__init__.py  
  inflating: 10714_course_project-main/src/python/needle/data/datasets/mnist_dataset.py  
  inflating: 10714_course_project-main/src/python/needle/data/datasets/ndarray_dataset.py  
  inflating: 10714_course_project-main/src/python/needle/data/movielens.py  
  inflating: 10714_course_project-main/src/python/needle/init/__init__.py  
  inflating: 10714_course_project-main/src/python/needle/init/init_basic.py  
  inflating: 10714_course_project-main/src/python/needle/init/init_initializers.py  
  inflating: 10714_course_project-main/src/python/needle/ndarray_backend_sparse.py  
 extracting: 10714_course_project-main/src/python/needle/nn/__init__.py  
  inflating: 10714_course_project-main/src/python/needle/nn/gnn.py  
  inflating: 10714_course_project-main/src/python/needle/nn/nn_basic.py  
  inflating: 10714_course_project-main/src/python/needle/ops/__init__.py  
  inflating: 10714_course_project-main/src/python/needle/ops/ops_logarithmic.py  
  inflating: 10714_course_project-main/src/python/needle/ops/ops_mathematic.py  
  inflating: 10714_course_project-main/src/python/needle/ops/ops_sparse.py  
  inflating: 10714_course_project-main/src/python/needle/ops/ops_tuple.py  
  inflating: 10714_course_project-main/src/python/needle/optim.py  
  inflating: 10714_course_project-main/src/tests/conftest.py  
  inflating: 10714_course_project-main/src/tests/hw2/test_data.py  
  inflating: 10714_course_project-main/src/tests/hw2/test_nn_and_optim.py  
  inflating: 10714_course_project-main/src/tests/test_gnn_sparse.py  
  inflating: 10714_course_project-main/src/tests/test_matmul_sparse_dense.py  
  inflating: 10714_course_project-main/src/tests/test_movielens_gnn.py  
  inflating: 10714_course_project-main/src/tests/test_ops_sparse.py  
  inflating: 10714_course_project-main/src/tests/test_sparse.py  
  inflating: 10714_course_project-main/src/tests/test_sparse_backend.py  
In [ ]:
%cd /content/10714_course_project-main/src
/content/10714_course_project-main/src
In [ ]:
!pip install numpy pandas matplotlib pytest
Requirement already satisfied: numpy in /usr/local/lib/python3.12/dist-packages (2.0.2)
Requirement already satisfied: pandas in /usr/local/lib/python3.12/dist-packages (2.2.2)
Requirement already satisfied: matplotlib in /usr/local/lib/python3.12/dist-packages (3.10.0)
Requirement already satisfied: pytest in /usr/local/lib/python3.12/dist-packages (8.4.2)
Requirement already satisfied: python-dateutil>=2.8.2 in /usr/local/lib/python3.12/dist-packages (from pandas) (2.9.0.post0)
Requirement already satisfied: pytz>=2020.1 in /usr/local/lib/python3.12/dist-packages (from pandas) (2025.2)
Requirement already satisfied: tzdata>=2022.7 in /usr/local/lib/python3.12/dist-packages (from pandas) (2025.2)
Requirement already satisfied: contourpy>=1.0.1 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (1.3.3)
Requirement already satisfied: cycler>=0.10 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (0.12.1)
Requirement already satisfied: fonttools>=4.22.0 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (4.61.0)
Requirement already satisfied: kiwisolver>=1.3.1 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (1.4.9)
Requirement already satisfied: packaging>=20.0 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (25.0)
Requirement already satisfied: pillow>=8 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (11.3.0)
Requirement already satisfied: pyparsing>=2.3.1 in /usr/local/lib/python3.12/dist-packages (from matplotlib) (3.2.5)
Requirement already satisfied: iniconfig>=1 in /usr/local/lib/python3.12/dist-packages (from pytest) (2.3.0)
Requirement already satisfied: pluggy<2,>=1.5 in /usr/local/lib/python3.12/dist-packages (from pytest) (1.6.0)
Requirement already satisfied: pygments>=2.7.2 in /usr/local/lib/python3.12/dist-packages (from pytest) (2.19.2)
Requirement already satisfied: six>=1.5 in /usr/local/lib/python3.12/dist-packages (from python-dateutil>=2.8.2->pandas) (1.17.0)
In [ ]:
import sys
import os
NEEDLE_PYTHON_PATH = "/content/10714_course_project-main/src/python"
if NEEDLE_PYTHON_PATH not in sys.path:
    sys.path.insert(0, NEEDLE_PYTHON_PATH)
try:
    import needle as ndl
except ModuleNotFoundError:
    import importlib.util
    spec = importlib.util.spec_from_file_location(
        "needle",
        "/content/10714_course_project-main/src/python/needle/__init__.py"
    )
    ndl = importlib.util.module_from_spec(spec)
    sys.modules['needle'] = ndl
    spec.loader.exec_module(ndl)
    print("✓ needle loaded via importlib")
import needle.nn as nn

print("✓ Setup complete!")
✓ Setup complete!

Sparse Array Backend¶

src/python/needle/ndarray_backend_sparse.py¶

Purpose: Low-level sparse array storage and format conversion (COO ↔ BSR).

Key Classes:

  • SparseArray: Container for sparse matrices
    • .data: Non-zero values (1D array)
    • .indices: Column indices (1D for COO, 2D for BSR block indices)
    • .indptr: Row pointer array (CSR-style, for BSR row compression)
    • .shape: Matrix dimensions (m, n)
    • .format: "coo" or "bsr"
    • .block_shape: Block size for BSR (e.g., (4, 4))

Key Methods:

  • from_dense(dense_array, format, dtype, device) — Convert dense → sparse
  • to_dense() — Convert sparse → dense
  • to_coo() — Convert to COO format
  • to_bsr(block_shape) — Convert to BSR format with given block size
  • matmul(dense_rhs) — Sparse–dense matrix multiply (A @ X)

Supported Formats:

  • COO (Coordinate): (data, row_indices, col_indices, shape)

    • Dense packing, simple random-access writes
    • Good for unstructured sparsity
  • BSR (Block Sparse Row): (data, block_col_indices, row_ptr, block_shape)

    • Compressed storage for structured block patterns
    • Lower memory, better cache locality

src/python/needle/ops/ops_sparse.py¶

Purpose: Autograd operators for sparse–dense operations.

Key Operators:

  • SparseDenseMatMul — Forward: Y = A @ X (sparse A, dense X)

    • Backward: Computes dA (sparse) and dX (dense)
  • SparseAdd — Element-wise addition (two sparse or sparse+scalar)

  • SparseScale — Scalar multiplication (sparse * scalar)

Test¶

Our project relies on Needle's existing test suite plus several new tests we added for sparse operations. The original homework tests cover data loading, common neural network layers, and optimizers, ensuring that the dense parts of the framework behave as expected.

We also include tests for the sparse backend, such as COO/BSR formats, sparse–dense matmul, and gradient checks. These help confirm that our sparse tensor implementation matches the behavior of its dense counterparts.

In [ ]:
%cd /content/10714_course_project-main/src
!PYTHONPATH=/content/10714_course_project-main/src/python \
  pytest -v \
    --ignore=tests/test_gnn_sparse.py \
    --ignore=tests/test_movielens_gnn.py \
    tests
 # test successful integration with needle framework using HW2 test
/content/10714_course_project-main/src
============================= test session starts ==============================
platform linux -- Python 3.12.12, pytest-8.4.2, pluggy-1.6.0 -- /usr/bin/python3
cachedir: .pytest_cache
rootdir: /content/10714_course_project-main/src
plugins: typeguard-4.4.4, langsmith-0.4.55, anyio-4.12.0
collected 113 items                                                            

tests/hw2/test_data.py::test_flip_horizontal PASSED                      [  0%]
tests/hw2/test_data.py::test_random_crop PASSED                          [  1%]
tests/hw2/test_data.py::test_mnist_dataset PASSED                        [  2%]
tests/hw2/test_data.py::test_dataloader_mnist PASSED                     [  3%]
tests/hw2/test_data.py::test_dataloader_ndarray PASSED                   [  4%]
tests/hw2/test_nn_and_optim.py::test_check_prng_contact_us_if_this_fails_1 PASSED [  5%]
tests/hw2/test_nn_and_optim.py::test_op_power_scalar_forward_1 PASSED    [  6%]
tests/hw2/test_nn_and_optim.py::test_op_power_scalar_forward_2 PASSED    [  7%]
tests/hw2/test_nn_and_optim.py::test_op_power_scalar_backward_1 PASSED   [  7%]
tests/hw2/test_nn_and_optim.py::test_op_logsoftmax_forward_1 PASSED      [  8%]
tests/hw2/test_nn_and_optim.py::test_op_logsoftmax_stable_forward_1 PASSED [  9%]
tests/hw2/test_nn_and_optim.py::test_op_logsoftmax_backward_1 PASSED     [ 10%]
tests/hw2/test_nn_and_optim.py::test_op_logsumexp_forward_1 PASSED       [ 11%]
tests/hw2/test_nn_and_optim.py::test_op_logsumexp_forward_2 PASSED       [ 12%]
tests/hw2/test_nn_and_optim.py::test_op_logsumexp_forward_3 PASSED       [ 13%]
tests/hw2/test_nn_and_optim.py::test_op_logsumexp_forward_4 PASSED       [ 14%]
tests/hw2/test_nn_and_optim.py::test_op_logsumexp_forward_5 PASSED       [ 15%]
tests/hw2/test_nn_and_optim.py::test_op_logsumexp_backward_1 PASSED      [ 15%]
tests/hw2/test_nn_and_optim.py::test_op_logsumexp_backward_2 PASSED      [ 16%]
tests/hw2/test_nn_and_optim.py::test_op_logsumexp_backward_3 PASSED      [ 17%]
tests/hw2/test_nn_and_optim.py::test_op_logsumexp_backward_5 PASSED      [ 18%]
tests/hw2/test_nn_and_optim.py::test_op_logsumexp_backward_4 PASSED      [ 19%]
tests/hw2/test_nn_and_optim.py::test_init_kaiming_uniform PASSED         [ 20%]
tests/hw2/test_nn_and_optim.py::test_init_kaiming_normal PASSED          [ 21%]
tests/hw2/test_nn_and_optim.py::test_init_xavier_uniform PASSED          [ 22%]
tests/hw2/test_nn_and_optim.py::test_init_xavier_normal PASSED           [ 23%]
tests/hw2/test_nn_and_optim.py::test_nn_linear_weight_init_1 PASSED      [ 23%]
tests/hw2/test_nn_and_optim.py::test_nn_linear_bias_init_1 PASSED        [ 24%]
tests/hw2/test_nn_and_optim.py::test_nn_linear_forward_1 PASSED          [ 25%]
tests/hw2/test_nn_and_optim.py::test_nn_linear_forward_2 PASSED          [ 26%]
tests/hw2/test_nn_and_optim.py::test_nn_linear_forward_3 PASSED          [ 27%]
tests/hw2/test_nn_and_optim.py::test_nn_linear_backward_1 PASSED         [ 28%]
tests/hw2/test_nn_and_optim.py::test_nn_linear_backward_2 PASSED         [ 29%]
tests/hw2/test_nn_and_optim.py::test_nn_linear_backward_3 PASSED         [ 30%]
tests/hw2/test_nn_and_optim.py::test_nn_relu_forward_1 PASSED            [ 30%]
tests/hw2/test_nn_and_optim.py::test_nn_relu_backward_1 PASSED           [ 31%]
tests/hw2/test_nn_and_optim.py::test_nn_sequential_forward_1 PASSED      [ 32%]
tests/hw2/test_nn_and_optim.py::test_nn_sequential_backward_1 PASSED     [ 33%]
tests/hw2/test_nn_and_optim.py::test_nn_softmax_loss_forward_1 PASSED    [ 34%]
tests/hw2/test_nn_and_optim.py::test_nn_softmax_loss_forward_2 PASSED    [ 35%]
tests/hw2/test_nn_and_optim.py::test_nn_softmax_loss_backward_1 PASSED   [ 36%]
tests/hw2/test_nn_and_optim.py::test_nn_softmax_loss_backward_2 PASSED   [ 37%]
tests/hw2/test_nn_and_optim.py::test_nn_layernorm_forward_1 PASSED       [ 38%]
tests/hw2/test_nn_and_optim.py::test_nn_layernorm_forward_2 PASSED       [ 38%]
tests/hw2/test_nn_and_optim.py::test_nn_layernorm_forward_3 PASSED       [ 39%]
tests/hw2/test_nn_and_optim.py::test_nn_layernorm_backward_1 PASSED      [ 40%]
tests/hw2/test_nn_and_optim.py::test_nn_layernorm_backward_2 PASSED      [ 41%]
tests/hw2/test_nn_and_optim.py::test_nn_layernorm_backward_3 PASSED      [ 42%]
tests/hw2/test_nn_and_optim.py::test_nn_layernorm_backward_4 PASSED      [ 43%]
tests/hw2/test_nn_and_optim.py::test_nn_batchnorm_check_model_eval_switches_training_flag_1 PASSED [ 44%]
tests/hw2/test_nn_and_optim.py::test_nn_batchnorm_forward_1 PASSED       [ 45%]
tests/hw2/test_nn_and_optim.py::test_nn_batchnorm_forward_affine_1 PASSED [ 46%]
tests/hw2/test_nn_and_optim.py::test_nn_batchnorm_backward_1 PASSED      [ 46%]
tests/hw2/test_nn_and_optim.py::test_nn_batchnorm_backward_affine_1 PASSED [ 47%]
tests/hw2/test_nn_and_optim.py::test_nn_batchnorm_running_mean_1 PASSED  [ 48%]
tests/hw2/test_nn_and_optim.py::test_nn_batchnorm_running_var_1 PASSED   [ 49%]
tests/hw2/test_nn_and_optim.py::test_nn_batchnorm_running_grad_1 PASSED  [ 50%]
tests/hw2/test_nn_and_optim.py::test_nn_dropout_forward_1 PASSED         [ 51%]
tests/hw2/test_nn_and_optim.py::test_nn_dropout_backward_1 PASSED        [ 52%]
tests/hw2/test_nn_and_optim.py::test_nn_residual_forward_1 PASSED        [ 53%]
tests/hw2/test_nn_and_optim.py::test_nn_residual_backward_1 PASSED       [ 53%]
tests/hw2/test_nn_and_optim.py::test_nn_flatten_forward_1 PASSED         [ 54%]
tests/hw2/test_nn_and_optim.py::test_nn_flatten_forward_2 PASSED         [ 55%]
tests/hw2/test_nn_and_optim.py::test_nn_flatten_forward_3 PASSED         [ 56%]
tests/hw2/test_nn_and_optim.py::test_nn_flatten_forward_4 PASSED         [ 57%]
tests/hw2/test_nn_and_optim.py::test_nn_flatten_backward_1 PASSED        [ 58%]
tests/hw2/test_nn_and_optim.py::test_nn_flatten_backward_2 PASSED        [ 59%]
tests/hw2/test_nn_and_optim.py::test_nn_flatten_backward_3 PASSED        [ 60%]
tests/hw2/test_nn_and_optim.py::test_nn_flatten_backward_4 PASSED        [ 61%]
tests/hw2/test_nn_and_optim.py::test_nn_flatten_backward_5 PASSED        [ 61%]
tests/hw2/test_nn_and_optim.py::test_optim_sgd_vanilla_1 PASSED          [ 62%]
tests/hw2/test_nn_and_optim.py::test_optim_sgd_momentum_1 PASSED         [ 63%]
tests/hw2/test_nn_and_optim.py::test_optim_sgd_weight_decay_1 PASSED     [ 64%]
tests/hw2/test_nn_and_optim.py::test_optim_sgd_momentum_weight_decay_1 PASSED [ 65%]
tests/hw2/test_nn_and_optim.py::test_optim_sgd_layernorm_residual_1 PASSED [ 66%]
tests/hw2/test_nn_and_optim.py::test_optim_sgd_z_memory_check_1 PASSED   [ 67%]
tests/hw2/test_nn_and_optim.py::test_optim_adam_1 PASSED                 [ 68%]
tests/hw2/test_nn_and_optim.py::test_optim_adam_weight_decay_1 PASSED    [ 69%]
tests/hw2/test_nn_and_optim.py::test_optim_adam_batchnorm_1 PASSED       [ 69%]
tests/hw2/test_nn_and_optim.py::test_optim_adam_batchnorm_eval_mode_1 PASSED [ 70%]
tests/hw2/test_nn_and_optim.py::test_optim_adam_layernorm_1 PASSED       [ 71%]
tests/hw2/test_nn_and_optim.py::test_optim_adam_weight_decay_bias_correction_1 PASSED [ 72%]
tests/hw2/test_nn_and_optim.py::test_optim_adam_z_memory_check_1 PASSED  [ 73%]
tests/hw2/test_nn_and_optim.py::test_mlp_residual_block_num_params_1 PASSED [ 74%]
tests/hw2/test_nn_and_optim.py::test_mlp_residual_block_num_params_2 PASSED [ 75%]
tests/hw2/test_nn_and_optim.py::test_mlp_residual_block_forward_1 PASSED [ 76%]
tests/hw2/test_nn_and_optim.py::test_mlp_resnet_num_params_1 PASSED      [ 76%]
tests/hw2/test_nn_and_optim.py::test_mlp_resnet_num_params_2 PASSED      [ 77%]
tests/hw2/test_nn_and_optim.py::test_mlp_resnet_forward_1 PASSED         [ 78%]
tests/hw2/test_nn_and_optim.py::test_mlp_resnet_forward_2 PASSED         [ 79%]
tests/hw2/test_nn_and_optim.py::test_mlp_train_epoch_1 PASSED            [ 80%]
tests/hw2/test_nn_and_optim.py::test_mlp_eval_epoch_1 PASSED             [ 81%]
tests/hw2/test_nn_and_optim.py::test_mlp_train_mnist_1 PASSED            [ 82%]
tests/test_matmul_sparse_dense.py::test_matmul_sparse_dense_equivalence PASSED [ 83%]
tests/test_matmul_sparse_dense.py::test_matmul_with_bsr_format PASSED    [ 84%]
tests/test_matmul_sparse_dense.py::test_matmul_direct_comparison PASSED  [ 84%]
tests/test_ops_sparse.py::TestSparseDenseMatMul::test_sparse_dense_matmul PASSED [ 85%]
tests/test_ops_sparse.py::TestSparseDenseMatMul::test_sparse_dense_matmul_vs_dense PASSED [ 86%]
tests/test_ops_sparse.py::TestSparseDenseMatMul::test_sparse_dense_matmul_gradient PASSED [ 87%]
tests/test_ops_sparse.py::TestSparseDenseMatMul::test_sparse_dense_matmul_with_bsr PASSED [ 88%]
tests/test_ops_sparse.py::TestSparseDenseMatMul::test_sparse_dense_matmul_gradient_matches_torch PASSED [ 89%]
tests/test_sparse.py::test_sparse_array_basic PASSED                     [ 90%]
tests/test_sparse.py::test_sparse_from_dense PASSED                      [ 91%]
tests/test_sparse.py::test_sparse_dense_matmul PASSED                    [ 92%]
tests/test_sparse.py::test_sparse_tensor_creation PASSED                 [ 92%]
tests/test_sparse.py::test_sparse_scalar_operations PASSED               [ 93%]
tests/test_sparse.py::test_sparse_gradient_basic PASSED                  [ 94%]
tests/test_sparse.py::test_sparse_dense_matmul_gradient PASSED           [ 95%]
tests/test_sparse.py::test_sparse_addition_gradient PASSED               [ 96%]
tests/test_sparse_backend.py::test_coo_format PASSED                     [ 97%]
tests/test_sparse_backend.py::test_bsr_format PASSED                     [ 98%]
tests/test_sparse_backend.py::test_from_dense PASSED                     [ 99%]
tests/test_sparse_backend.py::test_format_conversion PASSED              [100%]

======================== 113 passed in 60.34s (0:01:00) ========================
In [ ]:
%cd /content/10714_course_project-main
!PYTHONPATH=/content/10714_course_project-main/src/python \
  python src/tests/test_sparse.py
/content/10714_course_project-main
Running sparse tensor tests...

Testing SparseArray basic functionality...
✓ SparseArray basic functionality works
Testing SparseArray.from_dense...
✓ SparseArray.from_dense works
Testing sparse-dense matrix multiplication...
✓ Sparse-dense matrix multiplication works
Testing SparseTensor creation...
✓ SparseTensor creation works
Testing sparse scalar operations...
✓ Sparse scalar operations work
Testing sparse gradient computation...
✓ Sparse gradient computation works
Testing sparse-dense matmul gradient...
✓ Sparse-dense matmul gradient works
Testing sparse addition gradient...
✓ Sparse addition gradient works

🎉 All tests passed! Sparse tensor implementation is working correctly.
In [ ]:
%cd /content/10714_course_project-main
!PYTHONPATH=/content/10714_course_project-main/src/python \
  python src/tests/test_matmul_sparse_dense.py
/content/10714_course_project-main
Testing MatMul Correctness: Dense vs Sparse
============================================================
=== Testing Sparse @ Dense MatMul Equivalence ===

Test 1: Diagonal sparse matrix
Sparse matrix (dense form):
[[1. 0. 0.]
 [0. 2. 0.]
 [0. 0. 3.]]
Dense matrix:
[[1. 2.]
 [3. 4.]
 [5. 6.]]
Result (dense MatMul):
[[ 1.  2.]
 [ 6.  8.]
 [15. 18.]]
Result (sparse @ dense):
[[ 1.  2.]
 [ 6.  8.]
 [15. 18.]]
Expected (numpy):
[[ 1.  2.]
 [ 6.  8.]
 [15. 18.]]
✓ Test 1 passed: Diagonal sparse matrix

Test 2: Random sparse matrix
Sparsity: 7/20 = 35.00%
Result (dense MatMul):
[[ 0.47829634  0.11099328 -0.07490407]
 [ 0.22775377 -0.82369167 -0.59852594]
 [-0.38616377  0.5731548  -0.09805611]
 [ 3.749398    2.541192   -0.37665072]
 [-1.5036445   1.080902   -0.10653212]]
Result (sparse @ dense):
[[ 0.47829634  0.11099328 -0.07490407]
 [ 0.22775377 -0.82369167 -0.59852594]
 [-0.38616377  0.5731548  -0.09805611]
 [ 3.749398    2.541192   -0.37665072]
 [-1.5036445   1.080902   -0.10653212]]
✓ Test 2 passed: Random sparse matrix

Test 3: Large sparse matrix
✓ Test 3 passed: Large sparse matrix

✓ All MatMul equivalence tests passed!

=== Testing MatMul with BSR Format ===
BSR matrix shape: (6, 9)
BSR nnz: 24
Result (dense MatMul):
[[  2.8852155   -1.9828202    3.2381496    2.7753031 ]
 [  2.8852155   -1.9828202    3.2381496    2.7753031 ]
 [  4.6652427   -3.6486473    4.432621     2.3327777 ]
 [  4.6652427   -3.6486473    4.432621     2.3327777 ]
 [ -2.9188368  -10.001517    -5.1221447    0.97784317]
 [ -2.9188368  -10.001517    -5.1221447    0.97784317]]
Result (sparse @ dense):
[[  2.8852155   -1.9828202    3.2381496    2.7753031 ]
 [  2.8852155   -1.9828202    3.2381496    2.7753031 ]
 [  4.6652427   -3.6486473    4.432621     2.3327777 ]
 [  4.6652427   -3.6486473    4.432621     2.3327777 ]
 [ -2.9188368  -10.001517    -5.1221447    0.97784317]
 [ -2.9188368  -10.001517    -5.1221447    0.97784317]]
✓ BSR format MatMul test passed!

=== Testing MatMul Class with Sparse Arrays ===

Test 1: COO format sparse array
Sparse (COO) -> Dense:
[[1. 0. 0.]
 [0. 2. 0.]
 [0. 0. 3.]]
MatMul result:
[[ 1.  2.]
 [ 6.  8.]
 [15. 18.]]
Numpy matmul:
[[ 1.  2.]
 [ 6.  8.]
 [15. 18.]]
✓ Test 1 passed: COO format

Test 2: BSR format sparse array
BSR -> Dense shape: (4, 4)
MatMul result shape: (4, 3)
Results match: True
✓ Test 2 passed: BSR format

Test 3: Dense vs Sparse-to-Dense equivalence
Sparsity: 12/20 = 60.00%
✓ Test 3 passed: Dense vs Sparse-to-Dense equivalence

✓ All MatMul class tests passed!

============================================================
🎉 All MatMul correctness tests passed!

Summary:
✓ Sparse-to-dense conversion + MatMul produces same results as numpy
✓ MatMul works correctly with both COO and BSR formats
✓ Converting sparse arrays to dense and using MatMul is correct

MovieLens 100K dataset¶

The MovieLens 100K dataset is one of the most widely used benchmarks in recommendation system research and education. Released by the GroupLens research lab at the University of Minnesota, it contains 100,000 explicit ratings collected from 943 users on 1,682 movies. Each rating is an integer from 1 to 5, representing the user’s preference level.

One of the notable features of MovieLens 100K is that it is high sparsity. If we consider the full user–item rating matrix of size (943 \times 1682), more than 93% of entries are missing which means the dataset an excellent testbed for models and frameworks that rely on sparse data representations.

In addition to ratings, the dataset includes user attributes (age, gender, occupation, zip code) and movie metadata (genres, release year). While not all models require these features, they provide opportunities for hybrid systems that combine collaborative filtering with side information.

For this project, we treat MovieLens 100K as a bipartite graph where:

  • Each user is represented as a node
  • Each movie is represented as a node
  • Each rating forms an edge connecting a user to a movie

This graph-based view naturally aligns with GNN-style message passing and allows us to leverage the sparse adjacency structure efficiently via our custom sparse operators.

Data Loading & Preprocessing¶

src/python/needle/data/ml-100k¶

We load the MovieLens 100K data by reading the ml-100k file into a pandas DataFrame and extracting user IDs, item IDs, and ratings. The DataFrame is then converted into indexed user/item lists and a sparse interaction matrix, which is later used to construct the bipartite graph

Key Functions:

def read_ml100k_ratings() -> Tuple[pd.DataFrame, int, int]:

In [ ]:
"""Test that MovieLens 100K can be loaded and basic statistics are correct."""
print("Testing MovieLens 100K loading and basic stats...")

import sys, os
NEEDLE_PYTHON_PATH = "/content/10714_course_project-main/src/python"
if NEEDLE_PYTHON_PATH not in sys.path:
    sys.path.insert(0, NEEDLE_PYTHON_PATH)

import needle.data.movielens as ml

data, num_users, num_items = ml.read_ml100k_ratings()

# Basic sanity checks (standard ML-100K stats)
assert num_users == 943, f"Expected 943 users, got {num_users}"
assert num_items == 1682, f"Expected 1682 items, got {num_items}"

num_interactions = len(data)
sparsity = 1.0 - num_interactions / (num_users * num_items)

# MovieLens 100K is known to be very sparse (~93.7%)
assert sparsity > 0.9, f"Expected sparsity > 0.9, got {sparsity}"
assert sparsity < 0.99, f"Expected sparsity < 0.99, got {sparsity}"

print(
    f"✓ MovieLens loaded: users={num_users}, items={num_items}, "
    f"interactions={num_interactions}, sparsity={sparsity:.4f}"
)
Testing MovieLens 100K loading and basic stats...
✓ MovieLens loaded: users=943, items=1682, interactions=100000, sparsity=0.9370

GNN Modules¶

src/python/needle/nn/gnn.py¶

This file contains the lightweight GNN layers used in our MovieLens experiments.
The goal is to keep the implementation simple and consistent with Needle's style while allowing sparse adjacency matrices to participate naturally in message passing.

The GraphConv class implements one round of graph convolution. Each node first transforms its own features, and then aggregates information from its neighbors using the adjacency matrix.

GraphConv¶

class GraphConv(Module):
    """Graph convolution layer: Y = σ(A @ X @ W + b)"""
    
    def __init__(self, in_features: int, out_features: int, device=None, dtype="float32")
    
    def forward(self, x: Tensor, adj: SparseTensor) -> Tensor:
        """
        Args:
            x: Node features (n_nodes, in_features)
            adj: Adjacency matrix (n_nodes, n_nodes), sparse
        Returns:
            out: (n_nodes, out_features)
        """

Mechanism:

  1. Apply linear transform: X' = X @ W
  2. Aggregate neighbors: Z = A @ X'
  3. Apply activation (ReLU): out = σ(Z + b)

The layer keeps the essential structure of a GCN without extra complications (normalization, self-loops, etc.). This makes it easier to verify correctness and focus on the sparse operator behavior.

SimpleGCNRec is a small recommendation model built on top of GraphConv. It treats the user's item rating data as a bipartite graph and learns embeddings for both sides.

SimpleGCNRec¶

class SimpleGCNRec(Module):
    """Multi-layer GCN for recommendation (user–item bipartite graphs)"""
    
    def __init__(
        self,
        num_users: int,
        num_items: int,
        embed_dim: int,
        n_layers: int = 2,
        device=None,
        dtype="float32"
    )
    
    def forward(self, adj: SparseTensor) -> Tuple[Tensor, Tensor]:
        """
        Args:
            adj: Bipartite adjacency (num_users+num_items, num_users+num_items)
        
        Returns:
            user_embed: (num_users, embed_dim)
            item_embed: (num_items, embed_dim)
        """

Architecture:

  • Initialize: User embeddings (num_users, embed_dim), Item embeddings (num_items, embed_dim)
  • Stack n_layers GraphConv blocks with ReLU between layers
  • Output: Final user and item embeddings
In [ ]:
%cd /content/10714_course_project-main/src
!PYTHONPATH=/content/10714_course_project-main/src/python \
  pytest -v tests/test_gnn_sparse.py
/content/10714_course_project-main/src
============================= test session starts ==============================
platform linux -- Python 3.12.12, pytest-8.4.2, pluggy-1.6.0 -- /usr/bin/python3
cachedir: .pytest_cache
rootdir: /content/10714_course_project-main/src
plugins: typeguard-4.4.4, langsmith-0.4.55, anyio-4.12.0
collected 8 items                                                              

tests/test_gnn_sparse.py::test_graphconv_basic_chain PASSED              [ 12%]
tests/test_gnn_sparse.py::test_graphconv_random_graph_shape_and_grad PASSED [ 25%]
tests/test_gnn_sparse.py::test_graphconv_matches_dense_implementation PASSED [ 37%]
tests/test_gnn_sparse.py::test_graphconv_two_layer_stack PASSED          [ 50%]
tests/test_gnn_sparse.py::test_sparse_dense_matmul_basic PASSED          [ 62%]
tests/test_gnn_sparse.py::test_graphconv_with_bsr_format PASSED          [ 75%]
tests/test_gnn_sparse.py::test_simplegcnrec_forward_backward_small_bipartite PASSED [ 87%]
tests/test_gnn_sparse.py::test_simplegcnrec_batch_permutation_invariance PASSED [100%]

============================== 8 passed in 0.19s ===============================
In [ ]:
!python '/content/10714_course_project-main/src/tests/test_gnn_sparse.py'
Running GNN + sparse tensor tests...

Testing GraphConv on a simple chain graph...
✓ GraphConv chain graph forward/backward works
Testing GraphConv on a random graph (shape & grad)...
✓ GraphConv random graph shape & grad work
Testing GraphConv numerical consistency with dense implementation...
✓ GraphConv matches dense implementation numerically
Testing two-layer GraphConv stack...
✓ Two-layer GraphConv stack forward/backward works
Testing SparseDenseMatMul basic correctness...
✓ SparseDenseMatMul forward/backward works
Testing GraphConv with BSR sparse format...
✓ GraphConv works with BSR sparse format (if backend supports it)
Testing SimpleGCNRec forward/backward on a small bipartite graph...
✓ SimpleGCNRec small bipartite forward/backward works
Testing SimpleGCNRec batch permutation invariance...
✓ SimpleGCNRec is permutation-invariant over batch examples

🎉 All GNN sparse tests passed! GNN implementation on SparseTensor looks correct.

Applications & Benchmarks¶

gnn_movielens.py trains our SimpleGCNRec model on the MovieLens 100K dataset for collaborative filtering.
It does the following steps:

  • Loads the user item ratings and builds a bipartite graph.
  • Constructs a sparse adjacency matrix using our SparseTensor backend.
  • Runs several epochs of training with the GCN-based model, printing the training loss and using the learned user/item embeddings for rating prediction.

The main purpose of this file is to show that the sparse backend, GNN layers, and MovieLens data can work together in a realistic end-to-end training loop.

Training gnn_movielens.py¶

The script trains a simple GCN-based recommender by combining sparse graph propagation with a standard regression objective. After filtering the MovieLens interactions, it builds a bipartite adjacency matrix in COO format, which serves as the message-passing structure for the model. SimpleGCNRec initializes user and item embeddings and updates them through stacked graph-convolution layers that operate directly on the sparse adjacency.

During training, each batch provides a set of user–item pairs, and the model retrieves their corresponding embeddings after GCN propagation. A dot product produces the rating prediction, and the parameters are optimized with MSE loss and SGD. The printed losses indicate how well the embeddings align with the observed ratings; consistent decrease suggests that the sparse GCN layers are integrating neighborhood information effectively and improving predictive quality.

In [ ]:
%cd /content/10714_course_project-main/src/apps
!python gnn_movielens.py
/content/10714_course_project-main/src/apps
Number of training interactions: 55375
Num users: 943, num items: 1682
Batch size: 1024, num_batches per epoch: 55
Start training...

Epoch 1/3 | Batch 10/55 | Loss (this batch): 0.7620
Epoch 1/3 | Batch 20/55 | Loss (this batch): 0.7189
Epoch 1/3 | Batch 30/55 | Loss (this batch): 0.6838
Epoch 1/3 | Batch 40/55 | Loss (this batch): 0.6516
Epoch 1/3 | Batch 50/55 | Loss (this batch): 0.6270
Epoch 1/3 | Batch 55/55 | Loss (this batch): 0.6329

Epoch 1/3 finished, avg loss = 0.7005

Epoch 2/3 | Batch 10/55 | Loss (this batch): 0.6529
Epoch 2/3 | Batch 20/55 | Loss (this batch): 0.6519
Epoch 2/3 | Batch 30/55 | Loss (this batch): 0.6338
Epoch 2/3 | Batch 40/55 | Loss (this batch): 0.5600
Epoch 2/3 | Batch 50/55 | Loss (this batch): 0.5752
Epoch 2/3 | Batch 55/55 | Loss (this batch): 0.4606

Epoch 2/3 finished, avg loss = 0.5969

Epoch 3/3 | Batch 10/55 | Loss (this batch): 0.4956
Epoch 3/3 | Batch 20/55 | Loss (this batch): 0.5493
Epoch 3/3 | Batch 30/55 | Loss (this batch): 0.5122
Epoch 3/3 | Batch 40/55 | Loss (this batch): 0.5082
Epoch 3/3 | Batch 50/55 | Loss (this batch): 0.5047
Epoch 3/3 | Batch 55/55 | Loss (this batch): 0.6145

Epoch 3/3 finished, avg loss = 0.5342

Test sparse Adj computation¶

We also include tests that focus on building the sparse adjacency matrix from the raw rating data.
These tests check things like:

  • The shape of the adjacency matrix,
  • The number of non-zero entries and basic sparsity properties,
  • Simple consistency checks

These tests help us confirm that the graph construction logic is correct before we plug the adjacency into the GCN model.

In [ ]:
from needle.data.movielens import read_ml100k_ratings, build_bipartite_adj_sparse

data, num_users, num_items = read_ml100k_ratings()
print(f"Number of users: {num_users}, number of items: {num_items}")
print("First 5 rows:")
print(data.head())

adj, num_users2, num_items2 = build_bipartite_adj_sparse(format="coo")
print(f"Adjacency SparseTensor built. num_users={num_users2}, num_items={num_items2}")
print("Adjacency shape:", adj.cached_data.shape)
print("Number of non-zeros (nnz):", adj.cached_data.nnz)
Number of users: 943, number of items: 1682
First 5 rows:
   user_id  item_id  rating  timestamp
0      196      242       3  881250949
1      186      302       3  891717742
2       22      377       1  878887116
3      244       51       2  880606923
4      166      346       1  886397596
Adjacency SparseTensor built. num_users=943, num_items=1682
Adjacency shape: (2625, 2625)
Number of non-zeros (nnz): 200000
In [ ]:
%cd /content/10714_course_project-main/src
!PYTHONPATH=/content/10714_course_project-main/src/python \
  pytest -v tests/test_movielens_gnn.py
/content/10714_course_project-main/src
============================= test session starts ==============================
platform linux -- Python 3.12.12, pytest-8.4.2, pluggy-1.6.0 -- /usr/bin/python3
cachedir: .pytest_cache
rootdir: /content/10714_course_project-main/src
plugins: typeguard-4.4.4, langsmith-0.4.55, anyio-4.12.0
collected 2 items                                                              

tests/test_movielens_gnn.py::test_movielens_load_and_stats PASSED        [ 50%]
tests/test_movielens_gnn.py::test_movielens_simplegcnrec_single_batch PASSED [100%]

============================== 2 passed in 1.52s ===============================

Memory usage and computing performance (dense vs sparse)

In [ ]:
!python benchmark_movielens_gnn.py
python3: can't open file '/content/10714_course_project-main/src/benchmark_movielens_gnn.py': [Errno 2] No such file or directory

The MovieLens corresponds to a sparsity level of roughly 97%, meaning only a small fraction of the dense matrix is actually used. When stored densely, the adjacency requires over 26 MB, while COO and BSR formats reduce this to about 3.9 MB and 5.9 MB respectively—an order-of-magnitude improvement.

The computational difference follows the same pattern. A dense adjacency multiplies every entry in the matrix, but the sparse version only processes the real edges. As a result, the forward pass drops from roughly 0.22 GFLOPs to about 0.006 GFLOPs. This reflects the true structure of the data: message passing only depends on existing user–item interactions, so sparse storage and computation match the problem much more naturally.

As datasets scale, this gap grows even wider. The number of users and items typically increases much faster than the number of interactions per user, which means sparsity becomes even more pronounced. In such settings, dense representations grow quadratically, while sparse storage and computation grow only with the number of actual edges. This trend makes sparse methods not just an optimization, but a practical requirement for larger recommendation or graph-learning systems.

Future Extensions¶

There are several kinds of possible ways that could extend the current framework.

Support for additional sparse formats.
COO and BSR cover many cases, but other formats likes CSR/CSC, Hybrid (HYB), or formats specialized for bipartite graphs. These could improve efficiency depending on graph structure. Automatic format selection based on sparsity patterns is another useful extension.

Mini-batch graph sampling.
Full-graph training is workable on MovieLens 100K dataset right now. However, the larger datasets would have much larger cost on here. Incorporating neighbor sampling or subgraph-based minibatching would allow the system to scale to millions of nodes while retaining sparse efficiency.

Improve the runtime in the other sides.
One natural direction is to further optimize the sparse kernels themselves. Dense matrix multiplication in mainstream libraries is extremely optimized, benefiting from decades of engineering, vectorization, tiling, and GPU support. Sparse operations, by comparison, require more careful handling of irregular memory access patterns and often run below their theoretical peak performance. With better kernel tuning, caching strategies, or specialized formats tailored to bipartite graphs, the sparse implementation could close more of the performance gap in wall-clock time while retaining its asymptotic advantages.

References¶

  • Duff, I. S., Grimes, R. G., & Lewis, J. G. (1989). Sparse Matrix Test Problems. ACM Transactions on Mathematical Software.

  • Duff, I. S., Marrone, M., Radicati, G., & Vittoli, A. (1986). Level 3 Basic Linear Algebra Subprograms for Sparse Matrices: a user-level interface.

  • Dongarra, J. J., Duff, I. S., Sorensen, D. C., & van der Vorst, H. A. (1991).
    A Set of Level 3 Basic Linear Algebra Subprograms. ACM TOMS.

  • Zhang, A., Luyichen, & others. (n.d.). MovieLens 100K dataset. GroupLens. Retrieved from https://grouplens.org/datasets/movielens/100k/

  • Dive into Deep Learning. (n.d.). Recommender Systems · MovieLens. Retrieved from https://classic.d2l.ai/chapter_recommender-systems/movielens.html