Bipartite graph projections, with threshold
My two cents:

The worst case of building $G_\top$ is in $\Omega(n^2)$ time and space: assume $\bot$ contains a single node linked to all nodes in $\top$.
Maybe you are not looking for a worst case complexity? Then, $O(\sum_{u\in\bot}(d_u)^2)$ time to build $G_\top$ by listing all edges $u,v$ such that $u$ and $v$ are neighbors of the same node in $\bot$.
You can use some pruning in the case $k$ is large with the following algorithm. For each node $u\in \top$ such that its degree is $k$ or more: For each neighbor $v$ of $u$: For each neighbor $w$ of $v$ such that $w&gt;u$: List the edge $u,w$. Then postprocess the listed edges to find the ones that appear $k$ times or more. Here is a code that does something like that efficiently.
Some related code here for simple graphs (not bipartite, but can be adapted) where we look for pairs of nodes with Jaccard similarity higher than a threshold. It seems that Jaccard allows to leverage a more aggressive pruning: only a pair of nodes $u,v$ such that $\frac{\min(d_u,d_v)}{\max(d_u,d_v)}&gt;\alpha$ can have a Jaccard similarity higher than $\alpha$.