Implications of sparsity and high triangle density for graph representation learning
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph Representation LearningRepresentation LearningVocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
Covering a Graph with Dense Subgraph Families, via Triangle-Rich Sets
Graphs are a fundamental data structure used to represent relationships in domains as diverse as the social sciences, bioinformatics, cybersecurity, the Internet, and more. One of the central observations in network scie…
Graph MiningTriangle Splatting for Real-Time Radiance Field Rendering
The field of computer graphics was revolutionized by models such as Neural Radiance Fields and 3D Gaussian Splatting, displacing triangles as the dominant representation for photogrammetry. In this paper, we argue for a …
GPUNeRFNovel View SynthesisAccelerating Prefilling via Decoding-time Contribution Sparsity
Large Language Models (LLMs) incur quadratic attention complexity with input length, creating a major time bottleneck in the prefilling stage. Existing acceleration methods largely exploit attention score sparsity by est…
On the Power of Edge Independent Graph Models
Why do many modern neural-network-based graph generative models fail to reproduce typical real-world network characteristics, such as high triangle density? In this work we study the limitations of edge independent rando…
Clustering with Simplicial Complexes
In this work, we propose a new clustering algorithm to group nodes in networks based on second-order simplices (aka filled triangles) to leverage higher-order network interactions. We define a simplicial conductance func…
Clustering