Graph neural networks quiz

Question 1

What is the core computation performed by a single message-passing GNN layer?

Accepted Answer

Permutation-invariant neighbor aggregation followed by a learnable node update

Answer

A global softmax over all nodes in the graph each layer

Answer

Independent per-node MLPs that ignore graph structure

Answer

Recurrent unrolling of edges in a fixed traversal order

Question 2

Why must the neighbor aggregation function in a GNN be permutation invariant?

Accepted Answer

Because neighbors have no canonical ordering, so embeddings must be order-independent

Answer

Because it reduces memory usage during backprop

Answer

Because invariance guarantees the loss is convex

Answer

Because it prevents vanishing gradients in deep stacks

Question 3

What problem does over-smoothing describe in deep GNNs, and what causes it?

Accepted Answer

Node features converge to indistinguishable values due to repeated low-pass filtering

Answer

Gradients explode because of unbounded edge weights

Answer

Embeddings overfit to node IDs and memorize the graph

Answer

Attention weights collapse to uniform across all heads

Question 4

How does the GraphSAGE inductive framework differ from transductive GCN training?

Accepted Answer

GraphSAGE learns aggregators with neighbor sampling enabling embeddings for unseen nodes

Answer

GraphSAGE requires the full Laplacian eigendecomposition at inference

Answer

GraphSAGE only works on bipartite graphs

Answer

GraphSAGE replaces aggregation with global attention over all nodes

Question 5

In the Graph Attention Network (GAT), how are neighbor weights computed?

Accepted Answer

Learned per-edge scores via a feedforward+LeakyReLU, normalized by softmax over neighbors

Answer

Fixed weights from the inverse degree matrix

Answer

Cosine similarity of raw input features only

Answer

Random weights resampled every forward pass

Question 6

What is the symmetric normalization used in Kipf & Welling's GCN propagation rule?

Accepted Answer

D̃^(-1/2) Ã D̃^(-1/2) with self-loops added to the adjacency

Answer

D^(-1) A (random-walk row normalization without self-loops)

Answer

A^T A column normalization

Answer

Raw A with no normalization

Question 7

What is the expressive-power upper bound of standard message-passing GNNs, per the GIN paper?

Accepted Answer

Bounded by the 1-WL test; GIN attains this maximum

Answer

Equivalent to full graph isomorphism testing

Answer

Bounded by 3-WL for all aggregators

Answer

Strictly weaker than spectral methods in all cases

Question 8

Why does GIN use sum aggregation rather than mean or max for maximal expressiveness?

Accepted Answer

Sum preserves multiset information that mean and max discard

Answer

Sum is the only differentiable aggregator

Answer

Sum prevents over-smoothing entirely

Answer

Mean and max are not permutation invariant

Question 9

What is neighbor explosion and how do sampling methods like GraphSAGE mitigate it?

Accepted Answer

Exponential receptive-field growth; fixed-size neighbor sampling bounds it

Answer

Gradient explosion from deep stacks; gradient clipping fixes it

Answer

Memory leaks in sparse matrix multiply; caching fixes it

Answer

Label imbalance across classes; resampling fixes it

Question 10

How does layer-wise sampling in FastGCN differ from node-wise sampling in GraphSAGE?

Accepted Answer

FastGCN samples a fixed node set per layer via importance sampling, not per node

Answer

FastGCN samples edges uniformly while GraphSAGE samples nodes

Answer

FastGCN uses no sampling and relies on full-batch GD

Answer

FastGCN samples per node while GraphSAGE samples per layer

Question 11

What is the difference between spectral and spatial GNN approaches?

Accepted Answer

Spectral uses Laplacian eigenbasis filtering; spatial aggregates in the vertex domain

Answer

Spectral is inductive while spatial is always transductive

Answer

Spatial requires eigendecomposition; spectral does not

Answer

They are mathematically identical with no practical difference

Question 12

How does ChebNet avoid explicit eigendecomposition of the graph Laplacian?

Accepted Answer

Truncated Chebyshev polynomials of the scaled Laplacian via sparse recurrence

Answer

Power iteration to find the top eigenvector only

Answer

Random projection of the adjacency matrix

Answer

Caching a precomputed full eigenbasis on disk

Question 13

What is a readout (graph pooling) function and why is it needed for graph-level tasks?

Accepted Answer

A permutation-invariant aggregation of node embeddings into one graph vector

Answer

A normalization layer applied between message-passing layers

Answer

An edge-dropout regularizer used during training

Answer

A positional encoding added to node features

Question 14

How does DiffPool perform hierarchical graph pooling?

Accepted Answer

Learns soft cluster assignments to coarsen nodes and adjacency layer by layer

Answer

Drops the lowest-degree half of nodes each layer

Answer

Applies global max-pooling once at the end

Answer

Uses k-means on raw features as a fixed preprocessing step

Question 15

What does the Relational GCN (R-GCN) add to handle knowledge graphs with multiple edge types?

