All articles starting with G
18,970 articles
Graph Cartesian product
The graph Cartesian product, denoted G square H and also called the box product, is a binary operation on graphs whose vertices are ordered pairs, adjacent when they differ in exactly one coordinate.
Graph coloring
Graph coloring assigns colors to a graph's vertices so adjacent vertices get different colors, a central problem from map coloring; the four color theorem and scheduling are key examples.
Graph contrastive learning
Graph contrastive learning is a self-supervised method that learns node and graph representations without labels by contrasting augmented views, feeding tasks like node classification, graph classification, and drug discovery.
Graph convolutional network
A graph convolutional network (GCN) is a neural network architecture that applies convolution over graph-structured data, introduced by Kipf and Welling in 2016 and used chiefly for node classification and recommendation.
Graph database
A graph database is a database management system that stores data as nodes connected by edges and queries it by traversing connections rather than joining tables.
Graph drawing
Graph drawing, also called graph layout, is the branch of computer science that positions graph vertices and routes edges to render networks as readable diagrams.
Graph embedding
A graph embedding is a placement of a graph on a surface with vertices as points and edges as noncrossing curves, the central object of topological graph theory.
Graph filter
A graph filter is a linear operator that processes signals on graph vertices, typically a polynomial of the graph shift operator, and is the basic building block of graph signal processing.
Graph Fourier transform
The graph Fourier transform decomposes a signal defined on a graph's vertices into components carried by the eigenvectors of the graph Laplacian, like the classical Fourier transform.
Graph invariant
A graph invariant, also called a graph property, is a quantity of a graph that depends only on its structure, not on vertex labels or how it is drawn.
Graph isomorphism
Graph isomorphism, also called testing isomorphic graphs, asks whether two graphs have the same structure up to renaming vertices; László Babai's 2015 quasipolynomial algorithm was a major breakthrough.
Graph isomorphism network
A graph isomorphism network (GIN) is a graph neural network architecture that updates each node by summing neighbor features through an MLP, matching the 1-WL isomorphism test's power.
Graph isomorphism problem
The graph isomorphism problem asks whether two graphs can be relabeled to be identical. It lies in NP, and László Babai gave a quasipolynomial-time algorithm in 2015.
Graph kernel
A graph kernel is a positive semidefinite similarity function between graphs, letting kernel methods such as support vector machines classify graph-structured data like molecules and proteins.
Graph minor
A graph minor is a graph derived from another by deleting or contracting edges and removing isolated vertices; Robertson and Seymour developed the theory of it.
Graph neural network
A graph neural network (GNN) is a neural network model that operates directly on graph-structured data, proposed in 2005 and extended to molecules, social networks, and traffic forecasting.
Graph of a function
The graph of a function, also called a function graph, is the set of all ordered pairs relating each input to its output, plotted as points in the plane.
Graph of Thoughts
Graph of Thoughts (GoT) is a prompting framework for large language models, introduced by Besta et al. in 2023, that represents reasoning as an arbitrary graph of thoughts.
Graph partitioning
Graph partitioning divides a graph's vertices into roughly equal blocks while minimizing the edges crossing between blocks, an NP-hard problem used in parallel computing and VLSI design.
Graph reduction
Graph reduction is an implementation technique for functional programming languages in which a program is a graph rewritten in place during evaluation, introduced by Christopher Wadsworth in 1971.
Graph removal lemma
The graph removal lemma is a theorem in extremal graph theory: a graph with few copies of a fixed graph H can be made H-free by deleting few edges.
Graph rewriting
Graph rewriting is a family of formal methods in computer science that transform graphs by finding a pattern subgraph in a host graph and replacing it with a replacement.
Graph sampling
Graph sampling is a family of algorithms that randomly select nodes, edges, or subgraphs from a large graph to estimate statistics like degree and clustering when full processing is infeasible.
Graph search
Graph search is a family of algorithms that systematically explore the vertices and edges of a graph to find a target node, a path, or a structure.
Graph spectrum
The graph spectrum is the set of eigenvalues of a graph's adjacency matrix, real because the matrix is symmetric, and the subject of spectral graph theory.
Graph state
A graph state is a multi-qubit entangled quantum state defined by a simple graph, with each edge a CZ gate; its cluster states are the universal resource of the one-way quantum computer.
Graph structure learning
Graph structure learning (GSL) is a machine learning approach that jointly learns a graph's connectivity, as an adjacency matrix, with a downstream task like node classification.
Graph structure theorem
The graph structure theorem, proved by Neil Robertson and Paul Seymour, describes every graph with no fixed graph H as a minor as built from pieces embeddable in a surface.
Graph theoretical analysis
Graph theoretical analysis models systems as graphs of nodes and edges and computes summary measures, an interdisciplinary toolset applied to brain networks, power grids, and social networks.
Graph theory
Graph theory is the branch of mathematics that studies graphs, structures of vertices and edges modeling pairwise relationships, originating in Euler's 1735 analysis of the Königsberg bridges problem.