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

Weiren YuWWW 2025 · OpenReview

TL;DR

SimEdge is a novel graph-theoretic similarity model that treats nodes and edges as mutually reinforcing entities: edges are similar if they connect similar nodes, and nodes are similar if they are linked by similar edges. Unlike traditional models like SimRank, SimEdge guarantees transitivity, allowing it to capture complex, weakly connected relationships in massive graphs with billions of edges while maintaining high accuracy and linear memory usage.

What Problem Does This Paper Address?

In the world of network analysis—whether you're looking at web hyperlinks, social networks, or neural synapses—measuring how "similar" two objects are is a foundational task. For years, the SimRank family of algorithms has been the go-to for node-to-node similarity. However, these models have a major blind spot: they struggle with edge-to-edge similarity and often fail to capture transitivity.

In technical terms, SimRank is a pseudometric that violates the triangle inequality. This leads to the "zero-similarity" problem: if edge A is similar to edge B, and B is similar to C, SimRank might still report that A and C have zero similarity because they don't share immediate neighbors. This makes it unreliable for critical applications like link spam detection (identifying clusters of suspicious hyperlinks) or neural synapse classification (distinguishing between different types of brain connections).

Methods

The authors introduce SimEdge, which operates on a "mutual reinforcement co-recursion" philosophy. The logic is elegant:

  1. Edge Similarity: Two edges are similar if their "heads" (targets) and "tails" (sources) are similar.
  2. Node Similarity: Two nodes are similar if their incoming and outgoing edges are similar.

By intertwining these two definitions, the model propagates similarity scores across the entire graph structure.

The Scalability Breakthrough: Standard iterative methods for this kind of problem require $O(m^2)$ memory (where $m$ is the number of edges), which is a death sentence for large-scale graphs. The authors developed a "column-by-column" computation technique (Algorithm 1) that reduces the memory requirement to linear memory ($O(km)$). This allows SimEdge to run on commodity hardware even when processing graphs with billions of edges.

Datasets

The researchers evaluated SimEdge across a diverse range of real-world and synthetic datasets:

  • NU (Neuronal): A connectivity network of neurons and synapses.
  • DP (DBLP): A co-authorship network from computer science publications.
  • AL (OpenFlights): A snapshot of global flight routes.
  • HP, AM, LJ: Citation networks (arXiv), Amazon co-purchasing, and LiveJournal social links.
  • EU & TW: Massive-scale datasets representing EU web hosting infrastructure and Twitter follower networks (up to 1.4 billion edges).

To establish "ground truth," the authors recruited experts (bioinformatics researchers, travel consultants, etc.) to manually score the similarity of pairs in the smaller datasets.

Key Insights and Ideas

  • Transitivity is the Secret Sauce: By mathematically proving that SimEdge fulfills the triangle inequality, the authors ensure that similarity "flows" correctly through the network. This allows the model to capture "weakly connected paths" (long, indirect chains of relationship) that SimRank and its variants completely ignore.
  • Beyond Neighbors: Most models only look at 1-hop or multi-hop neighbors. SimEdge looks at the roles edges play in connecting nodes, making it much more robust against "dead-loops" in cyclic graphs.
  • Exactness at Scale: Usually, scaling to billions of edges requires "lossy" approximations. SimEdge provides a way to compute these similarities with guaranteed accuracy within a tiny error bound ($\epsilon$).

Key Results

  • Superior Accuracy: On the DBLP (DP) dataset, SimEdge achieved a 0.97 Mean Average Precision (MAP) for edge similarity.
  • Outperforming the Classics: In node-to-node similarity tests, SimEdge outperformed SimRank by 19.3% and the state-of-the-art SimRank by 10.9%*.
  • Massive Scalability: While traditional SimRank-based approaches crashed due to memory explosion on the Twitter and EU datasets, SimEdge successfully processed them, demonstrating its readiness for "Big Data" environments.
  • Qualitative Success: Heatmaps of the similarity matrices showed that SimEdge naturally identifies "communities" (e.g., grouping papers by their publication venues like VLDB or SIGCOMM) more clearly than previous models.

Limitations and Future Work

While SimEdge is a significant leap forward, the paper leaves a few avenues for future exploration:

  • Weighted Graphs: The current model focuses primarily on the topology (structure) of the graph. Extending this to handle edge weights (e.g., the strength of a social tie or the frequency of a flight) could add another layer of depth.
  • Heterogeneous Networks: The paper focuses on graphs where all nodes/edges are of the same type. Adapting SimEdge for heterogeneous graphs (where nodes could be "users," "products," and "locations" simultaneously) would be a valuable next step.
  • Dynamic Graphs: The model is designed for static snapshots. In the future, the authors might look into how SimEdge can efficiently update similarity scores as edges are added or removed in real-time.

Summary updated

Abstract

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.
BibTeX
@inproceedings{yu2025simedge,
  author = {Weiren Yu},
  title = {{SimEdge: A Scalable Transitivity-Aware Graph-Theoretic Similarity Model for Capturing Edge-to-Edge Relationships}},
  booktitle = {The Web Conference},
  year = {2025},
  url = {https://openreview.net/forum?id=a0XN5HXy4F},
}
Figure