1706.03762 (Annotated)
Structural equivalence foundations across hypergraph-native models and GNNs on Levi lifts.
Key Measures (from paper)
- Spectral distance between representations.
- Incidence distribution distances (e.g., Wasserstein).
- Downstream performance parity across model families.
- Statistical confidence across multiple seeds.
Levi Lift
Hypergraph $H=(V,E)$ with incidence matrix $B \in \{0,1\}^{|V|\times |E|}$ lifts to bipartite Levi graph $L(H)$ with parts $V$ and $E$.
Adjacency of $L(H)$: $$ A_{L}=\begin{pmatrix} 0 & B \\ B^\top & 0 \end{pmatrix} $$
Normalized Laplacian provides spectral signatures; parity claims bound distances across representations.
Invariants & Distances
Spectral
Top-$k$ eigenvalue distance: $$ d_\text{spec}=\bigg(\sum_{i=1}^{k} (\lambda_i-\tilde{\lambda}_i)^2 \bigg)^{1/2} $$
Incidence
Wasserstein between degree/incidence histograms: $$ W_1(p,\tilde p)=\inf_{\gamma\in\Pi(p,\tilde p)} \int |x-y|\, d\gamma(x,y) $$
Infographic