More Like this

1. Graph mixup with soft alignments

   Hongyi Ling, Zhimeng Jiang (July 2023, ICML2023)

   We study graph data augmentation by mixup, which has been used successfully on images. A key operation of mixup is to compute a convex combination of a pair of inputs. This operation is straightforward for grid-like data, such as images, but challenging for graph data. The key difficulty lies in the fact that different graphs typically have different numbers of nodes, and thus there lacks a node-level correspondence between graphs. In this work, we propose S-Mixup, a simple yet effective mixup method for graph classification by soft alignments. Specifically, given a pair of graphs, we explicitly obtain node-level correspondence via computing a soft assignment matrix to match the nodes between two graphs. Based on the soft assignments, we transform the adjacency and node feature matrices of one graph, so that the transformed graph is aligned with the other graph. In this way, any pair of graphs can be mixed directly to generate an augmented graph. We conduct systematic experiments to show that S-Mixup can improve the performance and generalization of graph neural networks (GNNs) on various graph classification tasks. In addition, we show that S-Mixup can increase the robustness of GNNs against noisy labels. Our code is publicly available as part of the DIG package (https://github.com/divelab/DIG). 

   more » « less
2. On Graph Neural Networks versus Graph-Augmented MLPs

   Chen, Lei; Chen, Zhengdao; Bruna, Joan (April 2021, International Conference on Learning Representations)

   null (Ed.)

   From the perspective of expressive power, this work compares multi-layer Graph Neural Networks (GNNs) with a simplified alternative thatwe call Graph-Augmented Multi-Layer Perceptrons (GA-MLPs), which first augments node features with certain multi-hop operators on the graph and then applies an MLP in a node-wise fashion. From the perspective of graph isomorphism testing,we showboth theoretically and numerically that GA-MLPs with suitable operators can distinguish almost all non-isomorphic graphs, just like the Weifeiler-Lehman (WL) test. However, by viewing them as node-level functions and examining the equivalence classes they induce on rooted graphs, we prove a separation in expressive power between GA-MLPs and GNNs that grows exponentially in depth. In particular, unlike GNNs, GA-MLPs are unable to count the number of attributed walks. We also demonstrate via community detection experiments that GA-MLPs can be limited by their choice of operator family, as compared to GNNs with higher flexibility in learning. 

   more » « less
3. On Graph Neural Networks versus Graph-Augmented MLPs

   Chen, Z; Chen, L; Bruna, J (April 2021, international conference on learning representations)

   null (Ed.)

   From the perspective of expressive power, this work compares multi-layer Graph Neural Networks (GNNs) with a simplified alternative that we call Graph-Augmented Multi-Layer Perceptrons (GA-MLPs), which first augments node features with certain multi-hop operators on the graph and then applies an MLP in a node-wise fashion. From the perspective of graph isomorphism testing, we show both theoretically and numerically that GA-MLPs with suitable operators can distinguish almost all non-isomorphic graphs, just like the Weifeiler-Lehman (WL) test. However, by viewing them as node-level functions and examining the equivalence classes they induce on rooted graphs, we prove a separation in expressive power between GA-MLPs and GNNs that grows exponentially in depth. In particular, unlike GNNs, GA-MLPs are unable to count the number of attributed walks. We also demonstrate via community detection experiments that GA-MLPs can be limited by their choice of operator family, as compared to GNNs with higher flexibility in learning. 

   more » « less
4. Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning

   Li, Pan; Wang, Yanbang; Wang, Hongwei; Leskovec, Jure. (January 2020, Neural Information Processing Systems (NeurIPS))

   Learning representations of sets of nodes in a graph is crucial for applications ranging from node-role discovery to link prediction and molecule classification. Graph Neural Networks (GNNs) have achieved great success in graph representation learning. However, expressive power of GNNs is limited by the 1-Weisfeiler-Lehman (WL) test and thus GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order-WL tests, only focus on representing entire graphs and they are computationally inefficient as they cannot utilize sparsity of the underlying graph. Here we propose and mathematically analyze a general class of structure related features, termed Distance Encoding (DE). DE assists GNNs in representing any set of nodes, while providing strictly more expressive power than the 1-WL test. DE captures the distance between the node set whose representation is to be learned and each node in the graph. To capture the distance DE can apply various graph-distance measures such as shortest path distance or generalized PageRank scores. We propose two ways for GNNs to use DEs (1) as extra node features, and (2) as controllers of message aggregation in GNNs. Both approaches can utilize the sparse structure of the underlying graph, which leads to computational efficiency and scalability. We also prove that DE can distinguish node sets embedded in almost all regular graphs where traditional GNNs always fail. We evaluate DE on three tasks over six real networks: structural role prediction, link prediction, and triangle prediction. Results show that our models outperform GNNs without DE by up-to 15% in accuracy and AUROC. Furthermore, our models also significantly outperform other state-of-the-art methods especially designed for the above tasks. 

   more » « less
5. Nonlinear Correct and Smooth for Graph-Based Semi-Supervised Learning

   https://doi.org/10.1145/3712604  

   Shao, Yuanhang; Liu, Xiuwen (April 2025, ACM Transactions on Knowledge Discovery from Data)

   Graph-based semi-supervised learning (GSSL) has achieved significant success across various applications by leveraging the graph structure and labeled samples for classification tasks. In the field of GSSL, Label Propagation (LP) and Graph Neural Networks (GNNs) are two complementary methods, in which LP iteratively propagates and updates node labels through connected nodes, whereas GNNs aggregate node features by incorporating information from their neighbors. Recently, the complementary nature of LP and GNNs has been utilized to improve performance through the combination of two approaches. However, the utilization of higher-order graph structures within these combined approaches, such as triangles, is still under-explored. Therefore, to advance understanding in this ongoing research, we first model GSSL as a two-step feature-label process. Then, we introduce Nonlinear Correct and Smooth (NLCS) in the post-processing step, a combined method that incorporates nonlinearity and higher-order structures into the residual propagation to handle intricate node relationships effectively. We propose a new synthetic graph generator to deepen the analysis and broaden the experimentation, providing insights into the mechanisms that enable NLCS to handle intricate node relationships effectively. Our systematic evaluations across six synthetic graphs show that NLCS outperforms base predictions by an average of 12.44% and the existing state-of-the-art post-processing method by 8.04%. Furthermore, on six commonly used real-world datasets, NLCS demonstrates a 10.9% improvement over six base prediction models and a 1.6% over the state-of-the-art post-processing method. Our comparisons and analyses reveal that NLCS substantially enhances the prediction accuracy of nodes within complex graph structures by effectively utilizing higher-order structures of graphs. 

   more » « less