Year: 2021

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 how the proposed method helps enhance the discriminative representation power and its efficacy in learning both node and graph-level representations.

heading: 1 INTRODUCTION
text: The graph data structure is widely adopted to describe interconnected objects, such as users in a social network and atoms held up by chemical bonds to form molecules. The edges in real-world graphs usually indicate strong and logically reasonable relations between nodes. Graph convolutional networks (GCNs) (Defferrard et al., 2016; Kipf & Welling, 2017; Veličković et al., 2018; Klicpera et al., 2019a;b) capture this property of graph data by introducing neighborhood aggregation 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 et al., 2018; Vashishth et al., 2020; Nickel et al., 2015), where the common ground these methods converges to is to learn multiple graphs, each one specified to one type of relation. The separation of relations-specific graphs from one graph is easy when these relations are explicitly annotated by edge labels, but is non-trivial when the relations are non-observable. To address this issue, some GCNs introduce techniques such as multi-head (Veličković et al., 2018; Gao & Ji, 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 models are either short of interpretability or too dependent on human knowledge to adapt to the underlying relations. Another line of research aims to disentangle relation-specific node representations by task-driven graph factorization (Ma et al., 2019; Yang et al., 2020), where the relational disentanglement is performed relying on label supervision, hence their performances would be negatively impacted by the scarcity of observed labels.
In contrast to the aforementioned methods, we introduce edge partition modulated graph convolutional networks (EPM-GCNs), a 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 a social network where people are linked
by online friendship, one person may be simultaneously affiliated with multiple social groups (e.g., graduating from the same school A, or working for the same company B, etc.). Then some similaritybased 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 a 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 logical OR of binary latent edges independently generated through the Bernoulli-Poisson 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 in multiple relations, we generate its representation as a composition of relation-specific sub-representations. These sub-representations are learned by three steps: the first step partitions the edges by normalizing 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-based 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 inference 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 as follows:
• We develop a novel generative model that generates labels from relation-specific subrepresentations, 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 information for latent communities/relations;
• 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-ofthe-art performance in most of the node and graph-level classification tasks.

heading: 2 EDGE PARTITION MODULATED GCNS
text: In this section, we present EPM-GCNs that learn the representation of node or graph from relationspecific sub-representations. As shown in Figure 1, the overall architecture of EPM-GCNs consists of a generative network (parameterized with θ) and an inference network (parameterized with ω). Section 2.1 outlines the data generation process and corresponding supportive modules in the generative network, Section 2.2 elaborates the module in the inference network as well as the inferencelearning details.

heading: 2.1 GENERATIVE TASK-LEARNING WITH LATENT COMMUNITIES
text: For the generative supervised graph analytic tasks under discussion, the information of a graph G with N nodes could be summarized by the triplet (X,A,y), where X is the design matrix whose rows represent the features of individual nodes, A is the binary adjacency matrix of G, with each “1” entry indicating the presence of an edge between the corresponding node pair, and y ∈ {yo,yu} is the set of labels, with subscripts o and u 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, we are enabled to predict the holdout labels from their posterior. The joint generation of edges A and labels y is modeled by stacking up the generation process of edges and the generation of labels given the edges.

heading: 2.1.1 THE GENERATION OF EDGES
text: We adopt the generation process developed in Zhou (2015) to model the formation of edges A:
Ai,j ∼ Ber(pij), pij := 1− e− ∑K k=1 γkΦi,kΦj,k , (1)
which has an alternative representation under the Bernoulli-Poisson link as Ai,j = 1Mi,j≥1, Mi,j ∼ Poisson (∑K k=1 γkΦi,kΦj,k ) . In this expression, Φ is a 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 k, γk (k ∈ [K]) is a positive community activation level indicator that measures the member interaction frequencies featured by community k, and γkΦi,kΦj,k quantifies the interaction rate between nodes i and j through community k. In our practice, we treat γ = [γ1, γ2, · · · , γk]′ as a part of the trainable parameters θ.
In this paper, we focus on another equivalent representation that partitions each edge into the logical disjunctions of K latent binary edges, expressed as
Ai,j = ∨Kk=1Ai,j,k, Ai,j,k ∼ Ber (pijk) , pijk := 1− e−γkΦi,kΦj,k ∀i, j ∈ [N ]1
where ∨ is the logical disjunction (i.e., logical OR) operator and pijk denotes the probability that the interaction of nodes i and j in community k results in an edge. The connection between nodes i and j would establish as long as their interaction in one community forms up an edge, in other words, nodes i and j would be disconnected only if their interactions in ALL communities fail to generate edges. Link function 1 gives the conditional probability pθ(A |Φ). 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 to partition the edges to separate these relations.

heading: 2.1.2 THE GENERATION OF LABELS:
text: In consonance with the graph generative model that establishes the graph from latent communities, we develop the generation process of labels from all relation-specific 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 A and community-affiliation score matrix Φ as inputs and returns K positive-weighted edges: {A(1),A(2), · · · ,A(K)},
1We use the [N ] notation for the integer set {1, 2, · · · , N} throughout the text.
s.t. ∑K k=1 A (k) = A. The partition function follows the form
A(k)i,j = e (γkΦi,kΦj,k)/τ∑ k′ e (γk′Φi,k′Φj,k′ )/τ = ( 11−pijk ) 1 τ∑ k′( 1 1−pijk′ ) 1 τ , k = 1, 2, · · · ,K, ∀i, j ∈ [N ]. (2)
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 proportion that each community-based relation takes in contributing to edge formation. When τ is set sufficiently small, A(1),A(2), · · · ,A(K) would approximate binary factors graphs of G, we hence refer to them as “relational graph factors”. Replacing γkΦi,kΦj,k with Φi,kdiag(γk)Φ ′ j,k generalizes Equation 2 to metacommunity-based edge partition, in this expression, the total number of communities is greater than K, and Φi,k denotes the kth segment in node i’s community-affiliation encoding. The generalized edge partitioner enriches the choices of Φ’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 input2, and outputs g(1)θ (X ∗), g (2) θ (X ∗), · · · , g(K)θ (X∗); g (k) θ (·) := GCNθ(·,A(k)), k ∈ [K].
The function of this design is to learn relation-wise separable node representations. We now qualitatively justify the fulfillment of this requirement. Without loss of generality, let us treat the relational 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 r1, r2, · · · , rk which are uniquely featured with communities c1, c2, · · · , cK . Assuming node u connects to its neighbors v1 and v2 by relations r1 and r2, respectively. Without edge partition, features of v1 would be propagated to v2 in two runs of neighborhood aggregation even if they connects to u with different community identities. This issue is moderated by the relational GCN bank, as the aggregation path (v1, u) would only be sent to the GCN component for relation r1 whereas the path (u, v2) would only exist in the GCN component corresponds to 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-specific sub-representations. This step involves the representation composer module:
REPresentation COMPoser (REPCOMP). Let H(k) := g(k)θ (X ∗) denote the node representations learned from the kth relation, k ∈ [K], and function f(·) denote the representation composer, whose functionality is to project a composite of relation-specific node representations to one representation matrix, i.e., HV = f ( H(1),H(2), · · · ,H(K) ) := GCNθ ( ‖Kk=1H(k),A ) . We could further obtain hG , the vector representation of graph G, by sending the node level representations HV to a graph pooling layer, i.e., hG := GRAPHPOOL(HV).
Taking softmax on the feature dimension of the representation composer’s output gives the uncertainty distribution of labels, from which we 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 pθ(y |A,Φ,X).

heading: 2.2 TRAINING EPM-GCN: INFERENCE AND LEARNING

heading: 2.2.1 THE REPARAMETERIZABLE EVIDENCE LOWER BOUND OBJECTIVE
text: We set the prior distribution of Φ as Φi,k iid∼ Gam(α, β), ∀(i, k) ∈ [N ]× [K], and use a community encoder3 to approximate the posterior distribution p(Φ |A,y): Community ENCoder (CENC). The community encoder models the variational posterior qω(Φ) by a Weibull distribution with shape K and scale Λ, both parameters are learned by a GCN, i.e.,
2The operator ‖ denotes “concatenation”. 3The community encoder is the only module in the inference network.

heading: K ‖Λ = GCNω(X,A). A random sample from qω(Φ) could be created through the inverse CDF transformation of a uniformly distributed variable, given as follows:
text: Φ = Λ ( − log(1−U) )◦(1 K) , Ui,k iid∼ U(0, 1), ∀(i, k) ∈ [N ]× [K].
The operators , and ◦ (in the front of superscript4) 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 = Eqω(Φ) log pθ(yo,A |Φ,X)−DKL(QΦ‖PΦ) = Eqω(Φ) log pθ(yo |A,Φ,X) + Eqω(Φ) log pθ(A |Φ)−DKL(QΦ‖PΦ),
(3)
where the notations PΦ and QΦ represent the prior and the variational posterior distributions of Φ, respectively. The three right hand side terms correspond to the classification task, graph reconstruction, and KL-regularization, we thereby refer to them as Ltask, Lrec and LKL in the sequel. Note that the aforementioned specifications of Φ’s prior and variational posterior, as in Zhang et al. (2018a), yield an analytical expression of LKL.

heading: 2.2.2 THE OVERALL TRAINING ALGORITHM
text: To effectively train EPM-GCNs, we separate the overall training algorithm into an unsupervised pretrain stage, followed by a supervised finetune stage.
The unsupervised pretrain: The ultimate goal of the community encoder is to find a community assignment according to 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,yo) 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 to 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, at which we pretrain the community encoder until convergence by optimizing Lrec + LKL, i.e., updating model parameters ω towards ω∗, which optimizes Eqω(Φ) log pθ(A |Φ) − DKL(QΦ‖PΦ). The variational probability qω(Φ) is learned to approximate p(Φ |A). The heuristic that the unsupervised pretrain is generally supportive to the ultimate goal is that although communities and node categories describe node similarity from different aspects, these two aspects of similarity are semantically mutually informative, i.e., the discovered communities from graph architecture is inherently correlated with node labels, which is suggested by previous work on 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 4.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 supervised finetune: This stage involves iteratively running inference and learning. In the inference step, we fix the generative network, and train the inference network by optimizing the ELBO L, given in Equation 3. Each inference step runs afterM learning steps, where we treat the inference network as stationary and update the generative network by optimizing Ltask. Both L and Ltask are computed over the training set {yo,A,X}. The supervised finetune updates the approximation target of the inference network from p(Φ |A) to p(Φ |A,yo), which finetunes community inference with label supervision, making the subsequent edge-partition more facilitative to the classification task.
The entire training pipeline of EPM-GCNs is summarized in Algorithm 1 (in Appendix A). After running the unsupervised pretrain and the supervised fintune stages, the variational distribution qω(Φ) is trained to approximate the posterior p(Φ |yo,A). We hence approximate the predictive distribution of unobserved labels with Eqω(Φ)[pθ(yu |A,Φ,X)], and estimate it via Monte Carlo estimation. In particular, we estimate p(yu |A,X,yo) with 1S ∑S s=1 pθ(yu |A,Φ(s),X), where Φ(s) iid∼ qω(Φ) for s = 1, . . . , S. For simplicity, we set S = 1 unless specified otherwise.
4Otherwise, the ◦ notation in the context of f ◦ g denotes function composition.

