# Scaling Granite Code Models to 128K Context

###### Abstract

This paper introduces long-context Granite code models that support effective
context windows of up to 128K tokens. Our solution for scaling context length
of Granite 3B/8B code models from 2K/4K to 128K consists of a light-weight
continual pretraining by gradually increasing its RoPE base frequency with
repository-level file packing and length-upsampled long-context data.
Additionally, we also release instruction-tuned models with long-context
support which are derived by further finetuning the long context base models
on a mix of permissively licensed short and long-context instruction-response
pairs. While comparing to the original short-context Granite code models, our
long-context models achieve significant improvements on long-context tasks
without any noticeable performance degradation on regular code completion
benchmarks (e.g., HumanEval). We release all our long-context Granite Code
models under an Apache 2.0 license for both research and commercial use.

https://github.com/ibm-granite/granite-code-models

Matt Stallone Vaibhav Saxena Leonid Karlinsky Bridget McGinn Tim Bula Mayank
Mishra Adriana Meza Soria Gaoyuan Zhang Aditya Prasad Yikang Shen Saptha
Surendran Shanmukha Guttula Hima Patel Parameswaran Selvam Xuan-Hong Dang Yan
Koyfman Atin Sood Rogerio Feris

Nirmit Desai David D. Cox Ruchir Puri† Rameswar Panda†

IBM Research

†Corresponding Authors

<EMAIL_ADDRESS><EMAIL_ADDRESS>
##  1 Introduction

With the emergence and development of repository-level coding tasks (Liu et
al., 2024; 2023b) and software development agents (OpenDevin Team, 2024), long
context length becomes an important feature for code language models. While
many proprietary large language models, like GPT4, Gemini, and Claude, support
very long context windows, most open-source code language models could only
provide relatively short context windows (CodeGemma Team et al., 2024; Rozière
et al., 2023). This short context length limits the practicality of open-
source code language models in real-world software development.

In this paper, we introduce the long-context Granite code 3B and 8B, a series
of code language models that support effective context lengths up to 128K
tokens. To achieve the extended context length, we first continue pretrain
Granite Code 3B/8B base models with a repository-level code corpus and
upsample the longer context repositories. Then, we instruction tune the
continue pretrained model on a combination of short and long context
instruction data. Due to the lack of long context instruction data, we
generate multi-turn instruction data from repository-level file-packed
documents with our original Granite-8B-Code-Instruct model to avoid the
dependency on an existing long context model. More details of long context
extension can be found in Section 2.

To evaluate the ability of long-context Granite Code models, we conduct
extensive experiments on both short and long-context tasks, including
HumanEvalPack, Long Code Completion, RepoBench-P, RepoQA, and Key Retrieval.
Experiment results show that our long-context models significantly improve
long-context performances without noticeable degradation in short-context
performances. We open-source all our long-context Granite Code models under an
Apache 2.0 license for research and commercial use.

##  2 Long Context Modeling

Our solution for scaling context length of Granite code models consists of a
continual pretraining and an instruction tuning phase. Similar to prior works
(Fu et al., 2024), we hold the basic hypothesis that the ability to utilize
information at arbitrary input locations, is a capability that is mostly
already acquired through large-scale pretraining, and that this capability can
be readily extended to contexts substantially longer than seen during original
pretraining (e.g., 4K to 128K) through lightweight training on appropriate
data mixture.

###  2.1 Continual Pretraining

We continue pretrain the full attention Granite code base models using
sequence parallelism111https://github.com/jzhang38/EasyContext (Li et al.,
2021) by gradually increasing its RoPE base frequency without using any sparse
or linear attention. Specifically, we continue pretrain Granite Code 3B/8B
base models using the original pretraining data used in Mishra et al. (2024)
but with repository-level file packing and per-language context length
upsampling, that we found to be critical for long-context continual
pretraining. This continued training stage focused on a curated selection of
programming languages, such as Python, C, C++, Go, Java, JavaScript, and
TypeScript, as in Pinnaparaju et al. (2024).

To create long-context data, we develop a new approach that packs files from
the same repository together, arranging them to prioritize semantic
dependencies. We identify these dependencies by analyzing file imports and
create a directed acyclic graph, where each file is a node and edges represent
API imports between files. After breaking any cycles in the graph, we perform
a topological sort to establish an ordering of files based on their semantic
dependencies. We then organize the files in a repository by placing
documentation and build files first, followed by the ordered set of files with
semantic dependencies, and finally the remaining non-connected files. These
non-connected files are arranged according to their folder structure, using a
depth-first search to traverse the repository. Finally, we determine the
dominant programming language of a repository based on file extensions and
presence of build files, to organise repo-ordered files by programming
languages.

The documents’ lengths and their source domains/languages are two closely
related confounding factors in data engineering because long data usually come
from particular sources. Thus, in addition to repository-level file packing,
we artificially oversampled longer document sequences on a per-language basis
to ensure the quantity of long sequences, thereby improving the overall
quality of our training data corpus, as in Fu et al. (2024); Yu (2023). In
particular, we downsample documents under 4096 tokens to a rate of 10%, which
we find to ensure a sufficient number of total tokens and documents. The total
number of documents within the training corpus after processing is 173,336
with a mean length of 73,451.

We adjust the RoPE base frequency, introduced in Xiong et al. (2023), to
support long context windows up to 128K where the base model itself is trained
on 2K/4K context length. For training, we adopt a progressive approach where
we doubled the context window until it reached the desired length of 128K. We
train for 500 steps with a batch size of 32 and search for the optimal RoPE
theta and learning rate for each iteration. For RoPE theta, we finf optimal
values of 100K, 250K, 500K, 2M, and 10M for context windows of 8K, 16K, 32K,
64K, and 128K, respectively. We train with data parallelism and Flash
Attention 2 until 64K tokens and then used Ring Attention (Liu et al., 2023a)
to reach 128K tokens. The final models are trained for an extra 4B tokens
which is only 0.1% of original pretraining data.

###  2.2 Instruction Tuning

Our training data for long context instruct models consists of a combination
of permissively licensed data used in training the original Granite code
instruct models (Mishra et al., 2024), in addition to synthetically generated
code instruction datasets tailored for solving long context problems.
Specifically, the 128K long context instruct models are derived by further
finetuning the long context base models on a mix of short and long context
data as follows.

Short-Context Instruction Data. Our short context instruction data consists of
a combination of CommitPackFT (Muennighoff et al., 2023), MathInstruct222We
removed GSM8K-RFT and Camel-Math from MathInstruct due to unknown or NC
license. (Yue et al., 2023), MetaMathQA (Yu et al., 2023), Glaive-Code-
Assistant-v3333https://huggingface.co/datasets/glaiveai/glaive-code-
assistant-v3, Self-OSS-Instruct-
SC2444https://huggingface.co/datasets/bigcode/self-oss-instruct-sc2-exec-
filter-50k, Glaive-Function-
Calling-v2555https://huggingface.co/datasets/glaiveai/glaive-function-
calling-v2, NL2SQL666https://huggingface.co/datasets/bugdaryan/sql-create-
context-instruction, HelpSteer (Wang et al., 2023b),
OpenPlatypus777https://huggingface.co/datasets/garage-bAInd/Open-Platypus (Lee
et al., 2023), and a few synthetically generated datasets for API calling
(Basu et al., 2024), and multi-turn code interactions with execution feedback.

Long-Context Instruction Data. The long context instruction data was
synthetically generated by bootstrapping the pretraining data. For each
repository-level file-packed document, we created a multi-turn dataset where
the instructions within each sample were human-designed for the purpose of
enhancing the long-context performance in specific tasks like generation,
retrieval and translation. The responses were either parsed semantically from
the original document or generated using Granite-8b-Code-Instruct-4K. The
dataset first parses the document into classes, methods, and stand-alone
functions. It then requests and extracts the implementations of a random
subset of the extracted functions/methods (up to 5 per file in the document)
and then asks for an explanation of that implementation using available
documentation. Additionally, it generates instructions for implementing the
sampled functions (methods) based on the remaining documentation and code with
the function excluded. These questions and instructions were repeated for
different functions until the desired length was achieved.

By exposing the model to both short and long context data, we aim to enhance
its long context capability without sacrificing code generation performance at
short input context. For finetuning, we use a multiturn loss mask for each
sample, as in Wang et al. (2023a). This is particularly important as our
finetuning data corpus consists of instruction-response pairs with multiple
turns. However, when composing a sequence, we append an EOS token after each
response from the model to prevent runaway generation during inference. We
followed the same training parameters that produced our previous short-context
instruct models (Mishra et al., 2024): 128 global batch size, 2e-5 learning
rate, a noise multiplier of 5 for input embeddings, and padding-free
transformers.

##  3 Results

We evaluate our long-context Granite code models on a wide variety of
benchmarks by measuring key retrieval accuracy and performance during
generation on code completion tasks at both short and long-context length as
follows.

###  3.1 Benchmarks

Long Code Completion. Long Code Completion (LCC) (Guo et al., 2023) tests a
model’s ability to predict the next line of code from long repository-based
context for Python, Java, and C#. While the benchmark’s context length spans
1/2K through 8K+ tokens, it is heavily weighted around 2K tokens. Thus,
following Bai et al. (2024) and Rozière et al. (2023), we rebalance this
dataset for equal representation with each context length bucket (<4K, 2 – 4K,
4 – 8K, 8K+), where each bucket has 100 samples when possible.

Table 1: Exact Match (EM) performance on Long Code Completion (LCC) benchmark (Balanced). Long-context Granite code models consistently outperforms original base models at different input context from 4K to 32K. Model | 4K EM | 8K EM | 16K EM | 32K EM
---|---|---|---|---
Granite-3b-Code-Base-2K | 24.5 | 15.4 | 11.4 | 10.0
Granite-3b-Code-Base-128K | 54.6 | 56.8 | 52.2 | 57.8
Absolute Gap | \+ 30.1 | \+ 41.4 | \+ 40.8 | \+ 47.8
Granite-8b-Code-Base-4K | 41.9 | 23.7 | 19.1 | 15.0
Granite-8b-Code-Base-128K | 56.5 | 60.1 | 51.8 | 57.4
Absolute Gap | \+ 14.6 | \+ 36.4 | \+ 32.7 | \+ 42.4

RepoBench-P. Like LCC, RepoBench-P (Liu et al., 2023c) tests the model’s next
line code completion ability for long-context input. We follow the methodology
in (Bai et al., 2024) by selecting the Cross-File-First data but then we
rebalance the buckets based on the Starcoder tokenizer used for training out
Granite code models.

RepoQA. RepoQA (Liu et al., 2024) is an advanced Needle-in-the-Haystack test
that focuses on testing LLMs’ capabilities on long-context code understanding
and retrieval. Specifically, given a long chunk of source code and a precise
function description, and the model is asked to find the function in the
context that corresponds to the description. This benchmark focuses on
retrieving 10 needle functions from each of 5 languages x 10 repositories (500
sub-tasks/tests) with a set context size of 16K tokens.

