Remark Since we apply the row-wise softmax in Eq. (7), P jpij = 1 i and pij 0 (i,j) is alwaysfulfilled.If C(P)=0,allbutoneentryinacolumn pi, are0andtheotherentryis1. Hence,P ipij = 1 j isfulfilled. Synthetic random graph generation To generate train and test graph datasets we utilized the pythonpackage NetworkX[1]. Ego graphs extracted from Binominal graphs (p (0.2,0.6))selecting all neighbours of onerandomnode. Training Details We did not perform an extensive hyperparameter evaluation for the different experiments and mostly followed [2]for hyperparameter selection. We set the graph embedding dimension to 64.

Computing such neural set divergence require aligning nodes and edges of the two graphs.

We consider the graph similarity computation (GSC) task based on graph edit distance (GED) estimation. State-of-the-art methods treat GSC as a learningbased prediction task using Graph Neural Networks (GNNs). To capture finegrained interactions between pair-wise graphs, these methods mostly contain a node-level matching module in the end-to-end learning pipeline, which causes highcomputational costsinboththetraining andinference stages.

Augmentations Graph Edit Operators Node DroppingNode Deletion Edge PerturbationEdge Deletion, Edge Addition Categorical Attribute MaskingFeature Masking Operator Sub-graph SamplingNode Deletions Forexample, consideragraphg A( |g), generated vianodedropping.

Graph Edit Distance (GED) measures the (dis-)similarity between two given graphs in terms of the minimum-cost edit sequence, which transforms one graph to the other.GED is related to other notions of graph similarity, such as graph and subgraph isomorphism, maximum common subgraph, etc. However, the computation of exact GED is NP-Hard, which has recently motivated the design of neural models for GED estimation.However, they do not explicitly account for edit operations with different costs. In response, we propose $\texttt{GraphEdX}$, a neural GED estimator that can work with general costs specified for the four edit operations, viz., edge deletion, edge addition, node deletion, and node addition.We first present GED as a quadratic assignment problem (QAP) that incorporates these four costs.Then, we represent each graph as a set of node and edge embeddings and use them to design a family of neural set divergence surrogates. We replace the QAP terms corresponding to each operation with their surrogates. Computing such neural set divergence requires aligning nodes and edges of the two graphs.We learn these alignments using a Gumbel-Sinkhorn permutation generator, additionally ensuring that the node and edge alignments are consistent with each other. Moreover, these alignments are cognizant of both the presence and absence of edges between node pairs.Through extensive experiments on several datasets, along with a variety of edit cost settings, we show that $\texttt{GraphEdX}$ consistently outperforms state-of-the-art methods and heuristics in terms of prediction error.

Abstract--Graph Similarity Computation (GSC) is a fundamental graph-related task where Graph Edit Distance (GED) serves as a prevalent metric. GED is determined by an optimal alignment between a pair of graphs that partitions each into aligned (zero-cost) and unaligned (cost-incurring) substructures. However, the solution for optimal alignment is intractable, motivating Graph Neural Network (GNN)-based GED approximations. Existing GNN-based GED approaches typically learn node embeddings for each graph and then aggregate pairwise node similarities to estimate the final similarity. Despite their effectiveness, we identify a fundamental mismatch between this prevalent node-centric matching paradigm and the core principles of GED. This discrepancy leads to two critical limitations: (1) a failure to capture the global structural correspondence for optimal alignment, and (2) a misattribution of edit costs by learning from spurious node-level signals. T o address these limitations, we propose GCGSim, a GED-consistent graph similarity learning framework that reformulates the GSC task from the perspective of graph-level matching and substructure-level edit costs. Specifically, we make three core technical contributions. First, we design a Graph-Node Cross Matching (GNCM) mechanism to learn pair-aware contextual-ized graph representations. Second, we introduce a principled Prior Similarity-Guided Disentanglement (PSGD) mechanism, justified by variational inference, to unsupervisedly separate graph representations into their aligned and unaligned substructures. Finally, we employ an Intra-Instance Replicate (IIR) consistency regularization to learn a canonical representation for the aligned substructures.

Machine unlearning seeks to efficiently remove the influence of selected data while preserving generalization. Significant progress has been made in low dimensions $(p \ll n)$, but high dimensions pose serious theoretical challenges as standard optimization assumptions of $Ω(1)$ strong convexity and $O(1)$ smoothness of the per-example loss $f$ rarely hold simultaneously in proportional regimes $(p\sim n)$. In this work, we introduce $\varepsilon$-Gaussian certifiability, a canonical and robust notion well-suited to high-dimensional regimes, that optimally captures a broad class of noise adding mechanisms. Then we theoretically analyze the performance of a widely used unlearning algorithm based on one step of the Newton method in the high-dimensional setting described above. Our analysis shows that a single Newton step, followed by a well-calibrated Gaussian noise, is sufficient to achieve both privacy and accuracy in this setting. This result stands in sharp contrast to the only prior work that analyzes machine unlearning in high dimensions \citet{zou2025certified}, which relaxes some of the standard optimization assumptions for high-dimensional applicability, but operates under the notion of $\varepsilon$-certifiability. That work concludes %that a single Newton step is insufficient even for removing a single data point, and that at least two steps are required to ensure both privacy and accuracy. Our result leads us to conclude that the discrepancy in the number of steps arises because of the sub optimality of the notion of $\varepsilon$-certifiability and its incompatibility with noise adding mechanisms, which $\varepsilon$-Gaussian certifiability is able to overcome optimally.

We consider the graph similarity computation (GSC) task based on graph edit distance (GED) estimation. State-of-the-art methods treat GSC as a learning-based prediction task using Graph Neural Networks (GNNs).