How is a graph encoded as the input to a graph neural network?
answer
- the model never sees a picture
- two arrays, not one
- one row per node
- connectivity as pairs of ids
- degree is derived, not stored
basics
~20 sA graph reaches the model as a node feature matrix — one row of features per node — plus an edge list of connected node id pairs, and optionally an edge feature matrix. Node ids are addresses, not values.
solid answer
~50 sTwo things are handed over: features and connectivity. Features live in a node matrix of shape `N x F` — N nodes, F features each, so row `i` is node `i`'s attributes (element and charge for an atom, account age for a user). Connectivity is normally an edge list: `E` pairs of integer node ids, with an undirected edge stored in both directions so each endpoint sees the other. The same information can be a dense `N x N` adjacency matrix, but for real graphs that is `N^2` memory for `E` non-zeros, so the pair list wins. Edges can carry their own `E x F_e` feature matrix, aligned row-for-row with the edge list — bond type, transaction amount, timestamp. Degree is not stored; it is derived, as the count of times a node id appears. The integer ids themselves carry no meaning: they are addresses into the feature matrix, not values.
go deeper
Be ready to name the two arrays out loud: a node feature matrix of shape N by F, and an edge list of connected id pairs. Say clearly that node ids are addresses, not values.
Explain the storage tradeoff — O(N^2) for a dense adjacency against O(E) for a pair list — and where degree comes from. Mention edge features and the row alignment they depend on.
Show you have laid this out for a real dataset: undirected edges duplicated, batching by offsetting ids, memory budget for a sparse production graph, and a heterogeneous schema with typed nodes and typed edge lists.
Own the schema decision — what becomes a node, what becomes an edge, what becomes an attribute — because that choice fixes what the model can ever express and what the ingestion pipeline must maintain as the upstream data evolves.
## The two halves of a graph input A neural network cannot consume a drawing of a graph. It consumes arrays, and a graph is turned into arrays along two independent axes: **what each node is** (features) and **who is connected to whom** (structure). ### The node feature matrix The first array is a node feature matrix of shape `N x F`: one row per node, F numeric features per row. For a molecule with N atoms, a row might be a one-hot element code, formal charge, valence and an aromatic flag. For a marketplace user, it might be account age, review count and a country code. Every row uses the same F columns, in the same order — that part is a fixed-size, tabular problem and nothing new. Row `i` belongs to node `i`. That number is an address, not a measurement: node 7 is not "greater than" node 3, and the numbering is whatever order you happened to build the matrix in. ### The structure The second array says which node pairs are joined. Two encodings are standard. - **Edge list (pair list).** Two aligned integer arrays of length E, holding the source and target id of each edge. An undirected edge between 3 and 7 is normally stored twice, as `(3,7)` and `(7,3)`, so that when the model gathers a node's neighbours both endpoints see each other. Memory is O(E). - **Dense adjacency matrix.** An `N x N` array `A` with `A[i][j] = 1` when an edge exists. Memory is O(N^2) regardless of how few edges there are. It is convenient for small, fixed-size graphs and for writing the maths down, and hopeless for a two-million-node social graph, where the same information is ten million pairs. Real graphs are sparse: a follower graph with millions of accounts has an average degree in the tens, so the pair list is smaller by orders of magnitude and is what production pipelines carry. ### Degree, and other derived quantities **Degree** is the number of neighbours a node has — the number of times its id appears as a source in the edge list, or the row sum of the adjacency matrix. It is not part of the input; it is computed from the structure whenever a layer needs it. Because it is derived, it stays consistent under any renumbering of the nodes. ### Edge features and graph features Edges frequently carry attributes of their own: bond order in a molecule, amount and timestamp on a transaction, relation type in a knowledge graph. These live in an `E x F_e` matrix whose row `k` describes the same edge as position `k` of the edge list — the alignment is the contract, and breaking it silently mislabels every edge. A graph may also carry graph-level features (total molecular weight, marketplace region) that attach to the whole object rather than to any node. ### Directed, weighted, heterogeneous, batched A directed graph simply stores each edge once, in its true direction. A weighted graph puts the weight in the edge feature matrix (or in the non-zero entries of the adjacency). A **heterogeneous** graph — buyers, sellers and products, each with a different natural feature width — is usually laid out as one feature block per node type plus a per-type projection into a shared width, with edges split into typed lists keyed by (source type, relation, target type). Several graphs are batched by concatenating their node matrices and offsetting the ids in each edge list, which makes one big disconnected graph whose components never exchange messages. ### What is deliberately missing Nothing in this encoding fixes an order. If you renumber the nodes and renumber the edge list consistently, you have the *same graph*, described differently — and the model is expected to behave accordingly. That requirement is what shapes every layer built on top of this input, and it is why the representation stops at "features plus pairs" rather than trying to serialise the graph into one canonical vector. ### Common mistakes Feeding structure with no node features (the model then has only topology to work with — sometimes intended, usually an oversight); storing a dense adjacency for a sparse graph and running out of memory; storing an undirected edge in one direction only, so half the neighbourhoods are empty; and treating node ids as ordinal values by feeding the raw index in as a feature, which invents an ordering that does not exist.
- When would you keep a dense N x N adjacency matrix instead of an edge list?When N is small and fixed — a few dozen nodes, as in a molecule or a small scene graph — and you want plain matrix arithmetic. Dense storage costs N^2 memory whatever the edge count, so it stops being viable at a few tens of thousands of nodes; a sparse pair list costs O(E) and scales with the edges you actually have.
- Where do edge attributes such as bond type or transaction amount live?In their own E x F_e matrix, row-aligned with the edge list so row k describes edge k. Keep the alignment invariant if you reorder or deduplicate edges, and remember that an undirected edge stored in both directions needs its attributes duplicated on both rows, or one direction silently loses them.
- How would you lay out a heterogeneous marketplace graph where buyers, sellers and products have different feature widths?Keep one node feature block per type at its natural width and project each into a shared dimension with a per-type transform, or pad to a common width and add a type indicator. Edges become several typed lists — buyer-bought-product, seller-lists-product — so relation type is explicit rather than encoded in the feature vector.
- How are several graphs put into one training batch?Stack the node feature matrices, offset each graph's node ids by the running node count, and concatenate the shifted edge lists. The result is one large graph with disconnected components, so no information crosses between examples, and a per-graph index vector records which nodes belong to which original graph.
It is a seating chart plus a guest list: one table lists each guest's details, a separate list names which pairs of guests talk to each other. Renumbering the guests changes neither the party nor anything you would conclude about it.
saying these in an interview costs you the question
- Says the model is given a picture or a drawing of the graph
- Feeds only the adjacency and forgets node features exist
- Treats node ids as numeric values with an ordering
- Stores a dense N x N adjacency for a million-node sparse graph
- Stores an undirected edge in one direction only
- Thinks degree must be supplied as an input column