A game-theoretic approach for unsupervised domain adaptation.
problem Assigning labels to unlabeled instances in a target domain using labeled instances from a source domain.
method Graph transduction games (GTG) for iterative algorithm.
result Guaranteed termination to a Nash equilibrium, corresponding to consistent labeling.
New bounds improve graph node classification using optimal transport.
problem Improving transductive generalization bounds for graph node classification.
method Representation-based generalization bounds via optimal transport, expressed in terms of Wasserstein distances.
result Strong correlation between derived bounds and empirical generalization in graph node classification.
New methods learn from single graphs, improving transductive node classification.
problem Statistical foundations of transductive learning for single graphs.
method Developed new concentration-of-measure tools for large graphs.
result Achieved optimal nonparametric rate of N−1/2 for single graph learning. GEN tackles few-shot out-of-graph link prediction in evolving multi-relational graphs.
problem Predicting links between unseen nodes in evolving multi-relational graphs with few edges per node.
method Transductive meta-learning framework (GEN) for inductive and transductive inference.
result GEN significantly outperforms relevant baselines for out-of-graph link prediction tasks.
We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher…
We develop a worst-case analysis of aggregation of classifier ensembles for binary classification. The task of predicting to minimize error is formulated as a game played over a given set of unlabeled data (a transductive setting), where prior label information is encoded as constraints on the game. The minimax solutio…
The study finds conditions for compressing the hidden dimension of Graph Transformers for transductive learning.
problem The challenge of efficiently analyzing and training Graph Transformers for transductive learning.
method Theoretical bounds on hidden dimension compression for Graph Transformers, considering both sparse and dense variants.
result Theoretical findings on how and under what conditions the hidden dimension of Graph Transformers can be compressed.
New method uses graph-based interpolation for few-shot classification.
problem Learning models with limited labeled examples.
method Graph-based feature vector interpolation for transductive learning.
result Significant gains in few-shot classification compared to other methods.
Graph neural networks generalize well under certain conditions, explained by learning theory.
problem Understanding why graph neural networks generalize well in transductive inference.
method Analysis of transductive Rademacher complexity to explain generalization properties of graph convolutional networks.
result Transductive Rademacher complexity can explain the generalization of graph convolutional networks for node classification in stochastic block models.
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.
NPGNN improves graph link prediction by adapting to new graphs.
problem Inductive link prediction in graphs with limited training data.
method Meta-learning with graph neural networks (NPGNN).
result NPGNN outperforms state-of-the-art models in real-world graphs.
The paper establishes bounds for transductive learning using information theory.
problem Transductive learning generalization gap control.
method Information theory, PAC-Bayes, mutual information, conditional mutual information, different information measures.
result Established transductive information-theoretic and PAC-Bayesian bounds.
In this paper we provide a principled approach to solve a transductive classification problem involving a similar graph (edges tend to connect nodes with same labels) and a dissimilar graph (edges tend to connect nodes with opposing labels). Most of the existing methods, e.g., Information Regularization (IR), Weighted …
PAC learning simplified as bipartite matching.
problem Efficiently solving PAC learning problems.
method Transductive learning and one-inclusion graphs.
result PAC learning can be reduced to bipartite matching.
Node Masking improves GNNs' scalability and generalization.
problem Improving GNNs' ability to handle arbitrary graphs.
method Introducing Node Masking to enhance GNNs' performance.
result Node Masking enables GNNs to generalize and scale better.
Proposes a novel graph representation learning framework using contrastive methods.
problem Graph representation learning for graph-structured data.
method Leverages a contrastive objective at the node level, generating two graph views by corruption and learning node representations by maximizing agreement.
result Consistently outperforms existing state-of-the-art methods on transductive and inductive learning tasks.
GCL-LRR improves node classification in noisy graphs.
problem Noise in real-world graph data impairs GNNs' effectiveness.
method Two-stage transductive learning with low-rank regularization and attention.
result Improved node classification performance in noisy graphs.
IDS algorithm optimizes sequential decisions in various monitoring settings.
problem Optimizing sequential decisions in complex monitoring scenarios.
method Information-directed sampling (IDS) algorithm for linear partial monitoring.
result IDS achieves nearly worst-case rate optimality in finite-action games.
Training-free GNNs use labels as features to improve node classification.
problem Improving graph neural networks for transductive node classification.
method Advocates labels as features, designs training-free GNNs based on this.
result Training-free GNNs outperform traditional GNNs in node classification.
CADE learns dual node representations for better generalization.
problem Transductive graph embeddings cannot generalize to unseen nodes or across different graphs.
method CADE combines real-time neighborhoods with neighbor-attentioned representation, preserving known node memory.
result CADE outperforms state-of-the-art methods in generalization and context-awareness.
DEAL model predicts links for new nodes with only attribute info.
problem Predicting links for new nodes with only attribute info.
method DEAL model with two encoders and alignment mechanism.
result DEAL significantly outperforms existing methods on inductive link prediction.
We present graph attention networks (GATs), novel neural network architectures that operate on graph-structured data, leveraging masked self-attentional layers to address the shortcomings of prior methods based on graph convolutions or their approximations. By stacking layers in which nodes are able to attend over thei…
Boosting theory explains why multi-scale GNNs work.
problem Over-smoothing in graph neural networks.
method Gradient boosting and transductive learning analysis.
result Test error bound decreases with more node aggregations.
Unified theory linking node embeddings and graph representations.
problem Clarifying the relationship between node embeddings and graph representations.
method Using invariant theory, the paper establishes a theoretical framework bridging node embeddings and structural graph representations.
result Proves equivalence between node embeddings and structural graph representations, showing they are interchangeable for various tasks.
A new graph neural network tackles oversmoothing and generalization issues.
problem Oversmoothing and poor generalization for unseen graphs in graph neural networks.
method Graph Entities with Step Mixture via random walk (GESM) that considers both edge-based and node-based features.
result GESM achieves state-of-the-art or comparable performances on benchmark datasets.
DGM learns graph structure for better graph neural network performance.
problem Graphs are often unknown or noisy, limiting graph neural network performance.
method DGM learns graph structure from data, improving performance in transductive and inductive settings.
result DGM achieves state-of-the-art results across various domains.
Proposes a neural framework to select subsets efficiently across different models.
problem Lack of generalizability in subset selection methods for unseen architectures.
method Introduces a trainable subset selection framework, SubSelNet, that uses attention-based neural gadgets and subset samplers.
result SubSelNet generalizes across architectures and outperforms existing methods.
A new method for few-shot learning using Laplacian regularization.
problem Few-shot learning with limited labeled data.
method Transductive Laplacian-regularized inference for feature embeddings.
result Our method outperforms state-of-the-art methods across various benchmarks.
In this paper we consider the problem of graph-based transductive classification, and we are particularly interested in the directed graph scenario which is a natural form for many real world applications. Different from existing research efforts that either only deal with undirected graphs or circumvent directionality…
Study shows transductive learning is equivalent to PAC learning for most natural loss functions.
problem Understanding the relationship between transductive and PAC learning models.
method Extending existing results and developing new techniques to analyze the equivalence of the two models.
result Transductive learning is essentially equivalent to PAC learning for realizable learning with most natural loss functions.
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…
GraIL predicts relations by reasoning over subgraphs, outperforming embeddings.
problem Relation prediction in knowledge graphs using latent representations is limited.
method Graph neural network with inductive bias to learn entity-independent relational semantics.
result GraIL outperforms existing rule-induction baselines in the inductive setting.
Geom-GCN improves graph neural networks by preserving structural information and capturing long-range dependencies.
problem Weaknesses in MPNNs' aggregators: loss of structural information and lack of long-range dependencies.
method Proposes a geometric aggregation scheme with three modules: node embedding, structural neighborhood, and bi-level aggregation.
result Achieved state-of-the-art performance on various graph datasets.
BayReL learns molecular interactions across multi-omics data.
problem Inferring meaningful interactions across diverse molecular data types.
method BayReL uses Bayesian representation learning with graph models to integrate multi-omics data.
result BayReL outperforms existing methods in inferring molecular interactions.
Mutual teaching improves graph models with less labeled data.
problem Training graph models with limited labeled data.
method Dual model training with mutual teaching strategy.
result Significant performance improvement with less labeled data.
IGMC learns inductive matrix completion without side info.
problem Inductive matrix completion without side information.
method Graph Neural Network (GNN) trained on 1-hop subgraphs of the rating matrix.
result Achieves competitive performance with state-of-the-art transductive baselines.
The paper extends game theory using Hodge theory on graphs.
problem Generalizing Shapley's value allocation formula for cooperative games on graphs.
method Connecting stochastic path integrals to Hodge-theoretic Poisson's equations on graphs.
result The value allocation operator is the solution to Poisson's equation in combinatorial Hodge theory.
Local regularization fails in transductive learning for some multiclass problems.
problem Whether local regularization can learn all transductive multiclass problems.
method Provided a negative answer by exhibiting a specific multiclass problem.
result Local regularization cannot learn all transductive multiclass problems.
A novel approach for semi-supervised learning using regularized optimal transport.
problem Improving model performance with unlabeled data.
method Regularized optimal transport between empirical measures for affinity matrix construction, incremental label propagation, and certainty score.
result Surpasses state-of-the-art results on 12 benchmark datasets.
Proposes a framework for deep learning on hypergraphs.
problem Lack of effective, unified framework for hypergraph learning.
method Jointly uses vertex and hyperedge embeddings for transductive and inductive learning.
result Achieves state-of-the-art performance on benchmark datasets.
The study analyzes and benchmarks graph conformal prediction methods.
problem Uncertainty quantification in graph node classification.
method Analysis and scaling of existing graph conformal prediction methods.
result Justified recommendations for future graph conformal prediction research.
DNA improves graph neural networks by selectively aggregating node embeddings.
problem Static neighborhood aggregation limits graph neural networks' performance.
method Dynamic neighborhood aggregation guided by attention and controlled channel connections.
result DNA outperforms current methods in transductive node classification.
We present Deep Graph Infomax (DGI), a general approach for learning node representations within graph-structured data in an unsupervised manner. DGI relies on maximizing mutual information between patch representations and corresponding high-level summaries of graphs---both derived using established graph convolutiona…
Paper uses GNN and conformal prediction for accurate edge weight prediction.
problem Predicting edge weights on graphs for various applications.
method Graph Neural Network (GNN) with conformal prediction and error reweighting.
result Our method provides better coverage and efficiency than baselines.
UGformer uses transformers to learn graph representations.
problem Graph representation learning for various tasks.
method UGformer is a transformer-based GNN model that samples or considers all neighbors for each node.
result UGformer achieves state-of-the-art accuracy on graph classification and text classification tasks.
Improved mistake bounds for transductive online learning.
problem Quantifying the power of unlabeled data in online learning.
method Proving lower and upper bounds on transductive mistake bounds.
result Exponential improvement in mistake bounds for transductive learning.
New method TLC improves transductive learning bounds.
problem Sharp generalization bounds for transductive learning.
method Transductive Local Complexity (TLC) framework.
result Nearly sharp bounds consistent with inductive results.
Transductive learning considers situations when a learner observes m labelled training points and u unlabelled test points with the final goal of giving correct answers for the test points. This paper introduces a new complexity measure for transductive learning called Permutational Rademacher Complexity (PRC) and …