Table 2: Exact Match (EM) scores on RepoBench-P (Balanced) benchmark. Model | 4K EM | 8K EM | 16K EM | 32K EM
---|---|---|---|---
Granite-3b-Code-Base-2K | 22.0 | 17.9 | 15.4 | 14.0
Granite-3b-Code-Base-128K | 39.8 | 46.8 | 43.1 | 45.3
Absolute Gap | \+ 17.8 | \+ 28.9 | \+ 27.7 | \+ 31.3
Granite-8b-Code-Base-4K | 27.9 | 23.0 | 15.7 | 7.8
Granite-8b-Code-Base-128K | 42.7 | 44.0 | 44.8 | 44.5
Absolute Gap | \+ 14.8 | \+ 21.0 | \+ 29.1 | \+ 36.7

Key Retrieval. This is a synthetic benchmark that tests the model’s ability to
find and execute a Python function buried within high-quality, syntactically
correct Python code. As proposed in Rozière et al. (2023), we took the Code
Contest finetuning dataset from Li et al. (2022) and concatenated Python
solutions around the key function. We then asked the model to return the
output of the key function by emulating a Python interpreter shell. We created
sequences of lengths of 512 tokens and key offsets of 512 tokens.

HumanEvalPack. To evaluate model performance at short-context length, we adopt
HumanEvalPack (Muennighoff et al., 2023), which extends Python problems of
Humaneval Benchmark to five additional commonly used programming languages,
namely JavaScript, Java, Go, C++, Rust to test three coding tasks (generation,
explanation and fixing). We evaluate our long-context models in a zero-shot
manner using greedy decoding with completion format for the base models, and
with instruction template for the instruction-tuned models.

###  3.2 Base Model Evaluations

Table 1 and Table 2 show the results of Granite 3B/8B code models before and
after long-context extension on LCC and RepoBench-P benchmarks respectively.
Prior Granite code models with 2K/4K support fail to generate meaningful
completions on long sequences. On the other hand, across all the context
length (4K to 32K), models scaled to handle long contexts up to 128K achieve
significantly higher performance. This demonstrates that long contexts are
informative for code completion, and long-context Granite code models are able
to effectively leverage this information to improve their generations on both
benchmarks.

In Table 3, we compare the performance of Granite code base models to their
counterparts prior to long-context extension. Our long-context models exhibit
strong retrieval performance across different matching thresholds, while the
short context versions mostly fail in finding the needle function
successfully. The absolute differences averaged over 5 programming languages
are very significant, e.g., $+38.6\%$ for Granite 8B model with a matching
threshold of 0.8. By looking at the score distribution across different
programming languages, we can see that both models are doing best at Python,
with 8B model consistently outperforming the 3B model. This result shows that
our long-context Granite code models can better understand natural language
description before retrieval, which aligns with the use of advanced code
search in many practical situations.

Table 3: Retrieval accuracy (%) of Granite code base models on RepoQA
benchmark evaluated using 16K context length at multiple thresholds of match
similarity. All models are evaluated using greedy decoding with 256 new token
limit.

Threshold | 0.0 | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0
---|---|---|---|---|---|---|---|---|---|---|---
Granite-3b-Code-Base-2K
Python | 6.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
C++ | 6.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Java | 4.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
TypeScript | 7.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Rust | 1.5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Average | 4.9 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Granite-3b-Code-Base-128K
Python | 76.0 | 57.0 | 54.0 | 49.0 | 44.0 | 40.0 | 34.0 | 30.0 | 28.0 | 25.0 | 20.0
C++ | 58.0 | 48.0 | 44.0 | 41.0 | 39.0 | 36.0 | 33.0 | 31.0 | 30.0 | 24.0 | 17.0
Java | 59.0 | 50.0 | 44.0 | 42.0 | 40.0 | 37.0 | 35.0 | 31.0 | 26.0 | 20.0 | 16.0
TypeScript | 58.0 | 38.0 | 34.0 | 33.0 | 29.0 | 27.0 | 23.0 | 23.0 | 23.0 | 16.0 | 7.0
Rust | 57.0 | 38.0 | 36.0 | 32.0 | 30.0 | 29.0 | 28.0 | 24.0 | 24.0 | 19.0 | 16.0
Average | 61.6 | 46.2 | 42.4 | 39.4 | 36.4 | 33.8 | 30.6 | 27.8 | 26.2 | 20.8 | 15.2
Absolute Gap | \+ 56.7 | \+ 46.2 | \+ 42.4 | \+ 39.4 | \+ 36.4 | \+ 33.8 | \+ 30.6 | \+ 27.8 | \+ 26.2 | \+ 20.8 | \+ 15.2
Granite-8b-Code-Base-4K
Python | 9.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0
C++ | 10.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 1.0 | 1.0
Java | 11.0 | 1.0 | 1.0 | 1.0 | 1.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
TypeScript | 9.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Rust | 11.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Average | 10.0 | 0.8 | 0.8 | 0.8 | 0.8 | 0.6 | 0.6 | 0.6 | 0.6 | 0.4 | 0.4
Granite-8b-Code-Base-128K
Python | 85.0 | 73.0 | 69.0 | 68.0 | 66.0 | 65.0 | 62.0 | 58.0 | 54.0 | 51.0 | 45.0
C++ | 60.0 | 45.0 | 42.0 | 40.0 | 37.0 | 35.0 | 35.0 | 34.0 | 32.0 | 27.0 | 23.0
Java | 57.0 | 52.0 | 48.0 | 44.0 | 42.0 | 39.0 | 38.0 | 36.0 | 32.0 | 28.0 | 23.0
Typescript | 64.0 | 55.0 | 49.0 | 48.0 | 44.0 | 40.0 | 38.0 | 36.0 | 35.0 | 28.0 | 12.0
Rust | 74.0 | 67.0 | 65.0 | 59.0 | 57.0 | 54.0 | 51.0 | 46.0 | 43.0 | 38.0 | 31.0
Average | 68.0 | 58.4 | 54.6 | 51.8 | 49.2 | 46.6 | 44.8 | 42.0 | 39.2 | 34.4 | 26.8
Absolute Gap | \+ 58.0 | \+ 57.6 | \+ 54.8 | \+ 51.0 | \+ 48.6 | +46.0 | \+ 44.2 | \+ 41.4 | \+ 38.6 | \+ 34.0 | \+ 26.4

Table 4: Retrieval accuracy (%) of Granite code instruct models on RepoQA
benchmark at different matching thresholds (larger represent closer to exact
match).

Threshold | 0.0 | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0
---|---|---|---|---|---|---|---|---|---|---|---
Granite-3b-Instruct-Base-2K
Python | 15.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
C++ | 10.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Java | 8.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
TypeScript | 11.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Rust | 9.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Average | 10.6 | 0.2 | 0.2 | 0.2 | 0.2 | 0.2 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Granite-3b-Code-Instruct-128K
Python | 76.0 | 60.0 | 55.0 | 54.0 | 50.0 | 48.0 | 42.0 | 41.0 | 40.0 | 38.0 | 33.0
C++ | 58.0 | 48.0 | 44.0 | 41.0 | 39.0 | 36.0 | 33.0 | 31.0 | 30.0 | 24.0 | 17.0
Java | 59.0 | 51.0 | 43.0 | 42.0 | 40.0 | 38.0 | 35.0 | 31.0 | 26.0 | 21.0 | 19.0
TypeScript | 80.0 | 68.0 | 54.0 | 50.0 | 43.0 | 39.0 | 36.0 | 35.0 | 29.0 | 20.0 | 9.0
Rust | 67.0 | 44.0 | 36.0 | 33.0 | 32.0 | 29.0 | 28.0 | 26.0 | 24.0 | 20.0 | 16.0
Average | 68.0 | 54.0 | 46.4 | 44.0 | 42.6 | 38.0 | 34.8 | 32.8 | 29.8 | 24.6 | 18.8
Absolute Gap | \+ 77.4 | \+ 53.8 | \+ 46.2 | \+ 43.8 | \+ 42.4 | \+ 37.8 | \+ 34.8 | \+ 32.8 | \+ 29.8 | \+ 24.6 | \+ 18.8
Granite-8b-Code-Instruct-4K
Python | 3.0 | 2.0 | 1.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
C++ | 10.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 1.0
Java | 8.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 0.
TypeScript | 10.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Rust | 4.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Average | 7.0 | 1.0 | 0.8 | 0.6 | 0.6 | 0.6 | 0.6 | 0.6 | 0.6 | 0.6 | 0.2
Granite-8b-Code-Instruct-128K
Python | 89.0 | 83.0 | 81.0 | 79.0 | 76.0 | 73.0 | 67.0 | 63.0 | 58.0 | 52.0 | 48.0
C++ | 63.0 | 51.0 | 46.0 | 42.0 | 41.0 | 37.0 | 36.0 | 30.0 | 24.0 | 15.0 | 3.0
Java | 91.0 | 84.0 | 79.0 | 77.0 | 76.0 | 73.0 | 69.0 | 66.0 | 63.0 | 46.0 | 39.0
TypeScript | 86.0 | 84.0 | 80.0 | 72.0 | 68.0 | 62.0 | 56.0 | 49.0 | 40.0 | 25.0 | 11.0
Rust | 83.0 | 78.0 | 73.0 | 67.0 | 65.0 | 63.0 | 60.0 | 55.0 | 53.0 | 48.0 | 40.0
Average | 82.4 | 76.0 | 71.8 | 67.4 | 65.2 | 61.6 | 57.6 | 52.6 | 47.6 | 37.2 | 28.2
Absolute Gap | \+ 75.4 | \+ 75.0 | \+ 71.0 | \+ 66.8 | \+ 64.6 | \+ 61.0 | \+ 57.0 | \+ 52.0 | \+ 47.0 | \+ 36.6 | \+ 28.0

###  3.3 Instruct Model Evaluations

Figure 1: Retrieval accuracy of Granite 3B/8B code instruct models before and
after scaling to 128K context length on RepoQA benchmark (with a matching
threshold of 0.5).

Table 4 compares the performance of long-context instruct models to their
short-context counterparts on RepoQA benchmark. As can be seen, our long-
context instruct models significantly outperforms short-context versions on
all 5 programming languages across different similarity thresholds. As an
illustration, figure 1 demonstrates the difference between short and long-
context models at similarity threshold of 0.5, where the performance of both
3B and 8B instruct models with 2K/4K context length support fails to achieve a
retrieval accuracy of more than 2% across 5 languages (on average 0.6% vs
61.6% for 8B instruct model). We attribute the improvements to the knowledge
learned from newly introduced synthetic long data for instruction tuning.

Figure 2: Key retrieval (a.k.a Needle-in-a-Haystack) performance of
Granite-8B-Code-Instruct with context scaling. X-axis represents sequence
length (tokens) and Y-axis represents key offset percent in retrieval. Best
viewed in color.

In Figure 2, we investigate key retrieval performance of our long-context
instruct models on a synthetic benchmark built on top of Python solutions
around a key function from Code Contest finetuning dataset (Li et al., 2022).
Note that this retrieval task is analogous to the famous famous Needle-in-a-
Haystack test, albeit tailored to code models. As can be seen from Figure 2,
our 8B instruct model before long-context extension only exhibit strong
retrieval performance up to 4K length, i.e., on the sequence length they were
originally trained on. On the other hand, our context scaling demonstrates a
perfect-all-green performance though we tend to view that this level of
retrieval is relatively easy for long-context code LLMs.

###  3.4 Short Context Evaluations

