Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More

Sudhanshu Chanpuriya 1 Cameron Musco 1

Abstract

Clustering algorithms generally try to find groups of nodes
that are in line with graph homophily, wherein edges connect nodes with similar attributes, and wedges tend to beclosed (“a friend of a friend is a friend”). Only a small
number of clustering algorithms can be seen as capturing
heterophilous structures, such as (near) bipartiteness: forexample, algorithms for the max-cut problem (Grötschel &Pulleyblank, 1981) can find approximately bipartite structure in graphs. Approaches for the closely related task ofgraph simplification (also called graph compression) areoften more amenable than typical clustering approaches toaddressing heterophilous structure. Like clustering, simplification is focused on finding structure in graphs, but withthe goal of minimizing reconstruction error from a compressed representation. Algorithms for simplification workby merging edges or nodes (Toivonen et al., 2011; Garg
& Jaakkola, 2019), or by approximate factorization of theadjacency matrix (Nourbakhsh et al., 2014).

Algorithms for node clustering typically focus onfinding homophilous structure in graphs. That is,they find sets of similar nodes with many edges
within, rather than across, the clusters. However,graphs often also exhibit heterophilous structure,
as exemplified by (nearly) bipartite and tripartite
graphs, where most edges occur across the clusters. Grappling with such structure is typically left
to the task of graph simplification. We present a
probabilistic model based on non-negative matrix
factorization which unifies clustering and simplification, and provides a framework for modelingarbitrary graph structure. Our model is basedon factorizing the process of taking a random
walk on the graph. It permits an unconstrained
parametrization, allowing for optimization via
simple gradient descent. By relaxing the hard clustering to a soft clustering, our algorithm relaxes
potentially hard clustering problems to a tractableones. We illustrate our algorithm’s capabilities on
a synthetic graph, as well as simple unsupervised
learning tasks involving bipartite and tripartite
clustering of orthographic and phonological data.

We present a probabilistic framework which unifies nodeclustering and graph simplification and is applicable to both
homophilous and heterophilous structure. In particular, we
n×n
propose factoring an undirected graph A ∈ R+
into two
n×m
components: a bipartite graph V ∈ R+ , which connects
the n original nodes to m latent nodes, where m < n, and am×m, which is a graph on
smaller undirected graph W ∈ R+
the latent nodes. Intuitively, this factorization approximatestaking one step of a random walk on A as a three step
procedure: first taking one random step on V from theoriginal nodes to the latent nodes, then one random step
within the latent graph W , and finally one random step on
V back from the latent to the original nodes:

1. Introduction
A core method of finding structure in networks is mapping
nodes to some smaller set of node clusters based on structural similarity. There are various algorithms for this taskof node clustering, one of the most well-known being thenormalized cuts algorithm (Shi & Malik, 2000), which assigns clusters based on an eigenvector of the normalizedgraph Laplacian. This algorithm finds a hard clustering,where each node is mapped to exactly one cluster; soft clustering (Yu et al., 2005) relaxes this problem and instead
assigns nodes to clusters probabilistically, so that each node
is mapped to a categorical distribution over clusters.

π(A) ≈ π(V ) π(W ) π(V ⊤ ),(1)

where π denotes dividing each row of a matrix by its sum,yielding the random walk transition matrix corresponding
to the adjacency matrix. Figure 1 illustrates this process. As
we discuss in Section 3, this model permits a differentiable
parametrization, allowing for fitting via gradient descent ona simple cross-entropy loss. Further, we can ensure that thetransition matrix on the right-hand side is reversible, meaning that it corresponds exactly to one step of a random walkn×n
on some undirected graph B ∈ R+
. Our model allows
for retrieval of this B as a rank-m approximation of A,
connecting this clustering method to graph simplification.

1
University of Massachusetts Amherst. Correspondence to:Sudhanshu Chanpuriya <schanpuriya@umass.edu>.

Published at the Differentiable Almost Everything Workshop of the
40 th International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s).

1Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More

𝑛

𝜋(𝑨)

𝑛

𝑨

