In GNN link prediction, what does a bilinear score buy over a plain dot product of two node vectors?
answer
- encoder gives vectors, head gives a score
- symmetry is the giveaway
- one matrix per relation type
- W equal to identity recovers the dot product
basics
~20 sA dot product of two node vectors is symmetric and parameter-free, expressing one undirected notion of similarity. A bilinear score adds a learned matrix per relation, so it can be asymmetric and score several edge types from one shared embedding set.
solid answer
~40 sAfter message passing you have one vector per node, and the head turns a pair into a score. The dot product `s(u,v) = h_u . h_v` has no parameters and is symmetric, so it can only say how aligned two nodes are — fine for a single undirected relation, wrong for a directed or multi-relation graph. A bilinear score `s_r(u,v) = h_u^T W_r h_v` learns one matrix per relation `r`; setting `W = I` recovers the dot product, a non-symmetric `W` can score direction, and separate `W_r` let one drug-interaction graph carry many interaction types over shared node embeddings. The cost is `d^2` parameters per relation, which overfits when a relation has few edges — so people use a diagonal `W` (DistMult), a low-rank factorization, or a shared basis of matrices combined per relation.
go deeper
Be ready to say that after message passing you have one vector per node and that an edge score comes from comparing two of them, with the dot product as the simplest way to do that.
You are expected to write both scoring functions down, state that the dot product is symmetric and parameter-free, and explain that a bilinear matrix generalises it and can be made relation-specific.
Show the cost side: d squared parameters per relation, rare relations that memorise their few edges, and the diagonal, low-rank or shared-basis reductions you would reach for instead.
Own the decision of how much capacity belongs in the encoder versus the head, and how that choice interacts with the number of relation types, the edge counts in the tail, and the cost of scoring candidate pairs at serving time.
## The encoder / decoder split Almost every graph link-prediction model factors into two parts. The **encoder** is the message-passing body: after `K` rounds it produces one vector `h_v` (dimension `d`) per node, summarising that node and its `K`-hop neighbourhood. The **decoder**, or head, is a scoring function that takes a candidate pair `(u, v)` and returns a real number `s(u, v)` — high if the edge should exist. Training pushes the score up on observed edges and down on sampled non-edges; at inference you score candidate pairs and rank or threshold them. The question is what shape the decoder should have. ## The dot product The cheapest decoder is the inner product: `s(u, v) = h_u . h_v = sum_i h_u[i] * h_v[i]` Properties worth being able to state out loud: - **No parameters of its own.** All the capacity lives in the encoder, which is a real advantage on small graphs — there is nothing extra to overfit. - **Symmetric.** `s(u, v) = s(v, u)` identically. There is no way for the model to say *u cites v* but not *v cites u*. - **One geometry for everything.** Two nodes are either close in the single embedding space or they are not. If your graph has several edge types, they all have to be explained by that one geometry. - **Cheap over many candidates.** Scoring a node against many others is one matrix product, whereas a pairwise network has to be evaluated pair by pair. On a single-relation, undirected graph — a friendship graph, a co-authorship graph — the dot product is often the right default and hard to beat. ## The bilinear form The bilinear decoder inserts a learned matrix between the two vectors: `s_r(u, v) = h_u^T W_r h_v = sum_i sum_j W_r[i][j] * h_u[i] * h_v[j]` Three things change. 1. **It generalises the dot product.** With `W = I` you get the inner product back, so the bilinear family strictly contains it. 2. **It can be asymmetric.** Because `W` need not equal its own transpose, `s(u, v)` and `s(v, u)` can differ. That is exactly what a directed edge needs. 3. **It can be made relation-specific.** Keep one `W_r` per relation type and share the node embeddings across all of them. On a drug-interaction graph where edges are labelled by interaction category — one drug amplifies another, one blocks another's clearance — a single dot product forces every category into the same notion of nearness. Per-relation matrices let each category apply its own linear map to the second vector before the comparison, while the node vectors themselves stay shared and therefore stay well-trained by all relations at once. ## The cost, and the standard fixes A full `W_r` costs `d^2` parameters. With `R` relation types that is `R * d^2`, and real knowledge-style graphs have a long tail of relations with very few observed edges each. Those relations will memorise their handful of training edges. Established remedies: - **Diagonal `W`** (the DistMult scoring function): only `d` parameters, an element-wise reweighting of the dot product. Very robust, but a diagonal matrix makes the score symmetric again, so it cannot represent an antisymmetric relation such as *is a parent of*. - **Low-rank or factorised `W`**: `W_r = A_r B_r^T` with a narrow inner dimension, trading expressiveness for parameter count. - **Basis decomposition**: define a small set of shared basis matrices and let each relation learn only mixing coefficients over them, so rare relations borrow structure from common ones. - **Complex-valued or translational alternatives** (ComplEx, TransE) attack the same asymmetry problem with a different algebraic trick rather than a full matrix. ## The other alternative: a pairwise network You can also concatenate `[h_u ; h_v]` and push it through a small feed-forward network. That is more expressive than any bilinear form, but it is asymmetric only by accident (you must feed both orders or symmetrise deliberately), it costs a forward pass per candidate pair instead of one product, and it is the easiest of the three to overfit. ## From score to decision Whatever the decoder, the raw score is an unbounded real number. It is squashed with a logistic function to get an edge probability and trained with a binary cross-entropy objective against sampled non-edges. Remember that the absolute probability depends on how those non-edges were sampled; the ranking induced by the score is usually the trustworthy part. ## What a good answer sounds like Start with the dot product as the default, name symmetry as its limitation, present the bilinear form as the parameterised generalisation that fixes direction and multi-relation modelling, then immediately price it at `d^2` per relation and offer the diagonal or basis-shared version as the practical middle ground.
- When is a diagonal bilinear matrix enough, and when does it fail?A diagonal `W` (the DistMult form) is just a learned per-dimension reweighting of the dot product: `d` parameters, very hard to overfit, and a good default when the relation is symmetric — *interacts with*, *is similar to*. It fails on antisymmetric relations, because a diagonal matrix makes `s(u,v) = s(v,u)` identically. If the graph contains *is a subtype of* or *cites*, a diagonal decoder cannot represent the asymmetry no matter how long you train it.
- You have hundreds of relation types and a full matrix each would dominate the parameter count. What do you do?Stop giving each relation its own free matrix. Use a shared basis: define a small number of basis matrices and let each relation learn only the mixing coefficients over them, so rare relations inherit structure from common ones. Low-rank factorisation of each `W_r` and the diagonal form are the other two standard reductions. Choose based on how many edges the rarest relations actually have.
- How would you check empirically whether the asymmetry of the bilinear decoder is doing anything?Compare a run with the learned `W` against a run that symmetrises it as `(W + W^T)/2`, holding everything else fixed. If ranking quality on held-out directed edges is unchanged, the asymmetry is not being used and you should drop to the cheaper symmetric decoder. You can also inspect the size of the antisymmetric part of `W` relative to its symmetric part.
A dot product asks one fixed question: how aligned are these two? A bilinear matrix first rotates and rescales the second vector, so each relation gets to ask its own version of the question.
saying these in an interview costs you the question
- Claims a plain dot product can score directed edges
- Thinks each relation needs its own separate node embeddings
- Assumes a bigger decoder always improves link prediction
- Treats the raw decoder score as a probability
- Cannot say that W equal to identity recovers the dot product