Understanding and Improving Graph Injection Attack by Promoting Unnoticeability

1 INTRODUCTION

• Homophily-based defenses can exploit that damage to alleviate or even prevent GIA, limiting its usefulness for evaluating GNN robustness.Homophily is the tendency of nodes to connect with others that have similar features or labels.Source: §1 · pp. 1–2
• Homophily unnoticeability constrains GIA to preserve the original graph’s homophily, and HAO instantiates this constraint by regularizing homophily-distribution shift.This is intended to make attacks harder for homophily defenders to identify while remaining effective.Source: §1 · p. 2
• Across 38 defense models and 6 benchmarks, GIA with HAO breaks homophily defenders and significantly outperforms previous attacks across targeted and non-targeted settings.The paper presents this approach as supporting more reliable evaluation of GNN robustness.Source: §1 · p. 2
• GIA can be provably more harmful than GMA because its greater flexibility enables stronger perturbations.The paper also finds that this flexibility severely damages the original graph’s homophily distribution.Source: §1 · p. 2

2.1 GRAPH NEURAL NETWORKS

• A graph is represented by an adjacency matrix and a node-feature matrix, and GNNs predict test-node labels after training on a labeled subgraph.GNNs update node representations by aggregating information from neighbors.Source: §2.1 · pp. 2–3

2.2 GRAPH ADVERSARIAL ATTACK2

• GMA perturbs the original graph’s structure or features, whereas GIA adds malicious nodes with constrained features, degrees, and connections.GIA’s connection matrix covers edges among injected nodes and between injected and original nodes.Source: §2.2 · p. 3
• The comparison uses an evasion, inductive, black-box setting: attacks occur at test time, test nodes are unseen during training, and the target model is inaccessible.The attack setting follows the Graph Robustness Benchmark.Source: §2.2 · p. 3

3.1 POWER OF GRAPH INJECTION ATTACK

• GIA can cause more damage than GMA with equal or fewer perturbation budgets when there is no defense.The theoretical comparison assumes optimal strategies and a fixed linearized GNN; the result is also verified empirically.Source: §3.1 · p. 4
• Plural Mapping M2 represents each GMA edge addition with an injected node and can then further optimize that node to increase damage.For an added edge between nodes u and v, M2 inserts a node connected to both and adjusts its features to match the prediction effect on u.Source: §3.1 · p. 4

3.2 PITFALLS IN GRAPH INJECTION ATTACK

• GIA damages homophily more than GMA, producing a pronounced out-of-distribution shift in node-centric homophily.The analysis focuses primarily on node-centric homophily, defined using similarity between a node’s features and aggregated neighbor features; edge addition is the focus of later discussion.Source: §3.2 · pp. 4–5
• Homophily defenders can prune edges under a suitable condition, and the paper shows that such defenses can reduce GIA’s harm below GMA’s or leave GIA causing little-to-no damage.For the specified high-homophily case, a mild nonpositive-similarity pruning condition can remove malicious GIA edges while possibly retaining some GMA edges.Source: §3.2 · p. 5

4.1 HARMONIOUS ADVERSARIAL OBJECTIVE

• Homophily unnoticeability requires the perturbed graph’s homophily distribution to stay within an allowed distance of the original distribution.The definition uses a distribution-distance measure m(·) and an upper bound on the allowed shift.Source: §4.1 · p. 6
• A rigid homophily constraint can clip all injected edges, while optimizing only target-node homophily does not guarantee unnoticeability.The proposed realization enforces the constraint softly; the paper argues that satisfying it can be approximated by bypassing homophily defenders.Source: §4.1 · p. 6
• HAO integrates a homophily-based regularizer into the attack objective, aiming to retain homophily while still conducting effective attacks.The regularizer has weight λ; one implementation maximizes homophily for each injected node.Source: §4.1 · p. 6

4.2 ADAPTIVE INJECTION STRATEGIES

• Adaptive injection alternates adjacency and feature optimization because HAO stops optimization when homophily is overly broken, unlike greedy strategies’ assumption about the other variable.The section proposes three adaptive strategies to coordinate injection with HAO.Source: §4.2 · p. 6
• Gradient-driven injection uses a bi-level formulation to optimize adjacency and features separately, with distinct homophily weights for discrete adjacency and continuous features.Adjacency can be optimized with MetaGIA or AGIA.Source: §4.2 · p. 7
• ATDGIA adapts heuristic-based injection with an early stop to avoid destroying homophily, while SeqGIA iteratively selects vulnerable targets to reduce gradient-method overhead on large graphs.The SeqGIA target selection uses the vulnerability score described for the heuristic strategy.Source: §4.2 · p. 7

5.1 SETUP & BASELINES

