Maximal knotless graphs have at least 74% of their vertices' edges.
problem Characterizing maximal knotless graphs and understanding their edge constraints.
method Analyzing edge maximality and constructing graphs to meet constraints.
result There exists an infinite family of maximal knotless graphs with fewer edges than previously thought.
New bounds on maximal linkless graphs with improved edge-to-vertex ratios.
problem Finding maximal linklessly embeddable graphs with improved edge-to-vertex ratios.
method Constructing families of graphs and proving necessary and sufficient conditions for clique sums.
result Improved edge-to-vertex ratios for maximal linklessly embeddable graphs.
A maximally linkless graph is a graph that can be embedded in R3 without any links, but cannot be embedded in such a way if any other edge is added to the graph. Recently, a family of maximally linkless graphs was found with m=3n−3 edges. We improve upon this by demonstrating a new family of maximally lin…
The paper shows conflict graphs of Petersen family graphs are mostly unbalanced.
problem Understanding the balance of conflict graphs in Petersen family graphs.
method Analyzing maximally planar subgraphs and their conflict graphs.
result All but three strong conflict graphs from Petersen Family Graphs are unbalanced.
The study extends Tutte's conflict graph concept to nonplanar graphs.
problem Understanding the structure of nonplanar graphs through conflict graphs.
method Defining a signed conflict graph for maximally planar subgraphs and analyzing their balance.
result For graphs with a flat embedding, every maximal planar subgraph has unbalanced conflict graphs if and only if the graph is intrinsically linked.
Maximal diameter theorem for graphs with positive Ricci curvature.
problem Diameter comparison in directed graphs with positive Ricci curvature.
method Introduced a Lin-Lu-Yau type Ricci curvature for directed graphs and investigated rigidity properties for the equality case.
result Concluded a maximal diameter theorem of Cheng type.
Study finds maximal linklessly embeddable graphs up to 11 vertices and their complements.
problem Characterizing linklessly embeddable graphs and their complements.
method Comprehensive search and verification of graphs up to 11 vertices.
result For graphs of order 11, either the graph or its complement is intrinsically linked.
Constructs graphs with singularities in a special space.
problem Creating graphs with specific singularities in a unique space.
method Using Weierstrass representation for minimal surfaces.
result Constructs entire singly periodic graphs with isolated cone-like singularities.
Maximal surfaces in Lorentz-Minkowski space have conjugate graphs.
problem Characterizing maximal surfaces in Lorentz-Minkowski space.
method Three proofs showing correspondence to minimal surfaces in Euclidean space.
result Conjugate surface of a maximal graph over a convex domain is also a graph.
We extend Osserman's lemma on the generalized Gauss map of two-dimensional minimal graphs of higher codimension, construct a Jenkins-Serrin type special Lagrangian Scherk graph explicitly, and generalize Calabi's correspondence between minimal graphs and maximal graphs.
We show that the number of entire maximal graphs with finitely many singular points that are conformally equivalent is a universal constant that depends only on the number of singularities, namely 2^$ for graphs with n+1 singularities. We also give an explicit description of the family of entire maximal graphs with a f…
In the lorentzian product Gn×R1, we give a comparison between the f-volume of an entire f-maximal graph and the f-volume of the hyperbolic Hr+ under the assumption that the gradient of the function defining the graph is bounded away from 1. As a consequence, we obtain a Bernstein type theor…
Algorithm calculates genus of embedded graphs on surfaces.
problem Finding minimal and maximal genus for graph embeddings.
method Constructing special branched coverings of the 2-sphere.
result Algorithm calculates orientable genus and maximal genus of graphs.
New simplicial complex for infinite-type surfaces shows graph properties.
problem Characterizing infinite-type surfaces using graph theory.
method Constructing grand arc graph and analyzing its properties.
result Grand arc graph is infinite-diameter and δ-hyperbolic under certain conditions.
New constructions from non-separating planar graphs improve understanding of graph linkability and knotability.
problem Understanding linkability and knotability of graph complements.
method Using maximal non-separating planar graphs to construct examples of maximal linkless and knotless graphs, and analyzing their Colin de Verdière invariant.
result The Colin de Verdière invariant of the complement of a maximal non-separating planar graph satisfies μ(cG) ≤ n-4, and equality holds.
In this paper, we unify the Markov theory of a variety of different types of graphs used in graphical Markov models by introducing the class of loopless mixed graphs, and show that all independence models induced by m-separation on such graphs are compositional graphoids. We focus in particular on the subclass of rib…
New method for fair influence maximization in social networks.
problem Maximizing influence while ensuring fairness across sensitive attributes.
method Co-training an auto-encoder and discriminator to create fair graph embeddings.
result Our method reduces disparity while maintaining competitive influence maximization performance.
New method constructs graphs from data efficiently, suitable for large datasets.
problem Memory and runtime limitations of traditional TMFG for large datasets.
method Uses k-Nearest Neighbors Graphs and memory management for scalable graph construction.
result Provides a parsimonious way to construct graphs for learning tasks.
GraphCL learns node representations by maximizing similarity between perturbed node features.
problem Learning node representations in graph data without labeled data.
method Contrastive learning of node embeddings using graph neural networks and a loss function.
result Significantly outperforms state-of-the-art in unsupervised node classification benchmarks.
Proposes a novel graph self-training method with EM regularization for semi-supervised node classification.
problem Handles noisy graph structures and feature spaces in semi-supervised node classification.
method Introduces an Expectation-Maximization (EM) regularization scheme for uncertainty-aware pseudo-label generation and model retraining.
result Significantly outperforms strong baselines by up to 2.5% in accuracy.
If the Lorentzian norm on a maximal surface in the 3-dimensional Lorentz-Minkowski space R13 is positive and proper, then the surface is relative parabolic. As a consequence, entire maximal graphs with a closed set of isolated singularities are relative parabolic. Furthermore, maximal and minimal graphs over closed…
This work improves GNN training efficiency by maximizing ego-graph information.
problem Training dedicated GNNs is costly for large-scale graphs.
method Proposes EGI (Ego-Graph Information maximization) to capture essential graph information and establish a theoretical framework for transfer learning.
result Demonstrates the effectiveness of EGI in improving GNN training efficiency and transferability.
New theorem connects minimal and maximal surfaces, affecting graphness.
problem Understanding graphness of minimal surfaces in different spaces.
method Introducing a new deformation family and proving Krust-type theorems.
result Graphness of minimal surfaces in isotropic 3-space affects deformed surfaces.
A novel method integrates feature and topology views for unsupervised graph representation learning.
problem Lack of mutual information across feature and topology views in graph representation learning.
method Proposes a multi-view representation learning module and a common representation learning module using mutual information maximization and reconstruction loss minimization.
result Demonstrates effectiveness in integrating feature and topology views, achieving comparable or better performance than supervised methods.
We construct a partial order relation which acts on the set of 3-cliques of a maximal planar graph G and defines a unique hierarchy. We demonstrate that G is the union of a set of special subgraphs, named `bubbles', that are themselves maximal planar graphs. The graph G is retrieved by connecting these bubbles in a tre…
A new algorithm learns MAGs from data more efficiently using entropy.
problem Learning MAGs from data is unstable and computationally expensive.
method Uses entropy estimation and refined Markov property to score MAGs.
result Algorithm is polynomial in number of nodes and outperforms existing methods.
We show that a Born-Infeld soliton can be realised either as a spacelike minimal graph or timelike minimal graph over a timelike plane or a combination of both away from singular points. We also obtain some exact solutions of the Born-Infeld equation from already known solutions to the maximal surface equation. Further…
Iterative Proportional Fitting (IPF), combined with EM, is commonly used as an algorithm for likelihood maximization in undirected graphical models. In this paper, we present two iterative algorithms that generalize upon IPF. The first one is for likelihood maximization in discrete chain factor graphs, which we define …
The main goal of this survey is to illustrate geometric applications of the Poincaré Lemma to constant mean curvature equations. In 1970, Calabi introduced the duality between minimal graphs in three dimensional Euclidean space and maximal graphs in three dimensional Lorentz space. We construct two extensions of Calabi…
A variety of graph neural networks (GNNs) frameworks for representation learning on graphs have been recently developed. These frameworks rely on aggregation and iteration scheme to learn the representation of nodes. However, information between nodes is inevitably lost in the scheme during learning. In order to reduce…
In this paper we establish some parabolicity criteria for maximal surfaces immersed into a Lorentzian product space of the form M2×R1, where M2 is a connected Riemannian surface with non-negative Gaussian curvature and M2×R1 is endowed with the Lorentzian product metric $<,>=<,>_M…
New GCNs solve graph embedding problems efficiently and interpretably.
problem Graph embedding for scalable and interpretable machine learning.
method Proposed two GCNs: CAFE-GCN and sphere-GCN, based on constrained optimization.
result Both GCNs yield good approximations of dominant eigenvectors and perform dimensionality reduction.
Spatio-temporal graphs such as traffic networks or gene regulatory systems present challenges for the existing deep learning methods due to the complexity of structural changes over time. To address these issues, we introduce Spatio-Temporal Deep Graph Infomax (STDGI)---a fully unsupervised node representation learning…
MissNODAG learns cyclic causal graphs from incomplete data.
problem Causal discovery in systems with feedback loops and missing data.
method Differentiable framework integrating additive noise model and expectation-maximization.
result MissNODAG uncovers cyclic structures and missingness mechanisms from partially observed data.
Convolution operations designed for graph-structured data usually utilize the graph Laplacian, which can be seen as message passing between the adjacent neighbors through a generic random walk. In this paper, we propose PAN, a new graph convolution framework that involves every path linking the message sender and recei…
We consider the Dirichlet boundary value problem for graphical maximal submanifolds inside Lorentzian type ambient spaces, and obtain general existence and uniqueness results which apply to any codimension.
Graph products inherit Morse local-to-global property from their components.
problem Generalizing local-to-global property to graph products of infinite groups.
method Generalizing maximization procedure for relatively hierarchically hyperbolic groups and showing stable embeddings.
result Graph products of infinite Morse local-to-global groups have the Morse local-to-global property.
Maximizes mixing efficiency in surface braids.
problem Finding the maximum mixing efficiency in surface braids.
method Introduced an efficient algorithm to compute topological entropy and TEPO for surface braids.
result Conjectured a novel candidate braid to have maximal mixing efficiency.
This paper studies learning the representations of whole graphs in both unsupervised and semi-supervised scenarios. Graph-level representations are critical in a variety of real-world applications such as predicting the properties of molecules and community analysis in social networks. Traditional graph kernel based me…
A new method improves graph node embeddings by considering both nearby and distant node similarities.
problem Improving graph node embeddings by considering both nearby and distant node similarities.
method Distance-aware Negative Sampling (DNS) which maximizes cohesion at nearby node-pairs and separation at distant node-pairs.
result DNS outperforms baseline methods in downstream node classification tasks on various datasets and GRL algorithms.
The richness in the content of various information networks such as social networks and communication networks provides the unprecedented potential for learning high-quality expressive representations without external supervision. This paper investigates how to preserve and extract the abundant information from graph-s…
Unsupervised method learns hierarchical graph representations without labels.
problem Lack of hierarchical graph representations and need for labeled data in GNNs.
method Maximizes mutual information between local and global graph representations.
result Comparable performance to supervised methods on graph classification benchmarks.
Graph clustering improved using Boltzmann machine heuristics.
problem Graph clustering to form densely connected clusters.
method Two mathematical programming formulations, two variations of Boltzmann machine heuristic.
result Boltzmann machine provides superior solutions and faster computation times.
Graph Neural Networks (GNNs) achieve an impressive performance on structured graphs by recursively updating the representation vector of each node based on its neighbors, during which parameterized transformation matrices should be learned for the node feature updating. However, existing propagation schemes are far fro…
A novel algorithm for unsupervised graph representation learning combining coarsening and mutual information maximization.
problem Current limitations in unsupervised graph representation learning, especially in embedding new graphs and considering both micro- and macro-structures.
method Combines coarsening with mutual information maximization to produce high-quality embeddings.
result The algorithm produces high-quality embeddings that are competitive with state-of-the-art methods.
New algorithms optimize decision-making under uncertainty with graph information.
problem Optimizing decisions in large, uncertain environments with graph-based similarities.
method Graph-based UcB and ζ-UcB algorithms for maximizing and satisficing.
result Proves algorithms are near-optimal and benefits from graph side information.
Explains partial duality for ribbon graphs in simple terms.
problem Understanding partial duality in ribbon graphs.
method Simplified explanation of existing research on hypermaps.
result Simplified exposition of complex graph theory concepts.
Investigates sequential problems on graph structures and large action spaces.
problem Sequential decision-making on graph structures and large action spaces.
method Spectral bandits, side observations, influence maximization, kernel bandits, polymatroid bandits, function optimization, infinitely many-arms bandits.
result Contributions to graph and structured bandits.