A Variational Edge Partition Model for Supervised Graph Representation Learning
Authors: Yilin He
Chaojie Wang
Hao Zhang
Bo Chen
Mingyuan Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: probabilistic graph modeling
graph deep learning

Abstract: Graph neural networks (GNNs), which propagate the node features through the edges and learn how to transform the aggregated features under label supervision, have achieved great success in supervised feature extraction for both node-level and graph-level  classification tasks. However, GNNs typically treat the graph structure as given and ignore how the edges are formed. This paper introduces a graph generative process to model how the observed edges are generated by aggregating the node interactions over a set of overlapping node communities, each of which contributes to the edges via a logical OR mechanism. Based on this generative model, we partition each edge into the summation of multiple community-specific weighted edges and use them to define community-specific GNNs. A variational inference framework is proposed to jointly learn a GNN-based inference network  that partitions the edges into different communities, these community-specific GNNs, and a GNN-based predictor that combines community-specific GNNs for the end classification task. Extensive evaluations on real-world graph datasets have verified the effectiveness of the proposed method in learning discriminative representations for both node-level and graph-level classification tasks.

A Variational Edge Partition Model for Supervised Graph Representation Learning
Yilin Hel", Chaojie Wang Hao Zhang', Bo Chen², Mingyuan Zhou 'he University of Texas at Austin, Nanyang Technological University, *Xidian University fyilin.he mingyuan. zhou] @wccombs. utexas edu chaojie wangentu. edu. sg
zhanghao xi di com bchen@mail. htt.mmmmixxxiiaaan xidian edu. cn
Abstract
Graph neural networks (GNNs), which propagate the node features through the edges and learn how to transform the aggregated features under label supervision, have achieved great success in supervised feature extraction for both node-level and graph-level classification tasks. However, GNNs typically treat the graph structure as given and ignore how the edges are formed. This paper introduces graph generative process to model how the observed edges are generated by aggregating the node interactions over set of overlapping node communities, each of which contributes to the edges via a logical OR mechanism. Based on this generative model, we partition each edge into the summation of multiple community -ppecfi weighted edges and use them to define community- speciffcc GNNs. A variational inference framework is proposed to jointly learn a GNN-based inference network that partitions the edges into different communities, these community-specific GNNs, and a GNN-based predictor that combines community-specifie GNNs for the end classification task. Extensive evaluations real-world graph datasets have verified the effectiveness of the proposed method in learning discriminative representations for both node-level and graph-level classification tasks.
1 Introduction
Many real-world entities are bonded by relations, e.g., the users in social network service connected by online friendships, and the atoms in molecules are held together by chemical bonds. Representing the entities by nodes and relations by edges, set of interconnected entities naturally forms a graph. Reasoning about these entities and their relations could be conducted under graph neural networks (GNNs) [T4]. Instead of isolating the feature transformation for each individual entity, GNNs allow the information to be exchanged between related entities. Models employing this strategy have achieved great success in wide range of applications involving graph-structured data, such as classification [S] 6), link prediction 77,, recommendation
g, (overlapping) community
detection [3. and drug discovery [14]
The essence of many graph-analytic tasks could be summarized as supervised graph representation learning, where the information on the graph is usually characterized by the node features, adjacency matrix, and node or graph labels. A supervised machine learning pipeline is often introduced to embed the nodes graph under label supervision for specific classification task. For most of the GNN-based methods, the information on nodes and edges is composited through neighborhood aggregation, i.e., updating the features of each node by combining the features of the surrounding nodes. During this process, the graph structure mostly serves as a given source to indicate the nodes' neighborship
15 or provide the weights for aggregation [ Treating the graph structure as given
Equua contribution. Corresponding authors. Code available at attttps://githuu cww//o- BHEHHHHHUUUHUEEEEEEEEE UMMSUB/MMV
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

overlooks the latent structures that control the formation of the graph, which, however, could provide valuable information for graph representation learning. In other words, failing to consider the latent graph structures may limit the ultimate potential of this line of work.
One type of latent structure the hinge of the graph structure and node information is node communi- -based graph generation
ties. Their connection to the graph can be explained under process. For example, both the mixed-membership stochastic blockmodel (MMSB) [T] and edge partition model (EPM) [ explain the formation of edges by node interactions over overlapping latent communities. Let us consider person u in social network G, some of her social connections may be established through interactions with colleagues as machine learning researcher, some may originate from her interactions with co-members of the same hobby club, and different types of interactions could overlap to strengthen certain social connections between the nodes.
The node community structure also sets the aspects of node information. In the example of social network 9 where person u is affiliated with both a research group and a few hobby groups, due to the diverse nature of these different communities, is likely that she exhibits different characteristics when interacting with co-members of different communities. Namely, the information on u for the research group may be related her research expertise, and the information on u for the hobby clubs may be related to her hobbies. Therefore, an ideal solution is to learn a different aspect of node properties for each community that it is affiliated with, and represent the overall node information as an aggregation of all community
node properties.
Based this insight, we develop a variational edge partition model (VEPM), which is generative graph representation learning framework. VEPM models how the edges and labels are generated from overlapping latent communities. Instead of hard assigning node single community, VEPM encodes each node into a K --dimensional vector of scores measuring the strength that the node is affiliated with each of the K communities. From these scores, we compute the intensities of pairwise interactions within each community. Given that information, under the Bernoulli-Poisson link, the edges could be modeled by the logical OR of independently generated binary latent edges .
The generation of labels includes A key premise of the first part is to detect the hidden structure specified for each community. In our model, it is achieved through edge partition, i.e., decomposing each edge into a summation of link strengths according the intensities of community-specift interactions. The edge partition step isolates the link strengths accumulated through each community. With the partitioned edges, we learn K separate GNNs to produce community-spen
crammunity-speciffe node representation learning and aggregation.
node representations, then compose them into the overall node embeddings to generate the labels. Evaluation shows that the proposed framework can achieve significant performance enhancement on various node and graph classification benchmarks.
We summarize our main contributions as follows:
We introduce VEPM that utilizes the idea of edge partitioning to extract overlapping la- tent community structures, which are used to not only enrich node attributes with node- community affiliation scores, but also define community-speccffi node feature aggregations.
We formalize the training of VEPM in variational inference framework, which is powered by GNNs in its latent community inference. representation generation, and label prediction.
We analyze how VEPM works and evaluate it over various real-world network datasets. Empirical results show that the proposed VEPM outperforms many previous methods in various node- and graph-level classification tasks, especially with limited labels.
2 Preliminaries and Related Work
Embedding nodes and graphs with GNNs. Given a node-attributed graph G with N nodes, its information is generally expressed by a design matrix X E RNNx FF, whose rows represent node features of dimension F, and adjacency matrix A of shape N x N. The nonzero values of A indicate the weights on the corresponding edges. GNNs 15 15 16] are multi-layer parametric models that maps (X, A) to the embedding space. The update of the embedding of node u at A..)) and (0 X,- Here AGG denotes the neighborhood aggregation function, N(u) denotes the neighbors of u, and fo(-) is transformation function parameterized with O. In VEPM, we adopt
the ith GNN layer could be summarized as (t) = AGG (o (""),

---

the aggregation function introduced by Kipf and Welling (5), which can be expressed as h. EvetojuN(w) fo (h!!"))) where À is the normalized adjacency matrix of g augmented with self-loops. When the task requíres a graph-level representation, all node embeddings would be summarized into a single embedding vector. This process is called graph pooling [17.19]. In this work, we focus on improving the overall performance from GNN's perspective and adopt a simple graph pooling method proposed by Xu et al. [6]. In the sequel, we unity the expression of models consisting of GNN layers as GNN X, A).
Community- -regulaiiz representation learning. Communities are latent groups of nodes in graph 220] The simplest way to use community information help a supervised learning task is related task. For instance, Hasanzadeh et al. [21] and Wang et al. [22 jointly train deep stochastic blockmodel and classification model; similar approach could be found in Liu et al. [23], where the graph reconstruction regularizer is replaced by a modularity metric. Fither way, the node embeddings are expected to reflect patterns of community structures and maintain informative to the task at the same time. These methods generally treat node-community affiliation as node embeddings and expect them to contain sufficient information for the downstream task. However, the affiliation strengths of nodes to community may oversimplify the information that such a community can provide for the downstream task. Unlike these methods, VEPM embeds node information each community with specific GNN, where the community structures are reflected by the partitioned adjacency matrices. Aggregating node features with these weighted adjacency matrices naturally incorporates community information into task-learning
to regularize it with a community-detectiin
Multi-relational data analysis. Leveraging heterogeneous relations has been extensively studied in the literature of mining Knowledge Graphs 264 The data of these models is usually organized by a multigraph, which is related to our perspective of the latent node interactions that generate the observed graph because the interactions in different communities
potentially heterogeneous, and they are permitted to coexist between a pair of nodes. This leads to a shared high-level idea to break down the original heterogeneous graph into homogeneous factors and analyze each factor with customized model. However, unlike those multigraphs where the edge types are explicitly annotated, the overlapping heterogeneous node interactions not observable from the data that VEPM aims to handle, escalating the difficulty of our optimization problem. To deal with the latent variables, we formalize VEPM into generative model and train it via variational inference.
Graph factorization- models. The existence of multiple hidden structures in graphs is also noticed by some previous work (27 28). The architecture of these models starts with graph factorization, followed by a set of modules with each one processing the information from one of the graph factors. In these methods, the only ground-truth information that trains graph factorization is from label supervision, making them rely on excessive label annotations, which might be hard to suffice in practice and thus potentially hinder their application. On account of the potential heterogeneity of graph information on different communities, VEPM adopts a similar pipeline to these methods, but the factorization of the original graph is driven by not only the supervised task but also a graph generative model, which greatly reduces our dependency on the amount of labeled data.
3 Variational Edge Partition Model
Many analytical tasks on node-attributed graphs could boil down to (semi-) supervised classification problems, i.e. given (X, and observed node or graph labels yo. predicting the unobserved labels ya. In VEPM, we formalize the classification task as modeling the predictive distribution as ply.. X, A, yo), and construct our variational supervised learning pipeline with GNNs.
3.1
Generative task-dependent graph representation learning with latent communities
To model p(ya X, A. yo). we introduce Z R.NKK a latent non-negative codm-ntmmunity affili- ation matrix, whose entry at the nth row and kth column is interpreted as the strength that the nth node affiliated with the kth community. Given Z, we specify a generative network as
A ~ (A Z), yo po X, Z)
to describe how the observed edges A and labels yo are generated. Due to the complexity brought by the deep architecture of the generative network, analytically inferring the posterior of Z is impractical.
3

---

X
Ex
2
The Inference Network
GNW
K
H
z'
Output
GANN
H
GNN
GNN
community encoder
edge partitioner
community-GNN bank
regresentation componer
Figure The overview VEPM's computation graph. The input data successively passes four modules described in Sections [.2] and 3.3 the community encoder, edge partitioner, community- GNN bank, and representation composer. Node information is processed community-wiss by the edge partitioner and the community- GNN bank. The former factorizes the original graph into set of weighted graphs by the relative inter-node interaction rates across communities; the latter performs neighborhood aggregation with the factorized graphs, such that in each community, nodes exchange more information with intensively interacted neighbors. Hence the obtained node representations are community-specffcc Please note that we use the transposed notation for Z and node embeddings in this diagram, the concatenations are along the vertical direction. Solid and dashed arrows indicate network forwarding and gradient back- pock-propagation, respectively.
We hence approximate the posterior (Z A.) with a variational distribution, (Z X), modeled by a separate GNN-basee inference network. The subscripts and denote the parameters in the generative network and inference network, respectively. We illustrate the architecture of VEPM in Figure 1 We approximate the posterior predictive distribution using the Monte Carlo method as
(y n X, A. yo) E X. A, Z()),
po
where (() sid g (Z A) for
In what follows, we outline the data generation process and corresponding modules in the generative network, introduce the module in the inference network, and describe how to train both networks.
3.2 Edge generation and label prediction
To model the distribution of the edges given Z, we adopt the generative process developed in EPM (II). which explains the generation of the edges under the Bernoulli-Poisse link as A =
k= 1>=1> Z..., Here 7/k is positive community activation level indicator, which measures the member interaction frequency via community and in our practice is treated trainable parameter shared by both the inference network and generative network. We interpret x, as the interaction rate between nodes and j via community k.
21, 21, Mij ~ Poisson
The EPM has an alternative representation that partitions each edge into the logical disjunction (i.e., logical OR) of K latent binary edges (29), expressed
Ai
VK Ar Ai.,A- Bernoull(pyga);
where Piyk := 1- e 2,, Thus nodes and j would be connected as long as their interaction forms an edge in at least one community. In other words, they are disconnected only if their interactions in all communities fail to generate any edges. Under the EPM, we have the conditional
probability as pa (Ai 1 l - K 22,, To complete the model, we the prior distribution of the
affiliation matrix as Z II I Gamma(Zi,es a, 3)).
Given A and Z, we now describe the predictive process of the labels. The node-community affiliation impacts this process from two aspects: for each node, the corresponding row of Z serves as side information that could enrich node attributes; for each pair of connected nodes, it could be used to derive the node interactions rate via each community, i.e., ( 7... / k=1,K, which are further used to partition the edges into K communities, carried out by the edge partitioner:

---

Edge partitioner. The edge partitioner takes edges A and node-community affiliation matrix Z as , inputs and returns K wesitiv edges: (A(1, , (K)), s.t. 1tt A (K) A. The edge partition finction is
(2,22,22222//
A Aij EN E E {I,.... (L. N}.
(3)
where T is a "temperature" " that controls the sharpness of partition.
The effect of the edge partitioner could be considered as a soft assignment of each edge into different communities. Setting temperature to be low could drive the soft assignment towards hard assignment, and consequently, when aggregating node features with (A(), A ..... A (K)). }. the edge partitioner would concentrate the information exchange between any two connected nodes at one community. In other words, the mutual influence between two nodes, measured by the edge weight, is relatively high in the community that contributes the most of the interactions between the pair, while being relatively weak in the other communities.
In our implementation, we further generalize Equation (3) to a metacommunity- -baed edge partition, specifically, by replacing Mi Z.. with Zi diiag()))))) Z j.a- In the new expression, Zi,e denotes the kth segment in node i's community-affiliatoo encoding, T/: is vector of the activation levels for communities in the kth metacommunity. This generalization allows the total number of communities to be greater than K, enhancing the model implementation flexibility at minor interpretability cost.
The edge partitioner provides a soft separation of the neighborhood aggregation routes for each community, which is passed to the community- GNNN bank:
= || Z as input, where the operator || denotes "concatenation." " and learns community-spent specific node embeddings with K separate GNNs, i.e., the out- puts are gg (X*), go (X*),
GGN bank. The module takes X= X
(K) (X*), where Eg (.) == GNN (+)).. k (1,..., K}.
8g
The intention of the edge partitioner and Community-GNN bank to capture the node information specific each community. For instance, social network, such kind of information could be the different social roles of people when considered affiliated with different social groups, e.g., one may be a former computer science major student in an alumni group, research scientist in work group, and an amateur chess player in hobby club group. As shown in Section 4.3 the node embeddings produced by the community- GNNN bank are separable by communities.
We finally introduce the representation composer, which embeds a combination of the information provided by each community into global representation via GNN:
(k) (X') denote the node representations learned from the Representation composer. Ler H = ge
kth community, where i = .....,.. ,, K, and f (.) denote the representation composer, whose functional- ity is to project a composite of community-specife node representations to one representation matrix, ie., Hy= 5 ((2)) ... H(K)) == GNN, (IK A)
For graph-level tasks, we further pool node embeddings into a single vector representation hgg in Xu et al. (6) Taking softmax probabilities of labels, from which we are able to classify the unlabeled objects. Cascading the edge partitioner and communityGNN bank with the representation composer yields the probability po(y X, A, Z).
the feature dimension of Hy or he gives the predicted
3.3
Variational latent community inference
We community encoder as the module in the inference network approximate the posterior distribution pe (Z) y) and provide the generative network with the critical latent variable Z:
Community encoder. The community encoder models the variational posterior qo (Z A. X) by Weibull distribution with shape K and scale A, whose parameters are learned by GNN as K || A = GNN (X, A). A Weibull random sample from 9 [Z) A, X) could be created through the inverse CDF transformation of a uniform random variable, given as follows:
Z = A (- log(1 - U)) .U.. sid U(0.1), V(ik) (1....,NY (1...., K}. (4)
where 3 and 2 denote element-wise multiplication and division.
5

---

3.4 The overall training algorithm and complexity analysis
We train VEPM by optimizing the evidence lower bound (ELBO), decomposed into three terms, as (5)
L = Lrask + Legen + LKI.;
where Crask Busl (Z) A.X) log (y / A, X),, Legen gg (2 A.X) legpe(A (A Z), and CKL
-DKL (go A,X) p(Z)). These three terms correspond to the classification task, edge genera- tion, and KL-reeularizzttoon respectively, Note that our specifications of Z's ss prior and variational posterior yield an analytical expression of LKL,, as described detail in Appendix B
Recall that N. M, K denote the numbers of nodes, edges, and communities (or metacommunities) in the graph: F' denotes the feature dimension; and L1, L2, L3 denote the number of layers in the community encoder, in the Saammmitty-GNy bank, and in the representation composer. In VEPM, we limit the size of hidden dimension in each community-GNe to 1/K of what is commonly used among the baselines, hence the time complexity of training VEPM is ((L + L2 + MM F + [L1 + "2/K L3) L3)N 22 + F). For a sparse graph where N2 > M, the computational overhead can be reduced to (MM) if graph reconstruction is accelerated via subsampling the nodes to (VVM) M), as in Salha et al. 30 Effects and implications of adopting such type of acceleration algorithms are discussed in L + +L1++>/ Lg) F²)) among which O((L) + Lz/K + L²) is contributed by model parameters. It is noteworthy to point out that the memory cost of graph reconstruction manageable by computing the dense matrix multiplication block-wits twiee with fixed maximum block size. From all aspects of complexity. VEPM (with acceleration) is comparable to GATs 15 31 and models involving graph factorization [27 28
Appendix A The space complexity of VEPM is +
Empirical Evaluation
4.1 Node & graph classification
Datasets & experimental settings. For node classification, consider three citation networks (Cora, Citeseer, and Pubmed) and Wikipedia-based online article network (WikiCS) (32), which provide either bag-of-words document representations or average word embed- dings node features, and (undirected) citations or hyperlinks as edges; For graph classification, we consider four bioinformatics datasets (MUTAG, PTC, NCII, PROTEINS) and four social network datasets (IMDB- REDDIT-MULTI, The imput node features are crafted
Table 1: Comparison of node classification performance.
Method
Cora
Cifeseer
Pubmed
WikiCS
ChebNet
81.2
69.8
74.4
GCN [5]
81.5
70.3
79.0
74.0 4: 1.0
GCN-64
81.4
70.9
79.0
SIG. VAE. 21
79.7
70.4
79.3
WOCAE 22
82.0
72.1
79.1
GAT 15
83.0
72.5
79.0
77.6 F 0.6
hGANee B1
83.5
72.7
79.2
DisenGCN 27
83.7
73,4
80.5
VEPM (this work)
84.3
1
0.1
72.5
1
0.1
82.4
1.
0.2
78.7 0.6
BINARY, IMDE-MULTI, in the same way as Xu et al. O Most of the baselines are compared following the 10-fold cross- validation- based evaluation protocol proposed by Xu et al. (). For the graph classification task, we also evaluate our model following Zhang and Chen K which conducts a more rigorous train- validation-test protocol. More details about the experiments are elaborated in Appendix C.2
Node classification. We use classification accuracy as the evaluation metric for node classification. Table [ reports the average performance of VEPM (# standard error) against related baselines that are categorized into three different groups The first group consists of the GCNs [5] and its variant GCN-64, which expands the hidden dimension from 16 to 64. VEPM outperforms the first group by significant margin. The explanation is twofold: (i) VEPM augments the node attributes with community information carried by the inferred node-community affiliations, (ii) VEPM learns community- community-specifii speeiicc node embeddings. The second group includes SIG-VAE [11 and WGCAE [22]. both of which learn node embeddings from graph generative models jointly optimized with a supervised loss. The performance gain that VEPM obtains could be attributed to our unique label predictive process, which not only appends extra community information to node attributes but also injects structural patterns of communities into neighborhood aggregation. The third group [15 31 27] is focused on learning node embeddings leveraging heterogeneous hidden relations. When fitting the hidden relations via the attention mechanism, they only use information from the node features
? For expression simplicity, the scale of F' is treated constant, which is ubiquitous in practice.

---

Table 2: Comparison of graph classification performance (average accuracy + standard error).
Method
IMDB-B
IMDB-M
MUTAG
PTC
NC11
PROTEINS
RDT-B
RDT-M
WL subirce 34
73.8 1: 3.9
50,9
1 3.8
90.4 5.7
59.9 1 4.3
86.0 1 1.8
75.0 1 3.1
81001
52.5 2.1
PATCHYSAN
35
710
45.2
2.8
92.6.44
86.3 4 1.6
49.1
AWE
36
5.5
51.5
336 3.6
879
87.9
54.7
GAT
47.8 2.3
8.14
66.7
60.8 2.5
70.5+:3.6
24.4
IGANet
31
49.0
90.0
65.0
78.7
GIN
5.11
52.3
894 5.6
64.6 + 7.0
82.7 1.6
76.2 + 2.8
92.4 + 2.5
57.5
R-GCN
25
8.3
61.8 = 13.2
CompGCN
89.
12.0
FactorGCN
28
75.3
51.0
89.9
74.3 = 8.9
76.4 2.1
74,2 + 4.6
90.0 + 1.2
46.5 + 2.1
VEPM (this work)
76.7 3.1
2.11
93.
5.9
83.9
80.5 -
90.5 + 1.8
55.0
Table 3: Graph classification accuracies under the protocol by Zhang and Chen
33
Method
IMDB-B
IMDB-M
MUTAG
NCI1
PROTEINS
RDT-M
subtree 34
13.4 4466
49.3
4.8
82.1 10.4
82.2 10022
74.7 10.3
19.4
DGCNN
-0.
09
+1.7
74.4 +0..5
75.5 +0.9
48.7 44.5
GCAPS CNN
38
71.7 134
48.5
4.1
82.7 L2.4
76.4 14.2
50.1 11.7
CapsGNN [33
50.3
86.7
26.9
78.4
73,66
52.9
VEPM (ibis wurk)
74.612
50.6
336
1.33
8L7
76.8 1 4.1
50.2
2.1
through label supervision, whereas our approach also takes the observed graph structure into account via a graph generative model. The additional information from the graph utilized by VEPM could explain the enhancement achieved by VEPM over the third group.
Graph classification. For the first protocol, we compare VEPM with classical graph classification baselines [34 generic- GNN- based models [IS 31 6). and GNNs with relation- based or task-
driven graph factorization 25 26 28). Results in Table 2 show that VEPM achieves the best graph classification performance on 5 out of 8 benchmarks, and the second-best performance on the other benchmarks, including NCI1, where VEPM outperforms all the other GNN-based models.
For the second protocol, aside from traditional method. WL 34 and a Ceveric-GNN-bae method, DGCNN (37), we compare VEPM with two GNNs [38
33 that adapt capsule neural networks 39 to graph-structured data, which aim to learn different aspects of graph properties via dynamic routing [4). The results in Table show that VEPM outperforms these GNN-based methods on most of the benchmarks. This indicates that the aspects of graph information, as defined with communities and learned via aggregating node features with partitioned graphs, are more pertinent to the end tasks.
Classification with reduced labels. The gain of incorporating the graph generation process into VEPM is that the observed graph structure also provides information for hidden community detection and edge partition, which is beneficial if the amount of labeled data is not sufficient for both de- composing the graph into hidden factors and semi- cemi-super task-learning. To il- lustrate this point, based on the evaluation protocol by Kipf and Welling 5 for node classification and Xu et al. 6 for graph classification, we re-evaluate the performance of VEPM under reduced training labels on Cora (for node classification) and MUTAG (for graph classification), along with generic-GNy Beriic--N--aae based methods 15 [6] and decomposition based methods [27 (2). The results are shown in Figure 2 the perfor- mance of all models is negatively impacted by the reduction in training labels, those suffering from the strongest performance decline are DisenGCN 2 and FactorGCN (28 that decompose graphs solely based label supervision, while VEPM also performs graph factorization with limited labels, it consistently outperforms the other methods under all settings, and the superiority becomes even more evident as the amount of annotated data further decreases. We consider the enhanced robustness under sparsely labeled data as crucial feature to have for real-world graphs.
Figure 2: Node classification accuracy on Cora (left) and graph classification accuracy on MUTAG (right) as the num- ber of labels decreases. The horizontal axis is the keep rate of labels the training set under corresponding protocols.
4.2 Ablation Studies
Different edge partition schemes. In this part, we study how much a meaningful edge partition would benefit the task. Except for the partition we obtained from training the regular VEPM, we tested the performance of VEPM under two edge partition schemes: even partition and random partition. Even partition means all edge weights are l/k. For random partition, we sample the unnormalized
7

---

edge weights from UO. 100), then normalize them along the community dimension with softmax. The random edge weights are fixed for training to simulate an undesirable convergence state of edge partition. The results are recorded in Table Generally speaking, the performance of VEPM with even edge partition comparable to that of GIN, our base model; when we substitute random partition for even partition, the model performance becomes worse than the base model. These ablation study results suggest that VEPM can benefit from enhancing the quality of edge partitions.
Table 4: The performance of VEPM with different edge partition schemes.
Method
IMDB-B
IMDB-M
MUTAG
PTC
PROTEINS
VEPM (even partition)
14,2=4.3 4.3
51.4 2.7
90.4
66.3 6.6
76.3 =
VEPM (random partition)
60.5 4.7
41.1 1.5
61.8 118=40 4.0
62.7 3.8
75.1
52.3
89,4
64.6
76.2
VEPM
76.7 3.1
2..1
75.6 5,9
80.5 2.8
Different represeniation composer. Next, we use the partition obtained from a regular VEPM to represent partitions that are meaningful for the task, and random partition to represent "meaningless partitions." For each partition scheme, we contrast the performance of VEPM between two designs of the representation composer: (i) GNN-based design, represented by the current design: (ii) par- simonious design, represented by a fully-connected (FC) layer. The results are in Table 5 When the edge partition is meaningful, i.e., relevant to the task, the overall performance with a simpler representation composer is generally slightly worse than the current design, but still better than most of the baselines. However, the partition is irrelevant to the task, the GNN-based representation composer would be the last thing standing between the model and failed task, as the graph structure used for neighborhood aggregation is still informative to the task. So the current design would slightly benefit VEPM in general case and protect the performance of the model in the worst-case scenario.
Table 5: The performance of VEPM with different designs of the representation composer.
representatio composer design
IMDB-B
IMDB-M
MUTAG
PTC
PROTEINS
GNs-b
7..
2.11
80.5288 5. 33
meuningful partition
FC-
74.6 3.4
$1.6
90.3 4.2
68.7
76.7 +
GNN-based
60.5 4.7
41.1
814
4.0
3.8
random partition
FC-based
4 3.8
2.0
7.66
5.95
59.8 3.9
Different edge partitioning temperatures. We use the same way as the previous study to get meaningful and random partitions, In this study, we focus on the effect of different selections of T, the temperature parameter of softmax. The value of r controls the sharpness of the partitioned edge weights, i.e. small r drives the partitioned weights for the same edge towards one-hot vector, whereas large T would eliminate the divergence among the edge weights and make the edge partition no more different from an even partition. The results of this experiment are recorded in Table 6, the upper half of which is obtained from a meaningful edge partition, and the lower half is obtained from random edge partition. We can induce from these results that when the basis to perform edge partition, namely, the inferred latent node interactions, is relevant to the task, a sharp edge partition that highlights the differences among the communities may be helpful for the task. Otherwise, a smooth edge partition might be more favorable.
Table 6: The performance VEPM with different selections of 7.
0.1
==1
10
== 100
T= 1000
meaningful partition
MUTAG
93.6143
93.6 3.4
91.61
90.8 92.6163
PTC
555
7,
74.7
69.66.4 66
PROTEINS
78.5
80.5
79.2 2.4
77
2.7
MUTAG
7.9
84.5 5..
87.7
554
898 4.6
random
partition
PTC
60.1 1488
61.8
4.0
6..5
64.6 1.55
64.6
65.2 4.9
PROTEINS
64.8
4.4.
62.7 = 38
68.7 2.77227
71.7
73.3 = 2.7
4.3 Qualitative analysis
Visualizing community structures. To show that through partitioning the edges, VEPM identifies each latent community from the original graph, in Figure 3] we plot the adjacency matrices of 200-node subgraph of Cora, before and after edge partition. The subgraph is created via breadth-fin first search 41 node selection to ensure connectivity. We sort the nodes sample S in order to present a clearer view of the community structures. Specifically, we prepare buckets; for node u, we compute the total interactions it engages under metacommunity & by Ma,k := Eves Zdigg (Tx )Z k and assign it to bucket K', where k' arg max; k- We first sort the buckets by descending their counts
8

---

(b) A (1)
(2) (c) Ag
(d) A
(c) A
(a) As
( (8)
(g) A (6)
(h) A
(i) A
Figure 3: S is connected subgraph of 200 nodes sampled from Cora with adjacency matrix As visualized (a). (b)-(i) are outpuls from the edge partitioner. Brighter color represents larger edge weights. clearer visualization effect, we enlarge the bright spots in (b)-() by 9 times.
(a) Z. Cora
(b) Z, MUTAG
(c) Eg (X'), Cora
(d) Eo (X'), MUTAG
Figure 4: t-SNE visualization of Z obtained from unsupervised pretrain on (a) Cora and (b) MUTAG, as well
community- -speciffc node embeddings obtained during supervised finetune on (c) Cora and (d) MUTAG.
of assigned nodes, then sort the nodes within bucket k, k E (I,...,A., K}. by descending value of M., The Z used for sorting is sampled the end of training.
The community structures that VEPM detects could be found in Figure 3a as the blocks on the main diagonal. The fact that most of the bright spots (i.e., edges) are located in these on-diagonal blocks reflects dense node connections internal to each community. Sparsely distributed off-diagonal spots provide evidence of overlapping membership between the communities, which is also taken into account by our graph generative model. Figures 3b to 3i show that the edge partitioner has done sound job in separating latent communities. Due the limited size of the subgraph, some small metacommunities may not contain any large-weighted edges between the nodes in this subgraph, which accounts for the appeared emptiness in Figures 3h and 3i Such kind of artifact disappears when we replace the subgraph by the full graph of Cora, as visualized in Figures 6 to 14 in Appendix G
Visualizing latent representations. The previous visualization experiment verifies the following propositions: (i) the identified hidden structures are latent communities, and (ii) the partitioned graphs are different from each other. We now study how they benefit representation learning. Cora and MUTAG are selected as the representatives for node and graph classification benchmarks. For the MUTAG dataset, we remove graphs that contain node categories with less than 5 instances (less than 10 from a totality of 188) and randomly sample 10 graphs for the visualization experiments.
We first visualize Z obtained at the end of the unsupervised pretrain stage (Figures 4a and 4b)) where the node-community affiliation vectors are projected to 2-D space via t-SNE [42]. Proposition (i) ensures that the node information carried by Z is about communities. We color code the scatters by node labels, both Figures 4a and 4b exhibit a strong correlation between the spatial clusters and colors, which indicates that even without label supervision, the node information provided with Z has discriminative power on classifying nodes.
We then visualize the community ceanmunnty-ssecfficccc node emebddings obtained at the end of the supervised finetune stage (Figures 4c and 4d). Similarly, t-SNE is adopted to reduce the dimensionality of obtained node embeddings. This time we color code the scatters by the latent metacommunity they correspond to. Both Figures 44c and and[4d]exx exhibit clear boundaries between the colored clusters, which show that the model is able extract di different information from multiple communities, which enhances the overall expressiveness of learned node or graph representations and potentially leads to better model performance on the downstream tasks.

---

4.01
2000
940
4504
Figure 5: The 10-fold cross-validation results of using node representations learned from each the eight communities for node classification, expressed in the format of normalized confusion matrices. The cell at the intersection of the ith row and jth column is the percentage of (missslassisication that predict the label of an ith class node j. A darker shade indicates higher (missclassification rate. Please note that the same color for different confusion matrices may correspond to different values.
5 Exploratory Studies
Task-relevant communities. We assess the relevance of the learned communities to the task from an experiment on the Cora dataset. In order to see the statistical dependency between communities and the task, we first hard-assign each node to the community of the highest affiliation strength, then we compute the normalized mutual information (NMI) between the hard tard-paatiioneed communities and node labels. NMI is a score between 0 and I, with higher values indicating stronger statistical dependencies between two random variables. In the above experiment, we obtain an NMI of 0.316 when the communities are learned solely by the unsupervised pretrain, such value increases to 0.322 after the supervised finetune. The results of this experiment show that the initial communities we obtained from the unsupervised pretrain are meaningful to the task, and the relevance between the inferred communities and the task would be enhanced by the supervised finetune.
Diverse community-speciffe information. To see the effect of the information provided by different communities, we first train VEPM until convergence, then use the node representations learned by each community GNN to train an SVM and visualize the averaged 10-fold cross-validatie by confusion matrix. With the results shown in Figure S we can further conclude that most of the communities can provide task related information, as we can observe from Figure 3 that the diagonal cells in most of the confusion matrices have darker shades than off- off-diagonal cells. Beyond that, the information extracted from different communities is complementary to each other. For example, in the second column of Figure 5] information from the upper community can separate classes 3 and 4 well, but would mix classes and 5; information from the lower community, on the other hand, can separate classes 4 and 5 but works worse separating classes 3 and 4.
results
The working mechanism of VEPM. In summary, the communities learned by VEPM have the following properties: (i) the communities are relevant to the task; (ii) the information provided by different communities is complementary. so the overall amount of information for the task is accumulated over communities. Both properties are intuitively helpful for the downstream task.
6 Conclusion
Moving beyond treating the graph adjacency matrix as given, we develop variational edge partition models (VEPMs) to extract overlapping node communities and perform community-specifi node feature aggregations. Specifically, we first utilize GNN-based inference network to obtain node- community affiliation strengths, with which we augment node attributes and partition the edges according to the intensities of node interactions with respect to each community. We learn GNN- based node embeddings for each community by aggregating node features with the corresponding partitioned graph, and aggregate all community-specific node embeddings for the downstream tasks. Extensive qualitative and quantitative experiments both node-level and graph-level classification
10

---

tasks are performed to illustrate the working mechanism and demonstrate the efficacy of VEPMs in supervised graph representation learning.
Acknowledgments
Y. He and M. Zhou acknowledge the support of NSF IIS 1812699 and 2212418, and the Texas Advanced Computing Center (TACC) for providing HPC resources that have contributed to the research results reported within this paper. Besides, this work was supported in part by the National Natural Science Foundation of China under Grant U21 B2006; in part by Shaanxi Youth Innovation Team Project; in part by the 111 Project under Grant B B18039; in part by the Fundamental Research Funds for the Central Universities QTZX22160.
References
[1] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabricle Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
[2] Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions Neural Networks, 20(3):498-55 511, 2009.
[3] James Atwood and Don Towsley. Diffusion-connvlutionaa neural networks. Advances in neural information processing systems, 29, 2016.
[4] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems (NeurIPS), volume 29, 2016.
[5] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
[6] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations (ICLR), 2019.
[7] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.073000 2016.
[8] Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph collabo- rative filtering. In Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval, pages 165-174, 2019.
[9] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. LightGCN: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development Information Retrieval, pages 649,,64,465 2020.
[10] Edo M Airoldi, David Blei, Stephen Fienberg, and Eric Xing. Mixed membership stochastic blockmodels. In Advances in Neural Information Processing Systems (NeurIPS), volume 21, 2009.
[11] Mingyuan Zhou. Infinite edge partition models for overlapping community detection and link prediction. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 38 of Proceedings of Machine Learning Research, pages 1135-1143, 2015.
[12] Fan- Yun Sun, Meng Qu, Jordan Hoffmann, Chin- Wei Huang, and Jian Tang. vGraph: A generative model for joint community detection and node representation learning. In Advances in Neural Information P Processing Systems (NeuriPS), volume 32, 2019.
[13] Nikhil Mchta, Lawrence Carin, and Piyush Rai. Stochastic blockmodels meet graph neural networks. In International Conference on Machine Learning (ICML), pages 4466-4474, 2019.
[14] Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. GraphAF: a flow-based autoregressive model for molecular graph generation. In International Conference on Learning Representations (ICLR), 2020.

---

[15] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liō, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICIRR), 2018
[16] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
[17] Hao Yuan and Shuiwang Ji. Structpool: Structured graph pooling via conditional random fields. In International Conference on Learning Representations (ICLR), 2020.
[18] Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling, In International Conference on Learning Representations (ICLR), 2020.
[19] Amirhossein Nouranizadeh, Mohammadjavad Matinkia, Mohammad Rahmati, and Reza Safabakhsh. Maximum entropy weighted independent set pooling for graph neural networks. arXiv preprint arXiv:2107.01410 2021.
[20] Jure Leskovec, Kevin Lang. Anirban Dasgupta, and Michael W Mahoney. Statistical properties of community structure in large social and information networks. In Proceedings of the 17th international conference on World Wide Web, pages 695-704, 2008.
[21] Arman Hasanzadeh, Ehsan Hajiramezanali, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. Semi-implicit graph variational auto-encoders. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, pages 10711-10722, 2019.
[22] Chaojie Wang, Hao Zhang, Bo Chen, Dongsheng Wang, Zhengjue Wang, and Mingyuan Zhou. Deep relational topic modeling via graph Poisson gamma belief network. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
[23] Yanbei Liu, Qi Wang, Xiao Wang. Fang Zhang, Lei Geng, Jun Wu, and Zhitao Xiao. Community enhanced graph convolutional networks. Pattern Recognition Letters, 138:462-466 468, 2020.
[24] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11-33, 2015.
[25] Michael Schlichtrrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference (ESWC), pages 593-607. Springer, 2018.
[26] Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition- based multi-relational graph convolutional networks. In International Conference on Learning Repre- sentations (ICLR), 2020.
[27] Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. Disentangled graph convolu- tional networks. In International Conference on Machine Learning (ICML), pages 4221, 2019.
[28] Yiding Yang. Zunlei Feng, Mingli Song, and Xinchao Wang. Factorizable graph convolutional networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 20286-20296, 2020.
[29] Mingyuan Zhou. Parsimonious Bayesian deep networks. Advances in Neural Information Processing Systems. 31, 2018.
[30] Guillaume Salha, Romain Hennequin, Jean- cann-Bapistt Remy, Manuel Moussallam, and Michalis Vazirgiannis. FastGAF: Scalable graph autoencoders with stochastic subgraph decoding. Neural Networks, 142:1-19, 2021.
[31] Hongyang Gao and Shuiwang Ji. Graph representation learning via hard and channel-wise attention networks. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 741-749, 2019.
12

---

[32] Péter Mernyei and Cätälina Cangea. Wiki-cs: A wikipedia-based benchmark for graph neural networks, arXiv preprint arXiv:2007.02901, 2020.
[33] Xinyi Zhang and Lihui Chen. Capsule graph neural network. In International Conference on Learning Representations (ICLR), 2019.
[34] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mchlhorn, and Karsten M Borgwardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[35] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning (ICMI), pages 2014- 2023, 2016.
[36] Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International conference on machine learning (ICML), pages 2186-2195, 2018.
[37] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[38] Saurabh Verma and Zhi-Li Zhang. Graph capsule convolutional neural networks. arXiv preprint arXiv: 1805, 080900000000..008 2018.
[39] Geoffrey E Hinton, Alex Krizhevsky, and Sida D Wang. Transforming auto-encoders. In International conference on artificial neural networks, pages 44-51. Springer, 2011.
[40] Sara Sabour, Nicholas Frosst, and Geoffrey Hinton. Dynamic routing between capsules. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[41] Edward Forrest Moore. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching, pages 285-292 Harvard University Press, 1959.
[42] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of machine learning research, 911)), 2008
[43] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. Proceedings the Intelligence, volume 35, pages 11015-11023, 2021.
the AAAI Conference on Artificial
[44] Hao Zhang, Bo Chen, Dandan Guo, and Mingyuan Zhou. WHAI: Weibull hybrid autoencoding inference for deep topic modeling. In International Conference on Learning Representations (ICLR), 2018
[45] Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. Proceedings of the 2014 conference on empirical methods natural language processing (EMNLP), pages 1 1333, 2014.
[46] Dongkwan Kim and Alice Haeyun Oh. How to find your friendly neighborhood: Graph attention design with self-supervision. International Conference on Learning Representations (ICLR), 2021.
[47] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. International Conference on Learning Representations (ICLR), 2020.
[48] George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1):359-392, 1998.
[49] Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and normalized cuts. In ACM SIGKDD international conference Knowledge discovery & Data data mining (KDD), pages 551 551-556, 2004.
[50] Paul Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 102:110-137,, 1983.
13


Reviews:
[{"review_id": "n_cq8JemsJ", "reviewer": "Reviewer_ZMJP", "summary": "This work proposes a novel variational auto-encoder that learns to separate the graph into different communities, and then perform a graph learning task by aggregating over those separate inferred community subgraphs. \n\nThe model works by learning a variational distribution for a node affiliation matrix, which essentially says how affiliated a node is with each community. From that, edges are are sampled using a poisson distribution based on how well adjacent nodes' affiliations overlap. The edges are then partitioned using an edge partitioner. Once partitioned, each community graph goes through a separate GNN encoder, and then the representations are composed using another model. The overall training algorithm has three objective terms corresponding to the classification task, the reconstruction task, and the KL divergence regularization.\n\nThe model is evaluated on node and graph classification tasks against a suite of relevant baselines. In addition, multiple visualizations and ablations are performed. ", "questions": "In no particular order:\n(Some of these are just open questions/ablations that do not necessarily have to be performed)\n\n1) In figure 1, should the concatenation of X and Phi be horizontally concatenated instead of vertically?\n\n2) (ablation) What would happen if there was no edge partitioner and all edges were passed to each GNN? Or randomly partitioned?\n\n3) (ablation) What if the composer was just a mean of the representations? Or weighted sum of the representations based on each nodes' affiliation scores? This would further tests the idea that the GNN community bank is doing a significant amount of work. \n\n4) Are there any datasets with community labels that we could see if the learned communities align with?", "limitations": "Adequately addressed", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n\n++ Seems to be a novel model overall and involves interesting ideas to learn these community associations through an unsupervised process.\n\nQuality:\n\n++ Paper is a complete work, it is well evaluated. In addition, the authors perform some good ablation studies and visualizations.\n\n-- I would like to see more ablations indicating where the model improvement comes from. How much does the edge partitioner matter? How about the composer? Would replacing these with super simple versions hurt performance? I think there are some questions potentially about where the gains in performance might be coming from\n\n- The analysis of space complexity is incorrect. It shows the parameter space complexity, not the space complexity. For example, if a model requires an N x N adjacency matrix in memory, that is O(N^2) space complexity even if there are no parameters. (This might just be a clarity issue, the authors should specify that this is analysis of the number of parameters).\n\nClarity:\n\n++ Paper is very well written, and is precise. \n\n+ Figure 1 is very helpful\n\n- Figure 1 could be improved by incorporating the different loss terms in the diagram.\n\n-Should probably specify that the optimization in equation 6 is maximization. \n\nSignificance:\n\n++ Model is definitely significant in that it improves the state of the art as well as introducing some new ideas.\n\n-- Unclear what the scalability of the method is in practice. No large graphs were tested. \n\nGrammar/Spelling:\n\nline 116: disjuction -> disjunction\nline 271 \"amount of label\" -> \"amount of labelled data\"\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gTEFvVZOeVw", "reviewer": "Reviewer_Sk5x", "summary": "This paper introduces a method called \"variational edge partition model\" that is generative graph learning framework. VEPM views edges and labels as overlapping community structures. The authors formalize the training of VEPM, and perform experiments evaluating its performance.", "questions": "Q1. The location of the \"Related Work\" is a bit strange. I would actually move it before Variational Edge Partition Model. Is there a particular reason why you did it this way?\n\nQ2. A bit of a theoretical analysis of why the current method works would make the paper more complete. Any plans to include some analysis?\n\nQ3. Why not release the code to make your work reproducible and your claims stronger? ", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The work has high originality as it views the edges of GNNs very differently compared to existing K-hop GNN idea.\nQuality: The work is of quality.\nClarity: The paper is clearly written. I have pointed out a few minor points below though.\nSignificance. The contribution seems significant as I have indicated above for my point about the work's originality.\n\nMinor points:\n- Line 58, put a comma after \"From these scores\"\n- Line 101, end the sentence at \"impractical\".\n- Line 171, typo on \"community\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "buCVueKitgx", "reviewer": "Reviewer_YYdd", "summary": "This paper proposed a variational edge partition method for supervised graph representation learning. The proposed method learns the community affiliation matrix $\\mathbf{\\Phi}$, generates $K$ partitioned graph representing different communities, and learn from all of when with two stages of GNNs. The idea of partitioning the graph into overlapping latent communities is very interesting, and extensive experimental results showed the effectiveness of the proposed method.", "questions": "Other than the weaknesses in the previous section, I also have two more questions:\n\n1. I wonder why many numbers are missing from Table 2. I would suggest the authors to get them if possible.\n\n2. In my understanding, the proposed method need to back-propagate through all $K$ adjacency matrices (as mentioned in w1). If this is correct, then the space complexity should be at least $O(N^2)$ instead of the given one in Section 4.4 (assuming $H << N$). If my understanding is wrong, please clarify.", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\ns1. This paper is clearly written and easy to follow.\\\ns2. The idea of edge partitioning with generative method is very interesting.\\\ns3. Extensive experiments validated the effectiveness of the proposed method.\\\ns4. The case study in Figures 3, 5-13 is shows that the proposed method successfully separates the community structures in the graph.\n\nWeakness:\n\nw1. It seems the method needs to back-propagate through all $K$ adjacency matrices $A^{(1)}, \\dots, A^{(K)}$, which could be expensive on the space when the graph is large. \\\nw2. The complexity analysis in Section 4.4 is pretty vague. I wonder if the authors can analyze in exact terms such as $N/K/F$ instead of GCN/GIN.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "K_pM9msIRZh", "reviewer": "Reviewer_JKdP", "summary": "This works aim at modeling the community structure of graphs via the latent variable of the generative model, that captures which nodes are assigned to which communities and then leverages such information on message passing of GNNs, all of which are trainable in an end-to-end fashion with a variational inference framework. In particular,\n* The authors model the community structure in the latent variable of the graph generative process, where they first calculate the affinity scores of nodes to the community and then use that scores for weighting edges during the aggregation of neighboring nodes in GNNs.\n* The authors use different GNNs for different communities and then merge representations from them to make a prediction for downstream tasks.\n* The authors formulate the proposed community-based generative model over a variational inference framework, making the proposed VEPM trainable.\n* The authors verify the performance of the proposed VEPM on node and graph classification tasks and also conduct analyses to see its efficacy.", "questions": "### Major Questions and Suggestions\n* Firstly, see the weaknesses above.\n* As shown in Table 5, if the proposed VEPM including inference and generative networks is trained jointly without pre-training, it totally fails on downstream tasks when comparing its performance to other baselines. More explanations are needed for this particular behavior.\n* I am wondering does the captured community by the proposed VEPM follow the community pattern extracted from existing community detection methods, for example, the METIS graph partitioning algorithm.\n\n\n### Minor Questions and Suggestions\n* Explaining how the generated edge weights are used in GNNs may be necessary. The form of a GNN layer in equation (1) lacks an expression of edges during neighborhood aggregation, which might be confusing for readers who are not familiar with GNNs.\n* The claims on \"state-of-the-art graph classification performance\" should be tone-downed. The compared works are mostly before 2021, and there are lots of works achieving remarkable performances [2, 5]. \n* More analysis of the temperature scaling value in equation (4) would be valuable. I would like to see the chaining communities of the proposed VEPM by varying the temperature value (i.e., from soft to hard community assignments and their performances).\n* The visualization in Figure 3 is extremely hard to see when I see this in a printed version. I would like to suggest authors visualize lesser nodes (e.g., 50 instead of the current 200).\n\n\n---\n\n[5] MaximumEntropy Weighted Independent Set Pooling for Graph Neural Networks. arXiv 2021.", "limitations": "The authors discuss the limitations and potential societal impact of their work in Section F of the supplementary file.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n* This work models the community structure into the latent variable of the graph generative process, which is reasonable, convincing, and interesting. I like the core idea that, the method captures community structures based on edge weights calculated from affinity scores of nodes to communities, which are then used for aggregating neighborhood features in GNNs.\n* This paper is well-structured and easy to follow.\n\n\n### Weaknesses\n* There is relevant work [1, 2] that considers latent community (cluster) structures of nodes, which should be discussed.\n* There is relevant work [3] that breaks down the entire training process into unsupervised training for capturing graph (edge) structures and supervised training for performing on downstream tasks, which is similar to this work's training process in Lines 182-192.\n* The performance improvements are not significant. Specifically, in Table 2 and 3, the proposed VEPM has huge variances, and, considering the variance, the results are not significant against baselines. Also, the powerful FactorGCN model is only compared on two datasets, namely IMDB-B and MUTAG among eight different datasets, on which the FactorGCN may outperform the proposed VEPM.\n* The authors should evaluate on recent benchmark datasets, namely OGB [4]. The used datasets, namely Cora, Citeseer, and Pubmed for node classification; TU datasets for graph classification, are relatively easy and somewhat outdated.\n* The analyses on the MUTAG dataset may be problematic. This is a very small dataset only having less than 200 graphs, compared to other datasets (e.g., the PROTEINS dataset has more than 1,000 graphs), and also known as showing high variance due to its size. Thus, I suggest authors analyze their model with larger datasets.\n\n---\n\n[1] StructPool: Structured Graph Pooling via Conditional Random Fields. ICLR 2020.\n\n[2] Accurate Learning of Graph Representations with Graph Multiset Pooling. ICLR 2021.\n\n[3] Data Augmentation for Graph Neural Networks. AAAI 2021.\n\n[4] Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept