Line Lifting (Graph to Simplicial)

This lifting constructs a simplicial complex called the Line simplicial complex. This is a generalization of the so-called Line graph. In vanilla line graph, nodes are edges from the original graph and two nodes are connected with an edge if corresponding edges are adjacent in the original graph.

The line simplicial complex is a clique complex of the line graph. That is, if several edges share a node in the original graph, the corresponding vertices in the line complex are going to be connected with a simplex.

So, the line lifting performs the following:

1. For a graph $G$ we create its line graph $L(G)$. The line (or dual) graph is a graph created from the initial one by considering the edges in $G$ as the vertices in $L(G)$ and the edges in $L(G)$ correspond to the vertices in $G$.
2. During this procedure, we obtain a graph. It is easy to see that such graph contains cliques for basically each node in initial graph $G$. That is, if $v\in G$ has a degree $d$ then there's a clique on $d$ vertices in $L(G)$.
3. Therefore let's consider a clique complex $X(L(G))$ of $L(G)$ creating $(d-1)$-simplices for each clique on $d$ vertices, that is, for each node in $G$ of degree $d$.

When creating a line graph, we need to transfer the features from $G$ to $L(G)$. That is, for a vertex $v\in L(G)$, which correponds to an edge $e\in G$ we need to set a feature vector. This is basically done as a mean feature of the nodes that are adjacent to $e$, that is, if $e=(a,b)$, then

$$f_v \coloneqq \frac{f_a + f_b}{2}.$$

From https://github.com/pyt-team/challenge-icml-2024/pull/9