Edge Partition Modulated Graph Convolutional Networks
Authors: Yilin He
Chaojie Wang
Hao Zhang
Bo Chen
Mingyuan Zhou
Venue: ICLR 2022 Submitted (2022)
Keywords: Latent Variable Models
Bayesian Methods
Variational Inference
Graph Neural Networks

Abstract: Graph convolutional networks (GCNs), 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 graph-level and node-level classification tasks. However, GCNs typically treat the graph adjacency matrix as given and ignore how the edges could be formed by different latent inter-node relations. In this paper, we introduce a relational graph generative process to model how the observed edges are generated by aggregating the node interactions over multiple overlapping node communities, each of which represents a particular type of relation that contributes to the edges via a logical OR mechanism. Based on this relational generative model, we partition each edge into the summation of multiple relation-specific weighted edges, and use the weighted edges in each community to define a relation-specific GCN. We introduce a variational inference framework to jointly learn how to partition the edges into different communities and combine relation-specific GCNs for the end classification tasks. Extensive evaluations on real-world datasets have demonstrated the working mechanisms of the edge partition modulated GCNs and their efficacy in learning both node and graph-level representations.

Under review as a conference paper at ICLR 2022
EDGE PARTITION MODULATED GRAPH CONVOLU- TIONAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph convolutional networks (GCNs), which propagate the node features through the edges and learn how to transform the aggregated features under label supervision, have achieved great success supervised feature extraction for both graph-level and node-level classification tasks. However, GCNs typically treat the graph adjacency matrix as given and ignore how the edges could be formed by different latent inter-node relations. In this paper, introduce a relational graph generative process to model how the observed edges are generated by aggregating the node interactions represents a particular type of relation that contributes to the edges via a logi- cal OR mechanism. Based on this relational generative model, we partition each edge into the summation of multiple relation-specific weighted edges, and use the weighted edges in each community define relation-specific GCN. We intro- duce a variational inference framework to jointly learn how to partition the edges into different communities and combine relation-specifie GCNs for the end clas- sification tasks. Extensive evaluations on real-world datasets have demonstrated how the proposed method helps enhance the discriminative representation power and its efficacy in learning both node and graph-level representations.
multiple overlapping node communities, each of which
INTRODUCTION
The graph data structure is widely adopted to describe interconnected objects, such as users in social network and atoms held up by chemical bonds form molecules. The edges in real-world graphs usually indicate strong and logically reasonable relations between nodes. Graph convolu- tional networks (GCNs) (Defferrard et al. 2016; Kipf Welling, 2017 Veličkoviē al., 2018 Klicpera et al.) 2019a by capture this property of graph data by introducing neighborhood aggrega- tion into regular perceptron layers. While this approach typically enhances the feature dependencies among strongly-related adjacent nodes, the absence of relational inference makes the aggregation mechanism indifferent to the multiple types of latent inter-node relations, ignoring which limits the ultimate potential of the model performance.
Extensive efforts have been made to seek solution for performance enhancement in dealing with graphs with heterogeneous relations (Schlichtkrull al. 2018 Vashishth et al., 2020 Nickel al. 2013). where the common ground these methods converges to is to learn multiple graphs, each one specified to one type of relation. The separation of reletions-specific graphs from one graph is easy when these relations are explicitly annotated by edge labels, but is non-trivial when the relations non-observable. To address this issue, some GCNs introduce techniques such as multi-head
[Veličković et al. 2018 Gao & Jil 2019) or multi-hop (Abu-El-Haija et al. 2019) aggregation that increase the model capacity for modeling multi-relations however, the aggregation weights in these too dependent on human knowledge to adapt to the underlying relations. Another line of research aims to disentangle relation -ppcifi- node represen- tations by task-driven graph factorization (Ma et al.) 2019 Yang et al.) (020). where the relational disentanglement is performed relying on label supervision, hence their performances would be neg- atively impacted by the scarcity of observed labels.
models are either short of interpretability
In contrast to the aforementioned methods, we introduce edge partition modulated graph convo- lutional networks (EPM-GCNs), generative framework that models the generation of edges and labels from latent relations. To begin with, we represent the latent relations with co-membership of K overlapping latent communities. For instance, in social network where people are linked

---

Under review as a conference paper at ICLR 2022
by online friendship, person may be simultancously affiliated with multiple social groups (e.g., graduating from the same school A, or working for the same company B, etc.). Then some similarity- based relations (e.g., schoolmates of A, colleagues in B) would naturally exist among people that are affiliated with the same social group. Under this modeling assumption, the strength of each relation between pair of nodes is measured by the multiplication of the following latent quantities: (i) the average interaction rate among co-members in the corresponding community and (ii) how strong the two ending nodes are affiliated with this community. The edges are further modeled by the logi- cal OR of binary latent edges independently generated through the Bernoulli- Poisssn link function given the strengths of each relation. This part of the generative model explains the shrinkage of heterogeneous relations into binary latent edges.
We next build up the generation process of labels. Since one node simultaneously engages multi- ple relations, we generate its representation as composition of relation-specifee sub-representations. These sub-representations are learned by three steps: the first step partitions the edges by normal- izing the strengths of K community-based relations, and defines K independent GCNs with each set of weighted edges; the second step obtains the desirable sub-representations by running the K GCNs in parallel. The labels of nodes or graphs could be predicted with the node representations generated in this way. This generative model allows the community-base relations to be inferred from both labels and edges, which not only systematically solves the relation non-observable issue, but also incorporates edges as an alternative source of information provided for the posterior infer- ence of latent relations. Since the observed edges dominate labels in quantity, our method would not heavily depend on label supervision, hence may suffer less from the scarcity of labels.
We summarize the major contributions of EPM-GCNS follows:
We develop a novel generative model that generates labels from -laatinn-specffic sub- representations, which are at first learned through independent neighborhood aggregations with weighted edges that are partitioned by the strengths of latent relations;
We integrate the label generation process with the generation of edges, which enables the observed edges to compensate for the scarcity of observed labels by providing extra infor- mation for latent communities/rclations
The proposed EPM-GCNs are end-to-end trainable via variational inference;
We analyze the working mechanism of EPM-GCNs and evaluate the models over various real-world network datasets. Empirical results show that the EPM-GCNs achieve state-of- the-art performance in most of the node and graph-level classification tasks.
EDGE PARTITION MODULATED GCNS
In this section, we present EPM-GCNs that learn the representation of node or graph from relation- specific sub-representatioos. As shown in Figure | the overall architecture of EPM-GCNs consists of a generative network (parameterized with 0) and an inference network (parameterized with w). Section 2.1 outlines the data generation process and corresponding supportive modules in the gen- erutive network, Section 2.2 elaborates the module in the inference network as well the inference- learning details.
2.1 GENERATIVE TASK LEARNING WITH LATENT COMMUNITIES
For the generative supervised graph analytic tasks under discussion, the information of graph G with N' nodes could be summarized by the triplet (X, A, .y, where X the design matrix whose rows represent the features of individual nodes, A is the binary adjacency matrix of G, with each "I" entry indicating the presence of an edge between the corresponding node pair, and y E {yo: y.} is the set of labels, with subscripts and a denoting the observed and unobserved parts of labels, respectively. The goal of our latent factor model is to describe the generation process of observed edges and labels. Based on that, The joint generation of edges A and labels is modeled by stacking up the generation process of edges and the generation of labels given the edges.
enabled to predict the holdout labels from their posterior.
2