While our long-context models are very effective on long sequences, we observe
that our long-context scaling does not significantly change the short-context
generic capability on standard code synthesis benchmarks consisting of short
sequences. Table 5 summarizes the results on HumanEvalPack, where we find only
an average $\sim$1% degradation for the pass@1 metric on 3B and 8B models
respectively. We also test the HumanEval-Python performance in Figure 3 and
observe that long context extension has any noticeable performance
degradation. Interestingly, we notice improvements in HumanEval performance of
long-context instruct models, which we attribute to our new long-context
synthetic data added to instruction tuning. To summarize, while long-context
extension comes at a minimal cost for short sequences, we believe this cost is
more than offset by the potential of handling long sequences for many real
downstream applications.

Table 5: Pass@1 performance on HumanEvalPack benchmark (Muennighoff et al., 2023). All models are evaluated using greedy decoding with completion format for the base models, and instruction template for the instruction-tuned models.  Model | Prompt | Synthesis | Fix | Explain | Avg.
---|---|---|---|---|---
Granite-3b-Code-Base-2K | Completion | 33.0 | 19.5 | 22.2 | 24.9
Granite-3b-Code-Base-128K | Completion | 30.5 | 19.9 | 22.4 | 24.2
Granite-8b-Code-Base-4K | Completion | 43.1 | 29.1 | 25.4 | 32.5
Granite-8b-Code-Base-128K | Completion | 40.2 | 25.2 | 28.2 | 31.2
Granite-3b-Code-Instruct-2K | Instruct | 39.6 | 27.3 | 26.0 | 31.0
Granite-3b-Code-Instruct-128K | Instruct | 41.4 | 26.2 | 25.1 | 30.9
Granite-8b-Code-Instruct-4K | Instruct | 49.6 | 40.9 | 40.4 | 43.6
Granite-8b-Code-Instruct-128K | Instruct | 51.4 | 38.3 | 38.9 | 42.9
Figure 3: Effect of long-context extension on HumanEval benchmark. While we
observe a slight degradation in performance for base models, instruct models
see an improvement with long-context scaling, most likely due to our mixing of
short-context SFT data with long-context multi-turn synthetic data. Best
viewed in color.

##  4 Conclusion

We present long-context Granite code models (3B and 8B) that support effective
context lengths up to 128K tokens. We perform long context scaling by
leveraging a simple yet effective strategy consisting of a lightweight
continual pretraining followed by instruction tuning on a mix of short and
long-context data. Our long-context models demonstrate much superior
performance compared to their short-context counterparts without significantly
affecting the short-context generic capability. We believe that given our
current results, methods to enable even longer context length and circumvent
the quadratic computational complexity of attention computation will continue
to further evolve (Gu & Dao, 2023). We plan to continuously release updates to
these models to improve their performance and bringing the best of breed
approaches to IBM Granite Family.

## Acknowledgments

We would like sincerely thank IBM Research leaders - Dario Gil, Sriram
Raghavan, Mukesh Khare, Danny Barnett, Talia Gershon, Priya Nagpurkar,
Nicholas Fuller for their support. Thanks and acknowledgement to Michele
Merler, Shivdeep Singh, Manish Sethi, Pengyuan Li, Kun-Lung Wu, Syed Zawad,
Andrew Coleman, Matthew White, Mark Lewis, Raju Pavuluri, Boris Lublinsky,
Maximilien de Bayser, Ibrahim Abdelaziz, Kinjal Basu, Mayank Agarwal, Yi Zhou,
Chris Johnson, Aanchal Goyal, Yousaf Shah, Petros Zerfos, Heiko Ludwig, Asim
Munawar, Maxwell Crouse, Pavan Kapanipathi, Shweta Salaria, Bob Calio, Sophia
Wen, Seetharami Seelam, Brian Belgodere, Carlos Fonseca, Colm Malone, Ray
Rose, Amith Singhee, Trent Gray-Donald, Xuan Liu, Luis Angel Bathen, Abraham
Daniels, Anita Govindjee, Kate Soule, and Lan Hoang.

## References

  * Bai et al. (2024) Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li.  Longbench: A bilingual, multitask benchmark for long context understanding, 2024.  URL https://arxiv.org/abs/2308.14508.
  * Basu et al. (2024) Kinjal Basu, Ibrahim Abdelaziz, Subhajit Chaudhury, Soham Dan, Maxwell Crouse, Asim Munawar, Sadhana Kumaravel, Vinod Muthusamy, Pavan Kapanipathi, and Luis A Lastras.  Api-blend: A comprehensive corpora for training and benchmarking api llms.  _arXiv preprint arXiv:2402.15491_ , 2024.
  * CodeGemma Team et al. (2024) CodeGemma Team, Ale Jakse Hartman, Andrea Hu, Christopher A. Choquette-Choo, Heri Zhao, Jane Fine, Jeffrey Hui, Jingyue Shen, Joe Kelley, Joshua Howland, Kshitij Bansal, Luke Vilnis, Mateo Wirth, Nam Nguyen, Paul Michel, Peter Choy, Pratik Joshi, Ravin Kumar, Sarmad Hashmi, Shubham Agrawal, Siqi Zuo, Tris Warkentin, and Zhitao et al. Gong.  Codegemma: Open code models based on gemma.  2024\.  URL https://goo.gle/codegemma.
  * Fu et al. (2024) Yao Fu, Rameswar Panda, Xinyao Niu, Xiang Yue, Hannaneh Hajishirzi, Yoon Kim, and Hao Peng.  Data engineering for scaling language models to 128k context.  _arXiv preprint arXiv:2402.10171_ , 2024.
  * Gu & Dao (2023) Albert Gu and Tri Dao.  Mamba: Linear-time sequence modeling with selective state spaces.  _arXiv preprint arXiv:2312.00752_ , 2023.
  * Guo et al. (2023) Daya Guo, Canwen Xu, Nan Duan, Jian Yin, and Julian McAuley.  Longcoder: A long-range pre-trained language model for code completion, 2023.  URL https://arxiv.org/abs/2306.14893.
  * Lee et al. (2023) Ariel N. Lee, Cole J. Hunter, and Nataniel Ruiz.  Platypus: Quick, cheap, and powerful refinement of llms.  2023\.
  * Li et al. (2021) Shenggui Li, Fuzhao Xue, Chaitanya Baranwal, Yongbin Li, and Yang You.  Sequence parallelism: Long sequence training from system perspective.  _arXiv preprint arXiv:2105.13120_ , 2021.
  * Li et al. (2022) Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d’Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals.  Competition-level code generation with alphacode.  _Science_ , 378(6624):1092–1097, December 2022.  ISSN 1095-9203.  doi: 10.1126/science.abq1158.  URL http://dx.doi.org/10.1126/science.abq1158.
  * Liu et al. (2023a) Hao Liu, Matei Zaharia, and Pieter Abbeel.  Ring attention with blockwise transformers for near-infinite context, 2023a.  URL https://arxiv.org/abs/2310.01889.
  * Liu et al. (2024) Jiawei Liu, Jia Le Tian, Vijay Daita, Yuxiang Wei, Yifeng Ding, Yuhan Katherine Wang, Jun Yang, and Lingming Zhang.  Repoqa: Evaluating long context code understanding.  _arXiv preprint arXiv:2406.06025_ , 2024.
  * Liu et al. (2023b) Tianyang Liu, Canwen Xu, and Julian McAuley.  Repobench: Benchmarking repository-level code auto-completion systems.  _arXiv preprint arXiv:2306.03091_ , 2023b.
  * Liu et al. (2023c) Tianyang Liu, Canwen Xu, and Julian McAuley.  Repobench: Benchmarking repository-level code auto-completion systems, 2023c.  URL https://arxiv.org/abs/2306.03091.
  * Mishra et al. (2024) Mayank Mishra, Matt Stallone, Gaoyuan Zhang, Yikang Shen, Aditya Prasad, Adriana Meza Soria, Michele Merler, Parameswaran Selvam, Saptha Surendran, Shivdeep Singh, et al.  Granite code models: A family of open foundation models for code intelligence.  _arXiv preprint arXiv:2405.04324_ , 2024.
  * Muennighoff et al. (2023) Niklas Muennighoff, Qian Liu, Armel Zebaze, Qinkai Zheng, Binyuan Hui, Terry Yue Zhuo, Swayam Singh, Xiangru Tang, Leandro von Werra, and Shayne Longpre.  Octopack: Instruction tuning code large language models, 2023.
  * OpenDevin Team (2024) OpenDevin Team.  OpenDevin: An Open Platform for AI Software Developers as Generalist Agents.  https://github.com/OpenDevin/OpenDevin, 2024.  Accessed: ENTER THE DATE YOU ACCESSED THE PROJECT.
  * Pinnaparaju et al. (2024) Nikhil Pinnaparaju, Reshinth Adithyan, Duy Phung, Jonathan Tow, James Baicoianu, Ashish Datta, Maksym Zhuravinskyi, Dakota Mahan, Marco Bellagente, Carlos Riquelme, et al.  Stable code technical report.  _arXiv preprint arXiv:2404.01226_ , 2024.
  * Rozière et al. (2023) Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafiori, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve.  Code llama: Open foundation models for code, 2023.
  * Wang et al. (2023a) Yizhong Wang, Hamish Ivison, Pradeep Dasigi, Jack Hessel, Tushar Khot, Khyathi Raghavi Chandu, David Wadden, Kelsey MacMillan, Noah A. Smith, Iz Beltagy, and Hannaneh Hajishirzi.  How far can camels go? exploring the state of instruction tuning on open resources, 2023a.  URL https://arxiv.org/abs/2306.04751.
  * Wang et al. (2023b) Zhilin Wang, Yi Dong, Jiaqi Zeng, Virginia Adams, Makesh Narsimhan Sreedhar, Daniel Egert, Olivier Delalleau, Jane Polak Scowcroft, Neel Kant, Aidan Swope, and Oleksii Kuchaiev.  Helpsteer: Multi-attribute helpfulness dataset for steerlm, 2023b.
  * Xiong et al. (2023) Wenhan Xiong, Jingyu Liu, Igor Molybog, Hejia Zhang, Prajjwal Bhargava, Rui Hou, Louis Martin, Rashi Rungta, Karthik Abinav Sankararaman, Barlas Oguz, et al.  Effective long-context scaling of foundation models.  _arXiv preprint arXiv:2309.16039_ , 2023.
  * Yu et al. (2023) Longhui Yu, Weisen Jiang, Han Shi, Jincheng Yu, Zhengying Liu, Yu Zhang, James T Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu.  Metamath: Bootstrap your own mathematical questions for large language models.  _arXiv preprint arXiv:2309.12284_ , 2023.
  * Yu (2023) Yijiong Yu.  ” paraphrasing the original text” makes high accuracy long-context qa.  _arXiv preprint arXiv:2312.11193_ , 2023.
  * Yue et al. (2023) Xiang Yue, Xingwei Qu, Ge Zhang, Yao Fu, Wenhao Huang, Huan Sun, Yu Su, and Wenhu Chen.  Mammoth: Building math generalist models through hybrid instruction tuning.  _arXiv preprint arXiv:2309.05653_ , 2023.


mathx"17

# The faces of Convolution: from the Fourier theory to algebraic signal
processing

Feng Ji, Wee Peng Tay, and Antonio Ortega F. Ji and W. P. Tay are with the
School of Electrical and Electronic Engineering, Nanyang Technological
University, 639798, Singapore (e-mail<EMAIL_ADDRESS>wptay@ntu.edu.sg).
A. Ortega is with the Department of Electrical and Computer Engineering,
University of Southern California, Los Angeles, CA 90089-2564 (e-mail:
aortega@usc.edu).

