RECS: Robust Graph Embedding Using Connection Subgraphs
This work addresses the issue of unstable and poorly preserving graph embeddings for tasks like node classification and link prediction, offering a deterministic solution with significant performance gains.
The authors tackled the problem of unstable and structurally inaccurate graph embeddings by proposing RECS, a deterministic framework that uses connection subgraphs and electrical circuit analogies, achieving up to 36.85% improvement in multi-label classification over state-of-the-art methods.
The success of graph embeddings or node representation learning in a variety of downstream tasks, such as node classification, link prediction, and recommendation systems, has led to their popularity in recent years. Representation learning algorithms aim to preserve local and global network structure by identifying node neighborhood notions. However, many existing algorithms generate embeddings that fail to properly preserve the network structure, or lead to unstable representations due to random processes (e.g., random walks to generate context) and, thus, cannot generate to multi-graph problems. In this paper, we propose RECS, a novel, stable graph embedding algorithmic framework. RECS learns graph representations using connection subgraphs by employing the analogy of graphs with electrical circuits. It preserves both local and global connectivity patterns, and addresses the issue of high-degree nodes. Further, it exploits the strength of weak ties and meta-data that have been neglected by baselines. The experiments show that RECS outperforms state-of-the-art algorithms by up to 36.85% on multi-label classification problem. Further, in contrast to baselines, RECS, being deterministic, is completely stable.