heading: 3 RELATED WORK
text: 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-analytic tasks such as semi-supervised node classification (Hasanzadeh et al., 2019; Wang et al., 2020), community discovery (Sun et al., 2019; Mehta et al., 2019), 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 a black-box prediction network, we use them to develop the generative process of the labels, leading to better interpretability.
GCNs modeling multi-relational data: The general idea is to individually process node representations aggregated from different types of relations. This logistic is 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-El-Haija et al., 2019; Vashishth et al., 2020), or learned via label supervision (Veličković et al., 2018; Gao & Ji, 2019; Ma et al., 2019; Yang et al., 2020). Contrary to these methods which treat edges as given, we jointly model the generation of labels as well as the edges, and systematically model the relations by posterior inference. The inferred relations are then used to partition edges, learn relation-specific sub-representations, and finally optimize the downstream tasks.

heading: 4 EMPIRICAL EVALUATION
text: We compare the proposed EPM-GCNs against related baselines on 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.

heading: 4.1 DATASETS PREPARATION
text: We evaluate EPM-GCNs on 11 benchmarks. For node classification, we use 3 citation networks: Cora, Citeseer and Pubmed. All three datasets provide bag-of-words document representations as node features and (undirected) citations as edges. For graph classification, we use 4 bioinformatics datasets (MUTAG, PTC, NCI1, PROTEINS) and 4 social network datasets (IMDB-BINARY, IMDB-MULTI, 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 1.

heading: 4.2 VISUALIZING LEARNED REPRESENTATIONS
text: To qualitatively assess the proposed model, we visualize the spatial distribution of Φ obtained at the end of the unsupervised pretrain stage (Figures 2(a), 2(b)), and the relation-specific subrepresentations obtained at the end of the supervised finetune stage (Figures 2(c), 2(d)). Node representation 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 5 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 our model’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 sub-representations {g(1)θ (X∗), g (2) θ (X
∗), · · · , g(K)θ (X∗)} are not repetitive, signaling that the proposed model successfully extracts relation-specific representations, which potentially enhance
the discriminative power of node or graph representations and lead to better performances on the downstream tasks.

heading: 4.3 NODE CLASSIFICATION
text: Experimental settings: To make a fair comparison, we use the train/test/validation split standardized by the vanilla GCN (Kipf & Welling, 2017) for Cora, Citeseer and Pubmed datasets. For the community encoder, we adopt a similar encoder structure devised by Kipf & Welling (2016) with softplus activations, which outputs 16-dimensional community-affiliation scores for each node. We set the number of metacommunities K = 4 for Cora and Citeseer and K = 8 for Pubmed dataset, the values of K are selected through cross-validation. The relational graph factors are then obtained through the generalized edge partition. Before being sent to the relational GCN bank, these graph factors are row-normalized by sparse softmax. We implement the relational GCN bank with K single-layer GCNs with ReLU activation, following (Veličković et al., 2018), we set their output dimensions as 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 a 2-layer GCN with 64 hidden units (GCN-64) regardless of the choice ofK. 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 reports EPM-GCN-n’s average performances (± standard error) against the paper records of the average performances of 3 groups of related baselines on the three citation network datasets, where ∗ marks the results reported by Veličković et al. (2018). The first group
(Defferrard et al., 2016; Kipf & Welling, 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 a wide margin. Since removing (i) relational inference and (ii) relation-specific feature learning degenerates EPM-GCN-n to GCN-64, the improvement of our model against GCN-64 could be explained 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 labels from a edge-partition based label generation process. Therefore our improvement with respect to the second group could be attributed to the marginal benefit from our label generative model. The third group of models (Veličković et al., 2018; Gao & Ji, 2019; Ma et al., 2019) employ multi-head
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.

heading: 4.4 GRAPH CLASSIFICATION
text: Experimental settings: For EPM-GCN-g, we implement the community encoder with a 2-layer GCN and produces the latent community-affliation encoding with 100 dimensions. The number of metacommunities is set to 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 5 (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 2 top hidden layers. The 2 ending layers are treated as the representation composer. The remaining implementation details are included in Table 6 (in Appendix C).
Performance comparison: We follow GIN (Xu et al., 2019) to perform 10-fold cross validation for each dataset and report the average classification accuracy (± standard error). As shown in Table 3, we compare the developed EPM-GCN-g with several state-of-the-art baselines for graph classification, 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, 2017), GAT (Veličković et al., 2018), GraphSAGE (Hamilton et al., 2017), and two variants of GIN (Xu et al., 2019): GIN-0 and GIN- . Thanks to our uniquely designed multi-relational inference as well as relation-specific graph representation learning and composition, EPM-GCN-g achieves state-of-theart graph classification performances on 5 out of 8 benchmarks, and the second-best performance on NCI1 dataset, where it outperforms all the other deep architectures. Notably, EPM-GCN-g achieves 75.6% accuracy on PTC dataset with a significant 7.9% improvement over the second place.

heading: 4.5 ABLATION STUDY
text: To further study the marginal benefit of each practice we take in implementing EPM-GCN, as 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. Various input features: We first evaluate model performances with four types of inputs: random noise, hand-crafted features by Xu et al. (2019), community-affiliation scores, and hand-crafted features concatenated with community-affiliation scores. Results are shown in Table 4. The classification 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 communityaffiliation scores are meaningful node representations and comparably informative to the task as
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 Φ as additional node features.
Number of communities: We next study the variation of the model’s performances with growing number of metacommunities. Figure 3 plots the average graph classification accuracy over 10- fold cross-validation against different selections of K ∈ {1, 2, 4, 8, 16}. In the context of graph classification, K denotes the number of all metacommunities with at least one presence among the graphs in the dataset. We could see that the optimal results are typically achieved withK > 1, which is in 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 in 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 EPM-GCN-g-{L1}-{L2} to denote the variant with L1 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 5 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-wise 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-g-{1}-{4} nor EPM-GCN-g-{5}-{0} triumphs 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 be a topic worth studying in the future.

heading: 5 CONCLUSION
text: 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-affiliation scores, and then partition the edges between nodes according to the edge-formation contribution of each communitybased relation with a edge partitioner. Then we obtain the relation-specific sub-representations with the relation GCN bank and finally put them together to make predictions with a representation composer. Extensive qualitative and quantitative experiments on both node and graph-level has been made to demonstrate the efficacy of our model.
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.

heading: A THE PSEUDOCODE OF TRAINING ALGORITHM
text: Algorithm 1: The overall training algorithm of EPM-GCN Data: node features X, observed edges A and observed labels yo Modules : CENC, EPART, RGCN BANK and REPCOMP Parameters: ω in the inference network, and θ in the generative network Initialize ω and θ; while the community encoder is not converged do
Φ,K,Λ← CENC(A,X); Compute Lrec and LKL, given in Equation 3; ω ← ω − ηunsup · ∇ω(Lrec + LKL) ; /* Unsupervised pretrain */
end while the whole model is not converged do
Φ,K,Λ← CENC(A,X); A(1),A(2), · · · ,A(K) ← EPART(Φ,A); for step← 1 to M do
p̂yo ← softmax ( REPCOMP ◦ RGCN BANK(Φ,X,A(1),A(2), · · · ,A(K)) ) ; Compute Ltask, given in Equation 3; θ ← θ − ηsup,θ · ∇θLtask ; /* The learning step */ end Compute L; ω ← ω − ηsup,ω · ∇ωL ; /* The inference step */
end

heading: B PROPERTY OF WEIBULL DISTRIBUTION
text: • Similar PDF with Gamma Distribution The Weibull distribution owns similar probability density functions (PDF) with a gamma one, which makes it flexible to model sparse and nonnegative latent representations:
Weibull PDF: P (x|k, λ) = k λk xk−1e(x/λ) k , Gamma PDF: P (x|α, β) = β α
Γ(α) xα−1e−βx.
(4)
• Easily Reparameterization The latent variable x ∼Weibull(k, λ) can be easily reparameterized as
x = λ(− ln(1− ε))1/k, ε ∼ Uniform(0, 1), (5)
leading to a similar gradient calculation with the Gaussian reparameterization.
• Analytic KL-Divergence Moverover, the KL-divergence between the Weibull and gamma distributions has an analytic expression formulated as
KL(Weibull(k, λ)||Gamma(α, β)) = −α lnλ+ γα k
+ ln k + βλΓ(1 + 1
k )− γ − 1− α lnβ + ln Γ(α).
(6)
C IMPLEMETATION DETAILS
In our experiments, we find the initial state of inference module provided by the unsupervised pretrain stage is essential to EPM-GCN’s performances.
The hyperparameters are either inherited from base models or selected on the basis of crossvalidation. Note that for the graph-level classification task, the parameters are shared across experiments on all datasets. And the reported results are potentially improvable if dataset-specific cross-validations are applied.

Review summaries:
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.  To 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".  The 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.  In 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.  Finally, a community matrix is sampled from the learned posterior and this is used along with the generative network to predict unknown labels.  The 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. 

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.

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.

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.