GLINKX: A Scalable Unified Framework For Homophilous and Heterophilous
Graphs
- URL: http://arxiv.org/abs/2211.00550v1
- Date: Tue, 1 Nov 2022 15:56:58 GMT
- Title: GLINKX: A Scalable Unified Framework For Homophilous and Heterophilous
Graphs
- Authors: Marios Papachristou, Rishab Goel, Frank Portman, Matthew Miller, Rong
Jin
- Abstract summary: In graph learning, higher-order interactions and message passing work well on homophilous graphs and are leveraged by GCNs and GATs.
On the other hand, shallow (or node-level) models using ego features and adjacency embeddings work well in heterophilous graphs.
We propose a novel scalable shallow method -- GLINKX -- that can work both on homophilous and heterophilous graphs.
- Score: 11.917267015292985
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In graph learning, there have been two predominant inductive biases regarding
graph-inspired architectures: On the one hand, higher-order interactions and
message passing work well on homophilous graphs and are leveraged by GCNs and
GATs. Such architectures, however, cannot easily scale to large real-world
graphs. On the other hand, shallow (or node-level) models using ego features
and adjacency embeddings work well in heterophilous graphs. In this work, we
propose a novel scalable shallow method -- GLINKX -- that can work both on
homophilous and heterophilous graphs. GLINKX leverages (i) novel monophilous
label propagations, (ii) ego/node features, (iii) knowledge graph embeddings as
positional embeddings, (iv) node-level training, and (v) low-dimensional
message passing. Formally, we prove novel error bounds and justify the
components of GLINKX. Experimentally, we show its effectiveness on several
homophilous and heterophilous datasets.
Related papers
- 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) - Provable Filter for Real-world Graph Clustering [11.7278692671308]
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.
arXiv Detail & Related papers (2024-03-06T12:37:49Z) - 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) - You Only Transfer What You Share: Intersection-Induced Graph Transfer
Learning for Link Prediction [79.15394378571132]
We investigate a previously overlooked phenomenon: in many cases, a densely connected, complementary graph can be found for the original graph.
The denser graph may share nodes with the original graph, which offers a natural bridge for transferring selective, meaningful knowledge.
We identify this setting as Graph Intersection-induced Transfer Learning (GITL), which is motivated by practical applications in e-commerce or academic co-authorship predictions.
arXiv Detail & Related papers (2023-02-27T22:56:06Z) - Graph Generation with Diffusion Mixture [57.78958552860948]
Generation of graphs is a major challenge for real-world tasks that require understanding the complex nature of their non-Euclidean structures.
We propose a generative framework that models the topology of graphs by explicitly learning the final graph structures of the diffusion process.
arXiv Detail & Related papers (2023-02-07T17:07:46Z) - Graph Neural Networks for Graphs with Heterophily: A Survey [98.45621222357397]
We provide a comprehensive review of graph neural networks (GNNs) for heterophilic graphs.
Specifically, we propose a systematic taxonomy that essentially governs existing heterophilic GNN models.
We discuss the correlation between graph heterophily and various graph research domains, aiming to facilitate the development of more effective GNNs.
arXiv Detail & Related papers (2022-02-14T23:07:47Z) - Label-Wise Message Passing Graph Neural Network on Heterophilic Graphs [20.470934944907608]
We investigate a novel framework that performs well on graphs with either homophily or heterophily.
In label-wise message-passing, neighbors with similar pseudo labels will be aggregated together.
We also propose a bi-level optimization method to automatically select the model for graphs with homophily/heterophily.
arXiv Detail & Related papers (2021-10-15T14:49:45Z) - 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.