SSNE: Effective Node Representation for Link Prediction in Sparse Networks

Ming-Ren Chen, Ping Huang, Yu Lin, Shi-Min Cai

TL;DR

This paper introduces SSNE, a novel graph embedding method designed specifically for link prediction in sparse networks. By transforming network structure into a theoretical co-occurrence probability matrix (SNHAM) and then mapping it to a low-dimensional feature space using a neural network, SSNE achieves superior link prediction performance compared to existing methods, especially in sparse network scenarios.

What Problem Does This Paper Address?

Complex networks, representing everything from social interactions to biological systems, are constantly evolving, and predicting future connections (link prediction) is crucial for understanding this evolution. While graph embedding techniques have shown promise, most existing methods struggle with sparse networks – networks with relatively few connections compared to the number of entities. These methods often rely on random walks, which are sensitive to parameter tuning and can accumulate errors, leading to poor performance in sparse settings. The paper aims to bridge this gap by developing a graph embedding approach that is robust and effective for link prediction in these challenging sparse network environments.

Methods

The core of SSNE lies in its two-step process:

  1. Sparse Structural Network Embedding (SNHAM) Matrix Construction: Instead of relying on random walks, SSNE transforms the network's adjacency matrix into a "Sum of Normalized H-order Adjacency Matrix" (SNHAM). This matrix captures theoretical co-occurrence probabilities between node pairs, effectively encoding structural information. The SNHAM algorithm involves calculating normalized h-order transition probability matrices and summing them. A key advantage is that it reduces the number of tunable parameters to just one (the order 'h'), making it less sensitive to empirical tuning compared to random-walk-based methods.
  2. Neural Network for Node Representation: The SNHAM matrix is then fed into a single-hidden-layer feedforward neural network. This network learns to map the SNHAM matrix into a lower-dimensional feature matrix, where each node is represented by a d-dimensional vector. The paper demonstrates that this mapping operation is equivalent to a variation of Singular Value Decomposition (SVD), which significantly improves computational efficiency. The neural network is trained by minimizing a loss function that measures the difference between the SNHAM matrix and the network's output.

Finally, nodal similarities are calculated using the Euclidean distance between these learned feature vectors, and these similarities are used to predict potential links.

Datasets

The paper evaluates SSNE on six real-world networks:

  • Brain: Neuronal connection network.
  • Yeast: Biological network of proteins and interactions.
  • Air: Air traffic control network.
  • Road: Road network in Minnesota.
  • Twitter: User retweeting network.
  • Power: U.S. west power grid network.

Additionally, two types of artificial network models were used:

  • Barabasi-Albert (BA) network model: Simulates scale-free properties.
  • Watts-Strogatz (WS) network model: Simulates small-world properties.

These datasets were chosen to represent a range of network densities and structures, with a particular focus on sparse networks.

Key Insights and Ideas

  • SNHAM as a robust alternative to random walks: The paper successfully demonstrates that a theoretically derived co-occurrence matrix (SNHAM) can effectively capture network structure without the pitfalls of random walk sampling, especially in sparse networks. This reduces parameter sensitivity and potential error accumulation.
  • SVD equivalence for efficiency: Proving the mapping operation to be an SVD variation is a significant insight. It not only validates the neural network's approach but also provides a computationally efficient way to obtain the node representations, crucial for large-scale networks.
  • SSNE's strength in sparsity: The experimental results consistently show SSNE outperforming other methods on sparse networks, highlighting its specialized design for this challenging scenario. This suggests a new direction for graph embedding research focused on network density.
  • Parameter insensitivity: The study finds that SSNE is generally insensitive to its adjustable parameters (h and p), making it more practical and easier to use than methods requiring extensive parameter tuning.

Key Results

  • Superior performance on sparse networks: SSNE achieved the best link prediction performance (measured by AUC) on several real-world sparse networks (Road, Twitter, Power) and artificial sparse networks.
  • Competitive performance on denser networks: While excelling in sparsity, SSNE also showed comparable performance to established methods on denser networks like Brain and Yeast.
  • Parameter stability: The study showed that varying the order 'h' and dimension reduction ratio 'p' had minimal impact on SSNE's performance, confirming its robustness. For instance, setting h=10 and p=0.1 was found to be a good default for near-optimal performance.
  • Efficiency: While SSNE's running time was longer than some structural similarity indexes, it was significantly faster than matrix optimization methods and comparable to or better than some graph embedding methods, especially considering its SVD-based optimization.

Limitations and Future Work

  • Computational Cost: While more efficient than some methods, SSNE's running time can still be substantial for very large networks due to the matrix computations involved in SNHAM.
  • Future Work: The authors suggest further exploring the relationship between network sparsity and link prediction performance, as well as investigating SSNE's applicability to dynamic networks and networks with node attributes. They also mention the potential for further optimization of the SNHAM algorithm and the neural network architecture.

Summary updated

Abstract

Graph embedding is gaining popularity for link prediction in complex networks. However, few works focus on the effectiveness of graph embedding models on link prediction in sparse networks. This paper proposes a novel graph embedding model, Sparse Structural Network Embedding (SSNE), to obtain node representation for link predication in sparse networks. The SSNE first transforms the adjacency matrix into the S μ m of Normalized H-order Adjacency Matrix (SNHAM) and then maps the SNHAM matrix into a d-dimensional feature matrix for node representation via a neural network model. The mapping operation is proved to be an equivalent variety of singular value decomposition. Finally, we calculate nodal similarities for link prediction based on the d-dimensional feature matrix. The extensive testing experiments based on artificial and real sparse networks suggest that the SSNE shows the effective node representation for link prediction in sparse networks, supported by the better link prediction performance compared to those of structural similarity indexes, matrix optimization, and other graph embedding models.
BibTeX
@inproceedings{chen2021ssne,
  author = {Ming-Ren Chen and Ping Huang and Yu Lin and Shi-Min Cai},
  title = {{SSNE: Effective Node Representation for Link Prediction in Sparse Networks}},
  booktitle = {IEEE Access},
  year = {2021},
  url = {https://openreview.net/forum?id=0ZHlkNExM4},
}
Figure