##  I Introduction and motivations

> You have three faces. The first face, you show to the world. The second
> face, you show to your close friends and your family. The third face, you
> never show anyone. It is the truest reflection of who you are!
>
> A Japanese saying

Convolution is a prevalent concept in both signal processing and machine
learning. The early uses of the term “convolution” date back to the 1700s. In
_Recherches sur différents points importants du système du monde (1754)_ ,
D’Alembert used the convolution integral to derive Taylor’s theorem. The
expression

$\displaystyle\int f(u)g(x-u)\,\mathrm{d}u$ (1)

is used by S. Lacroix in _Treatise on differences and series (1797-1800)_.
Since then, the notion has appeared in numerous works, with different names.
The term “convolution” was popularized in the 1950s-1960s to be the specific
integral form in 1. This is the _first face_ of convolution.

In the 1930s-1940s, L. Pontryagin and other mathematicians (e.g., E. van
Kampen and A. Weil) laid down the foundations of the theory of Pontryagin
duality [1, 2]. The theory takes the point of view that the Fourier kernel
$e^{-i2\pi\xi(\cdot)}$ defines a duality between $\mathbb{R}$ and itself. The
entire Fourier theory can be built from such a duality. The formalism
preserves all familiar expressions in the classical theory, for example,
convolution still takes the formal expression 1. This vast generalization has
numerous applications in harmonic analysis, signal processing, and number
theory [2]. For example, the discrete Fourier transform (DFT) is the duality
between the finite cyclic group $\mathbb{Z}/n$ and itself.

In the new age of data and artificial intelligence, convolution is associated
with many concepts. For example, in computer vision, we have convolutional
neural networks (CNNs) [3], which involve pixel-wise multiplication with
kernels of small size. In graph signal processing (GSP) and graph neural
networks (GNN) [4, 5], we have the notion of graph convolution, which is
closely related to graph message passing. For example, the above-mentioned DFT
can also be interpreted as GSP on the directed cycle graph. With many
seemingly different constructions bearing the same name, it is natural to ask
whether there is any relationship between these concepts and if there is a way
to place them within a common general framework. As an attempt, algebraic
signal processing (ASP) [6] is proposed as a convolutional framework for such
a purpose.

However, if we compare ASP, an algebraic generalization of GSP, with the
Pontryagin theory, convolutions no longer take any concrete form similar to
that of (1), i.e., it shows up with a different face. ASP relies largely on
the point of view that convolutions are linear transformations and they form a
ring analogous to the polynomial ring. Therefore, it remains to elucidate the
relations between the classical and more recent approaches.

In this expository article, we provide a self-contained discussion of a
selected list of theories, each embedded with the concept of “convolution”:
from the classical Fourier theory to the theory of ASP. We aim to achieve a
few goals in this discussion:

  * •

We carefully describe, with emphasis on mathematical rigor, the setup of each
theory and explain how convolution is perceived. We illustrate with examples
of how convolution is defined in each theory.

  * •

By following the approximate historical timeline, we explain the relations
among various notions of convolutions. We identify rigorous relationships
between the different theories, where possible.

  * •

We provide an opinion on whether there is a consistent approach to convolution
under the current literature status.

Convolution has many different “faces”. Toward the end of this article, we
describe what we see that might be common to what we know. The highlight is
the observation that _(informally) convolution determines the Fourier theory_.

The rest of the paper is organized as follows. In Section II, we discuss the
classical Fourier theory. Its generalization is the Pontryagin theory, which
we provide a self-contained overview in Section III. In Section IV, we
introduce GSP, which offers a different but equivalent interpretation of
discrete Fourier transform in Section III. Thus far, the notion of convolution
has appeared in a few different forms. We compare them in Section V. In
Section VI, we describe the theory of ASP, which is a generalization of GSP.
An overview of all the theories is provided in Section VII. We give our point
of view of a unification of different theories in terms of convolution.

##  II The classical Fourier theory

It is no exaggeration to say that the classical notion of convolution is
embedded in the classical Fourier theory. Therefore, it is helpful to first
properly describe the Fourier theory [7, 8].

We denote the variables of (complexed valued) functions on the time domain and
frequency domains, both can be identified by $\mathbb{R}$, by $t$ and $\omega$
respectively. Formally, the Fourier transform takes the integral expression

$\displaystyle f\mapsto\widehat{f},\text{ with
}\widehat{f}(\omega)=\int_{-\infty}^{\infty}f(t)e^{-i2\pi
t\omega}\,\mathrm{d}t.$ (2)

Apparently, the integral cannot be defined unconditionally for any function.
We describe a few candidate domains of the Fourier transform as follows:

  * •

The space $C_{c}(\mathbb{R})$ of continuous functions with compact support. If
$f\in C_{c}(\mathbb{R})$, then for any $\omega$, $f(t)e^{-i2\pi t\omega}$ is
compactly supported and uniformly bounded (in $t$). Therefore,
$\widehat{f}(\omega)$ is well-defined. Moreover, the Plancherel theorem holds:

######  Theorem 1.

$\displaystyle\int_{-\infty}^{\infty}|f(t)|^{2}\,\mathrm{d}t=\int_{-\infty}^{\infty}|\widehat{f}(\omega)|^{2}\,\mathrm{d}\omega.$

  * •

The space $L^{1}(\mathbb{R})$ of integrable functions. If $f\in
L^{1}(\mathbb{R})$, then it is easy to verify that

$\displaystyle|\widehat{f}(\omega)|\leq\int_{-\infty}^{\infty}|f(t)e^{-i2\pi
t\omega}|\,\mathrm{d}t=\lVert f\rVert_{1}$

as $|e^{-i2\pi t\omega}|=1$. Therefore, the Fourier transform defines a
bounded linear map $L^{1}(\mathbb{R})\to L^{\infty}(\mathbb{R})$. Moreover,
the Riemman-Lebesgue lemma states that $\widehat{f}$ is a continuous function
vanishing at $\infty$ if $f\in L^{1}(\mathbb{R})$.

  * •

The space $L^{2}(\mathbb{R})$ of square integrable functions. We notice that
$C_{c}(\mathbb{R})$ is a dense subspace of $L^{2}(\mathbb{R})$. Therefore, for
any $f\in L^{2}(\mathbb{R})$, we find a sequence $(f_{i})_{i\geq\infty}$ of
functions in $C_{c}(\mathbb{R})$ such that $f_{i}\to f$ as $i\to\infty$ in
$L^{2}$-norm. By the Plancherel theorem, we observe that $\lVert
f_{i}-f_{j}\rVert_{2}=\lVert\widehat{f_{i}}-\widehat{f_{j}}\rVert_{2}$. As
$(f_{i})_{i\geq\infty}$ is a Cauchy sequence, so is
$(\widehat{f_{i}})_{i\geq\infty}$. Then $\widehat{f}$ is defined as the
$L^{2}$-limit of the Cauchy sequence $(\widehat{f_{i}})_{i\geq\infty}$. As a
consequence, the Plancherel theorem holds for any $f\in L^{2}(\mathbb{R})$.

In this case, the Fourier transform $\widehat{\cdot}:L^{2}(\mathbb{R})\to
L^{2}(\mathbb{R})$ is:

    1. (a)

Invertible: the inverse transform is defined by

$\displaystyle
f(t)=\int_{-\infty}^{\infty}\widehat{f}(\omega)e^{t2\pi\mathfrak{i}\mkern
1.0mu\omega}\,\mathrm{d}\omega.$

    2. (b)

Inner product preservation: for $f,g\in L^{2}(\mathbb{R})$, we have

$\displaystyle\int_{-\infty}^{\infty}f(t)\widehat{g}(t)\,\mathrm{d}t=\int_{-\infty}^{\infty}\widehat{f}(t)g(t)\,\mathrm{d}t.$

As a formal consequence, we conclude the following:

######  Theorem 2.

The Fourier transform is a unitary operator on the Hilbert space
$L^{2}(\mathbb{R})$.

More generally, the Fourier transform can be defined for tempered
distributions, which is the dual of the Schwartz space. We shall not pursue
this in the article and interested readers can find details in [8].

Having described the fundamental framework, we can now introduce convolutions.
It is the safest to consider $f,g\in C_{c}(\mathbb{R})$, their _convolution_
is defined by the following integral

$\displaystyle h(t)=f*g(t)=\int_{-\infty}^{\infty}f(z)g(t-z)\,\mathrm{d}z.$
(3)

The resulting function $h(\cdot)$ also belongs to $C_{c}(\mathbb{R})$.
Intuitively, the convolution $h(\cdot)$ can be viewed as a weighted sum of
$f(\cdot)$ with weight $g(\cdot)$ and vice versa.

We may apply the same integral formula for $f$ and $g$ from other function
spaces. For example, if $f,g\in L^{1}(\mathbb{R})$, then $h=f*g\in
L^{1}(\mathbb{R})$ as well and $\lVert h\rVert_{1}\leq\lVert
f\rVert_{1}\cdot\lVert g\rVert_{1}$. On the other hand, if $f,g\in
L^{2}(\mathbb{R})$, then $h=f*g$ does not necessarily belong to
$L^{2}(\mathbb{R})$; instead, $f*g\in L^{\infty}(\mathbb{R})$. The convolution
theorem relates convolution and Fourier transform.

######  Theorem 3.

If $f*g\in L^{1}(\mathbb{R})$ or $L^{2}(\mathbb{R})$, then

$\displaystyle\widehat{f*g}=\widehat{f}\cdot\widehat{g}.$

Moreover, $L^{1}(\mathbb{R})$ is a commutative and associative algebra with
convolution $*$ as the multiplication.

From this result, to generalize this classical notion of convolution to
functions on a general domain $A$, there are two options:

  * •

Formulate the integral as in (3).

  * •

Use the Fourier transform via the convolution theorem.

For the former approach, we need a translation operation “$-$” in $A$, while
for the latter option, we need to make sense of the Fourier transforms, in
particular, find an appropriate replacement of the integration kernel
$e^{-t2\pi\mathfrak{i}\mkern 1.0mu\omega}$ in $A$. In both cases, we require a
measure on $A$. All these can be accomplished for $A$ being a locally compact
abelian group as we shall discuss in the next section ([1, 2]).

##  III Pontryagin duality

Recall from the previous section that in order to introduce a Fourier theory
and convolution for functions on a domain $A$, we need the following
ingredients analogous to the classical theory:

  1. 1.

Algebraic condition: there is a translation on $A$.

  2. 2.

Analytic condition: there is a measure on $A$ to perform integrations.

  3. 3.

A family of “Fourier kernels”.

We go through these one-by-one. To fulfill the algebraic condition, we require
$A$ to be an abelian group. More details regarding algebraic concepts
introduced in the paper can be found in standard textbooks [9, 10, 11, 12].

######  Definition 1.

$A$ is an abelian group if there is a binary operation $+:A\times A\to A$,
called the addition, such that the following holds

  * •

Associativity: $a+b+c=a+(b+c)$ for $a,b,c\in A$.

  * •

Commutativity: $a+b=b+a$ for $a,b\in A$.

  * •

Existence of the identity: there is an element $0\in A$ such that $0+a=a$ for
any $a\in A$.

  * •

