Spectral Relational Clustering, Multi-type Relational Data, Collective Factorization on Related Matrices

 Background: 

Most clustering approaches in the literature focus on "flat" data in which each data object is represented as a fixed-length feature vector. However, many real-world data sets are much richer in structure, involving objects of multiple types that are related to each other, such as Web pages, search queries and Web users in a Web search system, and papers, key words; authors and conferences in a scientific publication domain. Therefore, multi-type relational data has presented a great challenge for traditional clustering approaches.

 Technology Overview: 

This invention is based on a novel general model, the collective factorization on related matrices, to discover the hidden structures of multi-types of objects based on both feature information and relation information. By clustering the multi-types of objects simultaneously, the model performs adaptive dimensionality reduction for each type of data.  The algorithm has the simplicity of spectral clustering approaches but at the same time also applicable to relational data with various structures. Theoretic analysis and experimental results demonstrate the promise and effectiveness of the algorithm.

 Advantages: 

• It deals with the problem of high dimensionality more efficiently.
• It deals with the problem of sparsity more efficiently.
• Unlike the existing technologies which are applicable to only the relational data with special structures, it is applicable to relational data with various structures.
• Unlike the traditional approaches that provide only local hidden structures, it provides both local and global hidden structures.

 Intellectual Property Summary: 

• U.S. 8,185,481
• U.S. 8,700,547