3 papers
cs.DS2024
Space Complexity of Minimum Cut Problems in Single-Pass Streams
Matthew Ding, Alexandro Garces, Jason Li +4
We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the spec…
cs.LG2024
Even Sparser Graph Transformers
Hamed Shirzad, Honghao Lin, Balaji Venkatachalam +3
Graph Transformers excel in long-range dependency modeling, but generally require quadratic memory complexity in the number of nodes in an input graph, and hence have trouble scali…
cs.LG2024
A Theory for Compressibility of Graph Transformers for Transductive Learning
Hamed Shirzad, Honghao Lin, Ameya Velingker +3
Transductive tasks on graphs differ fundamentally from typical supervised machine learning tasks, as the independent and identically distributed (i.i.d.) assumption does not hold a…