Chia-Tung Kuo
ABSTRACT
The analysis of data represented as graphs is common having wide scale applications from social networks to medical imaging. A popular analysis is to cut the graph so that the disjoint subgraphs can represent communities (for social network) or background and foreground cognitive activity (for medical imaging). An emerging setting is when multiple data sets (graphs) exist which opens up the opportunity for many new questions. In this paper we study two such questions: i) For a collection of graphs find a single cut that is good for all the graphs and ii) For two collections of graphs find a single cut that is good for one collection but poor for the other. We show that existing formulations of multiview, consensus and alternative clustering cannot address these questions and instead we provide novel formulations in the spectral clustering framework. We evaluate our approaches on functional magnetic resonance imaging (fMRI) data to address questions such as: "What common cognitive network does this group of individuals have?" and "What are the differences in the cognitive networks for these two groups?" We obtain useful results without the need for strong domain knowledge.
- A. Argyriou, M. Herbster, and M. Pontil. Combining graph laplacians for semi--supervised learning. In Y. Weiss, B. Schölkopf, and J. Platt, editors, NIPS, pages 67--74. MIT Press, 2006.Google Scholar
- J. Bailey and G. Dong. Contrast data mining: Methods and applications. IEEE ICDM 2007 Tutorials, 2007.Google Scholar
- I. Davidson, S. Gilpin, O. Carmichael, and P. Walker. Network discovery via constrained tensor analysis of fmri data. In ACM SIGKDD, pages 194--202. ACM, 2013. Google ScholarDigital Library
- I. Davidson and Z. Qi. Finding alternative clusterings using constraints. In ICDM, pages 773--778. IEEE, 2008. Google ScholarDigital Library
- S. Fortunato. Community detection in graphs. Physics Reports, 486(3):75--174, 2010.Google ScholarCross Ref
- K. J. Friston. Functional and effective connectivity: a review. Brain connectivity, 1(1):13--36, 2011.Google ScholarCross Ref
- S. Gilpin, T. Eliassi-Rad, and I. Davidson. Guided learning for role discovery (glrd): framework, algorithms, and applications. In ACM SIGKDD, pages 113--121. ACM, 2013. Google ScholarDigital Library
- A. Goder and V. Filkov. Consensus clustering algorithms: Comparison and refinement. In ALENEX, volume 8, pages 109--117. SIAM, 2008. Google ScholarDigital Library
- M. D. Greicius, G. Srivastava, A. L. Reiss, and V. Menon. Default-mode network activity distinguishes alzheimer's disease from healthy aging: evidence from functional mri. Proceedings of the National Academy of Sciences of the United States of America, 101(13):4637--4642, 2004.Google ScholarCross Ref
- J. Han. Mining heterogeneous information networks by exploring the power of links. In Discovery Science, pages 13--30. Springer, 2009. Google ScholarDigital Library
- M. H. Hansen and B. Yu. Model selection and the principle of minimum description length. Journal of the American Statistical Association, 96(454):746--774, 2001.Google ScholarCross Ref
- M. S. Hossain, S. Tadepalli, L. T. Watson, I. Davidson, R. F. Helm, and N. Ramakrishnan. Unifying dependent clustering and disparate clustering for non-homogeneous data. In ACM SIGKDD, pages 593--602. ACM, 2010. Google ScholarDigital Library
- P. Jain, R. Meka, and I. S. Dhillon. Simultaneous unsupervised learning of disparate clusterings. Statistical Analysis and Data Mining: The ASA Data Science Journal, 1(3):195--210, 2008. Google ScholarDigital Library
- A. Kumar and H. Daumé. A co-training approach for multi-view spectral clustering. In ICML, pages 393--400, 2011.Google ScholarDigital Library
- A. Kumar, P. Rai, and H. Daume. Co-regularized multi-view spectral clustering. In NIPS, pages 1413--1421, 2011.Google ScholarDigital Library
- C.-T. Kuo and I. Davidson. Directed interpretable discovery in tensors with sparse projection. In SIAM Data Mining, pages 848--856, 2014.Google Scholar
- C.-T. Kuo, P. B. Walker, O. Carmichael, and I. Davidson. Spectral clustering for medical imaging. In ICDM, pages 887--892, Dec 2014. Google ScholarDigital Library
- A. Lancichinetti and S. Fortunato. Consensus clustering in complex networks. Scientific reports, 2, 2012.Google Scholar
- M. Meila and J. Shi. A random walks view of spectral segmentation. In AISTATS, 2001.Google Scholar
- D. Niu, J. G. Dy, , and M. I. Jordan. Iterative discovery of multiple alternativeclustering views. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(7):1340--1353, 2014. Google ScholarDigital Library
- J. Nocedal and S. J. Wright. Numerical Optimization. Springer, second edition, 2006.Google Scholar
- Z. Qi and I. Davidson. A principled and flexible framework for finding alternative clusterings. In ACM SIGKDD, pages 717--726. ACM, 2009. Google ScholarDigital Library
- K. Ramamohanarao, J. Bailey, and H. Fan. Efficient mining of contrast patterns and their applications to classification. In Intelligent Sensing and Information Processing, 2005. ICISIP 2005. Third International Conference on, pages 39--47. IEEE, 2005. Google ScholarDigital Library
- V. Sindhwani, P. Niyogi, and M. Belkin. A co-regularization approach to semi-supervised learning with multiple views. In Proceedings of ICML workshop on learning with multiple views, pages 74--79. Citeseer, 2005.Google Scholar
- A. Strehl and J. Ghosh. Cluster ensembles--a knowledge reuse framework for combining multiple partitions. The Journal of Machine Learning Research, 3:583--617, 2003. Google ScholarDigital Library
- U. Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395--416, 2007. Google ScholarDigital Library
- Y. Wakabayashi. The complexity of computing medians of relations. Resenhas do Instituto de Matemática e Estatística da Universidade de São Paulo, 3(3):323--349, 1998.Google Scholar
- X. Wang, B. Qian, and I. Davidson. On constrained spectral clustering and its applications. Data Mining and Knowledge Discovery, 28(1):1--30, 2014. Google ScholarDigital Library
- X. Yan and J. Han. gspan: Graph-based substructure pattern mining. In ICDM, pages 721--724. IEEE, 2002. Google ScholarDigital Library
- L. Zelnik-Manor and P. Perona. Self-tuning spectral clustering. In NIPS, pages 1601--1608, 2004.Google ScholarDigital Library
- D. Zhou and C. J. Burges. Spectral clustering and transductive learning with multiple views. In ICML, pages 1159--1166. ACM, 2007. Google ScholarDigital Library
Index Terms
- Unified and Contrasting Cuts in Multiple Graphs: Application to Medical Imaging Segmentation
Recommendations
Efficient Algorithms for Public-Private Social Networks
KDD '15: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data MiningWe introduce the public-private model of graphs. In this model, we have a public graph and each node in the public graph has an associated private graph. The motivation for studying this model stems from social networks, where the nodes are the users, ...
Algorithmic Cartography: Placing Points of Interest and Ads on Maps
KDD '15: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data MiningWe study the problem of selecting a set of points of interest (POIs) to show on a map. We begin with a formal model of the setting, noting that the utility of a POI may be discounted by (i) the presence of competing businesses nearby as well as (ii) its ...
Going In-Depth: Finding Longform on the Web
KDD '15: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Miningtl;dr: Longform articles are extended, in-depth pieces that often serve as feature stories in newspapers and magazines. In this work, we develop a system to automatically identify longform content across the web. Our novel classifier is highly accurate ...
Comments