  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.
