Clique matrices for statistical graph decomposition and parameterising restricted positive definite matrices

David Barber
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:26-33, 2008.

Abstract

We introduce Clique Matrices as an alternative representation of undirected graphs, being a generalisation of the incidence matrix representation. Here we use clique matrices to decompose a graph into a set of possibly overlapping clusters, defined as well-connected subsets of vertices. The decomposition is based on a statistical description which encourages clusters to be well connected and few in number. Inference is carried out using a variational approximation. Clique matrices also play a natural role in parameterising positive definite matrices under zero constraints on elements of the matrix. We show that clique matrices can parameterise all positive definite matrices restricted according to a decomposable graph and form a structured Factor Analysis approximation in the non-decomposable case.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR6-barber08a, title = {Clique matrices for statistical graph decomposition and parameterising restricted positive definite matrices}, author = {Barber, David}, booktitle = {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence}, pages = {26--33}, year = {2008}, editor = {McAllester, David A. and Myllymäki, Petri}, volume = {R6}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r6/main/assets/barber08a/barber08a.pdf}, url = {https://proceedings.mlr.press/r6/barber08a.html}, abstract = {We introduce Clique Matrices as an alternative representation of undirected graphs, being a generalisation of the incidence matrix representation. Here we use clique matrices to decompose a graph into a set of possibly overlapping clusters, defined as well-connected subsets of vertices. The decomposition is based on a statistical description which encourages clusters to be well connected and few in number. Inference is carried out using a variational approximation. Clique matrices also play a natural role in parameterising positive definite matrices under zero constraints on elements of the matrix. We show that clique matrices can parameterise all positive definite matrices restricted according to a decomposable graph and form a structured Factor Analysis approximation in the non-decomposable case.}, note = {Reissued by PMLR on 09 October 2024.} }
Endnote
%0 Conference Paper %T Clique matrices for statistical graph decomposition and parameterising restricted positive definite matrices %A David Barber %B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2008 %E David A. McAllester %E Petri Myllymäki %F pmlr-vR6-barber08a %I PMLR %P 26--33 %U https://proceedings.mlr.press/r6/barber08a.html %V R6 %X We introduce Clique Matrices as an alternative representation of undirected graphs, being a generalisation of the incidence matrix representation. Here we use clique matrices to decompose a graph into a set of possibly overlapping clusters, defined as well-connected subsets of vertices. The decomposition is based on a statistical description which encourages clusters to be well connected and few in number. Inference is carried out using a variational approximation. Clique matrices also play a natural role in parameterising positive definite matrices under zero constraints on elements of the matrix. We show that clique matrices can parameterise all positive definite matrices restricted according to a decomposable graph and form a structured Factor Analysis approximation in the non-decomposable case. %Z Reissued by PMLR on 09 October 2024.
APA
Barber, D.. (2008). Clique matrices for statistical graph decomposition and parameterising restricted positive definite matrices. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:26-33 Available from https://proceedings.mlr.press/r6/barber08a.html. Reissued by PMLR on 09 October 2024.

Related Material