Implications of sparsity and high triangle density for graph representation learning
Hannah Sansford, Alexander Modell, Nick Whiteley, Patrick Rubin-Delanchy
Abstract
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.
BibTeX
@InProceedings{pmlr-v206-sansford23a,
title = {Implications of sparsity and high triangle density for graph representation learning},
author = {Sansford, Hannah and Modell, Alexander and Whiteley, Nick and Rubin-Delanchy, Patrick},
booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics},
pages = {5449--5473},
year = {2023},
editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem},
volume = {206},
series = {Proceedings of Machine Learning Research},
month = {25--27 Apr},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v206/sansford23a/sansford23a.pdf},
url = {https://proceedings.mlr.press/v206/sansford23a.html},
abstract = {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.}
}