The Infinite Contextual Graph Markov Model
Authors: Daniele Castellana
Federico Errica
Davide Bacciu
Alessio Micheli
Venue: ICLR 2022 Submitted (2022)
Keywords: graph neurals networks
graph classification
probabilistic models

Abstract: The Contextual Graph Markov Model is a deep, unsupervised, and probabilistic model for graphs that is trained incrementally on a layer-by-layer basis. As with most Deep Graph Networks, an inherent limitation is the lack of an automatic mechanism to choose the size of each layer's latent representation. In this paper, we circumvent the problem by extending the Contextual Graph Markov Model with Hierarchical Dirichlet Processes. The resulting model for graphs can automatically adjust the complexity of each layer without the need to perform an extensive model selection. To improve the scalability of the method, we introduce a novel approximated inference procedure that better deals with larger graph topologies. The quality of the learned unsupervised representations is then evaluated across a set of eight graph classification tasks, showing competitive performances against end-to-end supervised methods. The analysis is complemented by studies on the importance of depth, hyper-parameters, and compression of the graph embeddings. We believe this to be an important step towards the theoretically grounded and automatic construction of deep probabilistic architectures for graphs.

Under review as a conference paper at ICLR 2022
THE INFINITE CONTEXTUAL GRAPH MARKOV MODEL
Anonymous authors
Paper under double-blind review
ABSTRACT
The Contextual Graph Markov Model is deep, unsupervised, and probabilistic model for graphs that is trained incrementally on layer-by-layer basis. As with most Deep Graph Networks, an inherent limitation is the lack of an automatic mechanism to choose the size of each layer's latent representation. In this paper, we circumvent the problem by extending the Contextual Graph Markov Model with Hierarchical Dirichlet Processes. The resulting model for graphs can automatically adjust the complexity of each layer without the need to perform an extensive model selection. To improve the scalability of the method, we introduce a novel approximated inference procedure that better deals with larger graph topologies. The quality of the Iearned unsupervised representations is then evaluated across a set of cight graph classification tasks, showing competitive performances against end-to-end supervised methods. The analysis is complemented by studies on the importance of depth, apper-parametes, and compression of the graph embeddings. We believe this to be an important step towards the theoretically grounded and automatic construction of deep probabilistic architectures for graphs
INTRODUCTION
It can be argued that of the most daunting processes in machine learning is the selection of appropriate syper-parameters for the task at hand. Indeed, due to the data- mata-dependent nature of the learning problem, there usually exists single model configuration that works well in all contexts. The most straightforward approach to mitigate this issue has typically been to rely on standard model selection techniques such as grid and random searches (Bergstra & Bengio 2012), where the range of values to try are fixed a priori by the user. Nonetheless, there has always been an interest in alternative methods that automatically choliteratureose the "right" values for some hyper-parametent (Gershman & Blei| 20122 He et al., [202I) In the Bayesian nonparametric (BNP) literature, which is of particular interest for this work, the complexity of Bayesian models automatically grows with the data (Teh et al. 2006), e.g., a BNP mixture model can adjust the number of its mixtures to better fit the empirical data distribution, thus freeing the user from the burden of choosing the most important (if not all) apprepparaeetrs.
In recent years, much research effort has been devoted to the theoretical and practical development of Deep Graph Networks (DGNs), which originated from Micheli (2009); Scarselli et al. (2009). DGNs can deal with graphs varying topology without the need for human intervention, and they rely on local and iterative processing of information commonly known as message passing; for thorough description of some of the most popular DGNs in the literature (and of the more general graph representation learning field) refer the reader recent surveys on the topic (Bronstein et al. 2017 Battaglia et al. 2018 [aaciu et al. 20206] Wu et al., 2020). Despite most of these methods belonging to the neural world, the Contextual Graph Markov Model (CGMM) stands out as deep. unsupervised, constructive and fully probabilistic model that has shown competitive performances on downstream graph classification tasks (Bacciu et al.) 2018 2020a). CGMM trains a stack of Bayesian networks, where each layer is conditioned on the frozen posteriors of the nodes of the graph computed at previous layers. Each layer optimizes the likelihood of the data using the Expectation Maximization (EM) algorithm (Moon) 1996) with closed-form solutions. Like its neural counterparts, for which the number of hidden units in each layer has typically been selected as hhper--arament parameter, CGMM relies model selection to choose the "reasonable" number of hidden states associated with the categorical latent variables. Differently from the neural methods though, CGMM is amenable to BNP extension, as each layer is essentially conditional mixture model.

---

Under review as a conference paper at ICLR 2022
The main challenge tackle in this work is the adaptation of CGMM to the elegant theoretical framework of BNP methods. in order to automatize the choice of its hyper-parameters, c.g., the number of states. The principal difficulty lies in how to handle the variable-size number of neighbors of each node inside this framework, which in CGMM is solved by (possibly weighted) convex combinations of the neighbors' posteriors. The resulting model, called Infinite Contextual Graph Markov Model (ICGMM), can generate as many latent states as needed to solve the unsupervised density estimation task at each layer. To the extent of our knowledge, this is the first Bayesian nonparametric model for adaptive graph processing. As second contribution, we provide a faster implementation of our method that scales to the social datasets considered in this work while still providing state of the art results. We compare ICGMM against CGMM as well as end-to-end supervised methods eight different graph classification tasks, following a fair, robust and reproducible experimental procedure (Errica et al.) 2020). Results show that ICGMM performs on par or better than the related models. We complement the analysis with studies on the effects of depth and generation of our model's latent states. All in all, we believe that ICGMM is important (if not the first) step towards theoretically grounded and automatic construction of Deep Bayesian Graph Networks.
RELATED WORKS
The fundamental Bayesian nonparametric literature that is relevant to our work relates to the families of Dirichlet Processes (DPs) (Gershman & Blei| 2012) and Hierarchical Dirichlet Processes (HDPs)
(Teh et al. 2006). In its most essential definition, a DP is a stochastic process that defines a probability distribution over other probability distributions. A DP is parametrized by base distribution Go, i.e., the expected value of the process, and a scaling parameter On that controls the concentration of DP realizations around Go (Teh) 2010). In particular, the Chinese Restaurant Process (Aldous [1985). the Stick-breaking Construction (Sethuraman 1994) and the Polya urn scheme (Hoppe) 1984) are all alternative ways to formalize a DP. Moving to HDPs is conceptually straightforward, in that considers the base distribution Go as draw from another DP parametrized by a base distribution H and a scaling parameter y. For a detailed treatment of learning with DP and HDPs, the reader can check a number of tutorials and surveys (Teh et al. 2006 Orbanz & Teh 2010: Gershman & Bleil 20122. Our work shares similarities with the Infinite Hidden Markov Model for temporal series (Beal et al. 2002). with the fundamental differences that causality assumptions have to be relaxed to deal with graphs and that the hidden variables' distributions are conditioned on a varying number of observations.
Most of the recent advances of the graph representation learning field are based on the so called feedforward DGNs (Bacciu et al.] 2020b). These models rely on "spatial" graph convolutional layers, i.e. the state of each node in the graph is determined by applying a permutation invariant function to its neighboring states computed at the previous layers. Combined with the depth of the architecture, these models propagate contextual information across the graph, a process also known as "message passing" (Gilmer et al. 2017). However, to the best of our knowledge, the only neural method for graphs that automatically constructs part of its architecture in a principled way is the pioonering work Michell (2009). In fact, the Neural Network for Graphs (NN4G), known to be the first spatial DGN, relies on the Cascade Correlation learning algorithm (Fahlman & Lebiere 1990) to determine the number of layers to use for the task under investigation.
Instead, despite being loosely related to our work, AutoMI. methods for graphs are yet another way
to automatize the selection of all syper-parameters of a DGN (He et al.) (202). In particular, the Auto-GNN technique relies on Neural Architecture Search to discover, based on performance trends, an adequate configuration for the supervised task (Zhou et al. 2019). We differ from these approaches in two fundamental respects: first, we build upon theoretical grounds rooted in the BNP literature; secondly, we determine the right number of states in a completely unsupervised fashion.
In what follows, we provide formalization of the Infinite Contextual Graph Markov Model. Apart from the technical details, our hope is to show how the cross-fertilization of ideas from different research fields can help us advance the state of the art, both in the theoretical and empirical sense.
2

