It is common to treat graph motifs as just another feature. You run some graph job, the job hands you a list of triangles, and you bolt them onto your ranker the way you would bolt on a “number of common friends” counter. That framing hides the entire problem. A triangle comes out of the pipeline as three integer node ids, and a neural ranker cannot eat three integer ids. Between those three integers and a model that actually scores one person against another is a gap, and the gap is not a formatting detail. It is where the real question lives, and the real question is the one I have been writing about in the rest of this series: a person is not an item, so a person’s representation has to depend on who is looking.
A triangle is not an embedding.
This post is the engineering companion to the earlier three. There I argued that social recommendation breaks the item-recommendation playbook because the viewer-candidate matrix is high-rank and viewer-conditioned, and that the honest fix is a per-viewer projection W_v applied to a structural fingerprint E_c. Here I want to show the two unglamorous problems that have to be solved before any of that theory touches a serving system, and they are both more interesting than the theory suggests.
There are two problems and people conflate them. The first is how you get the triangles at all when the graph has a billion nodes and degree-500 hubs. The second is what you do with a triangle once you have it, because “feed it to the ranker” is not an operation a ranker supports. I will take them in order, and then show how the second one turns out to be the concrete instance of the per-viewer projection from the earlier posts.
Getting triangles out of a graph that does not fit on a machine
The input is an edge list. Each row is a follow. The job is to find every triangle (every set of three mutually connected people) and hand the result downstream. The naive algorithm is to, for every node, look at every pair of its neighbors and check whether the pair is also an edge. On a degree-500 node that is C(500, 2) ≈ 125,000 candidate checks for one node, and a graph with a few of those hubs will spend almost all of its time inside them. Worse, every triangle gets counted six times, once for each of its three vertices acting as the pivot in each direction.
The standard fix is degree ordering, and it is older than most of the people reading this. Order the vertices by degree, breaking ties by id, and reorient every edge to point from the lower-degree endpoint to the higher-degree one. The graph becomes a directed acyclic graph, because every edge points strictly “up” in the order. Now enumerate triangles by pivoting only at the lowest-degree vertex of each triangle: for a vertex v, look at pairs of its out-neighbors and check whether the pair is itself an edge. Each triangle is found exactly once, because a total order has a unique minimum, and the work collapses from roughly O(m · Δ) (with Δ the max degree) to O(m^{1.5}) for power-law graphs. This is NodeIterator++, and the bound is Suri and Vassilvitskii’s. The hub is never the pivot; only the small vertices at the bottom of the order do the enumeration, and they are cheap. The star graph that blew up the naive algorithm now does essentially no work, because the center is the highest-degree node and is never a pivot.
So far this is single-machine. The distributed hazard is the part that bit me, and it is worth being precise about because it is not in most writeups.
The natural thing to do on Spark is to hash-partition the oriented edges and run the enumeration inside each partition. The claim you will hear is “vertex-cut, replication factor drops to two.” That claim is about storage, not about triangle locality, and the distinction matters. A triangle {v, u, w} (with v the lowest-degree vertex, the pivot) has three oriented edges: v→u, v→w, and u→w. If you hash each edge by its source, then v→u and v→w both land on the partition that owns v, because both have source v. Good. But the closing edge u→w has source u, so it lands on the partition that owns u, which is almost certainly a different machine. The pivot’s partition has both legs of the triangle and can see that u and w are both neighbors of v, but it cannot confirm that u and w are connected, because that edge lives elsewhere. The triangle is invisible to the only partition that is allowed to find it.
This is not a bug you can fix by choosing a better hash. Any single-endpoint hash will split some triangle across partitions, because a triangle is a closed structure and its three edges are mutually reinforcing. The fix is to stop pretending the worker can close the triangle locally. Let the worker do only the cheap, local part: enumerate the open wedges (v, u, w) where u and w are both out-neighbors of v. Then close the triangle with a single Spark join, matching each wedge against the edge table on (u, w). The two legs are local because degree ordering made the pivot the source of both of them and the hash-by-source co-located them. The one closing edge is the join’s job. Three edges accounted for: two local, one joined.
The worker is small, and it is the hot inner loop, so it runs as a native sidecar that Spark feeds columnar slices over stdio. Stripped to its bones:
// One partition's oriented edges, hashed by src. outAdj[v] is exactly N+(v).
std::vector<Wedge> worker_emit_wedges(
const std::vector<int64_t>& srcs, const std::vector<int64_t>& dsts,
const std::vector<int32_t>& dst_degree, const std::vector<int64_t>& view_ids)
{
std::unordered_map<int64_t, std::unordered_map<int64_t, NbrInfo>> outAdj;
for (size_t i = 0; i < srcs.size(); ++i)
outAdj[srcs[i]][dsts[i]].views.insert(view_ids[i]);
std::vector<Wedge> out;
for (const auto& [v, nbrMap] : outAdj) {
std::vector<std::pair<int64_t, NbrInfo>> nbrs(nbrMap.begin(), nbrMap.end());
for (size_t i = 0; i < nbrs.size(); ++i)
for (size_t j = i + 1; j < nbrs.size(); ++j) { // each pair once
// canonicalize {u,w} to the edge table's (lower-degree, higher-degree)
int64_t u, w;
if (nbrs[i].second.degree != nbrs[j].second.degree
? nbrs[i].second.degree < nbrs[j].second.degree
: nbrs[i].first < nbrs[j].first) {
u = nbrs[i].first; w = nbrs[j].first;
} else { u = nbrs[j].first; w = nbrs[i].first; }
out.push_back({u, w, v, /*leg views*/});
}
}
return out;
}
And the closing step is one join, no graph machinery:
-- wedges(v, u, w) from the worker; oriented is the degree-ordered DAG
SELECT wed.v, wed.u, wed.w
FROM wedges wed
JOIN oriented e ON e.src = wed.u AND e.dst = wed.w; -- the one and only join
This is the version that survives a billion nodes. The alternative people reach for, running node2vec or some random-walk tokenizer over the graph and letting a Transformer discover the motifs, dies on the same graph for a reason that is arithmetic rather than aesthetic. On a degree-500 node, an unbiased walk comes back to its previous vertex with probability 1/500; the probability it goes twelve hops without ever turning around is (499/500)^12 ≈ 97.6%. You can sample a hundred walks and ninety-seven of them will be the same straight chain [0,1,2,...,11], and the diamond-shaped substructure the tokenizer was invented to find will essentially never appear. I ran exactly this and that is what happened. The tokenizer papers validate on molecular graphs (average degree three) and citation graphs (average degree seven), where you cannot take a hop without bumping into a triangle. On a social graph the triangles are there but the walk sails past them.
So the enumeration is not the part where you get to be clever about deep learning. It is the part where you respect the degree distribution and pay O(m^{1.5}) instead of O(m · Δ), and where you accept that the closing edge costs one join.
What a triangle becomes
Now the harder and more interesting problem. The pipeline hands you (v, u, w) for each triangle. A ranker needs vectors. The question is what the conversion is, and the obvious answers are wrong.
The obvious answer is to give every node a learned embedding and call it done. That is the path that the item-recommendation playbook implies, and it is the path that fails for exactly the reason the rest of this series is about: one static vector per person cannot represent the fact that the same candidate is a different person to each viewer. A triangle is precisely the kind of structure that exposes this. A triangle says “these three people form a closed group,” and which group that is, and what it means for whether two of them should be connected, depends on who the third one is and on who is asking.
The conversion has two levels, and they are easy to conflate.
The first level fuses the three node embeddings inside one triangle into a single triangle embedding. The second level fuses all the triangles a node participates in into that node’s fingerprint. People hear “DeepSets over motifs” and assume the DeepSets is at the first level, fusing the three nodes. It is not. The first level is a plain mean over the three node embeddings (an undirected triangle’s vertices are interchangeable, so a symmetric fuse is the principled choice, and something fancier on three elements buys very little). The DeepSets is at the second level, fusing a node’s many triangles into one fingerprint E_c.
E_c is the candidate’s structural fingerprint. It encodes how many triangles the candidate is in and what kind, which is the only stable signal a person has (a person has no content semantics the way an item does; their semantics is their topology). E_c is a noun. It is static. It does not know anything about the viewer.
The viewer comes in through the operator. The viewer has their own fingerprint f_v, produced by the exact same two-level pipeline run over the viewer’s triangles, and a small hypernetwork reads f_v and emits a low-rank residual (U_v, V_v). The per-viewer operator is W_v = I + U_v V_v^T, and the score is ⟨a_v, W_v E_c⟩, where a_v is a query vector derived from f_v. The candidate fingerprint is the noun. The operator generated from the viewer’s fingerprint is the verb. The viewer’s triangles never touch the candidate directly; they shape the operator that re-projects the candidate.
The reason this is I + U_v V_v^T and not a full d × d matrix is that a full matrix is a billion scale impossibility. At d = 128 and a billion viewers, a per-viewer matrix is sixty-four terabytes. The low-rank residual stores 2dr numbers per viewer, which at d = 128 and r = 8 is two kilobytes, and the same idea is why LoRA works for fine-tuning language models. The serving trick is the part that makes it actually deployable. You do not want to multiply W_v by E_c for every candidate, because that defeats the two-tower retrieval the candidate table exists for. So move the operator to the viewer side:
score(v,c) = ⟨ a_v , W_v E_c ⟩
= ⟨ a_v + V_v (U_v^T a_v) , E_c ⟩
= ⟨ z_v , E_c ⟩
z_v costs O(dr) to compute per viewer, the candidate table E_c stays static, and serving collapses to a standard nearest-neighbor lookup of z_v against the table. The operator is real, it acts on the candidate, but at serve time the candidates never have to know it is there.
In code the whole ranker is short, and training and serving run the same forward:
class MotifProjectionRanker(nn.Module):
def __init__(self, n_nodes, d, r, use_motif=True, pooling="deepsets"):
super().__init__()
self.proj = ViewerProjection(d, r)
if use_motif:
self.tri_enc = TriangleEncoder(n_nodes, d_id, d_motif) # Level 1: mean
self.fp = MotifFingerprint(d_motif, d, pooling) # Level 2: pool
else:
self.id_table = nn.Embedding(n_nodes, d) # baseline: no motifs
def forward(self, ftab, viewer_ids, cand_ids):
f_v = ftab[viewer_ids] # viewer fingerprint
E_c = ftab[cand_ids] # static candidate table
z_v = self.proj.query_vec(f_v) # z_v = a_v + V_v(U_v^T a_v), O(dr)
return (z_v * E_c).sum(-1) # <z_v, E_c> = <a_v, W_v E_c>
There is one ablation built into that constructor that is worth pausing on, because it is the cleanest statement of what the projection is actually worth. Set r = 0 and W_v becomes the identity, so the score is ⟨a_v, E_c⟩, which is plain matrix factorization. Set use_motif = False and E_c becomes a raw learned id table with no triangle structure in it at all. Those two switches span a small grid, and the cell that isolates the projection’s contribution is the one with no motifs and r > 0: a learned id table, viewer-relative only through W_v, no graph encoding whatsoever. If that cell lifts the metric, the lift is the projection’s and nothing else’s. Then you turn motifs back on and measure how much the structural fingerprint adds on top. That is the experiment that tells you whether any of this earned its keep, and it is the experiment most “we added graph features” papers cannot run, because they never built the version without the graph features.
What I expect, and what I do not
The aggregation at the second level has three settings, sum, deepsets, and attention, and they form a ladder of expressiveness: linear aggregation, plus a per-element nonlinearity, plus inter-element interaction. I expect attention to win modestly over deepsets and deepsets to win modestly over sum, and I expect the win to be small, because the per-triangle embeddings are already rich and the marginal value of fancier pooling on top of rich elements is usually small. The bigger lever is the rank r of the viewer operator, and the switch that turns motifs on at all.
The one upgrade I do not expect to come from pooling is the one that actually matters at the first level, and it is not attention. The first level loses information about role: inside a triangle, degree ordering makes one vertex the pivot (lowest degree), one the middle, and one the highest, and the plain mean does not record which is which. Attention on three interchangeable elements will not recover that. What recovers it is plumbing the degree-ordering roles in as an explicit role embedding, so the triangle encoder knows that “this candidate is the hub of this triangle” is a different fact from “this candidate is the leaf.” That is the meaningful first-level improvement, and it is sitting on the to-do list, not in the pooling axis.
I want to be honest about where the headroom actually is, because the temptation in a post like this is to oversell. The enumeration is not a ranking improvement; it is the cost you pay to have structural features at all, and the alternative (random-walk tokenizers) does not work on graphs that look like the one I work on. The structural fingerprint and the per-viewer projection are where any metric lift lives, and the lift is bounded by how much of friendship formation is actually driven by local topology rather than by activity and timing, which a triangle cannot see. Triadic closure is the strongest single signal in friend suggestion, so the bound is generous, but it is a bound. The point of building the ablation grid is to measure the bound instead of asserting it.
The shape of the thing
The deeper claim is the one from the earlier posts and I will not re-derive it here. A person is not an item. An item has stable content semantics, so one embedding per item is a reasonable object and the user-item matrix is low-rank. A person has no stable content semantics; their semantics is their graph, and the relevant graph is different for every viewer, so one embedding per person is the wrong object and the viewer-candidate matrix is high-rank. The job of the per-viewer operator W_v is to make the candidate a function of the viewer without storing a full matrix per viewer, and the job of the structural fingerprint E_c is to give that operator something honest to operate on, something that encodes edges rather than interests.
What this post adds is the part the earlier posts glossed over. The fingerprint has to come from somewhere, and “somewhere” is a pipeline that enumerates triangles at scale by respecting degree ordering and accepting one join, and then fuses them through two levels into a vector. The theory said you needed E_c and W_v. This is what E_c is made of, and this is the engineering that makes W_v servable. A triangle is three integers. The rest of the work is turning those three integers into a ranker that knows who is asking.
Notes
[1] Degree ordering and the O(m^{1/2})-per-edge work bound (the O(m^{3/2}) total) for triangle enumeration go back to Schank and Wagner’s experimental studies and are laid out cleanly for the MapReduce setting in Suri and Vassilvitskii, “Counting Triangles and the Curse of the Last Reducer” (WWW 2011). The “lowest-degree vertex is responsible” rule is their NodeIterator++.
[2] The low-rank residual I + U V^T as a per-viewer operator is LoRA relocated (Hu et al. 2021), and the query-side identity ⟨a_v, (I+UV^T)E_c⟩ = ⟨a_v + V(U^T a_v), E_c⟩ is what makes it servable as a two-tower lookup. The same residual form appears in recommendation as per-user projection (McAuley et al., CIKM 2015; RecLoRA, 2024), though neither argues the structural-necessity version that the rest of this series is about.
[3] The (499/500)^12 ≈ 97.6% number is the probability a 12-hop unbiased walk on a degree-500 node never revisits its previous vertex. The collapse to straight chains is the reason random-walk motif tokenizers (the G2PM family) do not transfer from molecular and citation graphs to social graphs without heavy importance-biased sampling, and even then the walk is fighting the degree distribution rather than reading it.