Factorized Graph Representations for Semi-Supervised Learning from Sparse Data

• URL: http://arxiv.org/abs/2003.02829v1
• Date: Thu, 5 Mar 2020 18:57:45 GMT
• Title: Factorized Graph Representations for Semi-Supervised Learning from Sparse Data
• Authors: Krishna Kumar P. and Paul Langton and Wolfgang Gatterbauer
• Abstract summary: We show that a method called distant compatibility estimation works even on extremely sparsely labeled graphs. Our estimator is by orders of magnitude faster than an alternative approach and that the end-to-end classification accuracy is comparable to using gold standard compatibilities.
• Score: 8.875598257768846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Node classification is an important problem in graph data management. It is commonly solved by various label propagation methods that work iteratively starting from a few labeled seed nodes. For graphs with arbitrary compatibilities between classes, these methods crucially depend on knowing the compatibility matrix that must be provided by either domain experts or heuristics. Can we instead directly estimate the correct compatibilities from a sparsely labeled graph in a principled and scalable way? We answer this question affirmatively and suggest a method called distant compatibility estimation that works even on extremely sparsely labeled graphs (e.g., 1 in 10,000 nodes is labeled) in a fraction of the time it later takes to label the remaining nodes. Our approach first creates multiple factorized graph representations (with size independent of the graph) and then performs estimation on these smaller graph sketches. We define algebraic amplification as the more general idea of leveraging algebraic properties of an algorithm's update equations to amplify sparse signals. We show that our estimator is by orders of magnitude faster than an alternative approach and that the end-to-end classification accuracy is comparable to using gold standard compatibilities. This makes it a cheap preprocessing step for any existing label propagation method and removes the current dependence on heuristics.

Related papers

• HeteroMILE: a Multi-Level Graph Representation Learning Framework for Heterogeneous Graphs [13.01983932286923]
  We propose a Multi-Level Embedding framework of nodes on a heterogeneous graph (HeteroMILE) HeteroMILE repeatedly coarsens the large sized graph into a smaller size while preserving the backbone structure of the graph before embedding it. It then refines the coarsened embedding to the original graph using a heterogeneous graph convolution neural network.
  arXiv  Detail & Related papers  (2024-03-31T22:22:10Z)
• 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)
• 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)
• Demystifying Graph Convolution with a Simple Concatenation [6.542119695695405]
  We quantify the information overlap between graph topology, node features, and labels. We show that graph concatenation is a simple but more flexible alternative to graph convolution.
  arXiv  Detail & Related papers  (2022-07-18T16:39:33Z)
• Geometer: Graph Few-Shot Class-Incremental Learning via Prototype Representation [50.772432242082914]
  Existing graph neural network based methods mainly focus on classifying unlabeled nodes within fixed classes with abundant labeling. In this paper, we focus on this challenging but practical graph few-shot class-incremental learning (GFSCIL) problem and propose a novel method called Geometer. Instead of replacing and retraining the fully connected neural network classifer, Geometer predicts the label of a node by finding the nearest class prototype.
  arXiv  Detail & Related papers  (2022-05-27T13:02:07Z)
• Learning Based Proximity Matrix Factorization for Node Embedding [33.18041180501025]
  Recent progress on node embedding shows that proximity matrix factorization methods gain superb performance and scale to large graphs with millions of nodes. We propose em Lemane, a framework with trainable proximity measures, which can be learned to best suit the datasets and tasks at hand automatically. Our proposed solution outperforms existing solutions on both link prediction and node classification tasks on almost all datasets.
  arXiv  Detail & Related papers  (2021-06-10T03:29:15Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• 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)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.