• Experiments cover 38 defense models on six datasets, including citation, co-purchasing, and other networks, using PGD, TDGIA, and Metattack as baselines.The evaluation also includes popular and robust GNNs, plus Layer Normalization and FLAG; a 3-layer GCN serves as the attack surrogate.Source: §5.1 · pp. 7–8

5.2 EMPIRICAL PERFORMANCE

• Up to 30%, HAO improves non-targeted attack performance across methods and datasets; adaptive injection strategies outperform PGD and TDGIA in most cases.With HAO, even PGD can make robust models comparable to or worse than a simple MLP.Source: Table 1 · p. 8, §5.2 · p. 8
• Up to 15%, HAO improves targeted attack performance across methods and datasets, while adaptive injections with HAO establish a new state-of-the-art.The evaluation covers targeted attacks against different models.Source: Table 2 · p. 8, §5.2 · p. 8

5.3 ANALYSIS AND DISCUSSIONS

• As the HAO regularization weight λ increases, performance against homophily defenders improves at a slight cost to performance against GCN; overall performance gains reach 5%.The reported trade-off does not hurt overall performance.Source: Figure 3 · p. 9, §5.3 · p. 9
• GIA with HAO preserves homophily while still conducting effective attacks, unlike the homophily changes associated with GIA without HAO.Figure 4a compares the homophily changes after attacks with and without HAO.Source: Figure 4 · p. 9, §5.3 · p. 9
• Across varying node and edge budgets, HAO consistently improves overall attack performance while slightly trading away performance against undefended models.Figures 4b and 4c show results against GCN and EGuard.Source: Figure 4 · p. 9, §5.3 · p. 9

• GIA with HAO breaks homophily defenders and substantially outperforms previous works in the reported experiments.The paper frames HAO as a way to constrain homophily damage in GIA.Source: §6 · p. 9

• The authors report no ethical concerns and state that their study involves no human subjects, dataset releases, potentially harmful insights, or listed privacy, security, fairness, legal, or integrity issues.They connect effective robustness evaluation to the development of trustworthy GNNs, including for safety-critical applications.Source: ETHICS STATEMENT · p. 10

A.1 DISCUSSIONS ON HAO AND ITS LIMITATIONS

• Poorly defined graph unnoticeability can reward homophily-destroying shortcuts, making attacks unreliable for evaluating GNN robustness.HAO penalizes these shortcuts and is presented as a way to better expose underlying GNN vulnerabilities.Source: §A.1 · p. 14
• HAO trades attack performance against vanilla GNNs for performance against homophily defenders, with larger λ amplifying the trade-off.The authors call for more tailored optimization methods to improve injection matrices and node features.Source: §A.1 · p. 14
• The discussion focuses mainly on homophilous graphs; direct HAO adaptation may not work for non-attributed graphs.The authors suggest deriving new homophily definitions where predictive information still resembles homophily, and report HAO retains an advantage on disassortative graphs.Source: §A.1 · p. 15
• The paper considers adversarial robustness and homophily but leaves label noise as a separate threat needing attention.Appendix B.3 is described as related to GNN vulnerability to label noise.Source: §A.1 · p. 15

A.2 MORE FUTURE DIRECTIONS

• The authors call for better definitions of unnoticeability beyond graphs and images, and for studying robustness across deeper and more complicated GNNs.They note that methods developed for linearized GNNs may not adapt to models with normalizations or Transformers; the layer-depth and homophily interplay remains unexplored.Source: §A.2 · pp. 15–16
• Future work could test whether downstream tasks such as link prediction and graph clustering depend on homophily and how task objectives shape attack optimization.Source: §A.2 · p. 15
• Proposed future directions include small-budget attacks, combining GMA with GIA, and injecting nodes to strengthen vulnerable nodes' degree, MLP margin, and homophily.Source: §A.2 · pp. 15–16
• Reinforcement-learning GIA was excluded because adapting it to the paper's setting required additional effort, but the authors identify tailored strategies and scalability as future opportunities.Source: §A.2 · p. 16

B.3 MEMORIZATION EFFECTS OF GRAPH NEURAL NETWORKS

• Figure 5 presents GCN training curves on Cora with random labels.Source: Figure 5 · p. 18, §B.3 · p. 18
• With all labels randomized, the GCN's training accuracy can still reach nearly 100%, which the authors cite as evidence of memorization.The experiment uses a two-layer GCN with 16 hidden units, trained for 1,000 epochs on Cora.Source: §B.3 · p. 18

C.1 IMPLEMENTATION OF GRAPH MODIFICATION ATTACK

• For GMA, each step selects the largest entry in the attack-loss gradient and changes the corresponding eligible edge.The implementation excludes feature perturbations under limited budgets, citing prior observations and the paper's mapping argument.Source: §C.1 · p. 19

C.2 IMPLEMENTATION OF GRAPH INJECTION ATTACK WITH PLURAL MAPPING