---

Under review as a conference paper at ICLR 2022
3 METHOD
This Section introduces the details of our method. Since we borrow ideas from two relatively distant fields, we define unified mathematical notation and jargon as well as high-level overview of the CGMM and HDP models to ease the subsequent exposition.
We define graph as tuple g (Vg: Eg. Xg) where Vig is the set of entities (also referred to as nodes or vertices), Eg is the set of oriented edges (u, v) connecting node u to v, and the symbol Xg stands for the set of node attributes associated with the graph g. Also, the neighborhood of node is the set of nodes connected to u, i.e., Nu = for E Vgl(v, (v, u) E }- For the purpose of this work, we will define the (categorical or continuous) node feature of node u with the term Ta E Xg.
3. BASICS OF CGMM
To best understand how and why this work extends CGMM, we now give brief but essential description of its main characteristics. CGMM is, first and foremost, a deep architecture for the adaptive processing of graphs. Like other DGNs, it maps the entities of graph, if not the graph itself, into latent representations. More specifically, we can get one of such representations for each layer of the architecture and then concatenate all of them to obtain richer node and graph embeddings. The latter is usually obtained as a global aggregation of the former.
The second peculiarity of CGMM is that it is constructive, i.e., trained in incremental fashion: after one layer trained, another one can be stacked atop of it and trained using the frozen outputs of the previous layer. This idea is borrowed from NN4G (Micheli, 2009), and it allows CGMM to relax the mutual dependencies between latent variables in a cyclic graph. However, because the local and iterative message passing mechanism used by spatial methods (Micheli) [009] Kipf & Welling 2017) responsible for information propagation across the graph, this relaxation is not restrictive.
Thirdly, the node/graph embedding construction is fully probabilistic and unsupervised, since layer é is represented as the Bayesian network on the left hand-side of Figure A latent variable of, is attached to each node u, and is responsible for the the generation of the node feature Tu. To take into account structural information, the hidden state qu, is conditioned on the neighboring hidden states computed at the previous layer, i.e. the set {g.- u N.). Importantly, the constructive approach allows us to treat the hidden (frozen) states of the previous layer as observable variables. Each layer trained fit the data distribution of node features using the EM algorithm, thus guaranteeing the convergence to a local minima. Once inference is performed, the state of each node is frozen and we can move to the subsequent layer. Lastly, the embedding of each node layer is encoded as the posterior of its hidden state.
3.2 BASICS OF HDP
The HDP is a Bayesian nonparametric prior for the generation of grouped data using different infinite mixture models with shared mixture components. Let P2,, ...... be set of observations that are grouped into J groups, i.e., each observation x,, belongs to the group ju E f1, J). Using
the stick-breaking representation (Sethuraman 1994), the HDP mixture model that generates the
observations can be defined as (Teh et al. 2006):
β 7 Stick(7)
Ju, (TT) ~ J
1,800 DP(co, B) T
qu. (0c) F((
0 H.
where (O.,.) denotes the emission distribution, parametrized by 0g.. that generates the observation Ta. The latent state qu indicates which mixture component should be used to generate Zu. The value of qu is sampled from the distribution J. which stands for the mixture weights of group ju. All (TT))² are obtained from a DP with concentration parameter ag and base distribution 3. Notably, all groups' mixture weights defined on the same set of mixture components, meaning there is a form of parameter sharing across different groups. Finally, we sample the distribution / via the breckknn process Stick(r) of Sethuramann (1994).
To generate possibly infinite number emission distributions, we exploit a prior distribution H that allows us create mixture components on demand. Thanks to the
construction,
3

---

Under review as a conference paper at ICLR 2022
3
j= 1.....C C
11..C'-1
00
π
H
qu
qu
A
1
2
Q2
Ey U
Iu
f-1
nij
[Ma.
E V
V E V/
g E D
g D
CGMM
ICGMM
Figure 1: Differences between layer E's graphical model of the original CGMM and the proposed empty circles, and white boxes
ICGMM. Observable variables blue circles, latent denote prior knowledge. Each ICGMM is an HDP mixture model where the group j for each node observation Zu is pre-determined by the set of states of neighboring nodes f-1 computed at layer t- 1. Contrarily CGMM, the number of values that the latent indicator variable Qu can assume automatically adjusted to fit the underlying data distribution. Dashed arrows denote the flow of contextual information from previous layers through the neighbors of each node
even though infinite number of mixture components can be used, only a finite number of them is istantiated during the inference phase. Hereinafter, we indicate with the symbol C' the number of mixture components that are chosen by the HDP at inference time.
3.3 MODEL DEFINITION
Architecturally speaking. ICGMM shares the same characteristics of CGMM described Section whereas the differences of each layer's graphical model are highlighted in Figure [ In particular, ICGMM assumes that the generation of the node features v,, at each layer is governed by a HDP mixture model. Thus, following the stick-breaking construction detailed in Section 3.2 process of a single ICGMM layer & can be formalized as follows:
3.1
the generative
e 7 Stick(>²) T
_ 00
DP(a
d ji (TT C²-1 TT/
8º H H
Zu d... (0 F(O..).
where we add the superscript the HDP mixture model quantities highlight that they are different at each ICGMM layer. Similarly to the HDP case, we use C to denote the number of states chosen by the model the current layer. When clear from the context, we will omit such a superscript to ease the notation.
In any HDP mixture model, each observation must be assigned to group in advance. In this work, the assignment of node feature to group is not known a priori, but that is the key propagate contextual information across the graph. We select the group j of the feature node I,, based on the neighbors'
observable posteriors computed at the previous layer, i.e., 9v. However, due to known intractability issues, each posterior distribution f-1 is approximated by the
e-1 {q. E [0, 10 v E M.).
4

---

Under review as a conference paper at ICLR 2022
inference phase of the previous layer (see Section 3.4). To stick as much possible to the original CGMM formalism, ju is chosen as the most likely position in the Cf-1-sized -sized macrostate, obtained by averaging the neighbors' probabilities in q',""
Iu = =((N)))
Σ VENU
arg max JE(L..,,O-11 W
It follows that nodes with the same feature may have different latent state c. due to the fact that they are assigned to different groups, i.e., different J. on the basis of their neighborhood: this mimics the role of CGMM neighborhood aggregation but in an HDP mixture model. In the first layer, where previous layer exists, we shall just assume that all node features belong to the same group.
Summing up, depart from the basic CGMM layer of Bacciu et al. (2020a) in more than one way. First and foremost, we do not parametrize nor learn the CGMM transition distribution, which was responsible for the convex combination of neighboring states when computing the E-step of the EM algorithm. Instead, we rely on the most probable choice of the group ju that is encoded by the neighbors' macrostate. Secondly, due the sheer complexity of the Bayesian nonparametric treatment, we do not train the model via EM as done with CGMM; instead, we will exploit Gibbs sampling (Geman & Geman 1984) compute the quantities of interest. Finally, ICGMM retains one important architectural characteristic of CGMM, i.e., it prevents vanishing gradient effects and over-smoothing by default (Bacciu et al. 2020a), thus allowing us to construct deeper architectures that propagate contextual information.
3.4 INFERENCE
The inference phase of every BNP method is meant to estimate the posterior of the model parameters. For each ICGMM layer L, we wish compute the quantities q , πT. and 0¹. Thanks to the incremental construction of the ICGMM architecture, we can do so one layer at a time. It is worth mentioning that the constructive approach of CGMM is not an approximation of a more complex graphical model, rather it is design choice that applies the basic principle of iterative computation underpinning all DGNs. Thus, since each ICGMM layer is an HDP mixture model, we can infer its parameters following the Gibbs sampling schema of Teh et al. (006).. Note that it is also possible to estimate the aperrpprameters a and 7/: whenever that is the case, we shall append a subscript "auto" to our model's name. In the interest of space, report the ICGMM complete Gibbs sampling equations and pseudo-code in Appendix A and respectively.
Graph Embedding Generation. In similar vein with (Baceiu et al. 2020a), we prefer to use the sample distribution of 9u (Eq. 4 at the last iteration, rather than the last sampled state, as an approximation of node u's posterior distribution. This way, we encode more information about state occupancy into node/graph embeddings.
As in Bacciu et al.] (2020a), node embeddings of each layer are represented as unibigrams. unibigram concatenates the posterior of node, i.e., vector called unigram, with its bigram. A bigram counts, for each possible state que how many of u's neighbors are in another state, and is represented as a vector of size C The final graph representation that is fed into the classifier is obtained by concatenation of node unibigrams across all layers followed by global aggregation.
Faster Inference with Node Batches (ICGMM,). Due the sequential nature of the Gibbs sam- pling procedure, a naive implementation is slow when applied to the larger social graphs considered in this work. In the literature, there exist several exact distributed inference methods for HDP (Lovell et al. [012 2012 Williamson et al.) 2013: Chang & Fisher III 2014 Ge et al.) 2015), but their effectiveness might be limited due to the unbalanced workload among workers or the elevated rejection rate (Gal & Ghahramani] 2014).
In this work, we prefer to speed-up the inference procedure by introducing an approximation rather than relying on an exact distributed computation. As suggested in Gal & Ghahramani (2014), an approximated inference procedure may indeed suffice for many problems. What we propose is based on straightforward idea, which is to perform sampling for batch of node observations in parallel. This way, the necessary statistics are updated in batch rather than individually, and matrix operations can be used to gain efficiency. To maintain good trade-off between the quality and speedup, we stick
5

---

Under review as a conference paper at ICLR 2022
to graph the size of our batch. Such a trade-off provides CPU speedup of up to 60x at training time, and we empirically observed that performances remain unchanged with respect to the original version the smaller chemical tasks considered. While this faster version of ICGMM, which we call ICGMM,, f. does not strictly adhere to the technical specifications of the previous section, we believe that the pros largely outperform the cons. The interested reader can refer to Appendix for an analysis of the speedup gains on the different datasets.
3.5 LIMITATIONS
Due to the complexity of the BNP treatment, one limitation of this work that naive Gibbs sampling does not scale to very large datasets. The node independence assumption made by CGMM enables a faster batch computation, which can also be run on GPU. Despite having provided a simple, but approximated, sampling process that guarantees substantial speedup and allows to process graphs of non-negligible size, it would be interesting in the future to explore other inference methods to increase ICGMM's ' speedup, e.g., variational inference (Bryant & Sudderth 2012. Wang & Blei 2012; Hoffmmnn et al. 20133] Hughes et al. 2013). The second limitation of ICGMM is that edge features are not taken into account. While there exist many neural models that do the same, we know that CGMM and its variant E-CGMM (Atzeni et al. (021) can deal with discrete and arbitrary features, respectively. Our research directions for the future will investigate these aspects, providing an exact and efficient version of ICGMM that can process edge features as well.
4 EXPERIMENTS
We evaluated the performances of ICGMM using the fair, robust, and reproducible evaluation setup for graph classification defined in Errica et al. (2020). consists of an external 10-fold cross validation for model assessment, followed by an internal hold-out model selection for each of the external folds. Stratified data splits were already provided; in this respect, we had re-assess CGMM and E-CGMM (Atzeni et al. 2021). recently proposed variant, by trying all the hyper-paramed specified in the original papers (in particular, the values of C tried were 5, 10 and 20). We first experiment on the three chemical datasets D&D (Dobson & Doig 2003). NCI1 (Wale et al. 2008) and PROTEINS (Borgwardt et al. 2005), where node features represent atom types. Then, we consider social datasets, including IMDB-BINARE IMDB-
REDDIT-
REDDIT-
MULTI-5K, and COLLAB (Yanardag & Vishwanathan 2015). where the degree of each node is the sole continuous feature available. All datasets are publicly available (Kersting et al. 2016) and their statistics are summarized in Appendix C Finally, we relied on Pytorch Geometric (ey & Lenssen 2019 for the implementation of our method!
Apart from CGMM's 's variants, we will compare ICGMM against the following end-to-ent supervised neural architectures for graphs: DGCNN (Zhang et al. 2018). DIFFPOOL (Ying et al. 2018). ECC
(Simonovsky & Komodakis 2017). GIN (Xu et al. 2019). GRAPHS AGE (Hamilton et al. (017). and a structure-agnostie baseline method BASELINE, described in Errica et al. (2020), which was competitive on a number of benchmarks. We recall that these supervised methods construct the graph embeddings leveraging the supervision information coming from the target label; on the contrary, ICGMM embeddings are built in an unsupervised and constructive way, thus this represents a challenging comparison for our approach. Results for the supervised models are taken from (Errical et al. 2020).
We have discussed how ICGMM can automatize the choice its syper-parameters. e.g., the size of the latent representation. In general, the choice of the Bayesian hyper- pnner-parameters is much less important than that of the number of states C, as in principle one can recursively introduce hyper-priors over these syper-parameters (Bernardo & Smith 2009; Goel & Degroot 1981). That said, being this the first work to study HDP methods in the context of graph classification, we both i) explored the hyper-parament parameter space to best assess and characterize the behaviour of the model and ii) introduced hyper-priors to estimate an and 7 at each layer, thus further reducing the need for an extensive model selection.
For the chemical tasks, the prior H over the emission parameters O was the uniform Dirichlet distribution. The range of ICGMM hyper-parameters tried in this case were: number of layers
The code rigorously reproduce our results is provided in the supplementary material.

---

Under review as a conference paper at ICLR 2022
Table 1: Results on chemical datasets (mean accuracy and standard deviation) are shown. The best performances are highlighted in bold.
D&D
PROTEINS
BASELINE
78.4 1: 4.5
69.8 1 2.2
75.8 1 3.7
DGCNN
4.3
76.4
72.9
DHTPOOL
3.5
76.9 1.9
T3.7
3.5
4.1
T2.3
GIN
75.31.2.
75.3 1..11:21
80.0114 1.4
73.3
4.0
GRAPHSAGE
2.0
76.0
73.0
4.5
CGMM
3.4
76.2 2.0
74.0
3.9
E-CGMM
4.1
78.5 1.7
73.3
ICGMM
4.3
16.5
72.7 3.4
ICGMM,
5.6
7.77
73.3
ICGMMauto
76.3
77.6 1.5
3.9
JCGMM Fauto
3.8
76.1
73.2
Table 2: Results on social datasets (mean accuracy and standard deviation) are shown, where the node degree is used as the only node feature. The best performances are highlighted in bold.
IMDB-B
IMDB-M
REDDIT-SK
BASELINE
70.8
5.0
19.1 + 3.5
82.2 = 3.0
52.2 = 1.5
70.2 + 1.5
DGCNN
3.4
7L.
DIFEPOOL
68.4 3.3
45.6
3.4
89.1 1 1.6
53.8 1 1.4
68.9 1 2.0
67.7
43.5
3.1
GIN
3.9
18.5
3.3
89.9
1.9
56.1
75.6 2.3
GRAPHSAGE
68.8
47.6
3.5
84.3
50.0 133
73.9
CGMM
72.7
47.5
3.9
77.32
2.2
E-CGMM
70.7= 3.8
48.3
4.1
89.5 = 1.3
53.7 = 1.0
77.45
2.3
ICGMM,
73.0
48.6 3.4
91.3 1.8
56.5 1.9
78.6 2.8
ICGMM
71.8
3.8
1.7
78.9
E (5, 10, 15, 20), og E (1,5). (1, unibigram aggregation E (sum, mean]. and Gibbs sampling iterations E {10, 20, 50}. Instead, for the social tasks implemented Nammal prior H over a Gaussian distribution. Here the prior is parametrized by the following hyper-priors: pa. the mean node degree extracted from the data; λo, which is inversely proportional the prior variance of the mean; and (ao, bo). whose ratio fo
as represents the expected variance of the data. The ICGMM hyper-parameters here were: number of layers E (5, 10, 15, 20). Ào E {le-6), ap {1.}. bo {0.09, 1.), og E 5. 10). (2, 10). unibigram aggregation {sum, mean). and Gibbs Sampling iterations E [100). To further automate learning of ICGMM's unsupervised layers, we place uninformative Gamma rate 0.01) hyper-priors on both of,77 7 hyper-parameters. To prevent the model from getting stuck a local minimum on COLLAB (due to bimodal degree distribution and large variances), tried Ao E (lc-4, le-5).
To conclude, we list the paramttars tried for the one-layer MLP classifier trained on the unsupervised graph embeddings: optimizer E (Adam), batch size E (32), hidden units {32, 128), learning rate E (1e-3), L,2 regularization E Se-4,, epochs E (2000). ReLU activation, and early stopping validation accuracy with patience 300 chemical tasks and 100 social ones.
RESULTS
The empirical results on chemical and social benchmarks are reported in Tables I [add] respectively, There are several observations to be made, starting with the chemical tasks. First of all, ICGMM performs similarly to CGMM, E-CGMM, and most of the supervised neural models; this suggests that the selection of ja based on the neighboring recommendations is subtle but effective form of information propagation between the nodes of the graph. In addition, results indicate that we have succeeded in effectively automatizing the choice of the number of latent states without compromising the accuracy, which was the main goal of this work. Finally, ICGMM, performs well as the exact version, and for this reason we safely applied the faster variant to the larger social datasets (including IMDB-B and IMDB-M to ease the exposition).
7

---

picked the Under review as a conference paper at ICLR 2022
Moving to the social datasets, observe that ICGMM achieves better average performances than other methods on IMDB-B, REDDIT-B and COLLAB. One possible reason for such an improvement with respect CGMM variants may be how the emission distributions hand, and differently from the chemical tasks, CGMM and E-CGMM use the k-means algorithm (with fixed k=C), to initialize the mean values of the C' Gaussian distributions, which can be stuck in a local minimum around the most frequent degree values. One the other hand, ICGMM adopts fully Bayesian treatment, which combined with the automatic selection of the latent states allows better model outliers by adding new state when the posterior probability of data point is too low.
initializedd. On the one
In what follows, we will try shed more light into the improved generalization performances of ICGMM, by analyzing the exact model from a layer-wise perspective.
76.0
average C per layer
85-
accuracy
80-
75.0
74.5
75-
average
DCMM w. C-20-11 TR
74.0
70-
JCGMM w. es: 5. TR
C-20 VL
73.5
3.
1112 111111114111117111122
layer
(a) Effect of depth on training/validation accuracy
(b) Average VI. accuracy (solid line) number of chosen states (dashed line) w.r. ao and y values
Figure 2: Figures| 2a and chosen states on NCI1.
2b analyze the relation between depth, performances, and the number of
On the effectiveness of depth and hyper-paramen parameters. To confirm our intuition about the benefits of the proposed information propagation mechanism, Fagure the NCII training and validation performances of both CGMM and ICGMM best ICGMM configuration on the first external fold, and we compared it against the CGMM configuration with the most similar performances. Note that C = 20 was the most frequent choice of CGMM states by the best model configurations across the 10 outer folds: this is because having more emission distributions to choose from allows the CGMM model find better local minima, whereas JCGMM can automatically add states whenever the data point's sampling probabilities are too low. We trained the same classifier different depths, and we averaged scores across the 10 outer folds. We observe that the validation performance of both models are similar, with an asymptotic behavior as we reach 20 layers; it follows that depth remains fundamental to improve the generalization performances (Bacciu et al., 2020a). Importantly, we see that gap between ICGMM training and validation scores thinner than its non-BNP counterpart, suggesting that the classifier less prone overfitting the data.
add more layers. For simplicity,
We now study how ICGMM behaves as we vary the main syper-parameters ag and y. We continue experimentation on NCII; Figure 2b depicts the average validation performance and number of states over configurations and folds, subject to changes of ag and values. The trend indicates how greater values for both hyper-parameten achieve, average, better validation performance. Also, smaller values of the two syper-parameter tend to strongly regularize the model by creating fewer states, with consequent reduction validation accuracy. The relation between the number of states and these hyper-parameters remains consistent with the mathematical details of Section 3
On the quality of graph embeddings. So far, we have argued that ICGMM selects the appropriate number of states for its unsupervised task at each layer. As matter of fact, Figure 3a reports such a statistic on the same NCII configuration as before: ICGMM preferred a lower number of latent states than CGMM, i..., around per layer. In turn, the resulting graph embeddings become much smaller, with important savings in terms memory footprint and computational costs to train the subsequent classifier. Figure 3h displays the cumulative graph embedding size across layers, using
8

---

Under review as a conference paper at ICLR 2022
CGMM C=20
17.5
graph embedding size
5.
ICGMM
15.0
6000
chosen
12.5
C-20
10.0
ICGMM
ICGNM w. os: K
4000
7.5
1011 111101111111111111111111
10 101112133 101113311111117780000 layer
layer
(a) # states chosen at each layer
(b) Cumulative graph embedding size on NCII
Figure 3: We show comparative results on the size and quality graph embeddings between CGMM and ICGMM. Overall, ICGMM generates ~ 0 unused latent states, with consequent savings in terms of memory and compute time the classifier with respect to CGMM. See the text for more details.
the unibigram representation without loss generality. We see that, when compared with CGMM (C=20), the size of graph embeddings produced by ICGMM is approximately 7% of those of the original model, while still preserving the same performance as CGMM.
On the automatic estimation of af and 7-. We conclude this work with a performance analysis of the fully automated versions of ICGMM and ICGMM,, namely those with an "auto" " subscript observe statistically significant performance differences
in Tables and 2 in particular, with respect to the original models. By estimating all prreerpprameters of our models using uninformative priors, almost always (but for COLLAB) managed to avoid the model selection for the unsupervised graph embeddings creation. In turn, this amounted to a 6x reduction in the overall number of configurations be tried, but most importantly it frees the user from making hard choices about which configurations of hyper-parametent to try. Additionally, we observe that the number of chosen states and the consequent graph embedding size very similar that of ICGMM with 5, 3, but this time the two hyper-parameter have been automatically adjusted by the model on the basis of the data.
To sum up, we have shown that: our model has very competitive performances with respect the state of the art; ii) the information propagation mechanism introduced in the HDP is effective; iii) the model can automatically selects the number of states; iv) we can get much lower memory and computational footprints due to the previous points without sacrificing the predictive performance; v) we can fully automatize the choice the hyper- parammerseessrs using uninformative priors, which drastically reduces the cost of the model selection phase.
CONCLUSIONS
With the Infinite Contextual Graph Markov Model, have bridged the gap between Bayesian nonparametric techniques and machine learning for graphs. We have described how our approach can automatically adjust the number of states and most hyper-parameters of each unsupervised layer, thus freeing the user from the burden of selecting them a priori. As the empirical analyses show, not only can the model exploit depth to increase its generalization performances, but it also produces smaller embeddings than CGMM, with consequent savings in terms of memory footprint and training time of the subsequent classifier. For these reasons, we believe that ICGMM represents first relevant step towards the automatic construction of fully probabilistic deep learning models for graphs.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
To ensure that the results in this paper are reproducible, we relied on the PyDGN library (https: : pypi. orgg porg/rroooooooooooooooooooooo// /pro ject/ /PDDGN/). which automatically handles both data and experiment pipelines, thus letting the researcher focus on the model definition. We follow the robust and reproducible settings of Errica al. (2020); Section further experimental details and the hyper-parameters tried for the models considered. Likewise, the appendix contains a detailed description of the inference procedure, as well as the pseudocode that has been implemented in the supplementary material. The data splits used can be retrieved from Errica et al. (2020), but they are nonetheless stored in the supplementary material alongside the code for ICGMM. To completely reproduce the experiments (model selection, model assessment) and the data pre- prepprocessing steps, we have also provided the necessary PyDGN configuration files.
REFERENCES
David Aldous. Exchangeability and related topics. École d' Ésé de Probabilités de Foont-Flour XII1-1933, pp. 1-198. Springer, 1985.
Daniele Atzeni, Davide Bacciu, Federico Errica, and Alessio Micheli. Modeling edge features with deep bayesian graph networks. Proceedings of the International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEFE, 2021.
Davide Bacciu, Federico Errica, and Alessio Micheli. Contextual Graph Markov Model: A deep and generative approach to graph processing. Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pp. 294-303. PMLR, 2018
Davide Bacciu, Federico Errica, and Alessio Micheli. Probabilistic learning on graphs via contextual architectures. Journal of Machine Learning Research, 21(134):1-39 2020a.
Davide Bacciu, Federico Errica, Alessio Micheli, and Mareo Podda. gentle introduction to deep learning for graphs. Neural Networks, 129:203-221, 9 2020b.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, and others. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1rXhv:1806.01261 2018.
Matthew Beal, Zoubin Ghahramani, and Carl Edward Rasmussen. The infinite hidden markov model. Proceedings of the 16th Conference on Neural Information Processing Systems (NIPS), 1: 577-584, 2002.
James Bergstra and Yoshua Bengio. Random search for machine learning research, 13(2):281-30) 2012.
optimization. Journal of
José M Bernardo and Adrian FM Smith. Bayesian theory, volume 405. John Wiley & Sons, 2009.
Karsten M Borgwardt, Cheng Soon Ong. Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl_I) I): i47-i56. 2005.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):25. 18-42, 2017.
Michael Bryant and Erik Sudderth. Truly nonparametric online variational inference for hierarchical dirichlet processes. In Proceedings of the 26th Conference on Neural Information Processing Systems (NIPS), 2012.
Jason Chang and John W Fisher III. Parallel sampling of hdps using sub-cluster splits. In Proceedings of the 28th Conference on Neural Information Processing Systems (NIPS), 2014.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783 2003.
10

