Estimating the number of triangles in a graph is a fundamental problem and has found applications in many fields. This problem has been widely studied in the context of graph stream processing. However, most of these algorithms are not robust or are limited to unweighted graphs. The reason why they do not robust is because most algorithms assume that the entire stream is predetermined before algorithm execution, rendering them vulnerable to adaptive inputs. For example, the first algorithm of this kind, which reduces the triangle counting problem to frequency moment computation. Their approach relies on CountSketch-based F_2 estimation, which has been shown to be vulnerable to adaptive adversarial attacks, potentially resulting in incorrect triangle count estimates. Besides, most prior work has focused on unweighted graphs, despite the fact that many real-world networks inherently involve edge weights. For example, when assessing the risk of a system, the weights of the edges may represent the level of risk of different paths. A weighted average of the triangular weights can reflect the combined risk of multiple paths in a system, avoiding the undue influence of a single high-risk path on the overall system assessment results.

In order to solve these problems, a research team led by Pan PENG published their new research on 15 January 2026 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
In their research, they employ the sketch switching technique combined with differential privacy to develop an adversarially robust streaming algorithm for triangle counting in unweighted graphs. Unlike conventional approaches that generate outputs only at the end of the stream, their proposed algorithm demonstrates strong tracking capabilities for triangle counting and exhibits resilience in adaptive streaming scenarios.
Additionally, they utilize L_1 sampling to develop a two-pass algorithm for estimating the total triangle weight in weighted graphs, which is applicable to fully dynamic streams.
Their work presents two main areas for potential improvement: First, while the adversarially robust algorithm demonstrates strong performance in pure insertion models, its extension to fully dynamic streams remains an open challenge. Second, the transition from the current two-pass implementation to a more efficient one-pass algorithm warrants further investigation.

DOI:10.1007/s11704-025-41203-9