Neighbourhood Complex Lifting (Graph to Simplicial)

Given that connections based on neighbourhoods of nodes are already present in GNN literature, the notion of a neighbourhood complex becomes of interest. Following from previous work, defining a neighbourhoods as the nodes with which a node shares a neighbour. Formally, $N(G)$ is defined in terms of a simplex. Where a simplex $\sigma_v$ is the neighbourhood simplex of node $v \in V(G)$, composed of all $u \in V(G)$ given that $\exists w: (v, w) \in E(G) \wedge (u, w) \in E(G)$. [1].

This structure has been proven to have certain properties that could be interesting in certain domains such as $k$-colorability. As stablished by Lovasz, if $N(G)$ is $(k+2)$-connected, then, $G$ is not $k$-colorable. Additionally, he shows a relationship between the homotopy invariance of $N(G)$ and the $k$-colorability of $G$.

Neighbourhood complexes can be used to calculate other more interesting structures in induced by graphs, such as the dominating set of $G$ which is the Alexander dual of $N(\bar{G})$ (neighbourhood complex of the complement of $G$). This is useful for computing homology groups of dominance complexes without having to actually calculated the dominance set [2]. In future implementations, adding a basic transformation pertaining to the Alexander Dual would help in having a Dominating Complex, namely, a simplicial complex composed of simplices where the complements of the nodes composing the simplifies are dominating in $G$.

Tags: Existing lift from literature | connectivity-based | deterministic | Feature lifting

---

[1] L, Lovász. (1967). Kneser's conjecture, chromatic number, and homotopy [2] T, Matsushita. S, Wakatsuki. (2023). Dominance complexes, neighborhood complexes and combinatorial Alexander duals

---

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