Sponsored by
 
Events
News
 
[ Events ]
 
 

Activity Search
Sort out
Field
 
Year
Seminars  
 
NCTS Seminar on Machine Learning
 
12:30 - 13:30, April 27, 2018 (Friday)
R202, Astronomy-Mathematics Building, NTU
(台灣大學天文數學館 202室)
Community Recovery from Beyond-Pairwise Information
I-Hsiang Wang (National Taiwan University)

Abstract:

In this talk, we explore two community detection methods that leverage beyond-pairwise relational information and statistical information respectively. For harnessing beyond-pairwise relational information, we cast it into a hypergraph clustering problem, where each hyperedge represents the relational information among the entities represented by the vertices in that hyperedge. A polynomial running time recovery algorithm is proposed to achieve the fundamental statistical limit of community detection on a hypergraph stochastic block model. For leveraging beyond-pairwise statistical information, we cast it into a data extraction problem where the recovery algorithm can actively take measurements on a group of entities, each of which records the histogram of community labels in that group. An explicit construction of the measured groups along with a linear running time recovery algorithm is proposed to achieve the fundamental limit on the total number of measurements required to recover all the hidden community labels. The fundamental limit is then extended to the setting of partial recovery with noisy measurements.



 

back to list  
 (C) 2021 National Center for Theoretical Sciences