A nonlinear diffusion method for semi-supervised learning on hypergraphs
- URL: http://arxiv.org/abs/2103.14867v1
- Date: Sat, 27 Mar 2021 09:54:16 GMT
- Title: A nonlinear diffusion method for semi-supervised learning on hypergraphs
- Authors: Francesco Tudisco, Konstantin Prokopchik, Austin R. Benson
- Abstract summary: Hypergraph semi-supervised learning is the problem of assigning labels to all nodes in a hypergraph, given labels on just a few nodes.
We develop a nonlinear diffusion process on hypergraphs that spreads both features and labels following the hypergraph structure.
Our approach is much more accurate than several hypergraph neural networks, and also takes less time to train.
- Score: 30.41251351699783
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Hypergraphs are a common model for multiway relationships in data, and
hypergraph semi-supervised learning is the problem of assigning labels to all
nodes in a hypergraph, given labels on just a few nodes. Diffusions and label
spreading are classical techniques for semi-supervised learning in the graph
setting, and there are some standard ways to extend them to hypergraphs.
However, these methods are linear models, and do not offer an obvious way of
incorporating node features for making predictions. Here, we develop a
nonlinear diffusion process on hypergraphs that spreads both features and
labels following the hypergraph structure, which can be interpreted as a
hypergraph equilibrium network. Even though the process is nonlinear, we show
global convergence to a unique limiting point for a broad class of
nonlinearities, which is the global optimum of a interpretable, regularized
semi-supervised learning loss function. The limiting point serves as a node
embedding from which we make predictions with a linear model. Our approach is
much more accurate than several hypergraph neural networks, and also takes less
time to train.
Related papers
- Hypergraph-enhanced Dual Semi-supervised Graph Classification [14.339207883093204]
We propose a Hypergraph-Enhanced DuAL framework named HEAL for semi-supervised graph classification.
To better explore the higher-order relationships among nodes, we design a hypergraph structure learning to adaptively learn complex node dependencies.
Based on the learned hypergraph, we introduce a line graph to capture the interaction between hyperedges.
arXiv Detail & Related papers (2024-05-08T02:44:13Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes.
The efficient computation is enabled by a kernerlized Gumbel-Softmax operator.
Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
arXiv Detail & Related papers (2023-06-14T09:21:15Z) - Transductive Linear Probing: A Novel Framework for Few-Shot Node
Classification [56.17097897754628]
We show that transductive linear probing with self-supervised graph contrastive pretraining can outperform the state-of-the-art fully supervised meta-learning based methods under the same protocol.
We hope this work can shed new light on few-shot node classification problems and foster future research on learning from scarcely labeled instances on graphs.
arXiv Detail & Related papers (2022-12-11T21:10:34Z) - Hypergraph Convolutional Networks via Equivalency between Hypergraphs
and Undirected Graphs [59.71134113268709]
We present General Hypergraph Spectral Convolution(GHSC), a general learning framework that can handle EDVW and EIVW hypergraphs.
In this paper, we show that the proposed framework can achieve state-of-the-art performance.
Experiments from various domains including social network analysis, visual objective classification, protein learning demonstrate that the proposed framework can achieve state-of-the-art performance.
arXiv Detail & Related papers (2022-03-31T10:46:47Z) - Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data.
We present a novel Graph Matching based GNN Pre-Training framework, called GMPT.
The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
arXiv Detail & Related papers (2022-03-03T09:53:53Z) - Adaptive Neural Message Passing for Inductive Learning on Hypergraphs [21.606287447052757]
We present HyperMSG, a novel hypergraph learning framework.
It adapts to the data and task by learning an attention weight associated with each node's degree centrality.
It is robust and outperforms state-of-the-art hypergraph learning methods on a wide range of tasks and datasets.
arXiv Detail & Related papers (2021-09-22T12:24:02Z) - NetVec: A Scalable Hypergraph Embedding System [1.8979377273990425]
We introduce NetVec, a novel framework for scalable un-supervised hypergraph embedding.
We show that NetVec can becoupled with any graph embedding algorithm to produce embeddings of hypergraphs with millionsof nodes and hyperedges in a few minutes.
arXiv Detail & Related papers (2021-03-09T18:06:56Z) - Distributed Training of Graph Convolutional Networks using Subgraph
Approximation [72.89940126490715]
We propose a training strategy that mitigates the lost information across multiple partitions of a graph through a subgraph approximation scheme.
The subgraph approximation approach helps the distributed training system converge at single-machine accuracy.
arXiv Detail & Related papers (2020-12-09T09:23:49Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications.
In this formalism, a link prediction problem is converted to a graph classification task.
We propose to seek a radically different and novel path by making use of the line graphs in graph theory.
In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
arXiv Detail & Related papers (2020-10-20T05:54:31Z) - Nonlinear Higher-Order Label Spreading [30.315829440115824]
We prove convergence of our nonlinear higher-order label spreading algorithm to the global solution of a constrained semi-supervised loss function.
We demonstrate the efficiency and efficacy of our approach on a variety of point cloud and network datasets.
arXiv Detail & Related papers (2020-06-08T17:29:40Z) - Line Hypergraph Convolution Network: Applying Graph Convolution for
Hypergraphs [18.7475578342125]
We propose a novel technique to apply graph convolution on hypergraphs with variable hyperedge sizes.
We use the classical concept of line graph of a hypergraph for the first time in the hypergraph learning literature.
arXiv Detail & Related papers (2020-02-09T16:05:17Z)
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.