Название статьи: Все, что вам нужно, это низкий уровень (ранг): защита от состязательных атак на графы
Цитирование статьи: Негин Энтезари, Саба А. Аль-Сайури, Амирали Дарвишзаде и Эвангелос Э. Папалексакис. 2020. Все, что вам нужно, это низкий уровень (ранг): защита от состязательных атак на графиках. На Тринадцатой международной конференции ACM по веб-поиску и интеллектуальному анализу данных (WSDM ’20), 3–7 февраля 2020 г., Хьюстон, Техас, США. ACM, Нью-Йорк, штат Нью-Йорк, США, 9 страниц. https://doi.org/10.1145/3336191.3371789
1. ОБЗОР:
а. Мотивация:
В области искусственного интеллекта и машинного обучения состязательное машинное обучение — это метод, который пытается обмануть модели машинного обучения, используя ложные данные, с целью вызвать сбой модели машинного обучения. Представление модели с ошибочными или неверными данными во время обучения или внедрение злонамеренно подготовленных данных, чтобы запутать уже обученную модель, являются примерами состязательных атак. Согласно недавнему известному исследованию, в котором изучалось влияние состязательных атак на данные графа, было обнаружено, что методы встраивания графов также подвержены состязательным атакам. Авторы в этой статье исследовали способы предотвращения генеративных состязательных атак на данные графа, поскольку, по их мнению, очень важно разработать алгоритмы анализа графов, которые могут противостоять состязательным атакам, поскольку графы часто используются во многих областях из-за их способности отображать реальные данные. -мировые данные в различных дисциплинах, таких как социальные сети, цитирование и биологические сети. Авторы исследовали особенности возмущений, вносимых моделью NETTACK, чтобы найти соответствующие меры противодействия им. Авторы выбрали эту модель, потому что она оказалась очень эффективной для введения в заблуждение модели графовой сверточной сети и некоторых подходов к классификации узлов, таких как встраивание узлов. Они также представили состязательную атаку низкого ранга под названием LowBlow, которая может ухудшить точность классификации как вложений узлов на основе тензора, так и модели графовой сверточной сети.
б. Основной технический вклад и предыдущая работа, которая привела к этому:
Предыдущее исследование попыток «вакцинировать» сеть:
Слово «вакцинировать» относится к оснащению сети средствами защиты от атак злоумышленников. В одном исследовании сжатие JPEG использовалось для «вакцинации» глубокой нейронной сети, поскольку они предположили, что состязательные атаки создают искажения в высокочастотном диапазоне изображений, которые визуально невозможно обнаружить, и поэтому сжатие JPEG может эффективно их искоренить. Бхагоджи и др. предложил метод защиты, который использует анализ основных компонентов для уменьшения размерности в другом исследовании. В другом исследовании используется декомпозиция по сингулярным значениям и низкоранговая аппроксимация матрицы смежности отдельных пользователей в Amazon и Twitter для выявления странных действий, когда
иметь дело с физическими противниками, при этом основной целью является обнаружение плотного блочного поведения, которое указывает на мошенничество, такое как фальшивые подписчики в Twitter. Есть два типа состязательных атак: уклонение и отравление. При атаках уклонения данные противника обновляются во время тестирования, чтобы обойти результат, а при атаках отравления, тип которых исследуется в этой статье, данные обучения искажаются, и модель классификации переобучается с использованием этих искаженных данных.
Концепции, используемые авторами:
Разложение по единственному числу:
SVD используется для вычисления наилучших приближений ранга r заданной матрицы A. SVD матрицы A вычисляется следующим образом:
Где U и V — ортогональные матрицы, а сигма — неотрицательная диагональная матрица. Аппроксимация ранга r (Ar) матрицы A может быть рассчитана следующим образом:
Здесь:
Ur и Vr — две матрицы, содержащие r верхних сингулярных векторов, а sigma_r — диагональная матрица, содержащая r сингулярных значений. Таким образом, используя SVD, мы можем получить аппроксимацию ранга r любой вещественной матрицы A.
Тензоры:
Тензор — это многомерная матрица. Количество индексов, необходимых для индексации тензора, является его порядком. Предметом исследования являются трехмодовые тензоры.
Используемые методы и исследования, проведенные авторами:
Исследование влияния NETTACK на графические данные:
Авторы использовали модель NETTACK (предложенную Zügner et al.) для создания состязательных атак для нарушения сверточных сетей Graph (GCN). NETTACK создает необнаруживаемые возмущения, накладывая различные ограничения на атаки, чтобы гарантировать сохранение структуры графа и атрибутов узла. При наличии графика G = (A, X), где A — неориентированная матрица смежности, а X — матрица признаков, любые изменения в матрице A называются структурными возмущениями, а любые изменения в X называются возмущениями признаков. Атаки, которые поддерживают распределение степеней графа, считаются необнаруживаемыми, когда речь идет о создании незаметных возмущений структуры, а совместное появление признаков учитывается для создания незаметных возмущений признаков. Авторы исследовали матрицы смежности и признаков до и после атаки, чтобы эмпирически проверить свою интуицию и понять особенности возмущений, вызванных моделью NETTACK. Чтобы показать различия, авторы отобразили сингулярные значения матриц исходного и атакованного графов. На рисунке 1, показанном ниже, показаны сингулярные значения матрицы смежности до и после одной атаки на целевой узел в полулогарифмическом масштабе. Из рисунка видно, что только на более высоких рангах сингулярные значения исходной и атакованной матриц имеют существенную разницу. Затем авторы исследовали сингулярные значения матрицы смежности и признаков для нескольких атак (более одной) и обнаружили, что сингулярные значения довольно похожи на более низких рангах, но различаются на более высоких рангах. Они используют эту идею, чтобы предоставить два метода низкого ранга, которые могут успешно защищаться от NETTACK.
Решения низкого ранга, предложенные авторами для защиты от атак:
Авторы построили оценку низкого ранга для матриц признаков и смежности, извлекая их из их SVD-разложения, чтобы устранить помехи высокого ранга, вызванные NETTACK. Затем GCN был повторно обучен с использованием матриц аппроксимации низкого ранга. Авторы продемонстрировали, что при правильном выборе r оценка ранга-r атакованного графа может повысить производительность GCN и приблизить ее к производительности GCN, обученной на исходном графе. По сути, вычисление SVD графа раскрывает спектр атаки, а также здоровые области графа. Затем авторы сохраняют усеченный SVD, который содержит только верхние k сингулярных значений для графа, а затем восстанавливают граф из него, поскольку они предполагают высокий ранг NETTACK на основе своих экспериментов. Вакцинированный граф является результатом такого усечения.
t-PINE: встраивание узлов на основе тензоров с высокой надежностью
Аль-Сайури и др. в своей статье описали основанный на тензоре подход к встраиванию узлов, который использует тензорную CP-декомпозицию (известную как CANDECOMP/PARAFAC) для захвата отношений между узлами с использованием низкоразмерных скрытых компонентов. В своей статье они оценили производительность t-PINE с встраиванием узлов, но не проверяли его устойчивость в неблагоприятной ситуации. Авторы этой статьи сочли t-PINE подходящим выбором для защиты от возмущений высокого ранга, созданных NETTACK, из-за его внутреннего характера низкого ранга, и поэтому они использовали этот подход в своих экспериментах.
LowBlow — предлагаемая атака Low-Rank:
Изменения в сингулярных числах высокого ранга вызваны сбоями NETTACK, которым можно противодействовать с помощью аппроксимации графа низкого ранга. С другой стороны, атаки низкого ранга все еще могут влиять на данные графа. Чтобы продемонстрировать, влияют ли атаки низкого ранга на данные графа, авторы скорректировали возмущения NETTACK для создания атак низкого ранга, которые могут снизить производительность как GCN, так и t-PINE.
Авторы также продемонстрировали, что модификация LowBlow, чтобы иметь только те ребра, которые поддерживают распределение степеней графа, делает его атакой высокого ранга, похожей на NETTACK.
в. Интересный экспериментальный результат/теоретическое открытие:
Авторы использовали для своих экспериментов крупнейший связанный компонент наборов графических данных Cora-ML, CiteSeer и PoliticalBlogs. Чтобы оценить эффективность предложенной ими защитной меры, авторы вычислили эффективность, используя различные значения ранга r.
График на рис. 2 выше показывает процент целевых узлов, которые были правильно классифицированы для возмущенного графа NETTACK и исходного (чистого) графа для различных аппроксимаций ранга (значения тестируемого ранга r равны 5, 10, 15 и 50) от матрицы признаков и смежности. Как видно из рисунка 2, при атаке матриц полного ранга доля целевых узлов, должным образом классифицированных после атаки, резко снижается. Но доля правильно классифицированных узлов на атакованном графе близка к доле исходного графа при использовании аппроксимации SVD низкого ранга, как видно из рисунка 2. Из графика можно сказать, что при использовании аппроксимации 10-го ранга матриц смежности и признаков (т. е. с использованием только десяти сингулярных значений/векторов) влияние NETTACK может быть значительно уменьшено (аппроксимация ранга 10 дает наилучшие результаты). Аппроксимация ранга 10 может обеспечить надежную аппроксимацию структуры и характеристик графа, а также может «привить» графовые сверточные сети от атак со стороны противника.
Авторы также проверили устойчивость t-PINE к NETTACK и обнаружили, что он довольно устойчив к меньшим размерам встраивания, но по мере увеличения размера устойчивость встраивания также снижается. Кроме того, авторы обнаружили, что LowBlow резко снижает производительность как t-PINE, так и GCN, но LowBlow больше влияет на GCN, чем t-PINE. Авторы также протестировали предложенный ими метод защиты от LowBlow, приняв аппроксимацию графа 10-го ранга, чтобы «привить» его. Из этого эксперимента они заметили, что LowBlow труднее сопротивляться, чем NETTACK, из-за его низкого ранга. Также из результатов можно сделать вывод, что предложенная авторами стратегия «вакцинации» лучше работает на NETTACK, чем на LowBlow, поскольку LowBlow по своей сути является атакой низкого ранга.
2. МОИ МЫСЛИ:
а. Плюсы и проблемы, которые они решают:
я. Враждебные атаки являются серьезной проблемой в области искусственного интеллекта и машинного обучения. Предыдущая работа посвящена проблемам состязательных атак на
модели машинного обучения для разработки стратегий защиты, устойчивых к указанным атакам, однако относительно меньше исследований проводится в области эффектов и смягчения последствий атак злоумышленников на данные графа. Из-за нелинейной структуры сверточных сетей Graph они продемонстрировали огромный успех в задачах, связанных с классификацией узлов, но, несмотря на свой успех, они уязвимы для незначительных помех. Таким образом, это исследование направлено на подробное изучение воздействия состязательных атак на графы и изучение некоторых эффективных механизмов защиты от них. Поскольку графы используются во многих различных областях, таких как социальные сети, цитирование и биологические сети, это исследование затрагивает широкий круг проблем.
II. Авторы исследовали свойства возмущений NETTACK и успешно продемонстрировали, что они вызывают значительные изменения в спектре высокого ранга графа, который коррелирует с низкими сингулярными значениями.
III. Авторы показывают, что при использовании аппроксимации низкого ранга графа модель GCN может значительно противостоять атакам, основанным на концепции, что возмущения Неттака имеют высокий ранг.
IV. Авторы продемонстрировали, что тензорные вложения узлов, которые аппроксимируют низкоранговое представление графа, особенно устойчивы к состязательным атакам, продемонстрировав влияние модели NETTACK, сгенерированной состязательными высокоранговыми атаками, на тензорный подход к встраиванию узлов.
v. Авторы разработали атаку LowBlow, которая изменяет возмущения NETTACK, чтобы воздействовать на низкоранговые компоненты графа. В результате новая атака низкого ранга может ввести в заблуждение как тензорные вложения, так и GCN.
ви. Авторы демонстрируют, что изменение атаки низкого ранга для сохранения распределения степеней графа превращает ее в атаку высокого ранга.
б. Ограничения:
я. В статье исследуется только отравляющий тип состязательных атак для построения защиты от них без исследования типа уклонения от состязательных атак на данные графа.
II. Хотя в исследовании утверждается, что сингулярные значения матриц смежности и признаков до и после возмущений NETTACK довольно похожи на более низких рангах, но различаются на более высоких рангах, возможно, что такое поведение наблюдается не во всех возможных сценариях, и контрпримеры такого предположение может присутствовать. Требуются дополнительные исследования, чтобы определить возможные подводные камни такого предположения и найти возможные способы защиты от атак со стороны противника без таких предположений.
III. В этом исследовании оценивался только один тип подхода к встраиванию узлов на основе тензора. Сравнительное исследование с другими подходами к вложению узлов на основе тензора требуется для лучшей оценки поставленной задачи, поскольку другие подходы к встраиванию узлов на основе тензора теоретически должны обеспечивать аналогичные низкоранговые аппроксимации графа, которые, по мнению авторов, должны быть способен противостоять возмущениям NETTACK.
IV. Исследование касается только состязательных атак, генерируемых NETTACK и LowBlow. Однако не определено, насколько хорошо метод низкоранговой аппроксимации будет противостоять реальным атакам со стороны противника на данные графа.
3. ПОСЛЕДУЮЩИЕ/СЛЕДУЮЩИЕ ШАГИ:
а. Атаки отравления встречаются редко по сравнению с атаками противника типа уклонения. В этой статье только исследуется и делается попытка построить защиту от атак типа отравления на данные графа. Будущая работа может быть предпринята для создания защиты от атак уклонения на данные графа.
б. Исследования могут быть предприняты для определения способов защиты от враждебных атак без предположения, что сингулярные значения матриц смежности и признаков до и после возмущений в результате враждебной атаки довольно схожи на более низких рангах, но различаются только на более высоких рангах.
в. Исследования можно проводить, используя несколько типов подходов к встраиванию узлов на основе тензора, а затем наблюдая, верны ли для них те же результаты или нет. Другие подходы к встраиванию узлов, основанные на тензорах, теоретически должны обеспечивать аналогичные аппроксимации графа низкого ранга, которые можно использовать, чтобы увидеть, обеспечивают ли они устойчивость к возмущениям NETTACK.
д. Это исследование посвящено состязательным атакам, генерируемым NETTACK и LowBlow. Могут быть предприняты дальнейшие исследования для проверки состязательных атак, генерируемых различными другими подходами, и, если возможно, против реальных состязательных атак.
4. ССЫЛКИ:
а. Негин Энтезари, Саба А. Аль-Сайури, Амирали Дарвишзаде и Евангелос Э. Папалексакис. 2020. Все, что вам нужно, это низкий уровень (ранг): защита от состязательных атак на графиках. Материалы 13-й Международной конференции по поиску в Интернете и интеллектуальному анализу данных. Ассоциация вычислительной техники, Нью-Йорк, штат Нью-Йорк, США, 169–177. DOI: https://doi.org/10.1145/3336191.3371789
б. https://www.youtube.com/watch?v=CpD9XlTu3ys
