10 papers
Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance
Jingbang Chen, Chenhao Ma, Yingli Zhou
Hypergraphs model interactions involving groups of entities, and finding highly connected groups is a fundamental task in analyzing these data. When interactions arrive and expire,…
The Price of Order in the Logarithmic Method
Sichen Wang, Zhipeng Lu, Jingbang Chen
The logarithmic method is a classical static-to-dynamic transformation: it stores one dynamic ordered set as several immutable static components and rebuilds them by merges. The sa…
Scalable Approximate Biclique Counting over Large Bipartite Graphs
Jingbang Chen, Weinuo Li, Yingli Zhou +5
Counting -bicliques in bipartite graphs is crucial for a variety of applications, from recommendation systems to cohesive subgraph analysis. Yet, it remains computationally…
Entrywise Approximate Laplacian Solving
Jingbang Chen, Mehrdad Ghadiri, Hoai-An Nguyen +2
We study the escape probability problem in random walks over graphs. Given vertices, and , the problem asks for the probability that a random walk starting at will hi…
Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-aware Index
Qiuyang Mang, Jingbang Chen, Hangrui Zhou +6
Bipartite graphs are ubiquitous in many domains, e.g., e-commerce platforms, social networks, and academia, by modeling interactions between distinct entity sets. Within these grap…
Scalable Algorithm for Finding Balanced Subgraphs with Tolerance in Signed Networks
Jingbang Chen, Qiuyang Mang, Hangrui Zhou +3
Signed networks, characterized by edges labeled as either positive or negative, offer nuanced insights into interaction dynamics beyond the capabilities of unsigned graphs. Central…
Nearly Optimal Internal Dictionary Matching
Jingbang Chen, Jiangqi Dai, Qiuyang Mang +2
We study the internal dictionary matching (IDM) problem where a dictionary containing substrings of a text is given, and each query concerns the occurrences o…
Sandpile Prediction on Undirected Graphs
Ruinian Chang, Jingbang Chen, Ian Munro +3
The model is a well-known model used in exploring . Despite a large amount of work on other aspects of sandpiles, t…
Exponential Convergence of Sinkhorn Under Regularization Scheduling
Jingbang Chen, Li Chen, Yang P. Liu +2
In 2013, Cuturi [Cut13] introduced the Sinkhorn algorithm for matrix scaling as a method to compute solutions to regularized optimal transport problems. In this paper, aiming at a…
Hardness of Graph-Structured Algebraic and Symbolic Problems
Jingbang Chen, Yu Gao, Yufan Huang +2
In this paper, we study the hardness of solving graph-structured linear systems with coefficients over a finite field and over a polynomial ring $\mathbb{F}[x_1,\ldo…