---

Under review as a conference paper at ICLR 2022
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
Scott E. Fahlman and Christian Lebiere. The Cascade-Correland learning architecture. In Pro- ceedings of the 3rd Conference Neural Information Processing Systems (NIPS), pp. 524-532, 1990.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In Representation Learning on Graphs and Manifolds Workshop, International Conference on Learning Representations (ICLR), 2019.
Emily B Fox, Erik B Sudderth, Michael Jordan, and Alan S Willsky. The sticky hdp-hmm: Bayesian nonparametric hidden markov models with persistent states. Preprint, 2007.
Emily Fox, Erik B Sudderth, Michael Jordan, and Alan Willsky. An hdp-hmm for systems with state persistence. In Proceedings of the 25th International Conference Machine Learning (ICML), pp. 3 312-319, 2008.
Yarin Gal and Zoubin Ghahramani. Pitfalls in the use of parallel inference for the dirichlet process. In Proceedings of the 31st International Conference on Machine Learning (ICML), volume 32, pp. 208-216. PMLR, 22-24 Jun 2014.
Hong Ge. Yutian Chen, Moquan Wan, and Zoubin Ghahramani. Distributed inference for dirichlet process mixture models. Proceedings of the 32nd International Conference on Machine Learning, volume 37, pp. 2276-226622 2284. PMLR, 2015.
Stuart Geman and Donald Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, PAMI-6 (6):721-741, 1984.
Samuel J Gershman and David M Blei. A tutorial on bayesian nonparametric models. Journal of Mathematical Psychology. 56(1):1-12, 2012.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp. 1263-1272. PMLR, 2017.
Prem K. Goel and Morris H. Degroot. Information about hyperparamters in hierarchical models. Journal of the American Statistical Association, 76(373):140-147 1981. ISSN 01621459. URL http:// / www. jstor.srrrr....... wwt.org/gtbeleeeeeeeoeeeoo/
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Advances in Neural Information Processing Systems (NIPS), pp. 1024-1034. Curran Associates, Inc., 2017.
Xin He, Kaiyong Zhao, and Xiaowen Chu. Automl: survey the state-of-the-art, Knowledge- Based Systems, 212:106622, 2021.
Matthew Hoffman, David M Blei, Chong Wang, and John Paisley, Stochastic variational inference. Journal of Machine Learning Research, 14(5), 2013.
Fred Hoppe. Pólya-like urns and the ewens' sampling formula. Journal of Mathematical Biology, 20(1):91-99) 194, 1984.
Michael Hughes, Dae Il Kim, and Erik Sudderth. Reliable and scalable variational inference for the hierarchical dirichlet process. In Proceedings of the 18th International Conference Artificial Intelligence and Statistics (AISTATS), 2015.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. URL http:: /ttp:://graphkeeeeees cs. tu- dor-toumu
del

