Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings

Sudhanshu Chanpuriya, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Zhao Song, Cameron Musco

Abstract

Many models for undirected graphs are based on factorizing the graph's adjacency matrix; these models find a vector representation of each node such that the predicted probability of a link between two nodes increases with the similarity (dot product) of their associated vectors. Recent work has shown that these models are unable to capture key structures in real-world graphs, particularly heterophilous structures, wherein links occur between dissimilar nodes. In contrast, a factorization with two vectors per node, based on logistic principal components analysis (LPCA), has been proven not only to represent such structures, but also to provide exact low-rank factorization of any graph with bounded max degree. However, this bound has limited applicability to real-world networks, which often have power law degree distributions with high max degree. Further, the LPCA model lacks interpretability since its asymmetric factorization does not reflect the undirectedness of the graph. We address these issues in two ways. First, we prove a new bound for the LPCA model in terms of arboricity rather than max degree; this greatly increases the bound's applicability to many sparse real-world networks. Second, we propose an alternative graph model whose factorization is symmetric and nonnegative, which allows for link predictions to be interpreted in terms of node clusters. We show that the bounds for exact representation in the LPCA model extend to our new model. On the empirical side, our model is optimized effectively on real-world graphs with gradient descent on a cross-entropy loss. We demonstrate its effectiveness on a variety of foundational tasks, such as community detection and link prediction.

Introduction

Most graph embedding models rely on "dot product" similarity: if two nodes have similar vectors, they are likely to have an edge. This works well for homophily (e.g., friends sharing interests), but fails for heterophily, where links occur between dissimilar nodes, such as in dating apps or word-adjacency networks.

While recent models like Logistic Principal Component Analysis (LPCA) can handle heterophily and offer "exact representation," they rely on the graph's maximum degree for theoretical bounds. In real-world power-law networks, massive hubs make these bounds practically useless. Furthermore, LPCA uses an asymmetric factorization that lacks interpretability for undirected graphs.

Methods

We propose a symmetric, nonnegative model defined by the probability of an edge between nodes $i$ and $j$: $$\tilde{A}_{i,j} = \sigma(\mathbf{b}_i^\top \mathbf{b}_j - \mathbf{c}_i^\top \mathbf{c}_j)$$ Where $\sigma$ is the logistic function, $\mathbf{b}$ represents "attractive" or homophilous features, and $\mathbf{c}$ represents "repulsive" or heterophilous features. By forcing nonnegativity, the factors can be interpreted as soft community assignments.

Comparison of learned embeddings for SVD, BigClam, and the proposed model.

The Arboricity Breakthrough

We prove a new bound for exact representation based on arboricity ($\alpha$)—the minimum number of forests needed to cover a graph's edges. Unlike max degree, arboricity remains low even in graphs with massive hubs, provided the graph is generally sparse. Any graph with bounded arboricity can be exactly represented by our model with a rank of $O(\alpha^2)$.

Key Results

We evaluated the model on synthetic dating app data and real-world networks (BLOG, YOUTUBE, POS, PPI, AMAZON). On the synthetic dating app, our model perfectly captured both city (homophilous) and gender (heterophilous) structures, whereas baselines like BIGCLAM only identified cities.

Adjacency reconstruction and Frobenius error comparison across embedding lengths.

As shown in the reconstruction comparison, our model achieves significantly lower Frobenius error than SVD and BigClam, especially as embedding length increases. This demonstrates the model's ability to represent complex adjacency structures with low-rank factors.

Conclusion

By shifting theoretical guarantees to arboricity and utilizing a symmetric $BB^\top - CC^\top$ structure, we provide a model that is both mathematically robust and highly interpretable. The separation of attractive and repulsive factors allows for a clear understanding of link predictions in both homophilous and heterophilous contexts. Future work will address scaling to massive graphs using stochastic optimization techniques.

Summary updated

Abstract

Many models for undirected graphs are based on factorizing the graph's adjacency matrix; these models find a vector representation of each node such that the predicted probability of a link between two nodes increases with the similarity (dot product) of their associated vectors. Recent work has shown that these models are unable to capture key structures in real-world graphs, particularly heterophilous structures, wherein links occur between dissimilar nodes. In contrast, a factorization with two vectors per node, based on logistic principal components analysis (LPCA), has been proven not only to represent such structures, but also to provide exact low-rank factorization of any graph with bounded max degree. However, this bound has limited applicability to real-world networks, which often have power law degree distributions with high max degree. Further, the LPCA model lacks interpretability since its asymmetric factorization does not reflect the undirectedness of the graph. We address these issues in two ways. First, we prove a new bound for the LPCA model in terms of arboricity rather than max degree; this greatly increases the bound's applicability to many sparse real-world networks. Second, we propose an alternative graph model whose factorization is symmetric and nonnegative, which allows for link predictions to be interpreted in terms of node clusters. We show that the bounds for exact representation in the LPCA model extend to our new model. On the empirical side, our model is optimized effectively on real-world graphs with gradient descent on a cross-entropy loss. We demonstrate its effectiveness on a variety of foundational tasks, such as community detection and link prediction.
BibTeX
@misc{chanpuriya2021exact,
  author = {Sudhanshu Chanpuriya and Ryan A. Rossi and Anup Rao and Tung Mai and Nedim Lipka and Zhao Song and Cameron Musco},
  title = {{Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings}},
  year = {2021},
  eprint = {2111.03030},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.03030},
}
Figure