|
Abstract:
|
We propose the Graph Product Partition Model (graphPPM), a probability model for random partitions of nodes set on a fixed graph where each subset of nodes induces a connected subgraph. The graphPPM has a product form of cohesion functions, which encodes information on the internal and external connectivity of each subgraph induced by a graph partition. For the community detection task with node attributes, graphPPM can be used as a prior distribution on graph partition which directly incorporates graph structures and hence bypass the need to impose graph generative assumptions such as the stochastic block model. We propose two novel inference strategies: 1) the importance sampling method for estimating the pairwise similarity matrix of the graph partition, and 2) the split-merge sampler using uniform random spanning trees to design the MCMC transition kernel on the partition space. We demonstrate the effectiveness of graphPPM in real networks for community detection tasks.
|
