The Four Point Permutation Test for Latent Block Structure in Incidence Matrices

MaRDI QIDQ6307666zbMATH OpenFDO

Authors Richard W. R. Darling, Cheyne Homberger

Publication date 3 October 2018

Mathematics Subject Classification ID

Measures of association (correlation, canonical correlation, etc.) (62H20)

Abstract: Transactional data may be represented as a bipartite graph $G:=(LcupR,E)$, where $L$ denotes agents, $R$ denotes objects visible to many agents, and an edge in $E$ denotes an interaction between an agent and an object. Unsupervised learning seeks to detect block structures in the adjacency matrix $Z$ between $L$ and $R$, thus grouping together sets of agents with similar object interactions. New results on quasirandom permutations suggest a non-parametric extbf{four point test} to measure the amount of block structure in $G$, with respect to vertex orderings on $L$ and $R$. Take disjoint 4-edge random samples, order these four edges by left endpoint, and count the relative frequencies of the $4!$ possible orderings of the right endpoint. When these orderings are equiprobable, the edge set $E$ corresponds to a quasirandom permutation $pi$ of $|E|$ symbols. Total variation distance of the relative frequency vector away from the uniform distribution on 24 permutations measures the amount of block structure. Such a test statistic, based on $lfloor|E|/4floor$ samples, is computable in $O(|E|/p)$ time on $p$ processors. Possibly block structure may be enhanced by precomputing extbf{natural orders} on $L$ and $R$, related to the second eigenvector of graph Laplacians. In practice this takes $O(d|E|)$ time, where $d$ is the graph diameter. Five open problems are described.

This page was built for publication: The Four Point Permutation Test for Latent Block Structure in Incidence Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6307666)