73 citations · 116 across the 12 of their papers we have counts for
14 papers
Graph Anomaly Detection with Unsupervised GNNs
Lingxiao Zhao, Saurabh Sawlani, Arvind Srinivasan +1
Graph-based anomaly detection finds numerous applications in the real-world. Thus, there exists extensive literature on the topic that has recently shifted toward deep detection mo…
Fast Attributed Graph Embedding via Density of States
Saurabh Sawlani, Lingxiao Zhao, Leman Akoglu
Given a node-attributed graph, how can we efficiently represent it with few numerical features that expressively reflect its topology and attribute information? We propose A-DOGE,…
A Study of Performance of Optimal Transport
Yihe Dong, Yu Gao, Richard Peng +2
We investigate the problem of efficiently computing optimal transport (OT) distances, which is equivalent to the node-capacitated minimum cost maximum flow problem in a bipartite g…
Flowless: Extracting Densest Subgraphs Without Flow Computations
Digvijay Boob, Yu Gao, Richard Peng +4
We propose a simple and computationally efficient method for dense subgraph discovery, which is a classic problem both in theory and in practice. It is well known that dense subgra…
Faster width-dependent algorithm for mixed packing and covering LPs
Digvijay Boob, Saurabh Sawlani, Di Wang
In this paper, we give a faster width-dependent algorithm for mixed packing-covering LPs. Mixed packing-covering LPs are fundamental to combinatorial optimization in computer scien…
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
David Durfee, Laxman Dhulipala, Janardhan Kulkarni +3
In this paper we study the problem of dynamically maintaining graph properties under batches of edge insertions and deletions in the massively parallel model of computation. In thi…
ZeroER: Entity Resolution using Zero Labeled Examples
Renzhi Wu, Sanya Chaba, Saurabh Sawlani +2
Entity resolution (ER) refers to the problem of matching records in one or more relations that refer to the same real-world entity. While supervised machine learning (ML) approache…
Near-Optimal Fully Dynamic Densest Subgraph
Saurabh Sawlani, Junxing Wang
We give the first fully dynamic algorithm which maintains a -approximate densest subgraph in worst-case time per update. Dense subgraph discove…
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Timothy Chu, Yu Gao, Richard Peng +3
We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collec…
Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Matthew Fahrbach, Gary L. Miller, Richard Peng +3
Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides a…
On Computing Min-Degree Elimination Orderings
Matthew Fahrbach, Gary L. Miller, Richard Peng +3
We study faster algorithms for producing the minimum degree ordering used to speed up Gaussian elimination. This ordering is based on viewing the non-zero elements of a symmetric p…
Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent
David Durfee, Kevin A. Lai, Saurabh Sawlani
We present preconditioned stochastic gradient descent (SGD) algorithms for the minimization problem in the overdetermined case, where there are far…
Density Independent Algorithms for Sparsifying -Step Random Walks
Gorav Jindal, Pavel Kolev, Richard Peng +1
We give faster algorithms for producing sparse approximations of the transition matrices of -step random walks on undirected, weighted graphs. These transition matrices also for…
Pebbling Meets Coloring: Reversible Pebble Game On Trees
Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani
The reversible pebble game is a combinatorial game played on rooted DAGs. This game was introduced by Bennett (1989) motivated by applications in designing space efficient reversib…