---

Under review as a conference paper at ICLR 2022
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations (ICLR), 2017.
Dan Lovell, Ryan P. Adams, and Vikash K. Mansinghka. Parallel markov chain monte carlo for dirichlet process mixtures. In Workshop on Big Learning, Advances Neural Information Processing Systems (NIPS), 2012.
Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20(3):99-5511 2009. Publisher: IEEE.
Todd K Moon. The expectation-maxxinzztion algorithm. IEEE Signal Processing Magazine, 13(6): 47-60, 1996. Publisher: IEEE.
Radford M Neal. Markov chain sampling methods for dirichlet process mixture models. Journal of computational and graphical statistics, 9(2):249-265, 2000.
Peter Orbanz and Yee Whye Teh, Bayesian nonparametric models. Encyclopedia of machine learning. 1. 2010.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1) 20(1):61-88) 2009. Publisher: IEEE.
Jayaram Sethuraman. constructive definition of dirichlet priors. Statistica sinica, pp. 639-650, 1994.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters convolutional neural networks graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 29-38, 2017.
Yee Whye Teh. Dirichlet Process, pp. 280-287. Springer US, Boston, MA, 2010. ISBN 978-0-387- 30164-8.
Yee Whye Teh, Michael I Jordan, Matthew J Beal, and David M Blei. Hicrarchical dirichlet processes. Journal of the american statistical association, 15666)):156-11 1581,, 2006.
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Chong Wang and David Blei. Truncation-free stochastic variational inference for bayesian nonpara- metric models. In Proceedings of the 26th Conference on Neural Information Processing Systems (NIPS), 2012.
Sinead Williamson, Avinava Dubey, and Eric Xing. Parallel Markov chain Monte Carlo for nonpara- metric mixture models. Proceedings of the 30th International Conference on Machine Learning (ICML), volume 28, pp. 98-106 PMLR, 2013.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. Proceedings of the 21th ACM International Conference Knowledge Discovery and Data Mining (SIGKDD), pp. 1365-1374, 2015.
Zhitao Ying, Jiaxuan You. Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems (NeurIPS), pp. 4810- Curran Associates, Inc., 2018
12

