GraphHop: An Enhanced Label Propagation Method for Node Classification

• URL: http://arxiv.org/abs/2101.02326v1
• Date: Thu, 7 Jan 2021 02:10:20 GMT
• Title: GraphHop: An Enhanced Label Propagation Method for Node Classification
• Authors: Tian Xie, Bin Wang, C.-C. Jay Kuo
• Abstract summary: A scalable semi-supervised node classification method, called GraphHop, is proposed in this work. Experimental results show that GraphHop outperforms state-of-the-art graph learning methods on a wide range of tasks.
• Score: 34.073791157290614
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A scalable semi-supervised node classification method on graph-structured data, called GraphHop, is proposed in this work. The graph contains attributes of all nodes but labels of a few nodes. The classical label propagation (LP) method and the emerging graph convolutional network (GCN) are two popular semi-supervised solutions to this problem. The LP method is not effective in modeling node attributes and labels jointly or facing a slow convergence rate on large-scale graphs. GraphHop is proposed to its shortcoming. With proper initial label vector embeddings, each iteration of GraphHop contains two steps: 1) label aggregation and 2) label update. In Step 1, each node aggregates its neighbors' label vectors obtained in the previous iteration. In Step 2, a new label vector is predicted for each node based on the label of the node itself and the aggregated label information obtained in Step 1. This iterative procedure exploits the neighborhood information and enables GraphHop to perform well in an extremely small label rate setting and scale well for very large graphs. Experimental results show that GraphHop outperforms state-of-the-art graph learning methods on a wide range of tasks (e.g., multi-label and multi-class classification on citation networks, social graphs, and commodity consumption graphs) in graphs of various sizes. Our codes are publicly available on GitHub (https://github.com/TianXieUSC/GraphHop).

Related papers

• Graph Mixup with Soft Alignments [49.61520432554505]
  We study graph data augmentation by mixup, which has been used successfully on images. We propose S-Mixup, a simple yet effective mixup method for graph classification by soft alignments.
  arXiv  Detail & Related papers  (2023-06-11T22:04:28Z)
• Semi-Supervised Hierarchical Graph Classification [54.25165160435073]
  We study the node classification problem in the hierarchical graph where a 'node' is a graph instance. We propose the Hierarchical Graph Mutual Information (HGMI) and present a way to compute HGMI with theoretical guarantee. We demonstrate the effectiveness of this hierarchical graph modeling and the proposed SEAL-CI method on text and social network data.
  arXiv  Detail & Related papers  (2022-06-11T04:05:29Z)
• GraphHop++: New Insights into GraphHop and Its Enhancement [37.61655151222875]
  An enhanced label propagation (LP) method called GraphHop has been proposed recently. It outperforms graph convolutional networks (GCNs) in the semi-supervised node classification task on various networks. We show that GraphHop offers an alternate optimization to a certain regularization problem defined on graphs.
  arXiv  Detail & Related papers  (2022-04-19T03:58:47Z)
• Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
  This paper presents a cross-view graph pooling (Co-Pooling) method to better exploit crucial graph structure information. Through cross-view interaction, edge-view pooling and node-view pooling seamlessly reinforce each other to learn more informative graph-level representations.
  arXiv  Detail & Related papers  (2021-09-24T08:01:23Z)
• GraphGen-Redux: a Fast and Lightweight Recurrent Model for labeled Graph Generation [13.956691231452336]
  We present a novel graph preprocessing approach for labeled graph generation. By introducing a novel graph preprocessing approach, we are able to process the labeling information of both nodes and edges jointly. The corresponding model, which we term GraphGen-Redux, improves upon the generative performances of GraphGen in a wide range of datasets.
  arXiv  Detail & Related papers  (2021-07-18T09:26:10Z)
• GLAM: Graph Learning by Modeling Affinity to Labeled Nodes for Graph Neural Networks [0.0]
  We propose a semi-supervised graph learning method for cases when there are no graphs available. This method learns a graph as a convex combination of the unsupervised kNN graph and a supervised label-affinity graph. Our experiments suggest that this approach gives close to or better performance (up to 1.5%), while being simpler and faster (up to 70x) to train, than state-of-the-art graph learning methods.
  arXiv  Detail & Related papers  (2021-02-20T17:56:52Z)
• 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)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  Graph Identification (GI) has long been researched in graph learning and is essential in certain applications. This paper defines a novel problem dubbed Inverse Graph Identification (IGI) We propose a simple yet effective method that makes the node-level message passing process using Graph Attention Network (GAT) under the protocol of GI.
  arXiv  Detail & Related papers  (2020-07-12T12:06:17Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  We propose a multi-level graph matching network (MGMN) framework for computing the graph similarity between any pair of graph-structured objects. To compensate for the lack of standard benchmark datasets, we have created and collected a set of datasets for both the graph-graph classification and graph-graph regression tasks. Comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baseline models on both the graph-graph classification and graph-graph regression tasks.
  arXiv  Detail & Related papers  (2020-07-08T19:48:19Z)

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.