Existence of inverses: for $a\in A$, there is $-a\in A$ such that $a+(-a)=0$.

######  Example 1.

  1. 1.

$\mathbb{Z},\mathbb{R}$ and $\mathbb{C}$ are abelian groups with the usual
addition $+$.

  2. 2.

Let $S^{1}$ be the set of all complex numbers of (complex) norm $1$. Then it
is an abelian group under the complex multiplication $\times$, with $1$ as the
identity element. $S^{1}$ is called the circle group, as it can be visualized
as the unit circle on the complex plane.

  3. 3.

Let $\mathbb{Z}/n\mathbb{Z}$ be the finite set $0,\ldots,n-1$. Define $+$ on
$\mathbb{Z}/n\mathbb{Z}$ by taking sum as integers modulo $n$It is
straightforward to check that $\mathbb{Z}/n\mathbb{Z}$ is an abelian group
with $0$ as the identity. It is the cyclic group of order $n$.

As a consequence of the setup, we can perform translation on $A$, which is
nothing but addition with $-a$ for $a\in A$. When $A$ is $\mathbb{R}$, this
agrees with the usual notion of translation. To proceed with the analytic
condition on the existence of measure, we first impose a topological condition
on $A$.

######  Definition 2.

An abelian group $A$ is locally compact if there is a topology $\mathcal{T}$
on $A$ such that the following holds

  1. 1.

The binary operation $+:A\times A\to A$ is continuous (we endue $A\times A$
with the product topology).

  2. 2.

Taking inverse $-:A\to A,a\mapsto-a$ is continuous.

  3. 3.

Each $a\in A$ has a compact neighborhood, i.e., there is an open set $U$ and
compact set $K$ such that $a\in U\subset K$.

For example, $\mathbb{R},\mathbb{C}$, and $S^{1}$ are locally compact given
the usual Euclidean topology. While $\mathbb{Z}$ and $\mathbb{Z}/n\mathbb{Z}$
are locally compact given the discrete topology. An important property of a
locally compact abelian group is the existence of Haar measure.

######  Theorem 4.

If $A$ is a locally compact abelian group, there is a translation invariant
Radon measure $\mu$, called the Haar measure, on $A$. Moreover, it is unique
up to a scalar multiple.

Translation invariant in the theorem means that for any measurable set $U$ and
$a\in A$, we have $\mu(U)=\mu(U+a)$. The Lebesgue measure on each of
$\mathbb{R},\mathbb{C}$ and $S^{1}$ is the Haar measure. On $\mathbb{Z}$ and
$\mathbb{Z}/n\mathbb{Z}$, the discrete measure is the Haar measure.

For the last ingredient, we need to understand the Fourier kernel
$e^{-t2\pi\mathfrak{i}\mkern 1.0mu\omega}$ in the new context. Strictly
speaking, it is a common misconception to review
$\\{e^{-(\cdot)2\pi\mathfrak{i}\mkern 1.0mu\omega},\omega\in\mathbb{R}\\}$ as
an eigenbasis for some linear operator on a Hilbert space such as
$L^{2}(\mathbb{R})$. This is because it is not (square) integrable. Moreover,
this set of functions is uncountable. Maybe a more appropriate interpretation
is to view it as a character, which we introduce next.

######  Definition 3.

A function $\phi:A_{1}\to A_{2}$ from an abelian group $A_{1}$ to $A_{2}$ is
called a _homomorphism_ if $\phi(a+b)=\phi(a)+\phi(b)$ for $a,b\in A_{1}$,
i.e., $\phi$ preserves the addition. A bijective homomorphism is called an
isomorphism.

A _character_ of a locally compact abelian group $A$ is a continuous
homomorphism $\chi:A\to S^{1}$. The set $\widehat{A}$ of all characters of $A$
is called the _Pontryagin dual_ of $A$.

Two isomorphic groups are essentially the same in the algebraic sense, while
continuous homomorphism also respects the topologies.

Apparently, $\widehat{A}$ is also an abelian group with pointwise
multiplication in $S^{1}$. It carries the compact-open topology if $A$ is
locally compact.

######  Example 2.

  1. 1.

If $A=\mathbb{R}$, then for each $\omega$, we have a character
$\chi_{\omega}:\mathbb{R}\to S^{1}$ by the formula
$\chi_{\omega}(t)=e^{t2\pi\mathfrak{i}\mkern 1.0mu\omega}$. On the other hand,
for a character $\chi:\mathbb{R}\to S^{1}$, let
$\chi(1)=e^{2\pi\mathfrak{i}\mkern 1.0mu\omega}\in S^{1}$. As $\chi$ is a
homomorphism, one can easily verify that $\chi(t)=e^{t2\pi\mathfrak{i}\mkern
1.0mu\omega}$ for $t\in\mathbb{Q}$. Moreover, since $\chi$ is continuous, the
same formula holds for any $t\in\mathbb{R}$, i.e., $\chi=\chi_{\omega}$. In
conclusion, $\widehat{\mathbb{R}}$ can be identified with $\mathbb{R}$.

  2. 2.

If $A=\mathbb{Z}$, then one can use the same argument to show that
$\widehat{\mathbb{Z}}=\mathbb{R}/\mathbb{Z}\cong S^{1}$ using the fact that
$e^{2\pi\mathfrak{i}\mkern 1.0mu\omega}=e^{2\pi\mathfrak{i}\mkern
1.0mu(\omega+m)}$ for any $m\in\mathbb{Z}$. Conversely, it is also true that
$\widehat{S^{1}}=\mathbb{Z}$.

  3. 3.

If $A=\mathbb{Z}/n\mathbb{Z}$, then a character $\chi:A\to S^{1}$ is
determined uniquely by $\chi(1)=e^{2\pi\mathfrak{i}\mkern 1.0mu\omega}$ with
$\omega$ is any of number of the form $i/n,0\leq i\leq n-1$. Therefore,
$\widehat{A}$ can be identified with $A$.

The first example suggests interpreting the kernel of the Fourier transform as
a character of the group $\mathbb{R}$. Inspired by this observation, we are
prompted to define the Fourier transform analogously as an integral.

######  Definition 4.

For $f\in L^{1}(A)$, we define its Fourier transform
$\widehat{f}:\widehat{A}\to\mathbb{C}$, a function on $\widehat{A}$, by the
formula

$\displaystyle\widehat{f}(\chi)=\int_{A}f(a)\overline{\chi}(a)\,\mathrm{d}a,$

where $\chi\in\widehat{A}$ and $\,\mathrm{d}a$ is the Haar measure on $A$.

To be rigorous, let $V(A)$ be the complex span of continuous functions of
positive type on $A$. We do not formally define this technical term here.
However intuitively, the positive condition resembles that of the positive
semi-definiteness of matrices. We summarize the main results as follows (cf.
[2]), many of which can find their counterparts in the classical Fourier
theory.

######  Theorem 5.

  1. 1.

(Fourier inversion) There exists a Haar measure $\,\mathrm{d}\chi$ on
$\widehat{A}$ such that for all $f\in V^{1}(A)=V(A)\cap L^{1}(A)$,

$\displaystyle f(a)=\int\widehat{f}(\chi)\chi(a)\,\mathrm{d}\chi.$

Moreover, the Fourier transform $f\mapsto\widehat{f}$ identifies $V^{1}(A)$
with $V^{1}(\widehat{A})$.

  2. 2.

(Pontryagin duality) $A$ is self-dual, i.e., the evaluation map
$\alpha:A\to\widehat{\widehat{A}},\alpha(a)(\chi)=\chi(a)$ is a continuous
isomorphism.

  3. 3.

(The Plancherel theorem) The Fourier transform can be extended to a unitary
isometry of Hilbert spaces from $L^{2}(A)$ onto $L^{2}(\widehat{A})$.

These results describe a complete picture of what we expect from a Fourier
theory. In the following table, we summarize signal processing theories
corresponding to different choices of $A$ and $\widehat{A}$:

Theory | $A$ | $\widehat{A}$
---|---|---
Fourier transform | $\mathbb{R}$ | $\mathbb{R}$
Fourier series | $S^{1}$ | $\mathbb{Z}$
Discrete-time Fourier transform (DTFT) | $\mathbb{Z}$ | $S^{1}$
Discrete Fourier transform (DFT) | $\mathbb{Z}/n\mathbb{Z}$ | $\mathbb{Z}/n\mathbb{Z}$

It is worth mentioning that the framework has many other important
applications such as in number theory. A detailed discussion is beyond the
scope of the paper and interested readers may consult [13, 2].

With all the hard work that has laid down the foundation, introducing
convolution is just a matter of formality. For $f,g\in L^{1}(A)$, their
_convolution_ is defined as

$\displaystyle f*g(a)=\int g(a-b)f(b)\,\mathrm{d}b.$ (4)

The convolution $f*g$ exists for almost all $a\in A$ and $f*g\in L^{1}(A)$
satisfying $\lVert f*g\rVert_{1}\leq\lVert f\rVert_{1}\lVert g\rVert_{1}$. If
$f$ and $g$ are sufficiently regular, then the convolution theorem holds:
$\widehat{f*g}=\widehat{f}\cdot\widehat{g}$.

######  Corollary 1.

$L^{1}(A)$ is a commutative and associative (Banach) algebra with convolution
$*$ as the multiplication.

##  IV DFT, the directed cycle graph and GSP

As we have seen, a special case of the Pontryagin theory is DFT, when
$A=\widehat{A}=\mathbb{Z}/n\mathbb{Z}$. In this case, $A$ is a finite set and
hence all the function spaces on $A$ of interest can be identified
$\mathbb{C}^{n}$. Hence, linear operators such as the Fourier transform and
convolutions can be represented by matrices. For example, as we have seen in
Example 2, the characters of $A$ are $e^{2\pi\mathfrak{i}\mkern
1.0muj/n},0\leq j\leq n-1$. Therefore, the Fourier transform can be
represented by the matrix $\mathbf{U}$ with the $i,j$-th entry
$\mathbf{U}_{i,j}=e^{i2\pi\mathfrak{i}\mkern 1.0muj/n}$.

For the cyclic group $A$, we may also visualize it combinatorically. It can be
generated by the element $1$. The Cayley graph ([14]) $C_{n}$ associated with
this generator is the directed cycle graph of size $n$, i.e., there is a
directed edge from the node labeled by $i$ to the node labeled $i+1$ in $A$.
The matrix of eigenvectors of the adjacency matrix $\mathbf{A}_{C_{n}}$ of
$C_{n}$ is nothing but $\mathbf{U}$. Therefore, if we interpret a vector in
$\mathbb{C}^{n}$ as functions, or a signal, on the nodes of $C_{n}$, then the
DFT Fourier transform can be viewed as the linear transformation of the signal
space by the matrix of eigenvectors of $\mathbf{A}_{C_{n}}$. According to the
convolution theorem, convolution can be defined by componentwise
multiplication of the transformed signals.

If we extract the essential ingredients of the above combinatoric approach, we
need

  * •

a finite graph $G=(V,E)$ of size $|V|=n$

  * •

an operator (matrix) $\mathbf{S}$ associated with $G$ such that $\mathbf{S}$
has an orthonormal (or more generally, unitary) eigenbasis.