• The plural-mapping GIA implementation inserts a node for each added GMA edge, then uses PGD to optimize injected-node features.Source: §C.2 · p. 19

D.1 EDGE-CENTRIC HOMOPHILY

• Edge-centric homophily is defined as feature similarity between an edge's endpoints, but the paper favors node-centric homophily because it accounts for neighbor degrees and extends more naturally to higher-order relationships.The reported natural edge-centric homophily distributions follow a Gaussian prior.Source: §D.1 · p. 19

D.2 MORE HOMOPHILY DISTRIBUTIONS CHANGES

• GIA without HAO severely disrupts the original homophily distribution, whereas HAO retains it in the reported TDGIA experiments.The budgets in these appendix experiments differ from those used earlier to maximize harm relative to GMA.Source: §D.2 · p. 19, Figure 7 · p. 20

E.1 PROOF FOR THEOREM 1

• With moderate budgets, a fixed linearized GNN, no isolated nodes, and optimal strategies, some GIA budget no greater than GMA’s can match GMA’s effects.The proof constructs injections that reproduce the target prediction effects of GMA perturbations.Source: §E.1 · pp. 20, 24
• For linearized GNNs, mappings reproduce edge additions, edge deletions, and feature perturbations on the target or its k-hop neighbors; the proof extends by induction across layers.The authors also state that analogous conclusions extend to other neighbor-aggregation GNNs, including GCN and GraphSage.Source: §E.1 · pp. 21, 23, 24
• Post-processing that merges similar injected nodes and re-optimizes them can let GIA use less budget for the same or greater harm than GMA.The proof also notes that mappings may cover feature perturbations without additional budget when GMA combines them with edge addition.Source: §E.1 · p. 24

E.2 GIA WITH PLURAL MAPPING FOR MORE GMA OPERATIONS

• For edge removal and feature perturbation, plural mapping sets injected-node features to match target influence, then optimizes them further to amplify damage.Source: §E.2 · p. 24

E.3 PROOF FOR THEOREM 2

• Under Theorem 2’s assumptions, direct malicious GIA edges are more likely to be pruned than GMA edges by a defender using a similarity threshold based on the minimum original-edge similarity.The proof considers cases where GIA edges fall below the threshold, including cases in which all GIA edges are pruned.Source: §E.3 · p. 25

E.4 PROOF FOR LEMMA 2

• During PGD optimization of injected-node features for attack loss, the cosine similarity between the target and injected node decreases.The derivation assumes binary classification before extending the argument to multiple classes.Source: §E.4 · pp. 25–26

E.5 PROOF FOR THEOREM 3

• When λ > 0, the homophily measure for GIA with HAO is no greater than for GIA without HAO.The passage identifies the compared graphs as those generated with and without HAO, respectively.Source: §E.5 · p. 26

A Multi-Layer Perceptron (MLP) can be taken as a 0-layer GNN which the definition also applies. Then, we specify the certified robustness as follows:

• A homophily defender can neutralize a direct GIA attack on a linearized GNN by pruning malicious edges under the proposition’s similarity condition.The proposition assumes training includes at least one node from each class; its proof concludes that edges meeting the attack condition can be pruned, making the attack ineffective.Source: A Multi-Layer Perceptron (MLP) can be… · pp. 27, 29

F.1 DETAILS OF EFFICIENT GNNGUARD

• Efficient GNNGuard reduces the original O(n^2) node-node similarity computation to O(E) complexity.It adopts a similar message-passing scheme and uses a threshold to prune edges.Source: §F.1 · p. 29

F.2 DETAILS OF ROBUST GRAPH ATTENTION NETWORK (RGAT)

• RGAT removes unlike neighbors based on similarity during attention and adds layer normalization to stabilize hidden representations.The passage reports RGAT as more robust with or without GIA attacks.Source: §F.2 · p. 29

F.3 PERFORMANCE OF HOMOPHILY DEFENDERS

• On Cora, EGNNGuard is competitive with GNNGuard while 20× faster, and RGAT performs slightly better and 10× faster.The evaluation averages accuracy over 10 runs and reports test robustness against all attacks and running time per training epoch.Source: Table 3 · p. 30, §F.3 · p. 30

G.1.1 INDUCTION OF META GRADIENTS FOR METAGIA

• MetaGIA derives meta-gradients for its attack adjacency and approximates them using MAML-style methods for efficiency.The passage refers to Metattack for the detailed algorithms, with corresponding variables substituted.Source: §G.1.1 · p. 30

G.2 DETAILS OF AGIA

• AGIA sets the adjacency homophily penalty λA to zero, adds sparsity regularization, and uses Adam because it empirically performs better than PGD.The authors hypothesize that λA can degrade performance because the adjacency variable is discrete; Adam’s momentum and history are described as helping escape local optima.Source: §G.2 · p. 31

