Multi-View Stochastic Block Models

• URL: http://arxiv.org/abs/2406.04860v1
• Date: Fri, 7 Jun 2024 11:45:31 GMT
• Title: Multi-View Stochastic Block Models
• Authors: Vincent Cohen-Addad, Tommaso d'Orsi, Silvio Lattanzi, Rajai Nasser,
• Abstract summary: We formalize a new family of models, called textitmulti-view block models that captures this setting. For this model, we first study efficient algorithms that naively work on the union of multiple graphs. Then, we introduce a new efficient algorithm that provably outperforms previous approaches by analyzing the structure of each graph separately.
• Score: 34.55723218769512
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph clustering is a central topic in unsupervised learning with a multitude of practical applications. In recent years, multi-view graph clustering has gained a lot of attention for its applicability to real-world instances where one has access to multiple data sources. In this paper we formalize a new family of models, called \textit{multi-view stochastic block models} that captures this setting. For this model, we first study efficient algorithms that naively work on the union of multiple graphs. Then, we introduce a new efficient algorithm that provably outperforms previous approaches by analyzing the structure of each graph separately. Furthermore, we complement our results with an information-theoretic lower bound studying the limits of what can be done in this model. Finally, we corroborate our results with experimental evaluations.

Related papers

• Hierarchical Blockmodelling for Knowledge Graphs [0.5530212768657544]
  We use blockmodels for the purpose of hierarchical entity clustering on knowledge graphs. The integration of the Nested Chinese Restaurant Process and the Stick Breaking Process into the generative model allows for the induction of hierarchical clusterings. We evaluate our model on synthetic and real-world datasets and quantitatively compare against benchmark models.
  arXiv  Detail & Related papers  (2024-08-28T09:04:15Z)
• M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering [57.947071423091415]
  We introduce Minorize-Maximization Matching and Clustering (M3C), a learning-free algorithm that guarantees theoretical convergence. We develop UM3C, an unsupervised model that incorporates novel edge-wise affinity learning and pseudo label selection. Our method outperforms state-of-the-art graph matching and mixture graph matching and clustering approaches in both accuracy and efficiency.
  arXiv  Detail & Related papers  (2023-10-27T19:40:34Z)
• Sub-Graph Learning for Spatiotemporal Forecasting via Knowledge Distillation [22.434970343698676]
  We present a new framework called KD-SGL to effectively learn the sub-graphs. We define one global model to learn the overall structure of the graph and multiple local models for each sub-graph.
  arXiv  Detail & Related papers  (2022-11-17T18:02:55Z)
• Unified Multi-View Orthonormal Non-Negative Graph Based Clustering Framework [74.25493157757943]
  We formulate a novel clustering model, which exploits the non-negative feature property and incorporates the multi-view information into a unified joint learning framework. We also explore, for the first time, the multi-model non-negative graph-based approach to clustering data based on deep features.
  arXiv  Detail & Related papers  (2022-11-03T08:18:27Z)
• A Graph-Enhanced Click Model for Web Search [67.27218481132185]
  We propose a novel graph-enhanced click model (GraphCM) for web search. We exploit both intra-session and inter-session information for the sparsity and cold-start problems.
  arXiv  Detail & Related papers  (2022-06-17T08:32:43Z)
• A Unified Analysis of Dynamic Interactive Learning [5.474944738795308]
  Previous work by Emamjomeh-Zadeh et al. [ 2020] introduced dynamics into interactive learning as a way to model non-static user preferences. We give a framework that captures both of the models analyzed by [Emamjomeh-Zadeh et al., 2020], which allows us to study any type of concept evolution. We also study an efficient algorithm where the learner simply follows the feedback at each round.
  arXiv  Detail & Related papers  (2022-04-14T16:03:37Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  We propose an effective and efficient graph learning model for multi-view clustering. Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
  arXiv  Detail & Related papers  (2021-08-15T13:14:28Z)
• Multiple Graph Learning for Scalable Multi-view Clustering [26.846642220480863]
  We propose an efficient multiple graph learning model via a small number of anchor points and tensor Schatten p-norm minimization. Specifically, we construct a hidden and tractable large graph by anchor graph for each view. We develop an efficient algorithm, which scales linearly with the data size, to solve our proposed model.
  arXiv  Detail & Related papers  (2021-06-29T13:10:56Z)
• Stochastic Iterative Graph Matching [11.128153575173213]
  We propose a new model, Iterative Graph MAtching, to address the graph matching problem. Our model defines a distribution of matchings for a graph pair so the model can explore a wide range of possible matchings. We conduct extensive experiments across synthetic graph datasets as well as biochemistry and computer vision applications.
  arXiv  Detail & Related papers  (2021-06-04T02:05:35Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• Multi-view Graph Learning by Joint Modeling of Consistency and Inconsistency [65.76554214664101]
  Graph learning has emerged as a promising technique for multi-view clustering with its ability to learn a unified and robust graph from multiple views. We propose a new multi-view graph learning framework, which for the first time simultaneously models multi-view consistency and multi-view inconsistency in a unified objective function. Experiments on twelve multi-view datasets have demonstrated the robustness and efficiency of the proposed approach.
  arXiv  Detail & Related papers  (2020-08-24T06:11:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.