Implications of sparsity and high triangle density for graph representation learning
This addresses a foundational issue in graph representation learning for researchers, revealing limitations in finite-dimensional embeddings and challenging the assumption that triangles imply community structure.
The paper tackles the problem of representing sparse graphs with high triangle density using node embeddings, showing that infinite-dimensional inner product models on low-dimensional manifolds can reproduce such graphs, while global manifold recovery is impossible in sparse regimes but local neighborhoods allow lower-dimensional representations.
Recent work has shown that sparse graphs containing many triangles cannot be reproduced using a finite-dimensional representation of the nodes, in which link probabilities are inner products. Here, we show that such graphs can be reproduced using an infinite-dimensional inner product model, where the node representations lie on a low-dimensional manifold. Recovering a global representation of the manifold is impossible in a sparse regime. However, we can zoom in on local neighbourhoods, where a lower-dimensional representation is possible. As our constructions allow the points to be uniformly distributed on the manifold, we find evidence against the common perception that triangles imply community structure.