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.

Test Your Knowledge: Practice Questions for "Graph Representation"

Single choice pitfall questions with instant feedback and mistake tracking.