Graph Lineages and Skeletal Graph Products

• URL: http://arxiv.org/abs/2508.00197v1
• Date: Thu, 31 Jul 2025 22:31:34 GMT
• Title: Graph Lineages and Skeletal Graph Products
• Authors: Eric Mjolsness, Cory B. Scott,
• Abstract summary: Graphs, and sequences of growing graphs, can be used to specify the architecture of mathematical models in many fields including machine learning and computational science.<n>We define structured graph "lineages" that grow in a hierarchical fashion, so that the number of graph vertices and edges increases exponentially in level number.<n>We demonstrate such application to deep neural networks (including visual and feature scale spaces) and to multigrid numerical methods.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graphs, and sequences of growing graphs, can be used to specify the architecture of mathematical models in many fields including machine learning and computational science. Here we define structured graph "lineages" (ordered by level number) that grow in a hierarchical fashion, so that: (1) the number of graph vertices and edges increases exponentially in level number; (2) bipartite graphs connect successive levels within a graph lineage and, as in multigrid methods, can constrain matrices relating successive levels; (3) using prolongation maps within a graph lineage, process-derived distance measures between graphs at successive levels can be defined; (4) a category of "graded graphs" can be defined, and using it low-cost "skeletal" variants of standard algebraic graph operations and type constructors (cross product, box product, disjoint sum, and function types) can be derived for graded graphs and hence hierarchical graph lineages; (5) these skeletal binary operators have similar but not identical algebraic and category-theoretic properties to their standard counterparts; (6) graph lineages and their skeletal product constructors can approach continuum limit objects. Additional space-efficient unary operators on graded graphs are also derived: thickening, which creates a graph lineage of multiscale graphs, and escalation to a graph lineage of search frontiers (useful as a generalization of adaptive grids and in defining "skeletal" functions). The result is an algebraic type theory for graded graphs and (hierarchical) graph lineages. The approach is expected to be well suited to defining hierarchical model architectures - "hierarchitectures" - and local sampling, search, or optimization algorithms on them. We demonstrate such application to deep neural networks (including visual and feature scale spaces) and to multigrid numerical methods.

Related papers

• Disentangled Graph Representation Based on Substructure-Aware Graph Optimal Matching Kernel Convolutional Networks [4.912298804026689]
  Graphs effectively characterize relational data, driving graph representation learning methods.<n>Recent disentangled graph representation learning enhances interpretability by decoupling independent factors in graph data.<n>This paper proposes the Graph Optimal Matching Kernel Convolutional Network (GOMKCN) to address this limitation.
  arXiv  Detail & Related papers  (2025-04-23T02:26:33Z)
• Knowledge Probing for Graph Representation Learning [12.960185655357495]
  We propose a novel graph probing framework (GraphProbe) to investigate and interpret whether the family of graph learning methods has encoded different levels of knowledge in graph representation learning. Based on the intrinsic properties of graphs, we design three probes to systematically investigate the graph representation learning process from different perspectives. We construct a thorough evaluation benchmark with nine representative graph learning methods from random walk based approaches, basic graph neural networks and self-supervised graph methods, and probe them on six benchmark datasets for node classification, link prediction and graph classification.
  arXiv  Detail & Related papers  (2024-08-07T16:27:45Z)
• PlanE: Representation Learning over Planar Graphs [9.697671872347131]
  This work is inspired by the classical planar graph isomorphism algorithm of Hopcroft and Tarjan. PlanE includes architectures which can learn complete invariants over planar graphs while remaining practically scalable.
  arXiv  Detail & Related papers  (2023-07-03T17:45:01Z)
• HiGen: Hierarchical Graph Generative Networks [2.3931689873603603]
  Most real-world graphs exhibit a hierarchical structure, which is often overlooked by existing graph generation methods. We propose a novel graph generative network that captures the hierarchical nature of graphs and successively generates the graph sub-structures in a coarse-to-fine fashion. This modular approach enables scalable graph generation for large and complex graphs.
  arXiv  Detail & Related papers  (2023-05-30T18:04:12Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• State of the Art and Potentialities of Graph-level Learning [54.68482109186052]
  Graph-level learning has been applied to many tasks including comparison, regression, classification, and more. Traditional approaches to learning a set of graphs rely on hand-crafted features, such as substructures. Deep learning has helped graph-level learning adapt to the growing scale of graphs by extracting features automatically and encoding graphs into low-dimensional representations.
  arXiv  Detail & Related papers  (2023-01-14T09:15:49Z)
• Explanation Graph Generation via Pre-trained Language Models: An Empirical Study with Contrastive Learning [84.35102534158621]
  We study pre-trained language models that generate explanation graphs in an end-to-end manner. We propose simple yet effective ways of graph perturbations via node and edge edit operations. Our methods lead to significant improvements in both structural and semantic accuracy of explanation graphs.
  arXiv  Detail & Related papers  (2022-04-11T00:58:27Z)
• CommPOOL: An Interpretable Graph Pooling Framework for Hierarchical Graph Representation Learning [74.90535111881358]
  We propose a new interpretable graph pooling framework - CommPOOL. It can capture and preserve the hierarchical community structure of graphs in the graph representation learning process. CommPOOL is a general and flexible framework for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2020-12-10T21:14:18Z)
• GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
  We propose an end-to-end framework that learns an implicit model of graph structure formation and discovers an underlying optimization mechanism. The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain. GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm.
  arXiv  Detail & Related papers  (2020-07-07T16:51:39Z)
• 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)
• Graph Signal Processing -- Part III: Machine Learning on Graphs, from Graph Topology to Applications [19.29066508374268]
  Part III of this monograph starts by addressing ways to learn graph topology. A particular emphasis is on graph topology definition based on the correlation and precision matrices of the observed data. For learning sparse graphs, the least absolute shrinkage and selection operator, known as LASSO is employed.
  arXiv  Detail & Related papers  (2020-01-02T13:14:27Z)

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.