Your node2vec vectors cluster friend groups, but you need bridge accounts to look alike — what do you change?

## Two similarities, one embedding Ask what it means for two nodes to be similar and you get two defensible answers. - **Homophily / community**: two nodes are similar if they sit in the same densely connected region. Two students in the same dorm friend group. - **Structural equivalence / role**: two nodes are similar if they occupy the same *kind* of position, regardless of where. Two students who each sit between two otherwise disconnected friend groups — brokers, bridges, hubs — even if they have never met and share no friends at all. A single embedding cannot maximise both. node2vec's contribution is that the *sampler* — not the objective — chooses between them, through two parameters on a second-order walk. ## The bias, precisely The walk is standing at node `v`, having arrived from `t`. Each candidate next node `x` gets an unnormalised weight: - `1/p` if `x` is `t` — stepping straight back; - `1` if `x` is a neighbour of `t` as well as of `v` — staying inside the shared local structure; - `1/q` if `x` is two hops from `t` — moving outward into new territory. **`q` is the in-out parameter.** `q < 1` inflates `1/q`, upweighting the outward step: walks behave depth-first, drifting far from the start, sweeping long stretches of one region. **`q > 1` deflates it**, so walks stay inside the source's own neighbourhood, behaving breadth-first and repeatedly sampling the same local surroundings. **`p` is the return parameter.** Small `p` inflates `1/p` and encourages immediate backtracking, producing very local, redundant walks. Large `p` discourages returning to the previous node and keeps the walk exploring. ## Why local walks give you roles When `q > 1`, a node's context window is dominated by a repeated micro-survey of its own neighbourhood. What the vector ends up encoding is the *shape* of that neighbourhood — how many distinct clusters touch it, how dense they are, how quickly the walk gets trapped. Two broker accounts in a university social network, one bridging the chess club and the rowing team, another bridging two unrelated dorms, produce similar local micro-surveys: a walk starting at either keeps oscillating between two dense regions. Their vectors converge even though the walks never overlap on a single shared node. When `q < 1`, the walk instead escapes and roams one community, so the context of a chess-club member is other chess-club members, and the embedding recovers friend groups. That is the regime that produced the complaint in the question. ## The counter-intuitive consequence Under `q > 1`, embedding proximity no longer implies graph proximity. Two nodes that are twenty hops apart can be nearest neighbours in vector space, and two adjacent nodes — say a broker and one of the ordinary members it connects to — can be far apart. If a downstream system was built assuming near-in-vector-space means near-in-graph (a recommendation that suggests people you might actually know, for instance), it will start returning strangers who happen to share a role. Decide which similarity the *product* needs before you tune. ## How to verify you got the regime you asked for Do not trust the parameter setting; measure it. - **Labelled probe set.** Take a handful of nodes you already know are brokers or hubs and check whether they became mutual nearest neighbours. Do the same for a known tight community and check that its members did *not*. - **Correlate with a structural statistic.** If the embedding encodes role, nearest neighbours should share degree and clustering-coefficient magnitude while sitting in different components of the community structure. - **Downstream task.** The honest test is whether the classifier that consumes the vectors improved on the task you care about; role embeddings often help fraud and anomaly work and hurt friend recommendation. ## Costs and cautions The second-order bias is not free. Because the transition depends on the previous node, the sampler must consider, at each step, whether each candidate is the predecessor or a neighbour of the predecessor — so either you check neighbour membership online or you precompute per-edge transition distributions, whose memory grows with the sum over edges of the endpoint degrees. On a hub-heavy graph that precomputation can dwarf the embedding table itself. Also, `p` and `q` are not a small correction; they change what the model means. Tuning them by downstream validation score alone, without an interpretation of which similarity you want, tends to produce an embedding nobody can explain when it later misbehaves. Finally, note the limiting case: uniform DeepWalk walks are the `p = q = 1` setting, which sits between the two regimes and commits to neither.