Recent works show that Graph Neural Networks (GNNs) are highly non-robust with respect to adversarial attacks on both the graph structure and the node attributes, making their outcomes unreliable. We propose the first method for certifiable (non-)robustness of graph convolutional networks with respect to perturbations …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “node robustness”
Adding node feature kernels improves GCN robustness to graph perturbations.
problem GCNs' robustness to graph perturbations is a concern.
method Introduced random GCN and added node feature kernels to message passing.
result Perturbations of the graph structure can significantly degrade GCN performance.
Distributed Robust Learningstat.ML
We propose a framework for distributed robust statistical learning on {\em big contaminated data}. The Distributed Robust Learning (DRL) framework can reduce the computational time of traditional robust learning methods by several orders of magnitude. We analyze the robustness property of DRL, showing that DRL not only…
DA-GNN improves robustness of GNNs by modeling noise dependencies.
problem Real-world graph node features often contain noise, leading to performance degradation in GNNs.
method DA-GNN captures noise dependencies using variational inference and new benchmark datasets.
result DA-GNN consistently outperforms existing baselines across various noise scenarios.
Paper tackles robust Euclidean distance estimation with sparse outliers.
problem Estimating point positions from corrupted distance measurements.
method Proposes a novel algorithm using Nyström method and robust PCA.
result Achieves accurate recovery with minimal anchors and sparse outliers.
To improve the resilience of distributed training to worst-case, or Byzantine node failures, several recent approaches have replaced gradient averaging with robust aggregation methods. Such techniques can have high computational costs, often quadratic in the number of compute nodes, and only have limited robustness gua…
Graph attacks can be successful with just a few bad nodes.
problem Adversarial attacks on graph neural networks.
method Identifying and exploiting anchor nodes to compromise graph models.
result A few bad nodes can significantly degrade graph model performance.
Indirect attacks can fool graph classifiers even with poisoned neighbors.
problem How to evaluate and defend graph convolutional neural networks against indirect adversarial attacks.
method Proposed a method to generate adversarial perturbations on a single node far from the target.
result 99% attack success rate within two-hops from the target in two datasets.
An important problem in networked systems is detection and removal of suspected malicious nodes. A crucial consideration in such settings is the uncertainty endemic in detection, coupled with considerations of network connectivity, which impose indirect costs from mistakely removing benign nodes as well as failing to r…
This work evaluates graph models' robustness to structural distributional shifts.
problem Evaluating graph models' robustness to structural distributional shifts.
method Proposes a general approach for inducing diverse distributional shifts based on graph structure.
result Simple models often outperform more sophisticated methods on structural distributional shifts.
Proposes a method to model uncertainty in neural ordinary differential equations.
problem Lack of uncertainty modeling and robustness in neural ordinary differential equations.
method Introduces a novel approach to model uncertainty by considering a distribution over the end-time of the ODE solver.
result Demonstrates the effectiveness of the proposed approaches in modelling uncertainty and robustness through experiments.
Theoretical study shows adversarial training improves robustness in deep learning models.
problem Ensuring robustness in pre-trained deep learning models.
method Theoretical analysis of adversarial training and feature purification in two-layer neural networks.
result Adversarial training leads to feature purification, making models more robust to attacks.
I-GCN improves GCNs' robustness against adversarial attacks.
problem Adversarial attacks degrade GCNs' performance in security-critical applications.
method Influence mechanism divides node effects into introverted and extroverted influences.
result I-GCN achieves higher accuracy rates than state-of-the-art methods in defending against adversarial attacks.
Noise Injection Node Regularization improves robustness in neural networks.
problem Improving robustness of neural networks against various perturbations.
method Injecting structured noise into neural networks during training.
result Significant improvement in robustness against data perturbations.
Graph representation learning, aiming to learn low-dimensional representations which capture the geometric dependencies between nodes in the original graph, has gained increasing popularity in a variety of graph analysis tasks, including node classification and link prediction. Existing representation learning methods …
Hierarchical randomized smoothing improves model robustness for complex data.
problem Certifying robustness on complex data (e.g. images, graphs) is challenging.
method Add random noise to a randomly selected subset of entities in a hierarchical manner.
result Hierarchical randomized smoothing yields stronger robustness guarantees with high accuracy.
Learning distributed node representations in networks has been attracting increasing attention recently due to its effectiveness in a variety of applications. Existing approaches usually study networks with a single type of proximity between nodes, which defines a single view of a network. However, in reality there usu…
Despite the exploding interest in graph neural networks there has been little effort to verify and improve their robustness. This is even more alarming given recent findings showing that they are extremely vulnerable to adversarial attacks on both the graph structure and the node attributes. We propose the first method…
AdvImmune improves certifiable robustness of GNNs against adversarial attacks.
problem Vulnerability of graph neural networks to adversarial attacks.
method Proposes AdvImmune, an algorithm that optimizes with meta-gradient to improve certifiable robustness.
result Remarkably improves the ratio of robust nodes by 12%, 42%, 65% with an affordable immune budget of only 5% edges.
Heterophily affects GNN robustness; separating ego- and neighbor-embeddings improves defense.
problem The robustness of GNNs to adversarial attacks.
method Formalized relation between heterophily and GNN robustness; empirical analysis; design principles for improved robustness.
result Separating ego- and neighbor-embeddings increases GNN robustness.
GraphReach improves GNN performance by incorporating node positions.
problem Existing GNNs fail to capture node positions, leading to inaccurate predictions.
method GraphReach uses reachability estimations from anchor nodes to capture global node positions.
result GraphReach achieves up to 40% relative improvement in accuracy compared to state-of-the-art GNNs.
Impact of shocks to economies on the efficiency and robustness of the international pesticide trade networksphysics.soc-ph
This study assesses how economic shocks affect the efficiency and robustness of international pesticide trade networks.
problem Economic shocks impact the efficiency and robustness of international pesticide trade networks.
method Simulations were used to quantify efficiency and robustness under different economic shocks. Three strategies were tested: descending, random, and ascending node removal.
result The international pesticide trade networks became more efficient and robust except for clustering coefficient. Import-oriented economies were more vulnerable to shocks.
RoCP-GNN improves GNNs' robustness in graph node classification.
problem Uncertainty in GNN predictions for graph data.
method Integrates conformal prediction into GNN training for robust prediction sets.
result GNN models with size loss improve performance in node classification.
A new method for efficient structural node embeddings using Von Neumann entropy.
problem Efficiently identifying structurally equivalent nodes in complex networks.
method VNEstruct: a simple approach generating low-dimensional structural node embeddings using Von Neumann entropy.
result VNEstruct achieves robustness on structural role identification and state-of-the-art performance on graph classification tasks.
New aggregation method improves GNN robustness to structural perturbations.
problem Graph Neural Networks (GNNs) are vulnerable to adversarial attacks that manipulate graph structure.
method Proposes a robust aggregation function with a breakdown point of 0.5, inspired by robust statistics.
result Improves GNN robustness by a factor of 3 on Cora ML and 5.5 on Citeseer, and 8 for low-degree nodes.
New algorithm detects communities even with corrupted data, reaching Kesten-Stigum threshold.
problem Robust community detection in stochastic block model with node corruptions.
method Polynomial-time algorithm using Grothendieck norm of principal submatrices.
result First algorithm to achieve weak recovery at Kesten-Stigum threshold with node corruptions.
node2coords learns interpretable graph node representations robust to graph perturbations.
problem Need representations that capture graph structure and are robust to perturbations.
method Proposes a graph representation learning algorithm using Wasserstein barycenters.
result Learned representations are interpretable and stable to graph perturbations.
We propose a novel approach for learning node representations in directed graphs, which maintains separate views or embedding spaces for the two distinct node roles induced by the directionality of the edges. We argue that the previous approaches either fail to encode the edge directionality or their encodings cannot b…
New algorithm estimates eigenspace with faulty nodes, matching performance of existing methods.
problem Estimating eigenspace in distributed systems with node failures.
method Develops an eigenspace estimation algorithm for distributed environments with arbitrary node failures.
result Matches performance of existing non-robust estimator up to an additive error.
Graph attention improves node classification by distinguishing important edges.
problem Node classification in graph-based learning models.
method Theoretical analysis of graph attention networks for node classification.
result Graph attention can perfectly classify nodes in an 'easy' regime but fails in a 'hard' regime.
New spectral algorithm estimates random graph parameters robustly against corrupted nodes.
problem Estimating the parameter of an Erdős-Rényi random graph with adversarial corruption.
method Spectral algorithm designed for computational efficiency, with an inefficient but information-theoretic alternative.
result Achieves optimal error rate up to logarithmic factors, matching statistical lower bounds.
Proposes DeGLIF to denoise graph data for label noise robustness.
problem Label noise in graph data makes node classification challenging.
method Uses leave-one-out influence function to denoise graph data.
result DeGLIF improves accuracy in node classification on noisy datasets.
GNNs robustness in community detection is studied with various perturbations.
problem Understanding GNNs robustness in community detection tasks.
method Systematic computational evaluation of six GNN architectures on synthetic and real-world networks.
result Supervised GNNs achieve higher baseline accuracy, while DMoN shows stronger resilience to perturbations.
Paper tackles robust estimation of tree-structured Ising models without side information.
problem Learning tree-structured Ising models with flipped signs of variables.
method Proves unidentifiability, proposes an algorithm with logarithmic sample complexity and polynomial run-time complexity.
result Empirically demonstrates robustness of proposed algorithm in the flipped signs setting.
Network embedding has proved extremely useful in a variety of network analysis tasks such as node classification, link prediction, and network visualization. Almost all the existing network embedding methods learn to map the node IDs to their corresponding node embeddings. This design principle, however, hinders the ex…
New algorithm detects communities near KS threshold with optimal rate, even in noisy conditions.
problem Community detection in symmetric stochastic block models with noisy data.
method Polynomial-time algorithm using Sum-of-Squares framework and robust majority voting.
result Achieves minimax-optimal misclassification rate near Kesten-Stigum threshold, even with node corruption.
Develops structured noise for more accurate graph classifier robustness certificates.
problem Isotropic noise limits robustness certificates for graph classifiers.
method Randomized smoothing with anisotropic noise distribution.
result Structured-aware robustness certificates provide more accurate predictions.
Graph Information Bottleneck (GIB) optimizes graph representations for robustness against adversarial attacks.
problem Challenges in learning graph representations due to structure and feature information.
method GIB is an information-theoretic principle that balances expressiveness and robustness by maximizing mutual information between representation and target, while constraining mutual information with input data.
result GIB-based models are more robust to adversarial attacks, achieving up to 31% improvement.
Graph Random Neural Network improves semi-supervised learning on graphs.
problem Over-smoothing, non-robustness, and weak-generalization in GNNs with few labeled nodes.
method Random propagation strategy and consistency regularization.
result Significantly outperforms state-of-the-art GNN baselines on semi-supervised node classification.
Distributed model training is vulnerable to byzantine system failures and adversarial compute nodes, i.e., nodes that use malicious updates to corrupt the global model stored at a parameter server (PS). To guarantee some form of robustness, recent work suggests using variants of the geometric median as an aggregation r…
We present network embedding algorithms that capture information about a node from the local distribution over node attributes around it, as observed over random walks following an approach similar to Skip-gram. Observations from neighborhoods of different sizes are either pooled (AE) or encoded distinctly in a multi-s…
New algorithm improves hypergraph clustering for unbalanced communities.
problem Hypergraph clustering with unbalanced community sizes and outliers.
method CRTMLE algorithm using convex relaxation of truncated MLE.
result Achieves optimal recovery guarantees for unbalanced community sizes.
Efficiently matches subgraphs in noisy data without node labels.
problem Subgraph isomorphism in noisy, real-valued graphs.
method Two-step approach: extract topology, then expand matches.
result Realistically sub-linear computational efficiency, robustness to noise.
Paper provides robustness bounds for GNNs against adversarial attacks.
problem Adversarial robustness of GNNs for graph-related tasks.
method PAC-Bayesian framework applied to GCN and MP-GNN.
result Spectral norms of diffusion matrix and weights govern robustness.
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.
In network embedding, random walks play a fundamental role in preserving network structures. However, random walk based embedding methods have two limitations. First, random walk methods are fragile when the sampling frequency or the number of node sequences changes. Second, in disequilibrium networks such as highly bi…
AsylADMM improves gossip-based learning for non-smooth objectives.
problem Efficient and robust decentralized learning on edge devices.
method Asynchronous gossip algorithm for non-smooth optimization.
result AsylADMM converges faster on non-smooth problems.
Proposes MGMN for end-to-end graph similarity learning.
problem Lack of cross-level interactions in graph similarity learning.
method Multi-level graph matching network (MGMN) combining node-graph matching and siamese graph neural networks.
result MGMN outperforms state-of-the-art models on graph-graph classification and regression tasks.