# Retrieving Top Weighted Triangles in Graphs

arXiv: https://arxiv.org/abs/1910.00692 · HTML: https://mlsanity.com/paper/1910.00692/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2019.

## Built on by (most cited first, 2 of 2)

- [A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations](https://mlsanity.com/paper/2101.07730/) (2021)
- [Exact Learning of Weighted Graphs Using Composite Queries](https://mlsanity.com/paper/2511.14882/) (2025)

## Abstract (arXiv)

Pattern counting in graphs is a fundamental primitive for many network analysis tasks, and a number of methods have been developed for scaling subgraph counting to large graphs. Many real-world networks carry a natural notion of strength of connection between nodes, which are often modeled by a weighted graph, but existing scalable graph algorithms for pattern mining are designed for unweighted graphs. Here, we develop a suite of deterministic and random sampling algorithms that enable the fast discovery of the 3-cliques (triangles) with the largest weight in a graph, where weight is measured by a generalized mean of a triangle's edges. For example, one of our proposed algorithms can find the top-1000 weighted triangles of a weighted graph with billions of edges in thirty seconds on a commodity server, which is orders of magnitude faster than existing "fast" enumeration schemes. Our methods thus open the door towards scalable pattern mining in weighted graphs.