From Images to Graphs: How They Differs and Resembles

---

ABSTRACT: In this post we are discussing the similarities of graphs and images. We will start with matrix and spacial representations to show how graphs and images differs and resembles. Then we will dive into the applications from traditional signal processing to neural networks. Finally we take 3D vision as the bridging of image and graph in computer vision tasks.

Draft structure:

1. Basics (Spacial representation)
   1. Matrix representation of graph
      1. Non-Euclid properties of graph
   2. Matrix representation of image
      1. Euclid properties of images
   3. Image is special graph
      1. From group theory's perspective
2. Applications
   1. Signal and systems review, but 2d
      1. Frequency domain of graph and img
      2. Sampling, filtering and convolution of graphs and images.
   2. CNN & GNN (Local receptive fields in CNNs vs. neighborhood aggregation in GNNs)
   3. Graph transformers & ViT
3. Combinational application
   1. PointNet Series

Draft end.

Spacial Representations

Graphs

A graph consists of vertices and edges . Here we have a denotes the signal assigned to each node, it can be a scaler, vector, or even matrix. When we deal with graph signals, besides the signal on each node, the topology of graph should also be considered. To record such topology, we bring up the LAPLACIAN MATRIX.

DEFINITION. Each element of laplacian matrix is defined as:

DEFINITION. Symmetric normalized laplacian is given as:

The non-Euclid properties of Graphs

THEOREM. A graph if and only if it can be embedded on the surface of a sphere.

@TODO laplacian matrix & laplacian operator

References

Daigavane, A., Ravindran, B., & Aggarwal, G. (2021). Understanding convolutions on graphs. Distill.

Ortega, A. (2022). Introduction to graph signal processing. Cambridge University Press.

Gonzales, R. C., & Wintz, P. (1987). Digital image processing. Addison-Wesley Longman Publishing Co., Inc..

Wilson, R. J. (2015). Introduction to Graph Theory uPDF eBook. Pearson Higher Ed.