1. GPT-GNN: Generative Pre-Training of Graph Neural Networks
Main Idea
The paper considers the generative pretrained model (GPT) and combine it with Graph Neural Network (GNN) to introduce a self-supervised attributed graph generation task which is called GPT_GNN. The authors factorize the likelihood of attribute generation and edge generation.
Key insight
- Leverage GPT to graphs.
Experiments
- Datasets:
- Open Academic Graph
- Amazon Review Recommendation Dataset
- Baselines:
- GAE
- GraphSAGE
- Graph Infomax
2. Graph Unlearning
Main Idea
The paper follows the idea from Machine Unlearning to separate a large graph into several small subgraphs and use several local GNN to train and finally use a learning based aggregation to make the final decision.
Key insight
- Balanced Label Propagation Algorithm:
![BLPA]()
- Balanced Embedding Clustering Method
- Learning-based Aggregation
Evaluation
Matrics:
- Unlearning Efficiency: Randomly make 100 unlearning request and calculate the average time.
- Model Utility: Micro F1 to measure the performance. Experiments:
- Evaluation of Unlearning Efficiency
- Evaluation of Model Utility
- Effectiveness of LBAggr
- Comparing with other baselines
3. ADBench: Anomaly Detection Benchmark
Main Idea
The paper builds a comprehensive benchmark for tabular anomaly detection which covers three levels of supervision (Unsup, sup, Semi-sup) and considers 57 datasets and 30 algorithms.
Key Insight
- No benchmarked unsupervised algorithm is better than others: Specific algorithms should be selected for specific datasets.
- 1% labeled anomalies leads to a better performance for semi-supervised methods compared to the best unsupervised method.
- By preprocessing the data with carefully controlling, the best unsupervised methods https://www.ndss-symposium.org/ndss-paper/doitrust-dissecting-on-chain-compromised-internet-domains-via-graph-learning/for specific types of anomalies are better than semi- and fully-supervised methods: understanding the data characteristics is important.
- Semi-supervised methods show potential to be robust on noisy and corrupted data.
4. DoItrust: Dissecting On-chain Compromised Internet Domains via Graph Learning
Main Idea
The paper combines MLP for node features, GNN for topology information together to make suspicion prediction by global propagation and then designs pruning strategies to remove suspicious nodes.
Key Insight
- Define an expansion graph which creates
organically grown Internet domain all-listsbased on trust transitivity. - Design a semi-supervised suspicion prediction scheme to predict the relation of a node with the targets of compromise.
- Design a new ranking algorithm based on PageRank to combine both global information and the local topology.
- After that, use pruning strategies to remove highly suspicious nodes. There are two strategies.
- Shortest path-based pruning
- Flow-based pruning
5. Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence
Main Idea
The paper designes a specific loss funcation and optimizer on Average Precision (AP) / Areas under precision-recall curves (AUPRC). The optimization method has convergence guarantee.
Key Insight
- Formalize the loss function by approximation.
- Design the stochastic optimization of AP by approximation.
Provement
Step 1: (First approximation: AUPRC-> AP) The AUPRC is an average of the precision weighted by the probability of a given threshold. In that case, for a finite set of test dataset $D={(x_i, y_i), i=1,\dots ,n}$ and the prediction score $h_w(x_i)$ of $x_i$, the AP (average prevision) can approximate AUPRC as the following equation:
\[AP = \frac{1}{n_+}\sum_{i=1}^n I(y_i=1)\frac{\sum_{s=1}^nI(y_s=1)I(h_w(x_s)\geq h_w(x_i))}{\sum_{s=1}^nI(h_w(x_s)\geq h_w(x_i))}\]$I(\cdot)$ is 1 if the input discriminant is true and 0 if it is false.
Step 2:(Second approximation: loss function) The non-continuous indicator function $I(h_w(x_s)\geq h_w(x_i))$ is non-tractable, so a surrogate loss function is necessary to facilitate the optimization algorithm. In the paper, squared hinge loss is used: \(l(w;x_s;x_i)= (max\{m-(h_w(x_i)-h_w(x_s)), 0\})^2\) where $m$ is a margin paramter. In that case, the optimization problem becomes: \(\min_wP(w)= \frac{1}{n_+}\sum_{x_i\in D_+}\frac{-\sum_{s=1}^nI(y_s=1)l(w;x_s;x_i)}{\sum_{s=1}^nl(w;x_s;x_i)}\)
Step 3: (Formalize the objective function) Define: \(g(w;x_j,x_i)=[g_1(w;x_j,x_i),g_2(w;x_j,x_i)]^T=[I(y_s=1)l(w;x_s;x_i), l(w;x_s;x_i)]^T\) \(g_{x_i}(w)=E_{x_j\sim D}[g(w;x_j,x_i)]\) where $g_{x_i}(w): R^d\rightarrow R^2$ and $f(s)=-\frac{s_1}{s_2}:R^2\rightarrow R$. And then rewrite the $P(w)$ by $g(w;x_j,x_i)$ and $f(s)$. \(P(w)=\frac{1}{n_+}\sum_{x_i\in D_+}f(g_{x_i}(w))=E_{x_i\sim D_+}[f(g_{x_i}(w)]\) This function is an instance of two-level stochastic dependent compositional functions.
Step 4: (Calculate the gradient) Let the gradient of $g_{x_i}(w)$ be denoted by $\nabla_wg_{x_i}(w)^T=(\nabla_w[g_{x_i}(w)]1, \nabla_w[g{x_i}(w)]_2)$. \(\begin{align*} \nabla_w P(w)=\frac{1}{n_+}\sum_{x_i\in D_+}\nabla_wg_{x_i}(w)^T\nabla f(g_{x_i}(w)) = \\ \frac{1}{n_+}\sum_{x_i\in D_+} \nabla_wg_{x_i}(w)^T(\frac{-1}{[g_{x_i}(w)]_2},\frac{[g_{x_i}(w)]_1}{([g_{x_i}(w)]_2)^2})^2 \end{align*}\) And then use stochastic samplesw to approximate the quantities.
6. How to Cover up Anomalous Accesses to Electronic Health Records
Main Idea
The paper analyzes the electronic health record (EHR) system by two adversarial attacks (evasion attack and poisoning attack). It shows that the evasion attack is effective while the poisoning attack fails.
Key Insight
- The main difference with the previous works is the way to define the successful attack: all the injected covering accesses are stealthy to the model.
- It tries white-box, gray-box on evasion attack.