The operator $\mathbf{S}$ usually imitates a message passing on $G$, hence
called a _graph shift operator_. Typical examples of $\mathbf{S}$ include the
adjacency matrix of $G$, the Laplacian matrix of $G$, or their normalized
version. The theory of graph signal processing (GSP) [4, 15, 16, 17, 18, 19,
5, 20, 21, 22, 23, 24, 25] can be built upon such an $\mathbf{S}$. As we deal
with finite graphs, we do not need to worry about integrability. Therefore, it
is usually sufficient to use tools from linear algebra.

For the formal description of GSP, by the assumption, $\mathbf{S}$ has a
decomposition $\mathbf{S}=\mathbf{U}\bm{\Lambda}\mathbf{U}^{-1}$. A graph
signal is a function $V\to\mathbb{C}$. As $V$ is finite, such a signal can be
identified with a vector $\mathbf{x}$ in $\mathbb{C}^{n}$. Each component of
$\mathbf{x}$ corresponds to a node $v\in V$. Therefore, the domain of
$\mathbf{x}$ is called the graph domain. Usually, a linear transformation of
the space of graph signals is also called a _filter_. Here we consider complex
signals inconsistent with the classical Fourier theory, though most GSP
literature and applications use real signals.

The graph Fourier transform (GFT) of a graph signal $\mathbf{x}$ is

$\displaystyle\widehat{\mathbf{x}}=\mathbf{U}^{-1}\mathbf{x}.$

Its inverse is given by the inverse graph Fourier transform (IGFT)

$\displaystyle\mathbf{x}=\mathbf{U}\widehat{\mathbf{x}}.$

The codomain of GFT is called the frequency domain. Each component of the
frequency domain corresponds to an eigenvector $\mathbf{u}_{i}$ of
$\mathbf{S}$. The vector $\mathbf{u}_{i}$ is also a graph signal and
intuitively, it corresponds to a certain mode of signal fluctuation on $G$.

To introduce convolution, it is most convenient to take the analogy of the
equivalent formulation in the classical convolution theorem Theorem 3. More
precisely, for two graph signals $\mathbf{x},\mathbf{y}$, then their
convolution $\mathbf{z}=\mathbf{x}*\mathbf{y}$ is determined by

$\displaystyle\widehat{\mathbf{z}}=\widehat{\mathbf{x}}\odot\widehat{\mathbf{y}},$
(5)

where $\odot$ is the Hadamard product or component-wise multiplication.

If $\mathbf{x}$ is fixed, then taking convolution with it defines a linear
transformation, also called a _convolution filter_ , on the signal space:
$\mathbf{x}*:\mathbb{C}^{n}\to\mathbb{C}^{n},\mathbf{y}\mapsto\mathbf{x}*\mathbf{y}$.
The convolution theorem for GSP reads as follows.

######  Theorem 6.

If $\mathbf{S}$ does not have repeated eigenvalues, then for each convolution
filter $\mathbf{x}*$, there is a unique polynomial $P_{\mathbf{x}}(\cdot)$ of
degree at most $n-1$ such that the matrix form of $\mathbf{x}*$ is
$P_{\mathbf{x}}(\mathbf{S})$. Therefore, the set of convolution filters agrees
with the polynomial algebra of matrices in $\mathbf{S}$.

Moreover, a filter $\mathbf{M}$ is shift-invariant w.r.t. $\mathbf{S}$, i.e.,
$\mathbf{M}\circ\mathbf{S}=\mathbf{S}\circ\mathbf{M}$, if and only if it is a
convolution filter.

This result is useful as in theory, it gives yet another point-of-view of the
notion of convolution in the graph context. In practice, to perform
convolution, explicit eigendecomposition is not needed and one only has to
compute polynomials in $\mathbf{S}$. This also facilitates learning and
estimation as a parameterized model. Many interesting filters belong to the
convolution family including the band-pass filters. Moreover, they are
extensively used in graph neural networks to be discussed in the next section.

In this section, we consider $\mathbb{C}$ as the base field for the connection
with the previous sections. In most applications, it is sufficient to use
$\mathbb{R}$ as the base field, which will be assumed for subsequent sections
unless otherwise stated.

##  V CNN v.s. GNN

The term “convolution” is omnipresent in the era of artificial intelligence
[3, 26, 27, 28, 5]. In this section, we compare its usage in CNN for the field
of computer vision and GNN for graph neural networks.

For CNN, we shall only discuss the fundamental architecture eyeing to explain
the meaning of convolution (based on [3]). We model an image by a compactly
supported function on the (infinite) $2$D-lattice
$A=\mathbb{Z}\oplus\mathbb{Z}$ as follows. If the size of the image is
$w\times h$, we fit the lower left corner of the image with the origin and
each pixel corresponds to a node on the integer lattice. (as illustrated in
Fig. 1). We construct a function $f$ on $A$ as follows: $f(a,b)$ is the pixel
value at the $(a+1,b+1)$-th position of the image if $0\leq a\leq w-1,0\leq
b\leq h-1$; and otherwise, $f(a,b)=0$.

Figure 1: The setup for the basic CNN architecture.

On the other hand, for the proto-typical example of a $3\times 3$ convolution
kernel, we can model it by any function $g$ on $A$ supported on the $9$
lattice points $\\{-1,0,1\\}\times\\{-1,0,1\\}$ (as illustrated in Fig. 1).
Notice that $A$ is a locally compact abelian group. Then the convolution of
the image in CNN with stride $1$ is exactly $f*g$ given by the formula (4) in
Section III.

Encouraged by the success of convolution in computer vision, it is natural to
anticipate similar architectures for graph-structured data. However, there is
the major challenge that for a general graph $G$, unlike the 2$D$-lattice,
each node may have completely different neighborhood structures, for example,
different nodes usually have different degrees. The community quickly came to
the consensus that convolution from GSP (Section IV) should be the “correct
counterpart” to design graph neural networks. As a natural consequence, the
following GCN model [5] is proposed, which serves as the prototype for most of
the more sophisticated architectures [29, 30, 31, 32, 33].

For an undirected graph $G$, fix a graph shift operator $\mathbf{S}$, such as
the Laplacian or the normalized Laplacian of $G$ with self-loop. Suppose
$\mathbf{X}$ is a feature matrix such that the $i$-th row of $\mathbf{X}$ is
the feature vector associated with the $i$-th node. Set $\mathbf{W}$ to be a
learnable re-scaling matrix and $P$ to be a polynomial with learnable
coefficients. Then the building block of the GCN model is the following graph
convolution layer

$\displaystyle\theta(\mathbf{X})=P(\mathbf{S})\mathbf{X}\mathbf{W}.$

Rather than discussing various improvements of this fundamental model, which
is not the aim of this paper, we want to compare “convolution” in CNN and GNN.
For simplicity, we only consider information aggregation from the immediate
neighbors of each node and there is no feature scaling. Then for CNN, we use a
$3\times 3$ convolution filter, while for GNN, $P$ has degree $1$. An apparent
difference is that the former has $9$ degrees of freedom, while the latter has
only $2$ degrees of freedom. The implicit abelian group structure of a
$2$D-lattice makes the neighborhood of each node identical. More generally,
each node can be viewed as the center of the lattice. Therefore, the
convolution for CNN exploits this property such that the kernel can be both
local and sufficiently expressive. While for GNN, due to irregular
neighborhood structures, the convolution compromises by assigning the same
weight to the contribution of every neighborhood of all the nodes.
Intuitively, the convolution for CNN is “directional” while that of GNN is
“radial”.

##  VI Algebraic signal processing

GSP has the simplicity that the entire theory can be established given a
single operator $\mathbf{S}$. The graph structure is only used once to
construct such a matrix and the rest of GSP follows a formal procedure in
(linear) algebra. The essential ingredients of the algebraic approach are
reorganized to formulate the theory of algebraic signal processing (ASP) [6],
which founds applications outside the realm of graphs.

We remark that strictly speaking, it is inaccurate to claim that ASP is
derived from GSP. In the literature, ASP was proposed before the formal
introduction of GSP. However, it is more natural to view ASP as a
generalization of GSP as we discussed above.

To present ASP, we first introduce a few algebraic concepts.

######  Definition 5.

A _ring_ $R$ is a set with two binary operations $+,\times$ with the following
properties

  1. 1.

$R$ is an abelian group with $+$ with the identity $0$.

  2. 2.

The multiplication $\times$ on $R$ isassociative. By convention, we may also
denote $\times$ by $\cdot$ or omit it if no confusion arises.

  3. 3.

The multiplication $\times$ is distributive w.r.t. $+$, i.e.,
$r_{1}\cdot(r_{2}+r_{3})=r_{1}\cdot r_{2}+r_{1}\cdot r_{3}$ and
$(r_{2}+r_{3})\cdot r_{1}=r_{2}\cdot r_{1}+r_{3}\cdot r_{1}$.

$R$ is called commutative if $\times$ is commutative. It is called _unital_ if
there is a multiplicative identity $1$ such that $1\cdot r=r\cdot 1=r$ for any
$r\in R$.

######  Example 3.

  1. 1.

A unital commutative ring $R$ is called a _field_ if $R\backslash\\{0\\}$ is
also an abelian group under $\times$. For example, $\mathbb{R}$ and
$\mathbb{C}$ are both fields, while the ring of integers $\mathbb{Z}$ is not a
field as elements such as $2$ are not invertible in $\mathbb{Z}$.

  2. 2.

The set of $n\times n$ matrices $M_{n}(\mathbb{R})$ is a unital ring under the
usual matrix addition and multiplication. However, matrix multiplication is
not commutative. It can be identified with the _endomorphism ring_
$\text{End}(\mathbb{R}^{n})$ of linear transformation from $\mathbb{R}^{n}$ to
itself, with composition as the multiplication.

  3. 3.

Let $R$ be a commutative ring such as $\mathbb{Z},\mathbb{R}$ and
$\mathbb{C}$. Then the set of polynomials $R[t]$ with coefficients in $R$
forms the (unital) _polynomial ring_.

  4. 4.

The set of integrable functions $L^{1}(\mathbb{R})$ is a commutative ring with
the usual function addition and convolution $*$ as the multiplication.
However, it is not unital, while only has an approximate identity.

While the notion of ring generalizes that of field such as
$\mathbb{R},\mathbb{C}$, we have a corresponding generalization of the notion
of vector space.

######  Definition 6.

Given a ring $R$, an abelian group $M$ is a _module over $R$_ if there is a
scalar multiplication $\cdot:R\times M\to M$ (the symbol “$\cdot$” is often
omitted) such that the following holds for $r,r^{\prime}\in R$ and $x,y\in M$

  1. 1.

$r\cdot(x+y)=r\cdot x+r\cdot y$.

  2. 2.

$(r+r^{\prime})\cdot x=r\cdot x+r^{\prime}\cdot x$.

  3. 3.

$(rr^{\prime})\cdot x=r\cdot(r^{\prime}\cdot x)$.

  4. 4.

$1\cdot x=x$.

A subset $M^{\prime}$ of $M$ is called a submodule over $M$ if $rx\in
M^{\prime}$ for any $x\in M^{\prime}$. $M$ is irreducible if the only
submodule of $M$ are the obvious ones $\\{0\\}$ and $M$.

######  Definition 7.

