The Contextual Graph Markov Model (CGMM) 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 need to perform an extensive model selection to choose the proper size of each layer’s latent representation. In this paper, we address this problem by introducing the Infinite Contextual Graph Markov Model (iCGMM), the first deep Bayesian nonparametric model for graph learning. During training, iCGMM can adapt the complexity of each layer to better fit the underlying data distribution. On 8 graph classification tasks, we show that iCGMM: i) successfully recovers or improves CGMM’s performances while reducing the hyper-parameters’ search space; ii) performs comparably to most end-to-end supervised methods. The results include studies on the importance of depth, hyper-parameters, and compression of the graph embeddings. We also introduce a novel approximated inference procedure that better deals with larger graph topologies.
@inproceedings{castellana22,title={The Infinite Contextual Graph {M}arkov Model},author={Castellana, Daniele and Errica, Federico and Bacciu, Davide and Micheli, Alessio},booktitle={Proceedings of the 39th International Conference on Machine Learning},pages={2721--2737},year={2022},volume={162},series={Proceedings of Machine Learning Research},month={17--23 Jul},publisher={PMLR},}
Processing sentence constituency trees in binarised form is a common and popular approach in literature. However, constituency trees are non-binary by nature. The binarisation procedure changes deeply the structure, furthering constituents that instead are close. In this work, we introduce a new approach to deal with non-binary constituency trees which leverages tensor-based models. In particular, we show how a powerful composition function based on the canonical tensor decomposition can exploit such a rich structure. A key point of our approach is the weight sharing constraint imposed on the factor matrices, which allows limiting the number of model parameters. Finally, we introduce a Tree-LSTM model which takes advantage of this composition function and we experimentally assess its performance on different NLP tasks.
@inproceedings{Castellana2020coling,title={Learning from Non-Binary Constituency Trees via Tensor Decomposition},author={Castellana, Daniele and Bacciu, Davide},booktitle={Proceedings of the 28th International Conference on Computational Linguistics},month=dec,year={2020},publisher={International Committee on Computational Linguistics},url={https://aclanthology.org/2020.coling-main.346},doi={10.18653/v1/2020.coling-main.346},pages={3899--3910},}
The paper introduces two new aggregation functions to encode structural knowledge from tree-structured data. They leverage the Canonical and Tensor-Train decompositions to yield expressive context aggregation while limiting the number of model parameters. Finally, we define two novel neural recursive models for trees leveraging such aggrega-tion functions, and we test them on two tree classification tasks, showing the advantage of proposed models when tree outdegree increases.
@inproceedings{Castellana2020esann,author={Castellana, Daniele and Bacciu, Davide},booktitle={Proceedings of the the 28th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN)},isbn={978-2-87587-074-2},keywords={Computer Science - Machine Learning,Statistics - Machine Learning},title={{Tensor Decompositions in Recursive Neural Networks for Tree-Structured Data}},year={2020},month=oct,pages={451--456},}
Most machine learning models for structured data encode the structural knowledge of a node by leveraging simple aggregation functions (in neural models, typically a weighted sum) of the information in the node’s neighbourhood. Nevertheless, the choice of simple context aggregation functions, such as the sum, can be widely sub-optimal. In this work we introduce a general approach to model aggregation of structural context leveraging a tensor-based formulation. We show how the exponential growth in the size of the parameter space can be controlled through an approximation based on the Tucker tensor decomposition. This approximation allows limiting the parameters space size, decoupling it from its strict relation with the size of the hidden encoding space. By this means, we can effectively regulate the trade-off between expressivity of the encoding, controlled by the hidden size, computational complexity and model generalisation, influenced by parameterisation. Finally, we introduce a new Tensorial Tree-LSTM derived as an instance of our framework and we use it to experimentally assess our working hypotheses on tree classification scenarios.
@inproceedings{Castellana2020ijcnn,archiveprefix={arXiv},author={Castellana, Daniele and Bacciu, Davide},booktitle={2020 International Joint Conference on Neural Networks (IJCNN)},doi={10.1109/IJCNN48605.2020.9206597},eprint={2006.10021},isbn={978-1-7281-6926-2},month=jul,pages={1--8},publisher={IEEE},title={{Generalising Recursive Neural Models by Tensor Decomposition}},url={https://ieeexplore.ieee.org/document/9206597/},year={2020}}
Bottom-Up Hidden Tree Markov Model is a highly expressive model for tree-structured data. Unfortunately, it cannot be used in practice due to the intractable size of its state-transition matrix. We propose a new approximation which lies on the Tucker factorisation of tensors. The probabilistic interpretation of such approximation allows us to define a new probabilistic model for tree-structured data. Hence, we define the new approximated model and we derive its learning algorithm. Then, we empirically assess the effective power of the new model evaluating it on two different tasks. In both cases, our model outperforms the other approximated model known in the literature.
@inproceedings{Castellana2019b,author={Castellana, Daniele and Bacciu, Davide},booktitle={2019 International Joint Conference on Neural Networks (IJCNN)},doi={10.1109/IJCNN.2019.8851851},isbn={978-1-7281-1985-4},month=jul,pages={1--8},publisher={IEEE},title={{Bayesian Tensor Factorisation for Bottom-up Hidden Tree Markov Models}},url={https://ieeexplore.ieee.org/document/8851851/},volume={2019-July},year={2019},}
Hidden tree Markov models allow learning distributions for tree structured data while being interpretable as nondeterministic automata. We provide a concise summary of the main approaches in literature, focusing in particular on the causality assumptions introduced by the choice of a specific tree visit direction. We will then sketch a novel non-parametric generalization of the bottom-up hidden tree Markov model with its interpretation as a nondeterministic tree automaton with infinite states.
@inproceedings{bacciu2018learning,author={Bacciu, Davide and Castellana, Daniele},booktitle={Workshop on Learning and Automata (LearnAut'18)},title={{Learning Tree Distributions by Hidden Markov Models}},year={2018},month=jul,keywords={workshops},}
The paper introduces a new probabilistic tree encoder based on a mixture of Bottom-up Hidden Tree Markov Models. The ability to recognise similar structures in data is experimentally assessed both in clusterization and classification tasks. The results of these preliminary experiments suggest that the model can be successfully used to compress the tree structural and label patterns in a vectorial representation.
@inproceedings{Bacciu2018b,author={Bacciu, Davide and Castellana, Daniele},booktitle={Proceedings of the 26th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN)},isbn={978-287587047-6},year={2018},month=apr,pages={543--548},}