Efficient Learning on Large Graphs using a Densifying Regularity Lemma

• URL: http://arxiv.org/abs/2504.18273v1
• Date: Fri, 25 Apr 2025 11:34:44 GMT
• Title: Efficient Learning on Large Graphs using a Densifying Regularity Lemma
• Authors: Jonathan Kouchly, Ben Finkelshtein, Michael Bronstein, Ron Levie,
• Abstract summary: We introduce a low-rank factorization of large directed graphs based on combinations of intersecting bipartite components.<n>We show how to efficiently approximate any graph, sparse or dense, by a dense IBG.
• Score: 7.2134828716289645
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning on large graphs presents significant challenges, with traditional Message Passing Neural Networks suffering from computational and memory costs scaling linearly with the number of edges. We introduce the Intersecting Block Graph (IBG), a low-rank factorization of large directed graphs based on combinations of intersecting bipartite components, each consisting of a pair of communities, for source and target nodes. By giving less weight to non-edges, we show how to efficiently approximate any graph, sparse or dense, by a dense IBG. Specifically, we prove a constructive version of the weak regularity lemma, showing that for any chosen accuracy, every graph, regardless of its size or sparsity, can be approximated by a dense IBG whose rank depends only on the accuracy. This dependence of the rank solely on the accuracy, and not on the sparsity level, is in contrast to previous forms of the weak regularity lemma. We present a graph neural network architecture operating on the IBG representation of the graph and demonstrating competitive performance on node classification, spatio-temporal graph analysis, and knowledge graph completion, while having memory and computational complexity linear in the number of nodes rather than edges.

Related papers

• Learning on Large Graphs using Intersecting Communities [13.053266613831447]
  MPNNs iteratively update each node's representation in an input graph by aggregating messages from the node's neighbors.<n>MPNNs might quickly become prohibitive for large graphs provided they are not very sparse.<n>We propose approximating the input graph as an intersecting community graph (ICG) -- a combination of intersecting cliques.
  arXiv  Detail & Related papers  (2024-05-31T09:26:26Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs) This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings. Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
  arXiv  Detail & Related papers  (2024-05-27T17:52:12Z)
• 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)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings [51.82434518719011]
  GNNAutoScale (GAS) is a framework for scaling arbitrary message-passing GNNs to large graphs. Gas prunes entire sub-trees of the computation graph by utilizing historical embeddings from prior training iterations. Gas reaches state-of-the-art performance on large-scale graphs.
  arXiv  Detail & Related papers  (2021-06-10T09:26:56Z)
• Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
  Graph embedding is a way to transform and encode the data structure in high dimensional and non-Euclidean feature space. CensNet is a general graph embedding framework, which embeds both nodes and edges to a latent feature space. Our approach achieves or matches the state-of-the-art performance in four graph learning tasks.
  arXiv  Detail & Related papers  (2020-10-25T22:39:31Z)
• 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)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  We propose an end-to-end graph learning framework, namely Iterative Deep Graph Learning (IDGL) for jointly and iteratively learning graph structure and graph embedding. Our experiments show that our proposed IDGL models can consistently outperform or match the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2020-06-21T19:49:15Z)
• CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
  Graph Neural Networks (GNNs) provide a data-driven solution for this task. Existing GNN-based methods, which either respectively embeds two graphs or deploy cross-graph interactions for whole graph pairs, are still not able to achieve competitive results. We propose the "embedding-coarsening-matching" framework CoSimGNN, which first embeds and coarsens large graphs with adaptive pooling operation and then deploys fine-grained interactions on the coarsened graphs for final similarity scores.
  arXiv  Detail & Related papers  (2020-05-14T16:33:13Z)

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.