Background: Network homophily refers to the theory in network science which states that, based on node attributes, similar nodes may be more likely to attach to each other than dissimilar ones. (Ref: https://en.wikipedia.org/wiki/Network_homophily)
Here, we want to study homophily merely from the perspective of node embedding.
Given a simple graph (network) $G = (V,E)$, we find node embedding $Z \in \mathbb{R}^{|V| \times d}$ of the nodes in $V$, where $d$ is the dimension of node embedding. For each $v \in V$, we let $N_v \subseteq V$ denote the set of neighbors of $v$, and let $Z_v \in \mathbb{R}^d$ denote the embedding of $v$. We formally define network homophily.
Defenition: Given a graph $G = (V,E)$ and node embedding $Z \in \mathbb{R}^{|V| \times d}$, we say $G$ has
- local homophily (w.r.t $Z$) if for each $v \in V$, $\min_{u \in N_v} Z_u \cdot Z_v \geq \max_{w \notin N_v} Z_w \cdot Z_v$
- global homophily (w.r.t $Z$) if $\min_{(u, v) \in E} Z_u \cdot Z_v \geq \max_{(w, x) \notin E} Z_w \cdot Z_x$
Note: Clearly, if $d$ is large enough (e.g., $d \geq |E|$), we can easily find such node embedding.
Question 1: Given a graph $G = (V, E)$, what is the minimum dimension $d$ such that there exists node embedding $Z \in \mathbb{R}^{|V| \times d}$ such that $G$ has local/global homophily?
Question 2: What properties can make such a minimum $d$ smaller/larger?