Provable Filter for Real-world Graph Clustering

• URL: http://arxiv.org/abs/2403.03666v1
• Date: Wed, 6 Mar 2024 12:37:49 GMT
• Title: Provable Filter for Real-world Graph Clustering
• Authors: Xuanting Xie, Erlin Pan, Zhao Kang, Wenyu Chen and Bingheng Li
• Abstract summary: A principled way to handle practical graphs is urgently needed. We construct two graphs that are highly homophilic and heterophilic, respectively. We validate our approach through extensive experiments on both homophilic and heterophilic graphs.
• Score: 11.7278692671308
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph clustering, an important unsupervised problem, has been shown to be more resistant to advances in Graph Neural Networks (GNNs). In addition, almost all clustering methods focus on homophilic graphs and ignore heterophily. This significantly limits their applicability in practice, since real-world graphs exhibit a structural disparity and cannot simply be classified as homophily and heterophily. Thus, a principled way to handle practical graphs is urgently needed. To fill this gap, we provide a novel solution with theoretical support. Interestingly, we find that most homophilic and heterophilic edges can be correctly identified on the basis of neighbor information. Motivated by this finding, we construct two graphs that are highly homophilic and heterophilic, respectively. They are used to build low-pass and high-pass filters to capture holistic information. Important features are further enhanced by the squeeze-and-excitation block. We validate our approach through extensive experiments on both homophilic and heterophilic graphs. Empirical results demonstrate the superiority of our method compared to state-of-the-art clustering methods.

Related papers

• When Heterophily Meets Heterogeneous Graphs: Latent Graphs Guided Unsupervised Representation Learning [6.2167203720326025]
  Unsupervised heterogeneous graph representation learning (UHGRL) has gained increasing attention due to its significance in handling practical graphs without labels. We define semantic heterophily and propose an innovative framework called Latent Graphs Guided Unsupervised Representation Learning (LatGRL) to handle this problem.
  arXiv  Detail & Related papers  (2024-09-01T10:25:06Z)
• The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges [101.83124435649358]
  Homophily principle, ie nodes with the same labels or similar attributes are more likely to be connected. Recent work has identified a non-trivial set of datasets where GNN's performance compared to the NN's is not satisfactory.
  arXiv  Detail & Related papers  (2024-07-12T18:04:32Z)
• Simplified PCNet with Robustness [5.127360270463981]
  Possion-Charlier Network (PCNet) citeli2024pc, the previous work, allows graph representation to be learned from heterophily to homophily. We simplify PCNet and enhance its robustness.
  arXiv  Detail & Related papers  (2024-03-06T12:57:48Z)
• Robust Graph Structure Learning under Heterophily [12.557639223778722]
  We propose a novel robust graph structure learning method to achieve a high-quality graph from heterophilic data for downstream tasks. We first apply a high-pass filter to make each node more distinctive from its neighbors by encoding structure information into the node features. Then, we learn a robust graph with an adaptive norm characterizing different levels of noise.
  arXiv  Detail & Related papers  (2024-03-06T12:29:13Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  Graphs with homophily-prone edges tend to connect nodes with the same class. Heterophily-prone edges tend to build relationships between nodes with different classes. Existing GNNs only take the original graph during training.
  arXiv  Detail & Related papers  (2023-06-13T08:06:10Z)
• Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering [15.764819403555512]
  It is impossible to first identify a graph as homophilic or heterophilic before a suitable GNN model can be found. We propose a novel graph clustering method, which contains three key components: graph reconstruction, a mixed filter, and dual graph clustering network. Our method dominates others on heterophilic graphs.
  arXiv  Detail & Related papers  (2023-05-03T01:49:01Z)
• Graph Contrastive Learning under Heterophily via Graph Filters [51.46061703680498]
  Graph contrastive learning (CL) methods learn node representations in a self-supervised manner by maximizing the similarity between the augmented node representations obtained via a GNN-based encoder. In this work, we propose an effective graph CL method, namely HLCL, for learning graph representations under heterophily. Our extensive experiments show that HLCL outperforms state-of-the-art graph CL methods on benchmark datasets with heterophily, as well as large-scale real-world graphs, by up to 7%, and outperforms graph supervised learning methods on datasets with heterophily by up to 10%.
  arXiv  Detail & Related papers  (2023-03-11T08:32:39Z)
• Single-Pass Contrastive Learning Can Work for Both Homophilic and Heterophilic Graph [60.28340453547902]
  Graph contrastive learning (GCL) techniques typically require two forward passes for a single instance to construct the contrastive loss. Existing GCL approaches fail to provide strong performance guarantees. We implement the Single-Pass Graph Contrastive Learning method (SP-GCL) Empirically, the features learned by the SP-GCL can match or outperform existing strong baselines with significantly less computational overhead.
  arXiv  Detail & Related papers  (2022-11-20T07:18:56Z)
• Make Heterophily Graphs Better Fit GNN: A Graph Rewiring Approach [43.41163711340362]
  We propose a method named Deep Heterophily Graph Rewiring (DHGR) to rewire graphs by adding homophilic edges and pruning heterophilic edges. To the best of our knowledge, it is the first work studying graph rewiring for heterophily graphs.
  arXiv  Detail & Related papers  (2022-09-17T06:55:21Z)
• Heterogeneous Graph Neural Networks using Self-supervised Reciprocally Contrastive Learning [102.9138736545956]
  Heterogeneous graph neural network (HGNN) is a very popular technique for the modeling and analysis of heterogeneous graphs. We develop for the first time a novel and robust heterogeneous graph contrastive learning approach, namely HGCL, which introduces two views on respective guidance of node attributes and graph topologies. In this new approach, we adopt distinct but most suitable attribute and topology fusion mechanisms in the two views, which are conducive to mining relevant information in attributes and topologies separately.
  arXiv  Detail & Related papers  (2022-04-30T12:57:02Z)
• Is Homophily a Necessity for Graph Neural Networks? [50.959340355849896]
  Graph neural networks (GNNs) have shown great prowess in learning representations suitable for numerous graph-based machine learning tasks. GNNs are widely believed to work well due to the homophily assumption ("like attracts like"), and fail to generalize to heterophilous graphs where dissimilar nodes connect. Recent works design new architectures to overcome such heterophily-related limitations, citing poor baseline performance and new architecture improvements on a few heterophilous graph benchmark datasets as evidence for this notion. In our experiments, we empirically find that standard graph convolutional networks (GCNs) can actually achieve better performance than
  arXiv  Detail & Related papers  (2021-06-11T02:44:00Z)

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.