Networks are ubiquitous in modern science and technology, often containing millions of nodes and edges. The size of these networks often makes full-scale analysis computationally expensive, and in many cases it is even impossible to store the entire network. Sublinear-time algorithms offer a powerful solution by providing approximate results with only partial access to the network data, significantly reducing the time and computational resources needed for analysis. This talk presents two such algorithms: one for clustering signed graphs, which quickly groups nodes based on positive and negative relationships without needing to examine the entire graph, and another for opinion estimation in the Friedkin–Johnsen opinion formation model, which approximates steady-state opinions efficiently. These methods exemplify how sublinear-time algorithms can unlock insights from vast networks with limited data access.

This talk is based on two papers which appeared at ICML’22 and at the WebConf’24, and are joint work with Yinhao Dong and Pan Peng.