More Like this

1. Edge-transitive graphs and combinatorial designs

   Heather A. Newman, Hector Miranda (October 2019, Involve)

   A graph is said to be edge-transitive if its automorphism group acts transitively on its edges. It is known that edge-transitive graphs are either vertex-transitive or bipartite. We present a complete classification of all connected edge-transitive graphs on less than or equal to 20 vertices. We investigate biregular bipartite edge-transitive graphs and present connections to combinatorial designs, and we show that the Cartesian products of complements of complete graphs give an additional family of edge-transitive graphs. 

   more » « less
2. Transductive Linear Probing: A Novel Framework for Few-Shot Node Classification

   Tan, Zhen; Wang, Song; Ding, Kaize; Li, Jundong; Liu, Huan (January 2022, Proceedings of the First Learning on Graphs Conference)

   Few-shot node classification is tasked to provide accurate predictions for nodes from novel classes with only few representative labeled nodes. This problem has drawn tremendous attention for its projection to prevailing real-world applications, such as product categorization for newly added commodity categories on an E-commerce platform with scarce records or diagnoses for rare diseases on a patient similarity graph. To tackle such challenging label scarcity issues in the non-Euclidean graph domain, meta-learning has become a successful and predominant paradigm. More recently, inspired by the development of graph self-supervised learning, transferring pretrained node embeddings for few-shot node classification could be a promising alternative to meta-learning but remains unexposed. In this work, we empirically demonstrate the potential of an alternative framework, \textit{Transductive Linear Probing}, that transfers pretrained node embeddings, which are learned from graph contrastive learning methods. We further extend the setting of few-shot node classification from standard fully supervised to a more realistic self-supervised setting, where meta-learning methods cannot be easily deployed due to the shortage of supervision from training classes. Surprisingly, even without any ground-truth labels, transductive linear probing with self-supervised graph contrastive pretraining can outperform the state-of-the-art fully supervised meta-learning based methods under the same protocol. We hope this work can shed new light on few-shot node classification problems and foster future research on learning from scarcely labeled instances on graphs. 

   more » « less
3. A Collective Learning Framework to Boost GNN Expressiveness for Node Classification

   Hang, Mengyue; Neville, Jennifer; Ribeiro, Bruno (July 2021, International Conference on Machine Learning)

   Graph Neural Networks (GNNs) have recently been used for node and graph classification tasks with great success, but GNNs model dependencies among the attributes of nearby neighboring nodes rather than dependencies among observed node labels. In this work, we consider the task of inductive node classification using GNNs in supervised and semi-supervised settings, with the goal of incorporating label dependencies. Because current GNNs are not universal (i.e., most-expressive) graph representations, we propose a general collective learning approach to increase the representation power of any existing GNN. Our framework combines ideas from collective classification with self-supervised learning, and uses a Monte Carlo approach to sampling embeddings for inductive learning across graphs. We evaluate performance on five real-world network datasets and demonstrate consistent, significant improvement in node classification accuracy, for a variety of state-of-the-art GNNs. 

   more » « less
4. Removing Symmetry in Circulant Graphs and Point-Block Incidence Graphs

   https://doi.org/10.3390/math9020166  

   Brooks, Josephine; Carbonero, Alvaro; Vargas, Joseph; Florez, Rigoberto; Rooney, Brendan; Narayan, Darren A (January 2021, Mathematics)

   null (Ed.)

   An automorphism of a graph is a mapping of the vertices onto themselves such that connections between respective edges are preserved. A vertex v in a graph G is fixed if it is mapped to itself under every automorphism of G. The fixing number of a graph G is the minimum number of vertices, when fixed, fixes all of the vertices in G. The determination of fixing numbers is important as it can be useful in determining the group of automorphisms of a graph-a famous and difficult problem. Fixing numbers were introduced and initially studied by Gibbons and Laison, Erwin and Harary and Boutin. In this paper, we investigate fixing numbers for graphs with an underlying cyclic structure, which provides an inherent presence of symmetry. We first determine fixing numbers for circulant graphs, showing in many cases the fixing number is 2. However, we also show that circulant graphs with twins, which are pairs of vertices with the same neighbourhoods, have considerably higher fixing numbers. This is the first paper that investigates fixing numbers of point-block incidence graphs, which lie at the intersection of graph theory and combinatorial design theory. We also present a surprising result-identifying infinite families of graphs in which fixing any vertex fixes every vertex, thus removing all symmetries from the graph. 

   more » « less
5. Hamiltonian Cycles in Tough (P4∪P1)‐Free Graphs

   https://doi.org/10.1002/jgt.70090  

   Shan, Songling (July 2026, Journal of Graph Theory)

   ABSTRACT In 1973, Chvátal conjectured that there exists a constant such that every ‐tough graph on at least three vertices is Hamiltonian. This conjecture has inspired extensive research and has been verified for several special classes of graphs. Notably, Jung in 1978 proved that every 1‐tough ‐free graph on at least three vertices is Hamiltonian. However, the problem remains challenging even when restricted to graphs with no induced , the disjoint union of a path on four vertices and a one‐vertex path. In 2013, Nikoghosyan conjectured that every 1‐tough ‐free graph on at least three vertices is Hamiltonian. Later in 2015, Broersma remarked that “this question seems to be very hard to answer, even if we impose a higher toughness.” Instead he posed the following question: “Is the general conjecture of Chvátal's true for ‐free graphs?” We provide a positive answer to Broersma's question by establishing that every 23‐tough ‐free graph on at least three vertices is Hamiltonian. 

   more » « less