SimEdge: A Scalable Transitivity-Aware Graph-Theoretic Similarity Model for Capturing Edge-to-Edge Relationships

Measuring similarity based on network topology is a crucial task in the realm of web search. While many well-established similarity measures (e.g. SimRank) focus on assessing node-to-node similarity, capturing edge-to-edge relationships is equally important in many applications (e.g. link spam detection). However, existing node-to-node similarity measures from the SimRank family may violate the triangular inequality. When applied directly to assessing edge-to-edge similarity, such measures may fail to capture transitive relationships and misrepresent dissimilarity between nodes. In this paper, we propose a novel similarity measure, SimEdge, which can capture transitive relationships for assessing edge-to-edge similarity. The intuition of SimEdge revolves around a mutual reinforcement co-recursion: "two edges are assessed as similar if they are linked to similar nodes, and two nodes are assessed as similar if they are linked to similar edges." We show that SimEdge guarantees the transitivity of similarity, and enhances the accuracy of the node-to-node SimRank similarity without misrepresenting dissimilarity between nodes. For large-scale graphs, we also propose efficient techniques to compute SimEdge similarities in linear memory with guaranteed accuracy. Our empirical evaluation on various datasets validates that SimEdge is highly effective in capturing transitive edge-to-edge relationships, while offering a more reliable assessment of node-to-node similarity. Moreover, SimEdge shows superior scalability in assessing edge-to-edge similarities on large-scale graphs with billions of edges.