Our key contributions can be summarized as follows:𝜋(𝑩)𝑽• We present our latent random step model. To ourknowledge, this is the first probabilistic model for undirected graph simplification that accommodates arbitrary homophilous and heterophilous structure.

𝑚 𝑾• Unlike similar work, our model admits an unconstrained parametrization. Simple gradient descent (andits variants) on a natural probabilistic loss can be used
to fit our model, allowing for flexible node clustering and low-rank approximation of a weighted graph.
Modifying the latent graph W ranges the type of nodeclustering task through relaxations of potentially hard
problems like k-way max-cut.

Figure 1. Diagram of the latent random step model. A random
step on a graph A with n nodes is approximated by a random step
forward on a bipartite graph V , then a random step on a smallergraph W with m nodes, then a random step back on V .

Demonstrative Toy Graph. We construct a synthetic network that exhibits both homophily and heterophily as aconcrete demonstration of how our model can adapt to both.
Consider a union of 3 bicliques, each with 10 nodes in either set, for a total of 60 nodes. Figure 2 (left) is a plot of
this graph. We can naturally cluster the nodes in at least
two ways: either we find 3 homophilous clusters with mostedges within clusters (as in the min-cut task), or we find 2
heterophilous clusters with most edges across clusters (likethe max-cut task). As we discuss in Section 4, in our model,
this corresponds to fixing one of the following latent graphs
W , then finding a bipartite graph V that minimizes theapproximation error in Equation 1:




1 0 0
1 0 1
1
Wbiclique =.
Wclique = 0 1 0
3
2 1 0
0 0 1

• We apply our model and algorithm to real-world
data by simplifying weighted graphs constructed fromraw orthographic and phonological data. We findthat graphs with heterophilous structure naturally
arise when considering the sequences of letters andphonemes in words. From these graphs, our unsupervised algorithm finds heterophilous clusters that closelyalign with ground-truth labels.

2. Related Work
Our model can be represented as an approximate graph factorization of the form A ≈ U W U ⊤ , which has also been
employed in some prior works. Yu et al. (2005) present
such a model for use in soft clustering and also discuss its
interpretation in terms of random walks, but they focus on
the case where W is diagonal, that is, the homophilous case.
Perhaps the closest model to ours is that of Nourbakhsh
et al. (2014), who also allow their equivalent of W to be
non-diagonal. However, their experiments do not explore
non-homophilous clustering, and they do not work within
a fully probabilistic framework as we do; among other differences, the loss they optimize is based on Frobenius norm
rather than cross-entropy. While these are the two models
that are closest to ours, all three models fit under the umbrella of non-negative matrix factorization (NMF) for nodeclustering and graph simplification, for which there is otherprior work (Ding et al., 2008; Kuang et al., 2012).

In Figure 2 (right), we show the π(V ) matrices, which map
each node to a distribution over clusters, that result fromboth ways of clustering the graph. The one with Wclique
indeed assigns each node to three clusters, corresponding to
the three bicliques, so that edges occur only within clusters;
whereas the one with Wbiclique assigns each node to one oftwo clusters so as to split each biclique, such that edges
occur only across clusters. Each method also results in adifferent simplified graph B: the former erases the biclique
structure and results in three cliques; whereas the latter
erases the distinction between the three disjoint bicliques,
resulting in a single large biclique. The latter clustering may
be more useful for mining data structure in some applications, but most algorithms only allow for the former.

Adjacency

Clique10 20 30 40 50 60

Biclique

10 20 30 40 50 60

Our model, along with some of the other discussed models,can be seen as a very generalized variant of the well-known
stochastic block model (SBM) (Holland et al., 1983). The
key differences are that: 1) nodes in the SBM are assigned
to exactly one community, as opposed to our model’s distributional assignments; and 2) the central probability matrix
in the SBM gives probabilities of nodes in two communities being connected, which is slightly different from ourmodel, wherein the central matrix gives the proportion ofedges which occur between two communities; and 3) SBMs,
while capable of representing heterphilous structure, are

10 20 30 40 50 60

10
20
30
40
50
60
1
2
3