---

Under review as a conference paper at ICLR 2022
X
The Generative Network EPM-GGC
The Inference Network EPM-GCN
A
GCN
X
FT
A
11
GCN
GCN
H
Output
GON
A
GCN
Community ENCoder [CENC]
Edge PARTItioner (EPART)
Relational [RGCN_BAME BANK]
REPresentation COMPaser (REPCOMP)
Figure The overview EPM-GCN's computation graph. & encodes nodes' affiliation strength to each community, which is used to (1) enrich node features with community information (the dashed line) and (2) partition edges via normalized rank factorization (the solid arrows). They are then passed to an array of GCNs generate node representations that correspond to heterogeneous community based relations, and finally inte- grated together optimize the classification task.
2.1.1
THE GENERATION OF EDGES
We adopt the generation process developed in Zhou 2015) to model the formation of edges A:
Ang Ber(p.)), Po == 1 Σn P.
which has an alternative representation under the Bernoulli-Poisee link as A., 1M,211 May Poisson( Ek= "Ys P, j. ). In this expression, d is positive node-community affiliation matrix, whose entry at the ith row and kth column could be interpreted as the strength that node i is affiliated with community 7 (A [K] is positive community activation level indicator that measures the member interaction frequencies featured by community k, and "/k 2 j.r quantifies the interaction rate between nodes and] j through community k. In our practice, we treat y [n, "2. , 7k]' as a part of the trainable parameters 0.
In this paper, focus another equivalent representation that partitions each edge into the logical disjunctions of K latent binary edges, expressed as
A.j k Ai.j,k Aijj.k ~ Ber (pijk), Pijk == 1 17,0 Vi,j [
where V is the logical disjunction (i.e., logical OR) operator and piyk denotes the probability that the interaction of nodes and community k results in an edge. The connection between nodes and j would establish as long as their interaction in one community forms up edge, in other words, nodes and j would be disconnected only if their interactions ALL communities fail to generate edges. Link function gives the conditional probability Po Φ). Note that the node interaction over each community uniquely corresponds to one type of inter- node relation, the generation of A reflects the aggregation of these heterogeneous relations, suggesting that one would need partition the edges to separate these relations.
1.2 THE GENERATION OF LABELS:
In consonance with the graph generative model that establishes the graph from latent communities, develop the generation process of labels from all relation-specifie representations. To achieve that, we first need to separate each relation from their totality, i.e., factorize the edges with the edge partitioner module:
Edge PARTitioner (EPART). The edge partitioner takes edges and community-afiliatie score matrix & as inputs and returns K positive-weighted edges: {A (1) A (2) A (K)),
We the [N] notation for the integer set 21. N) throughout the
3

---