G.3 DETAILS OF SEQGIA

• SeqGIA uses divide-and-conquer to iteratively select vulnerable targets, unlike sequential injection methods that connect targets in a full batch.This strategy is proposed to reduce the computation overhead of gradient methods.Source: §G.3 · p. 31

H.1 STATISTICS AND BUDGETS OF DATASETS

• Dataset statistics report label homophily and node-centric average homophily; attack budgets are heuristically set using target-node counts and average degrees.The statistics and budget tables are identified as Tables 4–6.Source: §H.1 · p. 32, Table 4 · p. 33, Table 5 · p. 33
• Targeted attacks use 800 targets selected by surrogate-model classification margins and random sampling, with injected-node and degree budgets scaled down accordingly.Targets include 200 nodes with highest margins, 200 with lowest margins, and 400 sampled randomly.Source: §H.1 · p. 32

H.3 COMPLEXITY OF ALGORITHMS

• The attack-complexity analysis uses quantities including inner and outer optimization epochs, injected-node degree bounds, feature dimensions, and victim-neighborhood sizes.The supplied passage defines these quantities for the algorithms analyzed in the appendix.Source: §H.3 · p. 33, Table 7 · p. 34

H.4 DETAILS OF DEFENSE BASELINES

• Defense baselines are grouped as Vanilla, Robust, or Extreme Robust (Combo), with layer normalization treated as a robustness-enhancing trick.The appendix uses LN for normalization before the first convolution and LNi for normalization between convolution layers.Source: §H.4 · pp. 33–34, Table 8 · p. 34

H.5.1 MODEL SETTING

• Default GNNs have three layers, use dataset-dependent hidden dimensions, dropout 0.5, Adam at learning rate 0.01, and early stopping within 400 epochs.Homophily-defender thresholds default to 0.1, with specified dataset-specific exceptions.Source: §H.5.1 · p. 34

H.5.2 EVALUATION SETTING

• Evaluation is black-box: a surrogate generates the perturbed graph, then clean-trained target models are tested on it, with repeated runs and mean target-node accuracy reported.The number of runs is 10 for Cora, Citeseer, Computers, and Arxiv, and 5 for Aminer and Reddit; variance is omitted.Source: §H.5.2 · pp. 34–35

H.5.3 ATTACKS SETTING

• Attack settings specify PGD feature optimization, heuristic feature updates for TDGIA variants, batched MetaGIA updates, and tuned HAO parameters.For HAO, λ is searched from 0.5 to 8 in steps of 0.5; other supplied passages describe attack-specific optimization choices.Source: §H.5.3 · p. 35

I.1 FULL RESULTS OF AVERAGED ATTACK PERFORMANCE

• The appendix provides full averaged attack-performance results across defense models as a supplement to Table 3b.The supplied table caption identifies Table 9 as the full averaged performance across all defense models.Source: §I.1 · p. 36, Table 9 · p. 36

I.2 MORE RESULTS ON DISASSORTATIVE GRAPHS

• The study selects Chameleon and Squirrel for an initial investigation of non-targeted GIA performance on disassortative graphs.Dataset statistics and attack budgets are provided in Tables 10 and 11.Source: §I.2 · p. 36, Table 10 · p. 36, Table 11 · p. 36
• The disassortative-graph evaluation largely follows the earlier attack and evaluation setup, but uses a 0.05 homophily-defender threshold for Chameleon.Some robust tricks did not consistently improve GNN performance on these graphs, so selected defense results were excluded for fair comparison.Source: §I.2 · p. 36
• On Chameleon, HAO improves attack performance by up to 25% against homophily defenders, 12% against robust models, and 10% against extreme-robust models, with up to 3% averaged test-robustness gain.The authors report smaller but non-trivial improvements on Squirrel, including up to 4% test-robustness gain against homophily defenders.Source: §I.2 · pp. 36–37, Table 12 · p. 37

J.1 DETAILED RESULTS OF NON-TARGETED ATTACKS

• The appendix presents detailed non-targeted attack results for the top 20 robust models ranked by averaged test accuracy against all attacks.Table 12 reports categorized defense results and averaged attack performance.Source: §J.1 · p. 37, Table 12 · p. 37

J.2 DETAILED RESULTS OF TARGETED ATTACKS

• The section introduction says targeted-attack results are reported for the methods and datasets used in Table 2, showing only the top 20 robust models by averaged test accuracy against all attacks.Source: §J.2 · p. 37
• The supplied captions identify detailed targeted-attack results for Computers, Arxiv, Aminer, and Reddit.The results are divided across multiple tables for each named dataset.Source: Table 21 · p. 40, Table 22 · p. 40, Table 23 · p. 41
• The supplied table captions also identify detailed targeted-attack results for Reddit across two table parts.Source: Table 27 · p. 42, Table 28 · p. 42