If we have two modules $M_{1},M_{2}$ over $R$, there _direct sum_ $M_{1}\oplus
M_{2}$ consists of pairs $(x_{1},x_{2}),x_{1}\in M_{1},x_{2}\in M_{2}$. It is
a also a module over $R$ with $r(x_{1},x_{2})=(rx_{1},rx_{2})$.

######  Example 4.

  1. 1.

The vector space $\mathbb{R}^{n}$ is a module over $\mathbb{R}$. Moreover, it
is also a module over the matrix ring $M_{n}(\mathbb{R})$. Fix any matrix
$\mathbf{M}\in M_{n}(\mathbb{R})$, then $\mathbb{R}^{n}$ is a module over the
polynomial ring $\mathbb{R}[t]$ with
$P(t)\cdot\mathbf{x}=P(\mathbf{M})\mathbf{x}$ for any polynomial $P(t)$ and
vector $\mathbf{x}$. If the normal form of $\mathbf{M}$ has a Jordan block of
size $m$ with eigenvalue $\lambda$, then $\mathbb{R}^{n}$ has a
$m$-dimenisonal submodule over $\mathbb{R}[t]$. In general, $\mathbb{R}^{n}$
is the direct sum of irreducible submodules, each corresponding to a Jordan
block of the normal form of $\mathbf{M}$.

  2. 2.

For a ring $R$, it is a module over itself with module scalar multiplication
the same as the ring multiplication. A submodule $I\subset R$ is called an
_ideal_ of $R$. For example, the even numbers
$\\{\ldots,-4,-2,0,2,4,\ldots\\}$ is an ideal of the integer ring
$\mathbb{Z}$.

If $R$ is commutative, an ideal $\mathfrak{p}$ is _prime_ if it is not the
product of different ideals other than $0$ and $R$. For example, in
$\mathbb{Z}$, a prime ideal takes the form $\\{pm\mid m\in\mathbb{Z}\\}$ for
some prime number $p$. In commutative algebra and algebraic geometry, the set
of prime ideals is called the _spectrum_ of $R$ [9].

In each of Example 3 2)-4), there is a hidden base ring $R$. This gives an
additional structure to either example, which we formalize as follows.

######  Definition 8.

Let $R$ be a commutative ring (usually chosen as a field such as $\mathbb{R}$
or $\mathbb{C}$). A ring $A$ is an $R$-algebra or an algebra over $R$ if $A$
is a module over $R$ such that $(ra)a^{\prime}=r(aa^{\prime})$ for any $r\in
R,a,a^{\prime}\in A$.

If we have the same algebraic structure such as ring, module, or algebra on
sets $S_{1},S_{2}$, then a function $\phi:S_{1}\to S_{2}$ is a _homomorphism_
if it preserves the respective algebraic structure. It is an _isomorphism_ if
it is invertible, which essentially identifies $S_{1}$ and $S_{2}$.

Having introduced all the necessary concepts, we can describe ASP. It requires
the data $(\mathcal{A},\mathcal{M},\rho)$, where $\mathcal{A}$ is an unital
algebra (over a base field), $\mathcal{M}$ is a vector space, and
$\rho:\mathcal{A}\to\text{End}(\mathcal{M})$ is an algebra homomorphism of
$\mathcal{A}$ into the endomorphism ring of $\mathcal{M}$ (cf. Example 3 2)).
The map $\rho$ makes $\mathcal{M}$ an $\mathcal{A}$-module with

$\displaystyle a\cdot x=\rho(a)x,a\in\mathcal{A},x\in\mathcal{M}.$

It is usually assumed that $\mathcal{M}$ is finitely generated as an
$\mathcal{A}$-module.

######  Example 5.

In this example, we explain how GSP fits into the ASP framework. Consider a
graph $G$ of size $n$ and $\mathbf{S}$ a chosen graph shift operator (GSO).
Similar to Example 4 1), let $\mathcal{A}$ be the polynomial ring
$\mathbb{R}[t]$ in a single variable $t$ and $\mathcal{M}$ be the signal space
$\mathbb{R}^{n}$ on $G$. Then the endomorphism ring $\text{End}(\mathcal{M})$
is nothing but the matrix ring $M_{n}(\mathbb{R})$. The map
$\rho:\mathbb{R}[t]\to M_{n}(\mathbb{R}),t\mapsto\mathbf{S}$ is the setup for
graph signal processing (GSP). It is worth pointing out that the ring
$\mathcal{A}$ is a principal ideal domain, whose structure theorem says that
$\mathcal{M}$ can be decomposed into $1$-dimenision irreducible submodules
[12].

ASP has the following interpretations of the key concepts we are interested
in:

  * •

In ASP, the _Fourier transform_ is a decomposition of $\mathcal{M}$ into a
direct sum of ($1$-dimensional) irreducible submodules
$\Delta:\mathcal{M}\to\oplus_{w\in W}\mathcal{M}_{w}$, where $W$ is the index
set that also corresponds to the coordinates of the _frequency domain_.

  * •

In ASP, a _convolution_ is
$\rho(a)\in\text{End}(\mathcal{M}),a\in\mathcal{A}$. This corresponds to the
property that, in GSP, a convolution is a polynomial in the generators of
$\mathcal{A}$.

  * •

In ASP, a bandlimited space is a submodule of $\mathcal{M}$, which is
isomorphic to the direct sum of irreducible submodules.

The framework places the algebra $\rho(\mathcal{A})$ at the center of the
stage. As we have seen, in GSP, $\mathcal{A}=\mathbb{R}[t]$ and
$\rho(t)=\mathbf{S}$ for a chosen shift operator. In contrast, we illustrate
how this idea can be applied for lattice signal processing [34] without using
a single shift operator.

######  Example 6.

We describe lattice signal processing in this example. Instead of giving all
the details, we explain how the shifts and the associated matrix algebra are
defined, which is sufficient to apply the ASP framework.

Let $\mathcal{L}$ be a _meet semilattice_ of size $n$. This means that
$\mathcal{L}$ has a partial order $\leq$ that “compares” elements of
$\mathcal{L}$, with the following properties

  1. 1.

$a\leq a$ for any $a\in\mathcal{L}$.

  2. 2.

If $a\leq b,b\leq a$, then $a=b$.

  3. 3.

If $a\leq b,b\leq c$, then $a\leq c$.

  4. 4.

For $a,b\in\mathcal{L}$, there is a unique greatest lower bound (in terms of
$\leq$) $a\wedge b$, called the _meet_.

A signal $\mathbf{s}=\\{s_{a},a\in\mathcal{L}\\}$ assigns a number $s_{a}$ to
each $a\in\mathcal{L}$. For each $a\in\mathcal{L}$, we define a shift
$\mathbf{T}_{a}$ by requiring

$\displaystyle\mathbf{T}_{a}(\mathbf{s})=(s_{b\wedge a})_{b\in\mathcal{L}}.$

Intuitively, the signal on each $b\in\mathcal{L}$ is “shifted” to its meet
with $a$.

One verifies that $\\{\mathbf{T}_{a},a\in\mathcal{L}\\}$ are pairwise
commutative as $\mathbf{T}_{a}\circ\mathbf{T}_{a^{\prime}}=\mathbf{T}_{a\wedge
a^{\prime}}=\mathbf{T}_{a^{\prime}\wedge a}$. The shifts have a common
eigenbasis. By taking compositions and linear combinations in
$M_{n}(\mathbb{R})$, they form the required algebra $\mathcal{A}$ (with $\rho$
the identity map). As an application, the theory can be used for sampling in
auction [34].

##  VII Towards a unification

So far, we have briefly described two major approaches to having a “Fourier
theory”, namely, the Pontryagin theory and the theory of ASP. We summarize
their major differences in the following table.

TABLE I: The difference between the Pontryagin theory and the theory of ASP.

| Pontryagin | ASP
---|---|---
Signal space | Infinite dimensional | Finite dimensional
Domain symmetry | Group | Irregular
Fourier kernel | Characters | Vector space basis
Measure | Haar | “Not required”
Tools | Algebra, topology, analysis | Algebra, combinatorics

Technically, the Pontryagin theory and ASP are loosely hinged on DFT, which
can be interpreted with both a finite cyclic group and a finite directed cycle
graph. The relations among them and their specializations can be visualized
with a Venn diagram Fig. 2.

Figure 2: Relations among the theories discussed.

However, intuitively, any Fourier theory intends to analyze a signal by
inspecting its “response” to different frequency modes. Hence, there should be
a certain point of view that we can (partially) unify all the theories
technically. The classical Fourier theory starts with the Fourier transform.
While convolution can be introduced independently, it is usually associated
with Fourier transform as multiplication in the frequency domain. ASP turns
the table around by starting with a module structure of a vector space
$\mathcal{M}$ over an algebra $\mathcal{A}$. The frequency domain is
subsequently introduced as the index set of a module decomposition. Inspired
by this and a classical result of Gelfand, we propose to understand the
theories in terms of the convolution algebra of the signal space as follows.

For simplicity, we consider mainly the Pontryagin theory and GSP. If $A$ is a
locally compact abelian group, we consider the signal space
$\mathcal{S}=L^{1}(A)$. On the other hand, for GSP, we consider the signal
space $\mathcal{S}=\mathbb{R}^{n}$. In the former case, $\mathcal{S}$ is a
Banach algebra under convolution as in Corollary 1. For GSP, we define an
algebra structure $\mathcal{S}=\mathbb{R}^{n}$, called the convolution
algebra, with multiplication given by the convolution $*$ as in (5).

A _character_ of $\mathcal{S}$ is a continuous algebra homomorphism from
$\mathcal{S}$ to the base field, which is $\mathbb{C}$ and $\mathbb{R}$ for
the Pontryagin theory and GSP respectively. The set of nonzero characters is
denoted by $\widehat{\mathcal{S}}$. In theory, $\widehat{\mathcal{S}}$ is
uniquely determined by $\mathcal{S}$. Furthermore, $\mathcal{S}$ determines
the Fourier transform in the following sense.

######  Theorem 7.

There is a bijection between $\widehat{\mathcal{S}}$ and the Fourier kernel.

###### Proof.

If $A$ is a locally compact abelian group and $\chi\in\widehat{A}$, we define
a character $\nu_{\chi}:\mathcal{S}\to\mathbb{C}$ by the formula:

$\displaystyle\nu_{\chi}(f)=\widehat{f}(\chi)=\int_{A}f(a)\overline{\chi}(a)\,\mathrm{d}a.$

This defines a bijection between $\widehat{A}$ and $\widehat{S}$ according to
[8] p.218 or [2] 3-11.

For GSP, recall the Fourier transform is given by a base change
$\mathbf{U}:\mathbb{R}^{n}\to\mathbb{R}^{n}$, where $\mathbf{U}$ is an
orthogonal matrix. The algebra structure on $\mathcal{S}$ can be explicitly
expressed as
$\mathbf{U}\big{(}\mathbf{U}^{-1}(\mathbf{x})\odot\mathbf{U}^{-1}(\mathbf{y})\big{)}$.
It suffices to show that the columns $\mathbf{u}_{i},1\leq i\leq n$ of
$\mathbf{U}$ are uniquely determined by $\widehat{\mathcal{S}}$.

For each $\mathbf{u}_{i}$, we associate it with
$\nu_{i}\in\widehat{\mathcal{S}}$ by the formula
$\nu_{i}(\mathbf{x})=\langle\mathbf{u}_{i},\mathbf{x}\rangle$. As it is just
the $i$-th component of GFT, $\nu_{i}$ respects the mutliplication in
$\mathcal{S}$ and hence $\nu_{i}\in\widehat{\mathcal{S}}$.

