Interview: Graph Foundations

A graph $G=(V,E)$ has nodes $V$ (entities) and edges $E$ (relationships). Each node can have a feature vector $\mathbf{x}_i$. Edges can be directed or undirected, weighted or unweighted. Graphs encode relational structure that flat tables ignore.

Graphs have different sizes ($n$ varies), no canonical node order (permuting nodes changes the matrix but not the graph), and sparse structure. An MLP would need fixed input size and would give different outputs for the same graph with relabeled nodes. GNNs solve this with permutation-equivariant message passing.

$\mathbf{L} = \mathbf{D} - \mathbf{A}$. The quadratic form $\mathbf{f}^T\mathbf{L}\mathbf{f} = \frac{1}{2}\sum_{(i,j)\in E}(f_i-f_j)^2$ measures smoothness of a signal on the graph. Eigenvectors of $\mathbf{L}$ act as Fourier bases for graph signal processing. GCN derives from a first-order approximation of spectral convolution using $\mathbf{L}$.

$\tilde{\mathbf{A}} = \mathbf{D}^{-1/2}(\mathbf{A}+\mathbf{I})\mathbf{D}^{-1/2}$. Self-loops ($\mathbf{I}$) let nodes keep their own signal. Degree normalization prevents high-degree hub nodes from dominating the aggregation.

• Node classification: predict label per node
• Link prediction: predict missing edges
• Graph classification: predict label per entire graph
• Graph regression: predict scalar per graph
• Community detection: cluster nodes

Homophily: connected nodes tend to share labels/features ("birds of a feather"). Heterophily: connected nodes tend to differ. Standard GNNs assume homophily when aggregating neighbors. Under heterophily, blind neighbor averaging hurts - need specialized models (H2GCN, GPR-GNN).

Transductive: test nodes are in the graph at training time (labels hidden). Model sees test structure. Inductive: generalize to new nodes/graphs not seen during training. GraphSAGE is designed for inductive settings.

CNNs assume a regular grid with fixed neighbor layout (4 or 8 neighbors). Graph neighborhoods vary in size and have no spatial order (no up/down/left/right). You need permutation-invariant aggregation over arbitrary neighborhoods.

As GNN layers stack, embeddings minimize Dirichlet energy $\mathbf{h}^T\mathbf{L}\mathbf{h}$ - they become smooth across edges. Too many layers push all embeddings toward the same value (oversmoothing), making nodes indistinguishable.

Social networks, citation networks, molecules, knowledge graphs, road networks, protein interaction networks, user-item recommendation graphs, supply chains, fraud rings, and document hyperlink networks.