THE INFINITE CONTEXTUAL GRAPH MARKOV MODEL
Year: 2021

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.

heading: 1 INTRODUCTION
text: It can be argued that one of the most daunting processes in machine learning is the selection of appropriate hyper-parameters for the task at hand. Indeed, due to the data-dependent nature of the learning problem, there usually exists no 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-parameters (Gershman & Blei, 2012; He et al., 2021). 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) hyper-parameters.
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 of varying topology without the need for human intervention, and they rely on local and iterative processing of information commonly known as message passing; for a thorough description of some of the most popular DGNs in the literature (and of the more general graph representation learning field) we refer the reader to recent surveys on the topic (Bronstein et al., 2017; Battaglia et al., 2018; Bacciu et al., 2020b; Wu et al., 2020). Despite most of these methods belonging to the neural world, the Contextual Graph Markov Model (CGMM) stands out as a 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 a hyper-parameter, CGMM relies on 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 a BNP extension, as each layer is essentially a conditional mixture model.
The main challenge we 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, e.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 a 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 on 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 an important (if not the first) step towards a theoretically grounded and automatic construction of Deep Bayesian Graph Networks.

heading: 2 RELATED WORKS
text: 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 a base distributionG0, i.e., the expected value of the process, and a scaling parameter α0 that controls the concentration of DP realizations aroundG0 (Teh, 2010). In particular, the Chinese Restaurant Process (Aldous, 1985), the Stick-breaking Construction (Sethuraman, 1994) and the Pòlya urn scheme (Hoppe, 1984) are all alternative ways to formalize a DP. Moving to HDPs is conceptually straightforward, in that it considers the base distributionG0 as a draw from another DP parametrized by a base distribution H and a scaling parameter γ. 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 & Blei, 2012). 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 of Micheli (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, AutoML methods for graphs are yet another way to automatize the selection of all hyper-parameters of a DGN (He et al., 2021). 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 a 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.

heading: 3 METHOD
text: This Section introduces the details of our method. Since we borrow ideas from two relatively distant fields, we define a unified mathematical notation and jargon as well as a high-level overview of the CGMM and HDP models to ease the subsequent exposition.
We define a graph as a tuple g = (Vg, Eg,Xg) where Vg 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 a node u is the set of nodes connected to u, i.e., Nu = {v ∈ Vg|(v, u) ∈ Eg}. For the purpose of this work, we will define the (categorical or continuous) node feature of a node u with the term xu ∈ Xg .

heading: 3.1 BASICS OF CGMM
text: To best understand how and why this work extends CGMM, we now give a 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 a 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 an incremental fashion: after one layer is 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, 2009; Kipf & Welling, 2017) is 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 1. A latent variable q`u is attached to each node u, and it is responsible for the the generation of the node feature xu. To take into account structural information, the hidden state q`u is conditioned on the neighboring hidden states computed at the previous layer, i.e., the set {q`−1v | v ∈ Nu}. Importantly, the constructive approach allows us to treat the hidden (frozen) states of the previous layer as observable variables. Each layer is trained to 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 at layer ` is encoded as the posterior of its hidden state.

heading: 3.2 BASICS OF HDP
text: The HDP is a Bayesian nonparametric prior for the generation of grouped data using different infinite mixture models with shared mixture components. Let {x1, x2, . . . } be a set of observations that are grouped into J groups, i.e., each observation xu belongs to the group ju ∈ {1, . . . , J}. Using the stick-breaking representation (Sethuraman, 1994), the HDP mixture model that generates the observations can be defined as (Teh et al., 2006):
β | γ ∼ Stick(γ) qu | ju, (πj)Jj=1 ∼ πju πj | β, α0 ∼ DP(α0,β) xu | qu, (θc)∞c=1 ∼ F (θqu)
θ |H ∼H, (1)
where F (θqu) denotes the emission distribution, parametrized by θqu , that generates the observation xu. The latent state qu indicates which mixture component should be used to generate xu. The value of qu is sampled from the distribution πju , which stands for the mixture weights of group ju. All (πj) J j=1 are obtained from a DP with concentration parameter α0 and base distribution β. Notably, all groups’ mixture weights are 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 stick-breaking process Stick(γ) of Sethuraman (1994).
To generate a possibly infinite number of emission distributions, we exploit a prior distributionH that allows us to create new mixture components on demand. Thanks to the stick-breaking construction,
even though an 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.

heading: 3.3 MODEL DEFINITION
text: Architecturally speaking, ICGMM shares the same characteristics of CGMM described in Section 3.1, whereas the differences of each layer’s graphical model are highlighted in Figure 1. In particular, ICGMM assumes that the generation of the node features xu at each layer is governed by a HDP mixture model. Thus, following the stick-breaking construction detailed in Section 3.2, the generative process of a single ICGMM layer ` can be formalized as follows:
β` | γ` ∼ Stick(γ`) j`u | q`−1Nu = ψ(q `−1 Nu )
π`j | β`, α`0 ∼ DP(α`0,β`) q`u | j`u, (πj)C `−1
j=1 ∼ π`ju θ` |H ∼H xu | q`u, (θ`c)∞c=1 ∼ F (θ`q`u),
(2)
where we add the superscript ` to the HDP mixture model quantities to 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 at 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 a group in advance. In this work, the assignment of a node feature to a group is not known a priori, but that is the key to propagate contextual information across the graph. We select the group j`u of the feature node xu based on the neighbors’ observable posteriors computed at the previous layer, i.e., q`−1Nu = {q `−1 v ∈ [0, 1]C
l−1 | v ∈ Nu}. However, due to known intractability issues, each posterior distribution q`−1v is approximated by the
inference phase of the previous layer (see Section 3.4). To stick as much as possible to the original CGMM formalism, ju is chosen as the most likely position in the C`−1-sized macrostate, obtained by averaging the neighbors’ probabilities in q`−1Nu :
j`u = ψ(q `−1 Nu ) = arg max
j∈{1,...,C`−1} ( 1 |Nu| ∑ v∈Nu q`−1v ) j . (3)
It follows that nodes with the same feature may have a 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 no previous layer exists, we shall just assume that all node features belong to the same group.
Summing up, we 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 to 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) to 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.

heading: 3.4 INFERENCE
text: The inference phase of every BNP method is meant to estimate the posterior of the model parameters. For each ICGMM layer `, we wish to compute the quantities q`u,β `,π`j and θ `. 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 a 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. (2006). Note that it is also possible to estimate the hyper-parameters α`0 and γ
`: whenever that is the case, we shall append a subscript “auto” to our model’s name. In the interest of space, we report the ICGMM complete Gibbs sampling equations and pseudo-code in Appendix A and B, respectively.
Graph Embedding Generation. In a similar vein with (Bacciu et al., 2020a), we prefer to use the sample distribution of qu (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. A unibigram concatenates the posterior of a node, i.e., a vector called unigram, with its bigram. A bigram counts, for each possible state qu, how many of u’s neighbors are in another state, and it is represented as a vector of size C2. 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 (ICGMMf ). Due to the sequential nature of the Gibbs sampling 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., 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 a straightforward idea, which is to perform sampling for a 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 a good trade-off between the quality and speedup, we stick
to 1 graph as the size of our batch. Such a trade-off provides a CPU speedup of up to 60× at training time, and we empirically observed that performances remain unchanged with respect to the original version on the smaller chemical tasks considered. While this faster version of ICGMM, which we call ICGMMf , 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 D for an analysis of the speedup gains on the different datasets.

heading: 3.5 LIMITATIONS
text: Due to the complexity of the BNP treatment, one limitation of this work is 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 a substantial speedup and allows us 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; Hoffman et al., 2013; Hughes et al., 2015). 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., 2021) 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.

heading: 4 EXPERIMENTS
text: We evaluated the performances of ICGMM using the fair, robust, and reproducible evaluation setup for graph classification defined in Errica et al. (2020). It 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 to re-assess CGMM and E-CGMM (Atzeni et al., 2021), a recently proposed variant, by trying all the hyper-parameters 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-BINARY, IMDB-MULTI, REDDIT-BINARY, REDDITMULTI-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 (Fey & Lenssen, 2019) for the implementation of our method.1
Apart from CGMM’s variants, we will compare ICGMM against the following end-to-end supervised neural architectures for graphs: DGCNN (Zhang et al., 2018), DIFFPOOL (Ying et al., 2018), ECC (Simonovsky & Komodakis, 2017), GIN (Xu et al., 2019), GRAPHSAGE (Hamilton et al., 2017), and a structure-agnostic 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 (Errica et al., 2020).
We have discussed how ICGMM can automatize the choice its hyper-parameters, e.g., the size of the latent representation. In general, the choice of the Bayesian hyper-parameters is much less important than that of the number of states C, as in principle one can recursively introduce hyper-priors over these hyper-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-parameter space to best assess and characterize the behaviour of the model and ii) introduced hyper-priors to estimate α`0 and γ
` at each layer, thus further reducing the need for an extensive model selection.
For the chemical tasks, the prior H over the emission parameters θc was the uniform Dirichlet distribution. The range of ICGMM hyper-parameters tried in this case were: number of layers
1The code to rigorously reproduce our results is provided in the supplementary material.
∈ {5, 10, 15, 20}, α0 ∈ {1, 5}, γ ∈ {1, 2, 3}, unibigram aggregation ∈ {sum,mean}, and Gibbs sampling iterations ∈ {10, 20, 50}. Instead, for the social tasks we implemented a Normal-Gamma priorH over a Gaussian distribution. Here the prior is parametrized by the following hyper-priors: µ0, the mean node degree extracted from the data; λ0, which is inversely proportional to the prior variance of the mean; and (a0, b0), whose ratio t = b0a0 represents the expected variance of the data. The ICGMM hyper-parameters here were: number of layers ∈ {5, 10, 15, 20}, λ0 ∈ {1e-6}, a0 ∈ {1.}, b0 ∈ {0.09, 1.}, α0 ∈ {1, 5, 10}, γ ∈ {2, 5, 10}, unibigram aggregation {sum,mean}, and Gibbs Sampling iterations ∈ {100}. To further automate learning of ICGMM’s unsupervised layers, we place uninformative Gamma(1, rate = 0.01) hyper-priors on both α`0, γ
` hyper-parameters. To prevent the model from getting stuck in a local minimum on COLLAB (due to bimodal degree distribution and large variances), we tried λ0 ∈ {1e-4, 1e-5}. To conclude, we list the hyper-parameters tried for the one-layer MLP classifier trained on the unsupervised graph embeddings: optimizer ∈ {Adam}, batch size ∈ {32}, hidden units ∈ {32, 128}, learning rate ∈ {1e-3}, L2 regularization ∈ {0., 5e-4}, epochs ∈ {2000}, ReLU activation, and early stopping on validation accuracy with patience 300 on chemical tasks and 100 on social ones.

heading: 5 RESULTS
text: The empirical results on chemical and social benchmarks are reported in Tables 1 and 2, 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 ju based on the neighboring recommendations is a 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, ICGMMf performs as 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).
Moving to the social datasets, we 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 to CGMM variants may be how the emission distributions are initialized. On the one 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 a fully Bayesian treatment, which combined with the automatic selection of the latent states allows to better model outliers by adding a new state when the posterior probability of a data point is too low.
In what follows, we will try to shed more light into the improved generalization performances of ICGMM, by analyzing the exact model from a layer-wise perspective.
On the effectiveness of depth and hyper-parameters. To confirm our intuition about the benefits of the proposed information propagation mechanism, Figure 2a shows the NCI1 training and validation performances of both CGMM and ICGMM as we add more layers. For simplicity, we picked the 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 to find better local minima, whereas ICGMM can automatically add states whenever the data point’s sampling probabilities are too low. We trained the same classifier at 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 is thinner than its non-BNP counterpart, suggesting that the classifier is less prone to overfitting the data.
We now study how ICGMM behaves as we vary the main hyper-parameters α0 and γ. We continue our experimentation on NCI1; Figure 2b depicts the average validation performance and number of states C over all configurations and folds, subject to changes of α0 and γ values. The trend indicates how greater values for both hyper-parameters achieve, on average, better validation performance. Also, smaller values of the two hyper-parameters tend to strongly regularize the model by creating fewer states, with consequent reduction in 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 a matter of fact, Figure 3a reports such a statistic on the same NCI1 configuration as before: ICGMM preferred a lower number of latent states than CGMM, i.e., around 5 per layer. In turn, the resulting graph embeddings become much smaller, with important savings in terms of memory footprint and computational costs to train the subsequent classifier. Figure 3b displays the cumulative graph embedding size across layers, using
the unibigram representation without loss of 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 α` and γ`. We conclude this work with a performance analysis of the fully automated versions of ICGMM and ICGMMf , namely those with an “auto” subscript in Tables 1 and 2; in particular, we observe no statistically significant performance differences with respect to the original models. By estimating all hyper-parameters of our models using uninformative priors, we almost always (but for COLLAB) managed to avoid the model selection for the unsupervised graph embeddings creation. In turn, this amounted to a 6× reduction in the overall number of configurations to be tried, but most importantly it frees the user from making hard choices about which configurations of hyper-parameters to try. Additionally, we observe that the number of chosen states and the consequent graph embedding size is very similar to that of ICGMM with α0 = 5, γ = 3, but this time the two hyper-parameters have been automatically adjusted by the model on the basis of the data.
To sum up, we have shown that: i) our model has very competitive performances with respect to 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 a much lower memory and computational footprints due to the previous points without sacrificing the predictive performance; v) we can fully automatize the choice of the hyper-parameters using uninformative priors, which drastically reduces the cost of the model selection phase.

heading: 6 CONCLUSIONS
text: With the Infinite Contextual Graph Markov Model, we 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 a first relevant step towards the automatic construction of fully probabilistic deep learning models for graphs.
REPRODUCIBILITY STATEMENT
To ensure that the results in this paper are reproducible, we relied on the PyDGN library (https:// pypi.org/project/PyDGN/), 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 et al. (2020); Section 4 reports 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-processing steps, we have also provided the necessary PyDGN configuration files.

heading: C DATASET STATISTICS
text: Below we report some statistics for the chosen benchmarks.

heading: D SPEEDUP GAINS WITH FASTER INFERENCE
text: 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 of nodes (see Table 3).

Review summaries:
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. 

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  proposed solution.