PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Authors: Daniel Zilberg
Ron Levie
Venue: ICML 2025 poster (2025)
Keywords: graph representation learning
graph autoencoder
regularity lemma
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose a universal graph autoencoder, based on a non-Euclidean decoder, that can approximate any graph.

Abstract: We propose PieClam (Prior Inclusive Exclusive Cluster Affiliation Model): a graph autoencoder, where nodes are embedded into a code space by an algorithm that maximizes the log-likelihood of the decoded graph. PieClam is a community affiliation model that extends well-known methods like BigClam in two main manners. First, instead of the decoder being defined via pairwise interactions between the nodes in the code space, we also incorporate a learned prior on the distribution of nodes in the code space, turning our method into a graph generative model. Secondly, we generalize the notion of communities by allowing not only sets of nodes with strong connectivity, which we call inclusive communities, but also sets of nodes with strong disconnection, which we call exclusive communities. By introducing a new graph similarity measure, called the log cut distance, we show that PieClam is a universal autoencoder, able to uniformly approximately reconstruct any graph. Our method is shown to obtain competitive performance in graph anomaly detection and link prediction benchmarks.

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Daniel Zilberg'
Ron Levie
Abstract
of advantages. While different graphs can have different sizes and topologies, the code space is fixed with a fixed dimension. This helps when learning downstream tasks, where the representation of the graph in the code space can be processed. For example, in link prediction, one infers unknown edges by defining (Kipf & Welling, 2016) or learn- ing (Kumar al., 2020) a function that takes pairs of nodes in the code space and predicts if there is an edge between them. In anomaly detection, one defines (Ding et al., 2019 90; Fan et al.. 2020) or learns (Chen et al., 2020b; Ding et al., 2021) a function that takes the representation of a node and its neighborhood and predicts this node is normal or an anomaly. In graph and node classification, the graph is represented in the code space, and one learns a model that predicts from this representation the classes of the nodes of the graph (Kipf & Welling, 2017; Gilmer et al., 2017a).
We propose PieClam (Prior Inclusive Exclusive Cluster Affiliation Model): a graph autoencoder, where nodes are embedded into a code space by an algorithm that maximizes the log- lilliielihood of the decoded graph. PieClam is a community af- filiation model that extends well-known methods like BigClam in two main manners. First, instead of the decoder being defined via pairwise interac- tions between the nodes in the code space, we also incorporate a learned prior on the distribution of nodes in the code space, turning our method into a graph generative model. Secondly, we generalize the notion of communities by allowing not only sets of nodes with strong connectivity, which we call inclusive communities, but also sets of nodes with strong disconnection, which we call exclu- sive communities. By introducing a new graph similarity measure, called the log cut distance, we show that PieClam is a universal autoencoder. able uniformly approximately reconstruct any graph. Our method is shown to obtain competitive performance in graph anomaly detection and link prediction benchmarks.
Our Contribution. In this paper, we derive new graph autoencoder from a statistical model of graphs. In our model, similarly to Stochastic Block Models (SBM) (Nowicki & Snijders, 2001b; Lee & Wilkinson, 2019) and community- based statistical models (Airoldi al., 2008; Yang & Leskovec, 2013), graphs are generated from a combination of intersecting communities/cliques Namely, each node belongs to different subset of a predefined set of com- munities, and the affiliations of the nodes to the different communities determine the probabilities of the edges of the graph. Here, the estimation the community affiliations is seen as an encoder of graphs to a community affiliation space, and the computation of the corresponding edge prob- abilities is seen a decoder. As opposed past works, we consider two types of generalized communities. First, standard inclusive communities, where any two nodes in the same community are likely to be connected. Second, we propose exclusive communities, where belonging to the same community reduces the probability of nodes being connected.
1. Introduction
In recent years, considerable research has concentrated graph representation learning, aiming to develop vector rep- resentations for graph entities, including nodes, edges, and subgraphs (Hamilton et al., 2017; Chen et al., 2020a). In graph autoencoders, e.g., (Kipf & Welling, 2016; Grover al., 2019; Samanta et al., 2020: Mehta et al., 2019), the vertices of a graph are embedded in a code space, where edges are inferred from the locations of the vertices in this space. Encoding graphs into standard space has a number
'Faculty of Mathematics, Technion- Israel Institute of Technol- ogy, Haifa, Israel. Correspondence to: Daniel Zilberg ddannyzil- berg @ farg@gmail.com com> Ron Levie <levicron wet.chiinn.cc.l........
For illustration, consider social network of employ- ers/recruiters and employees/job-seeeen. Such network has roughly bipartite components, where job-seekers do not tend to connect to other seekers, and employers do not connect to other employers, but employers and seekers of the same subsector tend to connect. Hence, inclusive com-
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
munities for such graph can correspond job titles or
2. Community Affiliation Models With Prior
subsectors, and exclusive communities can correspond to sets of job-seekers and sets of employees from the same sec- tor. For example, while the inclusive community of product management will tend to connect all employers and special- ists of product management to a "clique-like" community, the two exclusive communities of employers and of special- ists of product management will each tend to delete the links between pairs of employers and between pairs of employees, creating bipartite structure.
2.1. Notations
We denote by [R,, the non-negative real numbers. We denote "and" by A. We denote matrices as boldface capital letter
B = (D vectors as boldface lowercase letters b (bn Ju. and scalars as lowercase letters b. Vectors b E R N are always column vectors. The rows of matrix B E R NxC are denoted by the same letter in lowercase b, where b, E IRC where we write in short byj E R A diagonal matrix D E NNN with diagonal entries d is denoted by diag(d) =
To formalize the above ideas, we propose the Prior Inclusive Exclusive Cluster Affiliation Model (PieClam). This model represents graphs as overlapping inclusive and exclusive communities. In addition to embedding the nodes of a given graph in the community code space, our model also be
The le norm of a vector b E R is defined to be ||b|| = (E 6g)
A graph is denoted by G = ([N], E, A), where [N] = (1,..., .N is the set of N nodes, S [M] [N] is the set of edges, and A {0, 10.1 is the adjacency ma- trix. For weighted graphs, A E [0, NJNN,, where an,m is the edge weight of (n, m).. In this work we focus on undi- rected graphs, for which (m, n) E E' + (n,
learns prior the code space, so new graphs generated from the learned model. This makes PieClam a graph generative model, like, e.g., (Kipf & Welling, 2016; Grover et al., 2019; Samanta et al., 2020; Mehta et al., 2019; Sun et al., 2019).
E E, and A = AA Any pair (n, m) E [N] x [N] is called a dyad. The neighborhood of a node n E [N] is [n)) = {m E [N] (m, n) E E). A graph-signal is a graph with node fea- tures G = ([AV), E, A, X) where X = [
m) (n,m)
To model both types of communities, we propose new type of decoder based on the Lorentz, inner product, in which case the code space is typically called a pseudo Euclidean space (Greub, 1963). The addition of exclusive communities in our model is not merely aimed at improving it heuristically for special graphs like social networks. Rather, we prove in Thcorems 3.7 and 3.8 that using exclusive communities (via the Lorentz inner product) makes our model universal, namely, able to approximate with fixed budget of param- eters any graph. This is in contrast to standard decoders based on merely inclusive communities, which we show are unable to represent many graphs.
J.N E RN X,, RD, and D is called the feature dimension. A random graph is graph-valued valued random variable. Given a random graph with nodes [N], we denote the event (n, m) E E by n ~ m, and the event (n, m) & E by -(n ~ m)) A graph is bipartite if its vertex set [AV] can be partitioned into two disjoint sets U and V. with 24 V = [N], such that every edge has one endpoint in l and the other in V.
2.2. BigClam
To formalize this universality property, we propose a new similarity measure between graphs with edge probabilities, that we call the log cut distance. We formalize the universal- ity of our model follows: one can choose the dimension of the code space (the number of communities) priori, and guarantee that any graph of any size and topology can be approximated up to small log cut distance by decoding points from this fixed space. We show that other related decoders do not satisfy this universality property.
Our model PieClam best understood as an extension of the BigClam model (Yang & Leskovec, 2012). The code space in BigClam is RC, where each axis is interpreted as a com- munity. Each entry f of point f = (f' fo) E RC is interpreted as how much the point belongs to community e, where 0 means "not included in e" and 1 "included." In this paper we call RC the affiliation space (AS), and call any point in the affiliation space an affiliation feature (AF).
BigClam is a model where simple random graph is decoded from a sequence of AFs F {fn (f) ......, "r),,,, in the AS. For each pair of nodes + m E [N], the probability of the event -(n ~ m) (no edge between n and m), given their amount of membership in the same community c, is defined to be
In Section 4 we support our construction with experiments, where our models achieve competitive performance with respect state of the art. First, we use PieClam to perform graph anomaly detection. Here, PieClam learns a proba- bilistic model given graph, and this model can be used for inspecting the probabilities of different nodes in this graph: nodes with low probabilities are deemed to be anomalies. Then, we use PieClam to predict edges in link prediction benchmarks.
P(-(n m)]ff, fm) e -Jat
Appendix B has extended discussion on related work.
BigClam makes two assumptions of independence. First, the membership in one community does not affect the mem-
2

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
bership in another community. Hence,
2.3. Inclusive-Exchusive Cluster Affiliation Model
P(-(n~~ F) = P(-(n~ ~ (o))=m)))))) m))]fn fm) = - ff
The BigClam decoder has limitation due to a "triangle inequality type" behavior. Namely, suppose that we would like to construct two features f1 and f2 with strong con- nectivity to a third feature f3. and we are limited by fixed affiliation feature dimension C. A naive approach to achieve this would be to put fl and fz close to fg so they have large inner products f f3 and f fg. This would mean that fj fe would also be large, so fi would be strongly connected to f2 under the BigClam model. However, some graphs, like bipartite graphs, do not exhibit this triangle inequality type behavior. For rigorous treatment, see Section 3.4 and Ap- pendix A. Next, we build the leClam decoder, that allows decoding any graph, that can model bipartite components without being limited by a triangle inequality-type behavior.
(1)
P(n ~ m)) F) = P(n ~ m fm] = =1 Fi
Due to this formula, BigClam is so called Bernoulli- Poisson model (see Appendix B.4 for more details). The second assumption is that the events of having an edge be- tween different pairs of nodes are independent. As a result, the probability of the entire graph ([N],E) conditioned on the AFs F is
P(EFF)
II [E[N]
P(n ~ m|F) V MEN(())
II
II mEN(())
(
Here, the square root is taken because the product considers each edge twice, and all sums are over m # n.
Our Inclusive Exclusive Cluster Affiliation Model (IeClam) can be extended from BigClam by replacing the inner prod- uct in the non-edge probability (1) by the more expressive Lorentz inner product, which does not enforce a triangle inequality-ty -type behavior. For that, we extend the affiliation space (AS) to be R with two types of communities. The first C' axes are called the inclusive communities, and their corresponding features are called inclusive affiliation fea- tures (IAF), denoted by E RCC The last C axes are called the exclusive communities, with exclusive affiliation features (EAF), denoted by s E RCC We define the concatenated affiliation feature by f = (t, 8) E R²20. Given a sequence of affiliation features = (f,, N
BigClam consists of a decoder, decoding from the AFs F the random graph GF) with node set [N] and independent Bernoulli distributed edges with probabilities P (P(n m/ ml,,,, fm )
From the encoding side, given a simple graph ([N], F),,
BigClam encodes the graph into the affiliation space by maximizing the log likelihood with respect to the AFs F
((F) = Σ Σ NE[N] (EN(m)
log(1 - - -TT - Σ I. fm). (g
E Nx2C IeClam defines
the probability of a single edge by
where all sums are over m # n. BigClam is optimized by gradient descent, with update at iteration i
P(n ~ fm) = =1 -- exp (- t, tm + +s,ssmm)
p(++1= = p(0) + (F(()
(4)
= exp (-f, Lfm),
for some learning rate 8= > 0. In order to implement the above iteration with O [!) operations at each step, instead of O O(N3), the loss can be rearranged as
where L = diag(1, ...1, 11,,, - 1). The bilinear form (u, v) + J Lv is called the Lorentz inner product, and has its roots in special relativity. See Appendix B.9 for more details on the Lorentz inner product.
2F(F)
Σ
Σ
logle
c.
1) - F.T
Σ fm + ||E, 11F,11P) ME(N]
(5)
Note that L is not positive-definite, so it does not actually define an inner product. Moreover, f, Lfm can be negative even if f,, fm E RC. To guarantee that (7) defines a proper probability between and 1, we limit the affiliation space as follows.
ME[N]
(E)
The gradient of the loss is now
Vel1= Σ (1- fm fm
Σ fm + fn- fn-
(6)
(EN(m)
ME[N]
Definition 2.1. A cone of non-negativiry is a subset C of R2C such that every f,g E C satisfy f Lg 2
Since the global term needs to be calculated only once, the number of operations is ElE)) instead of O
If we limit the affiliation space to be a cone of non-negativv then leClam gives well defined edge probabilities in [o, 1]. In our experiments, we restrict ourselves to the following simple construction of a cone of non-negativity, noting that it is not the only possible construction.
We observe that the optimization process a message pass- ing scheme. Looking at the dynamics of the optimization process, we see that every node is pushed in the direction of a weighted average of all of its neighbors, and pushed in the opposite direction to the average of all of the nodes. The sum of both forces tends to drive communities towards the axes in the optimization dynamics.
More generally, one define different number of inclusive and exclusive communities.
3

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Definition 2.2. The pairwise cone T is defined to be the set of affiliation features f (t,s) E R²C such that for every e [C] we have -t- < 0 < 1.
Notice that all of the caleulations are the same BigClam, up to replacing the dot product by the Lorenz inner product. Hence, the optimization process of IeClam is message passing scheme, and equivariant to node re-indexing.
is easy to see that T is cone of non-negativity. Indeed, for any = (t1, S1), fg s2), E TC, we have
2.4. Community Affiliation Models With Prior
Vc E [C]: 1ite s106 2 0,
BigClam and IeClam are not generative graph models. In- deed, these methods only fit a conditional probability of the graph, conditioned on the AF values, but the methods do not learn the probability of the AFs over the affiliation space. Hence, the total probability of E A F is not defined.
so
G Lf2 =
1115
5505 2 0.
As opposed to the BigClam decoder, the IeClam model can approximate a bipartite graph with small number of com- munities. Namely, a bipartite graph with two (disjoint) sides U,V C [M] and constant probability for edges between U and V can be represented using C = 1. Here, all of the nodes in U2 are encoded to (a, a), and all of the nodes of V are encoded to (a. a)), for some a 2 O. This gives zero probability for edges within each part, and probability 1 1-e 22a for edges between the parts.
To extend IeClam (and similarly BigClam) into probabilistic generative models, we define a prior probability distribution over the affiliation cone space C C R²C with probability density function p R + [0, oc) supported on C. Using Bayes law, we now obtain the joint probability P(E A F) of the edges and community affiliation features via the prob- ability density function
pFF. F) = P(F (F).
Remark 2.3. The above construction gives an interpretation for each pair of axes (t", ) in TC as a generalized com- munity which can model anything between clique and a bipartite component.
We assume that the prior probabilities of all nodes are inde- pendent, namely,
Given AFs F in a cone, leClam is seen as a decoder, by de- coding F into the random graph G(F) with node set [N] and
P(F)
II p(.)). NE(N]
independent Bernoulli distributed edges with probabilities P (P m|fn, Mm...
Hence, the probability densities that a dyad (n, m) is an edge or non-edge are
For affiliation features F E TCNN the probability of the graph ([V], F) given F of leClam is
p(n ~ m, fm) p((,))((fmm et Lfm).
F(E
p(-(n- ~ m), f,, fmmm = ((f))((fm)) fr LTm
II RE[N]
V II (1 (1-e (.))
II
f. 1.
(8)
As before, we assume that the probabilities of different edges are independent, which gives
meN(())
Like BigClam, IeClam is optimized by maximizing the log likelihood with gradient descent
P(E, F)
II p(f.)) ME[
II mEX((n)
P(n m/FF..) II P(-(n ~ m)]fn. mgN(())
(F)
(12)
Σ nE[N] (EN(n)
Σ
log(1 - e -fn TI.
Σ
P
Lfn
Now, the log likelihood loss is
(GN(())
(9) This loss can be efficiently implemented on sparse graphs, with O(EEI) complexity, by the formulation
((F) Σ nE M
log(p(f.))+
log(e Lfm -1) -1)- F Σ fm + f (.I....) (EN(())
Σ
log(e Lfm. - 1) - f. Σ fm + f L...)
ME[
(13)
ME[M] (m)
ME[N]
We call this extension of leClam PieClam (Prior Inclusive Exclusive Cluster Affiliation Model). We similarly extend BigClam to PClam (Prior Cluster Affiliation Model) by replacing L in (13) with the identity matrix.
(10)
The gradient of the loss for node n is
Vr, -
Σ fm (1 - e f. LFm 1
-1_
Σ fm + fn
(mN
mE(N]
Observe that the PieClam loss is similar to the IeClam loss, only with the addition of the prior acting as a per node
(11)
4

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
regularization term. The prior attracts all nodes to areas of higher probability during the optimization dynamics. As before, the optimization process of PieClam is message passing scheme with ((E)) complexity, and is equivariant to node re-indexing. Also, note that adding the prior to the Clam model only takes (( complexity, which is lower than the complexity of the leClam terms.
approximated up error by decoding some points in this space. To formalize the "up error c" statement, we present in this section new graph similarity measure which we call the log cut distance. Our construction is based on well-known graph similarity measure called the cut norm.
Definition 3.2. The cut norm of a matrix X E N is defined to be
In order to sample from the above generative models, we first sample features {fn [E[[N] according p. and then con- nect them using either the BigClam or leClam conditional probability. To model the prior in practice, we use realVVP, which a normalizing flow neural network model (Dinh et al., 2016). For more details on normalizing flows, see Appendix B.8.
X X ==
sup u.VC[N]
ΣΣ iEN JEV
Tisl
(14)
No
The metric ||A Blnn between two adjacency matrices A and B is interpreted as the difference between the edge densities of A and B on the block U x V on which their edge densities are the most different.
PieClam for graphs with node features. So far, we have used only the topology of the graph, not considering node features. We extend PieClam (and PClam) to graph-signals ([V), E, X) as follows. Concatenate the feature space of X to the affiliation space, and learn the prior on this com- bined space. This only affects the prior p. The conditional edge probabilities are defined only in terms of the affiliation features, before.
The following graph similarity measure modifies the cut norm, making appropriate for graphs with random edges over a fixed node set.
Definition 3.3. Given two random graphs over the nodes set [N]. with independently Bernoulli distributed edges with probabilities P (Pu.m [m. and Q {fn.m n..mE respectively, their log cul distance is de- fined to be
3. Universality of PieClam and IeClam
Do (=(I)) = inf
c d+
In this section, we define the universality of graph autoen- coders, and prove that leClam and PieClam are universal, while BigClam and PClam are not. The motivation behind the universality definition that we would like to uniformly choose the dimension of the code space, such that every graph can be approximated by decoding some points in this fixed code space. Namely, we would like one universal decoder that works for all graphs, as opposed to choosing the dimension of the code space depending on the graph.
osc,dgi
(15)
sup N [.VC[N]
log
II wel mEV
(1 d) d))m,
(1 e c)pm.
The second term in (15) is the cut distance between the matrix P with entries
-P-QQ
Pn.m = - log(1 1 - (1 - e e)Pm,m)
and the matrix Q with entries
3.1. General Graph Autoencoders
Next, we define general decoder that defines edge proba- bilities by operating on pairs of points in a code space. Definition 3.1. A pairwaise decoder over the code spaces RM is a mapping Das : 22M + [0, 1]. Given points in the code space = {zn E TRM )= the decoded graph Gz(z) is the weighted graph with adjacency matrix
In,m log(1 - d)),))m.m).
Namely, the cut distance between the log likelihoods of non-edges. The parameters e and d make the [o, 1]-valued probabilities valid inputs the log. The goal of e, d is to regularize the probability of the edges, where higher regularization is penalized via the additive term + d.
(z) = (Das(en: 2x)) N m
For each choice of a cut 2, V C [N]. the term
1- (1 e)Pr.m log (II nEW mEV
Clam models are special cases of pairwise decoders.
(16)
N
1 1- d)
3.2. Log Cut Distance
is somewhat similar in structure to an un-normalized KL divergence, or distance of log likelihoods, between the non- edge probabilies of the graphs P and Q over the dyads between 24 and V. Here, "un-nnormaizedd" means that the
Our definition of universality has the following form: for every error tolerance e > O, there a choice of the dimen- sion (c) of the code space such that every graph can be
5

---

PicClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
dyads are drawn uniformly with probabilities 1/N2, but the sum of probabilities is [4]- [VI/N2 and not 1. The un- normalized uniform distribution discourages the supremum inside the definition of Dn from choosing small blocks for maximizing (16). Note that normalized uniform dis- tributions would lead Do to choose small blocks, which do not reflect meaningful empirical estimates of the edge statisties (the edge densities of small blocks would not be interpretable expected number of edges). To conclude, (P(P]|Q Q) is interpreted as the maximal divergence be- tween P and Q over all blocks, up to the best regularizers.
bipartite graphs. Consider the bipartite graph B with N nodes at each part, and probability 1 - e- for an edge between the two parts, and within each part. Since in this case all probabilities are less than 1, we can use (17) the definition of the log cut distance. The analysis for Definition 3.4 extends naturally.
Let P be a decoded BigClam graph. We show that there is no way to make D [P] Q) small by choosing the dimen- sion C uniformly with respect to N. fact, we will show BigClam cannot approximate a bipartite graph at all. Claim 3.6. Under the above construction,
In our analysis we compute the log cut distance between the random decoded graph P and the deterministic target graph A. While A has edge probabilities in {0, 1], P has edge probabilities in [0, 1) for Clam models. Therefore, we only require regularization for A. We hence consider the following modified version of Definition 3.3.
a²
P
B
2
16
As a result, BigClam is not a universal autoencoder.
The proof is given in Appendix A.I. We note that one can similarly show that BigClam is not universal also with respect to the log cut distance of Definition 3.4.
Definition 3.4. Given an unweighted graph with adjacency matrix A E {0, 1 1)NNNN and a random graph over the nodes set [A], with independently Bernoulli distributed edges with probabilities P = {0 S Pn.m < [ the log cut distance between P and A is defined be
3.5. Universality of IeClam and PieClam
(P(IIAA)
We are now ready to show that IeClam (and hence also PieClam) is a universal autoencoder. The proofs of the following two theorems are in Appendix A.3 and A.4.
inf d 0541g1
sup N2 U.V[[N]
log III II nEM mEV
1 - Pm.m
(1 d)a.,
We give two versions for the universality result. The first is without cone restriction, and requires relatively small number of communities for the given error tolerance. The corresponding decoder produces edge weights that can be negative. The second theorem is restricted to the pairwise cone of non-negativity, and has pessimistic asymptotics for the required number of communities given an error tolerance. The second decoder is guaranteed to produce proper edge probabilities in [0, 1).
Lastly, in case both P and Q are [0, 1) 1)-valeed, simple version of the log cut distance is (15) with the choice = d = 0, namely,
(PIIQ)
1 sup U.CC(
log II II
Pr.m
(17)
N2
1 In.m
nEW mEV
3.3. Universal Graph Autoencoders
Theorem 3.7. For every epsilon e > 0, every N E N, and every adjacency matrix A E [0, [0,1]NxN, there are N affilia- tion features F E <R2K of dimension K = -9 -9oooee//) /e2 such that the corresponding leClam model = (P(n m mlfn, fm) y ) m,==1 satisfies D= (P]]AA) < 6. Here, the log cut distance is from Definition 3.4. As a result, IeClam and PieClam are universal autoencoders with code space 2
We are now ready to define the universality of general pair- wise autoencoders. Motivated by the fact that a Clam autoen- coder is actually family of autoencoders, parameterized by the number of communities, we also define general pairwise decoders as families.
Definition 3.5. A family of code spaces R and cor- responding pairwaise decoders DM 22M + [0, 1], parametrized by M E N, is called universal if for every > 0 there is M E N (which depends only on e) such that for every N E N and every graph with adjacency ma- trix A and N nodes there are N points in the code space {zn E MY In=1 such that D (D (2) A) <.
Theorem 3.8. For every epsilon é >> O, every N E N, and every adjacency matrix A E [0, 1] N there are N affilia- tion features F in the cone of pairwise non-negativity TO C R2C of dimension C = 2 log(s/ /e²) such that the cor- responding leClam model P = (P(n ~ m) satisfies (p|P| < Here, the log cut distance is from Definition 3.4. As a result, leClam and PieClam are univer- sal autoencoders with code space TC.
ml, fm) HN fim==
3.4. Big and PClam are Not Universal
II Appendix A.2 we show that one can approximate bipartite graph of 2NN nodes using C = N2 classes in BigClam if the model ignores self-loops.
We now show that BigClam (and hence also PClam) is not universal autoencoder since it cannot approximate
6

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
3.6. Log cut distance and maximum likelihood
connection probability of 0.5. We sample simple graph with N 210 nodes from the SBM, and fit PClam and PieClam to is. The SBM is off diagonal, so it cannot be well approximated by the PClam model, while the PieClam model approximates well qualitatively. Additional details are given in Appendix D.
It well known that it is NP hard compute cut distance (Alon & Naor, 2006; Rohn, 2000), and hence also log cut distance. Instead, we observe that maximizing log likeli- hood, which is efficiently implemented with gradient ascent, leads to a small log cut distance in practice, See Figure 1.
Abs. Log Likelihood logeuh, dir0.0t
8:0-
64
56
14
39
70
8:4
339
Figure Left to right: Original SBM with 3 classes and blocks; Adjacency matrix of the fitted PieClam graph, with two inclusive and two exclusive communities; Adjaceney matrix of the fitted PClam graph, with four communities.
Beracion No.
Figure 1: The value of log cut the abosolute value of log likelihood along the optimization of IeClam on Squir- rel. When log likelihood is optimized, log cut distance decreases.
4.3. Anomaly Detection
In unsupervised node anomaly detection, one is given a graph with node features, where some of the nodes are unknown anomalies. The goal to detect these anomalous nodes, without supervising on any example of normal or anomalous nodes, using only the structure of the graph and the node features.
4. Experiments
All of the experiments were run on Nvidia GeForce RTX 4090 and Nvidia L40 GPUs.
4.1. Reconstructing Synthetic Priors
We fit a Clam model to the graph and flag nodes as anoma- lous if they satisfy the following different criteria.
We consider ground-truth synthetic prior p. We sample N = 500 points from p. decode the corresponding PieClam graph, and sample simple graph from the random Bernoulli edges. Then, using the sampled graph as the target for the PieClam optimization, we fit PieClam on T The results are shown in Figure 2. We observe that the algorithm re- constructs both the positions of the nodes in the affiliation space and the original prior qualitatively well. Additional Experiments and results are given in Appendix D.4.
(S) Star probability: Given any Clam model, node is called anomalous if [mmme(m) P(n m m(F) < 8.
(P) Prior probability: Given any Clam model with prior, a node n is called anomalous if p(f,)
(PS) Prior star probability: Given any Clam model with prior, node is called anomalous if p(f,) Imm P(n ~ m|F) < 8.
Lo-
420
We reduce the dimension of the node features of the input graphs to 100 using truncated SVD, unless the dimension of the features is smaller than 100 in which case we only normalize them to have zero mean and standard deviation one. We use an affiliation space embedding dimension of 30 for for PieClam and leClam, and 24 for BigClam. Every Clam method starts with a random embedding F. Clam models with prior are trained with the following steps. (F- t): given fixed prior p. optimize only F for steps. (p-t): given fixed embedding F, optimize only p for steps. For regularization, when training, in each iteration of we add Gaussian noise with STD 0,05 to the affiliation features before plugging them into the prior. We train PieClam with the scheme F-500 - p-100 + F-500 + p- p-1300 - F-500 -> p- 1300 with learning rate 2e 26-6 on and 1e-6 6 on p. In
sa-
-10
Figure 2: Left to right: Ground truth synthetic prior in Th: Graph sampled from the prior; Reconstructed prior via PieClam; Reconstructed nodes via PieClam.
4.2. Reconstructing Synthetic SBMs
In Figure 3 consider synthetic SBM with intercom- munity connection probability of 0 and intracommunity
Our code can be found in: https://github... danizi1/PieClan
7

---

PicClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Method
Reddit
Elliptic
Photo
be efficiently computed by
(S)- leClam
64.1
43.6
57.7
(S) PieClam
*64.0
43.5
59.0
21(F, F, =2
Σ log(p(f,)))
+
Σ
log(1 - e - Lfm)
(P) PieClam
46.8
63.2
45.7
(PS)- PieClam
64.0
53.8
59.0
NE[N]
-iggClm
63.7
43.4
#58.1
ΣE E
Lf
+
Σ
Lf
AnomalyDAB
DOMINANT
50.9
51.1
+49.6
29.6
51.4
50.7
ME[N]
MEIN]
(N.m)EEUEUD
OCGNN
52.5
25.8
53.1
where E is the set of edges, E is the set of omitted edges, E is the set of omitted non-edges, & = EUE is the set of omit- ted dyads, and = {(n, n) E [N]]. This computation is as efficient as message passing when the number of omitted non-edges is of the same order as F.. After assigning prob- abilities to all of the omitted dyads, we calculate the AUC score of the classification. We use the experimental setting presented in (Zhou et al., 2022).
AEGIS
53.5
45.5
55.2
GAAN
52.2
25.9
43.0
TAM
60.6
40.4
56.8
Table 1: Comparison of Clam anomaly detectors with competing methods. First place in boldface, second with underline, third with *ttar. The accuracy metric is areas under curve (AUC).
For each dataset, we generate 10 random splits into a test set containing 10% of the edges, along with 5 randomly sampled non-edges for every omitted edge, and the rest the training set. For each split and each configuration of the hyperparameters, we generate three random validation sets consisting of 5% of the edges from the training set and 5 non- edges per omitted edge also from the training set, leaving the rest of the original training set for training. We perform hyperparameter optimization as follows: Fach hyperparam- eter configuration is trained against each of its respective 30 training sets, and its accuracy is evaluated over the corre- sponding 30 validation sets and averaged to obtain one mean validation accuracy per configuration. We then choose the configuration with maximal mean validation accuracy. The model with these optimal hyperparameters is then trained on each of the original 10 training sets and tested on each of the corresponding test sets, 10 times for each split. We report the mean accuracy across the 100 trained models on the 10 test sets, along with the standard deviation of the mean. We run our experiments on the datasets Squirrel and Texas (Pei et al., 2020). Photo (Shchur et al., 201 2018b) and Facebook I 00's Johns Hopkins (Lim et al., 2021b), and com- pare PieClam to the basclines AA (Adamic & Adar, 2003), VGAE (Kipf & Welling, 2016). GAT (Velickovic al., 2017), LINKX (Lim et al., 2021a) and Disenlink (Zhou et al., 2022). The results are presented in Table 2 (and with error bars in Table 6), and the baseline results are taken from Table 2 in (Zhou et al., 2022). An in depth explanation on the experimental setup and a table with confidence intervals is given in Appendix D.3.
every alternation between two (p-t) t) and (F t) schemes, both learning rates are decreased by factor of 2. For the models which only optimize F (leClam and BigClam) we use the following configurations. We train leClam with 2500 iterations with learning rate 1e-6. We train BigClam with 2200 iterations with learning rate 1e-6. More details on syper-parameters are given in Appendix D.2, and in our GitHub repository.
In Table 1 we compare the performance of Clam methods to DOMINANT (Ding et al., 2019a), AnomalyDAE (Fan et al., 2020), OCGNN (Wang et al., 2021), AEGIS (Ding et al., 2021), GAAN (Chen et al., 2020b) and TAM (Qiao & Pang, 2024) on the datasets Reddit, Elliptic (Elliptic) (Weher et al., 2019), and Photo (Shchur al., 2018a). The hyper-parameters of the competing methods are taken as the recommended values from the respective papers. The results are taken from Table in (Qiao et al., 2024). We observe that our methods are the first and second place on all datasets. Moreover, (PS)- PieClam beats the competing methods in all three datasets.
4.4. Link Prediction
In supervised link prediction, one is given a graph where for some of the dyads it is unknown if they are edges or not. The goal predict the connectivity of the omitted dyads. Given a Clam model fitted to the known data, we predict the probability of an edge using the conditional probability given in (7). In our experiments, the prior and features are not directly used for prediction, but they are used to train the Clam model if it has a prior. In Appendix D.3 we show that the log likelihood, restricted to the known dyads, can
We conducted additional link prediction experiments on the OGB-DDI dataset. In this dataset, nodes represent differ- ent drugs, and edge between two nodes indicates that different effect occurs when the drugs are taken together versus separately. Our model achieves state-of-the-art per- formance on this benchmark in terms of the Hits @ 20 metric (using OGB's 's official evaluator). A comparison between our model (TeClam) and selected baselines on the dataset's
8

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Method
Squirrel
Photo
Texas
JHS5
measure sparse graphs. This can be done, e.g., similarly to the sparse theory in (Finkelshtein et al., 2024), us- ing stretched graphons (Borgs et al., 2018), L graphons (Borgs et al., 2014), graphings (Lovász, 2012) graphops (Backhausz. & Szegedy, 2018).
PieClam
98.7
98.4
85.0
95.5*
BigClam
98.5
97.4 *
78.2 *
94.9
VGAE
98.2
94.9
68.6
92.8
GAT
98.0
97.3
68.5
94.3
LINKX
98.1
97.0
75.8
93.4
AA
97.1
97.4
53.1
96.1
DisenLink
98.3*
97.9
81.0
97.5
Impact Statement
Table Comparison of Clam link predictors with compet- ing models. First place in boldface, second with underline, third with *star
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Model
Hits@ 20 (Test)
AUC (Test)
IeClam
88.10 1.70
99.84
Acknowledgments
NCN
76.32 + 10.47
99.97 0.00
GraphSAGE
4 15.56
+
99.96 + 0.00
GCN
49.90 7.23
99.86 + 0.03
This research was supported by grant from the United States-Isracl Binational Science Foundation (BSF), Jerusalem, Israel, and the United States National Science Foundation (NSF), (NSF-BSF, grant No. 2024660), and by the Israel Science Foundation (ISF grant No. 1937/23).
BUDDY
29.60 1 4.75
99.81 1 0.02
Node2Vec
34.69 2.90
99.78 0.04
Table Performance on the OGB-DDI dataset. First place in boldface.
References
test set is presented in Table 3. Benchmark results are taken from (Zhang et al., 2022; Li al., 2023; Tan et al., 2022).
Adamic, L. A. and Adar, E. Friends and neighbors on the web. In Social Networks, volume 25, pp. 211-230. Elsevier, 2003.
5. Conclusion
Aicher, C., Jacobs, A. Z., and Clauset, Learning latent block structure in weighted networks. Journal of Complex Networks, (12):221-245) 2015.
We introduced PieClam, new probabilistic graph gener- ative model. PieClam models graphs via embedding the nodes into an inclusive and exclusive communities space, learning a prior distribution in this space, and decoding pairs of points in this space to edge probabilities, such that points more likely be connected the more inclusive communities and the less exclusive communities they share. We showed that PieClam is universal autoencoder, able to approximate any graph, where the budget of parameters per node (the number of communities) can be predefined, irrespective of any property of a specific graph, not even the number of nodes. Our experiments show that PieClam achieves competitive results when used in graph anomaly detection.
Airoldi, E. M., Blei, D., Fienberg, S., and Xing, E. Mixed membership stochastic blockmodels. Advances in neural information processing systems, 21, 2008
Alon, N. and Naor, A. Approximating the cut-norm via grothendieck's 's inequality. SIAM, 2006.
Backhausz, Á. and Szegedy, B. Action convergence of operators and graphs. Canadian Journal of Mathematics, 74:72 - 121, 2018.
Bojchevski, A., Shehur, O., Züigner, D., and Günnemann, S. Netgan: Generating graphs via random walks. In Proceedings of the 35th International Conference on Ma- chine Learning (ICML), pp. 610-619. PMLR, 2018.
One limitation of PieClam is that, for attributed graphs, it only models the node features through the prior in the community affiliation space, but not via the conditional probabilities of the edges (given the community affiliations). Future work will deal with extending PieClam also in- clude the node (or edge) features in the edge conditional probabilities. Another limitation is in the analysis. While our methods performs well for sparse graphs, our analy- sis involving the log cut distance is mainly appropriate for dense graphs. Indeed, the term 1/N2 in (16) leads all sparse graphs with E < 2 to be trivially close to each other. Future work will extend our log cut similarity
Borgs, C., Chayes, T., Lovász, L. M., Sós, T., and Vesztergombi, K. Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing. Advances in Mathematics, 219: 219:1800 1801-1811, 2007.
Borgs, C., Chayes, J. T., Cohn, H., and Zhao, Y. An lp theory of sparse graph convergence i: Limits, sparse random graph models, and power law distributions. Transactions of the American Mathematical Society, 2014.

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Borgs, C., Chayes, J. T., Cohn, H., and Holden, N. Sparse exchangeable graphs and their limits via graphon pro- cesses. Journal of Machine Learning Research, 18(210); 1-71, 2018.
Finkelshtein, B., Ismail īikan Ceylan, Bronstein, M., and Levie, R. Learning on large graphs using intersecting communities, 2024.
Fortunato, S. and Hric, D. Community detection net- works: A user guide. Physics reports, 659:1-44, 2016.
Cavallari, S., Zheng, V. W., Cai, H., Chang, K. C.-C., and Cambria, E. Learning community embedding with com- munity detection and node embedding graphs. In Proceedings of the 2017 ACM on Conference on Informa- lion and Knowledge Management, pp. 377-386, 2017.
Frieze, A. M. and Kannan, R. Quick approximation to matrices and applications. Combinatorica, 1999.
Gilmer, J., Schoenholz, S. S., Riley, F., Vinyals, O., and
Chen, F., Wang, Y-C.,, Wang, B., and Kuo, C.-C. Graph representation learning: survey. APSIPA Transactions on Signal and Information Processing, 9, 05 2020a.
Dahl, G. E. Neural message passing for quantum chem- istry. Proceedings of the 34th International Confer- ence on Machine Learning Volume 70, ICML'17, pp. 1263 1272. JMLR.org. 2017a
Chen, Z., Liu, B., Wang, M., Dai, P., Lv, J., and Bo, L.. Generative adversarial attributed network anomaly de- tection. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 1999-1992, 2020b.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017b.
De Cao, N. and Kipf, T. Molgan: An implicit genera- tive model for small molecular graphs. arXiv preprint arXiv: 1805. 1973, 2018
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial nets. Advances in neural informa- tion processing systems, 27, 2014.
Ding, K., Li, J., Bhanushali, R., and Liu, H. Deep anomaly detection on attributed networks. In Proceedings of the 2019 SIAM international conference on data mining, pp- 594-602. SIAM, 2019a.
Greub, W. Linear Algebra. Springer-Verlag, New York, 2nd edition, 1963. Pseudo-Euclidean Spaces.
Grover, A., Zweig, A., and Ermon, S. Graphite: Iterative generative modeling of graphs. In International confer- ence on machine learning, pp. 2434-2444, PMLR, 2019.
Ding, K., Li, J., Agarwal, N., and Liu, H. Inductive anomaly detection on attributed networks. In Proceedings of the twenty-ninth international conference international joint conferences artificial intelligence, pp. 1288 1294, 2021.
Guo, X. and Zhao, L. A systematic survey on deep genera- tive models for graph generation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(5):5370- 5390, 2022.
Ding, M., Yao, Q., Zhang. Q., Cui, P., Zhu, W., and Shen, J. Data augmentation for deep graph learning: survey. arXiv preprint arXiv:1909.00 0909.07251, 2019b.
Hamilton, W. L., Ying, R., and Leskovec, J. Representation learning graphs: Methods and applications. arXiv preprint arXiv: 1709.05584 2017.
Dinh, L., Sohl-Dickstein, J., and Bengio, S. Density esti- mation using real nvp. arXiv preprint arXiv: 08883,, 2016.
Harshvardhan, G., Gourisaria, M. K., Pandey, M., and Rautaray, S. S. A comprehensive survey and analysis of generative models in machine learning. Computer Science Review, 38:100285, 2020.
Duvenaud, D. K., Maclaurin, D., Iparraguirre, J., Bom- barell, R., Hirzel, T., Aspuru-Guzik, A., and Adams, R. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Holland, P. W., Laskey, K. B., and Leinhardt, S. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
Elliptic. Elliptic. cessed: 2025-05-19.
Ac-
Ingraham. J., Garg, V., Barzilay, R., and Jaakkola, T. Gener- ative models for graph-based protein design. Advances in neural information processing systems, 32, 2019.
Fan, H., Zhang, F., and Li, 7. Anomalydae: Dual autoen- coder for anomaly detection on attributed networks. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp- 5685-5689. IEEF, 2020.
Jiang, J. Q. Stochastic block model and exploratory amalysis in signed networks. Physical Review E, (1(6))062285, 2015.
10

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Kingma, D. Auto-encoding variational bayes. arXiv preprint arXiv: 13/6.1 2013.
Transactions on Knowledge and Data Engineering, 35 (12):1012--22338 2021.
Kipf, T. N. and Welling, M. Variational graph auto-encoders.
Madhawa, K., Ishiguro, K., Nakago, K., and Abe, M. Graph- nyp: An invertible flow model for generating molecular graphs. arXiv preprint wrXiv:190..16600 2019.
arXiv preprint arXiv: 1.77000,, 2016.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In 5th Interna- tional Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Mehta, N., Duke, L. C., and Rai, P. Stochastic blockmodels meet graph neural networks. In International Conference on Machine Learning, pp. 4466 4474. PMLR, 2019.
Miller, K., Jordan, M., and Griffiths, T. Nonparametric latent feature models for link prediction. In Bengio, Y., Schuurmans, D., Lafferty, J., Williams, C., and Culotta, A. (eds.), Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
Kumar, A., Singh, S. S., Singh, K., and Biswas, B. Link prediction techniques, applications, and performance: A survey. Physica A: Statistical Mechanics and its Applica- tions, 553:12 2020.
Latouche, P., Birmelé, E., and Ambroise, C. Variational bayesian inference and complexity control for stochastic 2012. Lee, C. and Wilkinson, D. A review of stochastic block models and extensions for graph clustering. Applied Network Science, 4(1):1-50, 2019.
Mohamed, S. and Lakshminarayanan, B. Learn- ing in implicit generative models. arXiv preprint arXiv: TrXiv:1610.0348: 2016.
block models. Statistical Modelling,
Mørup, M., Schmidt, M. N., and Hansen, L. K. Infinite multiple membership relational modeling for complex networks. In 2011 IEEE International Workshop on Ma- chine Learning for Signal Processing, pp. 1-6. IEEE, 2011.
Levie, R. A hightnn-signal analysis graph neural net- works. Thirty-seventh Conference on Neural Informa- tion Processing Systems, 2023.
Newman, M. E. The structure and function of complex networks. SIAM Review, 45(2):167-256, 2003.
Li, J., Shomer, H., Mao, H., Zeng, S., Ma, Y., Shah, N., Tang, J., and Yin, D. Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Nowicki, K. and Snijders, A. Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association, 964455):0777-088,, 2001a.
Lim, D., Hohne, F., Zitnik, M., Leskovec, J., and De Sa, C. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In Advances in Neural Information Processing Systems, 202
Nowicki, and Snijders, T. A. B. Estimation and prediction for stochastic blockstructures. Journal of the American statistical association, 96(455):1077-1088 2001b.
Lim, Li, X., Hohne, F., and Lim, S.-N. New benchmarks for learning on non-homophilous graphs. arXiv preprint arXiv:2104. 01 2021b.
Palla, K., Knowles, D. A., and Ghahramani. Z. An infinite latent attribute model for network data. In Proceedings of the 29th International Coference International Confer- ence on Machine Learning. ICML' 12, pp. 395-402 Madi- son, WI, USA, 2012. Omnipress. ISBN 978145031285
Liu, J., Kumar, A., Ba, J., Kiros, J., and Swersky, Graph normalizing flows. Advances in Neural Information Pro- cessing Systems, 32, 2019.
Pang, G., Shen, C., Cao, L., and Hengel, A. V. D. Deep learning for anomaly detection: A review. ACM comput- ing surveys (CSUR), 54(2):1-38, 2021.
Lovász, L. M. Large networks and graph limits. volume 60 of Colloquium Publications, 2012. doi: doi:10. 1090/ coll/060.
Pearl, J. Reverend bayes on inference engines: A distributed hierarchical approach. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 133-136. AAAI Press, 1982.
Lovász, L. M. and Szegedy, B. Szemerédi's lemma for the analyst. GAFA Geometric And Functional Analysis, 2007.
Ma, X., WU, J., Xue, S., Yang, J.. Zhou, C., Sheng, Q. Z., Xiong, H., and Akoglu, L. A comprehensive survey on graph anomaly detection with deep learning. IEEE
Pei, H., Wei, B., Chang. K. C.-C,, Lei, Y., and Yang, B. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv2200.005887, 2020.

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Peterson, W. W., Birdsall, T. G., and Fox, W. C. The the- ory of signal detectability. Transactions of the IRE Pro- fessional Group Information Theory, 4(4):171-212, 1954.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y., et al. Graph attention networks. stat, 1050 (20):10-4855,, 2017.
Wang. H., Wang. J., Wang. J., Zhao, M., Zhang, W., Zhang, F., Xie, X., and Guo, M. Graphgan: Graph representation learning with generative adversarial nets. In Proceed- ings of the AAAI conference artificial intelligence, volume 32, 2018.
Qiao, H. and Pang. G. Truncated affinity maximization: One-class homophily modeling for graph anomaly detec- tion. Advances in Neural Information Processing Systems, 36, 2024.
Wang, X., Jin, B., Du, Y., Cui, P., Tan, Y., and Yang, Y. One- class graph neural networks for anomaly detection in attributed networks. Neural computing and applications, 33:1 33:12073-12085 2021.
Qiao, H., Wen, Q., Li, X., Lim, E.-P., and Pang. G. Gen- erative semi-supervised graph anomaly detection. arXiv preprint arXiv:2402.1/889 2024.
Radford, A. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511. 1.06444, 2015.
Weber, M., Domeniconi, G., Chen, J., Weidele, D. K. I., Bellei, C., Robinson, T., and Leiserson, C. E. Anti-money laundering in bitcoin: Experimenting with graph convolu- tional networks for financial forensics. In KDD Workshop on Anomaly Detection in Finance, Anchorage, AK, USA, August 2019.
Rohn, J. Computing the norm ||aloo,,1 is np-hard. Linear and Multilinear Algebra, 2000.
Samanta, B., De, A., Jana, G., GÂ*mez, V., Chattaraj, P., Ganguly, N., and Rodriz-o,,,,, M. Nevac: A deep generative model for molecular graphs. Journal of Ma- chine Learning Research, (1114):1-33 2020.
Yang. J. and Leskovec, J. Structure and overlaps of commu- nities in networks. In SNAKDD, 2012.
Yang. J. and Leskovee, Overlapping community detection at scale: a nonnegative matrix factorization approach. In Proceedings of the sixth ACM international conference Web search and data mining, pp. 587-596, 2013.
Shchur, O. and Günnemann, S. Overlapping community detection with graph neural networks. arXiv preprint arXiv: 12201, 2019.
Yang. J. and Leskovec, J. Structure and overlaps of ground- truth communities in networks. ACM Transactions on Intelligent Systems and Technology (T7ST), 5(2):1-35, 2014.
Shchur, O., Mumme, M., Bojehevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 0008688, 2018a.
Shchur, O.,. Mumme, M.. Bojehevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. arXiv 2018b.
You, J., Ying, R., Ren, X., Hamilton, W., and Leskovee, J. Graphrnn: Generating realistic graphs with deep auto- regressive models. In International conference on chine learning, pp. 5708-5717, PMLR, 2018.
preprint 181
Snijders, T. and Nowicki, K. Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of Classification, 14(1):75-100, 1997.
Zhang, R., Zhang, Y., Lu, C., and Li, X. Unsupervised graph embedding via adaptive graph learning. IEEE Transac- tions Puttern Analysis and Machine Intelligence, 2022. doi: 10.1109/TAAM.22222222222
Sun, F--.,, Qu, M., Hoffmann, J., Huang, C.-W., and Tang. J. vgraph: A generative model for joint community de- tection and node representation learning. Advances in Neural Information Processing Systems, 32, 2019.
Zhou, M. Infinite edge partition models for overlapping community detection and link prediction. Proceedings of the 18th International Conference on Artificial Intelli- gence and Statistics (AISTATS), pp. 1135-1143, 2015.
Tan, Q., Liu, N., Huang, X., Chen, R., Choi, S., and Hu, X. Mgae: Masked autoencoders for self-supervised learning on graphs. In Proceedings of the 28th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 2096-2106 ACM, 2022.
Zhou, S., Guo, Z., Aggarwal, C., Zhang, X., and Wang, Link prediction on heterophilic graphs via disentangled representation learning, arXiv preprint arXiv:2208 01820. 2022.
Tschannen, M., Bachem, O., and Lucic, M. Recent advances in autoencoder-basse representation learning. arXiv preprint arXiv: /8/2.000// 2018.
12

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Supplementary Material
A. Proofs
A.1. Proof That BigClam Is Not Universal
In this subsection Prove Claim 3.6. Consider the bipartite graph B with N nodes each part, and probability e ema² for edge between the two parts, and 0 within each part. Consider (17) the definition of the log cut distance. Let P be decoded BigClam graph from the affiliation features F.
Denote by P the matrix with entries
Pn.m = log(1 - Pn,m) = f, fm
and by B the matrix with entries 6m.m - log(1 bn,m). We show that there is no way make ||P-Qlla small.
Claim A.1. Under the above construction,
a²
D (P
BB
16
As result, BigClam is not a universal autoencoder.
Proof. Note that bn.m a n, m are in opposite parts, and bn.m if n, m are on the same side. We index the nodes such that [N] is the first side of the graph, and [N] N is the second side. For E [N] denote q, = fa and yn futN- Next, we use the identity
D (P -IP Bl|a,
and bound the right-hand hind-side from below.
First, by the definition of cut norm, for every U, C [2N].
PP Bl| >
(in. kmmm
4N2
nEUl MEV
Hence, fo Vi = [N], U2 1/2 =
+ + = [N], V/3 [N] + N, and = [N] + N, 14
[N], we have
p - Bl|b
Σ (Pn.
bu
16N2
nEl, nEV,
N
N
N Σ
T 4m
y Ym
16N
16N2
n= m=1
n=1 m=1
N
(a qn
vm).
(18)
8N
Denote
N
N Σ
=
qu:
=
yn-
N
N
n=1
==1
With these notations, (18) can be written as
||
BI|D 2
1
1
1 (a² - q (y)
9
q+
y
y y +
16
16
1
a2 + (q y T) - -y)) > a²
16
We note that one can similarly show that BigClam is not universal also with respect the log cut distance Definition 3.4.
13

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communitics
A.2. BigClam With No Self Loops Approximating Bipartite Graphs
Consider the above bipartite graph B with N nodes at each part, and probability 1- e for an edge between the two parts, and 0 within each part. If we redefine the BigClam decoder to have self-loops, namely, P has entries Pn.m P(n m m fm) for # m, and Pm,m 0 for m, then can obtain bipartite P with C' N2 communities as follows.
In the following analysis, an addition or multiplication of a set by a scalar is defined to be the addition or multiplication of every element in the set by this scalar. Encode each node n E [N] in part to f, with fü = a for c [N] + n(N 1) and
f = 0 otherwise. Encode every node n E [M] + N from side 2 to f, with f = a for E [[[N] 1) + n and fü
otherwise. It is easy to see that the corresponding P is bipartite with edge probability between the parts being 1 - e
A.3. Proof of the Universality of PieClam
The proof is based on version of the weak regularity lemma for intersecting communities. While the standard weak regularity lemma (Frieze & Kannan, 1999; Lovász & Szegedy, 2007) partitions the graph into disjoint communities, it is well known that allowing the communities to overlap allows using much less communities, which improves the asymptotics of the approximation. The regularity lemma was used in the context of graph machine learning in (Levie, 2023; Finkelshtein al., 2024). To formalize the relevant version of the weak regularity theorem for our analysis, we first need to cite definition from (Finkelshtein al., 2024).
Definition A.2. A (hard) intersecting community graph (ICG) with N nodes and K communities is matrix C RN of the following form. There exist K column vectors Q (qi- {0, () E {0, xx and k coefficients r = (T& B k=1 E R K such that
C = Qdiaa(r)QQ..
The following is special case of the weak regularity lemma from (Finkelshtein et al., 2024), up to the small modification the adjacency matrix, allowing it to have values in [0, R] instead of [0, 1].
Theorem A.3. Let A E [0, R] NxN be an adjacency matrix of a graph with nodes. Let E > 0. Denote K there exists hard ICG C with K communities such that
9 Then, 4
A Clla S.
(19)
Proof of Theorem 3.7. Let > 0. Let A NxNN be adjacency matrix. Let 0 < d
Consider the matrix À with entries
Un.m = log(1 - (1 - d))...m)
In the following construction, build leClam affiliation features F and want
1 - exp(pppppp Lfm) x0 (1 d)an.m.
Note that - log(1 (1 dd),n.m) ) is increasing in (1 d) dm For (1 - d)an, 0 the value of this function 0, and d it R = log(d) (d). Choose d = c/2. For this specific choice of d, we replace d by c/2 in the definition of Du and omit the infimum, we get an upper bound of (P, A).
for d)an,,
Using the overlaping weak regularity lemma, approximate À by an ICG with
K 9 lolo(e/2)
communities,
C = Qdiag(r)
such that
A Clnn c//2.
Let r4 = (r) r_
r- = ReLU Denote
C+ = Qdiag( /r+)
14

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
and
C_ (oliag(vr-)
Denote the rows of C., by t, and the rows of C_ by Sn, .,..,, N. For each [N] we concatenate (Un,8n) to define the affiliation feature f,, with the first K coordinates being the inclusive communities, and the last K coordinates being the exclusive communities. Denote the corresponding IeClam matrix by P.
is easy to see that f, Lfm is the (n, m) entry of Qdiag(r) Q"_ This also proves that
log(1 - (1 - é) A) + log(1 P)]E
| - ClIo S e/2.
We can now summarize
Do(PIIA) &
6/2 + N2 u.v.IN]
1 sup
log II
II
1 - Pm.m
1 (1 e/22)
nEW MEV
= +
N2
1
sup U.V.[N]
Σ BELL mEV
log (1 - (1 - c))mmm)
+ +log (1 Pnmm))
= =//2+ |P P
A.4. Proof of the Universality of IeClam in the Pairwise Cone of Non-negativity
For this result, we use the standard weak regularity lemma for non-intersecting classes. is based on the weak regularity lemma from (Fricze & Kannan, 1999; Lovász & Szegedy, 2007), see also Lemma 9.3 and Corollary 9.13 from (Lovász, 2012).
Definition A.4. A block matrix B with K classes is a symmetric matrix B E [0, Nx) for which there exists a partition of [N] into K disjoint sets, called classes, CI,...,Co Cx (with UC, [N], such that for every pair of classes i, E [K], there a constant Ct 2 such that 6n,m = c. for any two nodes n E C, and E Cj.
Theorem A.S. Let A E [0, NxN be adjacency matrix of graph with N nodes. Let e > O. Denote K = 22 /2 Then, there exists block matrix B with K (disjoint) classes such that
A -B/o S c.
(20)
We stress that Theorem A.5 guarantees non-negative block values of B, while in Theorem A.3, in general, the matrix C may have negative entries.
Proof of Theorem 3.8. We start similarly to the proof of Theorem 3.7. Let e 0. Let A E [0, NxN be an adjacency matrix. Consider the matrix A E [0, - log(e/2) with entries
an.m
log(1 (1- (1-e/2)an,m)
In the following, build leClam affiliation features F such that
Lf, (1 e/2))nm...
By the weak regularity lemma (Theorem A.5), we approximate there is non-negative block matrix with K 2o/= classes Ci,..., Ck, such that
A --Bllo S..
15

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
We now take the affiliation space to have C' K2 inclusive communities and C K²2 exclusive communities.
For each E [V], let kin be the class such that E C.u. For each pair of classes i, E [K], let Ci 2 0 denote the edge weight between C₁ and Cj. The feature of each
[AV] at the inclusive channel (K- 1) + kn is E = VCk,, It t, VC at inclusive channels c (K - 1) + j and = (K 1)j + knn and s = V J / at exclusive channels c = (K - -1)k, + J and
c= KK- 1)j + hn- In all other channels e and s, are zero. Note that f, belongs the cone of pairwise non-negativity T C _22K*
is now direct to see that f Lfm = Ck Am As a result, as in the proof of Theorem 3.7, we get
(E(PIAA) S
sup c/2+ + N u.V[(N]
1
log II II
1 Pn.m
1 - (1 c/2)an. nn
neu MEV
=e/2 N2 u.V.[N]
1
sup
ΣΣ nEU MEV
log (1 -e)an.
+log -1-Ppra Pnmm)))
= e/2 + P B =
B. Extended Related Work
B.1. Message Passing Algorithms and Networks
The message passing algorithm is general architecture for processing graph-signals. An MPNN operates on the graph data by aggregating the features the neighborhood of each node, allowing for information to travel along the edges. The first example of this scheme (Message Passing) was originally suggested by Pearl et al (Pearl, 1982), and was combined with neural network in (Duvenaud et al., 2015), and later generalized in (Gilmer et al., 201 Most graph neural networks applied in practice are specific instances of MPNNs (Gilmer et al., 2017a; Kipf & Welling, 2017; Velickovic et al., 2017).
In MPNNs, information is exchanged between nodes along the graph's 's edges. Each node combines the incoming messages from its neighbors using an aggregation scheme, with common methods being summing, averaging, or taking the coordinate- wise maximum the messages. Let T E N represent the number layers, and define two sequences of positive integers (c+) and (d+ (d=) representing the feature dimensions the hidden layers { (T& y and {S.) / = {R.
) {R0)
Define the message functions as M X, + Gr and unpdate functions as U$ G X + S The features f++1 S.+1
at layer + 1 of the nodes [N] are computed from the features f E S, by
m = Σ M (f,, f kEN(m)
p++1 Um,,, (.)
Here, MM. U and m² are called the message function, update function and mail at time respectively. The summation over the messages can also be replaced for any node by any function Agg'. IIN G. + G. which is permutation invariant.
At step T a readout space can be defined R, = R²T with a permutation invariant readout function RT, e.g., summing, averaging, or taking the max all of the nodes the graph. This produces a vector representation of the whole graph.
B.2. Deep Generative Models
Generative models in machine learning assume that training data is generated by some underlying probability distribution. One goal in this context to approximate this distribution, or build a model that approximates a random sampler of data points from this distribution. Hence, generative models can be used generate synthetic data, mimicking training data by
16

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
sampling from the distribution (Harshvardhan et al., 2020; Dinh al., 2016; Mohamed & Lakshminarayanan, 2016), or to infer the probability of unseen data by substituting it into the probability function. The latter can be useful in tasks like anomaly detection (Pang et al., 2021) in which the model can asses whether sample is probable under the learned model. Two examples of generative models are Generative Adversarial Networks (GANs) (Goodfellow et al., 2014; Radford, 2015) and Variational Autoencoders (VAFs) (Kingma, 2013) 3), which are used both for inference and generation.
VAE models consist of an encoder and a decoder. The encoder maps data from a high-dimensional data space to a nower-dimensional, simpler, code space. The decoder reverses this process, transforming data from the code space back into the data space. The code space serves as a bottleneck, capturing the essential features of the training data, which is often nigh-dimensional (e.g., images, social network graphs) and thus more complex than the code space. If the model trains by encoding followed by decoding, then minimizing the difference between the input and its decoded version, it is called an autoencoder.
In a VAE, training involves encoding each data point to a known distribution (typically Gaussian), sampling from this distribution, decoding it, and then minimizing the difference between the distribution of the original data and the decoded data. For survey on VAEs, see (Tschannen al., 2018).
B.3. Graph Generative Models
Graph generative models learn a probability distributions of graphs. Such models allow for various tasks where the goal is not only to analyze existing graphs but also to predict or simulate new graph data.
Some classical generative models are pre-defined probabilistic models, e.g., the Ked6s-Rényi model, Preferential attachment, Watts-Strogatz model, and more. See (Newman, 2003) for review. Other graph generative models are learned from data, e.g., (Lee& & Wilkinson, 2019; Kipf& & Welling, 2016; You et al., 2018; Bojchevski et al., 2018).
Applications of generative graph models include social network analysis (Wang et al., 2018; Grover et al., 2019; Harshvardhan et al., 2020). anomaly detection B.6, graph synthesis (You et al., 2018; Guo & Zhao, 2022), data augmentation (Ding et al., 2019b), and protein interaction modeling (e.g. for drug manufacturing) (De Cao & Kipf, 2018; Ingraham et al., 2019), to name a few. For a review see (Ma et al., 2021).
Deep Graph Autoencoders. In graph deep learning-bee based autoencoders, one estimates the data distribution by learning to embed the nodes to code space, in which the data distribution is defined to be some standard distribution, e.g., Gaussian, in such a way that the encoded nodes can be recunstructed back to the graph with small error. Graph VAES (Kipf & Welling, 2016; Grover et al., 2019; Samanta et al., 2020; Mchta et al., 2019) embed the data into the code space by minimizing the evidence lower bound loss comprised of the decoding loss and the KL divergence between the encoded distribution and a Gaussian prior.
GAN-based Graph generative models. In (Wang et al., 2018), GAN method for graphs generates neighborhood for each of the nodes and the discriminator gives probability score for each edge. This method also formulate graph version of softmax, and offer a random walk based generating strategy. Another GAN model that is used for anomaly detection is GAAN (Chen et al., 2020b). In GAAN, the ground truth and generated node attributes are encoded into a latent space from which the adjacency between any two nodes is decoded using a sigmoid of the inner product between their latent features.
Normalizing Flows-based Graph Models. Normalizing flows models (Dinh et al., 2016) also have adaptations for graph data. For example, the work of (Liu et al., 2019; Madhawa et al., 2019) offers version of coupling blocks that use message passing neural networks. See more details on normalizing flows in Section B.8.
B.4. Stochastic block models
A stochastic block model (SBM) a generative model for random graphs. A basic stochastic block model is defined by specifying number of classes K, the probability pk of random node being in block k. for is E [K], where Σx Pk 1, and an array of values C = (ca. ) generated graph of N nodes is independently chosen to belong to one of the classes at random, with probabilities {pk [ Then, the edges of the graph are chosen independently at random according to the following rule. For each n E [N], denote by kn E [K] the class of n. Each dyad
E [0, 1 indicating edge probabilities between classes. Each node of a randomly
(n, m) E [N] is chosen to be an edge in probability kk... Namely, the entries ana of the adjacency matrix of the random graph are independent random Bernoulli variables. See (Lee & Wilkinson,
17

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communitics
2019) for a review SBMs.
For each node n, denote by fn {0, 1) the vector such that fü = if and only if K, Hence, in basic SBM, the presence of an edge between nodes n and m follows Bernoulli distribution with parameter P(n m fm fm C) f Cfmm where the adjacency matrix is P = FCF", where F E R K is the matrix where each row n has the feature f, (Nowicki & Snijders, 2001b). This model can be extended to intersecting classes, where now f, can have more than one nonzero entry (Mørup et al., 201 I; Miller et al., 2009; Palla et al., 2012).
In a Pernouli-Poissonn SBM OYang & Leskovec, 2013; Zhou, 2015; Shchur Günnemann, 2019), the probability for a non-edge is modeled by a Poisson distribution. The idea is that the more classes and m share, the higher the probability that there is an edge between them. Hence,
P(n m fffm fm,s C) = e Cf.
(21)
with the expected number of edges being f, T Cf..
In both the Bernouli and Bernouli- models, the probabilisic model of the entire graph is given by a product of the probabilities of all of the events
P C)
II nE[N] mEN(()
II
P(n mammm m) II P(-(n~m))
mgN(n)
Here, the square root is taken since assume that the graph is undirected so the product goes over all of the edges twice (Aicher et al., 2015; Morup et al., 2011).
When fitting an SBM to a graph, both the class affiliations of nodes and the block structure C are learned (Snijders & Nowicki, 1997; Nowicki & Snijders, 2001a; Latouche et al., 2012).
B.5. Community Affiliation Models
Community detection a fundamental task in network analysis, aiming to identify groups of nodes that are more densely connected internally than with the rest of the network. This process is useful for understanding the structure and function of complex networks, such as social, biological, and information networks (Fortunato & Hric, 2016).
Although there exist models in which each node belongs only one community as in traditional SBM models (Holland et al., 1983), and some relatively new deep learning models such as (Cavallari et al., 2017), it was shown that real-world networks often exhibit overlapping communities (Yang & Leskovec, 2014; 2013), where nodes belong to multiple groups and the probability of connectivity increases the more communities two nodes share. This indeed makes intuitive sense when looking at, e.g., social networks, where the more common interests and social circles people share the more they are likely to connect.
An example of a community affiliation model that can generate new graphs is AGM (Yang Leskovee, 2012), which classifies all of the nodes in graph into several communities, where each community is has probability pk for two member nodes to connect. If we denote by Cn.m the set of communities two nodes n, E [N] share, then the probability of an edge between n and m is
p(n ~ m) = 1- II Pk)-
AECxm
To sample a new graph from a trained model, nodes are sampled and assigned communities based on the relative sizes of communities in the training graph, and edges are connected based on their mutual community memberships.
Community affiliations can also be continuous, where nodes have varying degrees of membership in multiple communities. Community Affiliation models with continuous communities include Mixed Membership SBM (MMSBM) (Airoldi et al., 2008) which is an SBM which allows nodes to have mixed memberships in multiple communities, and BigClam (Yang & Leskovec, 2013), which is a Bernouii Poisson model model that scales efficiently for sparse graphs.
is also worth mentioning the NOCD model presented in (Shchur & Günnemann, 2019) which uses the Bernouli Poisson loss, but embeds the nodes of the graph into the code space using a learned GNN. Another related paper (Sun et al., 2019).
18

---

PicClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
which models the features and communities separately, learning latent features from which it estimates the community affiliation.
While community affiliations are typically non-negative, there are models where affiliations can be negative. An example is the Signed Stochastic Block Model (SSBM) (Jiang, 2015).
B.6. Anomaly Detection
Anomaly detection in graphs aims to identify nodes or subgraphs that deviate significantly from the typical patterns within the graph. This is useful in various applications such as network security, fraud detection, and social network analysis. In the unsupervised formulation of the problem, there is no labeled data in the training process, We highlight five works in this direction. GAAN (Chen et al., 2020b) and AEGIS (Ding et al., 2021) use a generative adversarial approach, training a discriminator to distinguish real and fake nodes. Dominant (Ding et al., 2019a) and AnomalyDAE (Fan et al., 2020) identify anomalies via reconstruction errors of graph autoencoder.
Another work is (Qiao et al., 2024), which considers semi-supervised setting. Here, there is a relatively small number of available labeled normal nodes during training (nodes that are known to not be anomalies), and the goal is to predict the anomalies in the unknown nodes.
B.7. Link Prediction
Link prediction in graphs aims to predict missing or future connections between nodes based on the existing structure and node features. This task is critical in various domains such as social networks, biological networks, and recommendation systems. In the supervised setting, a subset of dyads is withheld as a test set, with their labeles (edges or non-edges) omitted. The goal is to predict the connectivity of these omitted dyads using the remaining data, which may also include node features.
We highlight five notable works in this area. The Adamic-Adar index (Adamic & Adar, 2003) henceforth referred as AA, is second-order heuristic that assumes shared neighbors with lower degrees contribute more to the likelihood of a link, while high-degree neighbors are less significant. VGAE (Kipf & Welling, 2016) is variational graph autoencoder, discussed in Section B.3. LINKX (Lim et al., 2021a) decouples the feature and structure representations in a graph and uses a simple framework to process this information separately. GAT (Velickovic et al., 2017) applies an attention mechanism in the message passing process, allowing the model to weight neighboring nodes based on their importance, Another recent work, DisenLink (Zhou et al., 2022), learns disentangled representations of nodes by capturing multiple latent factors, allowing it model various aspects of node connectivity for link prediction. All models mentioned utilize node features accept for AA.
B.8. Normalizing Flows
Normalizing flows are deep learning algorithms that estimate probability distributions, and allow efficient sampling from this distribution. They do so by constructing an invertible coordinate transformation between the unknown target probability space and standard probability space with well known distribution (e.g. Gaussian). This transformation is modeled as deep neural network, composed of a series of basic transformations called flows.
Notations. Let F represent the space of the target data, with an unknown probability density function pr : F + 20). We denote the elements of F by f.
Let Z represent latent space with a known probability density funcion pz Z - [0, oo). We denote the elements of Z by z. The density function pz is often chosen be standard isotropic Gaussian with zero mean and identity covariance, denoted by (0.
Goal. The goal in normalizing flows is to learn an invertible transformation Tg F - Z (parameterized by 0) which maps the target space F to the latent space Z, and preserves probabilities. Namely, To should satisfy: for every measurable subset F C F we have
J. (o(D)p=(Ddd Jr JT.(P) Pz(2)dz.
Here (F) = (= E
3f E F such that (f()) = zz). Such a transformation can be seen as a change of variable.
19

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Density Transformation. Given invertible transformation Tg, the target density p=((f) can be expressed in terms of the latent density (z)... By upholding the constraint that either probability density function has integral 1 over their respective spaces, one can deduce the change of variable formula
(f) 0f
pf( (To((())) det
Here, (Ta(f) denotes the Jacobian matrix of the transformation To with respect to F and det(-) denotes its determinant.
Sequential Composition of Flows. In practice, the transformation Tg is modeled composition of L simpler invertible transformations {Toi 1En between the consecutive spaces {2') where 2 F and z 2 in the previous
notations. The invertible mappings To: Z zi-1 are called flows, and we have
Te ToL Ta--1 Tg:
where o denotes function composition. The overall density function for then becomes
(TT)(C))
ps( P2(To(f)
II det
Of;
Here, f; is the intermediate representation after applying the first i flows. The algorithm is optimized by maximum log likelihood, namely, by maximizing
log (fr(f))
(T,((.)) )
= =log (pz(T((f)))
log
det
Of,
using gradient descent.
Since To and every Tä invertible, information can also flow in the opposite direction in order to sample data. First, point is sampled pz and the inverse transformation T7 is applied to map the sample into the data space F. Since T's is composed of series of flows, the generated point in the data space is
f To (z) Tgi TTp (z).
T (z).
ReaINVP. One popular method of implementing normalizing flow the Real Valued Non- Con-Volume Preserving (RealNVP). In this model, the flows Tg: are modeled as mappings called coupling blocks. In coupling block, the input vector f (or z in the generative direction) is split into two vectors: fí and fj each the same dimension. Namely, f (fi f2)). The flow To is then defined to be
P fl
(22)
pi
f ④ Sgi (ft) + to. (f))
(23)
Where (sg: (-), tg: (-) are Multi Layer Perceptrons (MLPs) parameterized by 0', and @ is elementwise product. In addition, the elements of f are permuted at every i before applying the coupling block, using predefined permutations, that are parts of the hyperparameters of the model. easy to see that the Jacobian
(ar: (f,) a diagonal matrix with for the first
dim(f) ( elements, and sp: (f)) for the last dim(f;) elements. This makes the log of the determinant of the Jacobian
OT:
))
dim(fh) Σ
log (spr (Th)s).
log
det
(24)
Or,
Hence, this determinant is easily computed in practice.
20

---

J.N [0, uniformly. Observe that (X.)) R K are indepndent samples via the PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communitics
For generation, the inverse transformation be calculated easily as
1+1
Z'A
A
1+1 zB t(z'A)
2
s(Zi))
where the division is elementwise. Here, the log determinant the Jacobian can be calculated similarly to (24), applied to 1 1/s(z)))-
B.9. The Lorentz Inner Product
The Lorentz inner product a bilinear form used in the context of special relativity to describe the spacetime structure. In a four-dimensional spacetime, the Lorentz inner product between two vectors and w given by:
w) Wo U1 W1 02 Ug 00g
Here, up and Wo represent the "time" components, while V1, U2 vy and W1, W2, Wy represent the "spatial" components, The negative sign in front of the time component is what distinguishes the Lorentz inner product from the standard Euclidean inner product, making it suitable for modeling the geometry of spacetime where time and space are treated differently. Note that due to the subtraction, the Lorenz inner product is in fact not an inner product as it is not positive definite. the context of special relativity, the points for which the Lorenz product remain positive define the so called "light cone" structure of spacetime, separating events into those that are causally connected and those that are not.
The Lorentz inner product is specific example of broader class of inner products known as pseudo-Euclidenn inner products. In Euclidean space, the inner product can have mixture of positive and negative signs, leading to different geometric properties. These spaces generalize the concept of Euclidean space by allowing for non-positive definite metrics.
C. PClam and PieClam as Graphons
graphon is model which be seen graph generative model that extends SBMs. A graphon (Borgs al., 2007; Lovász, 2012) can be seen weighted graph with a "continuous" node set [0, 1]. Definition C.1. The space of graphons W defined to be the set of all measurable function W [0, 1]2 > [0, 1] which are symmetric, namely W (Ix, y) = W z).
The edge weight W (z, 3) of graphon W W can be seen the probability of having edge between node and node Given a graphon W, random graph is generated by sampling independent uniform nodes {X,, from the graphon domain [0, I]. and connecting each pair X,, X, in probability W(X, (Xa,, Xm) to obtain the edges of the graph.
We next show that Clam models with prior are special cases of graphon models. Note that the prior p defines a standard atomless probability spaces over the community affiliation space R Since all standard atomeless probability spaces are equivalent, there is probability preserving a.e. bijection E, [0, 1] - R that maps the prior probability to the uniform probability over [0, 1]. Now, the PieClam model for generating graph of N nodes can be written follows.
Sample N points { probability density p.
Connect the points according the BigClam of IeClam models P(n (x..)) or) (7).
This shows that PClam and PieClam coincide with the generative graphon model W y) P(n (X), where P is defined either by (1) by (7).
D. Extended Details on Experiments
D.I. Additional Architecture Details in PieClam and PClam
Added Affiliation Noise. When training the prior, overfitting may cause the probability to spike around certain areas in the affiliation space, e.g., around the affiliation features of the nodes. To avoid this issue, we add gaussian noise the
21

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Method
Reddit
Elliptic
Photo
(S)- IeClam
64.12 = 0.25
43.58 + 0.15
*57.67 = 1.79
(S) PieClam
*63.97 = 0.50
43,47 = 00.12
58.98 + 2.51
(P) PieClam
46.76 2.50
63.18 3.02
45.73 + 7.03
(PS) PieClam
63.99 0.50
53.81 1.63
58.99 + 2.52
DOMINANT
51.1
29.6
51.4
AnomalyDAE
50.9
*49.6
50.7
OCGNN
52.5
25.8
53.1
AEGIS
53.5
45.5
55.2
GAAN
52.2
25.9
43.0
TAM
60.6
40.4
56.8
Table 4: Comparison of Clam anomaly detectors with competing methods. First place in boldface, second with underline, third with star. We observe that our methods are first place on all datasets. Moreover, S- leClam, PS-PieClam and S BigClam each beats the competing methods in two out of the three datasets.. The accuracy metric is areas under curve (AUC).
Method
Reddit
Elliptic
Photo
(S)- IeClam
64.12 + 0.25
43.58 + 0.15
*57.67 1.79
(S) PieClam
*63.97 0.50
43.47
58.98 + 2.51
(P) PieClam
46.76 2.50
63.18
45.73 7.03
(PS) PieClam
63.99 + 0.50
53.81 + 1.63
58.99 = 2.52
(S) PieClam (No Attr)
63.46 + 0.15
43.50
58.11 # 2.73
(P) PieClam (No Attr)
45,30 # 1.42
$50.25
48.67 # 10.47
(PS) PieClam (No Attr)
63.51 + 0.15
43.50 + 0.13
58. 12 + 2.75
Table 5: Comparison of attributed and unattributed PieClam anomaly detection.
affiliation vector as a regularization at each step of training the normalizing flow prior model. The normalizing flow model then transforms the same point to a slightly different location in the code space. The noise optimization therefore provides resolution to the prior, smoothing the distribution in the affiliation space. Noise addition is the primary regularization method we have used when training the prior in all of our experiments.
Densification. For very sparse datasets, Clam models may not behave well. In such cases, the community structure sometimes unstable, where the same node can find itself in different communities based on slightly different initial conditions. In order to strengthen the connections within communities, we apply two-hop densification scheme very sparse graphs. Namely, we connect two disjoint nodes n, m with an edge there is a third node for which n ~ k and m k. find that this scheme improves anomaly detection on Elliptic, Photo and Reddit datasets. Densification may strengthen the community structure some datasets, but can also destroy it in others. In the experiments on synthetic datasets we did not use densification, as these graphs are relatively dense.
D.2. Anomaly detection
Metric. In order to measure the accuracy of the anomaly detection classification we use the area under the Receiver Operating Characteristic (ROC) curve (Peterson et al., 1954). The curve plot of the true positive rate (TPR) against the false positive rate (FPR) for the range of the threshold values between the value that classifies all samples as true and the value that classifies all false. The area under the curve signifies the general tendency of the curve toward the point (0,1) for which FPR= and TPR=1 1.
Experimental Details. For the anomaly detection results, each model is assigned a single configuration that is used across all datasets. Every configuration is evaluated by training the model 10 times per dataset, and the results are reported as mean and standard deviation. The detailed results with error bars are shown in Table 5. To select the global hyperparameters, we first conducted a wide sean over parameter ranges, followed by a finer search around the most promising regions.
22

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Method
Squirrel
Photo
Texas
John's Hopkins 55
PieClam
98.7 #0.0
98.4 #0.0
85.0 + 2.0
95.5 =0.0
BigClam
98.5 + 0.0
97.4 0.1*
78.2 + 3.0
94.9 = 0.0
VGAE
98.2 +0.1
#0.8
68.6 #4.2
92.8 +0.2
GAT
98.0
90.3
65.5
94.3 #0.5
LINKX
98.1 +0.3
97.0
75.8 +4.7
93.4 40.3
AA
97.1 #0.4
97.4 +0.4
53.1 #6.2
96.1 #0.5
DisenLink
98.3 #0.1*
+0.1
81.0 4.0
97.5 +0.1
Table Comparison of Clam link predictors with competing models. First place in boldface, second with underline, third with *star
Furthermore, in this section we also run our anomaly detection methods without using the node features, namely, only using the graph structure. We find that we comparable results on Photo and Reddit with or without node features, but that the detection Elliptic decreases significantly. Still, anomaly detection Elliptic without node features is competitive with state of the art models that do use node features. The results are in Table 5.
We proceed to compare the optimization that includes the node features to the optimization that didn't. tt The comparison is presented in
T-Test Comparison Summary. We conducted t-tests determine node features/atrributes ("With Features") significantly improve performance compared to not using attributes ("Without Features"), across the Reddit, Elliptic, and Photo datasets for each method (S, PS). Even though S method is not affected directly by the affiliation vectors, the latter affect the convergence of the prior in the affiliation space and have indirect effect.
Reddit Dataset: Attributes did not significantly improve performance for the "Star" (S) and "Prior Star" (PS) methods. However, "Prior" (P) did show a significant improvement with attributes (p-value=0.0002).
Elliptic Dataset: "Prior" (P) and "Prior Star" (PS) both showed significant improvements with attributes (p- value=<0.0001). However, the "Star" (S) method did not significantly benefit from attributes.
Photo Dataset: The "Star" (S) method did not show significant difference (p-value=0.6864) The "Prior Star" (PS) method, however, did show a significant benefit from attributes (p-value<<00000), and "Prior" (P) had borderline significant result (p-value=0.0529).
In conclusion, attributes did not make a difference for the "Star" (S) method across all datasets (as would be expected), and for the "Prior Star" (PS) method in the Reddit dataset. However, the "Prior" (P) and "Prior Star" (PS) methods mostly showed improvement in the Elliptic dataset.
D.3. Link Prediction
Probabilistic Model with Omitted Dyads. When doing link prediction (as explained in Section B.7) remove portion of all dyads from computation during training, treating the omitted dyads neither as edges nor non-edges. Having non-affiliated dyads modifies the PieClam log likelihood as explained next.
Recall that E denotes the set of all edges in the graph. Denote = {(n, n) E [N]] Denote by E = [N]] \ (EUD) the set of non-edges. Denote the sets of omitted edges and non-edges by É and É respectively. We assume that the number of omitted dyads ÉUË of the same order as the number of edges E. Hence, for sparse graphs |BÚB < N The PieClam loss which ignores the omitted dyads is defined to be
2, É) 2 Σ log(p(En)) +
Σ (N.m)EEV
log(1 - e Lem
Σ
f Lf.
(25)
nE[N]
(
Next we formulate the PieClam loss as an efficient "message passing," requiring only O((E)) operations. First, note that
[N] \ (E 6. FÜFUD.
23

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Therefore,
Σ
log(1 - f/ Lfm)
Σ
L
Lfm
(H,m)EEEE
(n.m)EEV
Σ
log(1
F. Lfm)
Σ
LL
E
L.
(
(n.m)e(N²
(N
Σ
log(1
Lf
E
L
LL
E
E Lfm
(n.))
(N,))EEUBU
Σ
log(1 e -..
Σ
Σ
Lfm +
Σ
Lf
(
nEIN]
mE[N]
(AU))EBUBUD
Hence,
2F E.F. -2 Σ log(p(f.)) +
Σ
log(1 e -hi
NE|N]
E
(26)
Σ
Σ ME(N)
Lfm
+
Σ
f Lfms
[E
(N.D)EBUEUD
gradient ascent with respect formulation an efficient message passing algorithm.
Developing the expression further, we achieve an equivalent form that resembles the original clam loss.
First we decompose the last term into
Σ
Lf..
Σ
f. Lf
Σ f Lf..
( BORLD
(n,m) EXB
(n.m)RRJBO
We substitute this sum into Equation 26 to get
E,FF
= Σ log(p(L.)) +
Σ
log(1 1 c -f
RE[N]
(R.
Σ RE[N]
f Σ Lf
Σ
log(e" Lfm)+
Σ
f, Lf..
m
BV
(UB))
We unify the second and fourth sums and use logarithm identities to get
2
É.
Σ log(p(F.))
Σ
log(e Lf
1)
Lf
CELLE.) (a)E[N]
Σ
L. (R.))EZUR
Σ
WE[N]
(
NE[M]
mE[N]
(27)
The first three terms (in brackets) of 27 make the original clam loss (Equation 10) the retained set of edges E' É. The forth temm represents MPNN the graph ([V), BUÉ). Since EUE is strictly contained in EUE we use Equation 27 for the link prediction implementation.
Experimental Setup the experiments, we evaluate the model's ability to classify edges and non-edges by constructing a ROC curve as described in Section B.6.
Note that, since the prior is not used in classification, there is added benefit from utilizing node features when training the prior, proposed 2.4. Therefore. the link prediction algorithm relies solely the graph's topological structure and the prior functions only as regularization. We use the scheme from (Zhou et al., 2022), where for each dataset, we generate 10 randomly sampled test sets, each containing 10% of the edges, along with randomly sampled non-edges for every omitted edge. For each split, we perform hyperparameter selection using separate 5% validation set, also paired with 5 non-edges the 10 test sets, along with the standard error of the mean. To select the hyperparameters for each split, we first conducted wide scan over parameter ranges, followed finer search around the most promising regions. To reproducibility, model dataset across sampled test sets. The test sets are available our GitHub repository.
edge. We report the mean accuracy across
single configuration per
24

---

PicClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Model
Dim.
Feat. Iter.
Prior Iter.
Prior Step
S Reg.
First Optimization
Squirrel
PieClam
90
700
2000
5e-6
0.1
Feature
Photo
PClam
150
700
1300
3e-6
Feature
Texas
PieClam
22
2000
1500
5e-6
0.0
Prior
JH55
PClam
200
750
1800
3e-6
Feature
Table 7: Link prediction hyperparameters for each of the datasets. Full configuration details are available in the project's GitHub repository.
Datasets and Baselines. We conduct these experiments four datasets: Facebook 100's Johns Hopkins 55 (Lim al., 2021b) Amazon Photo (Shchur et al., 201 WehKB's Texas and Wikipedia's 's Squirrel (Pei al., 2020). We compare ourselves to the baseline methods AA (Adamic & Adar, 2003), VGAE (Kipf & Welling, 2016), GAT (Velickovic et al., 2017). LINKX (Lim et al., 2021a). DisenLink (Zhou et al., 2022) and BigClam.
Hyperparameter Configuration. As was mentioned in D.3, hyperparameters are selected separately for each dataset and model by randomly selecting validation set outside of the test set. Since all four Clam models special case of PieClam, the best performing model and treat it as a hyperparameter. We describe the hyperparameter configuration for each the models in Table 7. The columns of the table signify the Clam model, AS dimension, number of feature iterations, feature step size, number of prior weight iterations, the prior weight step size, the added noise amplitude, community regularization and the first function in the alternation. The following hyperparameters
present only
constant across all datasets: feature step size (5c-6), I regularization (1), Noisc amplitude (0.1) the number of alternations (7), scheduler step size (3) and the scheduler step size (0.5).
The results on the datasets and the comparison to the other baseline models is presented in Table 6. Baseline results are taken from Table 2 in (Zhou et al., 2022).
Results
D.4. Reconstructing Synthetic Priors
We consider two ground-truth synthetic priors Pbig IR2 + (o) in PClam, and Pie T - [0. oc) in PieClam. We sample N 500 points from each of the priors, decode the corresponding PClam and PieClam graphs, and sample simple graphs from the random Bemouulli edges as shown in figure 4. Then, given these sampled graphs, we reset their affiliation features to random vectors and fit a BigClam and a PClam to the graph sampled from pbig. and an IeClam and a PieClam to the graph that was sampled from Pie-
The optimization results are shown in Figures 5 and 6. Both the priored and unpriored models effectively learned the feature reconstructions in the feature spaces T and R Notably, the features in the priored models are more localized, supporting the claim that the prior acts a regularizer.
The priors themselves are well-approximatee, as illustrated in Figure 6, with the quality of approximation improving as more nodes are sampled from the priors.
D.5. SBM Reconstruction And Distance Convergence
We extend the experiment in Section 4.2 by considering another synthetic SBM, which is off-diagonal dominant. As in Section 4.2, we sample a simple graph with = 210 nodes from the SBM. The non zero probability blocks have probability of 0.5. We estimate the log cut distance between the Clam models (BigClam and leClam) and the SBM during training. We consider for both methods affiliation spaces of dimensions 2,4 4 and 6. In addition, we calculate the cut distance and 12 errors between the Clam models and the SBM. The results shown in Figures& 8 8-13.
D.6. Ablation Study
J and Regularization. The 1 regularization is adapted from the BigClam original architecture and shows improvement when optimizing the models. This regularization type adds a constant update in all of the directions, which means that for every node and it's affiliation feature f., components that are not updated are moved towards 0 regardless of their magnitude. This constant push towards O forces sparsity in the affiliation matrix and also acts regularization. The regularization is an 1 regularization of the s features and has shown effective for the Squirrel dataset.
Noise Addition. Due to the high expressivity of the normalizing flow model, the neural network tends to learn a narrow distribution around the affiliation features. This overfitting tendency cannot be alleviated by simply reducing the network parameters without significantly compromising the expressivity of the prior. Noise addition offers way to control the prior's 's resolution while preserving its ability to learn complex distributions. An example comparing optimization results with and without noise addition is shown in Figure 7.
The densification method described in Section D.1 can yield varying results depending on the internal structure of the graph. To illustrate the impact of densification, we conducted 10 anomaly detection experiments, following the setup from Section 4.3,
Densification.
25

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
1.5
1.5
1.
1.
0.5
0.5
0.0
-0.5
-0.5
-1.0
-1.0
-1.5
-15
1
feat 0 vs feat 1
1.0
10
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Figure 4: Right left: ground truth synthetic prior and sampled graph. Top: graph sampled in T using PieClam. Bottom: graph sampled in R using Pelam.
but without applying densification. The results are shown in Table 8.
Method
Reddit
Elliptic
Photo
(S) PieClam
0.6320 0.0054
0.4354 0.0005
0.5727 0.0151
(S) PieClam (No Dens.)
0,5480 0.0022
0.4009 0.0021
0.5293 + 0.0446
(P) PieClam
0.5089 0.0219
0.6201
0.0176
0.4252 0.0074
PieClam (No Dens.)
0.5088 0.0383
0.6378
0.0245
0.4325 0.0089
(PS) - PieClam
0.6329 0.0052
0.5294 0.0089
0,5289 0.0127
(PS) PieClam (No Dens.)
0.5466 0.0047
0.6181 0.0233
0.4538 + 0.0030
Table 8: Comparison of PieClam on densified and non densified datasets. Boldface denotes a significantly better result (difference over 2 standard deviations), underline denotes an insignificant difference.
As seen in Table 8, densification generally improved results across the datasets, except for the Elliptic dataset using the P and PS methods, where the undensified datasets performed significantly better. For the Reddit and Photo datascts with the P method, the difference not significant.
26

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
Feat: 0 va feet
Feat vs feat
2.0
1.-
0.5
0.0
-0.5
-15
0.0
0.5
Figure 5: Left to Right: leClam and BigClam Reconstructions of features sampled from synthetic priors
13
320
925
820
33%
230
2.5
Seat a octwee
prior
55
10
Figure 6: Left right: reconstructed nodes, reconstructed prior. Top to botton: PieClam in T, PClam in R
feat vs feat
peior
15
14-
05
0.0
0.9
2.0
2.5
15.6
17.5
1.0
3.0
10.
2.5
0.
3.
Figure 7: Left to right: reconstructed nodes, reconstructed prior. Top to botton: With and without noise addition.
27

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
0
1.0
0
0.6
0.8
50
50
0.4
0.6
100
100
0.4
0.2
150
150
0.2
200
200
0.0
0.0
50
100
150
200
100
200
10
011
Acorscyy
0.7
04-
0.00
2000
4000
60C0
0000
10003
2000
1000
6000
8000
10000
2000
4000
6:00
8000
10000
Beroc on
Eeror
Eeratin
Figure 8: Left right: Target SBM. Fitted BigClam graph with two communities. Error function of optimization iteration where error is, left to right, log distance, cut distance, 12 distance. After convergence, the log cut distance between the SBM and BigClam is 0.0776.
28

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
0
1.0
0
0.6
0.8
50
50
0.4
0.6
100
100
0.4
0.2
150
150
0.2
200
0.0
200
0.0
0
50
100
150
200
0
100
200
36
13
30-
20
A3
6.8
2000
0002
8:00
B00C
20002
2020
1000
6000
D000
20000
2000
4000
2000
8000
10000
Recation
Berot
Eeracion
Figure 9: Left right: Target SBM. Fitted BigClam graph with four communities. Error function of optimization iteration where error is, left to right, log distance, cut distance, 12 distance. After convergence, the log cut distance between the SBM and BigClam is 0.0775.
29

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
0
1.0
0.6
0.8
50
50
0.4
0.6
100
100
0.4
0.2
150
150
0.2
200
200
0.0
0.0
0
100
200
50
100
150
200
1.
ACOPTEE
3.2
0.9
0.8
0
1000
4200
5000
8000
50000
2000
4000
5000
5002
10000
2000
5002
6000
D000
10000
Teradin
Stration
Eeratio
Figure 10: Left to right: Target SBM. Fitted BigClam graph with six communities. Error function of optimization iteration where error is, left to right, log distance, cut distance, 12 distance. After convergence, the log cut distance between the SBM and BigClam is 0.0776.
30

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
0
1.0
0
0.8
0.8
50
50
0.6
0.6
100
100
0.4
0.4
150
150
0.2
0.2
200
200
0.0
0.0
0
100
200
50
100
150
200
0.02
0.02
0.12
0.04
0.2
0.12
0.82
0.100
0.72
0.000
0
2000
2000
6000
5000
20000
2000
4000
6000
BOCO
10000
2000
4000
6000
5000
10000
Seratio
Keration
Figure 11: Left right: Target SBM. Fitted leClam graph with communities. Error function of optimization iteration where error is, left to right, log distance, cut distance, 12 distance. After convergence, the log cut distance between the SBM and IeClam is 0.0662.
31

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
0
1.0
0
50
0.8
50
0.6
0.6
100
100
0.4
0.4
150
150
0.2
0.2
200
200
0.0
0.0
50
100
150
200
100
200
34-
AC01915
20
2000
0002
0:00
800C
20002
2000
1000
6000
D000
20000
2000
4000
5000
8000
10000
Recation
Berot
Eeracion
Figure 12: Left right: Target SBM. Fitted IeClam graph with four communities (two inclusive and two exclusive). Error function of optimization iteration where errrr is, left to right, log cut distance, cut distance, 12 distance. After convergence, the log cut distance between the SBM and IeClam is 0.0312.
32

---

PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities
0
1.0
0
50
0.8
50
0.6
0.6
100
100
0.4
0.4
150
150
0.2
0.2
200
0.0
200
0.0
50
100
150
200
0
100
200
2.02
0.5
64
2.0
0.3
0.2
0.0
0
3000
4000
0000
8000
10000
2000
1200
60C0
0020
10000
2000
4000
0000
8000
10000
Emaaton
Benic
Seration
Figure 13: Left right: Target SBM. Fitted IeClam graph with six communities (three inclusive and three exclusive). Error function of optimization iteration where error is, left to right, log cut distance, cut distance, 12 distance. After convergence, the log cut distance between the SBM and leClam is 0.0309.
33


Reviews:
[{"review_id": "j0TkijSWJe", "reviewer": "Reviewer_3NUL", "summary": "The submitted manuscript introduces PieClam, a graph autoencoder that learns node embeddings by maximizing the log-likelihood of the decoded graph. It extends the well-known BigClam method in two ways. First, PieClam incorporates a learned prior on the node distribution in the embedding space, shifting from a simple pairwise interaction approach to a full-fledged graph generative model. Second, while it retains BigClam’s focus on sets of nodes with high connectivity (inclusive communities), it also introduces the notion of exclusive communities, i.e., groups of nodes that exhibit strong disconnection. This dual capacity to identify both inclusive and exclusive communities is enabled by a new graph similarity measure called the log cut distance, through which the authors demonstrate that PieClam is a universal autoencoder capable of approximating any graph distribution within a uniform bound. Empirical results are provided in tasks such as graph anomaly detection and link prediction.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and in depth evaluation of our paper.\n\n>**Weaknesses:**\n>>1. A key concern lies in the equivariance of the encoder architecture...\n\n*Response.* Thank you for this comment. **PieClam (and all other Clam models) are in fact equivariant to node re-indexing.** This is due to the fact that  maximizing the log likelihood via gradient descent in Clam models can be formulated as a message passing algorithm. We wrote this on Page 3, Column 1, Line 158 (about BigClam):\n\n*\"We observe that the optimization process is a message passing scheme\"*\n\nBut we indeed did not link this to equivariance, and did not repeat this claim about all other Clam models. **If accepted, we will add an explanation about the equivariance of Clam methods to node re-indexing.**\n\n>>2. The experimental evaluation would benefit from additional benchmarks...\n\n*Response.* We ran additional experiments on link prediction on the OGB-ddi dataset. We will add more experiments in the final version.\n\n| Model                  | Hits@20 test         | AUC\n|------------------------|----------------------|-------------\n| **IeClam**             | **90.72 ± 2.35**     | 99.89 ± 0.00\n| NCN                    | 76.52 ± 10.47        | 99.97 ± 0.00\n| NCNC                   | 70.23 ± 12.11        | 99.97 ± 0.01\n| GraphSAGE              | 49.84 ± 15.56        | 99.96 ± 0.00 \n| GCN                    | 49.90 ± 7.23         | 99.86 ± 0.03\n| SEAL                   | 25.25 ± 3.90         | 97.97 ± 0.19\n| PEG                    | 30.28 ± 4.92         | 99.45 ± 0.04\n| BUDDY                  | 29.60 ± 4.75         | 99.81 ± 0.02\n| Node2Vec               | 34.69 ± 2.90         | 99.78 ± 0.04\n| MF                     | 23.50 ± 5.35         | 99.46 ± 0.10 \n| Neo-GNN                | 20.95 ± 6.03         | 98.06 ± 2.00  \n| GAT                    | 31.88 ± 8.83         | 99.63 ± 0.21\n| CN                     | 17.73                | 95.20  \n| AA                     | 18.61                | 95.43 \n| RA                     | 6.23                 | 96.51\n| Shortest Path          | 0                    | 59.07  \n\n>>3. The computational complexity of the proposed approach remains unspecified, leaving questions about its scalability and feasibility for large datasets.\n\n*Response.* We wrote about the computational complexity of BigClam on Page 3, Column 1, Line 144:\n\n*\"In order to implement the above iteration with $O(|E|)$ operations at each step, instead of $O(N^2)$, the loss can be rearranged as...\"*\n\nAs written above, basically, Clam models are trained with message passing algorithms, so they have efficient computational complexity: linear in the number of edges. \n\nBigClam. On Page 4, Column 1, Line 208, wewrote:\n\n*\"This loss can be efficiently implemented on sparse graph by the formulation...\"*\n\nWe agree that we have not clarified enough that all other Clam models, including PieClam, share their computational and memory complexity with \n\n**We will clarify in the camera ready version (if accepted) that all Clam models have linear complexity with respect to the number of edges**\n\n>>4. The paper does not fully explain how the model generalizes to unseen data.\n\n*Response.* Studying how and why models generalize to unseen data is one of the key and most fundamental (mostly open) questions in learning theory, and specifically statistical learning. In this paper we do not provide generalization analysis, e.g., in a PAC learnability setting, VC dimension, Rademacher complexity, etc. We leave such analysis to future works, and note that most papers that first proposes a deep learning architecture do not provide a generalization analysis.\n\nIf your question is meant to be more practical, i.e., how the training and test data are defined, and how testing is defined, this depends on the problem.\n\n1. In anomaly detection, the setting is explained in Section 4.3:\n\n*\"In unsupervised node anomaly detection, one is given a graph with node features, where some of the nodes are unknown anomalies. The goal is to detect these anomalous nodes, without supervising on any example of normal or anomalous nodes, using only the structure of the graph and the node features\"*\n\nNamely, here generalization is better interpreted as a form of \"transfer learning\". One fits the Clam model to the whole graph data (solving the task of reconstruction/autoencoder), and then uses the trained community affiliation features to solve a different task: evaluating the likelihood of nodes according to the learned probabilistic graph model.\n\n2.  In link prediction, as explained in Section 4.4:\n\n*\"In supervised link prediction, one is given a graph where for some of the dyads it is unknown if they are edges or not. The goal is to predict the connectivity of the omitted dyads.\"*\n\nSo, here the training set for he Clam model are the known dyads (the given known edges and non-edges) and the test set are the unknown dyads, where the task is to decide if each unknown dyad is an edge or a non-edge.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes. The paper’s focus on discovering both inclusive and exclusive communities naturally lends itself to tasks that test how well a model captures nuanced graph structure. Evaluating on anomaly detection and link prediction is appropriate because these tasks directly assess whether the learned embeddings and generative assumptions effectively capture both the presence and absence exclusive of edges.", "theoretical_claims": "The theoretical claims appear to be correct, although I have not personally verified the proofs in detail.", "experimental_designs_or_analyses": "I carefully reviewed the experimental setup and the corresponding analyses, which appear reasonable.", "relation_to_broader_scientific_literature": "PieClam extends ideas from BigClam’s community affiliation framework by adding a learned prior to make it a generative model, drawing on concepts used in SBMs that define latent distributions for edge formation. In embracing both inclusive and exclusive communities, it generalizes beyond models that preserve the triangle inequality and can be applied to bipartite graphs. PieClam’s log cut distance builds upon well-known cut-based measures in graph theory and helps establish it as a universal autoencoder.", "essential_references_not_discussed": "The reference list is sufficient.", "other_strengths_and_weaknesses": "Strengths\n\n1. The paper demonstrates notable originality by extending BigClam into a generative framework and enables a richer representation of graph structure compared to BigClam.\n2. The theoretical analysis is thorough and convincingly supports the approach, underscoring its mathematical soundness.\n3. The manuscript is well written, clearly organized, and technically solid, making it accessible to both experts and newcomers in the field.\n\nWeaknesses\n\n1. A key concern lies in the equivariance of the encoder architecture. While it is straightforward to design universal autoencoders when equivariance is not enforced, the paper does not clarify how its approach balances equivariance against universality.\n2. The experimental evaluation would benefit from additional benchmarks, particularly for link prediction on OGB datasets, to more rigorously establish the method’s effectiveness and generalizability.\n3. The computational complexity of the proposed approach remains unspecified, leaving questions about its scalability and feasibility for large datasets.\n4. The paper does not fully explain how the model generalizes to unseen data.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please see respond to the aforementioned weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nxGirmpFhB", "reviewer": "Reviewer_gDLV", "summary": "The paper introduces PieClam, a universal graph autoencoder that extends traditional community affiliation models by incorporating both inclusive and exclusive communities. The method uses a novel decoder based on the Lorentz inner product to overcome the triangle inequality limitations of previous models, thereby accurately representing graphs with structures like bipartite components;Also, the paper proposes a generative extension through a learned prior ) . The authors perform experiments on tasks such as anomaly detection and link prediction and show competitive performance against state-of-the-art baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and in depth evaluation of our paper.\n\n>**Claims And Evidences:**\n>> ...the evidence on sparse graphs is a bit less comprehensive. Further empirical validation in more diverse settings would improve the support for universality claims.\n\n*Response.* The experiments in the current version of the paper (anomaly detection and link prediction) are already on sparse graphs. For example, the Texas graph has 183 nodes and 279 edges. \n\nWe ran additional experiments on link prediction on the OGB-ddi dataset. We will add more experiments in the final version.\n\n| Model                  | Hits@20 test         | AUC\n|------------------------|----------------------|-------------\n| **IeClam**             | **90.72 ± 2.35**     | 99.89 ± 0.00\n| NCN                    | 76.52 ± 10.47        | 99.97 ± 0.00\n| NCNC                   | 70.23 ± 12.11        | 99.97 ± 0.01\n| GraphSAGE              | 49.84 ± 15.56        | 99.96 ± 0.00 \n| GCN                    | 49.90 ± 7.23         | 99.86 ± 0.03\n| SEAL                   | 25.25 ± 3.90         | 97.97 ± 0.19\n| PEG                    | 30.28 ± 4.92         | 99.45 ± 0.04\n| BUDDY                  | 29.60 ± 4.75         | 99.81 ± 0.02\n| Node2Vec               | 34.69 ± 2.90         | 99.78 ± 0.04\n| MF                     | 23.50 ± 5.35         | 99.46 ± 0.10 \n| Neo-GNN                | 20.95 ± 6.03         | 98.06 ± 2.00  \n| GAT                    | 31.88 ± 8.83         | 99.63 ± 0.21\n| CN                     | 17.73                | 95.20  \n| AA                     | 18.61                | 95.43 \n| RA                     | 6.23                 | 96.51\n| Shortest Path          | 0                    | 59.07  \n\n>**Methods And Evaluation Criteria:**\n>>...additional discussion on scalability (especially for large or sparse graphs) and hyperparameter sensitivity would be valuable.\n\n*Response.* Regarding scalability, we will add to the camera ready version of the paper a discussion that shows that both the memory and time complexity of all Clam models are linear in the number of edges.\n\nWe already wrote about the computational complexity of BigClam on Page 3, Column 1, Line 144:\n\n*\"In order to implement the above iteration with $O(|E|)$ operations at each step, instead of $O(N^2)$, the loss can be rearranged as...\"*\n\nMoreover we wrote about BigClam, Page 3, Column 1, Line 158:\n\n*\"We observe that the optimization process is a message passing scheme\"*\n\nWe agree that we have not sufficiently clarified that all other Clam models are trained with a message passing scheme, and share their complexity with BigClam: linear in the number of edges. We only wrote on Page 4, Column1, Line 208:\n\n*\"This loss can be efficiently implemented on sparse graph by the formulation...\"*\n\n**We will clarify in the camera ready version that all Clam models have linear complexity with respect to the number of edges.**\n\nRegarding hyperparameter sensitivity, in Appendix D6 we do an ablation study where we show the impact of certain parameters on the performance of the model. We can extend this appendix to study sensitivity to more hyperparameters.\n\n>**Theoretical Claims:**\n>>...some assumptions (e.g., regarding graph density) might limit their direct applicability to real-world sparse graphs. \n    \n*Response.* We already shortly discussed this in the Conclusion (Page 8):\n\n\"Another limitation of our analysis is that the log cut distance is mainly appropriate for dense graphs. Future work will extend this metric to sparse graphs...\"\n\nbut we agree that this discussion may be too short. **If accepted, we can extend the discussion about sparsity, mainly stating that the analysis is mostly appropriate for dense graphs (but the method is appropriate also for sparse graphs).**\n\nRegarding applicability of the method to real-world graphs, the method was tested against sparse graphs in anomaly detection and link prediction benchmark, where we got competitive performance, demonstrating that the method performs well empirically also for sparse graphs.\n\n\n>**Experimental Designs Or Analyses:**\n>>Nonetheless, it would be useful to see more detailed analyses on the model’s performance with respect to computational efficiency... especially since the training involves simultaneous optimization of node embeddings and a prior.\n\n\n*Response.* Note that the prior is a node-wise computation, so it is dominated by the rest of the log likelihood terms in optimization.\n\nWe wrote on Page 4, Column 2, Like 216:\n\n*\"Observe that the PieClam loss is similar to the IeClam loss, only with the addition of the prior acting as a per node regularization term\"*\n\nWe will extend the text in the camera-ready version and write that, as a reuslt, adding the prior does not asymptotically increase the complexity of the model.\n\n>**Essential References Not Discussed:**\n\nWe will properly refer to the suggested papers in the camera-ready version of the paper if accepted.\n\n>**Weaknesses:**\n\n*Response.* See our responses above.", "claims_and_evidence": "The authors claim that PieClam is a universal autoencoder that can approximate any graph (with a fixed parameter budget per node) and that it outperforms or competes with existing methods on several benchmarks. The paper supports these claims with both theoretical results (specifically , this can be shown in Theorems 3.7 and 3.8) and extensive experimental evaluations on synthetic datasets and real-world tasks. While the theoretical proofs appear sound under the presented assumptions, the evidence on sparse graphs is a bit less comprehensive. Further empirical validation in more diverse settings would improve the support for universality claims.", "methods_and_evaluation_criteria": "I believe that the proposed method is well motivated and builds on prior models by extending the affiliation space to include exclusive communities. The use of the Lorentz inner product for decoding is a novel move that helps address challenges in previosu approaches. The evaluation (both synthetic experiments, anomaly detection, and link prediction) uses appropriate metrics and baselines. A minor comment is that, additional discussion on scalability (especially for large or sparse graphs) and hyperparameter sensitivity would be valuable.", "theoretical_claims": "The paper provides rigorous theoretical proofs of universality using the log cut distance framework. I checked the proofs for the main theoretical results (Theorems 3.7 and 3.8), and while they are largely convincing, some assumptions (e.g., regarding graph density) might limit their direct applicability to real-world sparse graphs. Clarifications on these limitations would improve the overall presentation.", "experimental_designs_or_analyses": "THe experimental design is thorough, that includes both synthetic and real-world datasets. The comparisons with several baselines in anomaly detection and link prediction are informative. Nonetheless, it would be useful to see more detailed analyses on the model’s performance with respect to computational efficiency and robustness to hyperparameter choices, especially since the training involves simultaneous optimization of node embeddings and a prior.", "relation_to_broader_scientific_literature": "The work is very relevant to the scientific literature.", "essential_references_not_discussed": "A couple of references that are relevant:\n1. Chanpuriya et al. 2020. Node Embeddings and Exact Low-Rank Representations of Complex Networks\n2. Jia et al. 2019.,CommunityGAN: Community Detection with Generative Adversarial Nets", "other_strengths_and_weaknesses": "Strengths:\n– Novel use of community affiliation models to include exclusive communities\n– Theoretical guarantees of universality add significant depth to the contribution.\n– Competitive empirical performant on multiple benchmarks\n\nWeaknesses:\n– The analysis appears more suited to dense graphs; applicability to very large, sparse graphs is less clear.\n– The training procedure (involving simultaneous optimization of node embeddings and the generative prior) might be computationally demanding.\n– Additional experiments on hyperparameter sensitivity and scalability would further strengthen the paper.", "other_comments_or_suggestions": "Check my previous section.", "questions_for_authors": "Check my previous section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m7sC1QYEBm", "reviewer": "Reviewer_WAjU", "summary": "The document presents PieClam (Prior Inclusive Exclusive Cluster Affiliation Model), a novel graph autoencoder that enhances the existing BigClam framework by utilizing overlapping inclusive and exclusive community structures for node representation learning. PieClam introduces a new log cut distance for measuring graph similarity and demonstrates universality in approximating any graph structure with a fixed number of communities, surpassing prior models in link prediction and anomaly detection tasks. Experiments validate the model's effectiveness across benchmark datasets, showing that it achieves competitive performance while offering a generative capability through prior distribution learning in the community affiliation space.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank that reviewer for the positive and in depth evaluation of our paper.\n\n>**Claims And Evidence:**\n>>...further clarity on the implications of using the log cut distance in sparse graphs would enhance the overall argument.\n\n*Response.*  Thank you for this suggestion.  We already shortly discussed this shortcoming in the Conclusion (Page 8):\n\n\"Another limitation of our analysis is that the log cut distance is mainly appropriate for dense graphs. Future work will extend this metric to sparse graphs...\"\n\nbut we agree that this discussion may be too short. **If accepted, we will extend the discussion about sparsity, stating that the analysis is mostly appropriate for dense graphs, but the method is empirically appropriate also for sparse graphs.**\n\nRegarding applicability of the method to real-world sparse graphs, the method was tested against sparse graphs in anomaly detection and link prediction benchmark, where we got competitive performance, demonstrating that the method performs well empirically also for sparse graphs.\n\n>**Theoretical Claims:**\n>> However, further discussion surrounding any assumptions made during the proof processes would strengthen the rigor of this section...\n\n*Response.*  As a principle in mathematical writing, all assumptions are clearly and explicitly stated in the body of the theorem. No additional assumptions are allowed to be taken during the proof, as this would undermine the correctness of the theorem. We believe to have complied with this basic principle. However, if the reviewer found a hidden assumption in the body of the proof, please let us know where specifically this is made so we can fix it. \n\n>**Essential References Not Discussed:**\n>> The manuscript could benefit from including related works that ... explored universal properties of graph representations. .. Works exploring the strengths and weaknesses of using similar graph distance measures in sparse networks should also be cited. \n\n*Response.* We will add paragraphs to the  Extended Related Work appendix about this. We will cite papers about universality of GNNs as functions from graphs to vectors (graph classification or regression). For example:\n\nS. Chen, S. Lim, F. Memoli, Z. Wan, and Y. Wang. Weisfeiler-Lehman meets Gromov-Wasserstein. ICML. 2022.\n\nS. Chen, S. Lim, F. Memoli, Z. Wan, and Y. Wang. The Weisfeiler- Lehman distance: Reinterpretation and connection with GNNs.  Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG ML). 2023.\n\nJ. B¨oker, R. Levie, N. Huang, S. Villar, and C. Morris. Fine-grained\nexpressivity of graph neural networks. NeurIPS. 2023.\n\nL. Rauchwerger, S. Jegelka, R. Levie. Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs. 2025.\n\nWe will also add a short discussion about sparse graph similarity measures that can potentially be used to define a version of log-cut distance appropriate for sparse graphs.  For example:\n\n**Stretched Graphons:** C. Borgs, J. T. Chayes, H. Cohn, and N. Holden. Sparse exchangeable graphs and their limits via graphon processes. Journal of Machine Learning Research. 2018.\n\n**$L^p$ graphons:** C. Borgs, J. Chayes, H. Cohn, and Y. Zhao. A theory of sparse graph convergence i: Limits, sparse random graph models, and power law distributions. Transactions of the American Mathematical Society. 2019.\n\n**Graphings:** L. Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.\n\n**Graphops:** Backhausz and B. Szegedy. Action convergence of operators and graphs. Canadian Journal of Mathematics, 74(1):72–121, 2022.\n\n>**Weaknesses:**\n>> The potential narrow focus on node affiliations without sufficiently addressing node features in edge conditions, which may limit applicability across diverse graph types...\n\n*Response.* First, we already addressed this issue in the Conclusion:\n\n*\"One limitation of PieClam is that, for attributed graphs, it only models the node features through the prior in the community affiliation space, but not via the conditional probabilities of the edges (given the community affiliations). Future work will deal with extending PieClam to also include the node (or edge) features in the edge conditional probabilities.\"*\n\nStill, we often observe in experiments that not using the features can still lead to competitive performance with methods that do use the features. We wrote in section D3 of the appendix on page 25: \n\n*\"Note that, since the prior is not used in classification, there is no added benefit from utilizing node features when training the prior, as\nproposed in 2.4. Therefore, the link prediction algorithm relies solely on the graph’s topological structure and the prior functions only as\nregularization.\"*\n    \n**Nevertheless, we will extend this discussion in the camera-ready version of the paper if accepted.**", "claims_and_evidence": "The claims presented in the manuscript are well-supported by the experiments conducted and the theoretical proofs provided. The authors assert that PieClam can accurately reconstruct graphs and achieve competitive link prediction and anomaly detection outcomes. Evidence for these claims includes:\nComprehensive experimental results on multiple datasets, including Squirrel and Texas, which confirm the model's performance against established baselines such as AA, VGAE, GAT, LINKX, and Disenlink.\nThe introduction of log cut distance, a new metric aimed at quantifying similarity between graphs, which is substantiated by both empirical and theoretical discussions in the paper.\nTheoretical proofs (Theorems 3.7 and 3.8) confirming the universality of the model, indicating its capability to approximate various graph structures efficiently.\nWhile most claims are convincingly backed by data, further clarity on the implications of using the log cut distance in sparse graphs would enhance the overall argument.", "methods_and_evaluation_criteria": "The methods employed in the manuscript, including the structure of PieClam and the evaluation criteria for performance assessment, are appropriate for the problem domain. The authors effectively leveraged benchmark datasets for rigorous testing and comparison, enhancing the robustness of their findings. Specific elements to note include:\nThe incorporation of both inclusive and exclusive communities broadens the model's applicability to various graph types, making it adaptable for real-world scenarios.\nThe use of the Lorentz inner product for decoding, allowing a flexible representation of nodes in the affiliation space, is a strong methodological choice that lends depth to the investigation.\nThe section on experimental design and analyses confirms that the evaluation strategies align well with the objectives of the study, providing a solid foundation for claiming model effectiveness.", "theoretical_claims": "The theoretical claims, particularly regarding the model's universality and the correctness of the proofs, are adequately presented. Notable points include:\nThe completeness of the proofs for Theorems 3.7 and 3.8 highlights the rigorous mathematical grounding of the claims surrounding PieClam’s ability to approximate any graph utilizing a fixed parameter budget.\nHowever, further discussion surrounding any assumptions made during the proof processes would strengthen the rigor of this section and provide additional assurance of the theoretical underpinnings.\nEngagement with these theoretical proofs can help peer reviewers assess the significance and flexibility of the proposed method against existing literature.", "experimental_designs_or_analyses": "The experimental framework and analyses appear sound, demonstrating the validity of the proposed model. Key considerations include:\nThe selection of datasets (such as Squirrel and Texas) is relevant and conducive to assessing graph autoencoding performance across various scenarios.\nDetailed accounts of the experimental setup, including the usage of Nvidia GPUs and the iterative optimization process, enhance reproducibility and clarity regarding the methodological rigor.\nA deeper exploration of potential biases in the datasets or evaluation methods may warrant further scrutiny to ensure the validity of the conclusions drawn.", "relation_to_broader_scientific_literature": "The contributions made by PieClam are significant within the landscape of graph representation learning. The use of overlapping community structures represents a notable advancement from predecessor models like BigClam and continue to resonate with core themes in community detection literature. \nThe model's introduction aligns with recent efforts to refine graph generative models and embed node representation learning in a probabilistic framework. Notably, the discussion of related works supports the authors' claim while presenting a complete narrative on how PieClam fits within the broader scientific discourse.", "essential_references_not_discussed": "The manuscript could benefit from including related works that have addressed the integration of features in graph models or explored universal properties of graph representations. For instance:\nRecent advancements in normalizing flows for better feature representation could establish a clearer context for PieClam's approach.\nWorks exploring the strengths and weaknesses of using similar graph distance measures in sparse networks should also be cited.\nInclusion of these references would provide a more rounded understanding of how PieClam positions itself within contemporary research on graph models.", "other_strengths_and_weaknesses": "Strengths of the paper include:\nThe originality of combining inclusive and exclusive communities to enhance node representation.\nThe clear presentation and methodological framework that makes the findings accessible and reproducible.\nWeaknesses may involve:\nThe potential narrow focus on node affiliations without sufficiently addressing node features in edge conditions, which may limit applicability across diverse graph types.\nA more elaborative discussion on model limitations would be beneficial.", "other_comments_or_suggestions": "A careful proofread of the text could address minor typographical issues observed in sections discussing model evaluations.\nThe authors could consider including additional visualizations to further illustrate the model's capabilities and performance comparisons.", "questions_for_authors": "How do you envision incorporating node features into the edge probability calculations in future iterations of PieClam?\nCould you elaborate on the potential applications of the log cut distance metric for sparse graphs, and your plans for addressing current limitations?\nWhat specific challenges did you encounter during the implementation of the prior distribution learning, and how did you overcome them?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The manuscript introduces PieClam, a graph autoencoder that extends BigClam by incorporating a learned prior over node embeddings, making it a generative model. It also introduces exclusive communities, representing disconnected node groups alongside traditional inclusive ones. Using a new similarity metric, log cut distance, the authors prove PieClam is a universal autoencoder capable of approximating any graph. Experiments on anomaly detection and link prediction demonstrate its strong performance.

The paper is of clear good quality and a solid contribution to ICML.
Decision: Accept (poster)