1
2

Figure 2. The synthetic graph A (left) and two different clusterings(right), for which we show B (top) and π(V )⊤ (bottom).

2

Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More

The transpose of this matrix isalso typically studied in the context of homophilous structure. As suggested by use of the term ‘latent’ states, ourmodel can also be seen as an instance of the Hidden Markov
Model (Baum & Petrie, 1966) to the process of taking arandom walk on a graph; unlike in most applications ofHMMs, here the analyzed process is explicitly first-order,
by construction. Finally, our fitting algorithm joins muchprior work as a relaxation of a computationally-hard nodepartitioning problem; perhaps best-known is the work of
Goemans & Williamson (1995), which gives a spectral relaxation of the max-cut problem. Unlike that work, we
provide no theoretical guarantees of performance, though
we observe good performance in experiments. On the other
hand, our framework can go well beyond max-cut to unify
min-cut, k-way max-cut, and more, depending on how thelatent graph W is set.

 −1
−1 ⊤
′−1
V
DV DB .
W DW
B ⊤ = V DV′
Note that if DV= DW , then the parenthesized parts of the
final expressions are equivalent. Further, with DB = DV ,the matrix is fully equal to its transpose and is therefore
symmetric. Explicitly, the matrix simplifies to the form
−1 ⊤
−1
V .
W DW
B = V DW

Hence reversibility is satisfied if the column-sums of the
bipartite graph V are equal to the degrees of the latentgraph W . If this condition is satisfied, the degrees DBof the reconstructed graph B, which corresponds to thetransition matrix π(B), are exactly the row-sums of V .
Parametrization. We can parametrize our model using
two matrices of free parameters, Wp ∈ Rm×m and Vp ∈Rn×m , to represent the latent graph W and the bipartite
graph V , respectively. Let σmat and σcol denote functions
which take the softmax of a matrix over all elements andover each column. We first construct W as follows:
W = σmat Wp + Wp⊤ ,3. Methodology
As stated in Section 1, we propose to approximately factorn×n
ize an undirected graph A ∈ R+
into a bipartite graphn×m
m×m
V ∈ R+
and a smaller undirected graph W ∈ R+.
We seek⊤π(A) ≈ π(V ) π(W ) π(V ) = π(B),which ensures both the positivity and the symmetry of W ;the softmax also ensures that all entries of W sum to 1. Let
DW be the diagonal matrix containing the degrees of W .
We now construct V with:(2)

where again π denotes dividing each row of a matrix by its
sum, yielding a random walk transition matrix. B, which isn×n
a symmetric matrix in R+, is a rank-m reconstruction ofA (that is, a simplified version of A); like A, B can be seen
as an undirected, weighted graph on the original n nodes.

V = (σcol (Vp )) DW ,which ensures the positivity of V and the reversibility criterion, that the column-sums of V are equal to the degrees
W . Note that while we provide the full parametrization forgenerality, in the experiments in this paper, we fix W andfind V , so Wp is not used.

Reversibility Criterion. We first establish a condition on
V and W for the transition matrix π(B) from Equation 2
to be reversible, that is, to correspond to a random step inan undirected graph B. This condition is crucial for fitting
the model to not only yield a clustering of the nodes (givenby π(V )), but also a simplified graph B. Reversibility is
n×nsatisfied iff there exists a diagonal matrix DB ∈ R+
forwhich the product DB π(B) is a symmetric matrix B. We
assume that V and W are not just non-negative, but strictly
positive; we will only parametrize such V and W anyway.

Fitting. We can fit this model via gradient descent on asimple and natural cross-entropy loss:XĀij log B̄ij ,(3)
L=−i,j∈[n]where an overline denotes dividing a matrix by the sum of
all of its elements. This loss views the adjacency matrixof the original graph A and that of the reconstructed graph
B as probability distributions over pairs of nodes. Minimizing it tries to place more mass in B among node pairs
which correspond to edges in A. We additionally use an L2
regularization penalty on the parameters.