In the reverse direction, for $\nu\in\widehat{\mathcal{S}}$, it is a linear
transformation $\mathcal{S}\to\mathbb{R}$. Therefore, there is a nonzero
vector $\mathbf{x}_{\nu}$ such that
$\nu(\mathbf{y})=\langle\mathbf{x}_{\nu},\mathbf{y}\rangle$ for any
$\mathbf{y}\in\mathcal{S}$. Moreover, $\nu$ respects the multiplication of
$\mathcal{S}$, and hence for $\mathbf{u}_{i},\mathbf{u}_{j},1\leq i,j\leq n$,
we have

$\displaystyle\nu(\mathbf{u}_{i})\nu(\mathbf{u}_{j})=\langle\mathbf{x}_{\nu},\mathbf{u}_{i}\rangle\langle\mathbf{x}_{\nu},\mathbf{u}_{j}\rangle=\langle\mathbf{x}_{\nu},\mathbf{u}_{i}*\mathbf{u}_{j}\rangle=\nu(\mathbf{u}_{i}*\mathbf{u}_{j}).$
(6)

Notice that $\mathbf{u}_{i}*\mathbf{u}_{j}=\mathbf{u}_{i}$ if $i=j$ and $0$
otherwise. Therefore, for some $1\leq i_{\nu}\leq n$,
$\langle\mathbf{x}_{\nu},\mathbf{u}_{i_{\nu}}\rangle\neq 0$ and
$\langle\mathbf{x}_{\nu},\mathbf{u}_{i_{\nu}}\rangle^{2}=\langle\mathbf{x}_{\nu},\mathbf{u}_{i_{\nu}}\rangle$.
We have $\langle\mathbf{x}_{\nu},\mathbf{u}_{i_{\nu}}\rangle=1$. Moreover, for
$j\neq i_{\nu}$, (6) implies that

$\displaystyle\langle\mathbf{x}_{\nu},\mathbf{u}_{j}\rangle=\langle\mathbf{x}_{\nu},\mathbf{u}_{i_{\nu}}\rangle\langle\mathbf{x}_{\nu},\mathbf{u}_{j}\rangle=\langle\mathbf{x}_{\nu},\mathbf{u}_{i_{\nu}}*\mathbf{u}_{j}\rangle=0.$

Hence, $\langle\mathbf{x}_{\nu},\mathbf{u}_{j}\rangle=0$ for any $j\neq
i_{\nu}$. Consequently, ${\mathbf{x}}_{\nu}=\mathbf{u}_{i_{\nu}}$. This
implies that $\nu$ determines a unique column of $\mathbf{U}$ as claimed. ∎

This observation demonstrates that convolution can indeed be unifyingly viewed
as an indispensable component of Fourier theories with both finite and
infinite domains. We end the paper with an example to illustrate this point of
view.

######  Example 7.

For simplicity, let $T$ be a finite (parameter) set of size $m$ and $V$ be a
set of $n$ nodes. As both $T$ and $V$ are finite, the space of (real)
integrable functions on $T\times V$ can be identified with
$\mathcal{S}=\mathbb{R}^{mn}$. Each signal in $\mathcal{S}$ can be written as
an $n\times m$ matrix, with the $t$-th column corresponding to the parameter
$t\in T$ assuming $T$ is given an order.

Assume that for each $t\in T$, there is a symmetric graph shift operator
$\mathbf{S}_{t}$ with an orthogonal matrix of eigenvectors $\mathbf{U}_{t}$.
This can happen if there exist multiple feasible connections among $V$, e.g.,
multi-layered graphs and heterogeneous graphs. We define a multiplication on
$\mathcal{S}$ as follows. For two matrices
$\mathbf{M},\mathbf{N}\in\mathcal{S}$, the $t$-th column of
$\mathbf{M}*\mathbf{N}$ is the GSP convolution of the $t$-th columns of
$\mathbf{M},\mathbf{N}$ w.r.t. $\mathbf{U}_{t}$. As $\mathcal{S}$ can be
vectorized, by the same argument as in the proof of Theorem 7, one shows that
$\widehat{\mathcal{S}}$ can be identified with
$\mathfrak{B}=\\{\mathbf{U}_{t,j},t\in T,1\leq j\leq n\\}$, where
$\mathbf{U}_{t,j}$ is the $j$-th column of $\mathbf{U}_{t}$. The explicit
formula for the character is given by

$\displaystyle\nu_{t,j}(\mathbf{M})=\langle\mathbf{U}_{t,j},\mathbf{M}_{t}\rangle,$

where $\mathbf{M}_{t}$ is the $j$-th column of $\mathbf{M}$. In the spirit of
the unification, $\mathfrak{B}$ can be considered as the Fourier kernel for a
transformation $\widehat{\cdot}:\mathcal{S}\to\mathcal{S}$. This agrees with
what has been proposed in [35], while the latter considers more general
parameter spaces $T$ other than finite sets.

In addition, in [35], $T$ is assumed to be a probability space. To process a
signal on $V$, we only need to introduce two operators
$\phi_{1}:\mathbb{R}^{n}\to\mathcal{S}$ and
$\phi_{2}:\mathcal{S}\to\mathbb{R}^{n}$ as “dictionaries” to translate between
the two signal spaces. For example, we may choose $\phi_{1}(\mathbf{x})$ such
that the vector associated with each $t\in T$ is $\mathbf{x}$, while
$\phi_{2}$ is the expectation operator $\mathbb{E}(\cdot)$ w.r.t. the measure
on $T$. We may use
$\phi=\phi_{2}\circ\widehat{\phi_{1}(\cdot)}:\mathbb{R}^{n}\to\mathbb{R}^{n}$
to analyze signals analogous to GFT in GSP, however, it is in general not an
orthogonal base change.

##  VIII Conclusion

In this article, we give an overview of the notion of convolution in theories
of Fourier type such as the Pontryagin theory, the theories of GSP and ASP. It
appears in different forms. A unifying view is provided.

## References

  * [1] S. Morris, _Pontryagin duality and the structure of locally compact Abelian groups_. Cambridge, UK: Cambridge University Press, 1977.
  * [2] D. Ramakrishnan and R. Valenza, _Fourier analysis on number fields_. New York, NY: Springer-Verlag, 1999.
  * [3] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proc. IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [4] D. I. Shuman, B. Ricaud, and P. Vandergheynst, “A windowed graph Fourier transform,” in _Proc. IEEE Workshop on Stats. Signal Process._ , 2012.
  * [5] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in _NeurIPS_ , 2016.
  * [6] M. Püschel and J. Moura, “Algebraic signal processing theory: Foundation and 1-D time,” _IEEE Trans. Signal Process._ , vol. 56, no. 8, pp. 3572–3585, 2008.
  * [7] W. Rudin, _Real and Complex Analysis_. McGraw-Hill, 1987.
  * [8] P. Lax, _Functional Analysis_ , 1st ed. Wiley-Interscience, 2002.
  * [9] M. Atiyah and I. Macdonald, _Introduction to Commutative Algebra_. Addison-Wesley Publishing Company, 1994.
  * [10] S. Lang, _Algebra_ , 3rd ed. New York, NY: Springer-Verlag, 2002.
  * [11] T. Hungerford, _Algebra (Graduate Texts in Mathematics) (v. 73)_ , 8th ed. Springer, 2002.
  * [12] M. Artin, _Algebra_ , 2nd ed. Pearson Education, 2011.
  * [13] J. Tate, _Fourier analysis in number fields, and Hecke’s zeta-functions_. Washington, D.C.: Thompson, 1965.
  * [14] A. Cayley, “Desiderata and suggestions: No. 2. The Theory of groups: graphical representation,” _Am. J. Math._ , vol. 1, no. 2, pp. 174–176, 1878\.
  * [15] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” _IEEE Signal Process. Mag._ , vol. 30, no. 3, pp. 83–98, 2013.
  * [16] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs,” _IEEE Trans. Signal Process._ , vol. 61, no. 7, pp. 1644–1656, 2013.
  * [17] ——, “Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure,” _IEEE Signal Process. Mag._ , vol. 31, no. 5, pp. 80–90, 2014.
  * [18] A. Gadde, A. Anis, and A. Ortega, “Active semi-supervised learning using sampling theory for graph signals,” in _Proc. ACM SIGKDD_ , 2014.
  * [19] X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst, “Learning Laplacian matrix in smooth graph signal representations,” _IEEE Trans. Signal Process._ , vol. 64, no. 23, pp. 6160–6173, 2016.
  * [20] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _ICLR_ , 2017.
  * [21] H. E. Egilmez, E. Pavez, and A. Ortega, “Graph learning from data under Laplacian and structural constraints,” _IEEE J. Sel. Top. Signal Process._ , vol. 11, no. 6, pp. 825–841, 2017.
  * [22] F. Grassi, A. Loukas, N. Perraudin, and B. Ricaud, “A time-vertex signal processing framework: Scalable processing and meaningful representations for time-series on graphs,” _IEEE Trans. Signal Process._ , vol. 66, no. 3, pp. 817–829, 2018.
  * [23] A. Ortega, P. Frossard, J. Kovačević, J. M. F. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” _Proc. IEEE_ , vol. 106, no. 5, pp. 808–828, 2018.
  * [24] B. Girault, A. Ortega, and S. S. Narayanan, “Irregularity-aware graph fourier transforms,” _IEEE Trans. Signal Process._ , vol. 66, no. 21, pp. 5746–5761, 2018.
  * [25] F. Ji and W. P. Tay, “A Hilbert space theory of generalized graph signal processing,” _IEEE Trans. Signal Process._ , vol. 67, no. 24, pp. 6188 – 6203, 2019.
  * [26] I. Goodfellow, Y. Bengio, A. Courville, and Y. Bengio, _Deep learning_. MIT Press, 2016, vol. 1.
  * [27] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _CVPR_ , 2016, pp. 770–778.
  * [28] A. Krizhevsky, I. Sutskever, and G. Hinton, “ImageNet classification with deep convolutional neural networks,” _Commun. ACM_ , vol. 60, pp. 84–90, 2017.
  * [29] T. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _International Conference on Learning Representations_ , 2017.
  * [30] W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _Advances in Neural Information Processing Systems_ , 2017, p. 1025–1035.
  * [31] P. Velic̄ković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in _International Conference on Learning Representations_ , 2018.
  * [32] I. Chami, Z. Ying, C. Ré, and J. Leskovec, “Hyperbolic graph convolutional neural networks,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 4869–4880.
  * [33] C. Gulcehre, M. Denil, M. Malinowski, A. Razavi, R. Pascanu, K. M. Hermann, P. Battaglia, V. Bapst, D. Raposo, and A. Santoro, “Hyperbolic attention networks,” in _International Conference on Learning Representations_ , 2019\.
  * [34] M. Püschel, B. Seifert, and C. Wendler, “Discrete signal processing on meet/join lattices,” _IEEE Trans. Signal Process._ , vol. 69, pp. 3571–3584, 2021.
  * [35] F. Ji, W. P. Tay, and A. Ortega, “Graph signal processing over a probability space of shift operators,” _IEEE Trans. Signal Process._ , vol. 71, pp. 1159–1174, 2023.