# Dynamic Structural Similarity on Graphs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2018.

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

- [ODEBrain: Continuous-Time EEG Graph for Modeling Dynamic Brain Networks](https://mlsanity.com/paper/2602.23285/) (2026)
- [DRESS: A Continuous Framework for Structural Graph Refinement](https://mlsanity.com/paper/2602.20833/) (2026)
- [Breaking Hard Isomorphism Benchmarks with DRESS](https://mlsanity.com/paper/2603.18582/) (2026)
- [GRFBrain: Graph-Structured Rectified Flows for EEG Dynamic Modeling](https://mlsanity.com/paper/2609.37934/) (2026)

## Abstract (arXiv)

One way of characterizing the topological and structural properties of vertices and edges in a graph is by using structural similarity measures. Measures like Cosine, Jaccard and Dice compute the similarities restricted to the immediate neighborhood of the vertices, bypassing important structural properties beyond the locality. Others measures, such as the generalized edge clustering coefficient, go beyond the locality but with high computational complexity, making them impractical in large-scale scenarios. In this paper we propose a novel similarity measure that determines the structural similarity by dynamically diffusing and capturing information beyond the locality. This new similarity is modeled as an iterated function that can be solved by fixed point iteration in super-linear time and memory complexity, so it is able to analyze large-scale graphs. In order to show the advantages of the proposed similarity in the community detection task, we replace the local structural similarity used in the SCAN algorithm with the proposed similarity measure, improving the quality of the detected community structure and also reducing the sensitivity to the parameter ε of the SCAN algorithm.