′
Let DV and DV
denote the diagonal matrices whose diagonal elements are the row-sums and column-sums of V ,respectively, and let DW denote the row-sums of W (which
are equivalent to the columns-sums since W is symmetric).
We have reversibility if, for some DB , the following matrix
is symmetric:

Our implementation uses PyTorch (Paszke et al., 2019)
for automatic differentiation and minimizes the loss using the SciPy (Jones et al., 2001) implementation of the
L-BFGS (Liu & Nocedal, 1989; Zhu et al., 1997) algorithm with default hyperparameters. The free parameters
are initialized uniformly at random on (−10−2 , +10−2 ).
The regularization term for the loss is set to 10−1 times themean squared norm of the free parameters.

B = DB π(V ) π(W ) π(V ⊤ )



′−1 ⊤
−1
−1
V
W DV
V DW
= DB D V

′−1 ⊤
−1
−1
V
.
W DV
V DW
= DB DV3

Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More

AH IH
EH
AA AE
IY EY
AO OW
AY
UW

1.00
0.75
0.50
0.25
0.00

n r l md v c t bw f s p h x z j k q g y u o i a e

AW UH
ZH OY
TH DH
Y
G
JH CH HH W NG
ZBF V
P
M
SH
T
D K

Figure 3. Results of bipartite clustering of the orthographic adjacency graph. For each letter, we plot the probability of assignment
to the first of the two clusters, that is, the first column of π(V ).
Letters are sorted in ascending order of this probability.

SL R
N

Figure 4. Results of tripartite clustering of the phonological adjacency graph. This ternary plot projects the 3D categorical distributions given by the cluster affinities π(V ) onto a 2D space. Eachcorner corresponds to a different cluster.

4. Experiments on Real-World Networks
To illustrate the power of our model and algorithm, we perform some experiments on real-world datasets made fromEnglish-language orthographic (spelling) and phonological(pronunciation) data. In particular, to find structure in thisdata in an unsupervised manner, we construct graphs fromit and factorize them using the following two latent graphs
to find (soft) bipartite and tripartite clusterings:




0 1 1
1 0 1
1
1 0 1 .
Wbi =Wtri =
2 1 0
6
1 1 0

we convert these words to sequences of phonemes as determined by the CMU Pronouncing Dictionary 2 . We use the
NLTK API (Bird et al., 2009) to access the dictionary. The
graph is similar to the orthographic one: the nodes of thisgraph correspond to 39 English language phonemes, andthe edge weights correspond to the number of times, acrossall common words in the dictionary, that two phonemes are
directly adjacent.

Factorizing with both latent graphs corresponds to finding
clusters such that intra-cluster edges are minimized: with
Wbi , we find two clusters, and with Wtri , we find three clusters such that roughly one-third of the total edge weight is
assigned to each of the three pairs of clusters. These clustering tasks can be seen as soft relaxations of the standard and3-way max-cut problems.

While applying a bipartite node clustering to phonological
data also separates vowel sounds as with the orthographic
data, we find that significantly more interesting structure
can be extracted with a tripartite clustering, using the latentgraph Wtri . See Figure 4 for a plot of the resulting cluster
affinities π(V ). The clustering strongly reflects groundtruth categorizations of the phonemes. Most striking is that
one of the clusters is dominated by vowel sounds, and thatvowel, stop, and nasal/liquid sounds have high affinities forthree distinct clusters.

Orthographic Adjacency. We construct a graph based onspellings of common English language words. The nodes of
the graph correspond to the 26 letters, and the edge weights
correspond to the number of times, across all common
words, that two letters are directly adjacent. For the listof words, we use the 20K most frequently-used English
words as determined by the Google Books Ngram Viewer 1 .

5. Conclusion
We propose our latent random step model and perform nodeclustering on a synthetic graph and real-world orthographic
and phonological graphs, finding structure in the graphs that
goes beyond typical homophilous clusterings. The simplicity and flexibility of the model suggests several directions
for extension of this work. We focus here on the setting
where the latent graph W is fixed and the bipartite graph V
is fit. We could instead attempt to fit both at once, yielding
the full graph simplification setting. Besides this, there may
be a straightforward extension to data and graphs of greater
scale than we consider here: the cross-entropy loss (Equation 3) could be approximated by sampling of node pairs
based on the weights of Ā, allowing for an SGD fitting algorithm. More broadly, we hope that considering latent graphs
beyond homophilous clusters can expand the applicabilityof node clustering, out to new problems and fields.

