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.
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.
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