Graph Representation

A graph $G = (V, E)$ is encoded as matrices so neural networks can process it. The adjacency matrix $A \in \mathbb{R}^{n \times n}$ has $A_{ij} = 1$ if nodes $i, j$ share an edge (arbitrary weights for weighted graphs); the degree matrix $D = \mathrm{diag}(d_1, \ldots, d_n)$ is diagonal with $d_i = \sum_j A_{ij}$. GNNs first add self-loops $\tilde{A} = A + I$ and then apply symmetric normalization $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$, whose element form is $(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2})_{ij} = \frac{\tilde{A}_{ij}}{\sqrt{\tilde{d}_i \tilde{d}_j}}$ — it preserves feature scale through propagation and prevents high-degree nodes from dominating (a celebrity's representation is not drowned by its own magnitude). The graph Laplacian $L = D - A$ (normalized $\mathcal{L} = I - D^{-1/2}AD^{-1/2}$) satisfies $x^T L x = \sum_{(i,j)\in E}(x_i - x_j)^2$ with eigenvalues in $[0, 2]$, and is the starting point for spectral GCN. Tasks split into three levels: node-level (node classification), edge-level (link prediction), and graph-level (graph classification/property prediction).

the entry point for modeling non-Euclidean data — social networks, molecular property prediction, recommendation, knowledge graphs; in interviews it is the prerequisite layer of the GNN series, often requiring hand-writing adjacency/degree matrices and deriving the element form of symmetric normalization.

CNNs/Transformers assume regular grids or sequences and cannot handle arbitrary graph topology. The adjacency matrix encodes structure into tensors that participate in matrix multiplication; symmetric normalization $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ makes aggregation weights inversely related to degree (high-degree nodes are not amplified, low-degree nodes are not ignored) while bounding the spectrum for numerically stable multi-layer propagation — the direct foundation of the GCN/GAT propagation rules.

Define the adjacency matrix $A$ and degree matrix $D$ ($A_{ij}$, $d_i = \sum_j A_{ij}$); why is adding self-loops $\tilde{A} = A + I$ necessary for GNNs?

Derive the element form of symmetric normalization $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$, i.e. $\frac{\tilde{A}_{ij}}{\sqrt{\tilde{d}_i \tilde{d}_j}}$, and explain why it prevents high-degree nodes from dominating aggregation.

Properties of the graph Laplacian $L = D - A$ and normalized Laplacian $\mathcal{L} = I - D^{-1/2}AD^{-1/2}$: the quadratic form $x^T L x = \sum_{(i,j)}(x_i - x_j)^2$ and the eigenvalue range $[0, 2]$.

Name one example for each of the three graph task levels (node/edge/graph), and what are the prediction targets and typical loss forms?

How to extend the basic matrix representation: weighted graphs, directed graphs (non-symmetric $A$), heterogeneous graphs (multiple edge types), and sparse storage for billion-node graphs?