Accepted Answer

Relation-specific weight matrices with basis decomposition for parameter sharing

Answer

A single shared weight ignoring edge types

Answer

Attention over relations replacing all linear layers

Answer

Treating every relation as a separate disconnected graph

Question 16

Why can't a standard GNN with anonymous nodes distinguish certain regular graph structures?

Accepted Answer

1-WL symmetry makes regular graphs with identical local structure indistinguishable

Answer

Anonymous nodes cause gradient vanishing, not a representational limit

Answer

The softmax saturates on regular graphs

Answer

Regular graphs have no valid adjacency normalization

Question 17

What are positional encodings in GNNs and name a common choice?

Accepted Answer

Features encoding node position/role, e.g., Laplacian eigenvectors

Answer

One-hot encodings of node class labels

Answer

Dropout masks applied to edges

Answer

Batch-normalization statistics per node

Question 18

What is the over-squashing problem in GNNs and how does it relate to graph topology?

Accepted Answer

Long-range info is compressed through topological bottlenecks, distorting distant signals

Answer

Excessive self-loops cause feature duplication

Answer

Too many attention heads dilute gradients

Answer

Random sampling drops important neighbors

Question 19

How do residual/skip connections help train deeper GNNs?

Accepted Answer

They preserve earlier representations, easing over-smoothing and vanishing gradients

Answer

They remove the need for nonlinear activations

Answer

They enforce permutation invariance

Answer

They eliminate the need for neighbor aggregation

Question 20

In PyTorch Geometric, what does the edge_index tensor represent?

Accepted Answer

A [2, num_edges] COO tensor of source and destination node indices

Answer

A dense [N, N] adjacency matrix

Answer

A [num_edges] vector of edge weights only

Answer

A [N, F] node feature matrix

Question 21

How does mini-batching of multiple small graphs work in frameworks like PyG?

Accepted Answer

Graphs are combined into one block-diagonal graph with a batch index vector

Answer

All graphs are padded to the largest size with zeros

Answer

Graphs are processed strictly one at a time, no batching exists

Answer

Edges are merged across graphs to form a fully connected batch

Question 22

What is the key idea behind APPNP (Approximate Personalized Propagation of Neural Predictions)?

Accepted Answer

Decouple MLP prediction from personalized-PageRank propagation with teleport

Answer

Replace aggregation with self-attention over all nodes

Answer

Use Chebyshev filters on the normalized Laplacian

Answer

Stack many GCN layers with batch norm

Question 23

Why is a mean aggregator sometimes preferred over sum despite lower expressivity?

Accepted Answer

Mean is degree-normalized, giving stability across varying node degrees and sizes

Answer

Mean is the only aggregator that is differentiable

Answer

Mean strictly increases WL expressivity over sum

Answer

Mean avoids the need for activation functions

Question 24

What distinguishes a heterogeneous GNN from a homogeneous one?

Accepted Answer

It handles multiple node/edge types with type-specific or metapath-based aggregation

Answer

It only allows directed edges

Answer

It forbids self-loops

Answer

It uses spectral filters exclusively

Question 25

How is link prediction typically formulated and scored in a GNN pipeline?

Accepted Answer

Encode nodes, score pairs with a decoder, train with negative sampling

Answer

Classify each node independently into edge classes

Answer

Run softmax over all possible edges every step

Answer

Use only the adjacency matrix with no learned embeddings

Question 26

What is the role of negative sampling in training GNN embeddings for link/recommendation tasks?

Accepted Answer

Provides false pairs so the model learns to discriminate true edges efficiently

Answer

Reduces the embedding dimension automatically

Answer

Replaces the need for a readout function

Answer

Enforces permutation invariance of aggregation

Question 27

What is the difference between transductive and inductive node classification settings?

Accepted Answer

Transductive sees test nodes (unlabeled) at train time; inductive does not

Answer

Transductive uses labels of test nodes; inductive uses features only

Answer

They differ only in batch size

Answer

Inductive requires the full Laplacian; transductive does not

Question 28

How does Cluster-GCN make full-batch GCN training scalable?

Accepted Answer

Partition the graph into clusters and train on subgraph mini-batches

Answer

Run PCA on node features before training

Answer

Use only one layer to avoid explosion

Answer

Convert the graph to a tree first

Question 29

What is edge feature incorporation, and how do architectures like MPNN handle it?

Accepted Answer

Messages are functions of endpoints and edge features, e.g., edge-conditioned convolution

Answer

Edge features are averaged into a global bias term

Answer

Edge features are ignored by all GNNs

Answer

Edge features replace node features entirely

Question 30

Why might adding self-loops (A + I) be important in GCN-style aggregation?

Accepted Answer

So each node retains its own features alongside neighbor aggregation

Answer

To make the graph directed

Answer

To increase the number of edges for regularization only

Answer

To force the adjacency to be orthogonal

Test yourself