---

Under review as a conference paper at ICLR 2022
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning archi- tecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 4438 1188-4445,20 2018.
Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu. Auto-gnn: Neural architecture search of graph neural networks. arXiv preprint arXiv: N0tv:/909.000 1909.03184, 2019.
13

---

Under review as a conference paper at ICLR 2022
A ICGMM GIBBS SAMPLING PROCEDURE
HDP Gibbs sampling is an iterative procedure Neal 2000; Teh et al. 2006 Fox et al. 2007 that we to estimate all node latent states and ICGMM's 's parameters at each layer. Hereinafter, to keep the notation less cluttered, we shall omit the superscript e of the current layer and define C=C--1
Sampling Qu- 'he conditional distribution qu of du given all the other variables is given by:
P(q.- = c Ju = j. j.q"".". 3,3,0, x (ao +
(e), C (L....,C++l
(4)
where recall that C denotes the number of current states in the mixture model, f is the p.d.f. associated with emission distribution F()) and the distribution тy has been integrated out (Teh et al. 2006). Here, Rje indicates the number of observations assigned so far to the mixture component c of group j. Whenever we have that qu C' + 1, we create a new state and sample a new emission distribution Oc-1 from H. On the contrary, if at the end of an iteration there are no observation of any group associated with a certain mixture component, we can remove that mixture component and decrement the current number of states C. This is how ICGMM varies in complexity to fit the data distribution. Also, note that q will be used in Eq. at the next layer & + When inferring the latent states of new data point, no statistics of the model are updated.
Sampling B. In the HDP stick breckbbe representation that we use to define the ICGMM in Section
3.3 we require an auxiliary variable method to sample the base distribution & (Teh et al. 2006). We therefore introduce the auxiliary variables m = {mze Vj E {1,..., ......,Cy C), Vc {1,.... ........y. CF} that need to be sampled in order to compute B. However, being mij dependent
nies the sampling step
of these variables is very inefficient for large values of ie as the probability values are proportional the Stirling number of the first-kind s(nje: -) (Fox al. 2008). Luckily, can avoid this step by observing that the value ji corresponds to the number of tables where dish Zu = C is served at restaurant j in the Chines Restaurant Franchise (CRF) representation (Teh et al., 2006 Fox et al.) 2007). Thus, we can compute each miee by simply simulating the table assignments process. We recall that, in the CRF representation, each customer (i.e., observation) of each restaurant (i.e., group) is assigned to a table where just a single dish (i.e., mixture component) is served. Thus, while all customers sitting at the same table must be eating the same dish, there can be multiple tables serving the same dish as well.
Knowing that customer u eating the dish qu = c, its table assignment ly can be sampled according to:
[nj... Vt s.t. =;
P(t.. = = = j. 3, on) &
(5)
LapBe,
= tnew,
where 1- represents the tables assigned to all the other nodes except u. Cye E speciffes the dish assigned to table t at restaurant j and n denotes the number of customers (except u) sitting at table t of restaurant j. Since we know the dish qu selected by the customer u, there is zero probability that the customer sits to a table where that dish is not served. The creation and deletion of tables is very similar that of Eq. 4 so we skip in the interest of the exposition and refer to the pseudocode in Appendix B for a complete treatment.
At last, after computing mije as described above (i.e., Ev Maze = =c), the base distribution P sampled from:
B q, m Dir(
m
mjc, 7),
where Dir stands for the Dirichlet distribution.
Sampling 0. To update the emission parameters 0, we rely on its posterior given and æ:: P(0 x. o h(..))
II Valqu=e
f( 0c).
By choosing the family of the base distribution H to be conjugate prior for F, e.g., a Dirichlet distribution for Categorical emissions or a can compute the posterior in closed form.
distribution for Normal emissions, we
14

---

Under review as a conference paper at ICLR 2022
Let the emission distribution be categorical distribution with M possible states. When creating new state, we can sample the emission parameter according to a Dirichlet distribution, which is a conjugate prior for the categorical distribution:
0. ~ Dir(n, 7),
(8)
where the subseript e indicates the mixture component. Thanks to the conjugate prior, the emission parameters can be updated by sampling Dirichlet posterior distribution:
8 Dir(n + ..:..., N )
where N indicates the number of times the visible label m has been associated with the latent state i.c., N E.. U/qu = cAA I. m..
Similarly the categorical case, let the emission distribution be univariate Gaussian. In this case, for each state, we can sample the emission parameter according to a Normal-Gamnn distribution:
Re (uo. 1/(A
(10)
Gamma (ao. bo);
(11)
where the subscript e indicates mixture component ant т. is the inverse of the variance. Then, the emission parameters of the Gaussian can be updated as follows:
AoHa No
1
Rke ~ N
(12)
do No
(Ao + No)T
T' ~ Gamma
a0 + 2 bo + NNoso +
No
AoNolEe - n002 An + No =
(13)
where Ne indicates the number of visible labels associated with the latent state c (i.e., No Σ. Ulq c)), Te is the mean of the data associated with the class c (i.e., T. = N. Evalgu=e Bud, and 8, the variance of the data associated with the class (i.e., 8, N: Evulgu= )ra)2). ))
Sampling ag- Following (Teh et al. 2006), the concentration parameter og can be updated between Gibbs sampling iterations by exploiting auxiliary variable schema. Assume that ag has Gamma prior distribution Gamma(a, b) (i.e., og ~ Gamma(a, b)). Then, we define the auxiliary variables W1, w1..... wh and s...... $6, where each w, variable takes value between 0 and 1, and each sy is binary variable. Then, the value of og can be sampled according to the following schema:
Wj Beta(ao + L, n,,,),,
(14)
n2
8j Bernoulli
(15)
M1. 000
C
a. Gamma
m.
Σ
5j,b
Σ
log wi
(16)
/=1
J=1
where ny. is the number of costumer cating in the j-th restaurant, and m. is the total number of tables all the restaurants.
Sampling Similarly, assuming that the hyperparameter has gamma prior distribution
Gamma(a' b') (i.e., 7 Gamma (a,, 6')), its value can be updated by following the auxiliary variable schema below (Teh et al. 2006 Fox et al. 2008):
Beta(y + 1, m..))
(17)
m.
Bernoulli
(18)
m. + +
Gamma(d + C - p,U' b' logr).
(19)
15

---

Under review as a conference paper at ICLR 2022
B ICGMM PSEUDOCODE
To facilitate the practical understanding of our model, we provide the pseudocode of the Gibbs sampling method employed in this work.
Algorithm 1 Gibbs sampling method for exact ICGMM
Require: A dataset of graphs D .g...... 9N JN Initialize C [013 (where 01 H) T, (for all restaurant j). q repeat
and n ñ
for E D do
For each graph For each node
for V. do
assign the restaurant
Ju + w(W..)
D Can done once
// assign the dish
n.. + Ringu
> qu * J., remove qa from the counting D Sample the dish according to Eq. ( b Create new state
- SAMPLING(J.. 0,,
if 9u is new then
Onew H
(0me)
- +1
Njaa + 0 (j.
> Initialize the counters
end if
Bjaou + niuqu
Update the counter
Il assign the table
Rjata < Riuuu -1 tu f- SAMPLING( qu, c, n. 3,, 0o) if fu is new then
If * remove from the counting
Sample the table according Eq. Create a new table
T, Tj (tu}
Siaaa t- 9n
Save the dish-table assignment Update the table count & Initialize customer counter
Miuua 5- Milsu
Migu. f-
end if R. Aguly +1
end for
I/ remove unused dishes
for e E (1...., C7} do
I 1=1 Aie 0 then
b No customers cat the dish c
0 + 0 {0c}
C + C
end if
end for
// remove empty tables for E {1, ..., C. do
for T do
if nit then
D customers eat the table restaurant
T + T, (t)
Mjjr, Mijge
end if for
end
// update model parameters
3 SAMPLING q, m))
> Sample according to Eq.
0 + SAMPLING( x))
> Sample according to Eq.
if ICGMMauss. then
Oig + SAMPLING(o., n2)
Sample according to Eq.
44 17
SAMPLING(a' m)
Sample according Eq.
18
19
until stopping criteria
16

---

Under review as a conference paper at ICLR 2022
C
DATASET STATISTICS
Below we report some statistics for the chosen benchmarks.
Table 3: Dataset statistics.
Graphs
# Classes
# Nodes
Edges
# Node labels
SOCIAL CHEM.
DD NCII
1178
2
284.32
715.66
89
4110
2
29.87
32.30
37
PROTEINS
1113
2
39.06
72.82
3
IMDB-BINAR
1000
2
19.77
96.53
IMDB-MULTI
1500
3
13.00
65.94
BEDDIT-BINARY
2000
2
429.63
497.75
REDDIT-SK
4999
5
508.82
594.87
COLLAB
5000
3
74.49
2457.78
D SPEEDUP GAINS WITH FASTER INFERENCE
We compare the performances of the exact version of ICGMM against the faster implementation. As we can see, the speedup increases for the datasets with larger average number nodes (see Table 3)
Table 4: Approximate speedup between the exact ICGMM and the faster version on all datasets.
ICGMM
ICGMM,
ref.
min/max
CHEM.
DD
1x
17.8x/30.8x
NCI1
1x
3.1x/5.1x x
PROTEINS
1X
4.2x/5.7x
IMDB-B
IX
2.4x/5.1xx
SOCIAL
IMDB-M
1X
1.6x/3.6x
REDDIT-B
1X
11.1x/45.60
REDDIT-5K
1X
36.7x/60.6x
COLLAB
1X
3.1x/8.6x
17


Reviews:
[{"review_id": "tZNapdW0XXi", "reviewer": "Reviewer_ynws", "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": "The proposed method is very interesting, since it's an unsupervised method for automatic selection of network structure, as opposed to the more popular supervised AutoML techniques. Traditional inference mechanisms for BNP-based methods are costly to run on larger datasets, hence authors propose a faster Gibbs sampling-based inference method. \n\nThe proposed method performs impressively against supervised learning-based methods and the parametric version of the method, i.e. CGMM. Given the unsupervised nature of the method, the results are encouraging for future work in the direction of BNPs. \n\nI lean towards acceptance of this paper, as it has the potential to encourage research on the integration of BNP methods with Deep Neural Networks. ", "summary_of_the_paper": "Authors propose a Bayesian Non-Parametric (BNP) method to automatically learn the \"structure\" of the graph neural network. Specifically, the authors have proposed a Hierarchical Dirichlet Process model for the automatic inference of latent code's size. ", "summary_of_the_review": "The authors propose an unsupervised Bayesian Non-Parametric method for GNN, which learns the GNN structure in an unsupervised fashion. For scaling-up, the authors propose a faster Gibbs Sampling based inference method. Experimental results indicate the strong performance of the method as compared to supervised learning methods. Overall, the direction is very interesting and could inspire future work at the intersection of BNP and Neural Networks. ", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "kZ88NqefVPG", "reviewer": "Reviewer_mmkq", "summary": "", "questions": "", "limitations": "", "rating": 5, "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:\n\n1. The idea of using Hierarchical Dirichlet Processes is quite intuitive.\n\nThe key idea of the paper is to use HDP to automatically decide the size of latent representations in the Contextual Graph Markov Model. To me, the idea of using HDP is intuitive.\n\n2. The proposed model is theoretically sound.\n\nFor Hierarchical Dirichlet Processes, one critical problem is inference, and the authors use Gibbs sampling to deal with that as described in appendix, and I think the derivation is theoretically sound.\n\nWeaknesses:\n\n1. The novelty of the paper is insufficient.\n\nThe key idea is on using HDP in the Contextual Graph Markov Model. However, the idea is not new, as it is a quite common practice to use HDP in unsupervised generative models for automatic model selection. For example, in clustering, HDP has been widely used to automatically decide the number of clusters. Similarly in topic modeling, many works use HDP to decide the number of latent topics. Given these well-known efforts in machine learning, I think the idea of extending the Contextual Graph Markov Model with HDP is not so innovative.\n\nAlso, this paper uses Gibbs sampling for inference, which has also been widely used for HDP, and the Gibbs sampling procedure derived in this paper is not so different from those used in existing works. In this sense, this paper doesn't provide many new insights or ideas in terms of model inference.\n\nTherefore, although the paper has some interesting ideas, I think the overall novelty is insufficient.\n\n2. The improvement over existing methods is not significant.\n\nIn the experiment, the authors compare iCGMM against many existing methods on the task of graph classification. However, on chemical datasets, the results of iCGMM are worse than a few baseline methods (e.g., GIN and DiffPool). On social datasets, the improvement over these baseline methods is also insignificant, given the high standard deviation. In particular, iCGMM only slightly outperforms CGNN, making the advantage of applying HDP to CGMM less convincing.\n", "summary_of_the_paper": "This paper is an extension of the Contextual Graph Markov Model, a deep unsupervised probabilistic approach for modeling graph data. The key idea is to leverage Hierarchical Dirichlet Processes, which enables the proposed approach to automatically choose the size of each layer’s latent representation. The authors conduct experiment on graph classification tasks, and the results are quite promising.\n", "summary_of_the_review": "In summary, this paper applies HDP to CGMM, which is intuitive and theoretically sound. However, the idea of using HDP is not new in unsupervised generative models, and the improvement of iCGMM over CGMM seems insignificant. Thus, I would lean towards a weak reject.", "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": "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": "4fV2M0P4PS8", "reviewer": "Reviewer_aqe6", "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": "Strengths:\n1. The paper is well written and easy to follow.\n2. Selecting an optimal model size (trainable parameters of each neural network) is essential to obtain reasonable performance. However, it involves an expensive model selection procedure. This work investigates automatic model size selection without compromising model performance. \n3.  Experimenting with chemical and social network datasets, the authors show the method perform comparable performance with the state-of-the-art baselines for graph classification problem.\n\n\nWeakness:\n1. However, the proposed method is restricted to a specific type of architecture, which is the Contextual Graph Markov model. Though the authors discussed why they have selected this architecture, it somewhat limits the applicability of the approach.  Other than CGMM, there exist powerful adaptive graph representation techniques like GraphSage. Can their proposed method be extended to automate model size selection for those neural models?\n\n2. Please discuss how likely it is to be extended to unsupervised generative model-based (VAE) techniques to obtain a representation of a graph?\n\n3. The authors should provide some comparison with AutoGNN /DGN types of methods in terms of performance accuracy and time of execution.\n\n4. The authors should provide execution time comparison with all existing baselines instead of only their model. Because the time overhead should not be significantly high to reduce the model selection overhead.\n\n5. They should provide the analysis of graph size versus the size of the latent variable, is there any interesting pattern or observation?", "summary_of_the_paper": "In this paper, the authors propose a mechanism to automate the size selection of each latent representation layer of the Contextual Graph Markov model. The model automatically adjusts the size of the model parameters mitigating the expensive model selection. Moreover, the authors introduce some techniques to scale the \nproposed solution.", "summary_of_the_review": "This work investigates automatic model size selection without compromising model performance, which is a very important and timely research question. \n\nHowever, the proposed solution revolves around a specific architecture that limits its applicability. Also, it does not consider the edge properties of graphs, which are extremely important for different graphs like crystal (CGCNN - Phys. Rev. Lett.). \n\nMore model ablation studies for e.g graph size (or structural complexity like wiener index/diameter/density) vs learned latent variable size are required.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4-nIba52Hko", "reviewer": "Reviewer_P2Q1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The authors propose an interesting idea of utilizing the HDP framework to obtain the number of latent variables at each layer. HOwever the gain in the accuracy seems either non-existent or marginal.", "summary_of_the_paper": "The paper combines the idea from the classical hidden dirichlet processe and CGMM to automate the process of selecting the hyperparameters of CGMM.", "summary_of_the_review": "Interesting idea but not very impressive experimental results.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends the Contextual Graph Markov Model, a deep unsupervised probabilistic approach. The key idea is to leverage Hierarchical Dirichlet Processes to automatically determine each layer's latent representation's size. The paper conducts experiments on graph classification tasks to show the superiority of the proposed method.

Strength
* A new method is proposed.
* The proposed method appears to be sound.
* Experiments are conducted to demonstrate the effectiveness.

Weakness
* The novelty and significance of the work are not enough.
* The improvements on existing methods are not significant.
* The proposed method is also not so general.

-----------

After rebuttal

Reviewer ynws, who gave the highest score, says

“I agree with the overall review of the paper by other reviewers. The proposed method is limited to the CGMM model and not generic enough to extend to other more popular graph neural networks. The improvements don't seem to be significant enough as well.”
Decision: Reject