SEG-BERT improves graph instance learning by adapting GRAPH-BERT.
problem Graph instance representation learning challenges due to diverse sizes and node order.
method Adapted GRAPH-BERT with a segmented architecture to handle graph node orderlessness and diverse sizes.
result SEG-BERT outperforms comparison methods on six out of seven benchmark datasets.
Multiple instance learning (MIL) aims to learn the mapping between a bag of instances and the bag-level label. In this paper, we propose a new end-to-end graph neural network (GNN) based algorithm for MIL: we treat each bag as a graph and use GNN to learn the bag embedding, in order to explore the useful structural inf…
BeGIN benchmarks GNNs for instance-dependent label noise in graphs.
problem Instance-dependent label noise in graph data.
method BeGIN introduces a benchmark with various noise types and evaluates noise-handling strategies across GNN architectures.
result Challenges of instance-dependent noise, especially LLM-based corruption, and the importance of node-specific parameterization.
Method detects anomalies on attributed graphs with few labeled instances.
problem Detecting anomalies on connected instances (attributed graphs) with limited labeled data.
method Embed nodes in latent space using GCNs, training to distinguish normal and anomalous nodes.
result Method outperforms existing methods on real-world attributed graph datasets.
MetAL improves graph classification models with fewer labeled data.
problem Efficiently selecting unlabeled graph instances for training.
method Formulates AL as bilevel optimization, uses meta-learning to approximate model performance.
result MetAL outperforms existing AL algorithms on multiple graph datasets.
We introduce an extension of the multi-instance learning problem where examples are organized as nested bags of instances (e.g., a document could be represented as a bag of sentences, which in turn are bags of words). This framework can be useful in various scenarios, such as text and image classification, but also sup…
Hard instances, which require a long time for a specific algorithm to solve, help (1) analyze the algorithm for accelerating it and (2) build a good benchmark for evaluating the performance of algorithms. There exist several efforts for automatic generation of hard instances. For example, evolutionary algorithms have b…
Graph ConvNet learns to solve Tree Decomposition problems efficiently.
problem Tree Decomposition problem in graph theory and its applications.
method Graph Convolutional Neural Network (GCN) combined with Reinforcement Learning (Actor-Critic method).
result The model efficiently generalizes from small to large real-world instances of the TD problem.
Graph kernels have recently emerged as a promising approach for tackling the graph similarity and learning tasks at the same time. In this paper, we propose a general framework for designing graph kernels. The proposed framework capitalizes on the well-known message passing scheme on graphs. The kernels derived from th…
Partial Label Learning (PLL) aims to learn from the data where each training example is associated with a set of candidate labels, among which only one is correct. The key to deal with such problem is to disambiguate the candidate label sets and obtain the correct assignments between instances and their candidate label…
Graph Convolutional Networks (GCNs) have shown significant improvements in semi-supervised learning on graph-structured data. Concurrently, unsupervised learning of graph embeddings has benefited from the information contained in random walks. In this paper, we propose a model: Network of GCNs (N-GCN), which marries th…
HGKT transfers knowledge from seen to unseen classes in GZSL without prior unseen class info.
problem Learning to classify unseen classes in GZSL.
method Structured heterogeneous graph with graph neural network for knowledge transfer.
result Achieves state-of-the-art results on public benchmark datasets.
New method adapts to structural shifts in graph data for better label prevalence estimation.
problem Structural shifts in graph data affect label prevalence estimation.
method Importance sampling variant of KDEy quantification approach.
result Adapts to structural shifts and outperforms standard approaches.
Improves BN graph learning with splines for scalability.
problem Learning accurate BN graph structures from data.
method Score-and-search approach with MARS for CPD modeling.
result Improves BN graph accuracy and scalability.
This work proposes an unsupervised neural network framework for solving combinatorial optimization problems on graphs.
problem Challenges in neural networks solving combinatorial optimization problems without labeled instances.
method Inspired by Erdos' probabilistic method, a neural network parametrizes a probability distribution over sets, optimizing it to find low-cost integral solutions.
result The method provides valid solutions to the maximum clique problem and local graph clustering, achieving competitive results.
Novel framework for efficient entity alignment labeling.
problem Efficient labeling of entity alignments in knowledge graphs.
method Active and passive learning strategies to select informative instances.
result Passive learning achieves comparable performance to active learning.
A method learns to solve multilevel combinatorial problems with two players.
problem Multilevel combinatorial optimization problems with multiple players.
method Value-based multi-agent reinforcement learning in a graph neural network framework.
result Close to optimal solutions on graphs up to 100 nodes, with a significant speedup.
Neural networks struggle with TSP beyond small instances, requiring new approaches.
problem Neural networks struggle to generalize to larger instances of the TSP.
method Unified pipeline to identify inductive biases and promote generalization.
result Zero-shot generalization requires rethinking neural combinatorial optimization.
Graph Neural Networks (GNNs) are a powerful tool for machine learning on graphs.GNNs combine node feature information with the graph structure by recursively passing neural messages along edges of the input graph. However, incorporating both graph structure and feature information leads to complex models, and explainin…
Deep RL learns effective job shop scheduling rules from raw features.
problem Designing effective priority dispatching rules for job shop scheduling is challenging.
method End-to-end deep reinforcement learning using Graph Neural Networks.
result Agent learns high-quality dispatching rules from raw features and generalizes well to unseen instances.
MetaCaDI learns causal graphs and unknown interventions from few data instances.
problem Discovering causal mechanisms in systems with high data costs and unknown interventions.
method MetaCaDI is a Bayesian meta-learning framework that optimizes for rapid adaptation to new intervention targets.
result MetaCaDI significantly outperforms state-of-the-art methods in causal graph recovery and intervention target prediction.
Meta-learning framework improves explainability of GNNs.
problem Improving explainability of graph neural networks.
method Meta-learning framework to steer GNN training towards interpretable minima.
result Models are easier to explain by different algorithms without sacrificing accuracy.
The goal of few-shot learning is to learn a classifier that generalizes well even when trained with a limited number of training instances per class. The recently introduced meta-learning approaches tackle this problem by learning a generic classifier across a large number of multiclass classification tasks and general…
Surveying machine learning for solving graph optimization problems.
problem Solving combinatorial optimization problems on graphs requires algorithmic engineering.
method Surveying machine learning approaches for graph optimization.
result Machine learning offers new ways to solve graph optimization problems.
Automates MIPs solution with semi-supervised graph neural networks.
problem Solving recurrent Mixed-Integer Programming (MIP) problems efficiently.
method Semi-supervised Graph Neural Networks (GNNs) for predicting variable values.
result GNNs can solve MIPs with unlabeled data and improve over other ML approaches.
Graph cuts find global optima for Potts models in slight perturbations.
problem Finding optimal solutions in Potts models with graph cuts.
method α-expansion algorithm for MAP inference, with certification for perturbations.
result All local minima are global minima in slight perturbations, and solutions are close to original.
The goal in network state prediction (NSP) is to classify the global state (label) associated with features embedded in a graph. This graph structure encoding feature relationships is the key distinctive aspect of NSP compared to classical supervised learning. NSP arises in various applications: gene expression samples…
Study how communication and feedback graphs affect learning outcomes.
problem Understanding the impact of feedback graphs on cooperative online learning.
method Analyzed network regret in terms of the independence number of the strong product of communication and feedback graphs.
result Proved bounds for network regret and demonstrated the non-improvable nature of positive results in pathological cases.
Graph neural network learns graph distances effectively.
problem Maintaining graph distance metric properties.
method GRAPH-BERT based semi-supervised distance metric learning.
result GB-DISTANCE outperforms existing methods.
The application of deep learning to symbolic domains remains an active research endeavour. Graph neural networks (GNN), consisting of trained neural modules which can be arranged in different topologies at run time, are sound alternatives to tackle relational problems which lend themselves to graph representations. In …
Zero-shot and few-shot learning aim to improve generalization to unseen concepts, which are promising in many realistic scenarios. Due to the lack of data in unseen domain, relation modeling between seen and unseen domains is vital for knowledge transfer in these tasks. Most existing methods capture seen-unseen relatio…
This paper introduces a new learning-based approach for approximately solving the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph Convolutional Networks to build efficient TSP graph representations and output tours in a non-autoregressive manner via highly parallelized beam search. Our approach ou…
New kernel improves graph learning with fewer labeled data.
problem Limited kernels for node-level problems on graphs.
method Derived from a regularization framework, transductive kernel for graphs with node features.
result Improved learning on fewer training points and non-Euclidean data.
Graph Prototypical Networks improve few-shot node classification on attributed networks.
problem Few-shot node classification in attributed networks with limited labeled instances.
method Graph Prototypical Networks (GPN) using meta-learning to extract meta-knowledge and identify informative labeled instances.
result GPN achieves superior performance in few-shot node classification.
Most graph kernels are an instance of the class of R-Convolution kernels, which measure the similarity of objects by comparing their substructures. Despite their empirical success, most graph kernels use a naive aggregation of the final set of substructures, usually a sum or average, thereby potentially dis…
We propose an algorithmic framework for convex minimization problems of a composite function with two terms: a self-concordant function and a possibly nonsmooth regularization term. Our method is a new proximal Newton algorithm that features a local quadratic convergence rate. As a specific instance of our framework, w…
New neural architectures invariant to sign flips and basis symmetries for graph representation learning.
problem Learning invariant graph representations from eigenvectors.
method SignNet and BasisNet neural architectures that are invariant to sign flips and basis symmetries.
result Proven to be universal, approximating any continuous function of eigenvectors with desired invariances.
Inferring new facts from existing knowledge graphs (KG) with explainable reasoning processes is a significant problem and has received much attention recently. However, few studies have focused on relation types unseen in the original KG, given only one or a few instances for training. To bridge this gap, we propose Co…
GCC pre-trains graph neural networks to transfer across diverse datasets.
problem Non-transferable graph models trained for specific datasets.
method Graph Contrastive Coding (GCC) framework using contrastive learning.
result GCC pre-trained models achieve competitive performance across multiple datasets.
Neural model with parameterized algorithms improves graph CO problem solving.
problem Solving NP-hard graph combinatorial optimization problems efficiently and accurately.
method Combining neural models and parameterized algorithms to identify and handle hard and easy parts of CO instances.
result Framework produces superior solution quality and out-of-distribution generalization.
Graph Neural Networks and Guided Local Search improve TSP solutions.
problem Finding optimal solutions to the Traveling Salesperson Problem quickly.
method Hybrid approach combining Graph Neural Networks and Guided Local Search.
result Significant reduction in optimality gap for TSP solutions.
TGNs learn from dynamic graphs efficiently and outperform previous methods.
problem Learning from graphs that evolve over time.
method Temporal Graph Networks (TGNs) combining memory and graph operators.
result Significantly outperforms previous approaches on dynamic graphs.
Study on sample complexity for pure exploration in feedback graph settings.
problem Sample complexity of pure exploration in online learning with feedback graphs.
method Derive instance-specific lower bounds and present asymptotically optimal algorithm TaS-FG.
result TaS-FG is asymptotically optimal and efficient across different graph configurations.
New method explains classifiers trained on raw hierarchical data.
problem Lack of interpretability in classifiers trained on raw structured data.
method Treating classifiers as subset selection problems, generating interpretable explanations efficiently.
result Computational efficiency and higher-quality explanations compared to existing methods.
TaRP predicts missing relations in KGs using type and instance-level info.
problem Missing relations in KGs.
method Type-augmented relation prediction (TaRP) combining type and instance-level info.
result Significantly better performance on benchmark datasets.
A new network learns to prioritize messages for efficient multi-robot path planning.
problem Efficient path planning and coordination for large-scale multi-robot systems.
method Message-Aware Graph Attention Network (MAGAT) incorporating attention mechanisms.
result MAGAT achieves performance close to a coupled centralized expert algorithm.
Proposes a novel graph signal model using narrowband kernels.
problem Graph signals with multiple concentrated frequency regions.
method Jointly learns graph signal model parameters and coefficients.
result Joint learning improves signal interpolation accuracy.
A new method for aligning datasets without known correspondences.
problem Aligning datasets from different domains without labeled correspondences.
method Integrates MDS and Wasserstein Procrustes for joint optimization of embeddings and correspondences.
result Maps datasets to a common low-dimensional space without labeled correspondences.