Under review as a conference paper at ICLR 2022
s.t. Σ =k=1
A A. The partition funiitinn follows the form
(/ Ex e (1w (
1,1,2 K, Vi,j E [N]
(2)
Ex 1-Piye
Here т denotes the "temperature" that controls the sharpness of weights, its value is specified in Table 6 in the appendix. The edge weights produced from edge partitioner represent the propor- tion that each community- based relation takes in contributing to edge formation. When set sufficiently small, ( A(2) A (K) would approximate binary factors graphs of G, we hence refer to them as "relational graph factors". Replacing 7 P. with & (ns gener- alizes Equation 2 to metacommunity based edge partition, in this expression, the total number of communities is greater than K, and i, denotes the kth segment in node i's community-affllinn encoding. The generalized edge partitioner enriches the choices of 4's dimensionalities, which enhances the flexibility in model implementation.
Subsequent to the edge partitioner follows the relational GCN bank:
Relational GCN BANK (RGCN BANK). The relational GCN bank is made up of K independent
GCN components, coupling with the corresponding relational graph factors. It takes X = X
as input and outputs gg
(1) (X*), 8. (X*),
80
(K)
(X*)
ge
(k) (+) == GCNo A (k)), k E [K].
The function of this design to learn relation-wiss separable node representations. We now qual- itatively justify the fulfillment of this requirement. Without loss of generality, let us treat the rela- tional graph factors as approximately binary, this means the each observed edge is annotated with the relation that makes the greatest contribution in its generation. Let us denote the relations as 22,22." ..... . T which are uniquely featured with communities C1 C2, ... ,CC Assuming node u connects to its neighbors and 02 by relations I1 and 72, respectively. Without edge partition, fea- tures of U1 would be propagated to 02 in two runs of neighborhood aggregation even if they connects u with different community identities. This issue moderated by the relational GCN bank, as the aggregation path (v), u) would only be sent to the GCN component for relation Vi whereas the path (u, 22) would only exist in the GCN component corresponds relation r2. As a result, in each GCN component, nodes only share features through edges explained by the same relation, we hence consider the outputs of relational GCN bank as relation-specific.
Finally, we learn the representations of nodes from relation-specins sub-representattios. This step involves the representation composer module:
(k) (X*) denote the node representa- REPresentation COMPoser (REPCOMP). Let (R) ge
tions learned from the kth relation, E [K], and function f(-) denote the representation composer, whose functionality is project composite of relation-specific node representations to one rep- resentation matrix, iee. Hy = f (H()), H , = GCN₂ ( A) We could further obtain hg, the vector representation of graph G, by sending the node level representations Hy to a graph pooling layer, i.e., hg == GRAPHPOOL(Hw)
Taking softmax on the feature dimension of the representation composer's ' output gives the uncer- tainty distribution of labels, from which are able to make predictions on the category of the object (node or graph). Cascading the edge partitioner, the community-GCN bank with the representation composer yields the probability po(y (y A, 4 X).
2.2
TRAINING EPM-GCN: INFERENCE AND LEARNING
2.2.1
THE REPARAMETERIZABLL EVIDENCE LOWER BOUND OBJECTIVE
We set the prior distribution of & as di.. Gam 3), V(i E [N] [K], and use a community encoder to approximate the posterior distribution p( A,y):
Community ENCoder (CENC). The community encoder models the variational posterior qu ( by a Weibull distribution with shape K and scale A, both parameters are learned by GCN, i.e.,
The operator || denotes "concatenation".
Thhe community encoder the only module in the inference network.
4

---

Under review as a conference paper at ICLR 2022
|| A= G A). A random sample from qw ( could be created through the inverse CDF transformation of a uniformly distributed variable, given as follows:
A ① ( logo U))
()))0(kk)) ((1k))
Ug iid U(0,1), v(i, [N] x [K].
The operators 3 2 and o (in the front of superscrip f denote element-wise multiplication, division and power, respectively.
To jointly infer the latent factors & and use them to learn the task, we optimize the evidence lower bound objective (ELBO) L, given by Equation 3 i.e.,
L = Eny Po (y. A X) DKL. (Qx
(3)
= (o) log A, X) + (o)) log pe pe(A (A ②) - DKL (KL(Q+1(
where the notations P& and Q+ represent the prior and the variational posterior distributions of 4, respectively. The three right hand side terms correspond to the classification task, graph reconstruc- tion, and KL-regularization, we thereby refer to them as Ltask, free and LKL in the sequel. Note that the aforementioned specifications of O's 's prior and variational posterior, in Zhang al. (2018a), yield an analytical expression of LKL.-
2.2.2 THE OVERALL TRAINING ALGORITHM
To effectively train EPM-GCNs, we separate the overall training algorithm into an unsupervised pretrain stage, followed by a supervised finetune stage.
The ultimate goal of the community encoder is to find a commu- nity assignment according which edge partitions would facilitate task learning. Since the overall likelihood of node labels involves stacking multiple modules embodied by deep neural networks, inferring the posterior p( / A.y.) is difficult from an optimization perspective. To seek better model convergence, we break this optimization problem into two stages, namely, we first train the community encoder discover the latent communities that explains the graph architecture, then finetune the communities to align them to task-learning. The first stage is the unsupervised pretrain, which we pretrain the community encoder until convergence by optimizing free + LKL, i.e. up- dating model parameters towards w", which optimizes (s) log pa ( 1) DKL (Pa). The variational probability (T) is learned to approximate p( A). The heuristic that the un- supervised pretruin is generally supportive to the ultimate goal that although communities and node categories describe node similarity from different aspects, these two aspects of similarity are semantically mutually informative, iee. the discovered communities from graph architecture is in- herently correlated with node labels, which is suggested by previous work graph representation learning with community information (Sun et al. 2019), in which the node classification results clearly benefit from the node representations that hold community information. Such assumption is further qualitatively verified in Section [.2] We find through practice that the unsupervised pretrain not only stabilizes model convergence, but also provides a reasonable initial state for subsequent supervised optimization thus leads to better performances.
The unsupervised pretrain:
This stage involves iteratively running inference and learning. In the in- ference step, we fix the generative network, and train the inference network by optimizing the ELBO L. given in Equation Each inference step runs after M learning steps, where we treat the inference network as stationary and update the generative network by optimizing Lrask. Both L and Lrask are computed over the training set {y.. A, X). The supervised finetune updates the approximation tar- get of the inference network from o ) to p( A,),), which finetunes community inference with label supervision, making the subsequent edge-partition more facilitative to the classification task.
The supervised finetune:
The entire training pipeline of EPM-GCNS is summarized in Algorithm | (in Appendix A Af- ter running the unsupervised pretrain and the supervised fintune stages, the variational distribution (<b) is trained to approximate the posterior p( / yo, A). We hence approximate the predictive distribution of unobserved labels with Ey_ (y A, C. X)], and estimate it via Monte Carlo
estimation. In particular, we estimate p(y.. A, X, y.) with 1/2 -. pe(y,, A (g(),,)), where
(a) fidd quo
+ for = I....... S. For simplicity, we set S = unless specified otherwise. *Otherwise, the notation in the context of g denotes function composition.
5

---

Under review as a conference paper at ICLR 2022
Table 1: Statistics of the datasets for node and graph-level classification..
Task
Node Classification
Graph Classification
Dataset
Cora
Cheseer
IMDE-R
IMDB-M
MUTAG
PTC
NCII
PROTEINS
RDT--I
Graphs
1000
1500
188
344
4110
1113
2000
5000
Edges
5,429
4,732
44,338
96.5
65.9
19.8
26.0
32.3
72.8
497.7
594.8
Features
1,433
3,703
500
59
7
37
566
734
Nodes
2,708
3,327
19,717
19.8
13.0
17.9
25.5
29.8
39.1
29.6
508.5
Classes
3 RELATED WORK
Deep graph generative models: Advances in this line of work include adopting deep architectures in learning node embeddings (Kipf & Welling 2016 Li et al., 2018) and joint optimization with associated graph-analytte tasks such seemi-uupervin
node classification (Hasanzadeh al. 2019 Wang et al. 2020), community discovery (Sun et al., 2019 Mchta et al. 20199), etc. Similar to these models, we regularize the node embeddings by its probabilistic dependency with the graph structure, but instead of simply passing the learned embeddings to black-box prediction network, we use them to develop the generative process of the labels, leading to better interpretability.
The general idea is to individually process node repre- sentations aggregated from different types of relations. This logistic widely adopted by GCN variants handling graph data where relational annotations are either explicit (Schlichtkrull et al. 2018 Vashishth et al. 2020) or implicit. In the latter setup, the missing relations are conventionally completed with human knowledge Abu--ElHaija et al. 2019 Vashishth et al., 2020), learned via label supervision VVelčković et al.] 2018; & Jij 2019, Ma et al. 2019; Yang et al. 2020). Con- trary these methods which treat edges given, jointly model the generation of labels well as the edges, and systematically model the relations by posterior inference. The inferred relations then used partition edges, learn relation-specific sub-represennations, and finally optimize the downstream tasks.
GCNs modeling multi-relational data:
4 EMPIRICAL EVALUATION
We compare the proposed EPM-GCNs against related baselines two fundamental tasks: node classification and graph classification. In the sequel, we use the suffixes -n and -g to distinguish the variants of EPM-GCN developed for node and graph-level classification tasks, respectively.
4.1 DATASETS PREPARATION
We evaluate EPM-GCNs 11 benchmarks. For node classification, use 3 citation networks: Cora, Citeseer and Pubmed. All three datasets provide bag-of-words document representations as node features and (undirected) citations edges. For graph classification, ies datasets (MUTAG, PTC. NCI1, PROTEINS) and 4 social network datasets BMDB-BINARY, MULTIM REDDIT-BINARY and REDDIT-MULTI, The input node features are crafted in the same way with Xu et al. (2019). We summarize the statistcis of selected datasets in Table
4 bioinformat-
4.2 VISUALIZING LEARNED REPRESENTATIONS
To qualitatively assess the proposed model, we visualize the spatial distribution of / obtained the end of the unsupervised pretrain stage (Figures 2(a) ((b).. and the relation-specific sub- representations obtained at the end of the supervised finetine stage (Figures ((c) 2()). Node repre- sentation are projected to 2-D space via t-SNE (Van der Maaten & Hinton 2008). We select Cora and MUTAG as representatives of the node and graph classification datasets. For the MUTAG dataset, we remove less than 10 graphs that contain node categories with less than instances and randomly sample 10 graphs for visualization. In Figures 2(a) and 2(b). the spatial clustering of nodes from the same class indicates strong correlation between inferred latent communities and node labels, which not only demonstrates
model's 's ability in capturing community structure (even in small graphs with only tens of nodes), but also positively supports our model designs, including (i) input feature augmentation: X X || + and (ii) edge partition. Figures 2(c) and 2(d) further justifies that the reb-reeeennations {gg (X*), 80
(2) (x*), ... (K) (X*)) are not repetitive, signaling that the proposed model successfully extracts relation-specific representations, which potentially enhance

---

Under review as a conference paper at ICLR 2022
the discriminative power of node graph representations and lead to better performances the downstream tasks.
(a) + Cora
(b) Φ, MUTAG
(c) 86 ( ) Cora
(d) 8e (X*). MUTAG
Figure 2: Visualization of the spatial distribution of node representations learned by EPM-GCN on Cora and MUTAG datasets, mapped to 2-D space. (a) and (b) plot the t-SNE projections of nodes' community- affiliation scores (i.e., rows b) at the end of the unsupervised pretrain stage, where nodes are colored by their categories. (c) and (d) plot the t-SNE projections of relation-specific sub-representations of all nodes over all types of relations obtained at the end of the supervised finetume stage, the colors annotate outputs from different GCN components in the relational GCN bunk (i.e., each color corresponds to relation, each node corresponds K points in different colors). Spatially clustering of each colored group supports our community -asedd edge partition and node feature augmentation ((a). (b)), and justifies the learned relation-spectie caption-ppeciii sub-representations are indeed relation-wist wise separable.
4.3 NODE CLASSIFICATION
Experimental settings: To make fair comparison, we use the train/test/aalidttinn split standard- ized by the vanilla GCN (Kipf & Welling 2017) for Cora, Citeseer and Pubmed datasets. For the community encoder, we adopt similar encoder structure devised by Kipf & Welling (2016) with softplus activations, which outputs 16-dimensional community-affilaatee
scores for each node. We set the number of metacommunities K = for Cora and Citeseer and K = 8 for Pubmed dataset, the values of K are selected through volssvvlldition.. The relational graph factors are then obtained through the generalized edge partition. Before being sent to the relational GCN bank, these graph factors row- oow-normalized by sparse softmax. We implement the relational GCN bank with K single-laye layer GCNs with ReLU activation, following (Veličković et al.) 2018), we set their output dimensions 64/ K. The representation composer is also implemented with a single-layer GCN. With these specifications, the amount of parameters in the generative network remains comparable with that of 2-layer GCN with 64 hidden units (GCN-64) regardless of the choice of K. We record the complete hyperparameter specifications in Table 6 (in Appendix C).
Performance comparison: We use classification accuracy as the evaluation metric in the node classification tasks.
Table 2: Comparisons node classification performances.
Method
Cora
Citeseer
Pubmed
ChebNer (Detterard al 2016
81.2
69.8
74.4
Table 2 reports EPM-GCN-n's average performances (#: standard error) against the paper records of the average perfor- mances groups of related basclines on the three citation network datasets,
GCN Kipt & Welling 2017
81.5
70.3
79.0
N.
81.4
70.9
79.0
SIG-VAE (Hasanzadch et al 2019
79.7
7044
79.3
WGC AF: Wain ee
82.0
72.1
79.
GAT (ell cl 2018
83.0
72.3
79.0
1GAD Gao
83.5
79.2
DisenGCl Ma 2019
83.7
73.4
80.5
where marks the results reported by Veličković et al. (2018). The first group
EPM--CN-R (Lais work)
72.4
82.2 1::.:.2.
2017 are plain GCNs that aggregated node features with only one set of weighted edges. These models are designed to handle at most two types of node relations: connected or not, so it is not surprised to find that EPM-GCN-n outperforms these models by wide margin. Since removing (i) relational inference and (ii) relation-speciff feature learning degenerates EPM-GCN-n to GCN-64, the improvement of our model against GCN-64 could be ex- plained as the joint effects of the mentioned two practices. The second group (Hasanzadeh et al. 2019 Wang et al., 2020) are graph generative models that jointly optimized with semi-supervised loss. Both SIG-VAE (Hasanzadeh et al. 2019) and WGCAE (Wang et al., 2020) adopt similar graph generative model and loss structure to ours, the difference is that these models directly projects the latent representations to node labels by a deterministic prediction network, whereas we sample la- bels from to the second group could be attributed to the marginal benefit from our label generative model. The
(Defferrard et al. 2016 Kipf & Welling
based label generation process. Therefore
improvement with respect
third group of models (Veličković et al. 2018 Gao & Ji 2019 Ma et al. 2019) employ multi-head
7

---

Under review as a conference paper at ICLR 2022
Table 3: Comparisons on graph classification performances.
Method
IMDB-B
IMDE-M
MUTAG
PTC
NCII
PROTEINS 7.
RDTB
RDIM
WL subares
(Servachidae et al 2011
73.8 3.9
50.9 18
904
2.3
86.0 18
810 3.1
52.5
AWL
2013
74.5 5.9
51,5 3.6
$79
27
51.7 2.99
DCNN
33.5
6131100 6.06..00
DGCNN
Ziant
70.0 1:
478 00
386::00
7.44:000
7
PATCHYSAN Napper of 2016
71.0 22
45.2 28
026+42
60.0+48
78.6 1 1.9
7
863+ 16
42.1 +00
GIN-D Xurer di 2019
7..1
+2.3-28
894
646+70
82.7
76.2
25
57.5 + 1.5
GIN-
1.11
52.1
3.36
60
632
82.7 1:111
75.9
57.0 93
FactorC
75.3
8.9+65
Welley
74.0
51.
80.2
3.2
500
20.0
GAT
Vall Br 2015
70.5 2.3
47.8 3.1
$9.4 6.1
66.2
5.1
GraphS AGE Hamilian et 2017
12.3 5.3
50.9 4 22
85.1
441476 76
63.9
4 7.7
77.7 4: 1,5
75,9 3,2
BPM-GC G.g (this
76.7
2..1
75.6
83.9
1.8
$0.5
903 55.0
Table 4: Comparisons of EPM-GCN-g with various input node features.
Random Hand-crafted Community-busce
IMDB-B
IMDB-M
MUTAG
PTC : 2.0
42.
80.3 2.0
53.5
74.7 - 4.1
74.7 5.1
2.0
88.9
68.9 = 3.9
76.7
54.1 2.1
3.5
5.9
and adaptively weighted feature aggregation mechanisms, which greatly enhances their ability in handling multi-relational data. However, these models lack systematic modeling of latent relations, which on the other hand is the strength of our model. Our performance boost against the third group on most of the benchmarks demonstrates the marginal benefit of our relational inference model.
4.4 GRAPH CLASSIFICATION
Experimental settings: For EPM-GCN-g. we implement the community encoder with 2-layer GCN and produces the latent community-affliatii encoding with 100 dimensions. The number of metacommunities is set K 4 and corresponding relational graph factors are generated through the generalized edge partition. We choose GIN layer as the building block to define the rest of the model, and set the total network depth as (including the input layer) such that EPM-GCN-g is comparable with the vanilla GIN (Xu et al., 2019). We define the K components in the relational GCN bank by sharing the input layer and evenly partitioning the neuron units in the top hidden lay- ers. The 2 ending layers are treated as the representation composer. The remaining implementation details are included Table 6 (in Appendix C).
We follow GIN (Xu et al. 2019 to perform 10-fold cross validation for each dataset and report the average classification accuracy (+t standard error). As shown in Table
Performance comparison:
we compare the developed EPM-GCN-g with several state-of-the-an baselines for graph classifica- tion, including the WL subtree kernel (Shervashidze et al. 2011), Anonymous Walk Embeddings (AWL) (Ivanov & Burnaev 2018) and other deep learning architectures like DCNN (Atwood & Towsley 2016), DGCNN (Zhang et al, 2018b), and PYTCHY-SAN (Niepert et al. 2016). We also compare EPM-GCN-g with five supervised GNNs including GCN (Kipf & Welling (017), GAT (Veličković et al.) 2018), GraphSAGE (Hamilton et al. 2017). and two variants of GIN (Xu et al., 2019): GIN-O and GIN-e. Thanks our uniquely designed multi-relational inference well as relation-specific graph representation learning and composition, EPM-GCN- -g achieves state-of-the art graph classification performances on 5 out of benchmarks, and the second-best performance on NCII dataset, where it outperforms all the other deep architectures. Notably, EPM-GCN-g g achieves 75.6% accuracy on PTC dataset with significant 7.9% improvement over the second place.
4.5 ABLATION STUDY
To further study the marginal benefit of each practice we take in implementing EPM-GCN, well as model's overall sensitivity to variations in hyperparameter setup, we evaluate EPM-GCN's graph classification performances over various choices of input features, number of metacommunities,, and network structure.
We first evaluate model performances with four types of inputs: random noise, hand-crafted features by Xu et al. (2019), community-afiilin scores. Results are shown in Table 4 The classi- fication accuracy measures the discriminative level of graph representations learned from these four types of inputs comparing the first and second rows with the third row tells us that community- affiliation scores meaningful node representations and comparably informative to the task as
Various input features:
scores, and hand-crafted
features concatenated with community-afflliatin
8

---

Under review as a conference paper at ICLR 2022
8
Mustar a.Dr BLAI
of
Ruraer SFOW
(a) IMDB-B
(b) IMDB-M
(c) MUTAG
(d) PTC
Figure 3: The average graph classification accuracy of EPM-GCN-g with various settings the numer of metacommunities K {1,2, 4, 8, 16). Results (a) IMDB-BINARY, (b) IMDE-MULTI, (c) MUTAG, and (d) PTC datasets are shown in the subfigures.
hand-crafted node features. We could further conclude by comparing the second row with the fourth row that the information & and X hold for the task enhances the discriminative level of learned representations in a complementary manner. Both conclusions justify the quality of o as additional node features.
Number of communities: We next study the variation of the model's ' performances with growing number of metacommunities.. Figure ] plots the average graph classification accuracy over 10- fold cross-validation against different selections of K E (1, 2, 4, 8, 16). In the context of graph classification, K denotes the number of all metacommunities with least one presence among the graphs in the dataset. We could see that the optimal results are typically achieved with K > 1. which consistent with the model assumption that the graph contains multiple underlying relations, the result also reflects the efficacy of the proposed model in modeling heterogeneous latent relations.
Network structures: Among our proposed results Table 3 the network structure for the label generation is not particularly fine-selected and hidden layers are evenly distributed to the relational GCN bank and the representation composer, In this part, we focus on studying how the balance between these two modules influences the model performance on downstream tasks. We use the name convention - (-( to denote the variant with I,, layers (including the input layer) in the relational GCN bank and L2 layers in the representation composer, where L1 > 0 and L1 L2 = 5, As Table [ shows, although the optimal layer assignments for each dataset are not the same, i.e., the IMDB-B and IMDB-M datasets generally require less relation-wiss locality in node representations than MUTAG or PTC datasets, both modules are verified to be necessary for the graph-analytic tasks, because neither EPM-GCN---(1I (1)((4) FEM--GCN--155)- over other layer combinations in any of these experiments. Additionally, the variation of model performances under different layer assignment demonstrates that datasets with larger amount of graphs are generally more insensitive to the change of model architecture, so the way to increase model robustness on datasets with less graphs would topic worth studying in the future.
triumphs
Table Comparisons of EPM-GCN-g with various network structures.
Network Structures
IMDB-B
IMDB-M
MUTAG
PTC
GIN-0 Xu et al.
2019
5.1
52.3
89.4 15.66
64.6
GIN Xu al. 2019
5.1
52.1 + 3.6
89.0 6.0
63.7
EPM-GUN-2-11P-
3..6
5.74=27
7.6
5.3
GPM-GCN---(2)-13
2.0
2.1
91.0
736
g3)-G
76.7 1311
54.1
93.6
75.6
1:61:00
EPM-GCN-g-14 (4)-
74.5
2.2
54.3
87.0
66.3 5.0
EPM-GCN-8-F (55))-(0))
7..2
5.
80.4 10.4
63.1 + 6.2
CONCLUSION
Moving beyond treating the graph adjacency matrix as given, we develop novel EPM-GCNs to aggregate the node interactions over multiple overlapping node communities. More specifically, we first construct a community encoder to project each node to its community-affilin partition the edges between nodes according to the edge-formation contribution of each community- based relation with a edge partitioner. Then we obtain the -aation-specific sub-representations with the relation GCN bank and finally put them together to make predictions with representation composer. Extensive qualitative and quantitative experiments on both node and graph-level has been made demonstrate the efficacy of model.
scores, and then

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
The PyTorch code to reproduce the results in the paper has been included in the supplementary material. Detailed hyperparameter settings have been provided in Table 6 in the Appendix.
REFERENCES
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference Machine Learn- ing (ICML), Proceedings of Machine Learning Research, pp. 21-29, 2019.
James Atwood and Don Towsley. Difflsionncoonoluttinaal neural networks. In Advances in neural information processing systems, pp. 1993-2001, 2016.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems (NeurIPS), volume 29, 2016.
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), pp. 741-749, 2019.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
Arman Hasanzadeh, Ehsan Hajiramezanali, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. Semi-implicit graph variational auto-encoders. In Advances in Neural Infor- mation Processing Systems (NeurIPS), volume 32, pp. 10711-10722, 2019.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International conference on machine learning. pp.
PMLR, 2018.
Thomas N Kipf and Max Welling. 1611:3300 2016.
Variational graph auto-encoders. arXiv preprint
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference Learning Representations (ICLR), 2019a.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann, Diffusion improves graph learn- ing. In Advances Neural Information Processing Systems (NeurIPS), volume 32, pp. 13354- 13366, 2019b.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint 38Xi:18003.0322,, 2018.
Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. Disentangled graph convolutional networks. In International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 4212-4221, 2019.
Nikhil Mehta, Lawrence Carin, and Piyush Rai. Stochastic blockmodels meet graph neural net- works. In International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 4466 4474, 2019.
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.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International conference on machine learning, pp. 2014-2023. PMLR, 2016.
10

---

Under review as a conference paper at ICLR 2022
Michael Schlichtkrull, Thomas N Kipf. Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. European semantic web conference (ESWC), pp. 593-607. Springer, 2018.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Fan-Yun 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 Processing Systems (NeurIPS), volume 32, 2019.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9111), 2008.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition- multi- relational graph convolutional networks. In International Conference on Learning Representa- tions (ICLR), 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
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.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
Yiding Yang, Zunlei Feng, Mingli Song, and Xinchao Wang. Factorizable graph convolutional networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 19286-20296, 2020.
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), 2018a.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 32, 2018b.
Mingyuan Zhou. Infinite edge partition models for overlapping community detection and link pre- diction. In International Conference on Artificial Intelligence and Statistics (AISTA7S), volume 38 of Proceedings of Machine Learning Research, pp. 1135-1143, 2015.

---

Under review as a conference paper at ICLR 2022
APPENDIX
A THE PSEUDOCODE OF TRAINING ALGORITHM
Algorithm 1:
The overall training algorithm of EPM-GCN
Data: node features X, observed edges and observed labels yo Modules : CENC, EPART, RGCN_BAC BANK and REPCOMP
Parameters: the inference network, and in the generative network Initialize w and 0:
while the community encoder not converged do D, K. A &- CFNC(A X);
Compute Lree and LKL, given Equation
w Munssup ( LKL);
/* Unsupervised pretrain */
end
while the whole model not converged do
④b, K. A &- CENC( A, X);
A (2) (2)
A (K) EP
for step + 1 to M do
Py. & softmax (REPCOMP o RGCN_BANK( X, A ((K))
A
Compute trakk: given in Equation 3
0 θ Mupp,0 V
/* The learning step +/
end
Compute L;
f- W Nsup. VwL;
/* The inference step +/
end
B PROPERTY OF WEIBULL DISTRIBUTION
Similar PDF with Gamma Distribution
The Weibull distribution owns similar probability density functions (PDF) with gamma one, which makes it flexible to model sparse and nonnegative latent representations:
Weibull PDF: P(=[k, A)
k
x
(a(//1)*
(4)
Ba
Gamma PDF: P(rla,
aa-le Bx
I'(a)
Easily Reparameterization
The latent variable æ Weibull(k;, A) can be easily reparameterized as
In(1n(1 E)) Uniform(0, 1),
(5)
leading to a similar gradient calculation with the Gaussian reparameterization.
Analytic KL--Dvergence
Moverover, the -iveereeeee between the Weibull and gamma distributions has an analytic ex- pression formulated as
KL(Weibull(e;; A)][Gamma(a, 3)) -a In A + 7
k
(6)
+ Ink +, 1) K - - - an (n
12

---

Under review as a conference paper at ICLR 2022
C IMPLEMETATION DETAILS
In our experiments, we find the initial state inference module provided by the unsupervised pre- train stage is essential to EPM-GCN's performances.
The hyperparameters are either inherited from base models or selected on the basis of cross- validation. Note that for the graph-level classification task, the parameters shared across ex- periments on all datasets. And the reported results are potentially improvable datasct-specific cross-validations are applied.
Table 6: Hyperparameters settings for EPM-GCN.
Hyperparameters
Experiments
Node Classification
Graph Classification
Community ENCoder
Settings
3
epoches of insupervised pretrain learning rate of unsupervised pretrain batch size of unsupervised pretrain
1500
1500
1e-3
le-2
32
type of GNN layers
GCN
GCN
module structure
(32)-(16)
(200)-(100}
Edge PARTitioner
Settings
number communities
[4,8]
the temperature 7 for partition
Relational GCN BANK
Settings
epoches of jointly training
200
100
learning rate of jointly training
1c-2
lc-3
weight decay of jointly training
5c-4
0.0
batch size of jointly training
32
concat weight of + type of GNN layers module structure
3e-2
3e-4
GCN
GIN
(64)
(64)-(64)
REPresentation COMPoser
Settings
epoches of jointly training
200
100
learning rate of jointly training
le-2
lc-3
weight decay of jointly training batch size of jointly training type of GNN layers module structure
5e-4
0.0
32
GCN
GIN
{class num)
(64)-(64)- num]
13


Reviews:
[{"review_id": "roKxApjXeqp", "reviewer": "Reviewer_tuFU", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "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": "Overall, this paper is well-organized. It is interesting to investigate how an edge is formed to make use of the inter-node relation to enhance GNNs for node representation learning. Experimental results on several graphs demonstrate the effectiveness of the proposed method in both node-level and graph-level tasks.\n\nHowever, I have some major concerns:\n- Lack of theoretical analysis. There is no theoretical analysis of the proposed method especially on the relationship between community information and embedding propagation.\n- Studies of different relations. Although the aggregated representations of all relations have been visualized in Figure 2, it may provide more information to explore each relation in contributing to form edges and learning representations.\n- Performance of community learning. Although in the visualization some community structures have been shown in Figure 2, it would be interesting to show quantitatively the performance of community detection.  \n\nThere are some minor comments:\n- Why Community ENCoder is part of model training?\n- Notation r has been used as parameters on Page 3 and also as relations on Page 4.\n- what does RHS mean under Eq (3)?\n- There are some typos:  (1) In REPresentataion COMPoser: denotes -> denote, after Eq (3), Where -> where", "summary_of_the_paper": "This paper investigates how an edge is formed by different latent inter-node relations and extends the community-based edge formulation mechanism to graph neural networks. A variational inference framework has been proposed to jointly learn how to partition the edges into different communities and combine relation-specific GCNs for the end classification tasks. Experiments on several real-world graph datasets demonstrate the effectiveness of the proposed method in both node-level and graph-level representation learning problems.", "summary_of_the_review": "The paper provides an interesting and novel solution to learn better representation with the investigation of edge formulation. However, several claims are not well-explained.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nubRJmmwQCv", "reviewer": "Reviewer_1iDH", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "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": "Apart from statements that need clarification or adjustments, the paper is generally well presented and organized. Technically speaking, there are three main issues with the submission that can be summarized by: i) lack of proper motivations for the proposed architecture; ii) missing or ambiguous technical details; iii) robustness of the empirical evaluation. This review will proceed by sections, by listing major and minor comments to provide a feedback as complete as possible.\n\n### Abstract\n\n#### Major\n\nFrom \"In this paper\" to \"OR mechanism\", the text is too dense and does not help the reader grasp the intuition of what is happening. Also, it is not clear why modeling latent node communities should be important to solve the main supervised task (point i) above).\n\n#### Minor\n\n\"have demonstrated the working mechanisms\" should be removed, as the paper does not fulfil the promise made by the authors.\n\n### Introduction\n\n#### Major\n\nWhen referring to GCNs works, the authors did not mention two of the earliest works in the graph learning literature, namely GNN (Scarselli et al, 2009) and NN4G (Micheli, 2009). It is recommended that at least these two works are added to the paper.\n\nFrom \"the absence of relational inference\" to the end of the paragraph: this statement looks like pure speculation unless supported by scientific evidence or concrete examples. \n\nThe paper seems to lack proper motivations, apart from the \"need of modeling latent communities\". Since the empirical evaluation relies on numeric results and a qualitative visualization, it is unclear why one should really need to model latent communities by using multiple GCNs. It is strongly recommended that the authors provide convincing motivations and justification for the development of their approach, other than stating that \"it performs better\" (see my comments below on the empirical evaluation).\n\n#### Minor\n\nQ: why is the GAT aggregation too \"ad-hoc\"? It seems pretty general and completely adaptive. And what does \"ad-hoc\" refers to?\n\nQ: could the authors please describe how and why \"extra information provided with the observed edges remedies optimization issues caused by the scarcity of label supervision\"? Otherwise this seems another claim unsupported by evidence (either from the paper or from the literature).\n\nQ: what are \"observed (target) labels\"? Are we considering a specific kind of task that considers unobserved and observed targets, like the semi-supervised setting of node classification? If that is the case, the authors should specify it, since that statement does not hold in general.\n\nPlease avoid using terms like \"insatiable\".\n\n### Methodology\n\n#### Major\n\nThe use of the terms \"generative\" and \"inference\" in contraposition can create confusion among readers. One of the reasons is that  the term \"generative model\" is often synonym of probabilistic models that perform inference, so \"reconstruction\" or \"community encoder\" could be more appropriate and disambiguating here. This distinction seems to confuse the authors as well: the \"generative\" model is associated with parameters \\theta at the beginning of Section 2, but it seems that it is the other way round, with the parameters of the community encoder being \\omega.\nIt would also benefit the presentation to state what is the role of the generative and inference models, to have a clearer picture in mind of what is to come.\n\nNotation-wise, at this stage it remains unclear why the distinction between y_o and y_u has to be made, and the symbols representing the original and reconstructed adjacency matrix coincide. \n\nThe last statement of Sec 2.1.1 is crucial to the justification of your work, but it is again unsupported by scientific evidence.\n\nThroughout the full text, there seems to be no reference whatsoever to the temperature values tried in the experiments. Please specify them.\n\nThe manuscript would probably benefit from a descriptive and empirical comparison with respect to Relational GCN (Schlichtkrull et al 2018), to understand why and whether or not your inductive bias is really more effective. For instance, R-GCN could be applied to the different adjacency matrices identified by the community encoder, as if edges had different types.\n\nThere is not proof or derivations for the equations of the community encoder in Sec 2.2.1, and the analytical expression of L_KL should be described somewhere.\n\nFrom \"and the model design that involves... to the end of the paragraph\": this is another claim unsupported by scientific evidence, and it is even not very clear. It could be better to drop it or add some support to it.\n\nSince the model is end-to-end trainable, it is not completely intuitive why the supervised finetuning stage should alternate between two different supervised optimizations, one of which is included into the other. The suspect is that this is a choice driven by necessity of convergence than to make the edge partition \"more facilitative to the classification task\". It would be appropriate to conduct an ablation study in which the model is finetuned in an end-to-end fashion, to show that this peculiar training strategy is indeed effective. Note that, at this stage of the article, it is still unclear what is the purpose of y_o and y_u.\n\nSetting S=1 cannot be justified by mere simplicity. The value of S has an important effect on the quality of the approximation, so it would be appropriate to rephrase that or conduct a study that shows how S=1 is indeed sufficient to provide good performances.\n\n#### Minor\n\nQ: what is the meaning of \"unsupervised parts of labels\"?\n\nIt would help the discussion to see an actual example of community-specific adjacency matrices, as well as computing a discrepancy score between them.\n\nPlease refer to equations instead of \"link functions\"\n\n\"K positive-weighted edges\" --> \"K positive-weighted matrices\"\n\n\"edge partitioner represents\" --> represent refers to \"edge weights\", please correct these severe mistakes across the manuscript.\n\nCould the authors please define \"underqualified\" and \"data-label ratio\"? This would help the comprehension of the manuscript.\n\n### Empirical Evaluation\n\n#### Major\n\nAll empirical evaluations in the paper follow protocols that have been heavily criticized by the community [1,2], either because they  are unfair, not robust, optimized wrt the test set, or all of the previous. The node classification tasks should have averaged the results over different train/val/test splits, and the 10-fold cv procedure of Xu et al. is known to optimize hyper-parameters on the test set. For these reasons, the empirical results in this paper should not be considered of sufficient quality, and the authors should set up a proper empirical evaluation. This includes:\n\n1) Being clear in separating model selection from model assessment, as well as stating the protocols used in the paper\n2) Testing a sensible amount of hyper-parameters configurations during model selection, rather than fixing most of them like in this paper. This is a computationally heavy phase, but it cannot be avoided in general.\n3) Conducting ablation studies and hyper-parameters sensitivity tests as part of the output produced during model selection (on the validation set). In this paper, it is evident that the results of Table 3 are the result of the analysis of different configurations of Table 5, meaning the hyper-parameters have been optimized on the test set (see MUTAG and PTC, for example). The effect of hyper-parameters should never be studied on the test set.\n\n[1] Shchur, Oleksandr, et al. \"Pitfalls of graph neural network evaluation.\" arXiv preprint arXiv:1811.05868 (2018).\n\n[2] Errica, Federico, et al. \"A fair comparison of graph neural networks for graph classification.\" ICLR 2020.\n", "summary_of_the_paper": "This article proposes a new architecture to solve node and graph classification tasks. The main idea is that an initial transformation is used to map nodes to K different communities, after which community-independent node features are computed and used together to classify the nodes/graph. The training process undergoes an initial unsupervised pre-training stage, followed by a supervised finetuning stage that, for some reason not well understood, alternates the optimization of two supervised objectives (one of which is included in the other), by fixing different parts of the end-to-end architecture at each step.\n", "summary_of_the_review": "In light of the above considerations, the paper needs substantial rewriting and the empirical evaluations must be done following a proper protocol. It cannot be accepted as is, and probably there is no time to properly fix these points in the rebuttal phase.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jGhxmHzTVoi", "reviewer": "Reviewer_6jg3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "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": "Strengths:\n1) The proposed methods perform favorably in the experiments.\n2) The presentation of the paper is clear and easy to follow.\n\nWeakness:\n1) The motivation of designing such partition based GNN is not clear. Why it is important to consider the latent inter-node relations? What are the implications should such relations are ignored assuming their existence? \n2) It lacks a comprehensive analysis of the learned partition weights (called node community affinity matrix). While the paper provides the T-SNE plot of the learned matrix, there are not quantitative measure of the properties of learned affinity. Do these K groups of affinity scores have similar structures? Are there clear pattern of partitions when we adjust the temperature parameter?\n3) The ablation study section misses a few important dimensions. a) The impact of doing pretraining step introduced in this paper. And why there are instability issues with end-to-end training. Is it sensitive to any of the parameters of the node affinity matrix? b) Does the proposed method only work with GNN? \n4) The methods proposed in this paper are based mature and well-known techniques. The novelty is limited.", "summary_of_the_paper": "This paper proposed a edge partition based graph neural network model. It samples a K sets of edges based on learnable node affinity matrixes. A composer layer is used to combine node representations from each partitions. To improve training stability, the paper trains the edge partition part first with unsupervised then finetune it on supervised learning task. Built upon mature techniques, the authors suggest this model has superior performance with experiments on both node classification and graph  classification data.", "summary_of_the_review": "This paper uses the graph generation model and a soft-max transformation with temperature term to implement the idea of doing K graph edge partitions in side GNN computation. The presentation of paper is well organized and experiments results are generally favorable. However, the motivations and assumptions are not discussed clearly and verified carefully. The ablation study does not address some of the key design in this model. The overall novelty of this paper is limited. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "6GmqqPd7-2u", "reviewer": "Reviewer_LpaE", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "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": "**Strengths :**\n\n1. Novel technique. While community detection has been explored before, using this community information to predict better labels is something that I have not come across. The model training procedure with the unsupervised pretraining followed by iterative supervised learning is interesting.\n2. Thorough evaluation across 11 datasets to demonstrate that the model works well in practice.\n\n**Weaknesses :**\n\n1. Problem needs to be better motivated. What are some examples of real world datasets with latent relations/communities? For example, what could be the latent communities in a citation network? I made an attempt to construct an example in the summary section above based on my understanding, but it would be nice to see something of the sort in the introduction.\n\n2. The ablation studies aren’t very comprehensive - they only compare across a) different input features, b) different numbers of latent communities, and c) different numbers of GCN layers. A better ablation study, in my opinion, would be to modify key parts of the model and not just change hyperparameters. Example - what is the performance with and without the unsupervised pretrain? What if we didn’t compose $X$ with $\\Phi$ to get $X*$?\n\nMore thoughts / Questions for the authors :\n\n1. In the Edge Partitioner module, is $\\tau$ always chosen such that the generated adjacency matrices are binary? I assume that must be so, because otherwise one cannot apply a GCN to a non-binary adjacency matrix. But it would be nice to have this clarified.\n\n2. Do all the baselines use hand-crafted features as in Xu et al (2019)? I couldn’t find this mentioned anywhere.\n\n3. Here is a thought - what if we were to take a multi-relational graph, homogenize the edges, then see what latent relations are predicted by your model and how well they track the original relations that we started with?\n\nMinor comments :\n\n1. It would be nice if the $||$ notation for concatenation could be explicitly defined somewhere. It becomes obvious after a little more reading, but it confused me the first time.\n\n2. Typos - “interatively” (page 5), “represnetation” (page 7), “edge-formation contributionedge-formation contribution” (page 9).", "summary_of_the_paper": "This paper develops Edge-Partition Modulated Graph Convolutional Networks, a GNN architecture that explicitly models latent relations between nodes in a graph. The key idea is that nodes may be organized as overlapping \"communities\", where each community represents a particular type of relation. For example, in a citation network of papers, where the task is to predict the category of each paper, all papers from a research group could form one latent community. If one could infer this latent community information, then this could help predict unknown labels.\n\nTo accomplish this task, the model learns a community affiliation matrix whose entries express how strongly each node is affiliated to a particular community. Once we have this matrix, the adjacency matrix is partitioned as a sum of K adjacency matrices, where K is the number of communities. The model then runs K different GCN models using the same node features but K different adjacency matrices, and the outputs of all these GCN models are concatenated. Finally, we apply a GCN model using these composite node features and the __original__ adjacency matrix, to get a final classification for each node. These GCN models together comprise the \"generative network\".\n\nThe different weights are learned using an intricate training procedure. First, the model learns a good initial community affiliation matrix, by maximizing the posterior probability of the community matrix given the adjacency matrix. This stage is entirely unsupervised, because it uses only the observed edges and not the edge labels.\n\nIn the next stage, the model iteratively runs inference (where the community affiliation matrix is learned by optimizing the ELBO using label supervision) and learning (where the community matrix is held fixed but the generative GCN models are trained). Inference and learning are repeated till convergence.\n\nFinally, a community matrix is sampled from the learned posterior and this is used along with the generative network to predict unknown labels.\n\nThe authors evaluate their model on a variety of node classification and graph classification benchmarks. They also visualize some embeddings for better interpretability, and perform some ablation studies.\n", "summary_of_the_review": "Overall this paper makes an interesting contribution to the field. The technique/key idea are, in my opinion, novel, and the evaluation is thorough. My concerns are limited to the problem motivation as presented in the paper, and the extent of the ablation studies.\n\nIt is possible that my understanding of the variational inference and ELBO optimization part is insufficient. I have not checked these parts for correctness, and I am not familiar with related work in the area. I have therefore indicated that my confidence in my assessment is slightly lower.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The weaknesses of the paper can briefly be summarised as follows: i) the suggested motivation is not so clear, and in addition the experimental results (by themselves questionable in the way they are obtained) do not support the main claim of the paper that "...edges are generated by aggregating the node interactions over multiple overlapping node communities, each of which represents a particular type of relation that contributes to the edges via a logical OR mechanism." In fact, the observed separation among components is not proven to be of the predicted nature. ii) empirical results are obtained using a deprecated experimental protocol. For the field to make real progress, experimental assessments should follow statistically sound protocols. Already published papers that were not following a sound protocol should not be taken as reference for future empirical assessments.
The last point alone is a strong motivation for rejecting the paper.
Decision: Reject