An undirectional graph $\mathcal{G}$ has the set of nodes $\mathcal{N}$ where each node has an associated unique embedding of $512$ dimensions. Note that the embeddings themselves are fixed, and not to be trained in this problem. So you can express the set of nodes as $$\mathcal{N}=\{v\in\mathbb{R}^{512}\}$$ where $v$ denotes the embedding of any node.

Some of the node pairs are connected, i.e. we know there are edges. Some other pairs are definitely unconnected, i.e. we know there are no edges. The edges follow the transitive property, i.e. if $n_1, n_2\in\mathcal{N}$ are connected, $n_2, n_3\in\mathcal{N}$ are connected, we can assume $n_1, n_3\in\mathcal{N}$ are connected.

About the rest of the node pairs, we do not know.

The problem

Train a model based on the graph that, given any two nodes' embeddings, will predict whether there is an edge connecting them. Best if it gives a soft prediction, i.e. a probability of linkage instead of a binary yes/no.


Edges are quite rare, i.e. sparse. So treated as a binary classification problem, probably accuracy is not a good metric.

Naive Approach

I can form a 1024 dimensional feature vector (concatenating the embeddings) for each node pair, then do a tabular supervised binary classification using the edge that I know are present.

However, this does not exploit the graphical nature of the problem, which is essential for some stakeholders. When I look on the internet, most problems seem to deal with training the embedding vectors rather than using fixed vectors.

What I am looking for

I do not need the entire code, but just a high level description of the sequential steps involved, best if in terms of relevant methods/objects from graph specific libraries in python such as networkx, scipy-csgraph, scikit-network, karateclub, neo4j etc. Any pointer to tutorials or documentations that deal with this problem using the above libraries will be sincerely appreciated too.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.