We perform a bipartite clustering of this graph using Wbi
based on the intuition that the spelling of words very roughly
tends to alternate between vowels and consonants. See
Figure 3 for the results. Indeed, the resulting clusteringreflects the intuition: if we convert the soft clustering π(V )into a hard clustering by assigning each letter to the cluster
for which it has higher probability, this clustering cleanly
divides the letters into vowels and consonants. (The letter‘y’, which can act as both, is placed into the vowel cluster,
but with the least probability among the vowels.)
Phonological Adjacency. We now construct a graphbased on pronunciations of English language words. Using
the same list of common words as for the orthographic data,
1

ER

Vowel
Stop
Fricative
Semivowel
Affricate
Aspirate
Nasal
Liquid2

Specifically, we use the list on the google-10000-english repo.

4This resource is hosted online at the speech.cs.cmu website.

Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More

References

Shi, J. and Malik, J. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine
intelligence, 22(8):888–905, 2000.

Baum, L. E. and Petrie, T. Statistical inference for probabilistic functions of finite state markov chains. The annals
of mathematical statistics, 37(6):1554–1563, 1966.

Toivonen, H., Zhou, F., Hartikainen, A., and Hinkka, A.
Compression of weighted graphs. In Proceedings of the
17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 965–973, 2011.

Bird, S., Klein, E., and Loper, E. Natural language processing with Python: analyzing text with the natural language
toolkit. ” O’Reilly Media, Inc.”, 2009.

Yu, K., Yu, S., and Tresp, V. Soft clustering on graphs. In
Nips, pp. 1553–1560, 2005.

Ding, C., Li, T., and Jordan, M. I. Nonnegative matrix
factorization for combinatorial optimization: Spectralclustering, graph matching, and clique finding. In 2008
Eighth IEEE International Conference on Data Mining,pp. 183–192. IEEE, 2008.

Zhu, C., Byrd, R. H., Lu, P., and Nocedal, J. Algorithm 778:
L-BFGS-B: Fortran subroutines for large-scale boundconstrained optimization. ACM Transactions on Mathematical Software (TOMS), 23(4):550–560, 1997.

Garg, V. and Jaakkola, T. Solving graph compression via optimal transport. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.),
Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Goemans, M. X. and Williamson, D. P. Improved approximation algorithms for maximum cut and satisfiability
problems using semidefinite programming. Journal of
the ACM (JACM), 42(6):1115–1145, 1995.
Grötschel, M. and Pulleyblank, W. R. Weakly bipartite
graphs and the max-cut problem. Operations researchletters, 1(1):23–27, 1981.
Holland, P. W., Laskey, K. B., and Leinhardt, S. Stochastic
blockmodels: First steps. Social networks, 5(2):109–137,
1983.
Jones, E., Oliphant, T., Peterson, P., et al. SciPy: Open
source scientific tools for Python, 2001. URL http://www.scipy.org/.
Kuang, D., Ding, C., and Park, H. Symmetric nonnegative
matrix factorization for graph clustering. In Proceedings of the 2012 SIAM international conference on data
mining, pp. 106–117. SIAM, 2012.
Liu, D. C. and Nocedal, J. On the limited memory BFGS
method for large scale optimization. Mathematical Programming, 45(1-3):503–528, 1989.
Nourbakhsh, F., Bulo, S. R., and Pelillo, M. A matrix
factorization approach to graph compression. In 2014
22nd International Conference on Pattern Recognition,
pp. 76–81. IEEE, 2014.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J.,
Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga,
L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison,M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L.,
Bai, J., and Chintala, S. PyTorch: An imperative style,high-performance deep learning library. In 2019, pp.
8024–8035. 2019.
5